微信服务号

微信订阅号

2025年3月13日 22:32 星期四
首页 > 过刊浏览>2017年第28卷第1期 >17-34. DOI:10.13328/j.cnki.jos.005151
PDF HTML阅读 XML下载 导出引用 引用提醒
轨迹大数据异常检测:研究进展及系统框架
作者:
基金项目:

国家自然科学基金（61370101，U1501252，U1401256）；上海市教委创新计划（14ZZ045）；西华师范大学国家级项目培育专项（16C005）


Anomaly Detection for Trajectory Big Data: Advancements and Framework
Author:
Fund Project:

National Natural Science Foundation of China (61370101, U1501252, U1401256); Shanghai Municipal Eduation Commission Innovation Plan (14ZZ045); China West Normal University Special Fundation of National Programme Cultivation (16C005)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [80]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    定位技术与普适计算的蓬勃发展催生了轨迹大数据，轨迹大数据表现为定位设备所产生的大规模高速数据流.及时、有效地对以数据流形式出现的轨迹大数据进行分析处理，可以发现隐含在轨迹数据中的异常现象，从而服务于城市规划、交通管理、安全管控等应用.受限于轨迹大数据固有的不确定性、无限性、时变进化性、稀疏性和偏态分布性等特征，传统的异常检测技术不能直接应用于轨迹大数据的异常检测.由于静态轨迹数据集的异常检测方法通常假定数据分布先验已知，忽视了轨迹数据的时间特征，也不能评测轨迹大数据中动态演化的异常行为.面对轨迹大数据低劣的数据质量和快速的数据更新，需要利用有限的系统资源处理因时变带来的概念漂移，实时地检测多样化的轨迹异常，分析轨迹异常间的因果联系，继而识别更大时空区域内进化的、关联的轨迹异常，这是轨迹大数据异常检测的核心研究内容.此外，融合与位置服务应用相关的多源异质数据，剖析异常轨迹的起因以及其隐含的异常事件，也是轨迹大数据异常检测当下亟待研究的问题.为解决上述问题，对轨迹异常检测技术的研究成果进行了分类总结.针对现有轨迹异常检测方法的局限性，提出了轨迹大数据异常检测的系统架构.最后，在面向轨迹流的在线异常检测、轨迹异常的演化分析、轨迹异常检测系统的基准评测、异常检测结果语义分析的数据融合以及轨迹异常检测的可视化技术等方面探讨了今后的研究工作.

    Abstract:

    The vigorous development of positioning technology and pervasive computing has given rise to trajectory big data, i.e. the high speed trajectory data stream that originated from positioning devices. Analyzing trajectory big data timely and effectively enables us to discover the abnormal patterns that hide in trajectory data streams, and therefore to provide effective support to applications such as urban planning, traffic management, and security controlling. The traditional anomaly detection algorithms cannot be applied to outlier detection in trajectory big data directly due to the characteristics of trajectories such as uncertainty, un-limitedness, time-varying evolvability, sparsity and skewness distribution. In addition, most of trajectory outlier detection methods designed for static trajectory dataset usually assume a priori known data distribution while disregarding the temporal property of trajectory data, and thus are unsuitable for identifying the evolutionary trajectory outlier. When dealing with huge amount of low-quality trajectory big data, a series of issues need to be addressed. Those issues include coping with the concept drifts of time-varying data distribution in limited system resources, online detecting trajectory outliers, analyzing causal interactions among traffic outliers, identifying the evolutionary related trajectory outlier in larger spatial-temporal regions, and analyzing the hidden abnormal events and the root cause in trajectory anomalies by using application related multi-source heterogeneous data. Aiming at solving the problems mentioned above, this paper reviews the existing trajectory outlier detecting techniques from several categories, describes the system architecture of outlier detection in trajectory big data, and discusses the research directions such as outlier detection in trajectory stream, visualization and evolutionary analysis in trajectory outlier detection, benchmark for trajectory outlier detection system, and data fusion in semantic analysis for anomaly detection results.

    参考文献
    [1] Liao L, Patterson DJ, Fox D, Kautz H. Learning and inferring transportation routines. Artificial Intelligence, 2007,171(5-6): 311-331.[doi: 10.1016/j.artint.2007.01.006]
    [2] Liu L, Andris C, Ratti C. Uncovering cabdrivers' behavior patterns from their digital traces. Computers, Environment and Urban Systems, 2010,34(6):541-548.[doi: 10.1016/j.compenvurbsys.2010.07.004]
    [3] Phithakkitnukoon S, Veloso M, Bento C, Biderman A, Ratti C. Taxi-Aware map: Identifying and predicting vacant taxis in the city. In: Proc. of the Ambient Intelligence. 2010. 86-95.[doi: 10.1007/978-3-642-16917-5_9]
    [4] Lippi M, Bertini M, Frasconi P. Collective traffic forecasting. In: Proc. of the ECML-PKDD. 2010. 259-273.[doi: 10.1007/978-3-642-15883-4_17]
    [5] Zheng Y, Liu YC, Yuan J, Xie X. Urban computing with taxicabs. In: Proc. of the Ubicomp. 2011. 89-98.[doi: 10.1145/2030112. 2030126]
    [6] Yuan J, Zheng Y. Zhang CY, Xie X, Sun GZ, Huang Y. T-Drive: Driving directions based on taxi trajectories. In: Proc. of the GIS. 2010. 99-108.[doi: 10.1145/1869790.1869807]
    [7] Liu HP, Jin CQ, Zhou AY. Popular route planning with travel cost estimation. In: Proc. of the DASFAA. 2016. 403-418.[doi: 10. 1007/978-3-319-32049-6_25]
    [8] Zheng VW, Cao B, Zheng Y, Xie X, Yang Q. Collaborative filtering meets mobile recommendation: A user-centered approach. In: Proc. of the AAAI Conf. on Artificial Intelligence. 2010. 236-241. http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1615
    [9] Zheng Y, Zhang L, Xie X, Ma W. Mining interesting locations and travel sequences from gps trajectories. In: Proc. of the WWW. 2009. 791-800.[doi: 10.1145/1526709.1526816]
    [10] Deng Z, Hu YY, Zhu M, Huang XH, Du B. A scalable and fast OPTICS for clustering trajectory big data. Cluster Computing, 2015, 18(2):549-562.[doi: 10.1007/s10586-014-0413-9]
    [11] Costa G, Manco G, Masciari E. Dealing with trajectory streams by clustering and mathematical transforms. Journal of Intelligent Information Systems, 2014,42(1):155-177.[doi: 10.1007/s10844-013-0267-2]
    [12] Yu YW, Wang Q, Wang XD, Wang H, He J. Online clustering for trajectory data stream of moving objects. Computer Science and Information Systems, 2013,10(3):1293-1317.[doi: 10.2298/CSIS120723049Y]
    [13] Mao JL, Song QG, Jin CQ, Zhang ZG, Zhou AY. TSCluWin: Trajectory stream clustering over sliding window. In: Proc. of the DASFAA. 2016. 133-148.[doi: 10.1007/978-3-319-32049-6_9]
    [14] Nehme RV, Rundensteiner EA. SCUBA: Scalable cluster-based algorithm for evaluating continuous spatio-temporal queries on moving objects. In: Proc. of the EDBT. 2006. 1001-1019.[doi: 10.1007/11687238_58]
    [15] Sacharidis D, Patroumpas K, Terrovitis M, Kantere V, Potamias M, Mouratidis K, Sellis TK. On-Line discovery of hot motion paths. In: Proc. of the EDBT. 2008. 392-403.[doi: 10.1145/1353343.1353392]
    [16] Zheng K, Zheng Y, Yuan NJ, Shang S. On discovery of gathering patterns from trajectories. In: Proc. of the ICDE. 2013. 242-253.[doi: 10.1109/ICDE.2013.6544829]
    [17] Tang LA, Zheng Y, Yuan J, Han JW, Leung A, Hung CC, Peng WC. On discovery of traveling companions from streaming trajectories. In: Proc. of the ICDE. 2012. 186-197.[doi: 10.1109/ICDE.2012.33]
    [18] Li XH, Ceikute V, Jensen CS, Tan KL. Effective online group discovery in trajectory databases. IEEE Trans. on Knowledge and Data Engineering, 2013,25(12):2752-2766.[doi: 10.1109/TKDE.2012.193]
    [19] Duan XY, Jin CQ, Wang XL, Zhou AY, Yue K. Real-Time personalized taxi-sharing. In: Proc. of the DASFAA. 2016. 451-465.[doi: 10.1007/978-3-319-32049-6_28]
    [20] Hawkins DM. Identification of Outliers. London: Chapman and Hall, 1980.
    [21] Bu YY, Chen L, Fu AWC, Liu DW. Efficient anomaly monitoring over moving object trajectory streams. In: Proc. of the SIGKDD. 2009. 159-168.[doi: 10.1145/1557019.1557043]
    [22] Yu YW, Cao L, Rundensteiner EA, Wang Q. Detecting moving object outliers in massive-scale trajectory streams. In: Proc. of the SIGKDD. 2014. 422-431.[doi: 10.1145/2623330.2623735]
    [23] Hodge VJ, Austin J. A survey of outlier detection methodologies. Artificial Intelligence Review, 2004,22(2):85-126.[doi: 10.1007/s10462-004-4304-y]
    [24] Chandola V, Banerjee A, Kumar V. Anomaly detection: A survey. ACM Computing Surveys, 2009,41(3):75-79.[doi: 10.1145/1541880.1541882]
    [25] Aggarwal CC. Outlier Analysis. Springer-Verlag, 2013.[doi: 10.1007/978-1-4614-6396-2]
    [26] Zhang Y, Meratnia N, Havinga PJM. Outlier detection techniques for wireless sensor networks: A survey. IEEE Communications Surveys and Tutorials, 2010,12(2):159-170.[doi: 10.1109/SURV.2010.021510.00088]
    [27] Gupta M, Gao J, Aggarwal CC, Han JW. Outlier detection for temporal data: A survey. IEEE Trans. on Knowledge and Data Engineering, 2014, 26(9):2250-2267.[doi: 10.1109/TKDE.2013.184]
    [28] Zheng Y. Trajectory data mining: An overview. ACM Trans. on Intelligent Systems and Technology, 2015,6(3):29.[doi: 10.1145/2743025]
    [29] Jeung H, Yiu ML, Jensen CS. Trajectory pattern mining. In: Computing with Spatial Trajectories. New York: Springer-Verlag, 2011. 143-177.[doi: 10.1007/978-1-4614-1629-6_5]
    [30] Barnett V, Lewis T. Outliers in Statistical Data. Hoboken: John Wiley & Sons, 1994.
    [31] Aggarwal CC, Yu PS. Outlier detection for high dimensional data. In: Proc. of the SIGMOD. 2001. 37-46.[doi: 10.1145/375663. 375668]
    [32] Johnson T, Kwok I, Ng RT. Fast computation of 2-dimensional depth contours. In: Proc. of the KDD. 1998. 224-228. https://www.aaai.org/Papers/KDD/1998/KDD98-038.pdf
    [33] Knorr EM, Ng RT. Algorithms for mining distance-based outliers in large datasets. In: Proc. of the VLDB. 1998. 392-403. http://www.vldb.org/conf/1998/p392.pdf
    [34] Knorr EM, Ng RT. Finding intensional knowledge of distance-based outliers. In: Proc. of the VLDB. 1999. 211-222. http://www.vldb.org/conf/1999/P21.pdf
    [35] Knorr EM, Ng RT, Tucakov V. Distance-Based outliers: Algorithms and applications. VLDB Journal, 2000,8(3-4):237-253.[doi: 10.1007/s007780050006]
    [36] Ramaswamy S, Rastogi R, Shim K. Efficient algorithms for mining outliers from large data sets. In: Proc. of the SIGMOD. 2000. 427-438.[doi: 10.1145/342009.335437]
    [37] Breunig MM, Kriegel HP, Ng RT, Sander J. LOF: Identifying density-based local outliers. In: Proc. of the SIGMOD. 2000. 93-104.[doi: 10.1145/342009.335388]
    [38] Papadimitriou S, Kitagawa H, Gibbons PB, Faloutsos C. LOCI: Fast outlier detection using the local correlation integral. In: Proc. of the ICDE. 2003. 315-326.[doi: 10.1109/ICDE.2003.1260802]
    [39] Sun P, Chawla S. On local spatial outliers. In: Proc. of the ICDM. 2004. 209-216.[doi: 10.1109/ICDM.2004.10097]
    [40] Chen F, Lu CT, Boedihardjo AP. GLS-SOD: A generalized local statistical approach for spatial outlier detection. In: Proc. of the KDD. 2010. 1069-1078. http://dl.acm.org/citation.cfm?doid=1835804.1835939
    [41] Birant D, Kut A. Spatio-Temporal outlier detection in large databases. Science, 2006,14(4):291-297.[doi: 10.2498/cit.2006.04.04]
    [42] Cheng T, Li ZL. A multiscale approach for spatio-temporal outlier detection. Trans. on GIS, 2006,10(2):253-263.[doi: 10.1111/j. 1467-9671.2006.00256.x]
    [43] Adam NR, Janeja VP, Atluri V. Neighborhood based detection of anomalies in high dimensional spatio-temporal sensor datasets. In: Proc. of the SAC. 2004. 576-583.[doi: 10.1145/967900.968020]
    [44] Wu E, Liu W, Chawla S. Spatio-Temporal outlier detection in precipitation data. In: Proc. of the KDD Workshop on Knowledge Discovery from Sensor Data. 2008. 115-133.[doi: 10.1007/978-3-642-12519-5_7]
    [45] Li XL, Han JW, Kim S, Gonzalez H. ROAM: Rule-and motif-based anomaly detection in massive moving object data sets. In: Proc. of the SDM. 2007. 273-284.[doi: 10.1137/1.9781611972771.25]
    [46] Yang WQ, Gao Y, Cao LB. TRASMIL: A local anomaly detection framework based on trajectory segmentation and multi-instance learning. Computer Vision and Image Understanding, 2013,117:1273-1286.[doi: 10.1016/j.cviu.2012.08.010]
    [47] Lei PR. A framework for anomaly detection in maritime trajectory behavior. Knowledge and Information Systems, 2016,47(1): 189-214.[doi: 10.1007/s10115-015-0845-4]
    [48] Lee JG, Han JW, Li XL. Trajectory outlier detection: A partition-and-detect framework. In: Proc. of the ICDE. 2008. 140-149.[doi: 10.1109/ICDE.2008.4497422]
    [49] Chen C, Zhang DQ, Castro PS, Li N, Sun L, Li SJ. Real-Time detection of anomalous taxi trajectories from GPS traces. In: Proc. of the MobiQuitous. 2011. 63-74.[doi: 10.1007/978-3-642-30973-1_6]
    [50] Ge Y, Xiong H, Zhou ZH, Ozdemir HT, Yu J, Lee KC. Top-Eye: Top-k evolving trajectory outlier detection. In: Proc. of the CIKM. 2010. 1733-1736.[doi: 10.1145/1871437.1871716]
    [51] Zhang DQ, Li N, Zhou ZH, Chen C, Sun L, Li SJ. iBAT: Detecting anomalous taxi trajectories from GPS traces. In: Proc. of the Ubicomp. 2011. 99-108.[doi: 10.1145/2030112.2030127]
    [52] Li XL, Li ZH, Han JW, Lee JG. Temporal outlier detection in vehicle traffic data. In: Proc. of the ICDE. 2009. 1319-1322.[doi: 10. 1109/ICDE.2009.230]
    [53] Liu W, Zheng Y, Chawla S, Yuan J, Xie X. Discovering spatio-temporal causal interactions in traffic data streams. In: Proc. of the SIGKDD. 2011. 1010-1018.[doi: 10.1145/2020408.2020571]
    [54] Chawla S, Zheng Y, Hu JF. Inferring the root cause in road traffic anomalies. In: Proc. of the ICDM. 2012. 141-150.[doi: 10.1109/ICDM.2012.104]
    [55] Pan B, Zheng Y, Wilkie D, Shahabi C. Crowd sensing of traffic anomalies based on human mobility and social media. In: Proc. of the SIGSPATIAL/GIS. 2013. 334-343.[doi: 10.1145/2525314.2525343]
    [56] Jonkery R, De LG, Van DV. Rounding symmetric traveling salesman problems with an asymmetric assignment problem. In: Proc. of the Operations Research. 1980. 623-627.[doi: 10.1287/opre.28.3.623]
    [57] Yi BK, Jagadish H, Faloutsos C. Efficient retrieval of similar time sequences under time warping. In: Proc. of the ICDE. 1998. 201-208.[doi: 10.1109/ICDE.1998.655778]
    [58] Vlachos M, Kollios G, Gunopulos D. Discovering similar multidimensional trajectories. In: Proc. of the ICDE. 2002. 673-684.[doi: 10.1109/ICDE.2002.994784]
    [59] Chen L, Ng R. On the marriage of LP-norms and edit distance. In: Proc. of the VLDB. 2004. 792-803. http://www.vldb.org/conf/2004/RS21P2.PDF
    [60] Chen L, Ozsu MT, Oria V. Robust and fast similarity search for moving object trajectories. In: Proc. of the SIGMOD. 2005. 491-502.[doi: 10.1145/1066157.1066213]
    [61] Daniel PH, Klara K, Jon MK. On dynamic voronoi diagrams and the minimum hausdorff distance for point sets under euclidean motion in the plane. In: Proc. of the Symp. on Computational Geometry. 1992. 110-119.[doi: 10.1145/142675.142700]
    [62] Lee JG, Han JW, Whang KY. Trajectory clustering: A partition-and-group framework. In: Proc. of the SIGMOD. 2007. 593-604.[doi: 10.1145/1247480.1247546]
    [63] Roh GP, Hwang SW. NNCluster: An efficient clustering algorithm for road network trajectories. In: Proc. of the DASFAA. 2010. 47-61.[doi: 10.1007/978-3-642-12098-5_4]
    [64] Han B, Liu L, Omiecinski E. Road-Network aware trajectory clustering: Integrating locality, flow, and density. IEEE Trans. on Mobile Computing, 2015,14(2):416-429.[doi: 10.1109/TMC.2013.119]
    [65] Li XL, Han JW, Kim S. Motion-Alert: Automatic anomaly detection in massive moving objects. In: Proc. of the ISI. 2006. 166-177.[doi: 10.1007/11760146_15]
    [66] Ge Y, Xiong H, Liu C, Zhou ZH. A taxi driving fraud detection system. In: Proc. of the ICDM. 2011. 181-190.[doi: 10.1109/ICDM.2011.18]
    [67] Liu SY, Ni LM, Krishnan R. Fraud detection from taxis' driving behaviors. IEEE Trans. on Vehicular Technology, 2014,63(1): 464-472.[doi: 10.1109/TVT.2013.2272792]
    [68] Pang LXL, Chawla S, Liu W, Zheng Y. On mining anomalous patterns in road traffic streams. In: Proc. of the ADMA. 2011. 237-251.[doi: 10.1007/978-3-642-25856-5_18]
    [69] Pang LXL, Chawla S, Liu W, Zheng Y. On detection of emerging anomalous traffic patterns using GPS data. Data & Knowledge Engineering, 2013,87:357-373.[doi: 10.1016/j.datak.2013.05.002]
    [70] Chen C, Zhang DQ, Castro PS, Li N, Sun L, Li SJ, Wang ZH. iBOAT: Isolation-Based online anomalous trajectory detection. IEEE Trans. on Intelligent Transportation Systems, 2013,14(2):806-818.[doi: 10.1109/TITS.2013.2238531]
    [71] Sun L, Zhang DQ, Chen C, Castro PS, Li SJ, Wang ZH. Real time anomalous trajectory detection and analysis. Mobile Networks and Applications, 2013,18(3):341-356.[doi: 10.1007/s11036-012-0417-8]
    [72] Zhu J, Jiang W, Liu A, Liu GF, Zhao L. Time-Dependent popular routes based trajectory outlier detection. In: Proc. of the WISE. 2015. 16-30.[doi: 10.1007/978-3-319-26190-4_2]
    [73] Liu LX, Qiao SJ, Liu B, Le JJ, Tang CJ. Efficient trajectory outlier detection algorithm based on R-tree. Ruan Jian Xue Bao/Journal of Software, 2009,20(9):2426-2435(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3580.htm[doi: 10.3724/SP.J.1001.2009.03580]
    [74] Liu LX, Le JJ, Qiao SJ, Song JT. Trajectory outliers detection based on local outlying degree. Chinese Journal of Computers, 2011,34(10):1966-1975(in Chinese with English abstract).
    [75] Byron L, Wattenberg M. Stacked graphs-Geometry & aesthetics. IEEE Trans. on Visualization & Computer Graphics, 2008,14(6): 1245-1252.[doi: 10.1109/TVCG.2008.166]
    [76] Buchin K, Speckmann B, Verbeek K. Flow map layout via spiral trees. IEEE Trans. on Visualization & Computer Graphics, 2011,17(12):2536-2544.[doi: 10.1109/TVCG.2011.202]
    [77] Wei LY, Zheng Y, Peng WC. Constructing popular routes from uncertain trajectories. In: Proc. of the KDD. 2012. 195-203.[doi: 10.1145/2339530.2339562]
    附中文参考文献:
    [73] 刘良旭,乔少杰,刘宾,乐嘉锦,唐常杰.基于R-Tree的高效异常轨迹检测算法.软件学报,2009,20(9):2426-2435. http://www.jos.org.cn/1000-9825/3580.htm[doi: 10.3724/SP.J.1001.2009.03580]
    [74] 刘良旭,乐嘉锦,乔少杰,宋加涛.基于轨迹点局部异常度的异常点检测算法.计算机学报,2011,34(10):1966-1975.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

毛嘉莉,金澈清,章志刚,周傲英.轨迹大数据异常检测:研究进展及系统框架.软件学报,2017,28(1):17-34

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2016-05-25
  • 最后修改日期:2016-08-18
  • 在线发布日期: 2016-10-27
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19698494位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号