基于自编码器的旅行同伴挖掘

doi:10.3969/j.issn.1000-5641.202091003

摘要/Abstract

摘要： 随着移动设备的广泛应用, 当今的位置跟踪系统不断产生大量的轨迹数据. 同时, 许多应用亟需具备从移动物体的轨迹数据中挖掘出一起旅行的物体(旅行同伴)的能力, 如智慧交通系统和智慧营销. 现有算法或是基于模式挖掘方法, 按照特定模式匹配旅行同伴; 或是基于表征学习方法, 学习相似轨迹的相似表征. 前一种方法受限于点对匹配的问题, 后一种方法往往忽略轨迹之间的时间相近性. 为了改善这些问题, 提出了一个基于自编码器的深度表征学习模型Mean-Attn(Mean-Attention), 用于发现旅行同伴. Mean-Attn分别使用低维稠密向量表征和位置编码技术, 将空间和时间信息同时注入轨迹的嵌入表征中; 此外, 还利用Sort-Tile-Recursive(STR)算法、均值运算和全局注意力机制, 鼓励轨迹向邻近的轨迹学习; 从编码器获得轨迹表征后, 利用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)对表征进行聚类, 从而找到旅行同伴. 实验结果表明, Mean-Attn在寻找旅行同伴方面的表现要优于传统的数据挖掘算法和最新的深度学习算法.

关键词: 旅伴同伴, 自编码器, 时空信息, STR算法, 注意力机制

Abstract: With the widespread adoption of mobile devices, today’s location tracking systems are producing tremendous amounts of trajectory data on a continuous basis. The ability to discover moving objects that travel together (i.e., traveling companions) from their respective trajectories is desirable for many applications, including intelligent transportation systems and intelligent advertising. Existing algorithms are either based on pattern mining methods that define a particular pattern of traveling companions or based on representation learning methods that learn similar representations for similar trajectories. The former method suffers from the pairwise point-matching problem, and the latter often ignores the temporal proximity between trajectories. In this work, we propose a deep representation learning model using autoencoders, namely Mean-Attn (Mean-Attention) , for the discovery of traveling companions. Mean-Attn collectively injects spatial and temporal information into its input embeddings using skip-gram and positional encoding techniques, respectively. In addition, our model encourages trajectories to learn from their neighbors by leveraging the sort-tile-recursive (STR) algorithm as well as the mean operation and global attention mechanisms. After obtaining the representations from the encoder, we run DBSCAN (Density-Based Spatial Clustering of Applications with Noise) to cluster the representations and find traveling companions. Experimental results suggest that Mean-Attn performs better than the state-of-the-art data mining and deep learning algorithms for locating traveling companions.

Key words: traveling companion, autoencoders, spatiotemporal information, sort-tile-recursive algorithm, attention mechanism

中图分类号:

TP391

李小昌, 陈贝, 董启文, 陆雪松. 基于自编码器的旅行同伴挖掘[J]. 华东师范大学学报（自然科学版）, 2020, 2020(5): 179-188.

LI Xiaochang, CHEN Bei, DONG Qiwen, LU Xuesong. Discovering traveling companions using autoencoders[J]. Journal of East China Normal University(Natural Science), 2020, 2020(5): 179-188.

参考文献

[1] VERES M, MOUSSA M. Deep learning for intelligent transportation systems: A survey of emerging trends [J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 12(8): 3152-3168.
[2] GHOSE A, LI B B, LIU S Y. Mobile targeting using customer trajectory patterns [J]. Management Science, 2019, 65(11): 5027-5049.
[3] JEUNG H, YIU M L, ZHOU X F, et al. Discovery of convoys in trajectory databases [J]. Proceedings of the VLDB Endowment, 2008, 1(1): 1068-1080.
[4] LI Z H, DING B L, HAN J W, et al. Swarm: Mining relaxed temporal moving object clusters [J]. Proceedings of the VLDB Endowment, 2010, 3(1/2): 723-734.
[5] ZHENG K, ZHENG Y, YUAN N J, et al. Online discovery of gathering patterns over trajectories [J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1974-1988.
[6] LI X C, ZHAO K Q, CONG G, et al. Deep representation learning for trajectory similarity computation [C]// 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, 2018: 617–628.
[7] YAO D, CONG G, ZHANG C, et al. Computing trajectory similarity in linear time: A generic seed-guided neural metric learning approach [C]// 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 2019: 1358–1369.
[8] YAO D, ZHANG C, ZHU Z H, et al. Trajectory clustering via deep representation learning [C]// 2017 International Joint Conference on Neural Networks (IJCNN). IEEE, 2017: 3880–3887.
[9] CHU E, LIU P J. MeanSum: A neural model for unsupervised multi-document abstractive summarization [EB/OL].(2019-05-22)[2020-07-01]. https://arxiv.org/pdf/1810.05739.pdf.
[10] LEUTENEGGER S T, LOPEZ M A, EDGINGTON J. STR: A simple and efficient algorithm for R-tree packing [C]// Proceedings 13th International Conference on Data Engineering. IEEE, 1997: 497–506.
[11] GEHRING J, AULI M, GRANGIER D, et al. Convolutional sequence to sequence learning [C]// Proceedings of the 34th International Conference on Machine Learning - Volume 70. New York: JMLR, 2017: 1243–1252.
[12] AL-NAYMAT G, CHAWLA S, GUDMUNDSSON J. Dimensionality reduction for long duration and complex spatio-temporal queries [C]// Proceedings of the 2007 ACM Symposium on Applied Computing. ACM, 2007: 393–397.
[13] ZHANG Y F, LIU A, LIU G F, et al. Deep representation learning of activity trajectory similarity computation [C]//IEEE International Conference on Web Services (ICWS). IEEE, 2019: 312–319.
[14] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality [C]// Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2. New York: Curran Associates Inc., 2019: 3111–3119.
[15] VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need [C]// Proceedings of the 31st International Conference on Neural Information Processing Systems. New York: Curran Associates Inc., 2017: 6000-6010.