吉林大学学报(工学版) ›› 2014, Vol. 44 ›› Issue (6): 1764-1770.doi: 10.13229/j.cnki.jdxbgxb201406035

Previous Articles     Next Articles

Regular route mining algorithm based on GPS trajectories

HE Wen1, 2, LI De-yi1, 2, AN Li-feng1, ZHANG Tian-lei1, GUO Mu1, CHEN Gui-sheng2   

  1. 1.Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
    2.Institute of Electronic System Engineering of China, Beijing 100840, China
  • Received:2013-04-27 Online:2014-11-01 Published:2014-11-01

Abstract:

Based on users' historical trajectory data, users' regular routes were mined and extracted. A concept of support route was defined after route pre-processing and grouping. A regular route mining algorithm was proposed based on the support score. A feature of Regular Stop Rate (RSR) was used to improve the accuracy of the transportation mode recognition. The effectiveness of the approach was validated based on the GPS data of 178 users over four years. A real user study was also performed among 37 users. The experiment results demonstrate that the algorithm can effectively extract the regular routes and is robust to slight disturbance in trajectory data.

Key words: artificial intelligent, trajectory mining, regular routes, transportation mode, location based service

CLC Number: 

  • TP18
[1] 袁冠,夏士雄,张磊,等. 基于结构相似度的轨迹聚类算法[J].通信学报,2011, 32(9): 103-110. Yuan Guan, Xia Shi-xiong, Zhang Lei, et al. Trajectory clustering algorithm based on structural similarity[J]. Journal on Communications, 2011, 32(9): 103-110.
[2] Lee J G, Han J, Li X, et al. Mining discriminative patterns for classifying trajectories on road networks[J]. IEEE Trans Knowledge and Data Eng, 2011, 23(5): 713-726.
[3] 赵越,刘衍珩,余雪岗,等,基于模式挖掘与匹配的移动轨迹预测方法[J]. 吉林大学学报:工学版,2008, 38(5):1125-1130. Zhao Yue, Liu Yan-heng, Yu Xue-gang, et al. Method for mobile path prediction based on pattern mining and matching[J]. Journal of Jilin University (Engineering and Technology Edition),2008,38(5):1125-1130.
[4] Chang K, Wei L, Yeh M Y, et al. Discovering personalized routes from trajectories[C]∥Pro 3rd ACM Sigspatial International Workshop on Location-Based Social Networks,New York, 2011:33-40.
[5] Chen L, Lü M, Ye Q, et al. A personal route prediction system based on trajectory data mining[J]. Information Sciences, 2011,181(7): 1264-1284.
[6] Zheng J, Ni L. An unsupervised framework for sensing individual and cluster behavior patterns from human mobile data[C]∥Pro 2012 ACM Conf on Ubiquitous Computing, New York, 2012:153-162.
[7] Farrahi K, Daniel G. What did you do today? Discovering daily routines from large-scale mobile data[C]∥Pro of the 16th ACM Conference on Multimedia, New York, 2008:849-852.
[8] Gidofalvi G, Pedersen T B. Mining long, sharable patterns in trajectories of moving objects[J]. GeoInformatica,2009,13(1):27-55.
[9] 郭黎敏,丁治明,胡泽林,等. 基于路网的不确定性轨迹预测[J]. 计算机研究与发展,2010, 47(1):104-112. Guo Li-min, Ding Zhi-ming, Hu Ze-lin, et al. Uncertain path prediction of moving objects on road networks[J]. Journal of Computer Research and Development,2010,47(1):104-112.
[10] Lee J G, Han J, Whang K Y. Trajectory clustering: a partition-and-group framework[C]∥Pro of the 2007 ACM SIGMOD International Conference on Management of Data, New York, 2007:593-604.
[11] Zheng Y, Li Q, Chen Y, et al. Understanding mobility based on GPS data[C]∥Pro of ACM Conference on Ubiquitous Computing, New York, 2008: 312-321.
[12] Zheng Y, Zhang L, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories[C]∥Pro of International Conference on World Wild Web, New York, 2009:791-800.
[13] Yuan J, Zheng Y, Xie X, et al. T-drive: enhancing driving directions with taxi drivers' intelligence[J]. IEEE Transactions on Knowledge and Data Engineering,2013,25(1):220-232.
[14] Zheng Y, Xie X, Ma W. GeoLife: a collaborative social networking service among user, location and trajectory[J]. IEEE Data Engineering Bulletin,2010,33(2):32-40.
[1] ZHAO Wei, QU Hui-yan. Fast collision detection algorithm based on Cloud Map-Reduce model [J]. 吉林大学学报(工学版), 2016, 46(2): 578-584.
[2] WU Jun-wei, ZHU Yun-long, KU Tao, WANG Liang. Hot routes detection algorithm based on grid clustering [J]. 吉林大学学报(工学版), 2015, 45(1): 274-282.
[3] WANG Dan, HAN Hui-rui, TIAN Song, ZANG Xue-bai, SONG Bing-qiang. Object recognition and location based on tree part-based model [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 346-349.
[4] PAN Hong-jun, SUN Ji-gui . Formalized model of multiagent software system based on OOAPN model
[J]. 吉林大学学报(工学版), 2008, 38(05): 1120-1124.
[5] Liu Jie,Sun Ji-gui,Li Hong-jian,Pan Zuo-feng,Wang Chang-bin . Setup of BP ANNbased crash sensing algorithm [J]. 吉林大学学报(工学版), 2008, 38(02): 414-0418.
[6] Zhou Chun-guang,Qu Peng-cheng,Wang Xi,Wang Jian-yu,Wang Zhe . DSNE:a new dynamic social network analysis algorithm [J]. 吉林大学学报(工学版), 2008, 38(02): 408-0413.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!