Review of spatio-temporal trajectory sequence pattern mining methods

doi:10.11772/j.issn.1001-9081.2020101571

Abstract

Abstract: With the rapid development of global positioning technology and mobile communication technology, huge amounts of trajectory data appear. These data are true reflections of the moving patterns and behavior characteristics of moving objects in the spatio-temporal environment, and they contain a wealth of information which carries important application values for the fields such as urban planning, traffic management, service recommendation, and location prediction. And the applications of spatio-temporal trajectory data in these fields usually need to be achieved by sequence pattern mining of spatio-temporal trajectory data. Spatio-temporal trajectory sequence pattern mining aims to find frequently occurring sequence patterns from the spatio-temporal trajectory dataset, such as location patterns (frequent trajectories, hot spots), activity periodic patterns, and semantic behavior patterns, so as to mine hidden information in the spatio-temporal data. The research progress of spatial-temporal trajectory sequence pattern mining in recent years was summarized. Firstly, the data characteristics and applications of spatial-temporal trajectory sequence were introduced. Then, the mining process of spatial-temporal trajectory patterns was described:the research situation in this field was introduced from the perspectives of mining location patterns, periodic patterns and semantic patterns based on spatial-temporal trajectory sequence. Finally, the problems existing in the current spatio-temporal trajectory sequence pattern mining methods were elaborated, and the future development trends of spatio-temporal trajectory sequence pattern mining method were prospected.

Key words: spatio-temporal trajectory data, trajectory sequence pattern mining, location pattern, periodic pattern, semantic pattern

摘要： 在全球定位、移动通信技术迅速发展的背景下涌现出了海量的时空轨迹数据，这些数据是对移动对象在时空环境下的移动模式和行为特征的真实写照，蕴含了丰富的信息，这些信息对于城市规划、交通管理、服务推荐、位置预测等领域具有重要的应用价值，而时空轨迹数据在这些领域的应用通常需要通过对时空轨迹数据进行序列模式挖掘才能得以实现。时空轨迹序列模式挖掘旨在从时空轨迹数据集中找出频繁出现的序列模式，例如：位置模式（频繁轨迹、热点区域）、活动周期模式、语义行为模式，从而挖掘时空数据中隐藏的信息。总结近年来时空轨迹序列模式挖掘的研究进展，先介绍时空轨迹序列的数据特点及应用，再描述时空轨迹模式的挖掘过程：从基于时空轨迹序列来挖掘位置模式、周期模式、语义模式这三个方面来介绍该领域的研究情况，最后阐述现有时空轨迹序列模式挖掘方法存在的问题，并展望时空轨迹序列模式挖掘方法未来的发展趋势。

关键词: 时空轨迹数据, 轨迹序列模式挖掘, 位置模式, 周期模式, 语义模式

CLC Number:

TP311

KANG Jun, HUANG Shan, DUAN Zongtao, LI Yixiu. Review of spatio-temporal trajectory sequence pattern mining methods[J]. Journal of Computer Applications, 2021, 41(8): 2379-2385.

康军, 黄山, 段宗涛, 李宜修. 时空轨迹序列模式挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2021, 41(8): 2379-2385.

References

[1] 许佳捷, 郑凯, 池明旻, 等. 轨迹大数据:数据、应用与技术现状[J]. 通信学报,2015,36(12):97-105.(XU J J,ZHENG K, CHI M M,et al. Trajectory big data:data,applications and techniques[J]. Journal on Communications, 2015, 36(12):97-105.)
[2] LIU X,GONG L,GONG Y X,et al. Revealing travel patterns and city structure with taxi trip data[J]. Journal of Transport Geography,2015,43:78-90.
[3] MAO F,JI M H,LIU T. Mining spatiotemporal patterns of urban dwellers from taxi trajectory data[J]. Frontiers of Earth Science, 2016,10(2):205-221.
[4] HUANG W,LI S N. An approach for understanding human activity patterns with the motivations behind[J]. International Journal of Geographical Information Science,2019,33(2):385-407.
[5] CUI J X,LIU F,JANSSENS D,et al. Detecting urban road network accessibility problems using taxi GPS data[J]. Journal of Transport Geography,2016,51:147-157.
[6] ANDRIENKO N,ANDRIENKO G,RINZIVILLO S. Leveraging spatial abstraction in traffic analysis and forecasting with visual analytics[J]. Information Systems,2016,57:172-194.
[7] TU W,CAO R,YUE Y,et al. Spatial variations in urban public ridership derived from GPS trajectories and smart card data[J]. Journal of Transport Geography,2018,69:45-57.
[8] KONG X J,XIA F,WANG J Z,et al. Time-location-relationship combined service recommendation based on taxi trajectory data[J]. IEEE Transactions on Industrial Informatics,2017,13(3):1202-1212.
[9] ZHANG S,TANG J J,WANG H X,et al. Revealing intra-urban travel patterns and service ranges from taxi trajectories[J]. Journal of Transport Geography,2017,61:72-86.
[10] SUN Y R,FAN H C,BAKILLAH M,et al. Road-based travel recommendation using geo-tagged images[J]. Computers, Environment and Urban Systems,2015,53:110-122.
[11] TSAI C Y,LAI B H. A location-item-time sequential pattern mining algorithm for route recommendation[J]. Knowledge-Based Systems,2015,73:97-110.
[12] CHEN C,MA J T,SUSILO Y,et al. The promises of big data and small data for travel behavior(aka human mobility)analysis[J]. Transportation Research Part C:Emerging Technologies,2016, 68:285-299.
[13] CHEN M,YU X H,LIU Y. Mining moving patterns for predicting next location[J]. Information Systems,2015,54:156-168.
[14] WU R Z,LUO G C,SHAO J M,et al. Location prediction on trajectory data:a review[J]. Big Data Mining and Analytics, 2018,1(2):108-127.
[15] LEI P R. A framework for anomaly detection in maritime trajectory behavior[J]. Knowledge and Information Systems,2016,47(1):189-214.
[16] JONIETZ D,BUCHER D. Continuous trajectory pattern mining for mobility behaviour change detection[C]//Proceedings of 14th International Conference on Location Based Services, LNGC. Cham:Springer,2018:211-230.
[17] KARSOUM S,GRUENWALD L,LEAL E. Impact of trajectory segmentation on discovering trajectory sequential patterns[C]//Proceedings of the 2018 IEEE International Conference on Big Data. Piscataway:IEEE,2018:3432-3441.
[18] ZHANG Y L,PENG P F,LIU J S,et al. AIS data oriented ships' trajectory mining and forecasting based on trajectory delimiter[C]//Proceedings of the 10th International Conference on Intelligent Human-Machine Systems and Cybernetics. Piscataway:IEEE,2018:269-273.
[19] YU W H. Discovering frequent movement paths from taxi trajectory data using spatially embedded networks and association rules[J]. IEEE Transactions on Intelligent Transportation Systems,2019,20(3):855-866.
[20] ENAMI S, SHIOMOTO K. Spatio-temporal human mobility prediction based on trajectory data mining for resource management in mobile communication networks[C]//Proceedings of the IEEE 20th International Conference on High Performance Switching and Routing. Piscataway:IEEE,2019:1-6.
[21] WANG L,HU K Y,KU T,et al. Mining frequent trajectory pattern based on vague space partition[J]. Knowledge-Based Systems,2013,50:100-111.
[22] CHEN Y,YUAN P S,QIU M,et al. An indoor trajectory frequent pattern mining algorithm based on vague grid sequence[J]. Expert Systems with Applications,2019,118:614-624.
[23] ZHAO P X,QIN K,YE X Y,et al. A trajectory clustering approach based on decision graph and data field for detecting hotspots[J]. International Journal of Geographical Information Science,2017,31(6):1101-1127.
[24] LUO T,ZHENG X W,XU G L,et al. An improved DBSCAN algorithm to detect stops in individual trajectories[J]. ISPRS International Journal of Geo-Information,2017,6(3):No. 63.
[25] SHAW A A,GOPALAN N P. Finding frequent trajectories by clustering and sequential pattern mining[J]. Journal of Traffic and Transportation Engineering (English Edition),2014,1(6):393-403.
[26] 王亮, 胡琨元, 库涛, 等. 随机采样移动轨迹时空热点区域发现及模式挖掘[J]. 吉林大学学报(工学版),2015,45(3):913-920. (WANG L, HU K Y, KU T, et al. Discovering spatiotemporal hot spot region and mining patterns from moving trajectory random sampling[J]. Journal of Jilin University (Engineering and Technology Edition),2015,45(3):913-920.)
[27] YIN F J,LI X,YAO C L,et al. Mining frequent spatio-temporal items in trajectory data[J]. International Journal of Database Theory and Application,2015,8(4):149-156.
[28] HUANG Q Y,LI Z L,LI J,et al. Mining frequent trajectory patterns from online footprints[C]//Proceedings of 7th ACM SIGSPATIAL International Workshop on GeoStreaming. New York:ACM,2016:No. 10.
[29] 王亮, 胡琨元, 库涛, 等. 基于多尺度空间划分与路网建模的城市移动轨迹模式挖掘[J]. 自动化学报,2015,41(1):47-58. (WANG L, HU K Y, KU T, et al. Mining urban moving trajectory patterns based on multi-scale space partition and road network modeling[J]. Acta Automatica Sinica,2015,41(1):47-58.)
[30] WANG T B,ZHANG D Q,ZHOU X S,et al. Mining personal frequent routes via road corner detection[J]. IEEE Transactions on Systems,Man,and Cybernetics:Systems,2016,46(4):445-458.
[31] BERMINGHAM L, LEE I. Mining distinct and contiguous sequential patterns from large vehicle trajectories[J]. KnowledgeBased Systems,2020,189:No. 105076.
[32] ZHANG D Z,LEE K,LEE I. Hierarchical trajectory clustering for spatio-temporal periodic pattern mining[J]. Expert Systems with Applications,2018,92:1-11.
[33] ZHANG D Z,LEE K,LEE I. Mining hierarchical semantic periodic patterns from GPS-collected spatio-temporal trajectories[J]. Expert Systems with Applications,2019,122:85-101.
[34] YANG W,LU W,AI T H,et al. Cycle periodic behavior detection and sports place extraction using crowdsourced running trace data[C]//Proceedings of the 26th International Conference on Geoinformatics. Piscataway:IEEE,2018:1-5.
[35] SHI T T,JI G L,LIU Y,et al. Mining group periodic moving pattern from spatio-temporal trajectories[C]//Proceedings of the 7th International Conference on Advanced Cloud and Big Data. Piscataway:IEEE,2019:108-113.
[36] 李海. 基于GPS轨迹的周期模式发现[J]. 电子设计工程, 2015,23(21):24-27.(LI H. Periodic pattern mining based on GPS trajectories[J]. Journal of Electronic Design Engineering, 2015,23(21):24-27.)
[37] CHEN X P,SHI D X,ZHAO B H,et al. Periodic pattern mining based on GPS trajectories[C]//Proceedings of the 2016 International Symposium on Advances in Electrical,Electronics and Computer Engineering. Paris:Atlantis Press, 2016:181-187.
[38] YUAN G,ZHAO J,XIA S X,et al. Multi-granularity periodic activity discovery for moving objects[J]. International Journal of Geographical Information Science,2017,31(3):435-462.
[39] ZHOU K C,TIAN Z S,YANG Y W. Periodic pattern detection algorithms for personal trajectory data based on spatiotemporal multi-granularity[J]. IEEE Access,2019,7:99683-99693.
[40] CHEN C C,KUO C H,PENG W C. Mining spatial-temporal semantic trajectory patterns from raw trajectories[C]//Proceedings of the 2015 IEEE International Conference on Data Mining Workshop. Piscataway:IEEE,2015:1019-1024.
[41] COMITO C,FALCONE D,TALIA D. Mining human mobility patterns from social geo-tagged data[J]. Pervasive and Mobile Computing,2016,33:91-107.
[42] 郭黎敏, 高需, 武斌, 等. 基于停留时间的语义行为模式挖掘[J]. 计算机研究与发展,2017,54(1):111-122.(GUO L M, GAO X,WU B,et al. Discovering common behavior using staying duration on semantic trajectory[J]. Journal of Computer Research and Development,2017,54(1):111-122.)
[43] WAN C C,ZHU Y M,YU J D,et al. SMOPAT:mining semantic mobility patterns from trajectories of private vehicles[J]. Information Sciences,2018,429:12-25.
[44] CAI G C,LEE K,LEE I. Itinerary recommender system with semantic trajectory pattern mining from geo-tagged photos[J]. Expert Systems with Applications,2018,94:32-40.
[45] CAI G C,LEE K,LEE I. Mining semantic trajectory patterns from geo-tagged data[J]. Journal of Computer Science and Technology,2018,33(4):849-862.