地球信息科学理论与方法

基于地图匹配和两阶段聚类的轨迹异常检测算法

  • 王书敏 , 1, 2 ,
  • 李元俊 1, 2 ,
  • 杨涛 1, 2 ,
  • 俞庆英 , 1, 2, *
展开
  • 1.安徽师范大学计算机与信息学院,芜湖 241002
  • 2.安徽省工业智能数据安全重点实验室,芜湖 241002
*俞庆英(1980— ),女,安徽黄山人,博士,教授,主要从事空间数据处理和信息安全研究。E-mail:

作者贡献:Author Contributions

王书敏和俞庆英参与实验设计;王书敏完成实验操作;王书敏、李元俊、杨涛、俞庆英参与论文的写作与修改。所有作者均阅读并同意最终稿件的提交。

The study was designed by WANG Shumin and YU Qingying. The experimental operation was completed by WANG Shumin. The manuscript was drafted and revised by WANG Shumin, LI Yuanjun, YANG Tao, and YU Qingying. All the authors have read the last version of paper and consented for submission.

王书敏(1999— ),女,安徽滁州人,硕士生,主要从事空间数据处理研究。E-mail:

收稿日期: 2025-03-24

  修回日期: 2025-05-21

  网络出版日期: 2025-07-23

基金资助

国家自然科学基金项目(62472006)

安徽省自然科学基金项目(2208085MF164)

A Trajectory Anomaly Detection Algorithm Based on Map Matching and Two-Stage Clustering

  • WANG Shumin , 1, 2 ,
  • LI Yuanjun 1, 2 ,
  • YANG Tao 1, 2 ,
  • YU Qingying , 1, 2, *
Expand
  • 1. School of Computer and Information, Anhui Normal University, Wuhu 241002, China
  • 2. Anhui Provincial Key Laboratory of Industrial Intelligence Data Security, Wuhu 241002, China
*YU Qingying, E-mail:

Received date: 2025-03-24

  Revised date: 2025-05-21

  Online published: 2025-07-23

Supported by

National Natural Science Foundation of China(62472006)

Anhui Provincial Natural Science Foundation of China(2208085MF164)

摘要

【目的】针对现有轨迹异常检测方法未充分考虑道路网络约束的问题,提出一种有效检测出租车司机搭载乘客时可能存在的欺诈行为的轨迹异常检测算法。【方法】首先进行地图匹配,将轨迹数据映射到实际道路网络上,从而获取轨迹的路径序列。接着,使用两阶段聚类方法,先对匹配后的轨迹路径进行初始聚类,提取出核心路段并扩展,形成多个核心路径,再计算不同核心路径之间的相似性,并将相似性高的路径分配到同一簇,从而形成多个路径簇。最后,根据路径簇计算出通行代价阈值,再结合通行时间代价和通行路程代价计算每条轨迹的通行代价,将其与通行代价阈值进行比较,以此判断轨迹的异常性。【结果】在真实轨迹数据集上与传统异常检测方法进行对比,所提方法在异常轨迹检测上具有良好的效果,其运行时间明显低于STADCS方法,并且检测准确率比STADCS方法最高提升了9.03%; F1分数值相较于Two Phase和ATDC方法也有明显提升,最高提升率分别为6.67%和9.45%。【结论】本文提出融合路网约束的检测方法,结合两阶段聚类和通行代价评估,有效提升检测准确性与效率,降低误判率。算法适用于复杂城市路网场景,为车辆轨迹数据挖掘及交通管理决策提供有力支持,在欺诈识别等领域具有重要应用价值。

本文引用格式

王书敏 , 李元俊 , 杨涛 , 俞庆英 . 基于地图匹配和两阶段聚类的轨迹异常检测算法[J]. 地球信息科学学报, 2025 , 27(8) : 1780 -1795 . DOI: 10.12082/dqxxkx.2025.250134

Abstract

[Objectives] To address the limitation that existing trajectory anomaly detection methods often fail to fully consider road network constraints, this study proposes a trajectory anomaly detection algorithm designed to effectively identify potential fraudulent behavior by taxi drivers during passenger pickup. [Methods] The algorithm first performs map matching, aligning trajectory data with the actual road network to obtain a sequence of path segments. Then, a two-stage clustering approach is applied: the matched trajectory paths are initially clustered to extract and expand core road segments, forming multiple core paths. Next, the algorithm calculates the similarity between different core paths and assigns highly similar paths to the same cluster, thereby generating multiple path clusters. Finally, a CostThreshold is computed based on each path cluster. The travel cost of each trajectory, calculated by combining travel time and distance costs, is compared against the corresponding CostThreshold to determine whether the trajectory is anomalous. [Results] Compared with traditional anomaly detection methods on real-world trajectory datasets, the proposed approach demonstrates superior performance in detecting anomalous trajectories. It achieves significantly lower runtime and improves detection accuracy by up to 9.03% compared to the STADCS method. The F1 score also improves considerably compared to the Two-Phase and ATDC methods, with maximum gains of 6.67% and 9.45%, respectively. [Conclusions] This paper presents a detection method that integrates road network constraints with two-stage clustering and travel cost evaluation. The method enhances detection accuracy and efficiency while reducing the false positive rate. It is well-suited for complex urban road networks, offering valuable support for vehicle trajectory data mining and traffic management decision-making, with significant practical value in fraud detection and related fields.

利益冲突:Conflicts of Interest 所有作者声明不存在利益冲突。

All authors disclose no relevant conflicts of interest.

[1]
曹翰林, 唐海娜, 王飞, 等. 轨迹表示学习技术研究进展[J]. 软件学报, 2021, 32(5):1461-1479.

[Cao H L, Tang H N, Wang F, et al. Survey on trajectory representation learning techniques[J]. Journal of Software, 2021, 32(5):1461-1479. ] DOI:10.13328/j.cnki.jos.006210

[2]
Li C N, Feng G W, Li Y N, et al. DiffTAD: Denoising diffusion probabilistic models for vehicle trajectory anomaly detection[J]. Knowledge-Based Systems, 2024, 286:111387. DOI:10.1016/j.knosys.2024.111387

[3]
Zhang S M, Luo Z P, Yang L, et al. A survey of route recommendations: Methods, applications, and opportunities[J]. Information Fusion, 2024, 108:102413. DOI:10.1016/j.inffus.2024.102413

[4]
廖祝华, 张健, 刘毅志, 等. 基于稀疏轨迹数据的出租车载客区域推荐[J]. 电子学报, 2020, 48(11):2178-2185.

DOI

[Liao Z H, Zhang J, Liu Y Z, et al. Taxi pick-up area recommendation based on sparse trajectory data[J]. Acta Electronica Sinica, 2020, 48(11):2178-2185. ]

[5]
Lombardo G, Picone M, Mamei M, et al. Digital twin for continual learning in location based services[J]. Engineering Applications of Artificial Intelligence, 2024, 127:107203. DOI:10.1016/j.engappai.2023.107203

[6]
Almukhalfi H, Noor A, Noor T H. Traffic management approaches using machine learning and deep learning techniques: A survey[J]. Engineering Applications of Artificial Intelligence, 2024, 133:108147. DOI:10.1016/j.engappai.2024.108147

[7]
Ji Y X, Zhou M H, Zheng Y J, et al. Urban passenger-and-package sharing transportation by e-hailing taxis: A simulation-based pricing analysis in Shanghai[J]. Transport Policy, 2024, 156:138-151. DOI:10.1016/j.tranpol.2024.07.020

[8]
Liao T X, Han L Z, Xu Y, et al. Multi-faceted route representation learning for travel time estimation[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25(9):11782-11793. DOI:10.1109/TITS.2024.3371071

[9]
Yin Y F, Xie L, Jiang Z W, et al. A systematic review of human activity recognition based on mobile devices: Overview, progress and trends[J]. IEEE Communications Surveys & Tutorials, 2024, 26(2):890-929. DOI:10.1109/COMST.2024.3357591

[10]
Preeti, Rana C. Artificial intelligence based object detection and traffic prediction by autonomous vehicles:A review[J]. Expert Systems with Applications, 2024, 255:124664. DOI:10.1016/j.eswa.2024.124664

[11]
Gao M X, Guo H J, Liu L W, et al. Integrating street view imagery and taxi trajectory for identifying urban function of street space[J]. Geo-spatial Information Science, 2024,1-23. DOI:10.1080/10095020.2024.2311866

[12]
李超能, 冯冠文, 姚航, 等. 轨迹异常检测研究综述[J]. 软件学报, 2024, 35(2):927-974.

[Li C N, Feng G W, Yao H, et al. Survey on trajectory anomaly detection[J]. Journal of Software, 2024, 35(2):927-974. ] DOI:10.13328/j.cnki.jos.006996

[13]
Wu Y, Fang J H, Chen W, et al. Safety: A spatial and feature mixed outlier detection method for big trajectory data[J]. Information Processing & Management, 2024, 61(3):103679. DOI:10.1016/j.ipm.2024.103679

[14]
Lee J G, Han J W, Li X L. Trajectory outlier detection: A partition-and-detect framework[C]// 2008 IEEE 24th International Conference on Data Engineering. IEEE, 2008:140-149. DOI:10.1109/ICDE.2008.4497422

[15]
Luan F J, Zhang Y T, Cao K Y, et al. Based local density trajectory outlier detection with partition-and-detect framework[C]// 2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD). IEEE, 2017:1708-1714. DOI:10.1109/FSKD.2017.8393023

[16]
Bao L, Du M C. A distance-based trajectory outlier detection method on maritime traffic data[C]// 2018 4th International Conference on Control, Automation and Robotics (ICCAR). IEEE, 2018:340-343. DOI:10.1109/ICCAR.2018.8384697

[17]
Yu Q Y, Luo Y L, Chen C M, et al. Trajectory outlier detection approach based on common slices sub-sequence[J]. Applied Intelligence, 2018, 48(9):2661-2680. DOI:10.1007/s10489-017-1104-z

[18]
Hu X Y, Xu Q, Guo Y J. Trajectory anomaly detection based on the mean distance deviation[M]// Neural Information Processing. Cham: Springer International Publishing, 2020:140-147. DOI:10.1007/978-3-030-63820-7_16

[19]
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. ACM, 2010:1733-1736. DOI:10.1145/1871437.1871716

[20]
Zhang D Q, 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. ACM, 2011:99-108. DOI:10.1145/2030112.2030127

[21]
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. DOI:10.1109/TITS.2013.2238531

[22]
Wang J W, Yuan Y, Ni T L, et al. Anomalous trajectory detection and classification based on difference and intersection set distance[J]. IEEE Transactions on Vehicular Technology, 2020, 69(3):2487-2500. DOI:10.1109/TVT.2020.2967865

[23]
Chen C M, Xu D S, Yu Q Y, et al. Abnormal-trajectory detection method based on variable grid partitioning[J]. ISPRS International Journal of Geo-Information, 2023, 12(2):40. DOI:10.3390/ijgi12020040

[24]
Li H, Achim A, Bull D. Unsupervised video anomaly detection using feature clustering[J]. IET Signal Processing, 2012, 6(5):521-533. DOI:10.1049/iet-spr.2011.0074

[25]
Lu L P, Cheng H, Xiong S W, et al. Distributed anomaly detection algorithm for spatio-temporal trajectories of vehicles[C]// 2017 IEEE International Symposium on Parallel and Distributed Processing with Applications and 2017 IEEE International Conference on Ubiquitous Computing and Communications (ISPA/IUCC). IEEE, 2017:590-598. DOI:10.1109/ISPA/IUCC.2017.00095

[26]
Doshi K, Yilmaz Y. Fast unsupervised anomaly detection in traffic videos[C]// 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW). IEEE, 2020:2658-2664. DOI:10.1109/CVPRW50498.2020.00320

[27]
Lan D T, Yoon S. Trajectory clustering-based anomaly detection in indoor human movement[J]. Sensors, 2023, 23(6):3318. DOI:10.3390/s23063318

[28]
Sánchez Pedroche D, García Herrero J, Molina López J M. Context learning from a ship trajectory cluster for anomaly detection[J]. Neurocomputing, 2024, 563:126920. DOI:10.1016/j.neucom.2023.126920

[29]
Chen C M, Ye Z, Hu F, et al. Vehicle trajectory-clustering method based on road-network-sensitive features[J]. Journal of Intelligent & Fuzzy Systems, 2021, 41(1):2357-2375. DOI:10.3233/jifs-211270

[30]
Knorr E M, Ng R T, Tucakov V. Distance-based outliers: Algorithms and applications[J]. The VLDB Journal, 2000, 8(3):237-253. DOI:10.1007/s007780050006

[31]
Breunig M M, Kriegel H P, Ng R T, et al. LOF: Identifying density-based local outliers[C]// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. ACM, 2000:93-104. DOI:10.1145/342009.335388

[32]
Belhadi A, Djenouri Y, Srivastava G, et al. A two-phase anomaly detection model for secure intelligent transportation ride-hailing trajectories[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(7):4496-4506. DOI:10.1109/TITS.2020.3022612

[33]
He L, Niu X Z, Chen T, et al. Spatio-temporal trajectory anomaly detection based on common sub-sequence[J]. Applied Intelligence, 2022, 52(7):7599-7621. DOI:10.1007/s10489-021-02754-z

文章导航

/