论文解读 | 基于时空多图卷积的交通流量预测

标题

Spatiotemporal Multi-Graph Convolution Network for Ride-Hailing Demand Forecasting

作者

Xu Geng, Yaguang Li, Leye Wang, Lingyu Zhang, Qiang Yang, Jieping Ye, Yan Liu

摘要

区域级需求预测是网约车服务中的一项重要任务。准确的叫车需求预测可以指导车辆调度，提高车辆利用率，缩短等待时间，缓解交通拥堵。这项任务由于区域之间的时空依赖关系复杂，因此具有挑战性。现有方法主要集中在模拟空间相邻区域之间的欧几里得相关性，同时我们观察到，可能遥远区域之间的非欧几里得成对相关性对于准确预测。
本文提出了一种用于网约车需求预测的新型深度学习模型——时空多图卷积网络(ST-MGCN)。

我们在网约车需求预测中识别区域之间的非欧几里德相关性，并建议使用多个图对它们进行编码。然后我们进一步利用所提出的多图卷积来明确地对这些相关性进行建模。
为了利用全局上下文信息对时间关系进行建模，我们进一步提出了上下文门控式递归神经网络(CGRNN)，该网络利用上下文感知的门控机制对递归神经网络进行扩充，以重新加权不同的历史观测值。
我们在两个真实的大型网约车需求数据集上评估了所提出的模型，并观察到比最先进的基线有超过10%的一致性改进。

论文背景

据 Uber 统计，2018年，全年的网约车使用次数达180亿次，超过全球人口的两倍。准确的网约车订单预测，能够更好的调度车辆，提高车辆的利用率，缓解交通拥堵，具有重要的经济和社会意义。

网约车需求量预测问题可以通过其数据建模方式来理解。以1小时为时间单位，1km*1km 的网格为空间单位，某城市某个小时订单量可以用如下所示的2d格点图片来表示，每个格点的数值是在该时间段内该区域所产生的滴滴打车的订单数的总和。那么所谓网约车需求量预测，就是已知过去几个小时每个格点的订单数，预测未来的订单数。

基于 grid 建模数据的示意图

实际上，直接做网约车需求量预测的文章并不多，但这个问题可以归结为交通流预测，并且本文的对比算法也是交通流预测模型，在同一网约车数据集上的表现。此外，交通流预测属于城市计算问题（urban computing）Yu Zheng. 2014. Urban Computing Concepts, Methodologies, and Applications。这个概念由当时还在微软亚洲研究院的郑宇提出。与我们生活息息相关的很多问题都可以归结为城市计算问题。比如车辆调度问题，输电网优化，物流及供应链管理，雾霾预测等。它们的特点是同时具有时间和空间两个维度的信息。

问题定义

本文要解决的问题是，如何能够更好的建模多个区域之间所存在的非欧且多模态的时间和空间相关性，以实现高准确率的网约车需求量预测。

问题的数学表述如下，输入连续 $T$个时刻的格点集合$ X$（格点的值为订单数），输出下一时刻的订单数，通过训练学习得到该映射函数 $f$。

$$
[X^{t-T+1},…,X^{t}]\stackrel{f(.)}{\longrightarrow}{X^{t+1}}
$$
这里的多模态可以理解为多重维度的关系。如下图所示，图中区域1和区域2在空间上是相邻关系，他们可能会有相似的约车量。区域1和区域3在功能上是相似的，可能在用车的 pattern 上存在比较高的相似性。区域4与区域1在同一条路旁边，同理，他们也会存在某种约车的相似性。

图1:区域间不同相关性的例子。预测区域1、空间相邻区域2的需求时，认为功能相似区域3和交通连通区域4更为重要，而距离较远和不相关区域5的相关性较小。

此外，订单数还与时间紧密相关，比如早晚高峰，节假日等，会对用车数产生比较大的影响，且会呈现某种周期性。所以，作者总结了这个问题所面临的两个挑战。空间上，需要学习区域间存在的多模态非欧相关性。时间上，需要学习复杂的多个时刻的时间依赖关系。

方法

这篇论文的工作思路如下：

首先将区域间的非欧几里得两两相关编码到多个图中，然后用多图卷积（multi-graph convolution）来建模其相关性。
然后用全局上下文信息（global contextual information）来建模时序信息，并进一步提出了上下文门控循环神经网络模型（contextual gated recurrent neural network），给历史数据分配权重。

网约车需求预测，$T$个点预测1个点。
空间依赖建模上：以图的形式表示数据，从空间地理关系、区域功能相似度、区域交通连通性三个角度构造了三个不同的图，提出了多图卷积，分别用$ k$ 阶 ChebNet 对每个图做图卷积，然后将多个图的卷积结果进行聚合(sum, average 等)成一个图；
时间依赖建模上：提出了融合背景信息的 Contextual Gated RNN (CGRNN)，用 ChebNet 对每个结点卷积后，得到他们的邻居表示，即每个结点的背景信息表示，与原结点特征拼接，用一个两层全连接神经网络计算出 $T$ 个权重，将权重乘到历史 $T$个时刻的图上，对历史值进行缩放，然后用一个共享的 RNN，针对每个结点形成的长度为$T$ 的时间序列建模，得到每个结点新的时间表示。最后预测每个点的网约车需求，对比的深度学习方法有上述的 DCRNN 和 STGCN 两个，数据是北京和上海的网约车需求数据。

方法描述

（一）区域级别的网约车需求预测
将全网需求网格化，利用过去$T$个时段预测$T+1$个时段。所提出的模型ST-MGCN的系统架构如图2所示。我们将区域间三种关系类型表示为多个图，图的顶点表示区域，边表示区域间的成对关系。首先，时间上，我们使用提出的上下文门控循环神经网络(CGRNN)考虑全局上下文信息，对不同时间的观测结果进行汇总，将多个时间步融合为一个时间步。然后，空间上，应用多图卷积来捕捉区域间不同类型的相关性。最后，利用全连接层进行特征融合转化为预测。

作者基于对网约车需求量预测问题的理解以及先验知识，设计了如下的算法框架。

图2:时空多图卷积网络(ST-MGCN)系统架构。

（二）空间依赖关系建模
所谓多图卷积，是指对空间上的多种相关关系分别进行图卷积，再进行特征融合。

1.领域图: 区域的邻域是根据空间邻近度来定义的。我们通过在一个3×3的网格中将一个区域与它的8个相邻区域相连接来构造图。
$$
A_{N,ij}=\begin{cases}
1 & \text{if $v_i$ and $v_j$ are adjacent } \
0 &\text{otherwise}
\end{cases} \quad\quad (3)
$$
2.功能相似图:当预测一个地区时，很自然地会参考与这个地区在功能上相似的其他地区。区域功能可以用每个点(区域)周围的POI来描述，两个顶点(区域)之间的边定义为POI相似性:

$$
A_{S,ij}=sim(P_{vi}、P_{vj})\in[0,1] \quad\quad(4)
$$

其中$P_{vi}、P_{vj}$分别为区域$v_i和v_j$的POI向量，其维数等于POI类目数，每个条目表示区域内特定POI类目数。

3.交通连通图:在进行时空预测时，交通系统也是一个重要因素。直观地说，那些地理上遥远但又容易到达的区域可以相互关联。这种连接是由高速公路、高速公路或地铁等公共交通诱导的。在这里，我们将这些道路直接相连的区域定义为“连通”，对应的边定义为:
$$
A_{C,ij}=max(0,conn(v_i,v_j)− A_{N,ij})\in[0,1] \quad\quad(5)
$$
其中$conn(u, v)$为$v_i和v_j$之间连接性的指示函数。注意，邻域边缘被从连通图中删除，以避免冗余的相关，也会导致稀疏图。

4.利用多图卷积对时空依赖关系进行建模

利用构建的上述三种类型的图，我们使用如下公式进行卷积，$f(A;θ_i)$表示拉普拉斯矩阵。

$$
X_{l+1}=\sigma\bigg(\coprod_{A \in\mathbb A} f(A;θ_i){X}_l{W_l}\bigg) \quad\quad（6）
$$

其中$X_{l}\in{\mathbb{R}^{|V |×P_l}}$,$X_{l+1}\in{\mathbb{R}^{|V |×P_{l+1}}}$分别为$l$层和$l+1$层$|V|$区域的特征向量。其中，$\sigma$为激活函数，$\coprod$为聚合函数，如sum、max、average等。$\mathbb A$为图的集合，$f(A;θi)\in |V |×|V|$表示基于图$A\in\mathbb A$用$θ_i$参数化的不同样本的聚合矩阵，而$W_l\in\mathbb R^{P_l×P{l+1}}$表示特征变换矩阵，
在实际过程中，$f(A;θ_i)$选为拉普拉斯矩阵$L$的$K$阶多项式函数，（本文$f(A;θ_i)$中图拉普拉斯矩阵度$K=2$,$\coprod$为聚合函数为sum）图3显示了图卷积层示例。$K$表示$v_i$通过$K$步能够到达$v_j$。在卷积运算方面，$k$定义了空间特征提取时感知域的大小。

图3:集中于黑色顶点的ChebNet图卷积的示例。左:中心区域为黑色。一跳邻居被标记为黄色，而两跳邻居被标记为红色。中:随着图形拉普拉斯阶数的增加，接收场增大(绿色标记)。右:这一层的输出是带有从1到K的度值的图形变换之间的和。

每一帧数据做图卷积的方法是使用 k-ordered ChebNet。这个方法与我们熟知的图卷积网络 GCN 的区别是，GCN 可以简单地认为是 1-ordered ChebNet，只是汇聚一阶邻居。如文中给出的示意图所示。黑色是中心节点，黄色是 1阶邻居，红色是 2阶邻居。通过 k-ordered ChebConv，可以实现 $k$阶领域的信息交互。使用$k$ 层的 GCN 堆叠也可以实现 k 阶邻域信息角度，但是随着层数增加，训练难度加大。所以，这可能是作者做模型选择的考虑点之一。

基于多图卷积的空间依赖关系建模并不局限于上述三种类型的区域关系，它可以很容易地扩展到其他区域关系以及其他时空预测问题的建模。它通过区域间的关系提取特征，对空间依赖关系进行建模。在$K$较小的情况下，特征提取将重点放在较近的区域，增加$K$值或叠加多个卷积层的最大程度将增加感知域，从而鼓励模型捕获更多的全局依赖关系。

（三）时间相关的建模

即通过多步处理，将多个时间步的信息融合到一张图上。这一块比较难理解，首先解释一下维度关系。对于图4左上角的$T×|V|×P$，$T$ 代表$T$个时间步，其中每个时间步为一个方块，该方块的高即$V$代表所有的节点，宽即$P$代表每个节点graph embedding 出来的高维表示。

图4左下角和图4左上角其实是一样的数据，只不过，左下角的数据是对每个时间步加了权重，所以他画的有的方块厚有的方块薄，即所谓的channel-wise attention，而其中所使用的权重，便是根据channel-wise attention中的公式7、8、9得到的，比较复杂（公式7图卷积，公式8对图卷积结果进行池化，池化结果利用公式9得到权重）。

图4右边他说的共享权重的RNN，其实就是将多张图经过RNN融合成一张图。按道理，对于每个节点，使用过去T个时间步预测未来T+1个时间步，应该训练一个RNN，50个节点要训练50个RNN，但是文章为了简化模型，对所有节点应用一个RNN模型，右边中间的黑色方块，是把RNN展开了，代表T个时间步，最后输出一个时间步，即融合为一张图。（其实共享权重的RNN效果肯定是不如对每个节点训练一个RNN效果好的，但是文章中说了这样做的原因：区域间共享RNN是为所有区域找到一个通用的聚合规则，从而促进模型的泛化，降低模型的复杂度）

图4:使用上下文门控回归神经网络(CGRNN)进行时间相关性建模。它首先使用输入的全局平均池和每个观测的图卷积输出生成区域描述。然后将总结出的向量z转换成权重，用于缩放每个观测值。最后，应用一个跨所有区域的共享RNN层将每个区域的门控输入序列聚合到单个向量中。

详细解释：

此部分提出了一种基于上下文门控的循环神经网络(CGRNN)来模拟不同时间点下观测值之间的相关性。CGRNN利用具有上下文感知门控机制的RNN将上下文信息集成到时态建模中，其体系结构如图4所示。

首先，将相关区域的信息视为上下文信息，利用对应的图拉普拉斯矩阵，通过最大度$K’$图卷积运算$F_{\mathcal{G}}^{K’}$进行卷积(公式7)（本文$K’=1$）。上下文门控机制的设计是先进行图卷积再进行池化，以使池化操作包含拓扑信息。我们有T个时间观察，$X^{(t)}\in{\mathbb{R}^{|V |×P}}$表示第$t$个观察,其中P为特征维数，如果特征只包含阶数，P为1。

$$
\hat X^{(t)}=[X^{(t)} ,F_{\mathcal{G}}^{K’}{ X^{(t)} } ] \quad for\quad t= 1,2,…,T\quad\quad(7)
$$

pooling 操作如下所示，将 $t$时刻 graph 上所有节点的值都加起来，然后除以节点的个数。使用全局平均池化$F_{pool}$将所有节点的信息汇总为一个节点 (公式8)。
$$
z^{(t)}=F_{pool}(\hat X^{(t)})=\frac{1}{|V|}\sum_{i=1}^{|V|}\hat X^{(t)}_{i,:}\quad for\quad t= 1,2,…,T\quad\quad(8)
$$
然后利用注意力运算对向量z进行非线性变换，生成自适应权值 $s$ （公式9）, $W_1$ 和 $W_2$相应的权重, $δ,σ$是分别ReLU和sigmoid函数。

$$
s=\sigma(W_{2}{\delta}(W_{1}z)) \quad\quad(9)
$$

最后，将$s$应用于对每个时间步进行加权(公式10)。
$$
\widetilde X^{(t)}=X^{(t)} {\circ}s^{(t)} \quad for\quad t= 1,2,…,T\quad\quad(10)
$$

得到对时间步进行加权后的多张图后，使用权值共享RNN将多张图融合为一张图 (公式11);

$$
H_{i,:}=RNN( \widetilde X^{(1)}{i,:},…, \widetilde X^{(T)}{i,:};W_3)\quad for\quad i= 1,…,|V|\quad(11)
$$
经过上下文门控后，应用一个具有跨所有区域权值$W_3$的共享RNN层，将一个区域的门控输入序列聚合成一个单独的向量$H_i$。(公式11)
区域间共享RNN的直觉是为所有区域找到一个通用的聚合规则，从而促进模型的泛化，降低模型的复杂性。

小结：
将$T$个时间步的历史数据融合为一张图，这里所谓的 Contextual Gated 是指将历史数据每一帧通过图卷积网络进行数据融合，并且通过全局 pooling 得到该小时的全局信息。这个全局信息再与原来的$T$个时间步的数据做点乘，得到了带权重的历史数据。然后迭代地输入到 RNN 中进行时间维度的信息融合，最终得到一张图。这里的 RNN 是权值共享的，也就是对于图上的每个顶点都过同一个 RNN，它们的所训练的是一套参数。这样的好处有两点：1. 学习更加普遍的时序维度的汇聚方法。2. 减少模型复杂程度，使得更容易训练。

实验

实验设置

数据集

北京和上海两个真实的大规模网约车数据集上进行了实验。
这两个数据集都是在2017年3月1日至2017年12月31日这段时间内，在网约车订单的主要城市区域内收集的。
训练集：2017年3月1日至2017年7月31日。
验证集：2017年8月1日至2017年9月30日。
测试集：2017年10月1日至2017年12月31日。
POI数据收集于2017年，包含13个主要POI类别。每个区域都与一个POI向量相关联，该向量的条目是某个POI类别的实例数。道路网络数据用于交通系统的可行性评估是由OpenStreetMap提供。

基准方法

Historical Average (HA):将网约车需求建模为一个季节过程，并使用前几个季节的平均值作为预测。使用的周期是1周，预测是基于前几周同一时间的汇总数据。
LASSO,Ridge
Auto-regressive model (VAR,STAR)
Gradient boosted machine (GBM)
ST-ResNet (Zhang, Zheng, and Qi 2017)ST-ResNet是一个基于cnn的交通流预测框架。模型使用带有残差连接的CNN来捕捉趋势、周期性和紧密度信息。
- DMVST-Net (Yao et al. 2018b)DMVST-Net多视图建立深度学习方法预测出租车的需求量，它由三种不同的视图组成:时间视图、空间视图、语义视图。分别采用LSTM、CNN和嵌入图建模。
- DCRNN, ST-GCN: Both DCRNN (Li et al. 2018c) and ST-GCN (Yu, Yin, and Zhu 2018)

参数设置

在实验中，城市地图划分为大小为1km×1km的网格，生成区域集$V$。北京有1296个地区，上海有896个地区。网络的输入由5个历史观测值组成，包括3个最近时间分量、1个周期分量和1个最新的趋势分量。在构建交通连接度图时，考虑了高速公路、高速公路和地铁。只要有一条高速公路把两个地区直接连接起来，就被认为是“连通”的。
图的拉普拉斯算子与度K等于2,隐藏层数为3,每一层应用64个隐藏单元和L2正则化，权重衰减等于1e-4。CGRNN中的图的卷积度K’等于1。使用ReLU作为图卷积网络的激活。ST-MGCN的学习率设置为2e-3，并使用验证数据集上的早期停止。

实验结果及分析

实验结果

(1) 表1:网约车需求预测不同方法的性能比较。ST-MGCN在两个数据集上的所有指标都达到了最佳性能。

我们在两个数据集中观察到以下现象:
(1)基于深度学习的方法，包括ST-ResNet、DMVST-Net、ST-GCN和提出的ST-MGCN能够建模非线性时空相关性，通常优于其他基线;(2) ST-MGCN在两个数据集的所有指标方面都取得了最好的性能，在相对误差减少方面至少比第二最佳基线高出10%，这表明所提出的时空相关性建模方法的有效性;(3)与其他深度学习模型相比，ST-MGCN降低了方差。
(2) 表2:空间相关建模对北京数据集的影响。删除任何组件都会导致显著的误差增加。

-(3) 表3:在北京数据集上向现有方法添加多图形设计的效果。在原模型中加入额外的图形，可以显著降低统计误差。

进一步研究时间依赖关系建模的影响,我们评估以下的变种ST-MGCN使用不同时序建模方法,包括(1)平均池化:不同时间观察使用平均池化,(2)RNN:聚合时间观察使用递归神经网络(RNN) (3) CG:使用上下文门控但不使用RNN (4) GRNN:不使用图卷积
计算结果如表4所示。我们观察到:不同观测值的平均pooling的性能最差，而能够进行内容依赖的非线性时间聚合的RNN的性能得到了明显的改善。基于上下文门控机制的CGRNN得到了比RNN更好的结果。此外，去掉RNN (CG)或图像卷积运算(GRNN)都会导致性能明显变差，这证明了各分量的有效性。

(4) 表4:时间相关建模对北京数据集的影响
(5) 图5:图卷积的层数和多项式阶数k对北京数据集的影响。

总结

本文模型应用到了北京和上海的滴滴网约车上，实验部分不再介绍，其中的POI数据，路网数据等感觉处理起来会比较麻烦。

总的来说，本文就是先提取三张关系图，即三个不同的拉普拉斯矩阵L，再将每张关系图的多个时间步融合为一个时间步，即一张图，融合后得到只含有一个时间步的三张图，对该三张图分别进行图卷积，再将结果进行特征融合即可得到预测值。

本文提到的 k-order ChebNet 可以进行 k-hop 邻居信息汇聚的方法.

亮点

总的来说，本文就是先提取三张关系图，即三个不同的拉普拉斯矩阵L，再将每张关系图的多个时间步融合为一个时间步，即一张图，融合后得到只含有一个时间步的三张图，对该三张图分别进行图卷积，再将结果进行特征融合即可得到预测值。使用CGRNN用于时间相关性建模，同时包含了全局上下文信息。

[不足]

基于该文章的多图数据融合机制，增加高精度的降水短临预报（例如，提供分钟级、街道级降水预报的彩云天气，http://caiyunapp.com/ ）可以显著提升订单数的预测准确性。

[启发]

(1)评估所提出的模型对其他时空预测任务的影响，比如交通流、人流、雾霾预报等，以及提高模型的能力，以满足多个时间步的预测需求。;
(2)扩展了多步序列预测方法。

BibTex

@inproceedings{DBLP:conf/aaai/GengLWZYYL19,
  author    = {Xu Geng and
               Yaguang Li and
               Leye Wang and
               Lingyu Zhang and
               Qiang Yang and
               Jieping Ye and
               Yan Liu},
  title     = {Spatiotemporal Multi-Graph Convolution Network for Ride-Hailing Demand
               Forecasting},
  booktitle = {The Thirty-Third {AAAI} Conference on Artificial Intelligence, {AAAI}
               2019, The Thirty-First Innovative Applications of Artificial Intelligence
               Conference, {IAAI} 2019, The Ninth {AAAI} Symposium on Educational
               Advances in Artificial Intelligence, {EAAI} 2019, Honolulu, Hawaii,
               USA, January 27 - February 1, 2019},
  pages     = {3656--3663},
  publisher = {{AAAI} Press},
  year      = {2019},
  url       = {https://doi.org/10.1609/aaai.v33i01.33013656},
  doi       = {10.1609/aaai.v33i01.33013656},
  timestamp = {Wed, 25 Sep 2019 11:05:08 +0200},
  biburl    = {https://dblp.org/rec/conf/aaai/GengLWZYYL19.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

论文解读 | 基于时空多图卷积的交通流量预测

标题

作者

摘要

论文背景

问题定义

相关工作

1、城市计算中的时空预测

2、图卷积

3、Channel-wise attention

方法

方法描述

实验

实验设置

数据集

基准方法

参数设置

实验结果及分析

实验结果

相关知识链接

下载

基础知识

基准实验涉及的论文

方法组件涉及的论文

后续研究涉及的论文

总结

亮点

[不足]

[启发]

BibTex

刷题2 剑指 Offer — 数组和字符串

刷题1 跳台阶&暴力跳台阶&调整数组顺序

可ai多