TrajGAT：轨迹相似度计算模型

轨迹相似度衡量任务

背景&应用：

随着物联网设备和定位技术的发展，会产生许多时空相似度很高的轨迹，例如：

• 对于单个个体：其轨迹可能会被多个定位系统所采集，比如当你驾驶汽车在高速上行驶，手机或汽车的GPS、路边的监控摄像头，以及经过的收费站等都会记录你的位置信息，生成多条轨迹。

• 对于多个个体：比如你的朋友和你结伴出行，生成的两条轨迹也是相似度很高的。

本文研究的方向就是设计一种方法来度量两条轨迹之间的相似度，帮助我们发现一些相似度很高的轨迹对。这是一项很有实际意义的工作，比如在案件侦破中，警方通过相似度分析可以将犯人的车辆、手机和人像联系起来，降低破案的难度。在疫情扩散的当下，我们还可以通过分析感染者的轨迹来寻找密切接触者。

内容参考自：https://zhuanlan.zhihu.com/p/452524959

任务：
设计一种算法来衡量两条轨迹之间的相似度，并且这些轨迹数据是有定位误差和零星采样问题。

存在的挑战

• 定位误差：存在噪声
• 零星采样：同一个路径$R$对应多个轨迹$Tr$
• 采样率不同：给定轨迹和需要比较的轨迹的长度不一
  

传统方法

• DTW（动态时间规整，将轨迹长度进行缩放，再计算欧氏距离）
• LCSS（最长公共子串，将轨迹投影到网格，计算公共网格）
• EDR（最小编辑距离，与LCSS类似）
• ERP、APM（提出了一些更复杂的指标，如转移概率等）
• 

局限：

• 对采样率变化的轨迹对的处理较为粗糙；
• 依赖于轨迹对齐，时间复杂度：$\mathcal{O}(n^2{l}^2)$ ,其中$n$是样本数，$l$是轨迹长度；
• 局限于一种度量，缺乏通用性。

深度表示学习方法

t2vec

• 来自论文：Deep Representation Learning for TrajectorySimilarity Computation[ICDE2018]
• 对原始轨迹$T_b$添加噪声、下采样为轨迹$T_a$，希望轨迹$T_a$能够生成原始轨迹$T_b$；利用encoder-decoder学习轨迹的表示。
• 对空间相关性的建模，主要是在嵌入层：
  • 对于每个网格$u$，根据远近的分布采样邻近网格集合$\mathcal{C}(u)$，用word2vec的方式得到$u$的表示.
  • 在decoder的$t+1$步，对$y_t$邻近的网格进行加权.
• 实验是看增广的轨迹能否匹配原轨迹，两个表示向量的相似度计算方法文中没有介绍，应该就是点积。
• 评价：将深度学习引入轨迹相似度计算，更强调的是学习轨迹的表示，测试集上：$\mathcal{O}(l+|v|)$.

NeuTraj

• 来自论文：Computing Trajectory Similarity in Linear Time: A Generic Seed-Guided Neural Metric Learning Approach [ICDE2019]
• 引入神经度量学习的方法，使得学习到的度量$g(T_i,T_j)$逼近真实度量$f(T_i,T_j)$
• 可以拟合任意的轨迹度量，$f(\cdot ,\cdot )$可以是豪斯多夫距离、弗雷歇距离、动态时间规整等任意的轨迹相似度的度量
• 模型层面：（1）仍然是基于RNN的模型，构建相似轨迹集进行训练；（2）空间信息在门控机制上进行了记忆设计
  
• 测试集上的复杂度$\mathcal{O}(l)$，训练集复杂度是$\mathcal{O}(n^2{l}^2)$，其中$n$是训练样本数，$l$是轨迹长度
• 评价：训练集的构建为方法不再局限于对原始轨迹的增广.

Traj2SimVec

• 来自论文：Trajectory Similarity Learning with Auxiliary Supervision and Optimal Matching [IJCAI2020]
• 和NeuTraj一样，神经度量学习，使得学习到的度量$G(X,Y)$逼近真实度量$S(X,Y)$.
• 文章指出，尽管测试集上的轨迹相似度计算已经降低到线性时间，但是训练集的时间开销仍然是平方阶的，因为需要计算每个样本对之间的相似度。
• 对轨迹的处理：
  • 引入了一篇轨迹简化（Trajectory Simplication）的工作，对轨迹点的重要性进行计算，对轨迹进行了划分和再采样后，引入了KD树（用于空间划分的特殊二叉树）进行存储。
  • 建树对轨迹点进行表示，降低了计算成本：建树复杂度为$\mathcal{O}(nlogn)$，查询为$\mathcal{O}(logn)$.
  • 基于再采样后的轨迹，设计了对比子轨迹(sub-trajectory)的loss，通过局部的loss加权得到单个样本的loss.
  • 进一步考虑长短不一的轨迹的局部相似性的问题，作者还设计了一种轨迹匹配点的triplet loss，进一步拓展了轨迹相似度的定义.
• 模型层面：仍然是RNN-based model.
• 评价：更关注训练阶段的计算开销；拓展了“相似”的定义。

TrajGAT

对之前工作的总结

经典的轨迹相似度指标：计算复杂度平方阶，且局限于单一的度量

基于深度表示学习的模型：

Motivation1: 长序列的处理

(1) 均为RNN-based，难在长序列上表现衰减，难以捕获长序列依赖

存在长序列依赖问题是怎样影响轨迹的相似度计算呢？

• 论文中给出的理由是：轨迹相似度的计算基于轨迹的对齐，如下图所示。当一个长的轨迹和短的轨迹进行对齐时，无法很好地捕获长的轨迹的信息。
  

• 在训练集构建的阶段，是用的传统算法来计算的ground truth；先前工作中中涉及轨迹对齐的应该说只有计算轨迹匹配loss的模块。个人认为还是最终学出的表示不够好的原因。

• 但是事实上，根据作者的实验，在西安数据集上，确实长序列的轨迹的命中率Recall@10\Recall@50和Recall10@50要小；效果更弱一些。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZEWTSqQ4-1666143031666)(https://p6-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/9b9aece0547649e9a4fe0374b5c13792~tplv-k3u1fbpfcp-watermark.image?)]
=> 最终目的是让长的轨迹得到比较好的表示。

Motivation2: 网格化的合理性

（2）作者认为，轨迹由空间的网格序列表示，让远距离的record无法相互作用（即：同一个轨迹中，间隔远的点也是具有相似性的）

（3） 此外，作者还认为，由于轨迹在空间中是不均匀分布的，一些网格的数据多，一些网格的数据少，这种空间的异质性会导致一些网格的token在网络训练过程中没有得到足够的数据去优化，因此在长序列的轨迹中，会恶化表示的效果。

=> 希望能充分利用远距离和小样本的网格信息。

Motivation3：长序列表示的挑战

• Transformer：GPU显存占用较高
• 长序列表示模型：Bp-transformer、Informer，没有建模空间信息

=> 希望能尽可能节省训练的显存占用。

本文的方案

引入了PR-四叉树可以较好地

1. 保证各网格训练的均衡
2. 基于四叉树的构图可以提供层次信息
3. 相比于要计算每一个网格对的attention，在图上基于GAT的模型，只需要计算邻居的attention，限制了显存的占用。

问题定义

定义：

• 轨迹库$\mathcal{T}$包含$N$条轨迹；
• 我们强调轨迹都分布在区域$\mathcal{A}$上；
• 每条轨迹：$T=[X_1,...,X_t,...]\in \mathcal{T}$，其中$X_t=(lo{n}_t,la{t}_t)$是第t个到达点；
• $f(T_i,T_j)$是对于轨迹$T_i$和$T_j$相似度的一个度量，可以是DTW，Hausdorff，Frechet距离等…
• 任务是学习一个函数$g(\cdot ,\cdot )$来估计轨迹的相似度，目标是最小化$|f(T_i,T_j)-g(T_i,T_j)|$.

模型概述

• 首先是对区域$\mathcal{A}$做了一个层次划分，划分树是$\mathcal{H}$。模型对$\mathcal{H}$下的每一个层次的网格做了表示的预训练，希望能够获取不同层次的信息。
• 基于树$\mathcal{H}$，作者构造了一个图$T^g$. 用GAT获得$T^g$的表示。根据轨迹的序列信息和层次信息生成轨迹的嵌入。
• 最后，设计ranking loss去学习轨迹的相似度度量。

层次划分

Traj使用Point Region Quadtree（点-区域四叉树）来表征区域的层次划分。

• 通过对区域进行不断的划分，四叉树的分支，最终保证每个区域包含$\delta$个节点，$\delta$是一个经验性的参数。
• 忽略叶子节点，四叉树构成了对原区域$\mathcal{A}$的一个划分，记作$\mathcal{H}$。
• 随着区域$\mathcal{A}$的增加，作者试图论证：$\mathcal{H}$倾向于稳定（实验见附录A.3，但pdf中没有给出附录）。
• Traj模型基于这个划分进行设计。

网格的嵌入

• 将树$\mathcal{H}$看做一个图。
• 用Node2vec获得图中各个节点的表示。
• 最终得到的嵌入记作：${\mathbf{M}}_{\mathcal{H}}\in d_h\times N_h$，得到的各个节点的表示后续将用于计算轨迹的表示

轨迹的编码

构图

对于轨迹$T$，我们构造了一个新的图$T^g=(\mathbf{N},\mathbf{E})$

$\mathbf{N}$包括两部分：由轨迹构成的${\mathbf{N}}_r$和轨迹的层次信息构成的${\mathbf{N}}_h$

• 首先找到其包含的轨迹点（对应的网格对应的节点）的嵌入： N r = { n 1 , . . . , n L } \bold{N}_r = \{\bold{n}_1,...,\bold{n}_L\} Nr​={n1​,...,nL​}.
• 递归地查找PR-四叉树$\mathcal{H}$中叶子节点$i$的父节点，即：包含该节点的所有大小的网格，直到网格大小（即节点的层次）到设定的阈值$\eta$.
• $\eta$是一个超参数，查找出的节点集合根据层级$i$分别记作：${\mathbf{N}}_r^1,{\mathbf{N}}_r^2,...,{\mathbf{N}}_r^{\eta }$
• 所有轨迹点的上$\eta$层构成的节点的嵌入集合记作：${\mathbf{N}}_h$，即：$\bold{N}_h = {\bold{N}_h^1 ,… ,\bold{N}_h^\eta} $

$\mathbf{E}$包括两部分：（1）原有四叉树中的边；（2）对同层的非叶子节点增加的全连接边，即：每一个$N_h^i$都是全连接的完全子图。

节点的表示

新的图$T^g=(\mathbf{N},\mathbf{E})$是同质的，即：每个节点的表示方式是一致的，都包括三部分：${\mathbf{f}}_i=concat({\mathbf{f}}^l,{\mathbf{f}}^r,{\mathbf{f}}^h)\in {\mathbb{R}}^{3d_f}$

• 地点特征：${\mathbf{f}}_i^l=MLP(x_i,y_i)$，$(x_i,y_i)$是归一化后的节点坐标或区域中心坐标。
• 区域特征：${\mathbf{f}}_i^r=MLP(w_i,h_i)$，$(w_i,h_i)$是区域的长和宽
• 层次特征：${\mathbf{f}}_i^h=Embedding({\mathbf{M}}_{\mathcal{H}},{\mathbf{n}}_i)$ //查询节点i的信息

序列编码

作者通过层次遍历生成树的序列信息，形成节点的列表$L$：

对$L$进行位置编码，得到${\lambda }_i^s$：

作者希望通过计算图的Laplacian矩阵对应的低频特征向量+节点对应的特征向量，表示节点的距离信息:

最终，得到节点的表示向量${\mathbf{i}}_i$：

GAT

基于图去计算注意力，只需要利用领近节点的表示，避免了序列Transformer中计算每一组向量的注意力带来的过大开销：

经过$P$层的聚合，得到每个节点的最终表示：$[{\mathbf{h}}_1^P,...,{\mathbf{h}}_M^P]$

轨迹的最终表示：

实验

作者选取了两个数据集：Didi Xian和Porto，根据轨迹的长短， 分成了两个子数据集：Mix和Long.

• 对于长的轨迹，超过了所有的baseline；作者认为单纯对长的轨迹的处理更为困难。因此模型的设计是有作用的。

轨迹相似度的计算可以服务于聚类任务，作者使用不同的相似度方法进行聚类，并比较了四种聚类指标下的聚类指数。可以看到TrajGAT远远领先于其它的方法。

在内存占用复杂度上，TrajGAT也有一定的优越性。

作者进一步做了消融实验，证明了网格划分、GAT和轨迹表示模块的有效性。

小结

1. 作者提出的空间划分方式，将equal-size的网格转换为了层次结构，并通过同一级节点的连接，构造出了一个空间划分的图，具有一定的新意。
2. 在此基础上，作者使用的图注意力机制捕获长序依赖，在实验上取得了良好的效果。

【拓展阅读】

关于通过二叉树的方式做轨迹的划分的文章:
POI2Vec: Geographical Latent Representation for Predicting Future Visitors

考虑了轨迹的时间维度：
Towards robust trajectory similarity computation: Representation-based spatio-temporal similarity quantification