面向交通流预测的分支定界算法图卷积模型

2023-06-16王静潇王辛岩周禹彤

现代电子技术 2023年12期

王静潇，王辛岩，周禹彤，张越

（西藏大学工学院，西藏拉萨 850000）

0 引言

城市正在由工业化向信息化转换，在城市数字化、智能化的进程中积累了海量的交通数据，但这些由物联网传感器产生的数据是一个复杂庞大且难以解决的计算问题[1]。边缘计算作为一种新兴技术，可以使计算能力更接近终端设备，并提供低延迟和高可靠性的资源密集型服务[2]，减少能源的消耗，在智能交通中发挥了举足轻重的作用。在不断发展的智能运输系统（ITS）中，为了从效率和拥堵两方面保障公共交通，交通量的预测至关重要，在优化资源配置、交通异常检测以及城市管理等方面也有着广泛的应用。

交通流预测常用方法包括标准机器学习（Standard Machine Learning, ML）和基于统计分析的方法等，然而上述方法只考虑了时间数据，而忽略了空间数据在预测中的重要性，因此基于深度学习的交通流预测算法得到了广泛的研究。 Ma 等首次将长期记忆（Long Short-Term Memory, LSTM）网络用于交通速度检测，获得了不错的效果[3]。胡姣姣等采用卷积神经网络（Convolutional Neural Network, CNN）提取数据中的时间特征，相比LSTM 可以参数共享，但是忽略了空间信息[4]。Harrou Fouzi 等研究人员将交通网络描述为网格，并使用CNN 捕获空间相关性[5]。由于道路的不规则性，交通网络拓扑结构复杂，采用网格建模最终会丢失交通网络内部的拓扑信息。Wang 等探索了时变图卷积网络来建模不同时间的动态空间相关性，并捕获交通图的稳定空间相关性[6]。文章将道路表示为节点，并根据道路网络之间的连接关系创建边缘以解决这一问题；接着用图卷积神经网络（GCNN）有效地捕获各种相关性，聚合相邻节点的信息，从而捕获复杂的时空联合。为了获得准确数值，需要先对图像进行预处理去除噪声、超参数和冗余节点。基于图卷积神经网络模型会为交通流预测带来丰富的超参数和庞大的计算，随机选择这些数值会降低研究整体有效性，Zhai 等使用基于优化的分支定界方法已经成功地解决类似的问题[7]。受图卷积神经网络以及分支定界的启发[8-9]，文章提出一种新的交通流预测框架HGCNNF，新颖之处在于：开发一个端到端的框架，该框架首先使用离群点检测技术进行数据清洗；然后使用图卷积神经网络处理清洗后的数据；最后使用超参数优化技术优化学习过程。面向交通流预测的混合图卷积神经网络模型如图1 所示。

图1 面向交通流预测的混合图卷积神经网络模型

1 模型框架介绍

1.1 预处理

预处理的作用是删除不相关的节点来缩小图的大小。在道路路网中，每个节点被视为一条道路，其中每条边是两个相邻道路之间的连接。在此框架里考虑使用离群点检测法来去除噪声和不必要的区域。局部离群因子算法（Local Outlier Factor, LOF）[10]是检测异常值的无监督的离群检测方法。文章将道路标记为节点，然后使用局部可达密度来计算LOF。若LOF≈1，则是正常点；若LOF≫1，则认为是异常值，并把其从图中删除，与之相关的边也被移除。

1.2 图卷积神经网络

为了建立GCNN，建立图的邻接矩阵。首先将文章中的交通路网定义为无向图，用无权重图G= (V,E,A)表示，其中E表示边的集合，邻接矩阵A∈RN×N表示道路之间的连接，Aij=1 当且仅当节点i和j之间存在连接，Aij=0 当且仅当节点i和j不相交。此外，创建节点矩阵H′表示每一层的特征，然后构造如下所示的矩阵：

式中：W是在深度学习框架中的线形层中每一层权重，是每个节点共享线性变换；σ是非线性激活函数；̂=A+I（I为单位矩阵，确保节点始终与自身连接，避免丢弃中心节点）；̂是̂度矩阵（̂-1的存在是为了规范邻接矩阵），对称归一化的结果如下：

目前，GCN 是最常用的图卷积层，此外，在扩展模型中，节点可以沿着边传递信息，然后节点用置换不变性函数聚合所有接收的消息。令表示从i到j节点所传输的信息，引入消息函数fe：

然后，利用式（4）读出函数，对所有进入节点的消息进行聚合：

式中，Ni为节点i邻居节点集合，这就产生了神经信息传递法（Message Passing for Node, MPNN）。fe和fv都是典型的微小多层感知器。更为普遍的公式如下：

式中，αij是一个不被明确定义的系数，这会导致文章实验结果出现偏差，因此扩展为：

从式（6）、式（7）可看出，a也许可以通过共享的自注意力机制来学习。图2 所示为文章模型中使用的图卷积神经网络（GCNN）框架。

图2 GCNN 模型框架图

1.3 超参数优化

超参数通常指在算法模型中无法使用传统方法直接优化的部分。令Γ={Γ1,Γ2,…,Γ|Γ|}表示所提框架使用的所有参数的集合,并且调用Γi的定义域空间，它包含所有潜在值D(Γi) 。不同的配置在配置空间C中表示,并且每个配置都是Γ中所有参数的集合。需要对C中所有配置进行调查，目的是确定Γ中所有参数的最优值。这需要大量的计算和运行的内存资源，成本也高，每一次训练都消耗一定的时间，特别是对于具有连续值的数量。因此，C中所有的配置的数量可以用下面公式计算：

为了处理以上问题，文献[11]中提供了一种有效的基于分支定界的启发式方法。该方法的分支过程涉及到一颗搜索树的构造，其中包含问题的所有可能解决方案。只有凸问题才能保证有全局最优解。分支界定法的思想是：首先构造问题目标值的上下界（上界一般是之前求出的最优解，下界为无约束条件下当前搜索路径的最优解），边搜索边减掉不是解决方案的分支，提高搜索效率；然后通过回溯法遍历搜索树，不断更新上下界。分支界定法在两个方面加速了算法的搜索效率：一是在选择扩展节点时，总是选择一个最小成本的节点，尽可能早地进入最有可能成为最优解的分支；二是扩展节点的过程，舍弃导致不可行解或导致非最优解的子节点。分支定界流程如图3 所示。

图3 分支定界流程

根据国内外研究现状，文章提出两个探索策略：

1）深度优先策略。首先爬下一根树枝，直到无法继续运行，然后开始回到分支。

2）广度优先策略。在每一个深度，检查几个分支，然后进一步下降，一直重复上述步骤，直至到达底层。

2 实验与结果分析

2.1 数据选取和对比模型

为了验证所提出的框架的交通流量预测性能，使用4 个公共交通网络进行了大量的交通流预测测试。文章选用了美国加利福尼亚交通运输部公开的高速公路PeMSD03、PeMSD05 和PeMSD08 以及PeMSD07 作为实验数据集，该数据集是通过PeMS 系统收集，并且数据会被聚合成5 min 的增量，从而在一天内可产生288 个交通点，且各种性能数据可用，如容量、速度、延迟、道路占用率和年平均日交通量（AADT）。并且数据已经进行过数据预处理等操作。图4 所示为PeMS 所展示的性能度量图和图标。

图4 PeMS 所展示的性能度量图和图标

每个数据集的空间邻接网络都使用基于距离的道路网络构建，因此对输入的数据进行归一化处理，采用Zscore标准化，公式如下：

式中：x表示原始数据；mean 表示交通流数据的平均值；std 表示交通流数据的标准差。

将HGCNNF 与以下的方法进行比较：

STGCN[12]：将图形卷积与一维卷积单元相结合的时空卷积网络。

STFGNN[13]：时空融合图神经网络，它基于不同的空间和时间图的融合操作，并行地处理不同的时间段，能够有效地学习隐藏的时空依赖关系。

GraphWaveNet[14]：一种新颖的自适应依赖性矩阵并通过节点嵌入来学习，该模型可以精确地捕获数据中隐藏的空间依赖性。

2.2 实验环境

文章的实验环境系统为Ubantu 19.04，Python 版本为3.7，CPU为IntelⓇCoreTMi5-12400 2.50 GHz 16.0 GB，GPU 为NVIDIA GeForce RTX 3070，采用Pytorch 1.4 框架来搭建HGCNNF 模型。用mAP（mean Average Precision）来评价HGCNNF 的指标。mAP 常被用来测试交通流预测的各个方面，定义如下：

式中：n被视为所有流中经过校正的预测流；AvgP(i)表示被计算为以i为序列的精度结果。