Skip to main content
SpringerLink
Log in

MAT-Tree: A Tree-Based Method for Multiple Aspect Trajectory Clustering

  • Conference paper
  • First Online:
Intelligent Systems (BRACIS 2023)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 14195))

Included in the following conference series:

Abstract

Multiple aspect trajectory is a relevant concept that enables mining interesting patterns and behaviors of moving objects for different applications. This new way of looking at trajectories includes a semantic dimension, which presents the notion of aspects that are relevant facts of the real world that add more meaning to spatio-temporal data. Given the inherent complexity of this new type of data, the development of new data mining methods is needed. Despite some works have already focused on multiple aspect trajectory classification, few have focused on clustering. Although the literature presents several raw trajectory clustering algorithms, they do not deal with the heterogeneity of the semantic dimension. In this paper, we propose a novel hierarchical clustering algorithm for multiple aspect trajectories using a decision tree structure that chooses the best aspect to branch and group the most similar trajectories according to different criteria. We ran experiments using a well-known benchmark dataset extracted from a location-based social network and compared our clustering results with a state-of-the-art clustering approach over different internal and external validation metrics. As a result, we show that the proposed method outperformed the baseline, where it revealed a formation of more cohesive and homogeneous clusters in 88% of the clusters, being five times more precise according to the external metrics.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    https://github.com/bigdata-ufsc/mat_tree.

References

  1. Alvares, L.O., Bogorny, V., Kuijpers, B., de Macedo, J.A.F., Moelans, B., Vaisman, A.: A model for enriching trajectories with semantic geographical information. In: Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems, pp. 1–8 (2007)

    Google Scholar 

  2. Chen, J., Wang, R., Liu, L., Song, J.: Clustering of trajectories based on Hausdorff distance. In: 2011 International Conference on Electronics, Communications and Control (ICECC), pp. 1940–1944 (2011)

    Google Scholar 

  3. Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P., et al.: Knowledge discovery and data mining: towards a unifying framework. In: KDD, vol. 96, pp. 82–88 (1996)

    Google Scholar 

  4. Furtado, A.S., Kopanaki, D., Alvares, L.O., Bogorny, V.: Multidimensional similarity measuring for semantic trajectories. Trans. GIS 20(2), 280–298 (2016)

    Article  Google Scholar 

  5. Gonzalez, M.C., Hidalgo, C.A., Barabasi, A.-L.: Understanding individual human mobility patterns. Nature 453(7196), 779–782 (2008)

    Article  Google Scholar 

  6. Halkidi, M., Batistakis, Y., Vazirgiannis, M.: On clustering validation techniques. J. Intell. Inf. Syst. 17, 107–145 (2001)

    Article  MATH  Google Scholar 

  7. Hung, C.-C., Peng, W.-C., Lee, W.-C.: Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. VLDB J. 24, 169–192 (2015)

    Article  Google Scholar 

  8. Zheng, K., Zheng, Y., Yuan, N.J., Shang, S.: On discovery of gathering patterns from trajectories. In: Proceedings of the IEEE International Conference on Data Engineering, Washington, DC. IEEE (2013)

    Google Scholar 

  9. Khoroshevsky, F., Lerner, B.: Human mobility-pattern discovery and next-place prediction from GPS data. In: Schwenker, F., Scherer, S. (eds.) MPRSS 2016. LNCS (LNAI), vol. 10183, pp. 24–35. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59259-6_3

    Chapter  Google Scholar 

  10. Liu, C., Guo, C.: STCCD: semantic trajectory clustering based on community detection in networks. Expert Syst. Appl. 162, 113689 (2020)

    Article  Google Scholar 

  11. Liu, G., Fan, Y., Zhang, J., Wen, P., Lyu, Z., Yuan, X.: Deep flight track clustering based on spatial-temporal distance and denoising auto-encoding. Expert Syst. Appl. 198, 116733 (2022)

    Article  Google Scholar 

  12. May Petry, L., Leite Da Silva, C., Esuli, A., Renso, C., Bogorny, V.: MARC: a robust method for multiple-aspect trajectory classification via space, time, and semantic embeddings. Int. J. Geogr. Inf. Sci. 34(7), 1428–1450 (2020)

    Google Scholar 

  13. Mello, R.D.S., et al.: MASTER: a multiple aspect view on trajectories. Trans. GIS 23(4), 805–822 (2019)

    Article  Google Scholar 

  14. Meng, F., Yuan, G., Lv, S., Wang, Z., Xia, S.: An overview on trajectory outlier detection. Artif. Intell. Rev. 52, 2437–2456 (2019)

    Article  Google Scholar 

  15. Morris, B., Trivedi, M.: Learning trajectory patterns by clustering: experimental studies and comparative evaluation. In: 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 312–319 (2009)

    Google Scholar 

  16. Nanni, M., Pedreschi, D.: Time-focused clustering of trajectories of moving objects. J. Intell. Inf. Syst. 27(3), 267–290 (2006)

    Article  Google Scholar 

  17. Petry, L.M., Ferrero, C.A., Alvares, L.O., Renso, C., Bogorny, V.: Towards semantic-aware multiple-aspect trajectory similarity measuring. Trans. GIS 23(5), 960–975 (2019)

    Article  Google Scholar 

  18. Poushter, J., et al.: Smartphone ownership and internet usage continues to climb in emerging economies. Pew Res. Center 22(1), 1–44 (2016)

    Google Scholar 

  19. Rendón, E., Abundez, I., Arizmendi, A., Quiroz, E.M.: Internal versus external cluster validation indexes. Int. J. Comput. Commun. 5(1), 27–34 (2011)

    Google Scholar 

  20. Santos, Y., Carvalho, J.T., Bogorny, V.: SS-OCoClus: a contiguous order-aware method for semantic trajectory co-clustering. In: 2022 23rd IEEE International Conference on Mobile Data Management (MDM), pp. 198–207 (2022)

    Google Scholar 

  21. Spaccapietra, S., Parent, C., Damiani, M.L., de Macedo, J.A., Porto, F., Vangenot, C.: A conceptual view on trajectories. Data Knowl. Eng. 65(1), 126–146 (2008)

    Article  Google Scholar 

  22. Sun, M., Wang, J.: An approach of ship trajectory clustering based on minimum bounding rectangle and buffer similarity. In: IOP Conference Series: Earth and Environmental Science, vol. 769 (2021)

    Google Scholar 

  23. Tan, P.N., Steinbach, M., Kumar, V.: Introduction to Data Mining. Pearson, London (2018)

    MATH  Google Scholar 

  24. Tortelli Portela, T., Tyska Carvalho, J., Bogorny, V.: HiPerMovelets: high-performance movelet extraction for trajectory classification. Int. J. Geograph. Inf. Sci. 36(5), 1012–1036 (2022)

    Article  Google Scholar 

  25. Varlamis, I., et al.: A novel similarity measure for multiple aspect trajectory clustering. In: Proceedings of the 36th Annual ACM Symposium on Applied Computing, pp. 551–558 (2021)

    Google Scholar 

  26. Wang, L., Chen, P., Chen, L., Mou, J.: Ship AIS trajectory clustering: an HDBSCAN-based approach. J. Marine Sci. Eng. 9(6), 566 (2021)

    Article  Google Scholar 

  27. Wu, S.X., Wu, Z., Zhu, W., Yang, X., Li, Y.: Mining trajectory patterns with point-of-interest and behavior-of-interest. In: 2021 IEEE International Conference on Communications Workshops (ICC Workshops), pp. 1–6. IEEE (2021)

    Google Scholar 

  28. Xuhao, G., Junfeng, Z., Zihan, P.: Trajectory clustering for arrival aircraft via new trajectory representation. J. Syst. Eng. Electron. 32(2), 473–486 (2021)

    Article  Google Scholar 

  29. Yang, D., Zhang, D., Zheng, V.W., Yu, Z.: Modeling user activity preference by leveraging user spatial temporal characteristics in LBSNs. IEEE Trans. Syst. Man Cybern.: Syst. 45(1), 129–142 (2014)

    Article  Google Scholar 

  30. Yao, D., Zhang, C., Zhu, Z., Huang, J., Bi, J.: Trajectory clustering via deep representation learning. In: 2017 International Joint Conference on Neural Networks (IJCNN), pp. 3880–3887. IEEE (2017)

    Google Scholar 

  31. Yuan, G., Xia, S., Zhang, L., Zhou, Y., Ji, C.: An efficient trajectory-clustering algorithm based on an index tree. Trans. Inst. Meas. Control. 34(7), 850–861 (2012)

    Article  Google Scholar 

  32. Yuan, G., Sun, P., Zhao, J., Li, D., Wang, C.: A review of moving object trajectory clustering algorithms. Artif. Intell. Rev. 47, 123–144 (2017)

    Article  Google Scholar 

Download references

Acknowledgements

This work has been partially supported by CAPES (Finance code 001), CNPQ, FAPESC (Project Match - co-financing of H2020 Projects - Grant 2018TR 1266), and the European Union’s Horizon 2020 research and innovation programme under GA N. 777695 (MASTER). We also thank the reviewers who contributed to the improvement of this work. The views and opinions expressed in this paper are the sole responsibility of the author and do not necessarily reflect the views of the European Commission.

Author information

Authors and Affiliations

  1. Universidade Federal de Santa Catarina, Florianópolis, Brazil

    Yuri Santos, Ricardo Giuliani, Mateus Grellert & Jônata Tyska Carvalho

  2. INE, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, Brazil

    Yuri Santos, Vania Bogorny, Mateus Grellert & Jônata Tyska Carvalho

Authors
  1. Yuri Santos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ricardo Giuliani
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vania Bogorny
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mateus Grellert
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jônata Tyska Carvalho
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuri Santos .

Editor information

Editors and Affiliations

  1. Federal University of São Carlos, São Carlos, Brazil

    Murilo C. Naldi

  2. Centro Universitario da FEI, São Bernardo do Campo, Brazil

    Reinaldo A. C. Bianchi

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Santos, Y., Giuliani, R., Bogorny, V., Grellert, M., Carvalho, J.T. (2023). MAT-Tree: A Tree-Based Method for Multiple Aspect Trajectory Clustering. In: Naldi, M.C., Bianchi, R.A.C. (eds) Intelligent Systems. BRACIS 2023. Lecture Notes in Computer Science(), vol 14195. Springer, Cham. https://doi.org/10.1007/978-3-031-45368-7_30

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-45368-7_30

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-45367-0

  • Online ISBN: 978-3-031-45368-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation