基于DGCN的交通流量预测

Traffic Flow Forecasting Based on Dynamic Graph Convolution Network

摘要: 及时准确的交通预测对城市交通控制和引导至关重要。由于交通数据的复杂性和非平稳变化，传统的预测方法不能满足中长期预测任务的要求，往往忽略了交通流的时空依赖性。文章采用了一种新的深度学习框架——动态图卷积网络(DGCN)来解决交通领域的时间序列预测问题。我们没有使用常规的卷积和循环单元，而是在图上表达问题，该网络引入潜在网络提取时空特征，用于自适应构建动态路网图矩阵。实验表明，我们的模型DGCN有效捕获了全面的时空相关性，并在各种真实交通数据集上始终优于最先进的基线。

Abstract: Timely and accurate traffic forecasting is very important for urban traffic control and guidance. Due to the complexity and non-stationary changes of traffic data, traditional forecasting methods can not meet the requirements of medium and long-term forecasting tasks and often ignore the temporal and spatial dependence of traffic flow. In this paper, a new deep learning framework—Dynamic Graph Convolution Network (DGCN), is adopted to solve the problem of time series prediction in the traffic field. We don’t use the conventional convolution and circulation unit, but express the problem on the graph. The network introduces the potential network to extract the spatio-temporal features and is used to adaptively construct the dynamic road network graph matrix. Experiments show that our model DGCN effectively captures the comprehensive spatial-temporal correlation and is always superior to the most advanced baseline on various real traffic data sets.

1. 引言

交通预测是智能交通系统不可缺少的一部分，特别是在交通流量大、行驶速度快的高速公路上。由于高速公路相对封闭，一旦发生拥堵，将严重影响通行能力。交通流量是反映公路状态的基本指标。如果能够提前准确预测，交通管理部门将能够更合理地引导车辆，提高公路网的运行效率。公路交通流预测是一个典型的时空数据预测问题。交通数据在固定的时间点和固定的分布地点进行记录。显然，相邻地点和时间戳的观测结果不是独立的，而是相互动态相关的。因此，有效地提取数据的时空相关性是解决这些问题的关键。公路网交通数据的相关性在空间维度和时间维度上都表现出较强的动态性。如何对非线性、复杂的时空数据进行挖掘，发现其内在的时空模式，并进行准确的交通流预测是一个非常具有挑战性的问题[1]。

幸运的是，随着交通运输业的发展，许多摄像头、传感器等信息采集设备已经部署在高速公路上。每一个设备被放置在一个独特的地理空间位置上，不断产生关于交通的时间序列数据。这些设备积累了大量丰富的具有地理信息的交通时间序列数据，为交通预测提供了坚实的数据基础[2]。许多研究人员已经为解决这些问题做出了巨大的努力。早期，时间序列分析模型被用于交通预测问题。但在实际应用中，对于不稳定的非线性数据的处理存在一定的困难。后来，传统的机器学习方法得到了发展[3]，可以对更复杂的数据进行建模，但仍然难以同时考虑高维交通数据的时空相关性[4]。此外，这类方法的预测性能严重依赖于特征工程，往往需要相应领域专家的大量经验。近年来，许多研究者使用深度学习方法处理高维时空数据[5]-[7]，即采用卷积神经网络(CNN)有效提取网格数据的空间特征；图卷积神经网络(GCN)用于描述基于图的数据的空间相关性[8] [9]。然而，这些方法仍然不能同时模拟交通数据的时空特征和动态相关性[10]。本文的主要贡献总结如下：提出了一种基于动态图拉普拉斯矩阵的交通预测动态图卷积网络(DGCN)；提出了一种基于图拉普拉斯矩阵的潜在网络自适应表示交通数据的时空联系；在多个真实交通数据集上进行了交通预测实验，验证了模型的有效性。

2. 图卷积网络理论基础

2.1. 图的概述

在数据科学领域中，图被用来描述各类关系型数据，通常表示物体与物体之间的关系。在数学中，图的定义为顶点(Vertex)和连接顶点的边(Edge)组成的集合，记为$G=\left(V,E\right)$ ，其中V是顶点集合，E是边集合，设顶点数为N，边数为M，连接顶点$v_i,v_j$ 的边记为$e_{ij}$ 。如果顶点$v_i$ 和$v_j$ 之间有边相连，则称$v_i$ 是$v_j$ 的邻居，记$v_i$ 的所有邻居为集合$N\left(v_i\right)$ ，即：

$N\left(v_i\right)=\left\{v_j|\exists e_{ij}\in E\text{or}{e}_{ji}\in E\right\}$

顶点$v_i$ 连接的边的数目称为$v_i$ 的度(Degree)，记为：$\mathrm{deg}\left(v_i\right)=\left|N\left(v_i\right)\right|$ 。

邻接矩阵常被用于描述图中各顶点之间的连接情况，通常是一个二维数组，记为$A\in R^{N\ast N}$ ，矩阵中的1值代表对应的顶点间有连接关系，0值代表没有连接关系，邻接矩阵的定义公式如下：

$A_{ij}=\{\begin{array}{l}1,\text{if}\left(v_i,v_j\right)\subseteq E\\ 0,\text{else}\end{array}$

设图$G=\left(V,E\right)$ ，重新对边进行编号$e_1,e_2,\cdots ,e_M$ ，如图1所示。

Figure 1. Figure G example

图1. 图G示例

在实际的图数据中，邻接矩阵会出现大量的0值，因此通常用稀疏矩阵的格式来存储邻接矩阵。图2中给出了图G的邻接矩阵存储表示，可以看出无向图的邻接矩阵是沿主对角线对称的，即$A_{ij}=A_{ji}$ 。

Figure 2. Adjacency matrix of graph G

图2. 图G的邻接矩阵

2.2. 神经网络基础

神经网络的运行过程分为三步：前向传播、反向传播、参数更新，通过不断迭代进行模型参数的更新，以从数据中挖掘出有价值的信息，如图3所示。

1) 前向传播：给定输入和参数，逐层向前进行计算，最后输出预测结果；

2) 反向传播：基于前向传播得到的预测结果，使用损失函数得到损失值，然后计算相关参数的梯度，该计算方法称为反向传播(back-propagation)，具体的细节后面将详细介绍；

3) 参数更新：使用梯度下降算法对参数进行更新，重复上述过程，逐步迭代，直到模型收敛。

Figure 3. Neural network operation process

图3. 神经网络运行过程

损失函数是指导模型进行有效学习的基础，常见的用于回归类问题的损失函数是平方损失函数，是模型的预测结果与真实值的平方差，其定义如下：

$L\left(y,f\left(x;\theta \right)\right)=\frac{1}{N}{\displaystyle \sum }_{i=1}^N{\left(y_i-f\left(x_i;\theta \right)\right)}^2$

激活函数是神经网络中一个十分重要的概念，使得神经网络几乎可以逼近任意非线性函数，常用的激活函数如表1所示。

Table 1. Activation function

表1. 激活函数

名称	表达式	特点
Sigmoid	$\sigma \left(x\right)=\frac{1}{1+{\text{e}}^{-x}}$	将任意大小的输入压缩到(0, 1)之间
Tanh	$\tanh \left(x\right)=\frac{{\text{e}}^x-{\text{e}}^{-x}}{{\text{e}}^x+{\text{e}}^{-x}}$	值域范围为(−1, 1)
ReLU	$\text{ReLU}\left(x\right)=\{\begin{array}{l}x\text{if}x\ge 0\\ 0\text{if}x<0\end{array}$	单侧抑制，当输入为负时，全部置零
LeakyReLU	$\text{LeakyReLU}\left(x\right)=\{\begin{array}{l}x\text{if}x>0\\ \lambda x\text{if}x<0\end{array}$	输入为负时，允许一定量信息通过
ELU	$\text{ELU}\left(x\right)=\{\begin{array}{ll}x\hfill & \text{if}x\ge 0\hfill \\ \alpha \left({\text{e}}^x-1\right)\hfill & \text{if}x<0\hfill \end{array}$	输入为负时，进行非线性变换

3. 基于动态图卷积网络的交通流量预测

3.1. 交通流量预测

交通流量预测。假设交通网络G中各节点记录的第f个时间序列为交通序列，$f\in \left(1,\cdots ,F\right)$ 。我们用$x_t^{c,i}\in R$ 表示节点i在时刻t的第c个特征值，$x_t^i\in R^F$ 表示节点i在时刻t的所有特征值。$X_t={\left(x_t^1,x_t^2,\cdots ,x_t^N\right)}^{\text{T}}\in R^{N\times F}$ 表示所有节点在时刻t的所有特征值。$\text{Χ}={\left(X_1,X_2,\cdots ,X_{\tau }\right)}^{\text{T}}$ 表示所有节点在$\tau$ 个时间片上的所有特征值。另外，设$y_t^i=x_t^{f,i}\in R$ 表示节点i在未来t时刻的交通流量。

问题。给定X，交通网络上所有节点在过去$\tau$ 时间片上的各种历史测量值，预测未来$T_P$ 时间片上的交通流量序列$\text{Y}={\left(y^1,y^2,\cdots ,y^N\right)}^{\text{T}}\in R^{N\times T_P}$ ，其中$y^i=\left(y_{\tau +1}^i,y_{\tau +2}^i,\cdots ,y_{\tau +T_P}^i\right)\in R^{T_P}$ 表示节点i从$\tau +1$ 开始的未来交通流量。

3.2. 图卷积

空间图卷积负责处理图结构数据中的空间依赖性，即节点与其邻居节点之间的关系。通过聚合邻居节点的特征信息来更新每个节点的表示。常用的图卷积方法包括谱图卷积(如GCN)、空间图卷积(如GraphSAGE)等。根据图的邻接矩阵或空间关系定义确定每个节点的邻居。使用聚合函数(如均值聚合、求和聚合等)将邻居节点的特征信息进行聚合。通过可学习的权重矩阵对聚合后的特征进行变换，以提取更高层次的特征图卷积过程，如图4所示。

Figure 4. Spatial graph convolution and temporal graph convolution

图4. 空间图卷积和时间图卷积

谱图理论将基于网格的数据的卷积运算推广到图结构数据。在本研究中，交通网络本质上是一个图结构，每个节点的特征可以看作是图上的信号。因此，为了充分利用交通网络的拓扑特性，我们在每个时间切片上采用基于谱图理论的图卷积直接处理信号，利用交通网络在空间维度上的信号相关性。谱法将图转换成代数形式，分析图的拓扑属性，如图结构中的连通性等。

在谱图分析中，一个图用它对应的拉普拉斯矩阵表示。通过分析拉普拉斯矩阵及其特征值，可以得到图结构的性质。图的拉普拉斯矩阵定义为$L=D-A$ ，其归一化形式为：

$L=I_N-D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}\in R^{N\times N}$

其中A为邻接矩阵，$I_N$ 为单位矩阵，度矩阵$D\in R^{N\times N}$ 为对角矩阵，由节点度组成，$D_{ii}={\displaystyle {\sum }_j{A}_{ij}}$ 。

拉普拉斯矩阵的特征值分解为$L=U\Lambda U^{\text{T}}$ ，其中$\Lambda =\text{diag}\left(\left[{\lambda }_0,\cdots ,{\lambda }_{N-1}\right]\right)\in R^{N\times N}$ 为对角矩阵，U为傅里叶基。以时刻t的交通流量为例，整个图上的信号为$\mathcal{x}=x_t^f\in R^N$ ，该信号的图傅里叶变换定义为$\widehat{\mathcal{x}}=U^{\text{T}}\mathcal{x}$，根据拉普拉斯矩阵的性质，U是一个正交矩阵，因此对应的傅里叶反变换为$\mathcal{x}=U\widehat{\mathcal{x}}$ 。图卷积是一种卷积操作，通过使用在傅里叶域中对角化的线性算子来取代经典卷积算子(Henaff, Bruna, and LeCun, 2015)。基于此，图G上的信号$\mathcal{x}$ 被核函数$g_{\theta }$ 过滤：

$g_{\theta }\ast G\mathcal{x}=g_{\theta }\left(L\right)\mathcal{x}=g_{\theta }\left(U\Lambda U^{\text{T}}\right)\mathcal{x}=U{g}_{\theta }\left(\Lambda \right)U^{\text{T}}\mathcal{x}$

其中$\ast G$ 表示图卷积操作。由于图信号的卷积运算等于通过图傅里叶变换到谱域的这些信号的乘积，因此上式可以理解为分别将$g_{\theta }$ 和$\mathcal{x}$ 进行傅里叶变换到谱域，然后将它们的变换结果相乘，进行傅里叶反变换，得到卷积运算的最终结果。

3.3. 基于DGCN的交通流量预测

与传统基于GCN方法中的固定和经验拉普拉斯矩阵相比，用于交通预测的新型动态图卷积网络引入了一个拉普拉斯矩阵潜在网络(LMLN)来自适应地表示时空关系，然后将这种关系馈送到GCN，形成一个动态图卷积网络。基于DGCN的交通预测组件主要有以下三个模块，它们被压缩以提取输入交通数据的时空特征，如图5所示。

Figure 5. The proposed DGCN based on spatial-temporal unit, where $\otimes$ is the Hadamard product

图5. 基于时空单位的DGCN，其中$\otimes$ 是哈达玛积

1) 时间卷积层(TCL)：该时间卷积层旨在从原始交通数据中提取高维局部时间信息。交通数据${\overrightarrow{X}}_{\left(1:k\ast T\right)}=\left(X_1,\cdots ,X_t,\cdots ,X_{k\text{*}T}\right)\in R^{N\times k\ast T\times F}$的一段上的时间卷积可以表示如下：

$TC=\Phi \star {\overrightarrow{X}}_{\left(1:k\ast T\right)}={\text{Conv}}_{1\times t_s}\left({\overrightarrow{X}}_{\left(1:k\ast T\right)}\right)$

其中${\text{Conv}}_{1\times t_s}$ 表示二维卷积算子，其核大小为$1\times t_s$ 。

2) 图时间卷积层(GTCL)：通常，在流量预测领域，这一层可以基于GCN实现，例如，可以将GCN和TCL堆叠为一个时空块，从TCL的输出中提取时空特征TC，如下所示：

$\overrightarrow{Fea}1=g_{\theta }\star G\left(TC\right)$

$\overrightarrow{Fea}2=\text{Φ}\star \text{Relu}\left(\overrightarrow{Fea}1\right)$

3) 时间注意力：除了TCL和GTCL，我们还需要一种方法来探索长距离时间关系，因此我们采用时间注意力来自适应地捕获交通数据的大规模时间相关性。

$E=V_e\sigma \left({\left(GC\right)}^{Tr}{U}_1\right)U_2{\left(\left(GC\right)U_3\right)}^{Tr}+b_e)$

${E^{\prime }}_{i,j}=\frac{\text{exp}\left(E_{i,j}+\text{Mas}\right)}{{{\displaystyle \sum }}_{j=1}^{k\ast T}\exp \left(E_{i,j}+\text{Mas}\right)}$

其中$V_e,b_e\in R^{k\ast T\times k\ast T},U_1\in R^N,U_2\in R^{F\times N},U_3\in R^F$ 是可训练的参数，$\text{Mas}\in R^{k\ast T\times k\ast T}$ 是一个掩模矩阵，用于保持不连续时间段之间的依赖性，并使不连续时间周期之间的关系${E^{\prime }}_{i,j}\in R^{k\ast T\times k\ast T}$ 的值为零。

综上所述，我们将基于DGCN的交通预测组件的算法总结为以下算法。

算法1. 基于图卷积网络的交通预测组件

输入：当前输入特征${\overrightarrow{X}}_{\left(1:k\ast T\right)}$ ，其中$\left(X_1,\cdots ,X_t,\cdots ,X_{k\ast T}\right)\in R^{N\times k\ast T\times F}$ ，表示N个节点在$k\ast T$ 个时间步上的F维特征 步骤： 1：根据当前输入特征$X_{\left(1:k\ast T\right)}$ 计算交通状态矩阵TC $TC=\Phi \star {\overrightarrow{X}}_{\left(1:k\ast T\right)}$ 2：使用算法1从TC中获取动态拉普拉斯矩阵Lp Lp = 从TC获取动态拉普拉斯矩阵(TC) 3：利用动态拉普拉斯矩阵Lp从TC中提取图卷积(GC)特征 GC = gate函数(Lp(TC)) 4：对GC应用注意力机制Tatt得到TA TA = Tatt注意力机制(GC) 5：对TA应用批归一化和Leaky ReLU激活函数 $F_{\left(1:k\ast T\right)}$ = 批归一化(Leaky ReLU激活(TA)) 6：返回结果$F_{\left(1:k\ast T\right)}$ 返回$F_{\left(1:k\ast T\right)}$

4. 交通流量预测实验分析

4.1. 数据介绍

在实验中，我们使用两个真实的交通数据集：PeMSD4和PeMSD8来评估所提出的方法。由Caltrans性能测量系统(PeMS)以每30秒一次采样的速率从加州高速公路收集的。在这里，我们以每5分钟一个样本的方式重新采样这些数据集。PeMSD4拥有2018年1月至2月记录的307个路段的交通数据。PeMSD8收集了2016年7月至8月170个路段的交通数据。它们都包含三个交通度量，即交通流量、平均速度和道路占用率，因此F = 3。

在我们的模型中，我们将预测交通流量作为两个数据集的输出。我们还将两个数据集分为三个部分：训练集、验证集和测试集，在时间方向上的比例分别为60%、20%和20%。在实验中，我们在验证集上选择最佳模型参数，并在测试集上对所提出的模型进行评估，对各路段的数据样本进行归一化处理。

4.2. 参数设置

所有实验使用Pytorch 1.7.0在Linux集群(CPU: Intel(R) Xeon(R) Platinum 8255C CPU @ 2.50GHz，GPU: RTX 2080 Ti(11GB))上进行编译和测试。我们设定时间核的大小$t_s=3$ ，多头注意的头数K = 4。与ASTGCN类似，基于交通流量预测的GCN输出特征大小为64，三个流量数据段的长度也与ASTGCN相同，即$T_h=24$ ，$T_d=12$ ，$T_w=24$ 。预测时间间隔$T_p=12$ ，即未来一小时。因此，我们采用60个样本对未来1小时内的12个样本进行训练和预测。在本文中，batch size为8，我们使用l2_loss作为模型的损失函数，然后使用Adam优化，原始学习率为0.0005。在训练阶段，我们训练了40个epochs。

4.3. 交通流量预测结果分析

表2展示了DGCN和基线在数据集PEMSD4、PEMSD8上的结果。DGCN模型在两个评价指标中均取得了最优的表现，且具有统计学显著性。我们可以很容易地观察到，传统的统计和机器学习方法可能在短期预测中表现良好，但由于错误积累、记忆问题和缺乏空间信息，它们的长期预测并不准确。ARIMA模型由于不能处理复杂的时空数据而表现最差。深度学习方法通常比传统的机器学习模型获得更好的预测结果。

Table 2. Effect of different methods on traffic flow prediction on data sets

表2. 不同方法在数据集上的交通流量预测效果

Method	PEMSD4		PEMSD8
	MAE	RMSE	MAE	RMSE
ARIMA	31.26	47.30	24.86	37.58
AGCRN	26.12	38.76	20.13	30.14
DGCN	20.10	32.31	15.20	24.83

以前的方法没有考虑空间拓扑，并且以粗粒度的方式建模时间序列。不同的是，通过对传感器的空间拓扑进行建模，我们的模型DGCN在短期预测方面取得了显著的进步，可以有效地利用空间结构进行更准确的预测。

Figure 6. Results of AGCRN and DGCN for different forecasting times

图6. 不同预测时间的AGCRN和DGCN结果

为了进一步分析不同预测时间的结果，我们比较了AGCRN和DGCN在12个不同未来时间的预测结果。如图6所示，在所有数据集中，DGCN的指标值在所有预测时间大小上都优于AGCRN，这进一步表明我们的方法在不同的预测任务和时间上都是稳健的。

5. 结束语

在本文中，我们提出了一种新的图卷积网络DGCN用于交通预测，通过时空卷积块集成图卷积和门控时间卷积。与目前大多数基于GCN的方法在图卷积中一般使用经验图拉普拉斯矩阵不同，我们提出了一种自适应估计动态拉普拉斯矩阵的潜在网络，并验证了该方法具有较好的提取交通数据时空相关性的能力。实验表明，我们的模型在两个真实世界的数据集上优于其他最先进的方法，表明它在从输入探索时空结构方面具有巨大的潜力。在未来，我们将进一步优化网络结构和参数设置。此外，我们提出的框架可以应用于更一般的时空结构序列预测场景，如社会网络的演化、推荐系统的偏好预测等。

致 谢

感谢甘肃省计算中心提供的计算资源和技术支持。本研究中的大量计算工作均在该中心进行，这对于本论文的顺利完成起到了至关重要的作用。

基金项目

本研究得到甘肃省科技计划项目(24YFFA055, 22JR5RA797)、甘肃省云计算重点实验室开放课题(2023KFKT-005)与甘肃省重点人才项目(“东数西算”场景下的后量子数据加密传输机制研究)的资助。

NOTES

^*通讯作者。