现有的轨迹恢复工作大都遵循序列到序列的图，用编码器对轨迹进行编码，并用解码器恢复轨迹中的实际GPS点。然而，这些工作忽略了路网的拓扑结构，只使用网格信息或原始GPS点作为输入。因此，编码器模型无法捕获轨迹沿线GPS点丰富的空间信息，导致预测精度、空间一致性降低。本次为大家带来的数据库领域顶级会议ICDE 2023收录的文章《RNTrajRec: Road Network Enhanced Trajectory Recovery with Spatial-Temporal Transformer》，针对以上问题提出了RNTrajRec框架。
GPS轨迹是许多应用的重要基础，如旅行时间估计，交通预测，轨迹相似性测量等。为了取得良好的性能，这些应用大多需要大量的高采样率轨迹，因为低采样率的轨迹会丢失详细的驾驶信息，增加不确定性。然而，正如之前的研究所指出的，在现实生活中生成的大量轨迹具有较低的采样率，例如，出租车通常每2 ~ 6分钟报告一次GPS位置，以减少能耗。因此，对于大多数为上述应用开发的现有模型来说，很难有效地利用这些轨迹。此外，GPS轨迹必须首先通过地图匹配映射到道路网络，然后才能被许多应用程序使用。大多数现有的地图匹配算法都是基于Hidden Markov Model (HMM)及其变体，并且它们只有在轨迹以相对较高的速率进行采样时才能达到较高的精度。所以目前为止还没有找到一个很好的解决方案来解决低样本轨迹带来的问题。 轨迹恢复旨在通过恢复给定轨迹的缺失点来提高采样率，由于传统方法存在精度差的问题。有两种基于学习的轨迹恢复方法被开发出来，包括DHTR和MTrajRec。然而，所有现有的工作仍然受到两个主要限制：（1）这些现有的工作大多忽略了路网结构，使得预测在一定程度上缺乏空间一致性；（2）这些现有的工作大多使用简单的编码器模型来表示轨迹，因此无法充分利用GPS轨迹的丰富上下文信息。例如，MTrajRec仅使用简单的门控循环单元(GRU) 进行轨迹表示。为了解决现有轨迹恢复方法的局限性，同时利用端到端框架的优势，本文提出了一种基于Transformer的新型模型——RNTrajRec，即具有时空Transformer的路网增强轨迹恢复框架。为了捕获路网结构，RNTrajRec首先开发了网格划分的路网表示模块GridGNN，以学习每个路段的隐藏状态嵌入。为了捕捉轨迹的时空特征和上下文信息，RNTrajRec开发了一种新的基于Transformer的模型GPSFormer，该模型首先将轨迹中的每个GPS点表示为通过子图形生成模块生成的围绕GPS点的子图形道路网络，然后引入一种新的时空Transformer模型来学习GPS轨迹的丰富时空模式。最后在编码器模型的基础上采用MTrajRec中提出的精心设计的解码器来恢复轨迹中缺失的GPS点。•GridGNN：一个网格划分的道路网络表示模块，用于学习每个道路段的空间特征，如图1(a)所示。给定一个道路网络 G = (V, E)，GridGNN学习丰富的道路网络特征 Σroad∈R|V |×d，其中 d是模型的隐藏层大小。 
图1 RNTarjRec的框架结构• GPSFormer：一个基于时空Transformer的GPS轨迹编码器，它将轨迹τ中的原始GPS点序列<p1,p2, ..., plτ>编码为隐藏向量，如图1(b)所示。为了获得GPSFormer的输入，首先通过子图生成模块提取每个GPS点pi周围的道路网络特征。生成过程结束后，轨迹τ中的每个GPS点pi都被表示成一个加权有向子图
，其中Vτ,i捕获了模块选择的围绕GPS点pi的道路段，Eτ,i是所选子图中道路网路的边集，Wτ, i是pi与子图中每个选定道路段之间的权重集。每个生成的子图从Xroad中收集道路网络特征以形成其初始表示，即
。随后进一步在图上执行加权均值池化以获得轨迹τ的输入表示，即
。然后将b条轨迹特征的小批量连同子图结构一起输入到N个堆叠的GPSFormerBlock中，这是由Transformer编码器层用于时间建模和图细化层用于空间建模的组合。• 解码器模型：专门设计用于轨迹恢复任务，如图1(c)所示。给定来自编码器模型的b条轨迹的输出，即
，解码器模型首先用一个注意力模块来计算门控循环单元（GRU）的隐藏状态向量（即查询向量）与编码器模型的输出（即键向量）之间的相似性，以获得第j个时间戳的输入隐藏向量 a(j)。此外，还提出了一个多任务学习模块，专门用于轨迹恢复任务，该模块首先预测目标道路段 ej，然后通过一个回归任务预测相应的移动比例 rj。 给定一小批量的b条轨迹，首先使用GPSFormer获得每个样本的轨迹表示，即
，然后将隐藏状态向量转发给解码器模型以获得GRU单元的隐藏状态向量，即
。约束掩码层：目标是加速解码器模型的收敛，并解决细粒度轨迹恢复的挑战。给定原始GPS轨τ =〈(p1, t1), (p2, t2), …, (plτ, tlτ)〉和目标地图匹配的 ϵρ-采样间隔轨迹
,为目标轨迹中的每个时间戳
计算约束掩码cj∈ Rlρ×|V|。对于
，输入轨迹中的GPS点在时间戳给出，即且pk = qj。因此，队医每个距离pk内的GPS设备最大误差范围内（如100米）的道路段ei，设置cj，i = ω(ei, pk),其他道路段设置cj, i = 0。对于没有出现在输入轨迹中的时间戳，对所有道路段ei ∈ V设置cj, i = 1。为了进一步提高RNTrajRec的准确率，提出一种带约束掩码的图分类损失。给定最后一层图细化层的输出图结构，即，计算图分类损失如下：Ltotal = Lid + λ1Lrate + λ2Lenc在配备AMD Ryzen 9 5950X 16核CPU和24GB NVIDIA GeForce RTX 3090 GPU的机器上进行。数据集：论文使用了三个真实轨迹数据集Shanghai-L 、Chengdu 、Porto，如表1所示。本文采用恢复的道路段精度和位置推断的距离误差来评估不同模型的性能，同时综合考量召回率、精确度和F1分数来评估，并定义了准确性来衡量预测轨迹与其真实轨迹的匹配程度，创建高架道路恢复这一任务以评估模型在高架道路和附近主干道轨迹恢复方面的准确性。结果表明：（1）线性HMM算法在所有数据集上的表现都是最差的，且随着采样间隔的增加，其性能显著下降；（2）NeuTraj和GTS这两种用于GPS轨迹学习的模型，在它们包含MTrajRec中提出的解码器模型时，其性能优于MTrajRec，证明这两个模型能够在低采样率轨迹中捕获时空信息；（3）端到端的方法比两阶段的方法表现更好。与最佳基线相比，RNTrajRec在成都数据集的F1分数和准确率平均提高了4.85%和8.48%，MAE和RMSE平均分别降低了27.42和35.91米；在上海-L数据集上，F1分数和准确率分别提高了4.94%和9.14%，MAE和RMSE分别降低了46.49和56.55米；在波尔图数据集上，最佳基线的F1分数和准确率分别提高了4.42%和8.78%，MAE和RMSE分别降低了6.75米和22.96米，证明了RN-TrajRec在轨迹恢复方面的有效性。原因分析：（1）RNTrajRec关注轨迹中每个GPS点周围的重要路网信息和路网结构；（2）本文提出了几个新颖的模块，如GridGNN和GPSFormer，使模型能够学习给定轨迹的丰富空间和时间特征。图3展示了不同模型恢复的轨迹，其中输入轨迹是一个低采样率的高架道路轨迹。在图3(a)的两个虚线矩形中采样了部分底层路网结构（例如，用红线表示的高架道路路段和用黑线表示的主要路段）。从可视化中可以观察到，高架道路附近的路网是复杂的。图中的紫色线代表真实轨迹，橙色、绿色、蓝色轨迹分别代表MTrajRec、GTS+Decoder和RNTrajRec恢复的轨迹。由图可知本文设计的模型恢复的轨迹与真实情况匹配得更好（例如，图3(d)绿色圆圈中的轨迹），说明RNTrajRec能够以更准确的方式捕获轨迹的时空模式。然后进一步在图3 (b)-(d) 中的右下角的小图中绘制了高架道路上不同模型恢复轨迹的两段快照（以标记为1和2的矩形为边界），并给出了每个路段的三个恢复点及其对应的真实值作为示例。可以看出，MTrajRec和GTS+Decoder恢复的路段都偏离了真实轨迹，而本文设计的模型恢复的路段与真实轨迹非常匹配。此外，由于两个基线模型对路网的利用不足，它们恢复的点缺乏空间一致性。例如，在图5 (b)-(c) 中标记为2的虚线矩形中的橙色/绿色星是一个位于主要道路上的点，而下一个恢复的点（即橙色/绿色圆圈）位于高架道路上。尽管在可视化图中，这两个点似乎位于同一条道路上，但实际上这两个点之间的最短路径距离大于2000米，这意味着这两个点之间的恢复路径与真实情况有很大的差异，即对于具有复杂网络拓扑结构的高架道路，本文设计的模型能够恢复出更精确的轨迹。本文提出了一个新的基于时空Transformer的框架——RNTrajRec，第一次尝试将路网表示与GPS轨迹表示结合起来进行轨迹恢复，以捕获给定低样本轨迹的丰富时空信息。为了考虑给定轨迹中每个GPS点周围的路网结构，文中提出了一种新的时空Transformer模型——GPSFormer，它由用于时间建模的Transformer编码器层和用于空间建模的图形Transformer模型(即图形细化层)组成，用于对GPS轨迹进行编码；同时开发了子图生成模块，用于捕获每个GPS点的空间特征；以及一种新的路网表示模型，即GridGNN，无缝地将网格级表示与路网表示相结合。此外，本文还提出了一种带有约束掩码的图分类损失来指导轨迹编码过程。论文将该框架在三个真实数据集上进行了大量的实验，结果验证了RNTrajRec 的有效性和高效性，表明其性能显著优于目前最先进的解决方案。
吴雨恒 重庆大学计算机科学与技术专业2023级本科生，重庆大学Start Lab团队成员。主要研究方向：时空数据可视化 | 
|
重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有3~5名研究生名额，欢迎计算机、GIS等相关专业的学生报考！
图文｜吴雨恒
校稿｜李佳俊
编辑｜朱明辉
审核｜李瑞远
审核｜杨广超
