Frequent trajectory recognition of taxi trajectory data

doi:10.13474/j.cnki.11-2246.2021.341

Abstract

Abstract: In order to identify the frequent paths in urban traffic, this paper proposes a method of frequent trajectory identification for taxi trajectory data. The method firstly compresses the trajectory data to reduce the computational complexity. Then calculates the trajectory similarity measure based on longest common subsequence and dynamic time warping algorithm, and generates a distance matrix by using the calculated similarity between trajectories. Finally, the generated distance matrix is clustered with HDBSCAN algorithm to get frequent trajectories. Two areas in Xiamen Island are selected for experimental analysis. The results show that the proposed method can identify the frequent trajectories in the trajectory data set and obtain the frequent paths between urban areas, which is helpful for road planning, path optimization and recommendation, traffic management and other applications.

Key words: trajectory data, trajectory compression, trajectory similarity, clustering group, frequent trajectory

CLC Number:

P208

WU Qunyong, WANG Xiangjian. Frequent trajectory recognition of taxi trajectory data[J]. Bulletin of Surveying and Mapping, 2021, 0(11): 70-75.

References

[1] CHEN G, CHEN B, YU Y. Mining frequent trajectory patterns from GPS tracks[C]//Proceedings of 2010 International Conference on the Computational Intelligence and Software Engineering.[S.l.]:IEEE, 2010:1-6.
[2] 张健钦, 仇培元, 杜明义. 基于时空轨迹数据的出行特征挖掘方法[J]. 交通运输系统工程与信息, 2014,14(6):72-78.
[3] 向隆刚, 龚健雅, 吴涛, 等. 一种面向Stop/Move抽象的轨迹时空关系[J]. 武汉大学学报(信息科学版), 2014,39(8):956-962.
[4] 王亮, 胡琨元, 库涛, 等. 基于多尺度空间划分与路网建模的城市移动轨迹模式挖掘[J]. 自动化学报, 2015,41(1):47-58.
[5] SRIKANT R, AGRAWAL R. Mining sequential patterns:generalizations and performance improvements[C]//Proceedings of the 5th International Conference on Extending Database Technology:Advances in Database Technology. Avignon:[s.n.], 1996:3-17.
[6] PEI J, HAN J, MORTAZAVI-ASL B, et al. Mining sequential patterns by pattern-growth:the PrefixSpan approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004,16(11):1424-1440.
[7] CAO H, MAMOULIS N, CHEUNG D. Mining frequent spatiotemporal sequential patterns[C]//Proceedings of the 5th IEEE Int Conf on Data Mining.[S.l.]:IEEE, 2005:82-89.
[8] YUAN H, ZHANG Y, WANG C. A novel trajectory pattern learning method based on sequential pattern mining[C]//Proceedings of the 2nd International Conference on Innovative Computing, Information and Control. Kumamoto:IEEE, 2007.
[9] GIANNOTTI F, NANNI M, PINELLI F, et al. Trajectory pattern mining[C]//Proceedings of the 13th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York:ACM, 2007:330-339.
[10] MONREALE A, PINELLI F, TRASARTI R, et al. Where next:a location predictor on trajectory pattern mining[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris:ACM, 2009.
[11] ZHANG C, HAN J, SHOU L, et al. Splitter:mining fine-grained sequential patterns in semantic trajectories[J]. Proceedings of the VLDB Endowment, 2014,7(9):769-780.
[12] GRAHNE G, ZHU J. Fast algorithms for frequent itemset mining using FP-Trees[J]. IEEE Transactions on Knowledge and Data Engineering, 2005,17(10):1347-1362.
[13] PYUN G, YUN U, RYU K H. Efficient frequent pattern mining based on Linear Prefix Tree[J]. Knowledge-Based Systems, 2014,55:125-139.
[14] GEETHA P, RAMARAJ E. Tree based space partition of trajectory pattern mining for frequent item sets[J]. Australian Journal of Basic and Applied Sciences, 2017,10(2):250-261.
[15] CAMPELLO, JGB R, MOULAVI D, et al. Density-based clustering based on hierarchical density estimates[C]//Proceedings of 2013 Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin:Springer, 2013.
[16] MCINNES L, HEALY J. Accelerated hierarchical density based clustering[C]//IEEE International Conference on Data Mining Workshops (ICDMW). New Orleans, IEEE, 2017:33-42.
[17] MCINNES L, HEALY J, ASTELS S. Hdbscan:hierar-chical density based clustering[J]. The Journal of Open Source Software, 2017,2(11):205.