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

李小昌; 陈贝; 董启文; 陆雪松

doi:10.3969/j.issn.1000-5641.202091003

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

doi: 10.3969/j.issn.1000-5641.202091003

华东师范大学数据科学与工程学院, 上海　200062

基金项目: 国家自然科学基金(61672234, U1711262)

详细信息

通讯作者:
陆雪松, 男, 副研究员, 研究方向为计算教育学、金融科技和自然语言处理. E-mail: xslu@dase.ecnu.edu.cn

中图分类号: TP391
计量
- 文章访问数: 210
- HTML全文浏览量: 124
- PDF下载量: 13
- 被引次数: 0
出版历程
- 收稿日期: 2020-08-02
- 网络出版日期: 2020-09-24
- 刊出日期: 2020-09-24

Discovering traveling companions using autoencoders

School of Data Science and Engineering, East China Normal University, Shanghai　200062, China

摘要

摘要: 随着移动设备的广泛应用, 当今的位置跟踪系统不断产生大量的轨迹数据. 同时, 许多应用亟需具备从移动物体的轨迹数据中挖掘出一起旅行的物体(旅行同伴)的能力, 如智慧交通系统和智慧营销. 现有算法或是基于模式挖掘方法, 按照特定模式匹配旅行同伴; 或是基于表征学习方法, 学习相似轨迹的相似表征. 前一种方法受限于点对匹配的问题, 后一种方法往往忽略轨迹之间的时间相近性. 为了改善这些问题, 提出了一个基于自编码器的深度表征学习模型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.
- traveling companion /
- autoencoders /
- spatiotemporal information /
- sort-tile-recursive algorithm /
- attention mechanism

HTML全文

图 1 Mean-Attn模型结构

Fig. 1 The architecture of the Mean-Attn model

下载: 全尺寸图片幻灯片

图 2 主要结果

Fig. 2 Summary of the main results

下载: 全尺寸图片幻灯片

图 3 调节MBR容量

Fig. 3 Varying the MBR capacity

下载: 全尺寸图片幻灯片

图 4 调节小批次大小

Fig. 4 Varying the mini-batch size

下载: 全尺寸图片幻灯片

图 5 位置编码的效果

Fig. 5 The effect of positional encodings

下载: 全尺寸图片幻灯片

图 6 位置编码的效果

Fig. 6 The effect of positional encodings

下载: 全尺寸图片幻灯片

表 1 传统方法效果表

Tab. 1 The performance of traditional methods

算法	变量			簇的个数	单个轨迹的簇
算法	k	m	e / m	簇的个数	单个轨迹的簇
Convoy	18	2	3	308	4 629
Convoy	18	2	5	814	3 875
Swarm	18	2	3	756	4 086
Swarm	18	2	5	2 431	2 710
LSTM-AE				786	895
Mean-Attn				727	1 112

下载: 导出CSV

参考文献(15)

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