姜
山1,2，丁治明1,3+，徐馨润1,2，严
瑾1,2
1.中国科学院软件研究所，北京100190
2.中国科学院大学，北京100190
3.大规模流数据集成与分析技术北京市重点实验室，北京100190+通信作者E-mail:**************** 摘 要：融合了路网结构的交通流态势预测是一个高度非线性化且复杂的时空动态相关性的时序数据预测问
题。然而，传统交通流态势预测方法无法建模交通网络中长时间序列数据间的时空相关性。针对交通路网交通流态势预测问题，提出了一种基于图结构的交通流预测深度学习模型。首先，基于图小波变换定义图小波卷积算子，设计了面向路网交通流态势预测的图小波卷积神经网络模块；其次，结合时空注意机制构建了用于道路网络交通流态势预测的时空动态相关性模型，以捕获交通网络的动态时空相关性； 最后，采用叠加多层图小波神经网络模块的策略，构建了一种面向路网交通流态势预测的图小波卷积神经网络模型。实验结果表明，该网络模型在数据集上的性能优于现有的基线模型。通过图小波变换矩阵与傅里叶变换矩阵非零元素统计对比实验，发现基于图小波变换定义的卷积运算更具稀疏性。因此，基于图小波变换定义的卷积运算更有助于提升交通流态势预测模型的计算效率。
关键词：交通流态势预测；图卷积；图小波神经网络；交通流文献标志码：A
中图分类号：TP391.4
Graph Neural Network for Traffic Flow Situation Prediction
JIANG Shan 1,2,DING Zhiming 1,3+,XU Xinrun 1,2,YAN Jin 1,2
1.Institute of Software,Chinese Academy of Sciences,Beijing 100190,China
2.University of Chinese Academy of Sciences,Beijing 100190,China
3.Beijing Key Laboratory on Integration and Analysis of Large-Scale Stream Data,Beijing 100190,China
Abstract:Road network structure integrated traffic flow situation prediction is a highly nonlinear and complexly spatial-temporal dynamic correlation time-series data prediction problem.However,traditional traffic flow situation forecasting methods cannot model the temporal and spatial correlation in long-term series data in the traffic network.To address the issue mentioned above,a deep learning model of traffic flow prediction based on graph structure is proposed.Firstly,the graph wavelet convolution operator is defined based on the graph wavelet transform.Furthermore,the graph wavelet convolution neural network module is designed based on the operator for the traffic flow situation prediction.Secondly,a spatial-temporal dynamic correlation model is constructed based on the spatial-temporal attention mechanism to capture the dynamic temporal and spatial correlation of the traffic network.Finally,the strategy
计算机科学与探索
1673-9418/2021/15(06)-1084-08doi:10.3778/j.issn.1673-9418.2011006
基金项目：国家自然科学基金（61703013，91646201）；北京市自然科学基金（4192004）。
This work was supported by the National Natural Science Foundation of China (61703013,91646201)and the Natural Science Founda-tion of Beijing (4192004).收稿日期：2020-11-
03
修回日期：2021-01-22
Journal of Frontiers of Computer Science and Technology
姜山等：面向路网交通流态势预测的图神经网络模型
城市道路网中的交通流态势预测问题是应急管理科学和城市管理科学等众多领域的核心问题之一。路网交通流态势预测是一个典型的时空时序数据预测问题，交通流数据被分布在城市道路网络各个固定卡口的数据采集设备以固定时间间隔连续采集。相邻设备采集的数据记录以及不同时间戳下的数据记录具有某种时空相关性。因此，有效地捕捉道路网络中观测数据间的时空相关性是解决交通流态势预测问题的关键。
近年来，卷积神经网络（convolutional neural net-work，CNN）[1-2]模型与算法已经广泛地被用于计算机视觉任务和模式识别任务等领域，神经网络以其独特的数据经验优势和其卷积核的领域相关性优势，在交通流预测问题中得到了学界的普遍关注，有大量学者研究并提出了用于交通流预测的循环神经网络及其多种改进版本[3-5]。然而，CNN的计算通常被限定在欧式空间。对于欧式空间以外的非欧式空间数据的处理，传统的CNN就显得乏力。由于非欧式空间下的图结构数据具有很强的数据建模与
表达能力，越来越受到关注，比如，文献[6-8]就提出了基于图数据结构的图卷积神经网络（graph convolutional neural network，GCNN）模型与算法，GCNN模型一经提出就受到了学界和工业界的广泛重视。此外，文献[9]提出了一种能预测结构化数据序列的深度学习模型，即图卷积循环网络（graph convolutional recurrent net-work，GCRN）。该模型结合CNN对图形进行空间结构特征提取，并采用循环神经网络[10]（recurrent neural network，RNN）对时序数据的动态特征进行提取，但是不能很好地拓展到更大尺度的时间预测窗口。进一步地，文献[11]针对交通领域的时间序列预测问题，提出了一种新的时空图卷积网络学习框架，基于图形结构建立了具有完整卷积结构的图神经网络模型，其在较少参数的情况下，能够有效保证训练速度，但是该方法对图的卷积核邻域尺寸的支持不够灵活。文献[12]提出了一种用于时空图建模的新型图神经网络模型，该模型能够准确地捕获数据中隐藏的空间依赖关系。此外，文献[13]将图小波代替图拉普拉斯的特征向量作为基底，通过小波变换和卷积定理定义卷积算子，提出的模型能够实现节点的分类预测，但无法对交通数据的时空特征和动态相关性进行同时建模。
一个时序预测模型与算法不仅要考虑某感兴趣路段的历史观测数据，还需要考虑相邻路网观测对其的累积影响效应。因此，本文提出了基于图小波卷积网络的路网交通流态势预测模型与方法。首先，基于图小波卷积算子，设计了面向路网交通流态势预测的图小波神经网络模块，对交通数据的时空相关性和动态相关性进行建模；其次，通过引入注意力机制构建时空注意力模型，以捕获交通网络上的动态时空相关性；最后，通过叠加多层图小波神经网络模块从交通网络图节点邻域中捕获空间相关性。
1路网交通流态势预测与图小波卷积
1.1路网交通流态势预测
1.1.1交通路网图模型
以城市路网交通流探测传感器i安装位置为节点，以v
i
表示，并且以相邻路段上的传感器j为邻居
节点v
j
，构建交通路网图模型G，定义如下：G=(V,E,A)（1）其中，V表示节点集合，在路网中表示交通流探测传感器集合，且|V|=N。E表示图G中边的集合，元素
e
i=<v i,v j>∈E表示节点v i和节点v j有联结关系。在路网图构建过程中，通常以节点v
i
邻域范围内邻居
of stacking multi-layer graph wavelet neural network modules is adopted to establish a novel graph wavelet neural network for road network traffic flow situation prediction.Experimental results show that the developed model s performance on the experimental datasets is better than the existing baseline models.In the comparative experiment on the non-zero element statistics of the graph wavelet transform matrix and the Fourier transform matrix,it s found that the convolution operation based on the graph wavelet transform is more sparse.Therefore,the convolution operation defined based on the graph wavelet transform is more helpful to improve the calculation efficiency of the traffic flow situation prediction model.
Key words:traffic flow situation prediction;graph convolution;graph wavelet neural network;traffic flow
1085
Journal of Frontiers of Computer Science and Technology 计算机科学与探索2021,15(6)
节点构建边或联结。A ∈R N ×N 为图G 的邻接矩阵。本文构建的交通路网图G 是无向图模型。在图G
中，每个传感节点v i 以相同频率p 采集m 个测量属性值（如车流量和行驶平均速度等），即在每个时间片
t 下每个节点v i 共收集m 维度的特征向量x i ∈R m 。
1.1.2路网交通流预测
交通路网图G 中每个节点以相同的频率进行数据采集，每个节点包含m 维测量属性值，即在时间步t 下图G 中每个节点v i 观测属性值属于m 维特征向量x i
t
∈R m
。对于道路网络图G ，在给定历史观测序列值(x t ,x t -1,⋯,x t -H +1)T
∈R
N ×m ×H
和预测时间窗口F
大小的情况下，交通流态势预测问题定义如下：x t +F ,⋯,x t +2,x t +1=f (x t ,x t -1,⋯,x t -H +1)
（2）
其中，x t ∈R
N ×m
是图G 中全部节点在时间t 下的特
征观测矩阵，x t 每一行代表某节点的特征观测向量
x i t
∈R m
，f 为映射函数，F 为预测窗口长度。
1.2
图小波卷积
（1）图谱卷积
利用多个卷积核对输入数据进行特征提取，各卷积层中每个神经元都与前一层位置临近区域的多个神经元相连接，以捕获空间相关性，卷积操作区域的大小取决于卷积核的尺寸。面向图结构的图谱卷积定义如下：
ζθ∗G x =ζθ(L )x =ζθ(UΛU T )x =U ζθ(Λ)U T x =U ζθU T x （3）
其中，x 表示图G 的节点信号，即x t 。ζθ表示卷积
滤波核。∗G 为卷积操作算符。矩阵L =D -A 是图G 的拉普拉斯矩阵，D ∈R N ×N 是图G 的度矩阵，并且D ii =∑j
A ij 。规范化之后的拉普拉斯矩阵L =I N -D -1/2AD -1/2，I N ∈R N ×N 为单位矩阵。U 是拉普拉斯
矩阵L 进行特征值分解后相应的特征向量矩阵，即L =UΛU T 。Λ∈R N ×N 是由L 特征分解后的特征值对
角矩阵。x =U T x 表示图傅里叶变换，矩阵U 为傅里叶变换基。
（2）图小波卷积
图小波卷积用图小波基替代L 特征值分解后的特征向量基[13]（傅里叶变换基U T ），并通过图小波变换和卷积定理定义图小波卷积算子。基于图小波变换的图小波卷积定义如下：
ζθ∗G x =Ψs ζθΨ-1
s
x
（4）
其中，Ψs =UG s U T =(Ψs 1,Ψs 2,⋯,ΨsN )，s 为扩散尺度因
子，Ψsi 表示以节点i 为中心并以s 为尺度向邻居节点扩散，G s =diag(g (sλi )|i =1:N )∈R N ×N ，
g (sλi )|i =1:N =e sλi
为热扩散核函数[14]，
液压滑环λi 为L 特征分解后特征值。为了计算方便，本文采用Ψ-1s =UG -1s U T ，G -1s =diag(g (-sλi )|i =1:N )∈
R N ×N 。为了不对图G 的拉普拉斯矩阵L 进行特征分
解，本文采用Hammond 等人[15]提出的基于切比雪夫多项式近似算法有效近似Ψs 和Ψ-1s ，从而有效避免了对矩阵L 的特征分解计算，近似求解算法复杂度为Ο(K ×|E |)，K 为多项式阶数，
|E |为图G 的边数。近似算法如下：
Ψ-1
s
τ=12c 0τ+∑k =1
K
c k T ∗k (L )τ
（5）c k =π2∫0π
cos(kβ)g (s (12λmax (cos β+1)))d β
（6）T ∗
k (L )τ=2(2/λmax L -I N )T ∗k -1(L )τ-T ∗k -2(L )τ
（7）
其中，τ为图信号，即x t ，T ∗k (L )表示矩阵L 的K 阶切比雪夫多项式，T ∗0=I N ，T ∗1=2/λmax L -I N 。λmax 为矩阵L 的最大特征值。多项式阶数K 值越大计算越精确，但会带来较高的计算复杂度，通常情况下K 的取值范围为3~10之间。与图谱卷积相比，图小波卷积计算复杂度更低；Ψs 和Ψ-1s 多为稀疏矩阵，运算效率
较高；图小波卷积具有局部特性[16]，扩散尺度因子s 控制着节点的邻域范围。
2图小波神经网络模型
2.1图小波神经网络模型总体结构
时空图小波卷积网络的总体架构如图1所示。时空图小波卷积网络由时空动态相关性捕获模型和时空相关性捕获模型串联组成时空块，再串联堆叠多个时空块，最后接入到一个多层感知机[17]（multilayer perceptron ，MLP ）模型输出层。在时空图小波卷积网络的总体架构中，时空动态相关性捕获模型由空间注意力模型和时间注意力模型组成，空间注意力模型通过引入空间注意力机制捕获空间动态相关依赖特征，空间注意力模型基于注意力机制构造时间注意力矩阵捕获交通流数据的时间
动态相关依赖特征；时空相关性捕获模型由图小波卷积和1维扩张因果卷积组成，图小波卷积用以提取图节点间的空间特征，1维扩张因果卷积用以提取时间维度上各观测值的时间相关性特征。从本质上讲，图小波神经网络是一种多层图谱卷积神经网络，其核心是利用小
1086
姜山等：面向路网交通流态势预测的图神经网络模型
波变换代替傅里叶变换来定义图卷积运算符。
2.2时空动态相关性捕获模型
图小波卷积运算能够捕获节点间的空间相关性
特征，并以此建模图节点间的信息流向和汇集的影响力，但是只能建模有限尺度邻域内节点间的静态依赖特征。在交通网络中，节点间相互影响具有长时空的动态相关性，比如相邻节点在不同时间发生了不同程度的堵车以及不同节点同一时段交通流量状况都有着时空关联性。为了建模节点间的动态相关性，引入注意机制模型[18]分别对时间和空间的动态相关性进行建模，并构建了时空动态相关性模型，对时空动态相关性进行建模。
（1）空间注意力模型
为了建模交通网络图节点间的空间动态相关性，在空间维度上定义空间注意力模型，如下：
Z s =W s ⋅h ((Χl T l
m
W 1)⋅W 2⋅((Χl T l m
)T W 3)+b s )=f Z s
(Χl T l m
)（8）Z s
(i ,j )|i =1:N =exp(Z s (i ,j ))
∑j =1时子环
N exp(Z s
(i ,j ))
（9）
其中，Z s ∈R
N ×N宠物垫
为空间注意力矩阵，Z s
为规范化后的空间注意力矩阵，h 为激活函数（如ReLU （rectified
linear unit ）），Z s
(i ,j )表示图节点i ,j 间的连接强度，通过设定合理的阈值大小可以动态调整空间注意力矩阵。Χl T l
m
={x t ,x t -1,⋯,x t -T
m
+1}l layer ∈R
N ×F l ×T l
m
是网络的第
l 层输入特征信号，T l
m 为第l 层时间序列长度，F l 为
第l 层特征维度；若l 为0，则表示第一层，其对应的输入为Χ0
T 0m
=(x t ,x t -1,⋯,x t -H +1)T
。W 1∈R T l m
，W 2∈R
F l ×T l
m
，
W 3∈R F l
，
W s ∈R N ×N 以及偏置b s ∈R N ×N 待训练学习的参数。
（2）时间注意力模型
为了建模交通网络图节点间的时间动态相关性，在时间维度上定义时间注意力模型，如下：
Z t =W t ∙h (((Χl T l m
)T H 1)∙H 2∙(Χl T l m
H 3)+b t )=f Z t
(Χl T l m
)（10）Z t (i ,j )|j =1:T l
m
=exp(Z t (i ,j ))∑j =1
T
l m exp(Z t
(i ,j ))
（11）弹性钢
催化裂解其中，Z t ∈R
T l m ×T l
m
为时间注意力矩阵，Z t
为规范化后的时间注意力矩阵，同理Z
t
(i ,j )表示图节点i 和节点j 在时间t 时的连接强度。Χl T l
m
∙Z t ={(x t ,x t -1
,⋯,x t -T
m
+1)l layer
∙Z t }∈R N ×F l
×T l
m
可以动态调节和融合不同时间Fig.1Architecture of spatial-temporal graph wavelets convolutional networks
图1
时空图小波卷积网络的总体架构图
1087
Journal of Frontiers of Computer Science and Technology
计算机科学与探索2021,15(6)
步下的信息。H 1∈R N
，H 2∈R F l ×N
，H 3∈R F l
，
W t ∈R T l m ×T l
m
和b t ∈R
T l m ×T l
m
待训练学习的参数。
2.3时序相关性捕获模型
为了能够捕获时序数据间的时间相关性，采用一维扩张因果卷积（dilated causal convolution ，DCC ）提取节点的时间相关特征。在扩张因果卷积网络中，随着层数的增加，接受域（或称感受野）变大，在当前时间步上所做的推论只包含历史信息。假设给定一个输入序列x ∗
∈R H
，则一维扩张因果卷积定义
如下：
x ∗∗D k (t )=∑i =0
K k (i )x ∗(t -id )
（12）
其中，∗D 表示扩张因果卷积操作算符，k ∈R K
为滤波
核，K 表示扩张因果卷积滤波核大小，d 为扩张率（或扩张因子）。通过将扩张因果卷积层与扩张因子按递增顺序叠加，模型的感受野会指数级增长。这使得扩张因果卷积网络能够以较少的层捕获较长的序列，从而有效节省了计算资源。
2.4图小波网络交通流预测算法训练步骤
基于图小波神经网络的交通流预测前向训练步
骤如下：
步骤1给定道路网络图G 和各节点的历史观测数据集，并设定历史时间窗口长度H 和预测时间窗口长度F ，将历史时间窗口H 对应的时序数据作为训练样本{x i }=(x t ,x t -1,⋯,x t -H +1)T
∈R
N ×m ×H
，将预测时
间窗口长度F 对应的时序数据作为训练样本的学习目标{y i }。
步骤2将数据集以6∶2∶2的比例随机分割为训
练集、验证集和测试集（其中，训练集用于模型拟合的数据样本，验证集用于“调优”模型的超参数设置，训练集和验证集数据均参与训练过程，测试集数据仅对训练调优后的模型进行测试验证），并对数据进行零均值归一化处理，以减小尺度因素对样本均衡性的影响，使模型更容易收敛到最优解。此外，在训练过程中对数据集进行了随机Shuffle 操作，以提升模型的泛化性能。
步骤3利用公式Ψ-1
s
τ=12c 0τ+∑k =1
K
c k T ∗k (L )τ计算
Ψs 和Ψ
-
1s
。
步骤4串联堆叠两个时空块（每个时空块由时空动态相关性捕获模型和时空相关性捕获模型串联
组成）构造时空图小波卷积网络模型。输入数据
{x i }∈R N ×m ×H ，计算Z t =f Z t
({x i })时间注意力矩阵，并规范
化为Z t ，计算{x i -t }=Z t ⋅{x i }∈R N ×m ×H ；计算Z s =f Z s
({x i })空间注意力矩阵，并规范化为Z s ，计算{x i -st }=Z s
⋅{x i -t }+{x i }∈R N ×m ×H 。
步骤5利用公式ζθ∗G x =Ψs ζθΨ-1s x 对{x i -
st }进行
空间特征提取运算，利用公式x ∗∗D k (t )=∑i =0
K k (i )x ∗(t -id )
对输入数据进行时间特征提取运算。
步骤6将由多个串联堆叠的时空块进行特征提取后的数据接入到多层感知机MLP [17]中，MLP 将特征进行融合输出，输出结果作为时空图小波卷积网络模型的前向传播输出。
步骤7以均方误差为优化损失函数，采用Adam 一阶优化算法进行梯度反向传播优化，迭代学习得到模型的参数数值。
步骤8基于已经训练得到的最优模型参数，进行路网交通流态势预测，得到预测时间窗口F 内的各节点交通流状态。
3结果与分析
3.1实验环境及数据预处理
（1）实验数据集
选用公开数据集PeMSD-4和PeMSD-8作为时空图小波卷积神经网络模型的验证数据[19]。实验中，将PeMSD-4和PeMSD-8数据聚合为5min 间隔的数据记录。PeMSD-4中记录了某高速公路307个传感器两个月的交通参数，具体包括交通流量、平均速度和平均车道占有量。PeMSD-8中记录了某高速公路170个传感器两个月的交通参数。
（2）实验环境
实验基础硬件平台为：Intel ®Xeon ®Gold 5218********GHz ，NVIDIA GeForce GTX 2080GPU ，显存32GB 。采用Adam 优化器进行优化，学习率为0.0001。为了提升计算效率，将Ψs 和Ψ-1s 中小于阈值0.0001的元素设置为0。训练过程中如果存在连续200个迭代步骤中验证集的损失无明显变化的情况，则表示完成模型训练。
（3）模型评估度量与对照基线
在实验过程中，选用平均绝对误差（mean absolute errors ，MAE ）、平均绝对百分比误差（mean absolute
车载广告1088
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议