冯 宁,郭晟楠,宋 超,朱琪超,万怀宇

1(北京交通大学 计算机与信息技术学院,北京 100044)

2(交通数据分析与挖掘北京市重点实验室(北京交通大学),北京 100044)

智能交通系统(ITS)[1]正在大力发展,交通数据预测问题是其中的重要组成部分.车流量是反映公路运行状态的主要参数之一,如果能够提前准确地对车流量进行预测,事先对车辆进行疏导,可以提高路网的运行能力和效率,减少交通事故,降低人们的出行时间和成本,降低环境污染.

交通流量预测是典型的时空数据预测问题,不同类别的交通数据内嵌于连续空间,并且随时间动态变化,因此,有效提取时空相关性对解决这类问题至关重要.图1所示为流量数据(也可以是车速、车道占用率等其他交通数据)的时空相关性示意图,时间维包含 3个时间片,空间维的 6个节点(A～F)表示公路的网状结构.在空间维上,节点的交通状况之间会相互影响(绿色虚线);时间维上,某节点历史不同时刻流量会对该节点未来不同时刻流量产生影响(蓝色虚线);同时,节点历史不同时刻的流量值也会对其关联节点未来不同时刻的流量产生影响(红色虚线).可见,交通流量在时空维度都存在很强的相关性.而如何从这些复杂、非线性的时空数据中挖掘出隐含的时空模式,并对这些模式进行分析从而提取出有价值的信息,是时空数据挖掘任务的一项极大挑战.

Fig.1 Spatio-Temporal correlation of traffic flow data图1 交通流量数据的时空相关性

随着交通行业的发展,道路上部署了许多摄像头、传感器等信息采集设备,这些设备拥有独特的地理空间位置,不断采集各类交通数据,如流量、车速、车道占用率等,积累了大量丰富的带有地理信息的交通时间序列数据,为流量预测提供了很好的数据基础.目前,已有很多学者在这类问题上进行了大量尝试.早期的时间序列预测模型只能用于数据相对稳定、呈线性变化的预测问题,很难适应实际需求.随后发展起来的传统机器学习方法虽然能对更复杂的数据进行建模,但仍然很难同时考虑交通数据的时空相关性,而且这类方法的预测效果很大程度上依赖于特征工程,这往往需要依赖领域专家的经验和大量的实验.近年来,很多人将深度学习的方法应用于时空数据预测问题,如利用卷积神经网络(CNN)可以有效提取网格数据的空间特征,但对于图结构的时空数据的特征描述和时空相关性分析,目前仍然还在探索之中.

为了应对上述挑战,我们提出了一种基于深度学习的交通流量预测方法——多组件时空图卷积网络(MCSTGCN)模型,使用基于时空卷积网络的深度学习模型来处理交通路网这类图结构数据,能够同时有效捕获数据的时空特性.该模型分别设置近期、日周期和周周期等 3个组件来描述交通数据的时空特征,最后将 3个组件的输出进行融合得到最终的预测结果.本文的主要贡献概括如下:

· 同时考虑并建模了交通流量数据固有的3种时间维特性,即近期依赖、日周期性和周周期性,并利用3个学习组件分别建模这3种特性;

· 提出了MCSTGCN模型,能够直接从基于图结构的交通数据中同时有效捕获空间和时间维特征;

· 在真实的高速公路流量数据集上进行实验,验证本文提出模型的预测效果优于其他现有的预测方法.

1 相关工作

交通量预测问题历经多年的不断研究和实践,取得了大量的成果.传统的统计学方法有历史均值法、自回归积分滑动平均法(ARIMA)[2]等.历史均值法是以历史一段时间数据的均值为依据进行预测,ARIMA将预测对象随时间推移而形成的数据序列视为一个随机序列,用一定的数学模型近似描述这个序列.这类方法对复杂非线性的交通数据处理能力不足,因为它们都要求数据满足一些前提假设,但实际中的数据往往很难满足这些假设.K近邻、支持向量机等机器学习方法能对更复杂的数据进行建模.采用K近邻方法的思想是识别相似的交通状况用于预测[3],而采用支持向量机方法的思想是通过核函数将低维非线性流量数据映射到高维空间后再进行线性分类[4].这类方法仍然无法同时有效考虑交通数据的时空相关性,且需要大量的特征工程.随着深度学习在语音识别、图像处理等领域取得的成果,越来越多的人将深度学习应用于时空数据预测问题.Zhang等人[5]设计了基于残差卷积单元的ST-ResNet来对城市人流量进行预测,这种方法虽然提取了流量数据的时空特征,但将输入限制为标准的2维或3维网格数据,因而不能用于图结构的高速路网上的交通预测问题.

传统的卷积神经网络可以有效提取数据的局部特征,但只能作用于标准的网格数据.而图卷积可以直接在图结构的数据上实现卷积操作.目前,主流的图卷积方法包括空间方法和谱图方法.空间方法直接把卷积核应用到图上的节点及其邻域,这种方法的核心在于如何选择节点的邻域.Niepert等人[6]为中心节点启发式线性选择邻域,将其映射为向量再进行卷积,在社交网络任务中取得了不错的效果;Li等人[7]在人体动作识别任务中引入图卷积,提出多种划分策略将节点的邻域划分为不同子集,通过控制子集的个数,保证不同节点可以共享卷积核权重.谱图方法通过图拉普拉斯矩阵将网格数据上的卷积操作推广到图结构数据上.Bruna等人[8]提出了一个通用的图卷积框架,将拉普拉斯矩阵的特征向量变换到谱域,再通过样条插值的方法近似求解;随后, Defferrard等人[9]优化了该方法,将样条插值替换成切比雪夫多项式的K阶截断近似求解,并证明了卷积核的范围严格限制在中心节点的K阶邻居内,同时降低了模型复杂度;Seo等人[10]提出了图卷积循环网络(GCRN),但在特定设置下很难确定循环网络和图卷积的最佳组合;随后,Li等人[11]成功地使用门控循环单元(GRU)和图卷积进行长期交通预测;Yu等人[12]提出了一个带有门控机制的图卷积网络,并应用于交通量预测问题.但这些模型都没有考虑交通数据在时间维度上的周期性和趋势性等多种固有特性.

交通流量预测问题的核心在于如何有效捕获数据的时空维特征及相关性.图卷积可以直接对图结构数据进行特征提取,自动挖掘交通数据的空间模式.沿时间轴做卷积操作,可以挖掘交通数据的时间模式.因此,本文采用基于时空图卷积网络的深度学习模型,将二者结合起来同时捕获交通数据的时空特性,有效解决交通流量预测问题.

2 问题定义

2.1 空间路网

我们将空间路网定义为无向图G=(V,E,A),如图2(a)所示,其中,V为节点集,|V|=N为节点个数;E为边集,表示节点间的连通性;A∈ℝN×N为图G的邻接矩阵.设在空间路网G上的每个节点都会检测F个采样频率一致的时间序列数据,即每个节点在每个时间戳都会产生一个长度为F的特征向量,如图2(b)(数据归一化后的示意图)实线所示.

Fig.2图2

2.2 流量预测

设路网G中各节点的第f∈(1,…,F)个时间序列为流量序列,未来某一段时间范围内的流量为我们的预测目标.用表示第i个节点的第c维时间序列在t时刻的值,表示所有节点的第c维时间序列在t时刻的值,表示所有节点的第c维时间序列在τ时段内的值,表示所有节点的所有时间序列在t时刻的值,表示所有节点的所有时间序列在τ时段内的值.设是第i个节点在t时刻的流量值,已知路网上所有节点的历史τ时段内的所有时间序列值X,我们的预测目标是未来所有节点在窗口长度为Tp的流量序列,其中,表示节点i的预测目标,如图2(b)中的蓝色虚线所示.表1列出了本文的符号约定.

Table 1 Mathematical notation表1 符号约定

3 基于深度学习的多组件时空图卷积网络

图3展示了本文提出的多组件时空图卷积(MCSTGCN)网络的总体架构,它由3个主要部分组成,分别用来建模预测目标的近期、日周期及周周期信息(GCN:空间维图卷积;Conv:时间维卷积;FC:全连接).例如,对某地下午2点的车流量进行预测,那么与预测时段直接相邻的历史1小时内的交通数据、对应的1天前及1周前下午2点的交通数据都会对该预测问题提供有用信息,而当天上午9点的交通状况往往与预测目标关系不大.为了得到充足的时间维信息,同时减少处理不相关历史信息带来的开销,我们设计了 3个组件分别用于描述交通数据的3种时间维特性:近期特性、日周期特性及周周期特性.

Fig.3 Architecture of MCSTGCN图3 MCSTGCN模型架构图

假设采样频率为每天q次,即时间序列上每天包含q个数据点.设当前时刻t0,待预测的时间窗口长度为Tp,我们沿时间轴分别截取长度为Th,Td和Tw的3个时间序列片段作为模型中近期、日周期和周周期3个组件的输入,如图4所示(设预测时段长度Tp为 1小时,Th,Td和Tw均取Tp的 2倍),其中,Th,Td和Tw均为Tp的整数倍.3个时间序列片段分别如下.

Fig.4 An example of constructing the input of time series segments图4 输入时间序列片段构建示例

3个组件共享相同的网络结构,由时空卷积模块(如图5所示)和全连接层组成,其中,时空卷积模块包括空间维度的图卷积和时间维度的标准 2维卷积两部分.模型最后将 3个组件的输出结果基于参数矩阵进行融合,得到最终的预测结果.这种结构能够有效捕获交通数据的时间维和空间维特征及其时空相关性.

Fig.5 Architecture of spatio-temporal convolutions of MCSTGCN图5 MCSTGCN模型的时空卷积结构

3.1 空间维图卷积

我们首先只考虑某一时间片上的空间图G,以了解空间特征的建模过程.在我们的模型中,采用谱图方法[9]将卷积操作推广到图结构数据,将数据视为图上的信号,然后直接在图上对图信号进行处理,来捕获空间中有意义的模式和特征.

谱图方法主要通过将图转化为代数的形式来分析图结构,在本文中,我们主要关心图结构中节点间的连通关系及相互影响,在谱图论中,可以将一个图用其对应的拉普拉斯矩阵来表示.通过分析拉普拉斯矩阵及其特征值就可以得到图结构的性质.图的拉普拉斯矩阵定义为L=D-A,其规范化形式为,其中,A为邻接矩阵,IN为单位阵,度矩阵是节点度数组成的对角矩阵,.对拉普拉斯矩阵进行特征值分解L=UΛUT,其中,是L的特征值组成的对角矩阵,U是傅里叶基[12].以t时刻流量数据为例,图信号为,对图信号进行傅里叶变换可表示为.根据拉普拉斯矩阵的性质可知U是正交矩阵,因此得到逆傅里叶变换.图卷积是利用定义在傅里叶域中对角化的线性算子来等价代替经典卷积算子[13]实现的卷积操作,用卷积核gθ对图G进行卷积操作[9]:

由于对图信号进行卷积操作再做傅里叶变换等于对这些信号进行傅里叶变换后的乘积[14],上式可以理解为对gθ和x分别做傅里叶变换到谱域,然后对二者的变换结果进行乘法操作,再做傅立叶逆变换得到卷积操作的结果.

将图变换到谱域实现图上的卷积操作即为图卷积,但当图的规模较大时,直接对拉普拉斯矩阵进行特征值分解代价昂贵,因此,本文采用切比雪夫多项式近似展开求解:

θk∈ℝK为切比雪夫多项式系数,表示拉普拉斯矩阵的最大特征值.切比雪夫多项式的递归定义:Tk(x)=2xTk-1(x)-Tk-2(x),其中,T0(x)=1,T1(x)=x.用切比雪夫多项式近似展开求解,相当于对图中的每个节点采用卷积核提取了以该节点为中心的周围 0～K-1阶邻居的信息[9].图卷积模块使用线性修正单元(ReLU)为激活函数,即ReLU(gθ×Gx).

以K=2为例,对每个节点提取其0～1阶邻居信息,对拉普拉斯矩阵特征值进行缩放使λmax=2,上述图卷积操作表示为

令θ0=-θ1=θ∈ℝ以减少参数,则,图上所有节点共享卷积核权重θ.同时,为避免数值不稳定、梯度爆炸或梯度消失[15],我们令,得到:.拓展到多维数据,第r层卷积的输入数据是,其中:r∈{1,…,l}(l是时空卷积层数);Cr-1是第r层网络的输入数据的通道数,当r=1时,是输入数据时间维长度,当r=1时,近期组件T0=Th(日周期组件T0=Td、周周期组件T0=Tw).对进行图卷积操作,表示为,其中,是卷积核参数.

以Cr-1=1为例,图6展示了图卷积过程中对空间节点的0～1阶邻居信息进行提取的过程.图6(a)为空间路网结构,图6(b)为根据图6(a)计算得到邻接矩阵A和度矩阵及输入数据的矩阵表示如图6(c)所示,由此计算出用卷积核对数据进行图卷积操作的结果如图6(d)所示,其中,节点F在t=2时刻的值由原来的变为,即,输入数据被其0～1阶邻居的信息更新.其他特征及卷积核同理,对整个输入数据进行一次图卷积操作,得到,每个节点被该节点的 0～K-1阶邻居的信息更新.

Fig.6 An example of graph convolutions and its matrix representation图6 图卷积示例及其矩阵表示

3.2 时间维卷积

通过空间维图卷积操作对输入数据的空间特征进行建模之后,再用标准 2维卷积捕获时间维特征.我们用线性修正单元激活函数,以提取近期特征为例,得到(Ψ为时间维卷积核的参数),具体卷积过程如图5所示.

经过一层时间维卷积之后,节点的信息被该节点相邻时间片信息更新,而节点及其相邻时间片信息在经过图卷积操作后已包含其相邻节点同时刻的信息.因此,通过一层时空卷积操作之后,就会捕获到数据的时间维和空间维特征以及时空相关性.我们使用多层时空卷积,以提取时空维上更远的信息,再通过全连接操作使时空卷积的结果与预测目标维数一致,全连接模块同样使用线性修正单元作为激活函数.

3.3 多组件融合

在本节中,我们将讨论如何融合近期、日周期和周周期组件的输出.以对整个路网周五上午 8点的流量进行预测为例,有些地方早晚高峰周期规律明显,其日周期、周周期组件的预测结果更为重要;而有些地方不存在明显的交通周期规律,日周期、周周期组件对预测目标起到的帮助较小.可见,不同节点受不同组件的影响程度是不一样的,在融合不同组件的输出结果时,其影响程度也应该不同.因此,应该从历史数据中进行学习.融合后的最终预测结果表示为

其中,⊙是矩阵对应元素相乘的哈达马积;Wh,Wd,Ww是学习参数,反映了近期、日周期、周周期这3种时间维特性对预测目标的影响程度.

4 实验与结果分析

为了检验本文提出模型的性能,我们在两个真实世界的数据集上进行了对比实验.本节将对数据集和实验设置进行说明,并对实验结果进行详细的对比分析.

4.1 数据集介绍

我们使用美国加利福尼亚州的真实高速公路数据集 PeMSD4和 PeMSD8来验证我们的模型.PeMS是由Caltrans Performance Measurement System实时采集的高速公路交通数据,该系统拥有超过39 000个传感器站,部署在加利福尼亚州高速公路系统的主要大都市区[16].数据集是基于 30s/次的频率采样得到的原始数据汇总成的以5m为时间间隔的样本.数据集包含带时间戳的车流量、平均车速、平均车道占用率这3个维度的特征及采集这些信息的检测器的地理位置信息.

· PeMSD4:San Francisco Bay区域的数据,共包含29条路上的3 848个检测器,我们选取时间范围为2018年1月～2月的数据进行实验,其中,前50天作为训练集,后9天作为测试集;

· PeMSD8:San Bernardino区域的数据,共包含8条路上的1 979个检测器,我们选取时间范围为2016年7月～8月的数据进行实验,其中,前50天作为训练集,后12天作为测试集.

4.2 数据预处理

我们对道路上的检测器进行筛选,去掉那些距离过近的检测器,保证检测器节点间距离大于 3.5英里.样本以5m为时间间隔,因此,道路上每个节点每天包含288个数据点.用线性插值法填充缺失值.另外,对数据进行0均值标准化(zero-mean)操作x′=x-mean(x),即让数据的平均值为0.

4.3 实验参数设置

我们基于Pytorch框架实现了MCSTGCN模型,图卷积使用32个相同大小的卷积核.时间维卷积同样使用32个相同大小的卷积核,这些卷积核沿空间轴维度为1,沿时间轴维度为3,通过控制步长调整时间维长度.整个模型训练时间大约为20s/轮.3个组件的输入数据长度会对实验结果产生影响,我们通过实验选定Th=3,Td=1和Tw=1为最佳的组合.均方误差是反映估计量与被估计量之间差异程度的一种度量,因此,本文采用该度量指标作为损失函数.

4.4 基准方法

我们将本文提出的模型与以下7种已有的时间序列预测方法进行比较.

· HA:历史均值法,其预测值为近期历史流量状况的平均值.在本文中,我们使用最近12个时间片的平均值来预测下一个时间片的值;

· ARIMA[2]:自回归积分滑动平均法,是时间序列分析中的一种经典方法;

· LSTM[17]:长短期记忆网络,一种特殊的RNN模型.LSTM单元由细胞、输入门、输出门和遗忘门组成;

· GRU[18]:门控循环单元网络[18],一种特殊的RNN;

· STGCN[7]:一种基于空间方法定义的时空图卷积模型,采用了多种划分策略将中心节点的邻居划分到不同子集,实现卷积核的参数共享;

· GCGRU[11]:一种将门控循环单元网络与图卷积网络结合的方法;

· GLU-STGCN[12]:一种带有门控机制的图卷积网络,在交通数据预测问题上取得了很好的效果.

本文采用均方误差(RMSE)和平均绝对误差(MAE)作为评价指标,具体计算公式下:

4.5 实验结果及分析

我们将MCSTGCN模型在数据集PeMSD4和PeMSD8上与前述7种基准方法进行了比较,表2展示了对未来1h内的流量进行预测的结果.

Table 2 Performance comparison of different approaches on the PeMSD4 and PeMSD8 dataset表2 不同方法在数据集PeMSD4和PeMSD8上的性能比较

从表2可以看出,我们的模型在两种评价指标中均达到最佳性能.我们还可以观察到,传统的时间序列预测方法由于建模能力有限,预测结果并不理想.基于深度学习的方法获得了比传统方法更好的预测结果,而包含时空图卷积机制的模型由于考虑了时空依赖性,预测结果要优于一般的深度学习模型.

此外,我们还比较了各种方法随着预测时长的增长性能变化情况.我们以5m为间隔,让预测时长从5m增长到1h,实验结果如图7所示.

Fig.7 Performance changes of different methods along with the forecasting duration图7 不同方法随着预测时长的性能变化情况

从图7可以看出,从整体上,随着预测时长的逐步增大,预测难度越来越大,误差整体呈上升趋势.我们的MCSTGCN模型在短期预测中就取得了较优的的预测结果,这表明了多组件与时空图卷积结合的策略能充分挖掘数据的时空模式;而随着预测时长的增大,我们的模型预测误差比其他方法增长更加缓慢,这是由于该模型显式建模了时间维度上的多种周期特性,因而在中长期预测中显示更加明显的优势.

最后,为了观察每个组件的输入数据的长度变化对预测结果的影响,我们在 PeMSD8数据集上将各组件的输入数据长度分别设置为Th∈{1,2,3},Td∈{1,2,3},Tw∈{1,2,3}进行了实验对比,其结果见表3.

Table 3 MAE with different component input lengths on dataset PeMSD8表3 不同组件输入数据长度在数据集PeMSD8上的MAE

可以看出,Th的变化对预测结果影响较大,而Td和Tw影响相对较小.我们选定Th=3,Td=1和Tw=1为最佳的组合.

5 总 结

本文提出一种新颖的多组件时空图卷积网络 MCSTGCN,该模型结合图卷积和标准卷积构造时空卷积块来同时捕获交通数据的时空特性.在真实的高速公路流量数据集上的实验表明,本文提出的模型的预测效果优于其他已有的交通数据预测方法,验证了该模型在捕获时空特征及时空相关性方面具有优势.事实上,除了高速公路流量预测任务外,我们提出的模型也适用于处理其他基于图结构表示的时空交通数据.未来,我们将进一步通过注意力机制等策略来优化模型的网络结构,进一步提升模型的预测能力.