KDD 2021：基于Seq2Seq多任务学习的路网轨迹恢复

Tech

随着GPS设备的普及，大量基于轨迹数据的智能应用迅速发展，例如导航系统、出行时间估计、司机驾驶行为分析等。这些应用的准确性依赖于匹配至路网上的高采样率轨迹的采集，然而由于采集设备性能的问题，现实中大量的轨迹是低采样率的且没有被很好的匹配至路网上。为了解决这一问题，一些工作首先将低采样率的轨迹恢复至高采样率，而后再将恢复好的轨迹匹配至路网上。这种两步走的做法虽然可以解决上述问题，但会带来噪声且效率低下。如何高效准确地将低采样率轨迹恢复至高采样率，且同时匹配至路网上，是一个极具有挑战的问题。

本文将介绍美国伍斯特理工学院及京东智能城市联合发表在KDD 2021 上的论文《MTrajRec: Map-Constrained Trajectory Recovery via Seq2Seq Multi-task Learning》。该论文作者提出了一种Seq2Seq多任务学习的神经网络框架，将低采样率轨迹恢复至高采样率的同时，也将高采样率轨迹匹配至路网上，进而更好地为上层应用提供支持和帮助。

关于KDD会议

ACM SIGKDD（国际数据挖掘与知识发现大会，简称 KDD）是世界数据挖掘领域的最高级别的学术会议，由 ACM 的数据挖掘及知识发现专委会（SIGKDD）主办，是CCF A类会议。

01问题背景

图1 轨迹恢复的方法及应用场景

在大数据时代下，导航系统、出行时间估计等应用服务为人们的生活带来诸多便捷。这些应用依赖于高质量的轨迹数据，若轨迹数据采样频率过低，两个轨迹点之间的距离较远，会损失很多信息，并且带来不确定性。而现实中低采样率的轨迹十分常见，以出租车为例，为了节约设备的通信成本，通常每2-6分钟才会上报一个位置信息，这导致收集到的轨迹数据十分稀疏[1]。为了更好地挖掘低采样率的轨迹，一个直接的方式是先将低采样率轨迹在自由空间上恢复至高采样率，而后再将恢复的轨迹匹配至路网上，以支持后续的应用服务。然而两步走的做法很可能会导致误差，如图1所示，由于低采样率轨迹中两点距离较远，路径选择较多，自由空间上的轨迹恢复可能会导致后续地图匹配选错路径。此外，传统的地图匹配是一种非常耗时的算法[2]，对于线上及时性的支持也略有不足。因此，作者提出了以下的研究问题：是否可同时实现轨迹恢复及地图匹配两个任务，使得轨迹恢复更加准确和高效？然而端对端的解决思路仍面临许多挑战：

为解决挑战1），将生成的轨迹限制在路网上，MTrajRec利用多任务学习，同时预测路段ID以及在该路段上移动的比例；为解决挑战2）和3），提升模型的准确率，作者提出了约束掩码、注意力机制以及特征模块三个部分的改进。

1） 路网限制：之前的轨迹恢复工作多在自由空间中研究，忽略了路网的限制，如何将生成的轨迹点直接匹配在路网上是困难的。

2）粗糙格子表达：之前利用深度学习处理轨迹的工作，为简化计算大多将轨迹点转为格子，与此同时也丢失了很多信息，如何平衡计算复杂度与信息的丢失是一个难点。

3）消息传递：复杂的外部因素影响：车辆的行进受外界因素的影响，速度并不是均匀的，如何将外部因素与模型融合是一个挑战。为此，作者提出一个基于Seq2Seq多任务学习的模型MTrajRec。

02问题定义

首先作者定义了两种轨迹形式。1）自由空间上的轨迹，其中每一个采样点由经度、纬度以及时间戳表示，即。2）采样率为的地图匹配轨迹，其中每一个采样点由路段ID，在该路段上移动比例以及时间戳表示，即，通过公式（1）可将路段ID及行进比例转换为经纬度：

此外，采样率表示为每隔一定时间生成一个采样点，即。为更好的模拟现实，地图匹配轨迹为均匀采样轨迹，自由空间轨迹可为均匀或不均匀采样。作者将问题定义为，给定一个低采样率的自由空间上的轨迹以及目标的采样率，将其恢复至采样率为的地图匹配轨迹。

03模型结构

图2 模型示意图

为解决上述问题，作者提出了MTrajRec，图2展示其基本模型结构。它包含（1）基础的Seq2Seq多任务模型（黄色、绿色及橙色部分）（2）模型表现提高部分即约束掩码（橘色Mask）、注意力机制（深绿色Attention）和特征模块（蓝色部分）。其中Seq2Seq多任务学习结构可解决挑战1）路网限制问题；约束掩码解决了挑战2）粗糙格子表达问题；注意力机制及特征模块用以解决挑战3）复杂的外部因素影响问题。下文将逐一展开介绍。

3.1Seq2Seq多任务学习结构

Seq2Seq多任务学习结构由一个Encoder和一个改进的Decoder组成，输入一个低采样率自由空间上的轨迹，输出一个高采样率的地图匹配轨迹。同前人工作类似，为简化计算，作者将原始的低采样率轨迹转换成格子序列，在Encoder中，通过GRU模型，学习整条轨迹的特征。为保证生成的轨迹在路网上，在Decoder中，作业并没有直接预测轨迹点的位置，而是引入多任务学习的概念，同时预测下一个点的路段ID以及在该路段上行进的比例。需要说明的是，在路段上的行进比例与路段ID有很大关系，因此，作者在多任务学习模块中设计了一个“串联”模式，即先预测路段ID，再将路段ID作为输入之一预测行进比例，如图2中橙色模块所示。

3.2约束掩码

在上文的Encoder中，作者同前人一样，将原始GPS序列转为格子序列作为输入，这种处理数据的方法虽然可以减少模型计算的复杂度，但却丢失了精度，为此作者设计了一个约束掩码用以补充缺失的信息。首先，作者定义了一个距离权重函数，用以表达在自由空间上的点，到路网上各个路段距离的权重（即被匹配到各个路段的可能性）。约束掩码设计的目的是为了补充低采样率轨迹点的信息，因此对于目标高采样率轨迹中未知的点不做计算。现实中，自由空间上的点会被匹配至附近的路段，因此为了节约计算空间，作者将超过50米的路段权重设为0，在50米以内的路段权重根据公式计算求得。作者将约束掩码与softmax函数融合，用以预测当前轨迹点可能被匹配到的路段，公式如下：

3.3注意力机制及特征模块

为了解决挑战3）复杂的外部因素影响问题，作者在Seq2Seq模型中加入了注意力机制。此外，将外部信息，例如天气、节假日、时间、POI、路网信息作为额外的输入，通过特征模块学习外部信息的特征，而后与Encoder的结果融合，一起输入至Decoder中预测生成的高采样率轨迹点。

综上，作者以Seq2Seq多任务模型为基础框架，结合约束掩码、注意力机制和特征模块三个部分，解决问题挑战，优化模型表现。在模型的训练中， 将低采样率轨迹及高采样率轨迹作为输入和ground-truth，预测路段ID及行进比例，伪代码如下：

04实验结果

表1 实验结果

作者利用济南市出租车的数据对模型的表现进行了评估，并选取了3种baseline方法作为比较。论文中使用了Precision, Recall, MAE 和 RMSE四种指标来评价模型的表现，除此之外，作者还进行了消融实验，验证每个模块的重要性，结果如表1所示。

图3 各模型可视化结果对比

作者还给出了各种模型在轨迹恢复中的表现，其中黑色点表示原始输入点，红色点表示ground truth，蓝色点表示模型预测值。可以明显地看到MTrajRec在轨迹恢复的表现中优于其他两种baseline结果。由于原始轨迹过于稀疏，DHTR+HMM方法在后期无法很好的预测轨迹值。DeepMove+HMM的方法虽然在各路段均有预测值，但很多点重叠于一个点，对于轨迹的移动没有很好的捕捉。

05小结

作者提出了一种轨迹恢复模型，创新点在于通过利用Seq2Seq多任务学习的框架，将生成的轨迹限制在路网上，端对端地实现了轨迹恢复与地图匹配任务。此外，作者还设计了约束掩码结构，利用先验知识，为地图匹配任务提供更多的信息，以解决格子化带来的信息缺失问题。约束掩码、注意力机制以及特征模块三个部分对模型表现的提高均有帮助，在真实数据集上得到了很好的验证。

推荐阅读

九数商业分析平台探索与创新实践