异常轨迹数据预警与预测关键技术综述

doi:10.16182/j.issn1004731x.joss.201711002

摘要/Abstract

摘要： 重大突发事件的事后处置已经愈加无法满足当前社会的迫切需求,急于需要向事前异常行为的预警预测转型。传感器网络与定位技术的快速发展与普及,为时空轨迹数据挖掘奠定了基础。围绕异常轨迹预警预测挖掘这一核心目的,对异常轨迹聚类识别与轨迹预测的国内外研究现状和进展进行了理论梳理、剖析,综述了相关算法在城市异常轨迹数据预警预测中的应用,指出了所面临的挑战和进一步的发展方向,为该领域的进一步研究提供参考。

关键词: 时空轨迹, 异常行为, 聚类, 预测

Abstract: The ex-post disposition of a major incident, which is expected to transform into prediction and precaution of abnormal behavior, is increasingly unable to meet the urgent needs of the society.Therapid development and popularization of sensor network and positioning technology lay the foundation for mining spatial-temporal trajectory data. With the key objective of prediction and precaution of abnormal trajectory based on big data mining, the future research directions and prospects on trajectory clustering and recognitionareanalyzed, discussed and elaboratedinthis paper.Temporal trajectory prediction applied in prediction and precaution of abnormal spatial-temporal trajectory is also presented, providing a reference for further research on this field.

Key words: spatial-temporal trajectory, abnormal behavior, clustering, prediction

中图分类号:

TP311

仇功达, 何明, 杨杰, 曹玉婷, 孙继红. 异常轨迹数据预警与预测关键技术综述[J]. 系统仿真学报, 2017, 29(11): 2608-2617.

Qiu Gongda, He Ming, Yang Jie, Cao Yuting, Sun Jihong. Key Technologies of Precaution and Prediction of Abnormal Spatial-Temporal Trajectory: A Review of Recent Advances[J]. Journal of System Simulation, 2017, 29(11): 2608-2617.

参考文献

[1] Hariharan R, Toyama K.Project Lachesis: parsing and modeling location histories[M]. Adelphi, MD: Springer Berlin Heidelberg, 2004: 106-124.
[2] 毛嘉莉, 金澈清, 章志刚, 等. 轨迹大数据异常检测:研究进展及系统框架[J]. 软件学报, 2017, 28(1):17-34.
Mao Jiali, Jin Cheqing, Zhang zhigang, et al. Anomaly Detection for Trajectory Big Data: Advancements and Framework[J]. Journal of Software, 2017, 28(1):17-34.
[3] Zhu J, Jiang W, Liu A, et al.Time-Dependent Popular Routes Based Trajectory Outlier Detection[C]// International Conference on Web Information Systems Engineering. Springer International Publishing, 2015: 16-30.
[4] Chawla S, Zheng Y, Hu J.Inferring the Root Cause in Road Traffic Anomalies[C]//IEEE, International Conference on Data Mining. IEEE, 2012:141-150.
[5] Lee J G, Han J, Whang K Y.Trajectory clustering: a partition-and-group framework[C]//ACM SIGMOD International Conference on Management of Data. ACM, 2007:593-604.
[6] Lee S L, Chun S J, Kim D H, et al.Similarity Search for Multidimensional Data Sequences[C]// International Conference on Data Engineering, 2000. Proceedings. IEEE, 2000:599-608.
[7] Toohey K, Duckham M.Trajectory similarity measures[J]. Sigspatial Special(S1946-7729), 2015, 7(1): 43-50.
[8] Masciari E.A framework for trajectory clustering[C]// International conference on GeoSensor Networks. Springer Berlin Heidelberg, 2009: 102-111.
[9] Mitsch S, Müller A, Retschitzegger W, et al.A Survey on Clustering Techniques for Situation Awareness[M]//Web Technologies and Applications. Springer Berlin Heidelberg, 2013: 815-826.
[10] Birant D, Kut A.ST-DBSCAN: An algorithm for clustering spatial-temporal data[J]. Data & Knowledge Engineering(S0169-023X), 2007, 60(1): 208-221.
[11] Nanni M, Pedreschi D.Time-focused clustering of trajectories of moving objects[J]. Journal of Intelligent Information Systems(S0925-9902), 2006, 27(3): 267-289.
[12] Yuan G, Xia S, Zhang L, et al.An efficient trajectory-clustering algorithm based on an index tree[J]. Transactions of the Institute of Measurement &Control (S0142-3312), 2012, 34(7):850-861.
[13] Chen Jing-yang, Song Jia-tao, Liu Xu-liang, et al.Trajectory Clustering Algorithm Based on Improved HausdorffDistance[J]. computer engineering (S1000-3428), 2012, 38(17):157-161.
[14] Sankoff D, Kruskal J B.Time warps, string edits, and macromolecules : the theory and practice of sequence comparison[M]. Addison-Wesley Pub. Co. Advanced Book Program, 1983.
[15] Little J J, Gu Z.Video retrieval by spatial and temporal structure of trajectories[C]//Photonics West 2001 - Electronic Imaging. International Society for Optics and Photonics, 2001:545-552.
[16] Zheng Y.Trajectory Data Mining: An Overview[J]. Acm Transactions on Intelligent Systems &Technology (S2157-6904), 2015, 6(3):1-41.
[17] 魏龙翔, 何小海, 滕奇志, 等. 结合Hausdorff距离和最长公共子序列的轨迹分类[J]. 电子与信息学报, 2013, 35(4):784-790.
Wei Long-xiang, He Xiao-hai, Teng Qi-zhi, et al.Trajectory Classification Based on Hausdorff Distance and Longest Common SubSequence[J]. Journal of Electronics & Information Technology, 2013, 35(4): 784-790.
[18] Chen L, Ng R T.On the marriage of Lp-norms and edit distance[C]. The Vldb Journal, 2004: 792-803.
[19] Palma A T, Bogorny V, Kuijpers B, et al.A clustering-based approach for discovering interesting places in trajectories[C]//Proceedings of the 2008 ACM symposium on Applied computing. ACM, 2008: 863-868.
[20] Rodriguez A, Laio A.Machine learning. Clustering by fast search and find of density peaks[J]. Science (S0036-8075), 2014, 344(6191):1492-1496.
[21] Hinneburg A, Gabriel H H.DENCLUE 2.0: Fast Clustering Based on Kernel Density Estimation[C]// International Conference on Intelligent Data Analysis. Springer-Verlag, 2007:70-80.
[22] Shang F, Jiao L C, Shi J, et al.Fast density-weighted low-rank approximation spectral clustering[J]. Data Mining & Knowledge Discovery(S1384-5810), 2011, 23(2):345-378.
[23] Pan Zhang-ming, Chen Yi-li.Research on Shared Nearest Neighbor Clustering for Large Dataset[J]. Journal of Chinese Computer Systems(S1000-1220), 2014, 35(1): 50-54.
[24] Wu Yu-hong.General Overview on Clustering Algorithms[J]. Computer Science(S1002-137X), 2015, 42(S1).
[25] 陈黎飞, 姜青山, 王声瑞. 基于层次划分的最佳聚类数确定方法[J]. 软件学报, 2008, 19(1): 62-72.
Chen Lifei, Jiang Qingshan, Wang Shengrui.A Hierarchical Method for Determining the Number of Clusters[J]. Journal of Software, 2008, 19(1): 62-72.
[26] Tsai C F, Chen Z C, Tsai C W.MSGKA: an efficient clustering algorithm for large databases[C]//IEEE International Conference on Systems, Man and Cybernetics. IEEE, 2003, 6: 5.
[27] 王莉, 周献中, 沈捷. 一种改进的粗K均值聚类算法[J]. 控制与决策, 2012, 27(11):1711-1714.
Wang Li, Zhou XianZhong, ShenJie. An improved rough K-means clustering algorithm[J]. Control and Decision, 2012, 27(11): 1711-1714.
[28] Killijian M O.Next place prediction using mobility Markov chains[C]//Proceedings of EuroSys 2012 Workshop on Measurement, Privacy, and Mobility.ACM, 2012.
[29] Marmasse N, Schmandt C.A User-Centered Location Model[J]. Personal and Ubiquitous Computing (S1617-4909), 2002: 318-321.
[30] Jeung H, Liu Q, Shen H T, et al.A hybrid prediction model for moving objects[C]//Data Engineering, 2008. ICDE 2008.IEEE 24th International Conference on.Ieee, 2008: 70-79.
[31] Assam R, Seidl T.Context-based location clustering and prediction using conditional random fields[C]//The, International Conference, 2014:1-10.
[32] Morzy M.Mining frequent trajectories of moving objects for location prediction[M]//Machine Learning and Data Mining in Pattern Recognition. Springer Berlin Heidelberg, 2007: 667-680.
[33] Ozer M, Keles I, Toroslu S H, et al.Predicting the change of location of mobile phone users[C]// ACMSigspatial International Workshop on Mobile Geographic Information Systems. ACM, 2013:43-50.
[34] Zheng Y, Xie X.Learning travel recommendations from user-generated GPS traces[J]. ACMTransactions on Intelligent Systems &Technology(S2157-6904), 2011, 2(1): 389-396.
[35] Alahi A, Goel K, Ramanathan V, et al.Social LSTM: Human Trajectory Prediction in Crowded Spaces[C]//Computer Vision and Pattern Recognition. IEEE, 2016: 961-971.
[36] Lv J, Li Q, Wang X. T-CONV: A Convolutional Neural Network For Multi-scale Taxi Trajectory Prediction[J]. arXiv preprint arXiv:1611.07635, 2016.
[37] Chen L, Lü M, Ye Q, et al.A personal route prediction system based on trajectory data mining[J]. Information Sciences(S0020-0255), 2011, 181(7): 1264-1284.
[38] Pelekis N, Kopanakis I, Kotsifakos E E, et al.Clustering uncertain trajectories[J]. Knowledge & Information Systems(S0219-1377), 2010, 28(1): 117-147.
[39] Lei P R, Shen T J, Peng W C, et al.Exploring Spatial-Temporal Trajectory Model for Location Prediction[C]//12th IEEE International Conference on Mobile Data Management, MDM 2011, Luleå, Sweden, 2011, 1: 58-67.
[40] Chiang M F, Yu P S, Lin Y H, et al.Inferring distant-time location in low-sampling-rate trajectories[C]//Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 2013: 117-126.
[41] Cox D, Fairall D, Macmillan N, et al.Trajectory Inference Using a Motion Sensing Network[C]. Canadian Conference on Computer and Robot Vision, 2014.