CN115206099B - 一种车辆gps轨迹的自适应路径推断方法 - Google Patents

Abstract

本发明给出了一种用于稀疏轨迹的自适应(API)路径推断方法，(1)构建路网模型，得到训练集和路段表征向量，初始化模型参数集；(2)获得候选点集合、候选路径集Γ；(3)计算轨迹点的单点特征即距离特征，连续两个轨迹点间的前后特征，即空间特征，时间特征，角度特征、交通相关性特征；并计算路径特征矩阵。(4)对候选轨迹的特征进行编码；(5)将隐藏层特征输入注意力层，经过全连接层得到各特征的权重；(6)用单点特征、前后特征及其相应的特征权重构建自适应权重的条件随机场模型，使用动态规划算法求解出一条最优推断路径。(7)后向传播算法更新模型参数参数集。(8)训练致模型收敛，并预测路径。本发明引入注意力机制对轨迹点的几个特征在不同复杂度的路网环境下对特征的权重进行自适应调节，从而达到在复杂路网环境下更优的匹配效果。

Description

一种车辆GPS轨迹的自适应路径推断方法

技术领域

本发明属于导航和智能交通领域，具体涉及一种用于GPS轨迹自适应路径推断的方法。

背景技术

随着卫星导航定位技术的发展以及人类出行活动对导航技术的愈发依赖，各种人类活动的轨迹数据愈发重要。在各种导航定位设备逐渐普及的背景下，无时无刻都在源源不断的产生大量GPS轨迹数据。但是，由于GPS定位本身的局限性和部分场景下GPS信号传播受到干扰的情况下的定位结果会存在较大误差。若使用未经后处理的GPS轨迹数据会造成较大误差。因此，在处理这些数据前往往会将其于高精密城市路网进行匹配，所以如何高效准确地匹配这些数据也成为了数据处理过程中重要的一环。

从轨迹数据匹配的过程上看，将GPS轨迹点匹配到路网上最简单的方法就是将轨迹点匹配到距离轨迹点最近的路段上。但在实际匹配过程中会出现诸多因素影响到匹配结果的准确率。例如，较长时间的GPS信号采样率对匹配的影响很大，采样时间间隔越长，匹配难度越大，其次道路的复杂程度也会增加匹配难度。

在轨迹匹配到路网的过程中，我们往往需要权衡轨迹点的前后走向以及单点到路网的距离等特征在不同的路网环境下的占比，在将轨迹匹配到路网时，输入到条件随机场模型的权重参数应根据路网的复杂程度自适应各个特征的权重将很大程度上能减少路网复杂区域的错误匹配，本发明引入注意力机制对轨迹点的几个特征在不同复杂度的路网环境下对特征的权重进行自适应调节，从而达到在复杂路网环境下更优的匹配效果。

发明内容

(一)要解决的技术问题

为解决现有轨迹匹配方法中在复杂路网下存在的问题，本发明给出了一种车辆GPS轨迹的自适应路径推断方法。

(二)技术方案

本发明包含以下步骤：

一种车辆GPS轨迹的自适应路径推断方法，其特征在于，包括以下步骤：

(1)构建路网模型，使用Skip-Gram图嵌入方法从历史轨迹获得路段之间依赖关系和每个路段的表征向量；标定轨迹点对应匹配路段和匹配点数据，得到训练集T_trn，初始化模型参数集{θ}，其中包括全连接层参数和注意力模型参数。

(2)以每个轨迹点p_t(x_t,y_t)为中心做边长为D_c的正方形，按距离大小选取距离最小的q条路段作为候选路段，轨迹点在每条候选路段的最小垂距所对应垂足作为候选点

轨迹点p_t所有候选点组成候选点集/>

对于任意一条轨迹τ，从路网中先找到所有轨迹点对应候选点集C_t组成的候选路径集Γ。

(3)计算轨迹点与候选路径的特征；对于任意一条轨迹τ，包含M个轨迹点，将其分为u条长为m的局域轨迹，且相邻轨迹设置重叠度Ov_i,i+1，计算轨迹点p_t及其候选点的单点特征

即距离特征/>

连续两个轨迹点p_t和p_t-1之间前后特征/>

即空间特征/>

时间特征/>

角度特征/>

以及两轨迹点对应匹配路段的交通相关性特征/>

对所有轨迹点求完特征后将所有特征连接起来形成一个路径特征矩阵LF＝[EF,PF]＝[DF,SF,TF,AF,CF]。

(4)对候选轨迹特征进行编码；计算候选路径集Γ中每一条候选路径的势函数

即候选路径中所有候选点特征的加权和；选取/>

最大的前q′条候选路径，其中第α条路径γ^α的特征矩阵/>

用全连接层进行编码得到该路径的隐藏层特征

其中FC为全连接层；将选取的q′条候选路径特征矩阵经过全连接编码后得到每条候选路径对应的隐藏层特征/>

其中h＝[h_DF,h_SF,h_TF,h_AF,h_CF]；全连接层对所有候选点的单点特征和前后特征进行编码，得到隐藏层特征；

(5)将隐藏层特征输入注意力层得到各个特征权重；将处理后的隐藏层特征分别作为注意力模型的查询项Q、键项K、值项V，由Att(Q,K)＝softmax(QK^T)计算拉伸点积，并作为各隐藏层特征之间关系强弱的关系矩阵，最后再经过全连接层W_a＝FC(Att(Q,K))，其中W_a＝[W_DF,W_SF,W_TF,W_AF,W_CF]，即各特征权重的大小；

(6)构建自适应权重的条件随机场模型API-CRF；将距离特征DF作为发射概率，PF＝[SF,TF,AF,CF]作为转移概率，将各个特征的权重W_a作为各个概率的权重构建条件随机场CRF，对于两条局部轨迹重叠部分的权重取这两个局域轨迹的权重的平均值；最后根据轨迹点与候选点之间的特征及其权重，使用动态规划算法求解最优推断路径，即基于一条轨迹的轨迹点与其候选点的特征的加权累加作为非归一化概率，找到最大的非归一化概率并回溯找到对应的候选轨迹作为最优推断路径。

(7)根据步骤(1)中训练集T_trn中匹配点所构成的路径与步骤(6)得到的最优推断路径y求取误差值，通过后向传播算法更新模型参数参数集。

(8)重复步骤(2)到步骤(7)直到模型收敛，输入需要预测的轨迹点到模型进行预测，得到预测路径。

(三)有益效果

本发明的优点体现在：

提出了一种自适应路径推断模型，针对GPS轨迹点在不同复杂程度路网下的匹配逻辑，设计了自适应调整权重的条件随机场模型，以推断出GPS轨迹点的真实行驶路径。它使用图嵌入方法提取路段之间的交通相关性，并使用注意力模型捕捉轨迹与周围路段之间的关系，从而在推断最优行驶路径的过程中，自适应地为不同复杂程度下的不同匹配特征加权。本发明选择了具有不同复杂程度路网的真实匹配数据集，用于在不同的道路环境下测试所提出的方法，并根据周围道路信息自适应地调整特征权重，能够较为准确地推断GPS轨迹对应的行驶路径。

附图说明

图1为本发明实施的步骤流程图。

图2为Skip-Gram图嵌入层网络结构图。

图3为本发明提出的自适应权重条件随机场网络模型图。

图4为本发明API-CRF与基于固定权重C-CRF模型、基于STD的匹配方法和基于HMM的匹配方法在同一测试样本上的匹配结果对比图。

具体实施方式

为使本发明的目的、内容、和优点更加清楚，下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述：

参照图1，本发明的具体实施步骤为：

1.初始化模型参数集{θ}，数据预处理

1.1初始化模型参数集{θ}

{θ}表示训练参数，其中包括全连接层参数

和注意力模型参数(W_K,W_Q,W_V)；模型参数集{θ}中所有参数赋随机初始值。

1.2建立路网模型

路网定义为一个有向图R(N,E)，其中N是路网的连接节点，E为节点间的路段。每一路段包括道路的起始节点和终止节点id、路网中各点的经纬度坐标、道路的长度以及道路的通行时间，中间的节点包含节点的经纬度以及id信息，使用Skip-Gram图嵌入方法从历史轨迹获得路段之间依赖关系和每个路段的表征向量，图2为使用Skip-Gram求取路段表征向量的示意图。

1.3车辆轨迹序列划分：对于一条有M个轨迹点的轨迹τ，可以将其分为u条具有m个轨迹点的局域轨迹，其中相邻轨迹设置一定的重叠度，第i和i+1条局域轨迹的重叠度Ov_i,i+1计算公式为：

以m个轨迹点组成的局域轨迹作为一个批次。每个训练批次中的轨迹点的信息要包括id、经度、纬度、匹配路网id、车辆速度、轨迹点记录时间。各训练批次组合形成训练数据集T_trn。然后将整个训练数据分成多个批次，并且每次只处理一个批次，每批次包括一个轨迹点列表，其大小由批次大小这个参数所确定。

1.4选定候选路段与候选点

以每个轨迹点p_t(x_t,y_t)为中心做边长为D_c的正方形，将落在正方形内的路段按距离大小选取距离最小的q条路段作为候选路段并组成候选路段集Γ；轨迹点在每条候选路段的最小垂距所对应垂足作为候选点

其中q值最小等于轨迹点对应的候选点个数中的最小值，最大等于轨迹点对应的候选点个数中的最大值。

2获得轨迹匹配特征矩阵LF

2.1计算距离特征DF，即单点特征

对于每个轨迹点p_t,都有候选点

与之对应，而后通过两点间距离公式便可求得距离/>

通过距离求得距离特征

2.2计算空间特征SF

采用迪杰斯特拉算法计算相邻两个轨迹点得候选点

的最短路径长度

两个相邻的轨迹点p_t-1和p_t，其空间特征(转移特征)/>

可以表示为：

其中dis(p_t-1,p_t)为两个轨迹点在投影坐标系中的直线距离。

2.3计算时间特征TF

对于轨迹点p_t-1和p_t，可以近似地将它们的瞬时速度平均值视为两轨迹点的行驶平均速度，其候选点对

的时间特征/>

可以近似表示为：

time_true＝t_t-t_t-1

其中t_t和t_t-1分别是p_t和p_t-1所在时刻，v_t和v_t-1分别是p_t和p_t-1的瞬时速度。

2.4计算角度特征AF

角度特征是轨迹点连线与候选点连线的夹角，其可以表示为：

2.5计算交通相关性特征CF

道路上下文特征通过历史轨迹获得路段之间的依赖关系，在传统Graphembedding模型的基础上进行改进，将道路关系模型表示为G(v,ε)，其中v←E,ε←ξ，E是路网节点N之间的路段，ξ是路段E之间的拓扑和交通相关性。求得路网中一定长度内所有路段间的最短路径集S_s，以便表达两条路段的拓扑相关性；同时训练集T_trn中将高频轨迹点匹配到路网上的车辆行驶路径集S_d中隐含着司机行车习惯和道路通行情况等特征；使用中地图匹配恢复后的路径集S_d以及最短路径集S_s来训练，并使用Skip-gram方法训练得到路网中每条路段E的表征向量emb。

对于轨迹点p_t-1和p_t，他们对应的两条候选路段

之间的交通相关性特征可以使用以下公式计算：

其中

为p_t-1点的第j个候选点所在路段，/>

为点p_t的第j'个候选点所在路段，

为/>

的表征向量，/>

为/>

的表征向量。

2.6所有特征连接起来形成路径特征矩阵LF

LF＝[EF,PF]＝[DF,SF,TF,AF,CF]

其中EF为单点特征，即距离特征DF，PF为前后特征，包括空间特征SF，时间特征TF，角度特征AF，路口上下文特征CF。

3将特征进行编码

对于轨迹τ，从路网中可以找到候选路径集对于候选路径Γ中第α条候选路径γ^α包括轨迹点p_t到候选点

之间的单点特征/>

以及候选点/>

与候选点/>

之间的前后特征/>

t＝1,2,…,M，M为轨迹τ中轨迹点个数。

首先对所有特征通过全连接层进行编码，得到隐藏层特征。

其中LF代表路径特征，FC为全连接层，M为轨迹个数，当k＝1时

代表轨迹τ中第α条候选路径中第t个轨迹点的单点特征；当k>1时，/>

代表轨迹τ中第α条候选路径中第t和t+1个轨迹点之间的前后特征。

再计算候选路径集Γ中每一条候选路径的势函数

并选取势函数最大的前q′条候选路径，选取的所有候选路径经过全连接编码后得到每条候选路径对应的隐藏层特征/>

h＝[h₁,h₂,…,h_n]，n为特征数目，h与每个轨迹点的特征相对应。

4隐藏层特征输入注意力层

将隐藏层特征h_k进行后处理后分别作为注意力模型的查询项Q、键项K、值项V，然后使用下面的公式计算拉伸点积，得到各项隐藏层特征的关系矩阵Att(Q,K)：

Q＝W_Q*h

K＝W_K*h

V＝LF

其中

经过全连接层将特征之间的关系映射强弱映射为各个特征的权重大小：

W_a＝FC(Att(Q,K))

其中W_a向量的维度为1*n，其中n为特征数目，此时W_a的含义为LF特征向量的权重大小，W_a中的值和LF一一对应，且此时W_a是一个共有参数，对于所有候选路径来说W_a都是一致的。

5自适应权重的条件随机场模型API-CRF

将距离特征DF作为发射概率，PF＝[SF,TF,AF,CF]作为转移概率，步骤4得到的权重作为各个概率的权重值，构建CRF；CRF表示给定轨迹序列τ(p₁,p₂,…,p_m)，推断出路径序列γ(y₁,y₂,…,y_m)的概率。这个概率可以表示为：

其中Z(τ)为归一化因子，其定义为：

针对上述构建CRF模型，对其中势函数

进行分解：

其中λ_k为特征权重，f_k为特征计算函数，λ_k′为单点特征的权重，μ_k″为前后特征的权重，f_k′为单点特征函数，t_k″为前后特征函数。

将单点特征的权重表示为ew_i，前后特征的权重表示为ow_i,EF_i为单点特征，PF_i-1,i为前后特征。因此势函数可以表示为：

其中

时注意力模型得到的权重值，M为轨迹点数目，n为特征数目。

按照步骤1.3对一条轨迹划分为局域轨迹，再按照步骤2计算局域轨迹的各个特征，通过步骤4得到局域轨迹的各个特征对应的权重值W_a，两条局域轨迹之间重叠部分的特征权重值取这两个局域轨迹的平均值。

6推断最优路径

最后根据轨迹点及其候选点的特征及其权重，使用维特比算法求解最优推断路径γ^*。

维特比算法是一种针对多步骤每步多选择模型的最优选择问题，它在每一步的选择都保存了前续步骤到当前步骤的最小总代价以及当前代价的情况下前续步骤的选择；基于每个候选轨迹点的特征及其权重，将非归一化概率的维特比递归定义为：

初始位置的非归一化概率

中，q表示第一个GPS点对应的候选点个数，/>

表示第i条子轨迹的路径特征对应权重，/>

表示第t个GPS点对应的第j个候选点的第k个特征。

在计算δ变量后，通过迭代计算最大非归一化概率值：

然后利用下式回溯最优路径

最终得到最优的推断路径

6后向传播{θ}并更新参数集

6.1计算损失

模型采用最大似然的方法对{θ}进行估计，训练集由输入序列τ＝{p₁,p₂,…,p_M}和标签序列γ＝{y₁,y₂,…,y_M}，似然函数为：

通过替换上述特征函数可以得到：

Z为步骤5种的归一化操作；对上式取负值即损失函数：

Loss＝-L(w)

6.2后向传播并更新{θ}

训练要求为真实标签应该对应推断路径最大的概率值，即最小化Loss，使用随机梯度下降的优化方法来求解参数，后向传播更新{θ}。

7重复步骤2到步骤6，直到损失函数达到收敛情况，则停止迭代，反之进一步更新{θ}；完成训练后将需要进行预测的轨迹点输入到模型种进行预测，得到预测路径。

上述过程在附图

实验结果：

本实施例从两个区域随机选取1804条轨迹，共766442个轨迹点，及其相应的匹配点集，其中A区，共有1042条轨迹，457895个GPS点，B区域共有726条轨迹和308547个GPS点，采样率均为3s；对每一条轨迹及其匹配点集做下采样处理，得到采样间隔为6s、12s、18s、24s、30s、36s、42s、48s、54s、60s、90s、120s的数据集，并分别从中随机抽取50％作为训练集，50％作为测试集；选取基于STD匹配方法、基于HMM的匹配方法、固定权重CRF模型C-CRF，以及自适应权重CRF模型API共四种方法进行对比实验，对测试集进行预测，以匹配正确率PCM作为评判指标，实验对比结果请见图4。

从实验结果可以看出，本发明给出的自适应路径推断方法在各个采样率下的PCM要高于C-CRF、HMM、STD方法的地图匹配结果，可以较为准确地将轨迹点匹配至路网。

如上所述，本发明的具体实现步骤使本发明更加清晰。在本发明的精神和权利要求保护范围内，对本发明做出的任何修改和改变，都落入本发明的保护范围。

Claims (2)

1.一种车辆GPS轨迹的自适应路径推断方法，其特征在于，包括以下步骤：

(1)构建路网，将路网定义为由节点N和节点之间的路段E构成的有向图R(N,E)，使用图嵌入的方法从历史轨迹获得路段之间依赖关系和每个路段的表征向量；标定轨迹点对应匹配路段和匹配点数据，得到训练集T_trn；

(2)以每个轨迹点p_t(x_t,y_t)为中心做边长为D_c的正方形，按距离大小选取距离最小的q条路段作为候选路段，轨迹点在每条候选路段的最小垂距所对应垂足作为候选点

轨迹点p_t所有候选点组成候选点集/>

进一步找到路网中所有轨迹点对应候选点集C_t组成的候选路径集Γ；

(3)计算轨迹点与候选路径的特征；对于任意一条轨迹τ，包含M个轨迹点，将其分为u条长为m的局域轨迹，且相邻轨迹设置重叠度Ov_i,i+1，对于候选路径Γ中第α条候选路径γ^α包括轨迹点p_t及其候选点

的距离特征/>

即单点特征/>

以及和连续两个轨迹点p_t-1,p_t及其候选点/>

之间的前后特征/>

即空间特征/>

时间特征/>

角度特征

根据每个路段的表征向量计算两轨迹点对应匹配路段的交通相关性特征/>

其中t＝1,2,…,M；所有特征连接后形成一个候选路径特征矩阵LF＝[EF,PF]＝[DF,SF,TF,AF,CF]；

(4)对候选轨迹特征进行编码；计算候选路径集Γ中每一条候选路径的势函数

即候选路径中所有候选点特征的加权和；选取/>

最大的前q′条候选路径，其中第α条路径γ^α的特征矩阵/>

用全连接层进行编码得到该路径的隐藏层特征/>

其中FC为全连接层；将选取的q′条候选路径特征矩阵经过全连接编码后得到每条候选路径对应的隐藏层特征/>

其中h＝[h_DF,h_SF,h_TF,h_AF,h_CF]；全连接层对所有候选点的单点特征和前后特征进行编码，得到隐藏层特征；

(5)将隐藏层特征输入注意力层得到各个特征权重；将处理后的隐藏层特征分别作为注意力模型的查询项Q、键项K、值项V，由Att(Q,K)＝softmax(QK^T)计算拉伸点积，并作为各隐藏层特征之间关系强弱的关系矩阵，最后再经过全连接层W_a＝FC(Att(Q,K))，其中W_a＝[W_DF,W_SF,W_TF,W_AF,W_CF]，即各特征权重的大小；

(6)构建自适应权重的条件随机场模型API-CRF；将距离特征DF作为发射概率，PF＝[SF,TF,AF,CF]作为转移概率，将各个特征的权重W_a作为各个概率的权重构建条件随机场CRF，对于步骤(3)中两条局部轨迹重叠部分的权重取这两个局域轨迹的权重的平均值；CRF表示为由给定轨迹序列τ(p₁,p₂,…,p_m)推断出路径序列γ(y₁,y₂,…,y_m)的概率

其中Z(τ)为归一化因子，/>

可以写为/>

其中/>

为特征权重，LF_t,k表示为第t个轨迹点的第k个特征；最后根据轨迹点与候选点之间的特征及其权重，使用动态规划算法求解最优推断路径，即基于一条轨迹的轨迹点与其候选点的特征的加权累加作为非归一化概率，找到最大的非归一化概率并回溯找到对应的候选轨迹作为最优推断路径；

(7)计算Loss函数，后向传播并更新参数集{θ}，直到Loss函数达到收敛的情况下再停止迭代，反之进一步更新{θ}；完成训练后将需要进行预测的轨迹点输入到模型种进行预测，得到预测路径。

2.根据权利要求1所述的一种车辆GPS轨迹的自适应路径推断方法，其特征在于，所述步骤(3)中计算两轨迹点对应匹配路段的交通相关性特征CF_t,t-1，具体如下所示：

(1)、将道路关系模型表示为G(v,ε)，其中v←E,ε←ξ，E是路网节点N之间的路段，ξ是路段E之间的拓扑和交通相关性；道路上下文特征可以通过历史轨迹获得路段之间的依赖，求取路网中一定长度内所有路段间的最短路径集S_s，以便表达两条路段之间的拓扑相关性；同时从训练集T_trn中截取出相同路段轨迹点匹配到路网上的结果即车辆行驶的路径集S_d，路径集S_d隐含司机的行驶习惯以及道路通行情况；S_s和S_d都可以表征路段间交通相关性的强弱，将S_s和S_d作为训练集对Skip-gram进行训练，训练好的Skip-gram模型可以用当前路段的表征向量预测前后路段的表征向量，对每一个路段使用Skip-gram方法预测得到路网中每条路段E的表征向量emb；

(2)、对于轨迹点p_t-1和p_t，他们对应的两条候选路段

之间的交通相关性特征可以使用以下公式计算：

其中

为p_t-1点的第j个候选点所在路段，/>

为点p_t的第j'个候选点所在路段，

为/>

的表征向量，/>

为/>

的表征向量。

Images