RiskOracle: A Minute-level Citywide Traffic Accident Forecasting Framework
【前言】城市计算领域中，智能交通、智慧出行一直是一备受关注的话题，而交通事故在交通中扮演越来越着重要的角色，据WHO统计，已逐渐成为人类第8大杀手。传统的基础交通动态元素流量、速度预测等不能完全等同于事故预测，因为事故分布更为零星，影响它的因素也更为复杂，包括天气、人为因素、路网显著的动态变化，区域之间的动态关联等，且存在数据量不足的问题。本文提出一种更为短期的交通事故预测框架，提出了多任务差分时变图卷积网络（Multi-task Differential Time-varying Graph convolution Network， Multi-task DTGN），旨在提升交通出行安全，推进数据赋能交通发展，并通过设计一更为专有化的神经网络，推动人工智能社区的进步，为城市计算、时空数据挖掘中的相似问题（如流感预测、犯罪侦测预测等）提供新的思路。
文章地址：https://github.com/zzyy0929/AAAI2020-RiskOracle/blob/master/AAAI-ZhouZ.1664.pdf
全文内容如下：
摘要
实时交通事故预测对于公共安全和城市管理越来越重要（例如，实时安全路线规划和应急响应的部署）。以前的事故预测工作通常在小时级别上进行，并且往往利用已有的神经网络，同时考虑了区域之间静态相关性（如利用CNN网络）。但是，由于道路网络的具有高度动态特性，且样本中事故记录数本身很稀少，这会导致结果偏差和零膨胀问题。因此，提高预测的粒度仍然是一个挑战。 在这项工作中，我们提出了一个新颖的框架RiskOracle，以将预测的时间粒度提高到足够细的水平。具体来说，（由于神经网络往往易于训练连续型的函数）我们首先将标签中的所有风险为零的值转换为适合训练网络的连续值。然后，我们提出了差分时变图神经网络（DTGN），以捕获交通状况的瞬时变化和子区域间动态相关性。此外，我们采用结合多任务的区域选择方案来突出显示全市范围内最可能发生的事故子区域，从而弥合了具有一定偏置的风险值与零星事故分布之间的沟壑。我们在两个真实数据集上进行的大量实验，验证了RiskOracle框架的有效性和可扩展性。
实时交通事故预测
交通事故预测对城市安全具有重要意义。精准的事故预测可以为旅行者提供更及时的安全路线建议。随着智能交通信息和自动驾驶的发展，生产生活中对更精细粒度的事故预测的需求越来越大。精准的预测可以为更为实时的路径规划、紧急救援等提供指导性、关键性信息。
现有的交通事故预测任务分为长期（日级预测）和中期（小时级预测）两部分。在小时级别上的事故预测通常通过神经网络（例如LSTM层）将历史交通事故记录喂入训练网络来学习时间关系。部分研究结合了实时人类活动，分别基于现有的深度学习框架SDAE，SDCAE和ConvLSTM研究事故模式。
尽管深度学习模型的最新进展为小时级事故预测带来了可喜的结果，但我们认为，有如下三个重要问题在很大程度上被忽略了，导致这些模型不能直接应用到更短期的、分钟级的预测中：
- 当预测任务的时空分辨率提高时，将出现零膨胀问题，将所有结果预测为零。如果没有任何解决此问题的策略，则训练数据中稀有的非零项将使模型无法生效。
- 尽管可以通过卷积神经网络（CNN）了解静态的子区域关联度，但时变的子区域关联在全市短期事故预测中也起着至关重要的作用，即两个子区域在由于潮汐流动存在上午的相关性较低，下午的相关性较低的情形。
- 在相邻时间间隔内同一子区域内交通状况的异常变化通常会引发事故或其他事件的发生。如果不考虑上述时空问题，以前的小时级预测模型的能力将受到严重阻碍。
在本文中，我们提出了基于多任务的差分时变图卷积网络（Multi-task DTGN）的三阶段框架RiskOracle，研究了全市范围内分钟级交通事故的预测问题。在数据预处理阶段，我们提出了一种协同感知策略（co-sensing strategy），以最大程度地推断全局交通状况，然后基于先验知识的数据增强功能可解决零膨胀问题，以进行短期预测。在训练阶段，我们提出了多任务DTGN，其中时变总亲和度矩阵可以显式地对短期动态的子区域相关性进行建模，而差分特征生成器则在交通状况在同一区域的短期变化与事故之间建立更为高阶的关联。由于事故和交通量在城市中往往分布不平衡（更多的车和更多的事故往往会集中在城市中心downtown，称之为空间异质性），因此多任务方案旨在解决事故预测中的空间异质性。然后，通过在预测阶段利用学习到的多尺度事故分布，我们可以获得一组离散的最有可能的子区域。在两个数据集上进行的实验表明，我们的框架在30分钟和10分钟级别的预测任务上都超过了最新的解决方案。
准备工作与问题定义
在我们的事故预测工作中，如果直接将整个研究区域建模为全部方形区域，并采用传统的CNN进行时空特征提取，则会导致不必要的冗余，同时，对于城市而言，其边缘轮廓通常是不规则的。 如图2（a）所示，我们首先将道路网络内的研究区域划分为
中等大小矩形区域（简称矩形区域）。 每个矩形区域都包含几个小型正方形子区域（简称子区域）。 我们将在路网中的区域选择出来，研究区域中共有
个子区域，我们使用城市图（网络）对这
个子区域进行建模。
定义1 城市图
整个研究区域我们定义为城市图
. 节点集合
, 集合中的每一个元素
表示第
个子区域。 给定
, 边
表示两个节点（子区域）相连 ，也就是这两个区域存在关联性。其形式化表达为：
本文中交通相关的元素包含2个方面，分别是静态的路网特征和动态交通特征。我们通过
-连通来控制亲和度矩阵
（静态亲和度） 和
（动态亲和度） 保持城市路网的稀疏性和计算复杂度。
定义2 静态路网特征
一个城市子区域
，即该子区域内道路网络的静态特征，涵盖了以下统计空间属性：车道数量，道路类型，路段长度和宽度，除雪优先级以及高架电子标志的数量， 内部的所有路段都可以表示为固定长度向量
。 整个城市区域的静态路网特征可以表述为
.
定义3 交通动态特征
区域
在
时间内的动态特征，可以包括：（1）交通流量
，（2）交通状态（速度）
，（3）事故风险
。 事故风险可以表示为：
因此，在
内，整个城市区域的事故风险分布和动态交通特征可以表示为
问题定义 交通事故预测
给定静态道路网络特征
和历史动态交通特征
，我们的目的是预测全市范围内交通事故风险
的分布，并选择高风险次区域
，用于未来
时间间隔的（全城）事故风险分布。
方法：分钟级别的实时交通事故预测
我们的模型分为3个部分，数据预处理，模型训练，事故预测（层次性事故区域筛选）如图1所示。
图1 模型总览
数据预处理
解决事故预测中的空间异质性
由于大多数的交通事故往往发生在交通流量较大、具有较高风险值的市中心区域，导致严重的风险空间失衡，而忽视了农村地区相对高风险的地区。 要进行全市范围的预测，必须选择最可能发生事故的区域并解决空间异质性问题。因此，如图2（a）所示，对城市以不同大小的尺度划分，中等的矩形区域负责收集粗粒度的事故分布而小的方形区域负责收集细粒度事故分布。 然后，将进一步分别高亮出每个中型矩形区域中的子区域。多尺度事故信息分布可视为一种空间层次性事故分布。
克服零膨胀问题
如果训练标签中的非零项目非常少见，深度神经网络（DNN）会使得训练的权重为全0，从而使得模型失效、遭受零膨胀问题。如图2（b）表明了短期事故的内在稀有性。为了克服实时事故预测中的这一问题，我们设计了一种基于先验知识的数据增强（PKDE）策略，以区分训练数据集标签中的风险值。具体来说，对于区间
，我们将
中的零值项转换为一个具有区分度负值。转换分为两个阶段：a）通过等式（2）将零值转换为事故风险指标； b）指标的值通过等式（3）转换为统计事故强度。给定分区
，我们可以计算其事故风险指标
，通过
其中
是训练数据集中的总周数，而
表示在整个训练期间区域
的总风险值第jj周的时间间隔。然后，我们可以计算区域
的统计事故强度
其中
和
是在
的绝对值范围和真实风险值的范围之间保持对称性的系数。我们利用（底数大于1的）对数函数在0到1之间的区分特性，可以轻松地使变换后的数据区分并适合于训练网络。转换的实现方式为：1）零值项的子区域的事故强度值为负，因此小于非零项目子区域的值，反映出零值项的子区域的事故风险在这个时间间隔内较低； 2）具有较低事故风险指标的次区域具有较低的事故概率，可以保留实际事故风险的排序。
图2 NYC城市划分的一种方式及随机选取的10min事故分布
填充稀疏的感知数据
实时交通信息通常难以充分收集到以进行事故预测，但是，动态交通信息往往与静态空间路网结构具有交互作用。 因此，我们通过利用因子分解机（FM）的交互操作将xDeepFM修改为适合交通数据的时空深度分解机（ST-DFM），提出了一种协同感知策略。
我们首先通过静态亲和力矩阵
提取路网相似性和子区域之间的连接， 其中
中的
表示子区域
和
之间的静态亲和度，可以通过以下方式计算：
散度函数可以表示为:
与xDeepFM类似，ST-DFM包含压缩交互网络（CIN）模块和DNN模块。三个时空字段，即静态空间特征，动态交通特征（对于一个子区域
中的动态交通特征字段，我们首先通过静态亲和力矩阵（可用动态交通，选择最接近
的子区域。这些子区域中的信息将由
。 中的动态流量特征构成，并且时间戳嵌入ST-DFM中）。然后，ST-DFM使用CIN模块学习矢量方向上不同时空特征之间的交互关系，并使用DNN模块学习特征的高级表示之间的交互关系，最终获得特征的高级组合。我们通过将相应子区域的交通量输入到ST-DFM中来推断速度值，反过来，亦可训练一个ST-DFM模型来推测交通量，这就是我们的协同感知技术。然后，通过训练两个实时交通数据集的交集内的数据，可以最大程度地推断交通信息以获得全局交通状态。
基于Multi-task DTGN的交通事故预测
Spatiotemporal DTGN
采用GCN的动机：（1）由于交通事故和道路拥堵存在一定的交互影响和传播关系。具体而言，一方面，可能由于拥堵造成车辆的频繁超车从而导致交通事故，另一方面，发生交通事故后往往会堵塞道路，从而造成车辆排队，进而增加交通事故发生的风险，造成交通事故，由此在事故点/拥堵点不断传播扩散。（2）相似的路网结构和相似的动态交通模式易产生事故共现。如具有三叉路口、四岔路口等，这些路况往往因为车流量集中且存在变道、转弯的现象，容易造成事故，当城市处于同一天气下，这些地区的事故风险会同时增加，然而由于不同的地区交通模式不同，其事故风险的增加量各不相同，故需要一种方式去量化在不同条件下不同路段（区域）交通事故风险的变化。然而这种关联可能并不是在欧氏关系上的相邻或邻近，而是存在远距离的相似，即非欧氏关联。基于以上两点考虑，我们利用GCN在非欧氏关系中良好的建模效果，建立了本模型。我们提出了一GCN的变体差分时变图卷积网络（Differential Time-varying Graph neural Network, DTGN）并针对观察特征与挑战考虑了以下两个因素： （1）【时变图网络】区域之间存在一定的相似性和关联性因潮汐车流等原因产生的会随时间变化的不同关联程度，如图3所示。总体亲和度矩阵
捕获特定时间间隔
内子区域间时变交通量相关性为
其中
部分为静态相似性，
为动态相似性，
为调和参数。 （2）【差分图网络】对于同一区域，相邻时间间隔内交通基础元素的数值变化对交通事故的影响（贡献）。与常规交通预测问题（基础元素）相比，事故或事件预测的任务与城市交通状况的异常变化更为相关，这一点已被人们普遍接受。 为此，我们引入了差分特征生成器来计算相邻时间间隔内的差分图像。 通过将差分动态交通特征输入到GCN中，可以对交通异常变化的传播和相互作用进行建模，并且可以了解即时交通状况变化与事故之间的高级关联，特别是对分钟级的事故预报有利。 给定
，可以通过以下公式计算微分矢量
：
参与差分特征生成的
包括流量，速度，而事故风险本身不参与差分生成（因为其差分无显著的物理意义）。
图3 时变的区域关联示意
通过结合其动态交通量特征和相应的差分矢量，我们生成一个统一的特征元组。由于动态的时空数据在时间维度上具有很强的特点，即连续性、周期性和趋势性，我们利用这一特点建立时间依赖关系。在模型的输入部分，基于以上三个特点建立样本并聚合数据，DTGN对输入的数据进行特征抽取，随着DTGN网络层数增加，更高阶区域之间的动态关联将被模型学到。
如图4所示，然后我们将所有三个时间趋势的视图统一特征元组集合独立地传入DTGN。 图4（a）中演示了一种DTGN的详细架构。 对于一个特定的时间角度，我们将对应的联合特征元组记为。 我们将传入全连接（FC）网络，以将所有元素编码为低维要素集，然后将其馈入GCN。 GCN递归地进行运算，
图4 Multi-task DTGN的实现细节
这里
表示
层图卷积，
表示
层图卷积内核的权重。 注意，在这里，从一个时间角度来看，我们将所有选定时间间隔的
矩阵的平均值作为
。 我们在每2个GCN层之间使用批标准化，以避免梯度爆炸。 考虑到转换后的数据集中的负值，我们选择
作为激活函数。 此外，实时动态外部因素（即时间戳和气象数据）被连续嵌入到固定长度的向量中，然后与每个GCN单元的输出融合。 对于三个时间角度，我们将DTGN的输出特征图表示为
，
和
。
多任务学习的交通事故预测
我们设计了一多任务学习机制，不仅可以增强深度表示学习的能力，还可以学习分层的事故分布并为最可能的事故区域选择提供指导信息。 我们首先将细粒度事故风险预测作为主要任务。 考虑到交通事故与人类活动强度之间的显着相关性，我们将区域交通量预测作为提高特征表示能力第一项辅助任务。 为提供分层事故区域区域选择的指导信息，我们将不同中等矩形区域内的事故总数作为第二项辅助任务（这两个是显著相关且可以相互提供信息的任务）。
具体地，如图1所示，我们将 DTGN 输出的特征图，包括
,
和
一起传入基于卷积的融合模块。然后我们进行多任务学习。我们在图4(b)中可视化了多任务部分的运算流程图。我们首先生成预测出来了的风险特征分布图
和交通流量特征图
，由于先前生成了负值的风险值，所以我们选用 Leaky_ReLU 作为主任务的激活函数。
利用额外的全卷积网络，我们学习到每个中等矩形中的事故数
此处
,
和
分别表示三个任务中细粒度交通事故风险分布，人类活动强度分布和中等矩形的事故分布（粗粒度事故分布）的训练权重。
是全连接的训练权值.
可以视作粗粒度的事故分布和
一起生成
，迫使其学习到两者之间的内在关联（粗细粒度之间的），然后，
可由下式更新：
我们模型的总体Loss可以定义为：
层次性的最有可能发生事故区域提名
在一个特定的城市中，城乡之间事故和交通流量的覆盖范围常常不平衡，从而引发了空间异质性的问题。 因此，用统一的风险阈值来选择最可能的事故子区域显然是不合逻辑的。 在本文中，我们基于在多任务方案中学习的层次性的事故分布，提出了一种分层的最可能事故区域选择（HARS）策略。
对于每个矩形区域
，我们选择风险最高的
个子区域，参数
等于第二个辅助任务学到的
中的相对应的元素。 因此，我们获得了一组最可能发生事故的区域。 通过这种方式学习的
减少了过度预测的区域，并使模型符合时间和天气的变化，并涉及外部因素。
实验
数据描述
我们在两个真实世界的数据集上进行实验：NYC Opendata和苏州工业园区（SIP）数据集。 对于纽约市数据集，由于缺乏实时交通量，在这里我们将每个子区域中的出租车数量用作人员出行的指标。 对于SIP数据集，它包含流量和速度。 我们将其与从社交媒体平台新浪微博收集的另一个交通事故数据集集成。两个数据集的统计信息显示在表2中。 有关更详细的信息，请参见网站：https://github.com/zzyy0929/AAAI2020-RiskOracle/。
表2 数据集统计特征
评估策略
我们从回归和分类两个角度评估我们提出的RiskOracle。 （1）回归角度：预测风险的均方误差（MSE）。 （2）从空间分类的角度来看：a）最高
（Acc @
）的准确度（在排名任务中广泛应用）指示
以内的次区域中准确预测的百分比最高风险。 根据统计数据，在纽约市数据集中进行30分钟和10分钟评估时，
等于20和6（NYC Accident Records 2017）。 同样，在SIP数据集中，
等于5。b）Acc @
，其中
是第二个辅助任务学习的
的总和。 其中Acc1表示发生事故的频率较高的时间段内的准确度。
基线方法
一共有5个baseline，他们分别是： (1) ARIMA： 经典的机器学习算法，用于理解和预测未来值，尤其是时间序列预测； (2) Hetero-ConvLSTM： 针对daily的事故预测模型，也是最新、效果最好的事故预测方法； (3) ST-ResNet： 针对人流量预测提出的经典方法，也是潜在的能够用于事故预测的深度学习模型； (4) SDAE： 针对短期事故预测，引入人流量（人类活动等）作为事故预测的指示； (5) SDCAE： 针对短期事故预测的模型。
结果显示与分析
模型间比较分析
表3展示了在间隔为30分钟和10分钟的情况下对NYC和SIP数据集的性能比较。我们的RiskOracle框架在几乎所有指标上都达到了最高的准确性。并且对于稀疏的传感数据以及短期的零星时空预测而言，可扩展性更高。NYC上的性能优于SIP数据集的原因可能是SIP中的事故标签不完整。我们将在以后的消融研究中报告Acc @
指标的结果。
总体而言，随着时间粒度的变细，我们的框架性能会略有下降，然而基线会因为事故label急剧减少而陷入零膨胀问题而急剧下降，这证明了我们的短期事故预测建议的有效性和可扩展性。即使在实际应用中的数据集包含罕见事故记录的情况下，两个数据集的评测验证了我们提出的RiskOracle的鲁棒性和通用性。
表 3 NYC和SIP模型预测比较
Acc @
与自身消融实验
在表4中，我们报告了我们在论文中提出的Acc @
的结果。Acc @ 20和Acc @ 6的结果略高于Acc @
，这是合理的因为统一阈值无法适应实时条件，并且往往会高估事故率。相反，我们的框架具有使用多尺度事故分布预测来潜在地近似估计每个矩形区域中事故数量的灵活性。如所观察到的，与表3中的结果相比，我们的框架可以胜过其他基准并在Acc @
上达到可接受的准确性水平。
我们在NYC数据集上进行了消融实验，我们从整体框架中分别删除以下的模块：
- RO-1 PKDE数据变换增强策略
- RO-2 ST-DFM（时空深度因子分解机，用于缺失数据推断的）
- RO-3 总体的动态亲和度矩阵（时变的图网络）
- RO-4 差异特征生成器（差分图网络）
- RO-5 带有HARS的多任务（层次性事故区域筛选机制）
表4 消融实验
案例分析（Case Study）
如图5所示，我们将在一天中选择特定的30分钟间隔来可视化由RiskOracle预测的事故效果。 总体而言，RiskOracle生成的全市范围的风险图显示了具有区分度的风险值，突出显示的子区域风险与真实值分布具有很大的空间相似性。 由于很少有人在周日上午外出，因此早晨7:00所预测发生的事故很少。 但是，当下午到来时，事故数量会增加，而到了晚上，事故甚至会更加严重。 这主要是由于当晚的大雨，导致易发生事故的路况。 结果证明，辅助任务和HARS通过捕获具有外部因素的事故分布的动态模式来学习相应地调整推理，这比统一阈值解决方案具有更好的适应性。
图5 RiskOracle 在2017年5月22日（周日），NYC的预测情况
总结：
在本文中，我们通过提出基于多任务DTGN的集成框架RiskOracle来应对分钟级别的全市范围交通事故预测的挑战，从而更及时地为城市安全提供定量决策依据。我们首先提出两种策略来克服零膨胀问题和稀疏感知。通过在多任务DTGN中合并差分特征生成器和时变总体亲和力，我们的框架具有对零星时空数据进行建模并捕获短期子区域相关性的功能。我们还重点介绍了在多任务方案中最可能发生事故的区域，以可学习的多尺度事故分布来处理空间异质性。在两个实际数据集上进行的实验证明，我们的框架优于最新的解决方案。因此，我们的工作可能是解决时空数据挖掘任务的范例，该任务具有零星的标签和不足的传感数据，例如犯罪和流行病爆发的预测。
【Accepted by AAAI 2020 (Application Track)】
