一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法[发明专利]

(12)发明专利申请

(10)申请公布号 CN 109409499 A(43)申请公布日 2019.03.01

(21)申请号 201811101999.3(22)申请日 2018.09.20

(71)申请人 北京航空航天大学

地址 100000 北京市海淀区学院路37号(72)发明人 王静远　吴宁　

(74)专利代理机构 北京慕达星云知识产权代理

事务所(特殊普通合伙) 11465

代理人 李冉(51)Int.Cl.

G06N 3/04(2006.01)

权利要求书4页 说明书11页 附图5页

()发明名称

一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法(57)摘要

本发明公开了一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法，具体步骤包括:S1轨迹点的离散化；S2循环神经网络与轨迹建模；S3轨迹恢复；S4利用时空注意力机制，得到基于序列到序列模型的注意力模型；S5将卡尔曼滤波和循环神经网络结合，引入卡尔曼滤波优化均方误差，协同训练卡尔曼滤波与所述注意力模型，得到最终模型。本发明提供了一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法，通过循环神经网络来建模轨迹点之间的转移规律，利用深度学习中的注意力机制来帮助进行轨迹恢复，最后引入了卡尔曼滤波来建模对象在时间和空间上的移动，从而降低了深度学习模型的不可解释性和误差，具有更强的可解释性，并且降低了轨迹恢复的误差。

CN 109409499 ACN 109409499 A

权　利　要　求　书

1/4页

1.一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法，其特征在于，具体步骤包括:S1轨迹点的离散化：将一个地理区域划分为长度是la的不相交的网格；所述网格的集合记为J，J按行存储着所有网格的中心点坐标，所述中心坐标记为网格id；

S2循环神经网络与轨迹建模：利用循环神经网络对所述离散化的轨迹点进行建模，得到不完整轨迹点序列，所述不完整轨迹点序列不包括缺失的轨迹点；

S3轨迹恢复：利用序列到序列的轨迹恢复模型将所述不完整轨迹点序列编码为上下文向量，然后解码器通过上下文向量来预测缺失的轨迹点；

S4时空注意力机制：所述序列到序列的轨迹恢复模型利用时空信息将注意力集中到所述不完整轨迹点序列上，得到基于序列到序列模型的注意力模型；

S5引入卡尔曼滤波来对注意力模型进行修正：将卡尔曼滤波和循环神经网络结合，引入卡尔曼滤波优化均方误差，协同训练卡尔曼滤波与所述注意力模型，得到最终模型。

2.根据权利要求1所述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法，其特征在于，所述S1中所述轨迹点映射到网格上，用网格id来表示轨迹点；循环神经网络的输入即为网格id，同时所述循环神经网络的输出为预测的位置所属网格id；轨迹点pi来自于一个移动的物体并以一个元组的形式被记录(x,y,s,id)；pi·x是经度，pi·y是纬度，pi·s是这个点的时间戳，pi·id是这个点所属位置的id。

3.根据权利要求1所述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法，其特征在于，所述S2中所述循环神经网络包括但不限于：长短时记忆模型和门单元模型。

4.根据权利要求1所述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法，其特征在于，在所述S3中，不完整轨迹点序列tinc作为输入，基于输入恢复出对应的完整轨迹tcom，具体的步骤如下：编码器从输入的序列中计算出一个表征s，解码器每一个时刻生成一个词，基于序列到序列的轨迹恢复模型将不完整的轨迹点序列编码为上下文向量，解码器通过上下文向量的帮助来预测缺失的点，条件概率分布为：

其中，tcom是按时间排序并保持着不变采样间隔ε而且长度为n的轨迹；

tcom＝b1→b2→...→bn；

tinc是大小为m的完整轨迹tcom的子集；tinc＝aj1→aj2→...→ajm；S31建模已知序列的编码器：所述网格id做为编码器的输入，所述输入被嵌入层转换为低维向量，送入到双向长短时记忆模型中；所述双向长短时记忆模型包括前向LSTM和后向LSTM；

前向LSTM按顺序读入输入的向量序列，从而计算出一个前向隐状态序列

后向LSTM按照相反的顺序读入输入的向量序列，并计算一个后向隐状态序列

在第jk时刻的输出为与之和，记为

S32重构缺失轨迹的解码器：当解码器生成下一个点的时，若为已知轨迹点，选择将已

2

CN 109409499 A

权　利　要　求　书

2/4页

知轨迹点拷贝作为神经网络的输出，拷贝机制形式化地写成：

假设jk≤i＜jk+1，加入了端点到预测阶段来建模局部轨迹信息，解码缺失点重写为：

隐状态hi为：hi＝LSTM(bi-1,ei,hi-1)；(4)

ei是端点向量，引入了包含有局部轨迹起点和终点的端点向量；第i时刻的端点向量被记为ei，

ge是以前向和后向作为输入来捕捉端点信息的函数；所述函数由

一个嵌入层和一个多层感知机组成；所有的嵌入层的参数均是被共享的；对于所述序列到

序列的恢复模型的训练，写成如下形式：

其中，D表示训练集。

5.根据权利要求1所述的一种基于4卡尔曼滤波修正的轨迹恢复方法，其特征在于，所述S4中，注意力机制的引入，公式(4)写为：

hj＝LSTM(bi-1,ei,hi-1,ci)    (7)；

上下文信息ci的表达式：

其中，ci由编码器i时刻输出的隐状态的加权得到；si包含编码器在i时刻的状态；每个隐状态的权重经softmax计算：

其中，uij＝vTtanh(Whhi+Wssj)    (10)；其中，v是计算内积使用的降维向量；Wh是解码器输出向量变换矩阵；Ws是编码器输出向量变换矩阵；

uik＝vTtanh(Whhi+Wssk)，k＝1，2，…，m；tanh(·)为反正切函数；由于考虑的是固定时间间隔，时间距离能够通过序列的相对位置来获得；另外，位置相近的点，相似程度越高；第i个要被预测的点和第k个输入的轨迹点d的时间距离

被定义为：

被定义为

空间距离

利用时间距离嵌入矩阵T和空间距离嵌入矩阵G将时间距离和空间距离转换成向量，分别记为

和

3

CN 109409499 A

权　利　要　求　书

3/4页

最后，时空注意力权重计算为：

其中，Wtd是时间距离向量变换矩阵；Wsd是空间距离向量变换矩阵。

6.根据权利要求1所述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法，其特征在于，所述S5引入卡尔曼滤波来对轨迹恢复模型进行修正具体步骤包括：

S51卡尔曼滤波的一般描述：卡尔曼滤波将带有噪音的测量坐标zi和对应的协方差矩阵Ri作为收入来计算后验状态估计

这里和

是被估计的i时刻的x和y方向的速度；卡尔曼滤波在i时刻的输出记为：oi＝

Hix(i,i)    (15)；其中，Hi是测量矩阵，描述后验状态和测量状态的关系，下标(i,i)代表i时刻的后验状态；卡尔曼滤波在i时刻的隐状态{x(i,i),C(i,i)}由x(i,i)和对应的协方差矩阵C(i,i)组成；

S52通过公式(3)和公式(4)计算出的softmax向量，在i时刻被估计的测量协方差被估计的位置写成如下形式：

和

其中，mi＝JTIi，

特别地，当是由拷贝机制生成的时候，将会被设置成一

个接近于0的常量矩阵；J是一个形状为n×2的矩阵，n是网格的数量；Jk是第k个网格的坐标；Ik为第i时刻神经网络计算出的softmax向量的第k维；

S53卡尔曼滤波上基于时间的反向传播，卡尔曼滤波的损失函数：

其中，oi是卡尔曼滤波在i时刻的输出，bi是i时刻实际的位置；对于t时刻的过程协方差，第t+n时刻的梯度推导为:

S最终的损失函数表达式：L＝L1+L2    (21)；其中，L1表示序列到序列的恢复模型的训练；L2表示用来优化卡尔曼滤波的均方误差。7.根据权利要求6所述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法，其特征在于，所述S51卡尔曼滤波计算后验状态估计具体步骤包括：

S511预测：预测过程利用前一时刻的后验状态估计{x(i-1,i-1),C(i-1,i-1)}来产生一个i时

4

CN 109409499 A

权　利　要　求　书

4/4页

刻的先验状态估计{x(i,i-1),C(i,i-1)}；

其中，x(i,i-1)＝Φi-1x(i-1,i-1)    (22)；C(i,i-1)＝Φi-1x(i-1,i-1)Φi-1T+Qi-1；下标(i,i-1)用来表示i时刻基于i-1时刻后验状态的先验状态；Φ是卡尔曼滤波的状态转移矩阵；

S512更新：更新过程结合先验状态估计{x(i,i-1),C(i,i-1)}和测量状态{zi,Ri}来得到后验状态估计{x(i,i),C(i,i)}；

x(i,i)＝x(i,i-1)+Ki(zi-Hix(i,i-1))    (24)；C(i,i)＝(I-KiHi)C(i,i-1)    (25)；Ri为常量矩阵；Qi是i时刻的过程协方差矩阵。

5

CN 109409499 A

说　明　书

1/11页

一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法

技术领域

[0001]本发明涉及轨迹数据挖掘领域，更具体的说是涉及一种基于深度学习和 卡尔曼滤波修正的轨迹恢复方法。

背景技术

[0002]目前的轨迹恢复问题的解决方案相比于过去的轨迹恢复方案最大的区别 就在于现有方案都是数据驱动的。通过从大量历史数据中进行挖掘，分析， 就可以非常准确地还原将轨迹从低采样率还原成高采样率。[0003]然而，现有的方案对于数据的利用还很不充分，大多数解决方案都停留 在对数据进行简单地统计，然后通过复杂的启发式搜索地方案搜索出最优的 轨迹，这些方案都不能捕捉到轨迹点之间复杂的转移规律。[0004]另一方面，随着深度学习的兴起，尽管深度学习模型可以捕捉到数据内 部复杂的规律，并且可以融合进多元的信息进行帮助，但是深度学习模型的 行为很难解释，它也不能显示建模时空信息，这也会导致其在建模轨迹的时 候出现问题。[0005]因此，如何提供一个可以捕捉到轨迹数据深层信息并且具有较好可解释 性的基于卡尔曼滤波修正的轨迹恢复方法是本领域技术人员亟待解决的问 题。发明内容

[0006]有鉴于此，本发明提供了一种基于深度学习和卡尔曼滤波修正的轨迹恢 复方法，通过循环神经网络来建模轨迹点之间的转移规律，利用深度学习中 的注意力机制来帮助进行轨迹恢复，最后引入了卡尔曼滤波来建模对象在时 间和空间上的移动，从而降低了深度学习模型的不可解释性和误差，具有更 强的可解释性，并且降低了轨迹恢复的误差。[0007]为了实现上述目的，本发明提供如下技术方案：

[0008]一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法，具体步骤包括:[0009]S1轨迹点的离散化：将一个地理区域划分为长度是la的不相交的网格； 所述网格的集合记为J，J按行存储着所有网格的中心点坐标，所述中心坐标 记为网格id；[0010]S2循环神经网络与轨迹建模：利用循环神经网络对所述离散化的轨迹点 进行建模，得到不完整轨迹点序列，所述不完整轨迹点序列不包括缺失的轨 迹点；[0011]S3轨迹恢复：利用序列到序列的轨迹恢复模型将所述不完整轨迹点序列 编码为上下文向量，然后解码器通过上下文向量来预测缺失的轨迹点；[0012]S4时空注意力机制：所述序列到序列的轨迹恢复模型利用时空信息将注 意力集中到所述不完整轨迹点序列上，不完整轨迹点序列中的点都会被用到， 但是被算法认为比较重要的点权重比较大，不重要的点权重很小。通过将模 型的注意力集中到不完整轨迹点序列中的部分关键点，可以得到基于序列到 序列模型的注意力模型；[0013]S5引入卡尔曼滤波来对注意力模型进行修正：将卡尔曼滤波和循环神经 网络结合，引入卡尔曼滤波优化均方误差，协同训练卡尔曼滤波与所述注意 力模型，得到最终模

6

CN 109409499 A

说　明　书

2/11页

型。

通过上述的技术方案，本发明的技术效果是：在轨迹恢复任务中引进注意 力机制

通过注意力机制，序列到序列模型可以学会将注意力集中到不完整轨 迹中的特定部分而不是依赖于编码器的混合输出。更进一步地，基于序列到 序列模型中初始的注意力机制，我们提出了时空注意力机制来捕获长期轨迹 中时空的变化；将卡尔曼滤波和循环神经网络结合起来更好地建模轨迹，引 入先验知识来帮助评估轨迹点的真实状态；除此之外，卡尔曼滤波简洁的形 式可以被矩阵操作实现，这使得它可以很方便地跟神经网络结合，由于卡尔 曼滤波可以被写成矩阵的形式，从而可以得到一个高效并且支持批处理的神 经网络版卡尔曼滤波。[0015]优选的，在上述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法 中，所述S1中所述轨迹点映射到网格上，用网格id来表示轨迹点；循环神经 网络的输入即为网格id，同时所述循环神经网络的输出为预测的位置所属网 格id；轨迹点pi来自于一个移动的物体并以一个元组的形式被记录(x,y,s,id)； pi·x是经度，pi·y是纬度，pi·s是这个点的时间戳，pi·id是这个点所属位置的 id。[0016]通过上述的技术方案，本发明的技术效果是：把无限空间中有限的个体映 射到有限的空间中去，以此提高算法的时空效率。[0017]优选的，在上述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法 中，所述S2中所述循环神经网络包括但不限于：长短时记忆模型和门单 元模型。[0018]通过上述的技术方案，本发明的技术效果是：上述两个模型通过门机制解 决了普通循环神经网络存在的梯度消失问题，从而可以用来建模较长的轨迹 序列同时可以捕获一个较长期的依赖关系。[0019]优选的，在上述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法 中，在所述S3中，不完整轨迹点序列tinc作为输入，基于输入恢复出对应的完 整轨迹tcom，具体的步骤如下：编码器从输入的序列中计算出一个表征s，解 码器每一个时刻生成一个词，基于序列到序列的轨迹恢复模型将不完整的轨 迹点序列编码为上下文向量，解码器通过上下文向量的帮助来预测缺失的点， 条件概率分布为：

[0014]

其中，tcom是按时间排序并保持着不变采样间隔ε而且长度为n的轨迹；[0021]tcom＝b1→b2→...→bn；

[0022]tinc是大小为m的完整轨迹tcom的子集；[0023]tinc＝aj1→aj2→...→ajm；[0024]S31建模已知序列的编码器：所述网格id做为编码器的输入，所述输入被嵌 入层转换为低维向量，送入到双向长短时记忆模型中；所述双向长短时记忆 模型包括前向LSTM和后向LSTM；

[0025]前向LSTM按顺序读入输入的向量序列，从而计算出一个前向隐状态序 列

[0020]

[0026]

后向LSTM按照相反的顺序读入输入的向量序列，并计算一个后向隐状 态序列

7

CN 109409499 A

说　明　书

3/11页

[0027][0028]

在第jk时刻的输出为与之和，记为

S32重构缺失轨迹的解码器：当解码器生成下一个点的时，若为已知轨迹点， 选择

将已知轨迹点拷贝作为神经网络的输出，拷贝机制形式化地写成：

[0029][0030]

假设jk≤i＜jk+1，加入了端点到预测阶段来建模局部轨迹信息，解码 缺失点

重写为：

[0031]

隐状态hi为：hi＝LSTM(bi-1,ei,hi-1)；   (4)[0033]ei是端点向量，引入了包含有局部轨迹起点和终点的端点向量； 第i时刻的端点向量被记为ei，

[0034][0035]

[0032]

ge是以前向和后向作为输入来捕捉端点信息的函数； 所述函

数由一个嵌入层和一个多层感知机组成；所有的嵌入层的参数均是被 共享的；对于所述序

列到序列的恢复模型的训练，写成如下形式：

[0036][0037]

其中，D表示训练集。[0038]通过上述的技术方案，本发明的技术效果是：[0039]优选的，在上述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法 中，所述S4中，注意力机制的引入，公式(4)写为：[0040]hj＝LSTM(bi-1,ei,hi-1,ci)   (7)；

[0041][0042][0043][0044][0045][0046][0047][0048]

上下文信息ci的表达式：

其中，ci由编码器i时刻输出的隐状态的加权得到；si包含编码器在i时刻 的状态；每个隐状态的权重经softmax计算：

其中，uij＝vTtanh(Whhi+Wssj)  (10)；其中，v是计算内积使用的降维向 量；

Wh是解码器输出向量变换矩阵；Ws是编码器输出向量变换矩阵；uik＝vTtanh(Whhi+Wssk)，k＝1，2，…，m；由于考虑的是固定时间间隔，时间距离能够通过序列的相对位置来获得；另外，位置相近的点，相似程度越高；第i个要被预测的点和第k个输入 的轨迹点d

被定义为：

8

的时间距离

CN 109409499 A[0049][0050][0051]

说　明　书

被定义为

4/11页

空间距离

利用时间距离嵌入矩阵T和空间距离嵌入矩阵G将时间距离和空间距离 转换成向

和

量，分别记为

[0052][0053]

最后，时空注意力权重计算为：

其中，Wtd是时间距离向量变换矩阵；Wsd是空间距离向量变换矩阵。

[00]通过上述的技术方案，本发明的技术效果是：通过向量相加的方式，融合了 时空信息，位置的表征信息，或者说是高层次的语义信息到注意力机制的权 重中，从而大大改进了原始注意力机制在轨迹恢复任务上的效果。从另一个 角度来说，注意力权重添加了时间和空间上的正则项，通过正则项的帮助， 可以减轻注意力机制导致的过拟合问题。[0055]优选的，在上述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法 中，所述S5引入卡尔曼滤波来对轨迹恢复模型进行修正具体步骤包括：[0056]S51卡尔曼滤波的一般描述：卡尔曼滤波将带有噪音的测量坐标zi和对应的协 方差矩阵Ri作为收入来计算后验状态估计

[0057]

这里和是被估计的i时刻的x和y方向的速度；卡尔曼滤波在i时刻的 输出记

为：oi＝Hix(i,i)  (15)；[0058]其中，Hi是测量矩阵，描述后验状态和测量状态的关系，下标(i,i)代表i时 刻的后验状态；卡尔曼滤波在i时刻的隐状态{x(i,i),C(i,i)}由x(i,i)和对应的协方差 矩阵C(i,i)组成；

[0059]S52通过公式(3)和公式(4)计算出的softmax向量，在i时刻被估计的测量 协方差和被估计的位置写成如下形式：

[0060][0061][0062]

其中，mi＝JTIi，

特别地，当是由拷贝机制生成的时候，将会 被设

置成一个接近于0的常量矩阵；J是一个形状为n×2的矩阵，n是网格的 数量；Jk是第k个网格的坐标；Ik为第i时刻神经网络计算出的softmax向量 的第k维；[0063]S53卡尔曼滤波上基于时间的反向传播，卡尔曼滤波的损失函数：

[00][0065][0066]

其中，oi是卡尔曼滤波在i时刻的输出，bi是i时刻实际的位置；

对于t时刻的过程协方差，第t+n时刻的梯度推导为:

9

CN 109409499 A

说　明　书

5/11页

[0067]

[0068][0069][0070][0071]

S最终的损失函数表达式：L＝L1+L2  (21)；其中，L1表示序列到序列的恢复模型的训练；L2表示用来优化卡尔曼滤 波的均方

误差。

通过上述的技术方案，本发明的技术效果是：将卡尔曼滤波和循环神经网 络结

合，引入卡尔曼滤波优化均方误差，协同训练卡尔曼滤波与所述注意力 模型，得到最终模型。

[0073]优选的，在上述的一种基于深度学习和卡尔曼滤波修正的轨迹恢复方法 中，所述S51卡尔曼滤波计算后验状态估计具体步骤包括：[0074]S511预测：预测过程利用前一时刻的后验状态估计{x(i-1,i-1),C(i-1,i-1)}来产生一个i 时刻的先验状态估计{x(i,i-1),C(i,i-1)}；[0075]其中，x(i,i-1)＝Φi-1x(i-1,i-1)  (22)；[0076]C(i,i-1)＝Φi-1x(i-1,i-1)Φi-1T+Qi-1；下标(i,i-1)用来表示i时刻基于i-1时刻后验状态的 先验状态；Φ是卡尔曼滤波的状态转移矩阵；[0077]S512更新：更新过程结合先验状态估计{x(i,i-1),C(i,i-1)}和测量状态{zi,Ri}来得到 后验状态估计{x(i,i),C(i,i)}；

[0078][0072]

x(i,i)＝x(i,i-1)+Ki(zi-Hix(i,i-1))  (24)；[0080]C(i,i)＝(I-KiHi)C(i,i-1)  (25)；[0081]Ri为常量矩阵；Qi是i时刻的过程协方差矩阵。[0082]通过上述的技术方案，本发明的技术效果是：协方差描述了对于卡尔曼 滤波内部运动模型的把握，协方差越低，预测结果就会更加偏向于卡尔曼滤 波的先验状态估计。[0083]经由上述的技术方案可知，与现有技术相比，本发明公开提供了一种基 于深度学习和卡尔曼滤波修正的轨迹恢复方法，通过循环神经网络来建模轨 迹点之间的转移规律，利用深度学习中的注意力机制来帮助进行轨迹恢复， 最后引入了卡尔曼滤波来建模对象在时间和空间上的移动，从而降低了深度 学习模型的不可解释性和误差，具有更强的可解释性，并且降低了轨迹恢复 的误差。附图说明

[0084]为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实 施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面 描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不 付出创造性劳动的前提下，还可以

10

[0079]

CN 109409499 A

说　明　书

6/11页

根据提供的附图获得其他的附图。

[0085]图1附图为本发明的整体模型的框架图；

[0086]图2附图为本发明的序列到序列模型的结构图；[0087]图3附图为本发明的注意力模型；

[0088]图4附图为本发明的卡尔曼滤波与循环神经网络结合模型；[00]图5附图为本发明的embedding向量大小的影响折线图；[0090]图6附图为本发明的网格长度的影响折线图；[0091]图7附图为本发明的轨迹恢复缩略图；[0092]图8附图为本发明的注意力权重可视化图；

[0093]图9附图为本发明的卡尔曼滤波内部状态在被划分的网格空间上的可视 化图。具体实施方式

[0094]下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行 清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而 不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做 出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0095]本发明实施例公开了一种基于深度学习和卡尔曼滤波修正的轨迹恢复方 法，通过循环神经网络来建模轨迹点之间的转移规律，利用深度学习中的注 意力机制来帮助进行轨迹恢复，最后引入了卡尔曼滤波来建模对象在时间和 空间上的移动，从而降低了深度学习模型的不可解释性和误差，具有更强的 可解释性，并且降低了轨迹恢复的误差。[0096]数据集的构建：

[0097]为了衡量我们模型的轨迹恢复性能，使用了三个真实的轨迹数据集来进 行评价，分别来自北京，深圳和波尔图(西班牙第二大城市)。来自北京的出租 车数据集是每分钟采样一次，但是深圳的数据集采样频率并不均匀。由于深 圳数据集的采样间隔低于五分钟，将轨迹预处理成了五分钟的时间间隔。来 自波尔图的公开轨迹数据集是由kaggle(知名数据挖掘竞赛平台)上一个轨迹 预测比赛提供。原始数据的采样间隔是15秒，我们将其预处理成了一分钟的 间隔。这三个城市有着完全不一样的路网结构以及交通状况，表1中详细总 结了数据集的详细统计特征。[0098]在预处理过程中，首先我们需要将目标区域划分成不相交的网格，把坐 标映射到网格编号。除此之外，需要确保一个数据集中的时间间隔是一致的。 对于不同的数据集，选择不同的网格长度。北京和波尔图数据集的格子长度 都是100m，而深圳数据集的格子长度为200m；首先是网格的划分，然后是 轨迹的离散化，接下来是不动点的去除，超长轨迹的裁剪，最后是训练数据， 验证数据以及测试数据的划分。[0099]为了完成好这些步骤，大量的数据可视化机制需要被使用进来，使用 leaflet来进行地图的构建，并使用在线的地图api接入地图数据，然后对部分 轨迹数据进行可视化。同时，对于数据集所对应的区域进行选择，一些区域 轨迹点非常稀疏的区域被我们删去了，这样减少神经网络的计算量；探究网 格长度对模型效果的影响，最后为每一个数据集都选择了一个合适的网格长 度。网格长度过小，会导致神经网络需要处理的词表过大，过大的词表会导 致神经网络的运行速度减慢，占用显存大大提高并且非常难以在一个合适

11

CN 109409499 A

说　明　书

7/11页

的 时间内收敛。而网格长度过大，就会导致模型的预测不够精确，过大的网格 会先天带来一个很高的误差，尽管卡尔曼滤波可以做出修正。[0100]表1

[0101]

数据集 北京 深圳 波尔图数据覆盖时长 一个月 两周 一年 出租车数量 18298 17998 442 轨迹数量 313560 149230 284100 轨迹点数量 31356000 1492300 8523000 位置数量 15870 19306 6351 采样间隔 一分钟 五分钟 一分钟 [0102]任务设定：对于每一个数据集，划分为三部分，训练集，验证集，测试 集。训练集用来训练模型，而超参数比如说embedding的大小，或者格子长 度是由验证集合来选择。最终的结果在测试集上进行评估。在我们的所有实 验中，百分之七十的轨迹用作训练集，百分之十的轨迹用作验证集，而剩下 百分之二十的轨迹用作测试集。对于每一个不完整的轨迹，它是由对应的完 整轨迹进行随机采样生成。采样率被定义为不完整轨迹和完整轨迹长度之比。 为了研究DRKF模型在不同环境下的比变化，测试了DRKF在采样率为百分 之三十，百分之五十和百分之七十的时候模型效果的变化。不变的采样策略 会导致结果的偏差，因此我们在训练，验证，测试的过程中每一个批次都会 重新进行一次采样。所有在测试集合上做的评价都被重复了三次。

[0103]需要比较的方法:在三个数据集上比较我们的模型和两个传统的模型以 及两个深度学习模型。这些方法都将会以四个评价指标被评估。普通的序列 到序列模型和基于序列到序列模型的注意力模型被选作基线模型。基线模型 对于相关模型有着一个很好的覆盖。

[0104]RICK:为不确定轨迹构建了一个路由表，用来通过搜索图上的top-k轨迹 来回应用户的在线查询。[0105]MPR：可以从一个转移网络中基于宽度优先搜索发现最流行的轨迹。[0106]Seq2seq:它利用编码器来将不完整轨迹压缩成一个向量，它的解码器通过 这个向量恢复一条完整的轨迹。

[0107]BahdanauAttention:在序列到序列模型的基础上，它会将注意力集中到不 完整轨迹中重要的点上。

[0108]参数设定:所有的模型都有一些参数要调，根据已被报告过的最优参数或 者通过验证集来分别优化每一个模型。本发明使用一个两层的LSTM， embedding大小为512维。[0109]结果和分析：

[0110]所有方法的性能都已经在表2中被写出了，可以观察到如下现象:[0111](1)首先，我们提出的DRKF模型在三个数据集和四个评价指标上都强于 其它模型。本发明的神经网络结构由序列到序列模型和注意力机制演变而来。 实验结果显示了传统的序列到序列模型和注意力机制在轨迹恢复任务上并不 是这么有效，而我们的DRKF非常适合这个任务。

12

CN 109409499 A[0112]

说　明　书

8/11页

(2)第二，RICK,一个传统的基于A*算法的模型在实验中表现的结果很不 错，然而

A*算法需要很长的时间来搜索一个最优的轨迹，并且它要被并行化 是非常困难的。而且，MPR对于任何情况的效果都不好，因为它对于有上千 个位置的情况很难适应。过高的计算量会导致MPR在适当的时间内无法给出 合适的结果。数据集包括了上百平方公里的区域，包含上万个位置。MPR的 时间复杂度实在是太高了，以至于它必须减少格子的数量，增大格子的面积 才能在一个可能容忍的时间内获得结果，导致性能下降得非常快。[0113](3)最后，当数据集和采样率一样的时候，欧几里得距离总是会大于NDTW 距离，因为在被预测的轨迹和实际的轨迹之间，时间偏移的现象是非常常见 的。欧几里距离与NDTW距离的比值应证了在这两个深度学习模型中，时间 偏移的现象很明显。当采样率是百分之七十的时候，DRKF的欧式距离与 NDTW距离之比要小于序列到序列模型以及bahdanau注意力机制，这个意味 着DRKF可以在卡尔曼滤波的帮助下部分地减轻这一现象。除此之外，当采 样率上升的时候，DRKF错误率下降得要比MPR和RICK快，这说明了DRKF 可以更好地利用不完整轨迹中提供的信息。[0114]表2

[0115]

[0116]

深度轨迹恢复模型的分析：

13

CN 109409499 A[0117]

说　明　书

9/11页

时空信息在轨迹恢复任务中是非常重要的上下文信息，这里比较了时空 注意力

机制，Bahdanau注意力机制，没有注意力机制的区别；也比较了双向 循环神经网络以及单向循环神经网络作为编码器的性能差别。考虑不同的采 样率下的情况，30％,40％,50％,60％,70％五种采样率下各种模型效果的变化。 正如表3所示，Bahdanau注意力机制可以对子序列到序列模型有一定的帮助， 但是这个帮助其实非常有限，并且发现时间信息和空间信息都可以改善性能。 本申请提出的时空注意力机制取得了最好的表现，意味着本发明确实找到了 一个有效的方法来将时空信息引入到注意力机制中。使用双向LSTM确实可 以提高性能；除此之外，观察到随着采样率的上升，模型的效果也产生了大 大提高，而同时考虑了时空信息以及双向LSTM的模型在采样率上升的时候 误差下降最快，因此可以更为有效地从输入序列中提取特征，完成轨迹恢复 任务，最终模型的深度学习部分采用STA+BiLSTM项。

[0118]表3

[0119]

卡尔曼滤波的分析:

[0121]将误差减少地百分比作为衡量指标。在表4中，比较静态方法和动态方 法性能地差别，动态协方差的效果更好，因为可以通过改变协方差大小的方 法来评估每一个预测位置的置信度。如果被估计的协方差非常大的话，那么 神经网络预测的可信度就并不高了，因此，一些被预测的低置信度的点会被 卡尔曼滤波修正。明显地，当采样率上升，卡尔曼滤波也会变得更加有效， 因为更多地采样点可以帮助卡尔曼滤波给出一个更加精确的先验状态估计， 从而有效地减小来自神经网络的噪音。。[0122]表4:不同协方差评估方法的影响

[0123]

[0120]

[0124]

[0125]

参数调优:

14

CN 109409499 A[0126]

说　明　书

10/11页

在北京的数据集上研究了超参数对性能的影响。在所有的基线模型中， Bahdanau

注意力机制表现得非常好并且和DRKF有着相似的超参数。因此， 将Bahdanau注意力机制作为唯一的参考基线模型。Embedding维度是循环神 经网络一个非常重要的超参数，直接地影响了模型地容量。在图5中，隐状 态大小被设置为128，256，384，512，0。通过验证集上的实验，发现512 的Embedding维度可以给两个模型提供最好的性能。在调优了Embedding维 度之后，将Embedding维度固定为512，然后比较不同网格长度的影响。在图 6中，网格长度被设为80m，100m，120m，140m，160m。其中100m长度的 网格给出了最好的效果。而当网格长度下降到80m的时候，位置的数量实在 是太多了，模型的训练比较困难，所以预测的误差会开始上升。

[0127]如图1所示，从左到右依次是时空信息的抽取，双向LSTM组成的编码器， 时空注意力机制的计算，子序列到序列模型的解码器。右上的图例指明了几 种神经网络单元的名称，包括双向LSTM，卡尔曼滤波以及单向LSTM。如图2所示，序列到序列模型的结构图，它展示了如何通过端点以及拷贝机 制进行的序列恢复。如图3所示，通过注意力机制利用时间和空间信息进行 轨迹恢复。如图4所示，使用神经网络的输出替代卡尔曼滤波的输出，并提 出了协同训练算法。如图5所示，展示了一条完整的轨迹是怎样被恢复出来 的，以及注意力权重在恢复过程中的变化，图7为采用leaflet绘制的轨迹恢 复缩略图，展示了轨迹恢复的大致效果。如图8所示，采用matplotlib画图， 绘制出的注意力权重矩阵。颜色越深，就代表权重越大，也就是说输入和输 出的关系也就越大，横轴是恢复的点，竖轴是输入的点。展示了一个轨迹恢 复的实例，三十个被采样的点被用来恢复原始的一百个点。在图7中，紫色 的图标是被采样的点而红色的线是对应的被恢复的轨迹。图8展示了被恢复 点和不完整的轨迹点之间注意力权重在恢复过程中的变化。图8上部的矩阵 说明了传统的注意力机制很难评估所有被采样点的权重，图8下部的矩阵显 示了我们的时空注意力机制可以在时空信息的帮助下计算一个更为合理的注 意力权重。如图9所示，演示了卡尔曼滤波的修正过程，二维的高斯分布代 表了卡尔曼滤波的先验，后验，以及测量状态。图中紫色的点是需要被恢复 的真实点。在预测阶段，卡尔曼滤波做出了一个先验状态估计，这个估计的 结果非常接近目标位置，而神经网络的预测偏离了目标很多。然而，在更新 阶段之后，修正的结果就非常接近目标了。图中还可以看出来卡尔曼滤波基 本上是一个线性的预测，根据i-2和i-1时刻估计的内部状态，卡尔曼滤波做 出了一个线性的外推，这个预测是考虑到时间和车速的，因此是具有相当大 参考价值的，而神经网络对自身预测的不确定性最终导致了模型决定更多地 去以卡尔曼滤波内部地预测为准。从图里就能看出来，卡尔曼滤波预测的高 斯分布明显要比神经网络预测地高斯分布要亮，也说明了卡尔曼滤波的先验 状态估计更加可靠。

[0128]本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都 是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。 对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述 的比较简单，相关之处参见方法部分说明即可。

[0129]对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用 本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易 见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下， 在其它实施例中实现。因此，本

15

CN 109409499 A

说　明　书

11/11页

发明将不会被于本文所示的这些实施例， 而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。

16

CN 109409499 A

说　明　书　附　图

1/5页

图1

图2

17

CN 109409499 A

说　明　书　附　图

2/5页

图3

18

CN 109409499 A

说　明　书　附　图

3/5页

图4

图5

19

CN 109409499 A

说　明　书　附　图

4/5页

图6

图7

20

CN 109409499 A

说　明　书　附　图

5/5页

图8

图9

21