An anomaly detection algorithm for taxis based on trajectory data mining and online real-time monitoring

doi:10.3969/j.issn.0253-2778.2016.03.010

Abstract

Abstract: Taking the prevention of taxi frauds as a motivating example, an anomalous spatio-temporal trajectory detection method that combines offline mining and online detection was proposed. A city roadmap was partitioned into a grid based on the longitude and latitude, using Pathlet sequences to express taxi trajectories instead of the traditional GPS sequences. Then, K-racial classes’ normal sequences were clustered in the same origin-destination pair from history data sets. The incoming online GPS data was transformed into Pathlet sequences and matched with K-racial classes’ normal sequences. The distance was computed and scored. Distance along with spatial and temporal factors together forms the criterion for determing anomalous taxi trajectories. Finally, based on the real taxi GPS data sets in Beijing area during March, 2011 to May, 2011, experimental results indicate that the proposed method is able to detect online anomalous trajectories efficiently and quickly.

Key words: GPS trajectory, anomalous trajectory detection, pathlet method, spatio-temporal data mining

CLC Number:

TP311

HAN Boyang, WANG Zhaoyang, JIN Beihong. An anomaly detection algorithm for taxis based on trajectory data mining and online real-time monitoring[J]. Journal of University of Science and Technology of China, 2016, 46(3): 247-252.

References

［1］
CHANDOLA V, BANERJEE A, KUMAR V. Anomaly detection a survey[J]. ACM Computing Surveys, 2009, 41(3): 75-79.
[2] VELOSO M, PHITHAKKITNUKOON S, BENTO C. Sensing urban mobility with taxi flow[C]// Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Location-Based Social Networks. Chicago, USA: ACM Press, 2011: 41-44.
[3] ZHU B, HUANG Q, GUIBAS L, et al. Urban population migration pattern mining based on taxi trajectories[C]// Proceedings of the 3rd International Workshop on Mobile Sensing. Springer, 2015, 9142: 172-181.
[4] ZHENG Y, LIU Y C, YUAN J, et al. Urban computing with taxicabs[C]// Proceedings of the 13th International Conference on Ubiquitous Computing. Beijing, China: ACM Press, 2011: 89-98.
[5] YUAN J, ZHENG Y, ZHANG C Y, et al. T-drive: Driving directions based on taxi trajectories[C]// Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. San Jose, USA: ACM Press, 2010: 99-108.
[6] LEE J G, HAN J W, WHANG K Y. Trajectory clustering a partition-and-group framework[C]// Proceedings of the SIGMOD International Conference on Management of Data. Beijing, China: ACM Press, 2007: 593-604.
[7] GE Y, XIONG H, LIU C R, et al. A taxi driving fraud detection system[C]// Proceedings of the 11th International Conference on Data Mining. Vancouver, Canada: IEEE Press, 2011: 181-190.
[8] FU Z Y, HU W M, TAN T N. Similarity based vehicle trajectory clustering and anomaly detection[C]// IEEE International Conference on Image Processing. Beijing, China: IEEE Press, 2005, 2: 602-605.
[9] ZHANG D, LI N, ZHOU Z H, et al. iBAT: Detecting anomalous taxi trajectories from GPS traces[C]// Proceedings of the 13th International Conference on Ubiquitous Computing. Beijing, China: ACM Press, 2011: 99-108.
[10] CHEN C, ZHANG D Q, CASTRO P S, et al. Real-time detection of anomalous taxi trajectories from GPS traces[A]// Mobile and Ubiquitous Systems Computing, Networking, and Services. Berlin Heidelberg: Springer, 2012: 63-74.
[11] GE Y, XIONG H, ZHOU Z H, et al. Top-eye Top-k evolving trajectory outlier detection[C]// Proceedings of the 19th ACM International Conference on Information and Knowledge Management. Toronto, Canada: ACM Press, 2010: 1733-1736.
[12] 胡佳峰. 基于轨迹数据的事件检测技术研究[D].硕士学位论文, 中国科学院大学, 2014.
[13] 袁晶. 大规模轨迹数据的检索、挖掘及应用[D].博士学位论文, 中国科学技术大学, 2012.
[14] CHEN C, ZHANG D Q, CASTRO P S, et al. iBOAT: Isolation-based online anomalous trajectory detection[J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(2): 806-818.
[15] SUN L, ZHANG D, CHEN C, et al. Real time anomalous trajectory detection and analysis[J]. Mobile Networks and Applications, 2013, 18(3) 341-356.
[16] CHEN C, SU H, HUANG Q, et al. Pathlet learning for compressing and planning trajectories[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Orlando, USA: ACM, 2013: 392-395.
[17] LEE A J T, CHEN Y A, IP W C. Mining frequent trajectory patterns in spatial-temporal databases[J]. Information Sciences, 2009, 179(13): 2218-2231.
[18] CHEN L, NG R. On the marriage of Lp-norms and edit distance[C]//Proceedings of the 30th International Conference on Very Large Databases. Toronto, Canada: VLDB Endowment, 2004: 792-803.
[19] HAN B, LIU L, OMIECINSKI E. Neat Road network aware trajectory clustering[C]// 32nd International Conference on Distributed Computing Systems. Macau, China: IEEE, 2012: 142-151.

[1]	WU Jiayu, LI Yongkun, XU Yinlong. A read/write balanced high-performance key-value store [J]. Journal of University of Science and Technology of China, 2020, 50(6): 825-831.
[2]	CAI Yong, CHEN Hongmei,. A parallel algorithm for constructing concept lattice based on hierarchical concept under MapReduce [J]. Journal of University of Science and Technology of China, 2018, 48(4): 275-283.
[3]	WANG Yong, HUANG Zhiqiu, WEI Liangfen, LU Guifu. Locating failure-inducing combinations based on fault forest [J]. Journal of University of Science and Technology of China, 2018, 48(1): 28-34.
[4]	XU Wanru, YANG Panlong. Mobile user propagation capability evaluation and coverage optimization algorithm [J]. Journal of University of Science and Technology of China, 2017, 47(7): 569-574.
[5]	LI Xiaolin,SUN Yue, LIU Yang. Forecasting Shanghai stock index using FTS model based on SVM-modify [J]. Journal of University of Science and Technology of China, 2016, 46(3): 238-246.
[6]	YIN Chao, WANG Jianzong, LV Haitao, CUI Zongmin, CHENG Lianglun, LI Tongfang, LIU Yan. BDCode: An erasure code algorithm for big data storage systems [J]. Journal of University of Science and Technology of China, 2016, 46(3): 188-199.
[7]	TANG Jiufei,LI He,YU Junqing. Research on stream program task scheduling and cache optimization for X86 multi-core processor [J]. Journal of University of Science and Technology of China, 2016, 46(3): 200-207.
[8]	HUANG Dongmei, SUN Le, ZHAO Danfeng. A composite index strategy for big marine data based on adaptive method of data merging strategy [J]. Journal of University of Science and Technology of China, 2015, 45(10): 813-821.
[9]	ZHU Meiling, WANG Xiongbin, ZHANG Shouli,LIU Chen, HAN Yanbo. Instant traveling companion discovery based on large scale streaming ANPR data [J]. Journal of University of Science and Technology of China, 2016, 46(1): 47-55.
[10]	HUANG Dongmei, SUN Le, SHI Shaohua, SU Cheng, ZHAO Danfeng. Tabular-oriented data model and its query issues [J]. Journal of University of Science and Technology of China, 2016, 46(1): 56-65.
[11]	HU Baoli, YOU Jinguo, ZHOU Cuilian, WANG Yang, CUI Hongbo. An efficient weighted graph aggregation algorithm [J]. Journal of University of Science and Technology of China, 2016, 46(3): 180-187.
[12]	CHANG Li, MA Chengxue, GAO Lifu. Corn-counting method based on photoelectric signal [J]. Journal of University of Science and Technology of China, 2015, 45(4): 275-279.
[13]	JI Duo, BI Chen, CAI Dongfeng. A latent semantic analysis classification technique based on optimized categorization information [J]. Journal of University of Science and Technology of China, 2015, 45(4): 314-320.