轨迹相似度计算是轨迹分析的重要形式。随着科技发展，越来越多的时空轨迹数据被收集。现有的轨迹相似性学习方案只考虑空间维度，在有时间感知的场景中效率低下。本次为大家带来国际数据挖掘顶级会议KDD 2022上的论文：《ST2Vec: Spatio-Temporal Trajectory Similarity Learning in Road Networks》
一. 背景
随着配备GPS的设备和基于在线地图服务的普及，人和车辆等移动物体的时空轨迹被大量收集，这也激发了对于轨迹分析的各种研究。轨迹相似度计算是轨迹分析的一种重要形式，用于评估两个轨迹之间的相似性，具有广泛的现实应用如拼车、社会推荐等。
对于相似性的度量，存在各种手工距离度量方式，但由于他们依赖于点态匹配计算，需要较高的计算成本。而利用神经网络学习轨迹相似性进行相似性计算可以很好地解决这一问题，通过神经网络获得轨迹表征嵌入后，轨迹之间的相似性关系可以在嵌入空间中保持良好，同时又减少了时间复杂性。
然而，现有的轨迹相似性学习方案强调空间相似性而忽视了时空轨迹的时间维度，这使得它们在有时间感知的场景中效率低下。为什么时间维度如此重要呢？举个例子来说，在拼车过程中，T1表示司机计划的行程，T2和T3是两个想要搭车的人。T1和T2在空间上更接近，因此仅考虑空间相似性的算法会推荐T2。然而，T1和T2的出发时间相去甚远。而T3虽然距T1空间上较远，但却和T1是相近的出发时间。因此，从时空两方面考虑，应选择T3。
实现道路网络中的时空轨迹相似性学习有两种方法，一种是将时间划分为时间片，然后分别处理空间和时间，但问题是对时间维度的粗粒度离散化并不能充分利用时间信息。另一种更有前途的方向是学习统一的时空嵌入，以捕捉轨迹之间复杂的时空相似性。现有研究仍有三个重大挑战有待解决：一是时间嵌入，如何捕捉轨迹之间的时间相关性生成嵌入。由于时间的连续性以及轨迹的周期性，直接将时间序列输入递归神经网络（RNN）模型是无效的。二是时空融合，如何融合嵌入实现统一的时空相似性学习。三是模型优化，如何提高有效性（即相似度查询质量）和效率（即模型收敛速度）。
文章提出了ST2Vec，一种基于轨迹表征学习的架构。它考虑了轨迹之间的细粒度时空相关性，很好地解决了三大挑战。文章还提到，这是第一个关于时空轨迹相似性分析的深度学习方案。
二. 相关定义
三. 基本框架
图1 ST2Vec的体系结构和训练方案
首先，用相似和不同的轨迹对来构造相似三联体，并且同时考虑空间和时间维度。然后，ST2Vec学习嵌入轨迹，将轨迹映射到低维空间，该过程如图1中的虚线矩形所示。这其中就涉及到时空相似性的嵌入（图1中带有红色边缘的绿色矩形），以统一的方式融合时空信息。为了实现这一点，STVec设立了时间建模（TMM）、空间建模（SMM）和时空协同注意融合（STCF）三个模块。可以看到，模块化的设计使得任何现有的空间相似度学习模块都可以取代我们的SMM。
嵌入轨迹的学习过程一直在进行，直到在嵌入向量（用浅蓝色和浅黄色立方体表示）上计算的轨迹相似度接近由等式计算的地面真实相似度（用蓝色和黄色立方体表示）。
四. 三大模块
接下来，详细阐述三大模块的内容，总览如图2所示。
图2 ST2Vec统一嵌入总览
1.时间建模（TMM）
使用序列模型如RNN或LSTM并不能处理时间的周期和非周期的时间模式。为了实现细粒度的时间表示学习，文章将时间嵌入与时间序列嵌入集成来构建TMM。此外，不同的时间点重要性不同，如高峰时间和深夜。因此，进一步引入了注意函数来增强时间不规则性的表征，以提高模型的有效性。
（1）时间嵌入：对于时间轨迹中的每个时间点t，我们学习它的时间嵌入t’。
ω和ϕ是学习参数（在cos函数中表示频率和相移），线性项表示时间的发展，用于捕获非周期模式。cos(·,·)作为一个周期激活函数，可以帮助捕获周期性行为。将时间轨迹T (t)嵌入到一个时间向量序列中，即<t1,t2,...,tm>到<t’1,t’2,...,t’m>。
（2）时间序列嵌入：在获取时间嵌入后，输入LSTM模型来模拟其时间依赖性。LSTM的循环步骤如下。
在每个步骤i中，以当前输入向量xi和前一步hi−1的状态作为输入，并输出当前步骤hi的状态向量。关于LSTM模型的细节就不过多赘述。总的来说，时间信息保存的表示是通过处理时间点并捕获时间点之间相关性的循环过程来学习的。
（3）注意力函数：使用注意力机制来捕获轨迹点之间的相关性，具体来说，就是使用一种自注意力机制来计算同一轨迹中时间点之间的注意力得分。
表示改进的状态表示，att(·,·)为注意函数。其中，
，αi、w1、W1和W2是需要学习的参数向量和矩阵。
2.空间建模（SMM）
实现面向空间相似性的表示学习，包括位置嵌入、空间序列嵌入和空间注意力三个阶段。
（1）位置嵌入：移动物体的轨迹受到道路网络拓扑结构的约束，若空间上相近的两点在路网中连接得不好，那么它们之间的距离仍然可以很大。为了捕获道路网络的拓扑或结构信息，文章首先使用Node2Vec捕获道路网络中相邻位置的并发情况，即近似其邻域顶点的空间条件概率。共享相似邻居的位置往往有相似的嵌入。然后，将嵌入的位置逐步提供给GNN，以获得局部平滑的位置嵌入。通过GCN函数最终获取空间轨迹的细粒度表示<l’1, l’2,...,l’m>。
（2）空间序列嵌入：这与时间序列嵌入过程相似，将上面获得其初始化的位置序列提供给LSTM模型来编码空间信息。使用LSTM模型最后一步的隐藏状态作为空间嵌入。
（3）空间注意力：此外，也应用了一种自我注意力机制来捕捉学习过程中不同位置的不同贡献。
3.时空协同注意融合（STCF）
已存在一种分离融合的方式，即用两个独立的LSTM模型生成轨迹的空间和时间嵌入，然后再结合生成时空轨迹嵌入。公式如下：
这种方法简单而有效，但它需要两个LSTM模型，故需要确定的参数数量增加了一倍。因此，本文提出了一种统一融合的方式。
统一融合（UF）：这个方式让时间序列嵌入和空间序列嵌入相互作用，彼此增强。具体来说，首先通过矩阵WF对时间特征和空间特征进行转换，公式如下。
这两个表示的相互作用表示如下：
其中，WQ’和WK’是与WF具有相同形状的矩阵，τ（tˆ）和τ（sˆ）是τ (t)和τ (s)的增强表示。然后，如图2所示，将得到的增强的时间和空间序列嵌入输入到相同的单一LSTM体系结构中，以实现统一的时空轨迹嵌入。这种融合方式的正式定义为：
关于训练和模型优化的内容，感兴趣的的读者可以去仔细阅读这篇文章。
五. 实验
1.实验设置
（1）数据集：采用了三个公共的真实轨迹数据集T-Drive，Rome2，Xi’an。
（2）评估指标：采用top-k相似度搜索作为验证方法，采用HR@10、HR@50和
R10@50作为评价指标（它们越接近1，模型的有效性越高）。
（3）基线：与所有现有的相似性学习方法进行了比较，包括 NEUTRAJ、Traj2SimVec、T3S和GTS。并且对基线进行扩展然后分成三类，窗口引导基线（*w）、LSTM引导的基线（*l）和TMM引导的基线（*t）。
（4）工具设备：使用Python和Pytorch。在一台拥有Intel Silver 4210R，2.40 GHz CPU，64-GB RAM和GeForce GTX-2080 Ti 11G GPU的服务器上进行。
2.模型有效性研究
文章在三个数据集上将ST2Vec与所有12种基线方法的性能进行了比较。在此只展示了T-Driver数据集。我们可以从表1观察到，TMM引导的基线明显优于窗口引导和LSTM引导的基线，这表明所提出的时间轨迹嵌入模块是有效的。并且在同一类别中，GTS和ST2Vec在所有指标上都优于其他方法，ST2Vec在所有距离度量的精度都明显优于GTS。
表1模型有效性研究
3.模型效率研究
通过离线模型训练和在线计算来研究模型效率。从图3可以看出，ST2Vec在训练和计算方面都有良好的性能。
图3模型效率研究
4.模型可伸缩性研究
从表2可以观察到，首先，运行时间随着基数的增加而增加。其次，ST2Vec提供了比其它四种基准更可观的性能。第三，ST2Vec的性能受基数增加的影响小于其它四个基线。因此，ST2Vec为基于学习的轨迹相似度计算提供了最佳的可伸缩性。
表2模型可伸缩性研究
六. 总结
这篇论文提出了一种基于表征学习的架构ST2Vec，用于道路网络中的时空相似性学习，同时实现了一系列的轨迹度量。文章使用三个真实数据集进行的大量实验证实，ST2Vec比目前最先进的方法具有更高的有效性、效率和可伸缩性。在未来，还可以将ST2Vec集成到空间数据库管理中，从而实现更多类型的轨迹分析。
|
