多角度语义轨迹相似度计算模型

doi:10.3778/j.issn.1673-9418.2008095

摘要/Abstract

摘要：

移动设备的发展使得轨迹数据可以记录更多有用的信息，比如签到信息、活动信息，构成了语义轨迹数据。快速有效的轨迹相似度计算会为分析问题带来巨大好处，已有学者对轨迹相似性及语义轨迹相似性做出研究，并提出了一些有效的方法。但是现有轨迹相似性计算方法无法应用于语义轨迹数据，而目前的语义轨迹相似性计算方法又在轨迹采样频率低的情况下效果不佳。因此在解决轨迹相似性计算对低采样频率敏感的基础上，结合了语义轨迹的附加访问地点信息，提出了一种新的轨迹相似性计算模型，叫作多角度语义轨迹（MAST）相似度计算。模型基于LSTM并且引入自注意力机制，学习到的轨迹表达为多个关注轨迹不同方面的低维向量，构成了一个矩阵，从而解决了单一向量无法准确表达轨迹的问题。这个矩阵不仅包含轨迹的空间信息，也包含语义信息，可用于计算语义轨迹相似度。提出的模型在两个现实语义轨迹数据集上进行实验，实验数据表明MAST的计算结果优于现有方法。

关键词: 轨迹相似度计算, 语义轨迹, 自注意力机制, 深度表示学习

Abstract:

The development of mobile devices enables trajectory data to record more useful information, such as check in information and activity information, constituting semantic trajectory data. Fast and effective trajectory similarity computation will bring great benefits to the analysis of problems. Scholars have studied trajectory similarity and semantic trajectory similarity and have proposed some effective methods. However, existing trajectory similarity computation methods cannot be applied to semantic trajectory data, and the current semantic trajectory similarity computation methods do not work well under the condition of low trajectory sampling frequency. In this paper, on the basis of solving the sensitivity of trajectory similarity computation to low sampling frequency, combined with the additional visited point information of semantic trajectory, a new trajectory similarity computation model is proposed, which is called multi-aspect semantic trajectory (MAST). The model is based on LSTM (long short-term memory) and introduces the self-attention mechanism. The learned trajectory is expressed as multiple low-dimensional vectors of different aspects of the trajectory, forming a matrix, thereby solving the problem that a single vector cannot accurately express the trajectory. This matrix contains not only the spatial information of the trajectory, but also the semantic information, which can be used to calculate the similarity of the semantic trajectory. MAST is tested on two realistic semantic trajectory datasets. Experimental data show that MAST is superior to existing methods.

Key words: trajectory similarity computation, semantic trajectory, self-attention mechanism, deep representation learning

蔡明昕, 孙晶, 王斌. 多角度语义轨迹相似度计算模型[J]. 计算机科学与探索, 2021, 15(9): 1632-1640.

CAI Mingxin, SUN Jing, WANG Bin. Multi-aspect Semantic Trajectory Similarity Computation Model[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(9): 1632-1640.

参考文献

[1] HUNG C C, PENG W C, LEE W C. Clustering and aggre-gating clues of trajectories for mining trajectory patterns and routes[J]. The VLDB Journal, 2015, 24(2): 169-192.
[2] ZHU J, JIANG W, LIU A, et al. Effective and efficient tra-jectory outlier detection based on time-dependent popular route[J]. World Wide Web: Internet and Web Information Systems, 2017, 20(1): 111-134.
[3] LI Z H, HAN J W, JI M, et al. MoveMine: mining moving object data for discovery of animal movement patterns[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(4): 1-32.
[4] BICHICCHI A, BELAROUSSI R, SIMONE A, et al. Analysis of road-user interaction by extraction of driver behavior features using deep learning[J]. IEEE Access, 2020, 8: 19638-19645.
[5] YI B K, JAGADISH H V, FALOUTSOS C. Efficient retrieval of similar time sequences under time warping[C]//Proceedings of the 14th International Conference on Data Engineering, Orlando, Feb 23-27, 1998. Washington: IEEE Computer Society, 1998: 201-208.
[6] VLACHOS M, KOLLIOS G, GUNOPULOS D. Discover-ing similar multidimensional trajectories[C]//Proceedings of the 18th International Conference on Data Engineering, San Jose, Feb 26-Mar 1, 2002. Washington: IEEE Computer Society, 2002: 673-684.
[7] CHEN L, ?ZSU M T, ORIA V. Robust and fast similarity search for moving object trajectories[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, Jun 14-16, 2005. New York: ACM, 2005: 491-502.
[8] SU H, ZHENG K, WANG H Z, et al. Calibrating trajectory data for similarity-based analysis[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, Jun 22-27, 2013. New York: ACM, 2013: 833-844.
[9] RANU S, DEEPAK P, TELANG A D, et al. Indexing and matching trajectories under inconsistent sampling rates[C]//Proceedings of the 31st IEEE International Conference on Data Engineering, Seoul, Apr 13-17, 2015. Washington: IEEE Computer Society, 2015: 999-1010.
[10] LI X C, ZHAO K Q, CONG G, et al. Deep representation learning for trajectory similarity computation[C]//Proceedings of the 34th IEEE International Conference on Data Engineering, Paris, Apr 16-19, 2018. Washington: IEEE Computer Society, 2018: 617-628.
[11] ALVARES L O, BOGORNY V, KUIJPERS B, et al. A model for enriching trajectories with semantic geographical information[C]//Proceedings of the 15th ACM International Symposium on Geographic Information Systems, Seattle, Nov 7-9, 2007. New York: ACM, 2007: 22.
[12] PARENT C, SPACCAPIETRA S, RENSO C, et al. Semantic trajectories modeling and analysis[J]. ACM Computing Surveys, 2013, 45(4): 1-32.
[13] YING J J C, LU E H C, LEE W C, et al. Mining user simi-larity from semantic trajectories[C]//Proceedings of the 2010 International Workshop on Location Based Social Networks, San Jose, Nov 2, 2010. New York: ACM, 2010: 19-26.
[14] BOGORNY V, RENSO C, DE AQUINO A R, et al. Constant-a conceptual data model for semantic trajectories of moving objects[J]. Transactions in GIS, 2014, 18(1): 66-88.
[15] SPACCAPIETRA S, PARENT C, DAMIANI M L, et al. A conceptual view on trajectories[J]. Data & Knowledge Engi-neering, 2008, 65(1): 126-146.
[16] VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need[C]//Proceedings of the 30th Annual Conference on Neural Information Processing Systems, Long Beach, Dec 4-9, 2017. Red Hook: Curran Associates, 2017: 5998-6008.
[17] LIU H, SCHNEIDER M. Similarity measurement of moving object trajectories[C]//Proceedings of the 3rd ACM SIG-SPATIAL International Workshop on GeoStreaming, Redondo Beach, Nov 6, 2012. New York: ACM, 2012: 19-22.
[18] XIAO X, ZHENG Y, LUO Q, et al. Inferring social ties between users with human location history[J]. Journal of Ambient Intelligence and Humanized Computing, 2014, 5(1): 3-19.
[19] FURTADO A S, KOPANAKI D, ALVARES L O, et al. Multidimensional similarity measuring for semantic trajectories[J]. Transactions in GIS, 2016, 20(2): 280-298.