Trajectory data clustering algorithm based on spatio-temporal pattern
SHI Lukui1,2, ZHANG Yanru1, ZHANG Xin1
1. School of Computer Science and Engineering, Hebei University of Technology, Tianjin 300401, China; 2. Hebei Province Key Laboratory of Big Data Calculation(Hebei University of Technology), Tianjin 300401, China
Abstract：Because the existing trajectory clustering algorithms in the similarity measurement usually used the spatial characteristics as the standards the characteristics lacking the consideration of temporal, a trajectory data clustering algorithm based on spatial-temporal pattern was proposed. The proposed algorithm was based on partition-and-group framework. Firstly, the trajectory feature points were extracted by using the curve edge detection method. Then the sub-trajectory segments were divided according to the trajectory feature points. Finally, the clustering algorithm based on density was used according to the spatio-temporal similarity between sub-trajectory segments. The experimental results show that the trajectory feature points extracted using the proposed algorithm are more accurate to describe the trajectory structure under the premise that the feature points have better simplicity. At the same time, the similarity measurement based on spatio-temporal feature obtains better clustering result by taking into account both spatial and temporal characteristics of trajectory.
[1] PAN J, JIANG Q, SHAO Z. Trajectory clustering by sampling and density[J]. Marine Technology Society Journal, 2014, 48(6):74-85. [2] HUNG C C, PENG W C, LEE W C. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes[J]. The VLDB Journal, 2015, 24(2):169-192. [3] LEE J G, HAN J, WHANG K Y. Trajectory clustering:a partition-and-group framework[EB/OL].[2015-01-13]. http://xueshu.baidu.com/s?wd=paperuri%3A%287e5e7260674abe825b7a245c93edbb10%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D6CE1053AAA540B0B1F600FE0C866E986%3Fdoi%3D10.1.1.76.8098%26rep%3Drep1%26type%3Dpdf&ie=utf-8&sc_us=17938122568389976672. [4] 袁冠,夏士雄,张磊,等.基于结构相似度的轨迹聚类算法[J].通信学报,2011,32(9):103-110.(YUAN G, XIA S X, ZHANG L, et al. Trajectory clustering algorithm based on structural similarity[J]. Journal on Communications, 2011, 32(9):103-110.) [5] 杜国红,徐克虎,杜涛.平面非规则曲线的一种快速识别与匹配算法[J].计算机工程与应用,2007,43(7):81-83.(DU G H, XU K H, DU T. Quick recognizing and matching algorithm for planar irregular curve[J]. Computer Engineering and Applications, 2007, 43(7):81-83.) [6] CHEN J, LEUNG M K, GAO Y. Noisy logo recognition using line segment Hausdorff distance[J]. Pattern Recognition, 2003, 36(4):943-955. [7] BOLLEN J, PEPE A, MAO H. Modeling public mood and emotion:Twitter sentiment and socio-economic phenomena[J]. Computer Science, 2009, 44(12):2365-2370. [8] 刘琴,王恺乐,饶卫雄.不等长时间序列滑窗STS距离聚类算法[J].计算机科学与探索,2015,9(11):1301-1313.(LIU Q, WANG K L, RAO W X. Non-equal time series data clustering algorithm with sliding window STS distance[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(11):1302-1313.) [9] 张延玲,刘金鹏,姜保庆.移动对象子轨迹段分割与聚类算法[J].计算机工程与应用,2009,45(10):65-68.(ZHANG Y L, LIU J P, JIANG B Q. Partition and clustering for sub-trajectories of moving objects[J]. Computer Engineering and Applications, 2009, 45(10):65-68.) [10] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial database with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park:AAAI Press, 1996:226-231. [11] GUDMUNDSSON J, VALLADARES N. A GPU approach to subtrajectory clustering using the Fréchet distance[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(4):924-937. [12] 廖律超,蒋新华,邹复民,等.一种支持轨迹大数据潜在语义相关性挖掘的谱聚类方法[J]. 电子学报,2015,43(5):956-964.(LIAO L C, JIANG X H, ZOU F M, et al. A spectral clustering method for big trajectory data mining with latent semantic correlation[J]. Acta Electronica Sinica, 2015,43(5):956-964.) [13] 龚玺,裴韬,孙嘉,等.时空轨迹聚类方法研究进展[J].地理科学进展,2011,30(5):522-534.(GONG X, PEI T, SUN J, et al. Review of the research progresses in trajectory clustering methods[J]. Progress in Geography, 2011, 30(5):522-534.) [14] ELNEKAVE S, LAST M, MAIMON O. Incremental clustering of mobile objects[C]//Proceedings of the 2007 ACM SIGMOD InternationalConference on Management of Data. New York:ACM, 2007:593-604. [15] YUAN G, SUN P, ZHAO J, et al. A review of moving object trajectory clustering algorithms[EB/OL].[2015-01-09]. https://www.researchgate.net/publication/299434359_A_review_of_moving_object_trajectory_clustering_algorithms.
2017, Vol. 37 
