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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
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)
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)
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)
Furtado, A.S., Kopanaki, D., Alvares, L.O., Bogorny, V.: Multidimensional similarity measuring for semantic trajectories. Trans. GIS 20(2), 280–298 (2016)
Gonzalez, M.C., Hidalgo, C.A., Barabasi, A.-L.: Understanding individual human mobility patterns. Nature 453(7196), 779–782 (2008)
Halkidi, M., Batistakis, Y., Vazirgiannis, M.: On clustering validation techniques. J. Intell. Inf. Syst. 17, 107–145 (2001)
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)
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)
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
Liu, C., Guo, C.: STCCD: semantic trajectory clustering based on community detection in networks. Expert Syst. Appl. 162, 113689 (2020)
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)
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)
Mello, R.D.S., et al.: MASTER: a multiple aspect view on trajectories. Trans. GIS 23(4), 805–822 (2019)
Meng, F., Yuan, G., Lv, S., Wang, Z., Xia, S.: An overview on trajectory outlier detection. Artif. Intell. Rev. 52, 2437–2456 (2019)
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)
Nanni, M., Pedreschi, D.: Time-focused clustering of trajectories of moving objects. J. Intell. Inf. Syst. 27(3), 267–290 (2006)
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)
Poushter, J., et al.: Smartphone ownership and internet usage continues to climb in emerging economies. Pew Res. Center 22(1), 1–44 (2016)
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)
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)
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)
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)
Tan, P.N., Steinbach, M., Kumar, V.: Introduction to Data Mining. Pearson, London (2018)
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)
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)
Wang, L., Chen, P., Chen, L., Mou, J.: Ship AIS trajectory clustering: an HDBSCAN-based approach. J. Marine Sci. Eng. 9(6), 566 (2021)
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)
Xuhao, G., Junfeng, Z., Zihan, P.: Trajectory clustering for arrival aircraft via new trajectory representation. J. Syst. Eng. Electron. 32(2), 473–486 (2021)
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)
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)
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)
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)
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
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
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)