A Systematic Approach to Clustering Whole Trajectories of Mobile Objects in Road Networks

摘要

Most of mobile object trajectory clustering analysis to date has been focused on clustering the location points or sub-trajectories extracted from trajectory data. This paper presents TraceMob, a systematic approach to clustering whole trajectories of mobile objects traveling in road networks. TraceMob as a whole trajectory clustering framework has three unique features. First, we design a quality measure for the distance between two whole trajectories. By quality, we mean that the distance measure can capture the complex characteristics of trajectories as a whole including their varying lengths and their constrained movement in the road network space. Second, we develop an algorithm that transforms whole trajectories in a road network space into multidimensional data points in a euclidean space while preserving their relative distances in the transformed metric space. This transformation enables us to effectively shift the clustering task for whole mobile object trajectories in the complex road network space to the traditional clustering task for multidimensional data in a euclidean space. Third, we develop a cluster validation method for evaluating the clustering quality in both the transformed metric space and the road network space. Extensive experimental evaluation with trajectories generated on real road network maps of different cities shows that TraceMob produces higher quality clustering results and outperforms existing approaches by an order of magnitude.