CN112101132B - 一种基于图嵌入模型和度量学习的交通状况预测方法 - Google Patents

Abstract

本发明公开了一种基于图嵌入模型和度量学习的交通状况预测方法，将道路的上下文道路，包括与当前道路在时间、空间邻近的道路以及与当前道路的城市兴趣点分布相似、通行速度高度相关的道路表示为隐空间中低维、稠密的向量。该向量表示能够保持道路之间原本的相似关系，从而能够提高交通状况预测任务的性能。在得到这种保持语义相似性的向量表示后，利用K近邻分类器对道路的交通状况进行分类，进而完成交通状况的预测任务。在K近邻分类器中，基于度量学习的方法，可以自动学习在交通状态预测任务中衡量向量之间距离的最佳度量方式，还能有效避免手动选择距离度量方式的弊端。

Description

一种基于图嵌入模型和度量学习的交通状况预测方法

技术领域

本发明属于大数据处理领域，具体涉及一种交通状况预测方法。

背景技术

通过数据驱动，实时监控城市交通状况的动态时空变化是智慧城市发展过程中十分重要的创新应用之一。目前已经有若干种基于城市道路视频监控等数据预测城市交通状况的方法。这些已有方法是通过考虑一条道路的交通状况时间演变规律(拥堵的时间段和周期性等)，或者基于关联规则挖掘算法挖掘交通拥堵关联规则、或者采用时空信息结合时间序列回归预测算法对城市交通状况进行预测。在某些方面已经取得了较为满意的准确率，但是还存在一些缺陷。譬如使用的数据有一定程度的限制，如视频监控数据存在分析困难的缺点。此外，这些方法没有充分考虑道路的时空邻近特征，无法利用道路之间的相似性预测当前道路的交通状况。配备GPS的出租车可以被看作是无处不在的传感器，而大规模的出租车轨迹数据可以很好地捕捉到城市交通的潜在动态运行规律。从大量出租车轨迹数据出发分析预测城市交通状况则可以有效避免这些问题。

图嵌入模型是一种表示学习方法，它可以把图中的每个结点的高维向量映射为低维向量空间中的向量，采用图嵌入模型可以极大提升结点分类等任务的准确性。受图嵌入模型的启发，道路状态的时间、空间等上下文特征也可以像图嵌入的上下文特征一样表示，而实际结果表明这种对城市感知数据的高效表示能使城市交通状况任务的预测性能得到较大的提升。

发明内容

为了克服现有技术的不足，本发明提供了一种基于图嵌入模型和度量学习的交通状况预测方法，将道路的上下文道路，包括与当前道路在时间、空间邻近的道路以及与当前道路的城市兴趣点分布相似、通行速度高度相关的道路表示为隐空间中低维、稠密的向量。该向量表示能够保持道路之间原本的相似关系，即相似度高的道路的向量之间的距离非常近，进而能够提高交通状况预测任务的性能。在得到这种保持语义相似性的向量表示后，利用K近邻分类器对道路的交通状况进行分类，进而完成交通状况的预测任务。在K近邻分类器中，基于度量学习的方法，可以自动学习在交通状态预测任务中衡量向量之间距离的最佳度量方式，还能有效避免手动选择距离度量方式的弊端。

本发明解决其技术问题所采用的技术方案包括以下步骤：

步骤1：获取若干辆出租车轨迹数据、出租车所在城市兴趣点数据和路网数据；利用地图匹配算法对轨迹数据和路网数据进行地图匹配，为所有出租车的每个轨迹点匹配相应的道路；

对于任意一个轨迹点z，用轨迹点z相邻的前后两个轨迹点之间的距离除以出租车通过前后两个轨迹点的时间间隔，表示出租车通过轨迹点z的速度；之后利用出租车通过每个轨迹点的速度和该轨迹点所在的道路数据，计算出每条道路l_i在给定的时间范围T内的相同时间片t_j上的通行速度向量v(l_i，j)∈R^T×1；i∈[1，X]，j表示时间片序号，X表示道路的总数量；l_i，j表示第j个时间片时的第i条道路；

统计每条道路周围城市兴趣点的分布类型及分布类型的数量，用城市兴趣点分布向量p(l_i，j)表示；

步骤2：构建道路表L∈R^X×Y，l中的元素为：

l_i，j＝i×X+j

式中，Y表示一天内划分的时间片的数量；在道路表中，l_i，j的值为道路l_i，j在道路表中的序号；

步骤3：构建道路表L中道路的上下文；

定义道路的上下文用邻接矩阵M∈R^XY×XY表示，M中的元素m_{(i，j)，(x，y)}定义如下：

式中，N_T(l_i，j)表示当前道路l_i，j在时间上邻近的道路集合，定义如下：

N_T(l_i，j)＝{l_i，r|j-w_t≤r≤j}

式中，w_t为预设时间窗口，r表示时间片序号；

N_S(l_i，j)表示当前道路l_i，j在空间上邻近的道路集合，定义如下：

N_S(l_i，j)＝{l_e，j|d(l_i，j，l_e，j)≤w_s}

式中，d(l_i，j，l_e，j)表示道路l_i，j和l_e，j在路网拓扑结构中的距离，w_s为预设路网距离窗口；e为道路序号；

N_C(l_i，j)表示与当前道路l_i，j的通行速度高度相关的道路集合，定义如下：

N_C(l_i，j)＝{l_k，m|JS(v(l_i，j)||v(l_k，m))＜ε}

式中，JS(v(l_i，j)||v(l_k，m))表示道路l_i，j的通行速度向量v(l_i，j)和道路l_k，m的通行速度向量v(l_k，m)之间的JS散度；ε表示两条道路通行速度相似度阈值，m表示时间片序号，k为道路序号；

N_P(l_i，j)表示与当前道路l_i，j的城市兴趣点分布高度相似的道路集合，定义如下：

N_P(l_i，j)＝{l_k，m|JS(p(l_i，j)||p(l_k，m))＜ε′}

式中，JS(p(l_i，j)||p(l_k，m))表示道路l_i，j的城市兴趣点分布向量p(l_i，j)和道路l_k，m的城市兴趣点分布向量p(l_k，m)之间的JS散度；ε′表示两条道路城市兴趣点分布相似度的阈值；

若邻接矩阵M中的元素m_{(i，j)，(x，y)}的值为1，则表示道路l_x，y是道路l_i，j的上下文；反之，则不是；

步骤4：将步骤3得到的邻接矩阵M输入图嵌入模型，以最大化生成道路l_i，j的概率为目标，基于负采样和随机梯度上升法的训练方法进行训练；训练完成后，得到表示任意道路l_i，j参数的参数向量vec_i，j；

步骤5：使用度量学习的方法学习衡量参数向量vec_i，j和vec_k，m之间距离的最佳方式d′(vec_i，j，vec_k，m)，定义如下：

式中，N为度量矩阵，表示度量学习的参数；N能被分解为：

N＝Q^TQ

式中，Q为正交基，表示模型参数；

步骤6：设计K近邻分类器；

通过概率投票的方式，正确判断道路l_i，j的交通状况类别的概率P_i，j定义如下：

式中，Ω_i，j表示在向量空间中距离参数向量vec_i，jK个最近的参数向量集合；Ψ_i，j表示在向量空间中距离参数向量vec_i，jK个最近的参数向量中道路交通状况与道路l_i，j相同的参数向量集合；

以分类准确率指标最大化定义目标函数：

式中，α为正则化项的常数；

完成对K近邻分类器的训练；

步骤7：将表示道路l_i,j的参数向量vec_i,j的K个最近的参数向量对应的道路交通状况类别作为输入，输入到训练完成的K近邻分类器，K近邻分类器的输出为对道路l_i,j的交通状况预测。

进一步地，所述轨迹点由出租车id、经度、纬度、时间四项数据唯一标识。

进一步地，城市兴趣点的类型包括但不限于餐饮区类型、购物区类型、娱乐区类型、办公区类型、居民区类型。

本发明的有益效果是：由于采用了本发明的一种基于图嵌入模型和度量学习的交通状况预测方法，克服了现有技术对中使用视频监控数据分析困难、无法利用道路之间的相似性预测当前道路的交通状况的缺点。本发明方法可以自动学习在交通状态预测任务中衡量向量之间距离的最佳度量方式，有效避免手动选择距离度量方式的弊端。能够根据道路之间原本的相似关系，实现道路交通状况预测任务。

附图说明

图1为本发明方法流程图。

图2为图嵌入模型示意图。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

如图1和图2所示，本发明提供了一种基于图嵌入模型和度量学习的交通状况预测方法，将道路的上下文道路，包括与当前道路在时间、空间邻近的道路以及与当前道路的城市兴趣点分布相似、通行速度高度相关的道路表示为隐空间中低维、稠密的向量。该向量表示能够保持道路之间原本的相似关系，即相似度高的道路的向量之间的距离非常近，进而能够提高交通状况预测任务的性能。在得到这种保持语义相似性的向量表示后，利用K近邻分类器对道路的交通状况进行分类，进而完成交通状况的预测任务。在K近邻分类器中，基于度量学习的方法，可以自动学习在交通状态预测任务中衡量向量之间距离的最佳度量方式，还能有效避免手动选择距离度量方式的弊端。

本发明解决其技术问题所采用的技术方案包括以下步骤：

步骤1：获取10000辆出租车轨迹数据、出租车所在城市兴趣点数据和路网数据；利用地图匹配算法对轨迹数据和路网数据进行地图匹配，为所有出租车的每个轨迹点(用＜出租车id，经度，纬度，时间>唯一标识)匹配相应的道路；

对于任意一个轨迹点z，用轨迹点z相邻的前后两个轨迹点之间的距离除以出租车通过前后两个轨迹点的时间间隔，表示出租车通过轨迹点z的速度；之后利用出租车通过每个轨迹点的速度和该轨迹点所在的道路数据，计算出每条道路l_i在给定的时间范围T内的相同时间片t_j上的通行速度向量v(l_i，j)∈R^T×1；i∈[1，X]，j表示时间片序号，X表示道路的总数量；l_i，j表示第j个时间片时的第i条道路；

统计每条道路周围城市兴趣点的分布类型及分布类型的数量，用城市兴趣点分布向量p(l_i，j)表示；城市兴趣点的类型包括餐饮区类型、购物区类型、娱乐区类型、办公区类型、居民区类型等；

步骤2：构建道路表L∈R^X×Y，L中的元素为：

l_i，j＝i×X+j

式中，Y表示一天内划分的时间片的数量；在道路表中，l_i，j的值为道路l_i，j在道路表中的序号；

步骤3：构建道路表L中道路的上下文；

定义道路的上下文用邻接矩阵M∈R^XY×XY表示，M中的元素m_{(i，j)，(x，y)}定义如下：

式中，N_T(l_i，j)表示当前道路l_i，j在时间上邻近的道路集合，定义如下：

N_T(l_i，j)＝{l_i，r|j-w_t≤r≤j}

式中，wt为预设时间窗口，r表示时间片序号；

N_S(l_i，j)表示当前道路l_i，j在空间上邻近的道路集合，定义如下：

N_S(l_i，j)＝{l_e，j|d(l_i，j，l_e，j)≤w_s}

式中，d(l_i，j，l_e，j)表示道路l_i，j和l_e，j在路网拓扑结构中的距离，w_s为预设路网距离窗口；e为道路序号；

N_C(l_i，j)表示与当前道路l_i，j的通行速度高度相关的道路集合，定义如下：

N_C(l_i，j)＝{l_k，m|JS(v(l_i，j)||v(l_k，m))＜ε}

式中，JS(v(l_i，j)||v(l_k，m))表示道路l_i，j的通行速度向量v(l_i，j)和道路l_k，m的通行速度向量v(l_k，m)之间的JS散度；ε表示两条道路通行速度相似度阈值，m表示时间片序号，k为道路序号；

N_P(l_i，j)表示与当前道路l_i，j的城市兴趣点分布高度相似的道路集合，定义如下：

N_P(l_i，j)＝{l_k，m|JS(p(l_i，j)||p(l_k，m))＜ε′}

式中，JS(p(l_i，j)||p(l_k，m))表示道路l_i，j的城市兴趣点分布向量p(l_i，j)和道路l_k，m的城市兴趣点分布向量p(l_k.m)之间的JS散度；ε′表示两条道路城市兴趣点分布相似度的阈值；

若邻接矩阵M中的元素m_{(i，j)，(x，y)}的值为1，则表示道路l_x，y是道路l_i，j的上下文；反之，则不是；

步骤4：假设通过道路的上下文交通状态可以推断出当前道路的交通状态，将步骤3得到的邻接矩阵M输入图嵌入模型，以最大化生成道路l_i，j的概率为目标，基于负采样和随机梯度上升法的训练方法进行训练；训练完成后，得到表示任意道路l_i，j参数的参数向量vec_i，j；

步骤5：将表示道路的参数向量在向量空间中的距离大小作为K近邻分类器中衡量距离的方式；为了提高预测交通状况的准确率，使用度量学习的方法学习衡量参数向量vec_i，j和vec_k，m之间距离的最佳方式d(vec_i，j，vec_k，m)，定义如下：

式中，N为度量矩阵，表示度量学习的参数；为了保持距离的非负性和对称性，N必须为正定或半正定矩阵，N能被分解为：

N＝Q^TQ

式中，Q为正交基，表示模型参数；

步骤6：设计K近邻分类器；

道路l_i，j的交通状况类别是由向量空间中vec_i，j的K个最近的向量对应的交通状况类别依据概率投票的方式决定的。通过概率投票的方式，正确判断道路l_i，j的交通状况类别的概率P_i，j定义如下：

式中，Ω_i，j表示在向量空间中距离参数向量vec_i，jK个最近的参数向量集合；Ψ_i，j表示在向量空间中距离参数向量vec_i，jK个最近的参数向量中道路交通状况与道路l_i，j相同的参数向量集合；

以分类准确率指标最大化定义目标函数：

式中，α为正则化项的常数；

完成对K近邻分类器的训练；

步骤7：将表示道路l_i，j的参数向量vec_i，j的K个最近的参数向量对应的道路交通状况类别作为输入，输入到训练完成的K近邻分类器，K近邻分类器的输出为对道路l_i，j的交通状况预测。

本发明为基于图嵌入模型和度量学习的交通状况预测方法，通过图嵌入模型可以学习到保持道路之间相似性的特征向量表示，进而利用基于度量学习的K近邻分类器对道路的交通状况进行预测，得到每条道路在每个时间片的交通状况。

Claims (3)

1.一种基于图嵌入模型和度量学习的交通状况预测方法，其特征在于，包括以下步骤：

步骤1：获取若干辆出租车轨迹数据、出租车所在城市兴趣点数据和路网数据；利用地图匹配算法对轨迹数据和路网数据进行地图匹配，为所有出租车的每个轨迹点匹配相应的道路；

对于任意一个轨迹点z，用轨迹点z相邻的前后两个轨迹点之间的距离除以出租车通过前后两个轨迹点的时间间隔，表示出租车通过轨迹点z的速度；之后利用出租车通过每个轨迹点的速度和该轨迹点所在的道路数据，计算出每条道路l_i在给定的时间范围T内的相同时间片t_j上的通行速度向量v(l_i，j)∈R^T×1；i∈[1，X]，j表示时间片序号，X表示道路的总数量；l_i，j表示第j个时间片时的第i条道路；

统计每条道路周围城市兴趣点的分布类型及分布类型的数量，用城市兴趣点分布向量p(l_i，j)表示；

步骤2：构建道路表L∈R^X×Y，L中的元素为：

l_i，j＝i×X+j

式中，Y表示一天内划分的时间片的数量；在道路表中，l_i，j的值为道路l_i，j在道路表中的序号；

步骤3：构建道路表L中道路的上下文；

定义道路的上下文用邻接矩阵M∈R^XY×XY表示，M中的元素m_{(i，j)，(x，y)}定义如下：

式中，N_T(l_i，j)表示当前道路l_i，j在时间上邻近的道路集合，定义如下：

N_T(l_i，j)＝{l_i，r|j-w_t≤r≤j}

式中，w_t为预设时间窗口，r表示时间片序号；

N_s(l_i，j)表示当前道路l_i，j在空间上邻近的道路集合，定义如下：

N_s(l_i，j)＝{l_e，j|d(l_i，j，l_e，j)≤w_s}

式中，d(l_i，j，l_e，j)表示道路l_i，j和l_e，j在路网拓扑结构中的距离，w_s为预设路网距离窗口；e为道路序号；

N_C(l_i，j)表示与当前道路l_i，j的通行速度高度相关的道路集合，定义如下：

N_C(l_i，j)＝{l_k，m|JS(v(l_i，j)||v(l_k，m))＜ε}

式中，JS(v(l_i，j)||v(l_k，m))表示道路l_i，j的通行速度向量v(l_i，j)和道路l_k，m的通行速度向量v(l_k，m)之间的JS散度；ε表示两条道路通行速度相似度阈值，m表示时间片序号，k为道路序号；

N_P(l_i，j)表示与当前道路l_i，j的城市兴趣点分布高度相似的道路集合，定义如下：

N_P(l_i，j)＝{l_k，m|JS(p(l_i，j)||p(l_k，m))＜ε′}

式中，JS(p(l_i，j)||p(l_k，m))表示道路l_i，j的城市兴趣点分布向量p(l_i，j)和道路l_k，m的城市兴趣点分布向量p(l_k，m)之间的JS散度；ε′表示两条道路城市兴趣点分布相似度的阈值；

若邻接矩阵M中的元素m_{(i，j)，(x，y)}的值为1，则表示道路l_x，y是道路l_i，j的上下文；反之，则不是；

步骤4：将步骤3得到的邻接矩阵M输入图嵌入模型，以最大化生成道路l_i，j的概率为目标，基于负采样和随机梯度上升法的训练方法进行训练；训练完成后，得到表示任意道路l_i，j参数的参数向量vec_i，j；

步骤5：使用度量学习的方法学习衡量参数向量vec_i，j和vec_k，m之间距离的最佳方式d′(vec_i，j，vec_k，m)，定义如下：

式中，N为度量矩阵，表示度量学习的参数；N能被分解为：

N＝Q^TQ

式中，Q为正交基，表示模型参数；

步骤6：设计K近邻分类器；

通过概率投票的方式，正确判断道路l_i，j的交通状况类别的概率P_i，j，定义如下：

式中，Ω_i，j表示在向量空间中距离参数向量vec_i，jK个最近的参数向量集合；Ψ_i，j表示在向量空间中距离参数向量vec_i，jK个最近的参数向量中道路交通状况与道路l_i，j相同的参数向量集合；

以分类准确率指标最大化定义目标函数：

式中，α为正则化项的常数；

完成对K近邻分类器的训练；

步骤7：将表示道路l_i,j的参数向量vec_i,j的K个最近的参数向量对应的道路交通状况类别作为输入，输入到训练完成的K近邻分类器，K近邻分类器的输出为对道路l_i,j的交通状况预测。

2.根据权利要求1所述的一种基于图嵌入模型和度量学习的交通状况预测方法，其特征在于，所述轨迹点由出租车id、经度、纬度、时间四项数据唯一标识。

3.根据权利要求1所述的一种基于图嵌入模型和度量学习的交通状况预测方法，其特征在于，所述城市兴趣点的类型包括但不限于餐饮区类型、购物区类型、娱乐区类型、办公区类型、居民区类型。

Images