ACM综述:Trajectory Outlier Detection: Algorithms, Taxonomies, Evaluation, and Open Challenges

摘要

1. 回顾轨迹异常处理(TOD)的算法
2. 基于应用，output，算法层面上的分类
3. 算法在小中大数据集上的表现
4. 挑战，和待解决的问题

introduction

1.1 Review works
这篇文章关于异常处理的深度学习算法
Raghavendra Chalapathy and Sanjay Chawla. 2019. Deep learning for anomaly detection: A survey. arXiv:1901.03407
Gupta等人。[54]提供了一个有趣的调查，讨论了检测时间异常值的技术。他们的调查组织了关于不同类型数据的讨论，提出了各种离群值定义，并讨论了时间离群值技术已成功应用的各种应用（环境传感器网络、轨道、生物、天文学和网络数据）
Manish Gupta, Jing Gao, Charu C. Aggarwal, and Jiawei Han. 2014. Outlier detection for temporal data: A survey. IEEE Transactions on Knowledge and Data Engineering 26, 9 (2014), 2250–2267
回顾了现有的模式挖掘技术在海上交通数据轨迹异常检测与预测中的应用。这项研究肯定了提出先进的数据挖掘技术以应对海上交通研究挑战的重要性。
Zhe Xiao, Xiuju Fu, Liye Zhang, and Rick Siow Mong Goh. 2020. Traffic pattern mining and forecasting technolo-gies in maritime traffic service networks: A comprehensive survey. IEEE Transactions on Intelligent Transportation
Systems 21, 5 (2020), 1796–1825

关于TOD相关的综述，看过91 写的一般般
1.2 基本概念
轨迹数据库
匹配过的轨迹数据库
2算法
Trajectory outlier detection: A partition-and-detect framework 经典文章
Claudio Piciarelli, Christian Micheloni, and Gian Luca Foresti. 2008. Trajectory-based anomalous event detection.
IEEE Transactions on Circuits and Systems for Video Technology 18, 11 (2008), 1544–1554 svm做的 没有看过
Xia Ying, Zhang Xu, and Wang Guo Yin. 2009. Cluster-based congestion outlier detection method on trajectory data.
In Proceedings of the International Conference on Fuzzy Systems and Knowledge Discovery, Vol. 5. 243–247. 也是比较经典的 没有看过
Yong Ge, Hui Xiong, Zhi-Hua Zhou, Hasan Ozdemir, Jannite Yu, and Kuo Chu Lee. 2010. TOP-EYE: Top-k evolv-
ing trajectory outlier detection. In Proceedings of the ACM International Conference on Information and Knowledge Management. 1733–1736.看到过很多次这篇文章 没有看过
Elio Masciari. 2011. Trajectory outlier detection using an analytical approach. InProceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI’11). 377–384 没有看过
Daqing Zhang, Nan Li, Zhi-Hua Zhou, Chao Chen, Lin Sun, and Shijian Li. 2011. iBAT: Detecting anomalous taxi trajectories from GPS traces. In Proceedings of the International Conference on Ubiquitous Computing. 99–108. 少而不同
Liangxu Liu, Shaojie Qiao, Yongping Zhang, and JinSong Hu. 2012. An efficient outlying trajectories mining ap-proach based on relative distance. International Journal of Geographical Information Science 26, 10 (2012), 1789–1810 没有看过
Chao Chen, Daqing Zhang, Pablo Samuel Castro, Nan Li, Lin Sun, Shijian Li, and Zonghui Wang. 2013. iBOAT:
Isolation-based online anomalous trajectory detection. IEEE Transactions on Intelligent Transportation Systems 14, 2(2013), 806–818. 实时监测
2018年文章
层次聚类，新的编辑距离加特殊的聚类算法
Yulong Wang, Kun Qin, Yixiang Chen, and Pengxiang Zhao. 2018. Detecting anomalous trajectories and behavior
patterns using hierarchical clustering from taxi GPS data. ISPRS International Journal of Geo-Information 7, 1 (2018),25.
公交车数据进行建模探索异常区域
Xiangjie Kong, Ximeng Song, Feng Xia, Haochen Guo, Jinzhong Wang, and Amr Tolba. 2018. LoTAD: Long-term traffic anomaly detection based on crowdsourced bus trajectory data. World Wide Web 21, 3 (2018), 825–847
Tao Zhang, Shuai Zhao, and Junliang Chen. 2018. Ship trajectory outlier detection service system based on collab-orative computing. In Proceedings of the IEEE World Congress on Services. 15–16 没看过
基于新的距离，轨迹分割加上自己衡量的距离
Qingying Yu, Yonglong Luo, Chuanming Chen, and Xiaohan Wang. 2018. Trajectory outlier detection approach based on common slices sub-sequence. Applied Intelligence 48, 9 (2018), 2661–2680
Kun Qin, Yulong Wang, and Bijun Wang. 2018. Detecting anomalous trajectories using the Dempster-Shafer evidence theory considering trajectory features from taxi GNSS data. Information 9, 10 (2018), 258没看过
定义一个上下文距离，特定场合的异常不同，关于距离的定义觉得奇怪
Ignacio San Román, Isaac Martín de Diego, Cristina Conde, and Enrique Cabello. 2019. Outlier trajectory detection through a context-aware distance. Pattern Analysis and Applications 22, 3 (2019), 831–839
Yingfu Huang and Qiurong Zhang. 2019. Identification of anomaly behavior of ships based on KNN and LOF combination algorithm. In AIP Conference Proceedings, Vol. 2073. AIP Publishing LLC, 020090没看过
Samir Bouindour, Hichem Snoussi, Mohamad Mazen Hittawe, Nacef Tazi, and Tian Wang. 2019. An on-line andadaptive method for detecting abnormal events in videos using spatio-temporal ConvNet.Applied Sciences9, 4 (2019), 757 没有看过
Wenqing Chu, Hongyang Xue, Chengwei Yao, and Deng Cai. 2019. Sparse coding guided spatiotemporal feature learning for abnormal event detection in large videos. IEEE Transactions on Multimedia 21, 1 (2019), 246–255. 没有看过

3 分类和讨论

首先，一些轨迹离群点检测方法是基于邻域计算的，这些方法使用有效的结构来计算轨迹之间的相似性。与其他方法相比，这种方法的精度较低，后者根据邻域轨迹局部提供异常判断。此类方法的另一个问题是确定轨迹之间的相似性的方法：一些方法使用自适应的欧几里德度量，而其他方法使用复杂的度量（例如，基于角度的）。因此，需要一个标准化步骤来比较这些方法 08年文章，基于领域
第二，一些方法将聚类技术作为寻找轨迹异常值的预处理步骤。一种可能的方法是建立基于密度的范式[110]，其中正常轨迹不必属于任何噪声簇。这些噪声团中的每个轨迹都可以解释为异常。现有的一些轨迹离群点检测方法定义了聚类，不将不属于任何聚类的轨迹视为离群点。这些方法在具有较少数据点的轨迹上表现良好；但是，对于高维数据，它们需要较高的计算时间处理 非常常用
第三，一些方法探索模式挖掘技术来发现轨迹异常值。这些方法首先将轨迹数据库转换为事务数据库，应用模式挖掘过程，然后使用一些有趣度度量导出异常值。这些方法在精度方面表现良好，但由于采用了传统的模型[3]在轨迹数据中寻找相关模式，因此它们非常耗时。采用新兴的模式挖掘模型[13,16,40,41]可以提高这些方法的性能。对轨迹数据提出具有特定兴趣度指标的特定模式挖掘算法是另一种方法 基本没有听过
第四，基于支持向量机、集成学习和粒度计算等机器学习技术的方法在提供具有地面真实性的训练轨迹数据的某些应用中是有效的。然而，在几乎所有的情况下，不可能有历史轨迹数据来学习这些模型。解决这一问题的一种方法是手动生成标记轨迹数据，这是一项计算成本很高的任务。在某些情况下，例如船舶数据，需要专家来判断标记的轨迹数据是否创建良好。另外，标记轨迹数据的生成方式也影响到这些方法的最终精度。对于这些方法，考虑标准训练轨迹数据是一个关键问题 是个核心问题，现在很多方法也是手动创造数据集
第五，对现有的轨迹离群点检测算法进行评估，可以判断轨迹是否异常。对于许多轨迹异常值检测方法，特别是当使用具有大量数据点的轨迹时，异常值的得分并不能真正解释。轨迹离群点检测方法的得分随尺度的不同而变化很大。因此，考虑到两种方法1和2以及给定的轨迹∧i，我们可以得到这样的情况：分数（A1，∧i）>>分数（A2，∧i）。在这种情况下，可能很难理解某些方法的异常值的含义，也不容易比较现有的轨迹异常检测模型。轨迹异常值检测的一个开放性研究问题是定义标准的异常值评分指标，以比较和评估轨迹数据中现有的异常值模型[91]。最新的建议包括轨迹距离度量：欧几里德距离、豪斯多夫距离、最长公共子序列（LCC）、动态时间扭曲（DTW）以及其他基于结构距离的度量，包括方向、角度、速度和密度的比较 确实

4 evaluation

4.1 指标和数据集

5 开放性研究问题

在这一部分，我们提供了一些关于轨迹异常点检测的开放性研究问题的见解。一些研究问题可以被认为是可以应用于任何密集计算问题的一般性主题，而其他问题则是特定问题，只与轨迹异常点检测相关。接下来将介绍有关算法、分类法和评估的开放性研究问题
5.1.1 Quality Improvements. Several algorithms could be investigated to improve the quality of the detected trajectory outliers.提高某些算法的质量
5.1.2运行时间提高。现有的轨迹离群点检测技术在计算时间上非常昂贵，特别是在增加点的数目时。图5（b）显示了北京出租车数据集（包含3.5亿条轨迹）连续10天的轨迹算法[71]的运行时间。图中显示，通过增加轨迹的数量，轨迹变得非常耗时。例如，对于5000万个轨迹，TROAD需要大约2.5个小时；但是对于3.5亿个轨迹，TRAOD需要超过52个小时（大约连续3天）来识别异常值。幸运的是，TRAOD通过提出基于Spark的实现得到了改进[31,87]，但是许多其他的轨迹异常点检测算法还没有得到改进。当处理实时环境中的轨迹异常值时，提出高性能计算工具可能会有所帮助[24,42]。然而，有几个问题需要解决。例如，应该使用哪些架构？我们如何在不同的作业之间有效地划分数据？我们如何设计一种并行方法来应对高性能计算的挑战，如降低通信和同步成本，或增加负载平衡和优化内存管理？
5.1.3多角度。考虑图5（d）中所示的三个出租车轨迹草图示例。每个出租车轨迹从出发点开始，到终点。传统的轨迹异常值检测算法可能会检测异常值在第一个图，如红色所示，其中taxi4直到给定点都遵循从源到目的地的正常行程，它与taxi1、taxi2和taxi3高度偏离。然而算法不能确定ICP在这个例子中。而且，整个过程无法识别中间和下面的图以红色和绿色表示的异常值。在中间的图中，不同的出租车（taxi5和taxi6）在同一组转换点（GCP）偏离正常行程，但遵循不同的轨迹（taxi5为绿色轨迹，taxi6为红色轨迹）。然而，在下面图所示的情况下，两辆出租车偏离了同一GCP的正常行程，并遵循红色显示的相同轨迹。检测这些不同类型的异常值可以帮助城市规划者提取和发现相关知识。例如，上半部分的案例可以确定个体出租车欺诈行为，而在同一个ICP中发现频繁的个体出租车欺诈行为可以让城市规划者做出正确的决策，比如在这一点上安装监控摄像头。在中间和底部的情况下，检测群体轨迹异常值可以使城市规划者对出租车异常值做出公正的决策。当出租车偏离相同的GCP但遵循不同的轨迹时，它们的目标很可能是为了避免交通堵塞等情况，而不是出租车欺诈。然而，当在相同或不同的GCP处存在具有相同轨迹的群出租车离群值时，他们很有可能成为出租车欺诈的合作伙伴。该问题与现有的出租车欺诈检测算法有关，在这种情况下，我们可以提出以下问题：如何得出个别轨迹异常值（ITO）和组轨迹异常值（GTO），以及如何确定ICP和GCP？