Discovering traveling companions using autoencoders

doi:10.3969/j.issn.1000-5641.202091003

Abstract

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

CLC Number:

TP391

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.

References

[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.