Graph Similarity-based Hierarchical Clustering of Trajectory Data
B. A. Sabarish, R. Karthi, T. Gireesh Kumar
Abstract
Trajectory is the path traversed by any moving object like animals, human, vehicles and natural phenomenon. Trajectory analysis and clustering are essential to learn the dynamics of movement and pattern of moving objects. This paper proposes to cluster and identify similar trajectories based on paths traversed by moving object. The proposed algorithm has two phases graph generation and clustering. Moving objects generate a trace of GPS points which are converted into a graph, representing spatial regions. Graph generation methodology transforms trajectories into a series of spatial grid numbers and clustering algorithm group trajectories based on similarity measure which are calculated using edge and vertex similarity. Hierarchical clustering is done using graph based similar measures and the resulting clusters are validated using three measures namely Cophenetic Correlation Coefficient, Davies Bouldin Index and Dunn Index. Experimental analysis demonstrates the effectiveness in representation and clustering of trajectories based on graph model.