Publication

Abstract : GPS devices generate huge number of spatial trajectories and understanding common patterns in these trajectories is an open problem. In this paper, Reduced String based Trajectory Clustering Algorithm (RSTCA) for clustering trajectories by transforming trajectories to a string-based representation is proposed. Trajectories are pre-processed and made into equal length by using the Douglas – Peucker algorithm. Spatial grid is generated to map the trajectories which convert trajectories from GPS based representation to string format. N-gram representation identifies sequential patterns in strings and increases the features of trajectories. Both string-based mapping and N-gram representation aid in clustering spatially close trajectories into the same cluster. Singular Value Decomposition (SVD) and t-Distributed Stochastic Neighbour Embedding (t-SNE) are applied on trajectories to reduce the dimensionality of trajectories. The reduced trajectories are clustered using hierarchical clustering by various linkage strategies. Performance analysis of RSTCA is done using Cophenetic Correlation Coefficient, Davies Bouldin Index and Dunn Index. Experimental results demonstrate that RSTCA can cluster trajectories efficiently.