Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Spatio-temporal trajectory anomaly detection based on common sub-sequence

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

With the rapid development of GPS positioning and wireless communication, more and more trajectories are collected. How to accurately and efficiently detect abnormal trajectories from a large number of trajectories has become a focused issue. The similarity measurement method adopted by the existing abnormal trajectory detection technology often ignores the situation that the abnormal sub-trajectory has enough neighbors. If a trajectory is composed of multiple such sub-trajectories, this anomaly will not be detected. At present, the trajectory outlier detection algorithm based on common slices sub-sequence(TODCSS) has improved the above problems. However, it is not accurate enough in feature extraction. Its detection scope is limited to 2D-plane and the time dimension is ignored, so it can’t detect abnormal vehicle behaviors such as multiple stops, detention, too slow speed and so on. Based on the above problems, this paper proposes a spatio-temporal trajectory anomaly detection based on common sub-sequence (STADCS). Firstly, in order to obtain accurate and reasonable similar trajectories, the length of sub-trajectory is added to the common sequence of trajectories, and non-common parts between two trajectories are added to the similarity measurement. Then the time is added to detect trajectories of time anomalies. It improves the accuracy and rationality of detection. Finally, we conducted experiments on real datasets and used F1 − measure to evaluate the accuracy of this algorithm. Compared with existing algorithms, the accuracy of STADCS is improved by about 15.15%.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Knorr EM, Ng RT, Tucakov V (2000) Distance-Based Outliers: Algorithms and applications. VLDB J 8(3):237–253

    Article  Google Scholar 

  2. Li XL, Han JW, Kim S, Gonzalez H (2007) ROAM: Rule- and Motif-Based anomaly detection in massive moving object data sets proceedings of the seventh siam international conference on data mining. Siam, Philadelphia

    Google Scholar 

  3. Lee JG, Han JW, Li XL, IEEE (2008) Trajectory outlier detection: A partition-and-detect framework. In: 2008 Ieee 24th International Conference on Data Engineering. IEEE International Conference on Data Engineering, vol 1-3. IEEE, New York, pp 140-+. https://doi.org/10.1109/icde.2008.4497422

  4. Lee J -G, Han J, Whang K -Y (2007) Trajectory clustering: a partition-and-group framework, SIGMOD. In: 2007: ACM SIGMOD International conference on management of data. https://doi.org/10.1145/1247480.1247546. Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, Beijing, pp 593–604

  5. Yu QY, Luo YL, Chen CM, Wang XH (2018) Trajectory outlier detection approach based on common slices sub-sequence. Appl Intell 48(9):2661–2680. https://doi.org/10.1007/s10489-017-1104-z

    Article  Google Scholar 

  6. Vlachos M, Kollios G, Gunopulos D (2002) Discovering similar multidimensional trajectories. In: Agrawal R, Dittrich K, Ngu A H H (eds) 18Th international conference on data engineering, proceedings. IEEE international conference on data engineering. https://doi.org/10.1109/icde.2002.994784. Ieee Computer Soc, Los Alamitos, pp 673–684

  7. Chen L, Ozsu MT, Oria V (2005) Robust and fast similarity search for moving object trajectories, SIGMOD. In: 2005: ACM SIGMOD International conference on management of data. Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, Baltimore, pp 491–502

  8. Birant D, Kut A (2006) Spatio-temporal outlier detection in large databases. J Comput Inf Technol 14(4):291–297. https://doi.org/10.2498/cit.2006.04.04

    Article  Google Scholar 

  9. Chen C, Zhang DQ, Castro PS, Li N, Sun L, Li SJ, Wang ZH (2013) iBOAT: Isolation-Based Online Anomalous Trajectory Detection. IEEE Trans Intell Transp Syst 14 (2):806–818. https://doi.org/10.1109/tits.2013.2238531

  10. Mohamad I, Ali MAM, Ismail M (2011) Abnormal driving detection using real time global positioning system data. In: 2011 IEEE International Conference on Space Science and Communication: Towards Exploring the Equatorial Phenomena, IconSpace 2011, Penang, Malaysia, 2011 IEEE International Conference on Space Science and Communication: “Towards Exploring the Equatorial Phenomena”, IconSpace 2011 - Proceedings. IEEE Computer Society, pp 1–6. https://doi.org/10.1109/IConSpace.2011.6015840

  11. Zhang DZ, Lee K, Lee I (2019) Mining hierarchical semantic periodic patterns from GPS-collected spatio-temporal trajectories. Expert Syst Appl 122:85–101. https://doi.org/10.1016/j.eswa.2018.12.047

    Article  Google Scholar 

  12. Yu QY, Luo YL, Chen CM, Chen SG (2019) Trajectory similarity clustering based on multi-feature distance measurement. Appl Intell 49(6):2315–2338. https://doi.org/10.1007/s10489-018-1385-x

    Article  Google Scholar 

  13. Gan G, Ng MK-P (2017) k-means clustering with outlier removal. Pattern Recognition Letters 90:8–14. https://doi.org/10.1016/j.patrec.2017.03.008

  14. Lv M, Chen L, Xu Z, Li Y, Chen G (2016) The discovery of personally semantic places based on trajectory data mining. Neurocomputing 173:1142–1153

    Article  Google Scholar 

  15. Li XL, Han JW, Kim S (2006) Motion-alert: Automatic anomaly detection in massive moving objects. In: Mehrotra S, Zeng D D, Chen H, Thuraisingham B, Wang F Y (eds) Intelligence and Security Informatics, Proceedings, Lecture Notes in Computer Science, vol 3975. Springer, Berlin, pp 166–177

  16. Yang WQ, Gao Y, Cao LB (2013) TRASMIL: A local anomaly detection framework based on trajectory segmentation and multi-instance learning. Comput Vis Image Underst 117(10):1273–1286. https://doi.org/10.1016/j.cviu.2012.08.010

    Article  Google Scholar 

  17. Lei PR (2016) A framework for anomaly detection in maritime trajectory behavior. Knowl Inf Syst 47(1):189–214. https://doi.org/10.1007/s10115-015-0845-4

    Article  Google Scholar 

  18. Shen M, Liu D -R, Shann S -H (2015) Outlier detection from vehicle trajectories to discover roaming events. Inf Sci 294:242–254. https://doi.org/10.1016/j.ins.2014.09.037

    Article  MathSciNet  Google Scholar 

  19. Liu W, Zheng Y, Chawla S, Yuan J, Xie X Discovering spatio-temporal causal interactions in traffic data streams. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’11, 2011. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, pp 1010–1018. https://doi.org/10.1145/2020408.2020571

  20. Chawla S, Zheng Y, Hu JF (2012) Inferring the root cause in road traffic anomalies. In: Zaki M J, Siebes A, Yu J X, Goethals B, Webb G, Wu X (eds) 12Th ieee international conference on data mining. IEEE international conference on data mining. https://doi.org/10.1109/icdm.2012.104. IEEE, New York, pp 141–150

  21. Liu L -X, Qiao S -J, Liu B, Le J -J, Tang C -J (2009) Efficient trajectory outlier detection algorithm based on R-tree. J Softw 20(9):2426–2435. https://doi.org/10.3724/SP.J.1001.2009.03580

  22. Liu L -X, Le J -J, Qiao S -J, Song J -T (2011) Trajectory outliers detection based on local outlying degree. Chin J Comput 34(10):1966–1975. https://doi.org/10.3724/SP.J.1016.2011.01966

  23. Bu YY, Chen L, Fu AWC, Liu DW (Acm (2009) Efficient Anomaly Monitoring Over Moving Object Trajectory Streams Kdd-09: 15th Acm Sigkdd Conference on Knowledge Discovery and Data Mining. Assoc Computing Machinery, New York

  24. Zhang DQ, Li N, Zhou ZH, Chen C, Sun L, Li SJ, Assoc Comp M (2011) IBAT: Detecting Anomalous Taxi Trajectories from GPS Traces. Ubicomp’11: Proceedings of the 2011 Acm International Conference on Ubiquitous Computing. Assoc Computing Machinery, New York

    Google Scholar 

  25. Mao J -L, Jin C -Q, Zhang Z -G, Zhou A -Y (2017) Anomaly detection for trajectory big data: Advancements and framework. J Softw 28(1):17–34. https://doi.org/10.13328/j.cnki.jos.005151

    Google Scholar 

  26. Piorkowski M, Sarafijanovic-Djukic N, Grossglauser M (2009) CRAWDAD dataset epfl/mobility(v 2009-02-24)[EB/OL]. http://crawdad.org/epfl/mobility/20090224/. Accessed 24 Feb 2009

  27. Lion M, Chen L, Qu H et al (2007) Taxi GPS reports in Shanghai, China. Smart City Research Group. https://www.cse.ust.hk/scrg/, Accessed 23 Jul 2007

  28. Kong XJ, Song XM, Xia F, Guo HC, Wang JZ, Tolba A (2018) LoTAD: long-term traffic anomaly detection based on crowdsourced bus trajectory data. World Wide Web 21(3):825–847. https://doi.org/10.1007/s11280-017-0487-4

    Article  Google Scholar 

  29. Ge Y, Xiong H, Zhou Z -H, Ozdemir H, Yu J, Lee K C T O P -E Y E Top-k evolving trajectory outlier detection. In: CIKM’10 - Proceedings of the 19th International Conference on Information and Knowledge Management and Co-located Workshops, 2010, International Conference on Information and Knowledge Management. Proceedings. Association for Computing Machinery, pp 1733–1736. https://doi.org/10.1145/1871437.1871716

  30. Guo Y (2019) Shnn-cad+: an improvement on shnn-cad for adaptive online trajectory anomaly detection. Sens (Switzerland) 19(1). https://doi.org/10.3390/s19010084

  31. Roman IS, de Diego IM, Conde C, Cabello E (2019) Outlier trajectory detection through a context-aware distance. Pattern Anal Appl 22(3):831–839. https://doi.org/10.1007/s10044-018-0732-1

    Article  MathSciNet  Google Scholar 

  32. Belhadi A, Djenouri Y, Srivastava G, Djenouri D, Lin J C -W, Fortino G (2021) Deep learning for pedestrian collective behavior analysis in smart cities: a model of group trajectory outlier detection. Inf Fusion 65:13–20. https://doi.org/10.1016/j.inffus.2020.08.003

    Article  Google Scholar 

  33. Cao K, Liu Y, Meng G, Liu H, Miao A, Xu J (2020) Trajectory outlier detection on trajectory data streams. IEEE Access 8:34187–34196. https://doi.org/10.1109/ACCESS.2020.2974521

    Article  Google Scholar 

  34. Ding ZG, Xing LD, Mo YC (2020) Mapping grid based online taxi anomalous trajectory detection. Int J Syst Sci 51(9):1589–1603. https://doi.org/10.1080/00207721.2020.1772397

    Article  Google Scholar 

  35. Wang Z, Yuan G, Pei H, Zhang Y, Liu X (2020) Unsupervised learning trajectory anomaly detection algorithm based on deep representation. Int J Distrib Sens Netw 16(12). https://doi.org/10.1177/1550147720971504

  36. Xie W, Chkrebtii O, Kurtek S (2020) Visualization and outlier detection for multivariate elastic curve data. IEEE Trans Vis Comput Graph 26(11):3353–3364. https://doi.org/10.1109/TVCG.2019.2921541

    Article  Google Scholar 

Download references

Acknowledgments

This research is sponsored by the Science and Technology Planning Project of Sichuan Province under Grant No. 2020YFG0054, and the Joint Funds of the Ministry of Education of China.

Author information

Authors and Affiliations

  1. School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu, China

    Ling He

  2. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China

    Xinzheng Niu, Ting Chen, Kejin Mei & Mao Li

Authors
  1. Ling He
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xinzheng Niu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ting Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kejin Mei
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Mao Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xinzheng Niu.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

He, L., Niu, X., Chen, T. et al. Spatio-temporal trajectory anomaly detection based on common sub-sequence. Appl Intell 52, 7599–7621 (2022). https://doi.org/10.1007/s10489-021-02754-z

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-021-02754-z

Keywords

Search

Navigation