基于时空图卷积网络的交通事故预测研究

刘 志,王锦梦,孔祥杰

(浙江工业大学 计算机科学与技术学院,浙江 杭州 310023)

随着智能交通技术的深入发展,大数据时代背景下针对交通事故的研究方法[1-2]已经越来越多,其中针对交通事故预测[3-4]的研究是交通安全领域的一个重大挑战,其对于减少交通路网中的事故发生,降低交通事故发生的影响程度有着重要作用,同时也可以为应急人员准确预测与评估事故严重影响程度,快速分析事故潜在或后续影响,并能向事故管理程序提供重要信息,对及时实施有效的医疗救助和运输有重要作用,是交通事故管理的重要环节。近年来,针对交通事故预测的研究,已经有大批学者研究发表了许多相关研究成果的论文,但众多实验研究结果表明:交通事故预测具有复杂的时空依赖性,一直是一项不断需求突破的挑战性预测,其复杂性表现在:1) 时间依赖性,交通状态会随着时间动态变化,主要体现在周期性和趋势性上;2) 空间依赖性,交通状态受路网拓扑结构的限制,相邻路段之间具有强烈影响。传统的预测方法有卡尔曼滤波模型[5]、支持向量回归机模型[6]、贝叶斯模型[7]和神经网络模型[8]等。上述方法虽然考虑到了交通数据的时间依赖性,却忽略了空间依赖性的存在,使得路网状态无法有效限制交通变化情况,导致实验预测效果不够准确。为了更好地描述空间特征,一些研究[9-11]采用基于卷积神经网络的模型方法对事故严重程度预测问题进行实验分析,然而,卷积神经网络通常用于欧式空间[12]如图像、规则网格等,在构建路网的复杂拓扑结构上无法准确学习空间相关性,因此在本质上不能描述空间依赖性。

为解决上述问题,笔者提出一种新的基于时空图卷积网络的交通事故预测模型(Traffic accident prediction model based on spatio-temporal graph convolutional network,简称STAP模型)。该模型主要结合长短期记忆网络和图卷积网络,分别获取实际交通路网空间信息的特征提取和时序信息的特征提取。在模型中充分考虑了时间、天气和兴趣点等交通信息数据,并采用区域划分的方法构建了路网的拓扑结构;通过实际数据对事故预测效果实验进行评估,与其他基线模型进行预测性能比较,STAP模型在交通事故预测中具有优越性。

1 相关工作

近年来,针对交通事故预测问题的相关研究和应用[13-14]已经有很多,根据近年来相关的主要文献,可将现有的方法分为两类:统计学习方法和机器学习方法。

1.1 统计学习方法

统计学习方法在交通事故预测中得到了广泛应用,大多数回归模型在自变量和因变量之间有假设和预定义的基本关系,其中多项式Logit[15]是应用最广泛的离散选择模型,利用多项式Logit分析可以计算出一个未知严重程度交通事故的每个等级严重程度的发生概率。Zong等[16]将贝叶斯网络和Logistic回归模型应用于交通事故预测研究,并利用这两种方法对3个事故评估指标进行分析,确定了其主要影响因素及影响结果,结果表明贝叶斯网络的拟合度高于Logistic回归模型。Chen等[17]从驾驶员伤害严重程度的角度,考虑到参数效应中可能存在未观察到的异质性问题,建立了一个随机参数二元有序Probit模型来检验影响两名驾驶员在同一次追尾事故中受伤的因素,为今后工作中处理类似的伤害严重程度分析提供了方法。Lee等[18]以韩国首尔市的交通事故为例,定义4个潜在变量,提出了一种统计拟合优度指标,其实验结果揭示了雨和水深以及其他因素在确定事故严重程度方面的作用。K近邻模型[19]分别对应于基于训练数据集对特征空间的一个划分,此外,马尔可夫过程[20]虽然是一种随机性较强的方法,但在该研究领域中也取得了不错的预测效果。Li等[21]通过实验比较了两个统计模型之间的性能,结果表明:在交通事故预测效果上,相较于有序概率模型,支持向量机模型表现出了更优的性能。Hashmienejad等[22]根据用户的偏好进行预测,定制了一种多目标遗传算法,并提出一种新的事故严重度预测模型替代了传统的决策树,结果表明该方法在分类精度、规则支持度和置信度等性能指标上均有更好的表现。

1.2 机器学习方法

针对某一个具体研究问题,机器学习就是通过筛选问题模型,使机器按照一定的规则对一批数据进行识别分类或回归,从而得到期望的结果,在交通事故预测领域有着广泛的应用。Sameen等[23]基于递归神经网络建立了深度学习模型来预测交通事故,通过选定的网络体系结构优化预测精度,其实验结果表明该模型的预测性能较优。Kunt等[24]采用遗传算法、模式搜索和人工神经网络,使用多层感知器结构,对高速公路交通事故分别进行了预测,结果表明人工神经网络表现出了更佳的性能。Zheng等[25]基于交通事故特征的权重,设计特征矩阵转化为灰度图像的算法,提出了一种新的交通事故预测卷积神经网络模型,其实验结果表明该模型具有较好的预测性能。Han等[26]引入一种新型的图特征提取方法,并据此定义图傅里叶变换,提出了一种基于机器学习的框架,实验结果表明该框架具有更优的预测性能。

上述方法均只考虑了时间特征,忽略了空间依赖性,使得事故数据的变化脱离了路网拓扑结构的限制,从而无法准确地对交通事故进行预测。充分利用时空特征是推进交通事故预测研究问题的关键,为了获得更好的空间关系特征,学者们在这一领域进行了深入研究和改进。Xia等[27]结合长短期记忆网络和卷积神经网络,设计了一种用于短期预测的特征融合体系结构,在获得空间特性的同时考虑时间特征短期变异性和周期性,对交通数据进行了预测。Yu等[28]提出了一种新的深时空图卷积网络预测交通事故模型,该模型由空间学习层、时空学习层和嵌入层等3个部分组成,实验结果表明该模型的性能优于经典方法。上述实验研究表明:卷积神经网络虽然对空间关系进行了依赖建模,但在本质上对复杂的路网结构不具有空间依赖的表征,存在难以解决的局限性缺陷。近年来,随着图卷积神经网络在各领域的空间依赖研究应用[29-31]中都表现出了良好的实验效果,又考虑到时间依赖和空间依赖上的复杂关系,时空图卷积的方法应运而生。

因此,在此背景下,笔者结合长短期记忆网络和图卷积网络,提出一种新的基于时空图卷积网络的方法,可以有效地从交通事故数据中获得复杂的时空特征,并用于交通事故预测的研究任务。

2 基于时空图卷积网络的交通事故预测

基于时空图卷积网络的交通事故预测建立在数据的时空依赖关系之上,其中,通过建立路网的拓扑结构表示事故预测的空间依赖关系,通过时间序列数据表示事故预测的时间依赖关系,即空间依赖代表的是交通路网中的空间特征提取,时间依赖代表的是交通数据中的时间特征提取。

2.1 问题定义

交通事故预测[32-34]的目的是根据一系列的历史信息数据预测未来一段时间内的交通状态是否会发生某种程度的碰撞,其中一系列的历史信息数据包括交通事件(例如拥堵、施工和道路危险等)、时间、天气和兴趣点,因此,交通事故预测任务主要是基于历史交通事故状态的相关因素来预测未来的交通事故状态。

定义1路网G:使用G=(V,E)来表示区域之间的连接关系,将每个划分区域视为一个节点。V={v1,v2,…,vn}表示一组区域节点的集合,其中n代表的是区域数量;E={e1,e2,…,em}表示两个区域之间连通性的边的集合,其中m代表的是边数量。邻接矩阵A则表示路网之中的连通性,当G为一个非加权的路网时,A∈Rn×n是一个由0和1组成的矩阵,其中1表示相应的区域连接,反之则为0。

定义2特征矩阵Xn×P:将一系列的历史交通信息作为路网节点的属性特征,表示为X∈Rn×P,其中P代表的是节点属性特征的数量。

因此,时空交通事故预测问题可以表示为在路网G和特征矩阵X定义下的学习映射函数,用以求解计算下一个时间序列内的交通事故状态,其计算式为

[Xt+1,Xt+2,…,Xt+T]=f(G,(Xt-i,…,Xt-1,Xt))

(1)

式中:i为历史时间序列的长度;T为预测的时间序列长度。

2.2 STAP模型框架

将研究问题分为时间预测部分和空间预测两部分,即首先在图卷积网络[29]的架构下实现对空间纬度上的数据空间特征处理,其次在长短期记忆网络[35]上实现对时序纬度上的数据时间特征处理。如图1所示,首先,对数据进行处理,并将处理过后的交通时序数据作为输入,利用图卷积网络提取路网区域的空间特征;其次,将得到的具有空间特征的时间序列输入长短期记忆网络以提取时间特征;最后,采用全连接层运算输出结果。

图1 方法总体框架Fig.1 Overall framework of the method

2.3 STAP模型构建

构建基于时空图卷积网络的交通事故预测模型共包含4个部分。

2.3.1 空间依赖建模

交通事故预测中的关键问题之一就是获得复杂的空间特征。通常来说,路网不是用二维网格的形式表示,而是以图形的形式呈现。传统的卷积神经网络只能用于欧式空间,不能全局地反应出交通路网的复杂拓扑结构,即意味着该网络模型不能准确地获得交通事故的空间特征。而基于传统卷积算法在图结构数据上设计出的图卷积网络(Graph covolutional networks,GCN)[36]可以直接用于处理图结构数据。近年来,GCN模型已经被成功地应用于许多研究领域之中,并得到了广泛的关注。给定一个邻接矩阵A和特征矩阵X,具有分层传播规则的多层图卷积网络GCN可以表示为

(2)

邻接矩阵A表示交通路网中区域之间的空间依赖性。根据图结构的表示方法,将交通路网的拓扑结构抽象为由n个节点和m条边组成的图结构G=(V,E),其中V表示每个地理区域节点的集合,E表示各个区域之间连通性的边的集合,区域之间的连通性则可表示为对应的邻接关系:

(3)

(4)

式中K为空间权值矩阵的最高阶数。

特征矩阵X表示基于交通时间序列数据的时间依赖性。将交通事故数据预测问题描述为:在时间t=15 min的时间间隔内,使用时间、天气和兴趣点等数据为每一个地理区域r计算特征向量表示,并确定该地理区域的事故标签值,利用前8个时间间隔的向量预测下一个时间间隔向量的事故标签值。笔者使用两层的GCN来获得空间特征,其模型结构图如图2所示。

图2 两层GCN模型结构图Fig.2 The image of two-layer GCN model structure diagram

通过使用GCN模型从交通事故数据中获得空间特征,可以得到路网区域之间的拓扑关系,并对路网拓扑结构和属性特征进行编码,进而得到空间依赖性,表示为

(5)

式中:ReLU为线性整流函数;W(0)为第一层的权值矩阵,用于将节点的特征表示映射为相应的隐层状态;W(1)为第二层的权值矩阵,用于将节点的隐层表示映射为相应的输出;softmax为激活函数。

2.3.2 时间依赖建模

交通事故预测中的另一个关键问题是获得时间特征。目前,传统应用于时间序列数据处理的神经网络模型是循环神经网络,但是该模型存在梯度消失和梯度爆炸等缺陷,对长期预测任务具有一定的局限性。因此,长短期记忆神经网络(Long short term memory networks,LSTM)[37]作为循环神经网络的一种变体,能够学习长时间的依赖关系,避免了训练过程中可能出现的梯度爆炸和梯度消失的问题,并使用门控机制来记忆尽可能多的长时间记忆,其结构示意图如图3所示。图3中:ht-1表示上一时刻的隐藏层输出;Xt表示当前时刻的输入;Ct-1表示上一时刻的状态值;Ct表示当前时刻的状态值;ht表示当前时刻的隐藏层输出。相较于传统的循环神经网络,LSTM的结构更为复杂,为了使内部的影响和状态变得可控引入了门控思想,并且比只包含门控循环单元的结构更为复杂,其主要有3个核心控制结构:输入门、输出门和遗忘门。

图3 LSTM结构示意图Fig.3 The image of LSTM structure diagram

2.3.3 时空图卷积网络

为了同时从交通数据中获得时间依赖和空间依赖,笔者提出一种基于长短期记忆网络和图卷积神经网络的时间图卷积网络,如图4所示。图4中:STAP模型的每个单元都由两个组织结构构成,在保持长短期记忆网络门结构和隐藏状态不变的基础上,使得其输入将由图卷积特性来取代,然后采用全连接层运算输出结果。因此,结合2.3.1,2.3.2,该模型在时间t上的具体计算过程为

ft=σ(Wf·[ht-1,f(A,Xt)]+bf)

(6)

it=σ(Wi·[ht-1,f(A,Xt)]+bi)

(7)

(8)

ot=σ(Wo·[ht-1,f(A,Xt)]+bo)

(9)

式中:f(A,Xt)为图卷积过程,由式(5)给出定义;W,b分别为训练过程中的权重和偏差。考虑到输入信息前向传播和误差反向传播之间的信息传递,以及相邻记忆单元之间的状态影响,可计算出最终的隐藏层输出ht和单元状态Ct分别为

ht=ot×tanh(Ct)

(10)

(11)

图4 STAP结构示意图Fig.4 The image of STAP structure diagram

对于给定地区的交通事故数据集示例,可以将其视为一个N×M的矩阵,其中N表示该地区被划分后区域数,M表示的是历史交通事故信息的数量。首先,通过使用大小为m补偿为s的划动窗口获得k段历史信息序列构建特征矩阵,其中1

2.3.4 损失函数

在实验训练过程中,模型预测的目标是使交通事故预测结果尽可能地接近实际交通事故状态,即损失函数的目的是最小化两者之间的误差,因此,STAP模型的损失函数可表示为

(12)

3 实 验

3.1 数据描述

实验使用真实数据集来评估STAP模型的交通事故预测性能:该数据集由Sobhan等[2]和Moosavi等[38]收集处理,部分数据示例如表1所示。将预测范围在地理位置上划分为大小为l×l的多个区域r表示,并设置l=5 km,在时间间隔t=5 min内每个地理区域r创建了一个特征向量表示,向量包含交通、时间、天气、兴趣点和区域描述。

表1 2018年12月1日部分数据示例Table 1 Example of partial data on Dec.1,2018

数据集最终以每个城市为单位,在每个城市范围之内,通过将预测范围在地理位置上划分为特定大小的多个地理区域r构建数据的空间依赖,所有地理区域构成一张城市路网G=(V,E),其中V表示每个地理区域节点的集合,E表示各个区域之间连通性的边的集合,若存在道路使得两个区域之间连通,则邻接矩阵A中对应的值为1,反之,则为0。同时,为每个地理区域构建数据的时间依赖,由于每一起交通事故的数据是离散的,因此以每个地理区域为单位,以t为时间间隔构建时间序列关系,使用时间、天气和兴趣点等数据创建区域r的特征向量表示,构成特征矩阵X,其中每个地理区域的交通事故状态作为区域r的标签,若是未发生事故则为0。因此,实验中交通事故预测的本质就是预测区域r中未来时间间隔t中的交通事故状态标签。其中,事故字段表示在时间点的约15 min间隔内发生交通事故的状态,纬度字段和经度字段表示事故发生的地理位置,街道号码字段表示事故发生街道的地址编号,温度字段和能见度字段表示事故发生的部分天气状态信息,减速带字段表示兴趣点信息之一,代表事故发生周围是否有减速带设施存在。每一条地理区域特征向量表示的数据由24个时变性维度和113个非时变性维度的多属性向量组成,在t=15 min的时间间隔内,各向量字段的具体含义如表2所示。

表2 区域数据字段含义Table 2 Field meaning of regional data

3.2 参数设置

模型的超参数包括网络结构参数和学习算法参数,通过学习获得的最终优化超参数为:时空图卷积按网络学习速率为10-3;卷积块个数为5个;图卷积输出特征维度为1;长短期记忆网络输出特征维度为16;全连接神经网络输出维度为10;训练学习次数为2 500。基于时空图卷积网络的交通事故预测模型中的神经网络模型采用图卷积神经网络模型和长短期记忆网络模型相结合。该网络先经过一层图卷积神经网络,捕获数据的空间特性,在经过3层的长短期记忆网络,捕获数据的时间特性,最后经过一层全连接层。图卷积神经网络的输入维度为315,输出维度为1。长短期记忆网络有3层,总共含有3个神经元,每层的输入维度为5,隐藏节点个数为16,输出最后一层所选取的有效输出维度为16。全连接层包含16个神经元,输入维度为16,输出维度为10。

3.3 评价指标

在实验预测效果的对比中,使用了3个评价指标来度量不同模型对交通事故的预测与评估性能,包括均方根误差、平均绝对误差和准确度。具体而言,均方根误差和平均绝对误差用于度量模型的预测误差,若数值越小,则表示该模型预测效果越好;准确度用于度量模型的预测精度,若数值越大,则表示该模型预测效果越好。

1) 均方根误差RMSE为

(13)

2) 平均绝对误差MAE为

(14)

3) 准确度Accuracy为

(15)

式中:xk为真实值;yk为预测值;X,Y分别为xk和yk的集合;N为样本数。

3.4 基线模型

将STAP模型的预测性能与4种基线方法进行比较,这4种基线方法包括:1) 支持向量机(Support vector machines,SVM)[39];2) 深度神经网络(Deep neural networks,DNN)[40];3) 长短期记忆网络(LSTM)[25];4) 图卷积网络(GCN)[36]。这4种基线方法的超参数与原稿或已发布代码中的超参数相同。

3.5 实验结果

为了实现交通和天气条件、人口、人口密度和城市特征(道路网、城市道路和公路的普及率等)的多样性,实验中选择了3个城市(Atlanta、Austin和Charlotte)的数据集,如表3所示。表3列出了STAP模型和其他基线模型在同一个数据集上,不同城市交通状态下事故严重程度的预测效果,从表3可以看出:STAP模型的实验结果在同样的评价指标下都比其他基线模型获得了更好的预测性能,证明了笔者提出的基于时空图卷积网络的交通事故预测方法有效。

表3 3个城市实验对比结果Table 3 Comparison results of 3 urban experiments

如图5(a)所示,支持向量机SVM模型、深度神经网络DNN模型和长短期记忆网络LSTM模型在数据集上的预测效果,要明显比基于时空图卷积网络的交通事故预测STAP模型劣势,由此证明传统的分类模型只考虑了时间依赖性,对于交通事故的预测不够全面,而引入空间依赖性的应用和结合,可以很好地提高预测效果;图5(b)则表现了图卷积神经网络GCN模型和STAP模型在3个城市数据集上的均方根误差对比,在只考虑空间依赖性的情况下,GCN模型的预测效果显然比不上STAP模型。由此可见:在只考虑单因子的前提下,不论是时间特征还是空间特征的提取都存在着一些潜在的问题,而结合了时空依赖的STAP模型则能更好地捕获数据中的时空特征,以达到更好的预测效果。

图5 各模型在3个城市数据集上的均方根误差直观对比图Fig.5 The image of RMSE comparison of each model in 3 city datasets

4 结 论

交通事故预测是一个重大的公共安全问题,实时、准确的事故预测不仅可以对道路交通异常状态提供及时预警,而且可以对如何最大可能地降低事故后续影响程度提供可靠的研究基础。通过将图卷积网络和长短期记忆网络相结合,提出了一种新的基于时空图卷积网络的交通事故预测方法,称为STAP。通过图卷积网络构建路网的拓扑结构,每个划分区域表示为图上的节点,区域之间的连通性表示为边,区域描述则表示为图上节点的属性,以此来获得交通事故的空间相关性;同时,引入长短期记忆网络模型来获取节点属性的动态变化,即时间相关性,最后将STAP模型用于处理时空依赖关系上的交通事故预测研究。在真实的交通事故数据集上进行评价,并与SVM模型、DNN模型、LSTM模型和GCN模型进行比较,结果表明:STAP模型具有更好的预测性能,可以应用于其他时空依赖关系的研究中。