一种基于轨迹大数据离线挖掘与在线实时监测的出租车异常轨迹检测算法

doi:10.3969/j.issn.0253-2778.2016.03.010

中国科学技术大学学报 ›› 2016, Vol. 46 ›› Issue (3): 247-252.DOI: 10.3969/j.issn.0253-2778.2016.03.010

• 论著 • 上一篇

一种基于轨迹大数据离线挖掘与在线实时监测的出租车异常轨迹检测算法

韩博洋，汪兆洋，金蓓弘

中国科学院软件所软件工程技术研究开发中心，北京 100190

收稿日期:2015-09-12 修回日期:2015-12-29 接受日期:2015-12-29 出版日期:2015-12-29 发布日期:2015-12-29
通讯作者: 金蓓弘
作者简介:韩博洋，男，1993年生，硕士生. 研究方向：数据挖掘. E-mail: hanboyang15@otcaix.iscas.ac.cn

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

HAN Boyang, WANG Zhaoyang, JIN Beihong

Research and Development Center of Software Engineering and Technology, Institute of Software Chinese Academy of Sciences, Beijing 100190, China

Received:2015-09-12 Revised:2015-12-29 Accepted:2015-12-29 Online:2015-12-29 Published:2015-12-29

摘要/Abstract

摘要： 以防止出租车欺诈绕路为例，提出一种基于出租车GPS时空轨迹数据离线挖掘与在线实时检测相结合的异常轨迹检测算法，获得快速反馈实时检测的结果.首先，将路网地图进行网格化切分并编号，用Pathlet方法优化常用的以GPS点组成的轨迹序列，并将轨迹通过匹配、补全等处理变换为Pathlet序列.然后，从大量出租车历史数据中，获得轨迹的Pathlet序列，并聚类得到起点与终点之间正常的K类轨迹.当实时轨迹需要被检测时，便与K类正常轨迹进行匹配，只需计算两段Pathlet序列的编辑距离，并同时考量时间和空间两个维度设定合理阈值，判断是否抛出异常.最后，基于北京地区2011年3月到5月出租车GPS轨迹的真实数据集进行了大量实验，对比了相关工作，印证了所提出算法的有效性和高效性.

关键词: GPS轨迹, 异常轨迹检测, Pathlet方法, 时空数据挖掘

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

中图分类号:

TP311

韩博洋，汪兆洋，金蓓弘. 一种基于轨迹大数据离线挖掘与在线实时监测的出租车异常轨迹检测算法[J]. 中国科学技术大学学报, 2016, 46(3): 247-252.

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.

参考文献

［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]	吴加禹，李永坤，许胤龙. 一种读写均衡的高性能键值存储系统[J]. 中国科学技术大学学报, 2020, 50(6): 825-831.
[2]	蔡勇，陈红梅，. MapReduce环境下基于概念分层的概念格并行构造算法[J]. 中国科学技术大学学报, 2018, 48(4): 275-283.
[3]	王勇，黄志球，韦良芬，卢桂馥. 基于故障森林的组合测试故障定位研究[J]. 中国科学技术大学学报, 2018, 48(1): 28-34.
[4]	徐婉茹，杨盘隆. 移动广告用户传播能力评价与覆盖优化算法[J]. 中国科学技术大学学报, 2017, 47(7): 569-574.
[5]	李小琳，孙玥，刘洋. 基于SVM修正的模糊时间序列模型在沪指预测中的应用[J]. 中国科学技术大学学报, 2016, 46(3): 238-246.
[6]	殷超，王健宗，吕海涛，崔宗敏，程良伦，李同芳，刘妍. BDCode: 一种面向大数据存储系统的纠删码算法[J]. 中国科学技术大学学报, 2016, 46(3): 188-199.
[7]	唐九飞，李鹤，于俊清. 面向X86多核处理器的数据流程序任务调度与缓存优化[J]. 中国科学技术大学学报, 2016, 46(3): 200-207.
[8]	黄冬梅，孙乐，赵丹枫. 基于ADMD融合策略的海洋大数据索引技术研究[J]. 中国科学技术大学学报, 2015, 45(10): 813-821.
[9]	朱美玲，王雄斌，张守利，刘晨，韩燕波. 基于大规模流式车牌识别数据的即时伴随车辆发现[J]. 中国科学技术大学学报, 2016, 46(1): 47-55.
[10]	黄冬梅，孙乐，石少华，苏诚，赵丹枫. 面向Tabular库的数据模型及其查询问题[J]. 中国科学技术大学学报, 2016, 46(1): 56-65.
[11]	胡宝丽，游进国，周翠莲，王洋，崔红波. 一种有效的加权图聚集算法[J]. 中国科学技术大学学报, 2016, 46(3): 180-187.
[12]	常礼，马成学，高理富. 基于光电信号的玉米粒计数方法的研究[J]. 中国科学技术大学学报, 2015, 45(4): 275-279.
[13]	季铎，毕臣，蔡东风. 基于类别信息优化的潜在语义分析分类技术[J]. 中国科学技术大学学报, 2015, 45(4): 314-320.

一种基于轨迹大数据离线挖掘与在线实时监测的出租车异常轨迹检测算法

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价