Press "Enter" to skip to content

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

 

Seq2Seq多任务学习结构

 

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

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注