TKDE|Foresee Urban Sparse Traffic Accidents: A Spatiotemporal Multi-Granularity Perspective

稀疏交通事故预测：以时空多尺度视角

本文以交通事故预测为应用背景，提出了一个基于多源时空数据的多步、多粒度稀疏事件预测模型。其中集中归纳总结并缓解了时空稀疏问题、短期状态变化感知与多步预测问题。

1 背景与介绍

  交通事故已成为最大的公共卫生威胁之一，据世界卫生组织（WHO）的全球状况报告，全世界约有 125 万人死于交通事故，WHO 已经将其列为人类第 9 大健康威胁。因此，实现城市交通事故的多尺度（多粒度）精确预测，可提高交通警察警力分配效率和公共资源分配的精准性与公平性，进而减少道路交通伤害、确保城市公共安全，提升全民幸福感和安全感。

图1 交通事故预测

  现有的交通事故预测任务大多分为长期预测和短期的预测:

【长期预测】：针对全州（全省）下一周中每日的事故总数进行预测，形成事故风险图，但均为固定的空间尺度。

【短期预测】：1h的时间粒度，且均为单步预测，不能感知到路网的短期变化。

  逐日事故风险预测对于实时智能交通系统作用甚微，因此本文着眼实时系统，研究短期交通事故预测。而对于短期预测，如能同时实现空间上多尺度（粒度）预测、时间上多步预测，将对不同层级的交通管理部门调度工作、以及不同出行需求的市民更有价值。在技术层面，目前的工作对零膨胀问题（大量数据的label为0，导致神经网络训练过程中趋向于将所有值归为0）、极度稀疏的多步时间序列预测任务仍然未研发出有效解决方案，且目前也尚未有工作融合稀疏的时空数据和多尺时空依赖关系来进行短期交通事故预测。

本文贡献与创新点：

• 这是第一项针对时空多粒度城市交通风险预测的工作，文中，我们将零星事件预测转换为可学习的自适应排名任务。它为零星事件的时空多粒度预测提供了一种基于DNN的解决方案。
• 根据时空数据中稀疏问题的起源，我们提出了两种时空稀疏性挑战。（1） 伪稀疏：数据本身存在然而却因为外界原因未被感知或探测； 和 （2）本质稀疏： 本身具有少量标签且难以生成新的有效标签的问题叫做本质稀疏问题。本文中，我们对应地分别提出了两种方法来缓解上述问题，并基于对短期交通流和事故模式的观察，提出了一种新的基于节点亲和度度量和图信号差分运算的时变差分图卷积神经网络（Differential-Time varying GCN, DT-GCN）来提取城市交通和事故在区域上的时变相关性，以信号运算和节点亲和度度量视角推动图卷积模型的进步和发展。
• 我们设计了一种新颖的层次型序列学习结构，即以上下文引导的LSTM，在两个空间尺度上并行地解码多步风险特征图，并将上下文信息（包括天气、时间）注入到解码器中，以学习区域级别与上下文因素的交互影响，进而通过风险分配和风险聚合层来引导空间多粒度的事故风险学习。

2 问题定义

定义1： 构建无向的城市图

G(\mathcal{V},\mathcal{E})

. 其中

\mathcal{V} = \{ {v_1},{v_2}, {v_i},\cdots ,{v_m}\}

，城市中有

m

个区域，其中第i个区域视作图中第i个节点

v_i

, 而区域

{v_i}

和区域

{v_j}

的连通关系用边

{e_{ij}} \in \mathcal{E}

来刻画。 定义2： 静态特征

\mathcal{S}

和动态特征

f

. 每一个节点

v_i

中都携带有本区域的动静态特征。其中，在

\Delta t

时间段内的动态特征

f_{v_i}({\Delta t})

由流量、速度和风险值表示，即

f_{v_i}({\Delta t})=\{T{V_{{v_i}}}(\Delta t),{a_{{v_i}}}(\Delta t),{r_{{v_i}}}(\Delta t)\}

，静态特征由路网结构向量构成

\mathcal{S} = \{ {s_1},{s_2}, \cdots ,{s_m}\}

。 问题：时空多尺度交通事故预测：给定静态路网结构特征

\mathcal{S}

和历史的动态交通信息

\mathcal{F}(\Delta t)\left ({\Delta t = 1,2, \cdots T}) \right.

, 我们的任务是同时预测在未来

r

步空间上粗粒度和细粒度的交通事故风险，以及最可能发生事故风险的M个区域，即

{\mathcal{O}_C}(\Delta t')

，

{\mathcal{O}_F}(\Delta t')

, 和

{\mathcal{V}_{\mathit{M}}(\Delta t')}

, 其中

{\Delta t' = T+1, T+2, \cdots T+r}

。

3 方法

3.1 模型概述

  如图2所示，面向事故数据的稀疏特性和时空多粒度预测的挑战，我们的模型分为三个阶段集中解决这些问题。数据预处理阶段，我们将路网数据划分为层次性的结构，即每一个在路网中的网格都作为一个小节点，地理上相邻的小节点又组成一个中等的矩形区域，因此模型在学习过程中可有效利用这两个粒度的信息进行协同预测。我们还提出了基于先验知识的数据增强策略（Prior Knowledge-based Data Enhancement, PKDE）和基于时空协同感知动态预测模型（ST co-sensing）来分别解决本质稀疏带来的零膨胀问题和时空感知中的伪稀疏挑战。空间建模阶段分别抽取两个空间尺度信息，且在细粒度空间建模中提出差分时变图卷积网络（DT-GCN）来捕获空间的动态关联、提升模型对短时流量变化的敏感性。在时间序列建模阶段，创新性地提出了基于上下文引导的LSTM解码器，输入两个空间尺度的事故风险特征序列，通过风险分配和风险聚合层来关联粗细粒度的事故信息，从而传递两者的交互影响。最后利用模型输出的多粒度的风险信息，进行联合筛选事故高风险区域，得到最终结果。

图2 模型概述：RiskSeq

3.2 数据预处理

（1）城市的层次性划分   由于我们发现深度学习中，稀疏的数据往往很难学习，而越连续、丰富的数据的内在规律越容易被学习，所以我们按如图3所示的方式划分城市区域，小区域称作小方形子区域，中等的方形被称作中等矩形区域。中等矩形区域中的事故大多不为0，因此可缓解零膨胀问题。

图3 城市的层次性划分方式

（2）缓解两类稀疏挑战

  本节中，我们正式提出两种稀疏时空数据的概念。从稀疏问题产生的源头和场景上，我们划分为本质稀疏和伪稀疏，本质稀疏指的是本身具有少量标签且难以生成新的有效标签的问题，如交通事故、城市的各类事件、极端天气等，该类信息无法通过学习的方法增大数据量，只能进行一定的数据变换，伪稀疏指的是数据本身存在然而却因为外界原因未被感知或探测，如处处存在的交通流量、速度信息、天气信息，由于传感器布置的昂贵代价而不能采集到所有区域，该类数据可以通过捕获其时空模型进行数据增强和推断。本质稀疏与伪稀疏示意图如图4所示。

图4 稀疏的事故分布（本质稀疏）与稀疏的交通流量采集设备分布（伪稀疏）

• 针对本质稀疏，我们提出了一种基于数据集先验信息的增强方法，核心思想是将数据离散化为一个负数，用这个负数替代训练过程中风险值为0的区域label。负数值意味该区域未发生事故，对数化后可差别化不同区域的区域且保持各区域潜在风险排序不发生变化，而这个排序表示即使未发生事故，平时发生事故越多的区域，在一个未知的时刻其事故风险也相对越高。 （1）统计每个区域的交通事故发生强度（每个区域在这个数据集上的事故总数占事故总数的百分比），并归一化到（0，1）之间，得到区域

v_i

的事故强度

\varepsilon _{{v_i}}

； （2）利用对数函数在0~1区间上的数据离散化和非正的特性，将

\varepsilon _{{v_i}}

用对数log 转化成一个负数，并且使用一些约束的参数b1、b2来使其和正的risk风险值相一致，如正的风险值在0-5之间，那么负数值也在-5~0之间，如下式所示。

{\pi _{{v_i}}} = {b_1}{\log _2}{\varepsilon _{{v_i}}} + {b_2}

事实上，将label进行替换的方式与设计loss具有相似的效果，因为替换后模型将按照现有的label来计算loss。

• 针对伪稀疏，我们设计了一种基于ST-DFM的协同感知策略。其思想是利用各种额外信息，对缺失的动态信息进行相互推断，使得模型获得的信息最大化。即知晓了本区域与邻近区域速度信息，基于天气、区域和时间戳和速度，进行流量信息的推断，对应地，可再训练用于基于流量和额外信息的速度推断模型。选用Deep Factorization Machine，是由于各种额外信息之间会产生明显的交互影响，如同一天气状况在不同区域的影响是不同的。 一般而言，具有相似路网结构的区域，往往具有相似的交通模式，因此我们通过基于路网结构特征来构建区域间静态亲和度矩阵

\mathcal{A} _ {s}

，进而对于筛选交通模式相似的区域，

\mathcal{A} _ {s}

将由下式计算得到：

{\alpha_{s}}(i,j) = \left\{ {\begin{array}{*{20}{c}} 1&\begin{array}{l} {\rm{if}}\;{\rm{subregion}}\;{v_i}\;{\rm{and}}\;\\{v_j}\;{\rm{are}}\ {\rm{geographically}} \; {\rm{adjacent}} \end{array}\\ {}&{}\\ {{e^{-\mathit{JS}({s_i}\left\| {{s_j}} \right.)}}}&{{\rm{otherwise}}} \end{array}} \right.

其中，

\alpha_{s}(i,j)

是

\mathcal{A} _ {s}

中的元素，JS表示一种度量静态特征分布相似度的尺度，JS散度。 基于此，我们便可顺利地筛选出邻近区域，并挑选出具有动态交通信息的区域加入到ST-DFM的特征中。

3.3 基于DT-GCN 的时空编码器

  本节中，我们提出了差分时变图卷积神经网络来对交通流和事故的时空信息进行编码。 基于交通事故发生模型的两点观察：（1）交通事故和道路拥堵存在一定的交互影响和传播关系。一方面，拥堵会造成车辆频繁超车从而导致交通事故，另一方面，发生交通事故后往往会堵塞道路，导致车辆排队，进而增加交通事故发生的风险，事故风险由当前的事故点/拥堵点不断向拥堵方向传播扩散。（2）相似的路网结构和相似的动态交通模式易产生事故共现。三叉路口、四岔路口等交通枢纽处的路况往往车流量较为集中，且存在变道转弯频繁的现象，易造成事故，当城市处于同一天气下，这些地区的事故风险会同时增加，然而由于不同的地区交通模式不同，其事故风险的增加量各不相同，故需要一种方式去量化在不同条件下不同路段（区域）交通事故风险的变化。然而这种关联可能并不是在欧氏关系上的相邻或邻近，而是存在地理空间远距离、语义空间近距离的相似特性，即非欧氏关联。

  基于以上两点考虑，考虑到GCN可基于灵活设计的邻接矩阵（亲和度矩阵）来建模非欧氏关系，我们提出了一GCN的变体差分时变图卷积网络（Differential Time-varying Graph neural Network, DT-GCN）并针对观察特征与挑战考虑了以下两个因素： （1）【时变图网络】如图5所示，区域之间存在一定的相似性和关联性因潮汐车流等原因产生的会随时间变化的不同关联程度，如图3所示。因此，我们考虑三个方面的特性： 静态相似性

{e^{ - \mathit{JS}(s_i^*\left\| {s_j^*} \right.)}}

，邻近的时变动态信息（流量速度等）

{e^{ - \mathit{JS}(C_i^{\Delta t}\left\| {C_j^{\Delta t}} \right.)}}

，区域

v_i

到

v_j

的OD流量转移信息

{\mathit{tr}_{ij}^{\Delta t}}

，因此，区域

v_i

和

v_j

在时间间隔

\Delta t

内的时变亲和度

\alpha _{o}^{\Delta t}(i,j) \in \mathcal{A} _ {o}^{\Delta t}

为

\alpha _{o}^{\Delta t}(i,j) = {e^{ - \mathit{JS}(s_i^*\left\| {s_j^*} \right.)}} + \gamma *{e^{ - \mathit{JS}(C_i^{\Delta t}\left\| {C_j^{\Delta t}} \right.)}+\beta *{\mathit{tr}_{ij}^{\Delta t}}}

其中

\gamma

为调和参数。 （2）【差分图网络】对于同一区域，相邻时间间隔内交通基础元素的数值变化对交通事故的影响（贡献）。与常规交通预测问题（基础元素）相比，事故或事件预测的任务与城市交通状况的异常变化更为相关。 为此，我们引入了差分特征生成器来计算同一区域在相邻时间间隔内的动态流量和速度的差分值。 通过将差分动态交通特征输入到GCN中，可以对交通异常变化及其传播特性与事故直接进行关联性学习，可让模型更敏感于路网交通状态的短期变化，有利于短期多步风险预测。 给定

\Delta t

，可以通过以下公式计算差分矢量

{\overrightarrow \Theta ^ {\Delta t}}

：

{\overrightarrow \Theta ^{\Delta t}} = \mathcal{D}(\Delta t) - \mathcal{D}(\Delta t - 1)\

参与差分特征生成的

\mathcal{D}(\Delta t)

包括流量，速度，需要说明的是，因事故本身的差分无显著的物理意义，此处事故风险不参与差分值生成。

图5 时变的区域关联示意

通过结合其动态交通量特征和相应的差分矢量，我们生成一个统一的特征元组

\mathcal{U}(\Delta t) = \left\{ {\mathcal{F}(\Delta t),{{\overrightarrow \Theta }^{\Delta t}}} \right\}

。

  对于某一区域未来多步的风险预测，可分解为由长期的交通状态、事故风险模式（季节性影响与周期性模式）与短期的瞬时变化（如近期趋势和突发事件）的组合，我们利用这一特点在模型的输入部分分别抽取最近连续

\tau

周（邻近

\tau

周中每周与当前weekday一致的对应的day interval）和

h

个邻近的时间间隔来构建长期依赖与短期依赖，DT-GCN分别对这两种时间依赖下的数据进行时空特征抽取。 图6展示了DT-GCN的详细结构。 我们将对应的联合特征元组记为

\mathbb {U} _*^{\Delta t}

，将

\mathbb{U} _*^{\Delta t}

传入全连接网络，并与时空信息融合，再输入GCN。 GCN递归地进行运算，

{\mathcal{H}^{n + 1}} = {\mathop{\rm Leaky\_ReLU}\nolimits} ({L^*}{\mathcal{H}^{n }}{\mathcal{W}^n})\;{\rm{where}}\;{\mathcal{H}^0} = \mathbb{U}_*^{\Delta t}

图6 DT-GCN的实现细节

  这里

\mathcal{H}^{n}

表示

n

层图卷积，

\mathcal{W}^n

表示

n

层图卷积内核的权重。 注意，在这里，从一个时间角度来看，我们将所有选定时间间隔的

L^{\Delta t}

矩阵的平均值作为

L^*

。 我们在每2个GCN层之间使用批标准化，以避免梯度爆炸。 考虑到转换后的数据集中的负值，我们选择

\mathop {\rm LeakyReLU}

作为激活函数。 此外，实时动态外部因素（即时间戳和气象数据）被连续嵌入到固定长度的向量中，然后与每个GCN单元的输出融合。 对于三个时间角度，我们将DTGN的输出特征图表示为

\mathcal{O} _ {hc} ^{\Delta t}

，

\mathcal {O} _ {dp} ^ {\Delta t}

和

\mathcal {O} _ {dt} ^ {\Delta t}

。同时，我们在GCN中引入2层残差结构，以缓解随着GCN网络层数增加所带来的梯度消失问题。经过实验，我们发现通过堆叠4-6层GCN可获得较为不错的效果。   至此，我们获得了长期依赖与短期瞬时变化组成的序列：

{\mathcal{M}_{F}} = \{{\mathcal{M}_{F}}^0, {\mathcal{M}_{F}}^1, ..., {\mathcal{M}_{F}}^{h+1}\}

，其中

{\mathcal{M}_{F}}^0, {\mathcal{M}_{F}}^1

表示长期依赖抽取的特征，剩下的上标为2~(h+1)均为瞬时变化信息。

3.4 基于Context-Guided LSTM的时空解码器 (CG-LSTM)

  首先我们选取了NYC中三个代表性区域，并将其雨天与非雨天的事故数进行了统计，如图7所示。我们发现，第一、二两个区域的交通事故数受天气影响较大（敏感于天气变化），而区域三受天气影响较小，因此我们发现天气等上下文信息对于不同区域而言，其影响是空间异质的。

图7 不同区域在下雨与不下雨情形下的事故量统计

  此外，每一个时间步当中，应当包含时间戳信息，因为不同的时间戳下所产生事故风险的大小也不尽相同，如高峰期所对应的时间戳的事故风险较大，尤其是在未来较长时间的多步预测中。 因此，基于以上观察，本文设计了一个上下文引导的LSTM时间序列预测模型，巧妙地将每一个时间步的上下文信息（时间戳和天气等）引入到解码器的LSTM中。

  另一方面，为实现空间多尺度预测并缓解零膨胀问题，使得网络能够顺利训练并获得我们预想的结果，我们利用两个并行的LSTM，C-LSTM和F-LSTM来同时学习空间粗粒度风险和细粒度风险在时间上的依赖关系。 具体地，由于粗粒度风险值更密集（细粒度风险更稀疏，零值更多）将更易被网络所学习，我们将粗粒度学习作为中间媒介，粗粒度C-LSTM的隐层特征

{\mathcal{I}}_C^{\Delta t + 1}

可用下式计算：

{\mathcal{I}}_C^{\Delta t + 1}{\rm{ = LSTM_{C}(\mathcal{M}}}_C^{\Delta t + 1},[{W_{{\text{ex}}t}} * {E^{\Delta t + 1}} + {\mathcal{I}}_C^{\Delta t}] {\rm{)}}

而细粒度F-LSTM的隐层特征

{\mathcal{I}}_F^{\Delta t + 1}

{\mathcal{I}}_F^{\Delta t + 1}{\rm{ = LST}}{{\rm{M}}_{\rm F}}{\mathcal{(M}}_F^{\Delta t + 1},[W_{{\rm{asgn}}} * {\mathcal{I}}_C^{\Delta t} + {\mathcal{I}}_F^{\Delta t}] {\rm{)}}

  进一步地，我们设计了风险分配层将中间媒介层（C-LSTM）的信息分别传播到细粒度risk feature map，和一风险聚合层来聚合事故风险到全城级别（citywide-level），这样我们就可以得到三个空间粒度的多步预测信息。以更易学习的C-LSTM作为媒介和引导，可以使得我们的模型更容易学习、细粒度风险学习更准确。 风险分配层全连接网络得到全城细粒度事故风险分布：

{\mathcal{O}}_F^{\Delta t} = {\rm{Leaky}}\_{\mathop{\rm Re}\nolimits} {\rm{Lu(}}{W_{RF}} * {\mathcal{I}}_F^{\Delta t}{\rm{ + }}{{\rm{b}}_{RF}})

风险聚合层全连接网络得到全城级别的事故总风险值：

\tilde{R}_S^{\Delta t} = {W_{gath}} * {\mathcal{I}}_C^{\Delta t}

最终输出的隐层对齐的粗粒度风险分布：

{\mathcal{O}}_C^{\Delta t} = {\mathop{\rm Re}\nolimits} {\rm{Lu(}}{W_{CF}} * {\mathcal{I}}_C^{\Delta t}{\rm{ + }}{{\rm{b}}_{CF}})

  对于以上三个空间粒度，细粒度为每个节点的风险值（零值利用PKDE的计算值替代），粗粒度为对应节点细粒度风险值的和，全城的事故风险总值为当前时间间隔内事故发生总数，因此，损失函数如下：

{\rm Loss}(\theta ) = \mathit{MSE}_{F} + {\lambda _1}*\mathit{MSE}_{C} + {\lambda _2}*\mathit{MSE}_{R} + {\lambda _3}*{\rm L2}

至此，我们的模型得到了未来

r

步中三个空间粒度的预测信息，为

r

个三元组，

\{<\mathcal{O}_F^{T+1},\mathcal{O}_C^{T+1}, \tilde{R}_S^{T+1}>,...,<\mathcal{O}_F^{T+r},\mathcal{O}_C^{T+r}, \tilde{R}_S^{T+r}>\}

模型总结： CG-LSTM从层次性的LSTM序列建模和逐步输入上下文信息引导中间粒度事故风险预测两个层面拓展了LSTM模型，缓解了LSTM在中长期预测中存在的误差增大、稀疏事件预测难的挑战。

3.5 基于多粒度风险预测的高风险区域筛选

  为了选择最可能发生的事故子区域，我们了设计一种自适应高风险区域选择机制。 具体来说，风险聚合与分配网络可学习多尺度空间风险分布的空间依赖、充分吸收层次相关性。 对于时间

\Delta t

内，我们将学习得到的总和风险

\tilde {R} _S^{\Delta t}

作为全市范围的风险指标，并将高风险子区域个数的自适应阈值设为

K(\Delta t)

等于

int(\tilde{R} _S ^ {\Delta t})

，即从

\mathcal {O} _F ^ {\Delta t}

中选择风险最高的

K(\Delta t)

个子区域作为一组最可能发生的事故子区域

\mathcal{V}_{\mathit {M}}

。 可学习的

K(\Delta t)

受时间、上下文因素、路网状态等影响动态地进行调整（更敏感于上下文变化），可减少区域数量过度预测。

4 实验

评估指标

   回归视角采用MSE， 分类视角采用ranking后选取Top-K的方式。

模型横向对比

如图8所示，和其他baseline对比，我们的模型在NYC和SIP数据集上分别达到56.42%和71.27%的准确率。

图8 Baseline对比

多时间步预测对比

   将模型和具有多步预测能力的时空模型Baseline相比，如图9所示，RiskSeq具有更高的准确率，且预测能力平稳。

图9 多时间步预测对比

模型纵向对比-消融实验

（1）RS-OA: 将动态亲和度矩阵替换成仅由路网结构特征计算的静态亲和度矩阵； （2）RS-DG: 移除差分值生成器模块； （3） RS-RC: 移除DT-GCN中的残差模块； （4）RS-CF: 在CG-LSTM中仅使用多个LSTM预测，而不将上下文信息逐步输入LSTM的隐层中； （5）RS-CGLSTM: 使用普通的LSTM代替CG-LSTM。   实验结果如图10所示。

图10 消融实验

案例分析与探讨

图11 案例分析

5 讨论

RiskSeq的一般适用性 RiskSeq的核心思想是动态聚合邻域图信号以获得更好的风险表示，并通过采用逐步上下文注入和多尺度的时间序列学习来增强多步事故风险预测。除了对事故预测的良好表现，我们的工作还可能使时空预测中的其他下游任务受益。犯罪和流行病与交通事故具有相似的性质，其偶尔发生并表现出时变的空间依赖和人员流动模式。因此可基于ST-DFM和城市协变量缓解数据不足，再通过PKDE缓解事件本质稀疏问题，从而得到适合RiskSeq训练的数据。与人类活动有关的数据以及特定于任务的历史记录被输入到DT-GCN中，以捕获时变和异常情况，并使用CG-LSTM解码器增强多步预测。

RiskSeq提供的新颖见解 针对两个不可避免的稀疏场景，我们通过提出新颖的策略来解决本质稀疏和伪稀疏问题。我们将稀疏事件预测转换为可通过DNN解决的可学习的回归和排序任务，为研究人员从稀疏性起源的角度挖掘时空稀疏数据集中的潜在相关性提供新视角，鼓励使用新颖的稀疏性划分（例如网络中的节点和边缘稀疏）和一定的新操作、问题转换方法来支出解决各种稀疏场景问题。这些相关研究最终可能会解决推荐系统、故障检测和社会检测等领域中具有稀疏挑战的任务。

6 结论

  在本文中，我们提出了一个新颖的统一框架RiskSeq，该框架可以通过多种时空粒度来学习稀疏交通事故，从而满足城市出现者和交通管理部门的多样化需求。 首先，我们总结了两种稀疏性挑战，并相应地缓解了其导致的零膨胀和稀疏感知问题。受交通事故特点和事故相关的交通模式启发，我们设计了DT-GCN，以通过捕获城市交通的短期变化来增强时间敏感的图表示。 为实现多尺度和多时间步预测，我们设计了CG-LSTM，我们可以动态地学习区域-上下文交互，并进一步减轻误差累积。在两个真实数据集上的实验结果证明了我们所提出的包含DT-GCN和CG-LSTM集成结构的RiskSeq框架的优越性。