交通预见未来(18): 基于时空多图卷积网络的网约车需求预测
1、文章信息《Spatiotemporal Multi-Graph Convolution Network for Ride-hailing Demand Forecasting》。
2019 AAAI大会的一篇论文，被引5次。
2、摘要区域级需求预测是网约车服务的一项重要任务。区域间具有复杂的时空依赖性，现有的方法主要侧重于对空间相邻区域之间的欧式相关关系进行建模，而我们发现，距离可能较远的区域之间的非欧式相关关系对于准确预测也至关重要。为此本文提出了时空多图卷积网络(ST-MGCN)。首先将区域间的非欧式成对相关关系编码为多个图，然后利用多图卷积对这些相关关系进行建模。为了利用全局上下文信息对时间相关性进行建模，我们进一步提出了上下文门控循环神经网络，该网络利用上下文感知的门控机制对不同的历史观测值进行重新加权。我们在两个真实的大型网约车需求数据集上评估了所提出的模型，与最先进的基准模型相比，该模型提高了10%以上。
3、简介区域级网约车需求预测的目标是根据历史观测，预测城市区域未来的需求。这一任务的挑战性主要在于复杂的时空相关性。一方面，不同区域之间存在复杂的依赖关系。例如，一个区域的需求通常受其空间相邻邻居的影响，同时与具有相似上下文环境的遥远区域相关。另一方面，不同的时间观测值之间也存在非线性依赖关系。对某一时刻的预测通常与各种历史观测结果相关联，如一小时前、一天前甚至一周前。
在时空相关性建模中，有两个重要的方面被忽略了。首先，这些方法主要针对不同区域间的欧氏相关关系进行建模，但我们发现非欧氏两两相关关系对准确预测也至关重要。图1显示了一个示例。对于区域1，除了邻域2，它还可能与一个遥远的区域3相关具有相似功能的，即，它们都在学校和医院附近。此外，区域1还可能受到区域4的影响，区域4通过公路与区域1直接相连。其次，在这些方法中，当使用RNN对时间相关性进行建模时，每个区域都是独立处理的，或者只基于局部信息。然而，我们认为全局和上下文信息也很重要。例如，全局网约车需求的增加/减少通常表明一些事件的发生，这些事件将影响未来的需求。
为了解决这些问题，我们提出了一种新的深度学习模型，称为时空多图卷积网络(ST-MGCN)。主要贡献如下：
在网约车需求预测中，我们识别出区域间的非欧式相关关系，并提出使用多个图对其进行编码。然后，我们进一步利用提出的多图卷积来显式地建模这些相关性。
提出了基于上下文门控的RNN (CGRNN)模型，在时序依赖关系建模时引入全局上下文信息。
4、文献综述（1）城市计算中的时空预测
非欧式结构化数据也存在于城市计算中。通常，基于站点的预测任务，比如基于站点的出租车需求预测，基于站点的自行车流量预测，是非欧式的，因为数据格式不再是矩阵，卷积神经网络变得不那么有用了。人工特征工程或图卷积网络是处理非欧式结构数据的最新技术。与以往的研究不同，ST-MGCN将区域间的成对关系编码为语义图。虽然ST-MGCN是为基于区域的预测而设计的，但区域间关系的不规则性使其成为非欧式数据的预测问题。然而，这些方法都没有明确地对区域间的非欧式成对关系建模。在这项工作中，ST-MGCN利用提出的多图卷积融合相关区域的特征，能够从不同角度关联区域的需求值进行预测。
（2）图卷积
（3）Channel-wise attention对channel做注意力机制
Channel-wise attention提出的初衷是学习每个channel的权重，以便找到最重要的channel，并通过给出更高的权重来强调它们。
Fpool是一个全局平均池化操作，它将每个通道总结为一个标量Zc，其中c是通道索引。然后利用注意力运算对向量z进行非线性变换，生成自适应权值s, W1和W2相应的权重,δσ是分别ReLU和sigmoid函数。然后，通过channel方向的点积将权值s应用于输入。最后，基于学习权值对输入通道进行缩放。在本文中，我们采用了Channel-wise attention的思想，并将其推广到一系列图之间的时间依赖关系建模中。
5、主体内容（一）区域级别的网约车需求预测
将全网需求网格化，利用过去T个时段预测T+1个时段。所提出的模型ST-MGCN的系统架构如图2所示。我们将区域间三种关系类型表示为多个图，图的顶点表示区域，边表示区域间的成对关系。首先，时间上，我们使用提出的上下文门控循环神经网络(CGRNN)考虑全局上下文信息，对不同时间的观测结果进行汇总，将多个时间步融合为一个时间步。然后，空间上，应用多图卷积来捕捉区域间不同类型的相关性。最后，利用全连接层进行特征融合转化为预测。
（二）空间依赖关系建模
所谓多图卷积，是指对空间上的多种相关关系分别进行图卷积，再进行特征融合。
在本节中，我们将展示如何使用多个图来编码区域之间不同类型的相关性，以及如何使用所提出的多图卷积来对这些关系建模。我们用图对区域间的三种相关性进行了建模，包括(1)邻域图，编码空间邻近性，(2)区域功能相似图，它对区域周围兴趣点的相似性进行编码，(3)交通连通性图，它编码了遥远地区之间的连通性。
（1）领域图
区域的邻域是根据空间邻近性来定义的。我们在一个3×3的网格中，将一个区域与其相邻的8个区域连接起来，构造出图形。
（2）功能相似图
在对一个区域进行预测时，可以直观地参考与此区域功能类似的其他区域。区域功能可以用其周围每个类别的POIs来表征，两个顶点(区域)之间的边定义为POI相似性:
Pvi和Pvj分别为区域vi和vj的POI向量，其维数等于POI类别的数量，每个条目表示区域内特定POI类别的数量。
（3）交通连通性图
在进行时空预测时，交通系统也是一个重要因素。直观地说，那些地理上遥远但方便到达的区域可以相互关联。这些连接是由高速公路、高速公路或地铁等公共交通诱导的。这里，我们将这些道路直接相连的区域定义为“连通”，对应的边定义为:
为vi与vj之间连通性的指标函数。注意，为了避免冗余关联，邻域图被从连通图中删除，这也会导致稀疏图。
（4）利用多图卷积对时空依赖关系进行建模
利用构建的上述三种类型的图，我们使用如下公式进行卷积，f(A;θi)表示健忘的太阳矩阵。
在实际过程中，f(A;θi)选为健忘的太阳算子L的K阶多项式函数，图3显示了图卷积层示例。K表示vi通过K步能够到达vj。在卷积运算方面，k定义了空间特征提取时感知域的大小。
基于多图卷积的空间依赖关系建模并不局限于上述三种类型的区域关系，它可以很容易地扩展到其他区域关系以及其他时空预测问题的建模。它通过区域间的关系提取特征，对空间依赖关系进行建模。在K较小的情况下，特征提取将重点放在较近的区域，增加K值或叠加多个卷积层的最大程度将增加感知域，从而鼓励模型捕获更多的全局依赖关系。
（三）时间相关的建模
即通过多步处理，将多个时间步的信息融合到一张图上。这一块比较难理解，首先解释一下维度关系。对于图4左上角的T×|V|×P，T 代表T个时间步，其中每个时间步为一个方块，该方块的高即V代表所有的节点，宽即P代表每个节点graph embedding 出来的高维表示。
图4左下角和图4左上角其实是一样的数据，只不过，左下角的数据是对每个时间步加了权重，所以他画的有的方块厚有的方块薄，即所谓的channel-wise attention，而其中所使用的权重，便是根据channel-wise attention中的公式6、7、8得到的，比较复杂（公式6图卷积，公式7对图卷积结果进行池化，池化结果利用公式8得到权重）。
图4右边他说的共享权重的RNN，其实就是将多张图经过RNN融合成一张图。按道理，对于每个节点，使用过去T个时间步预测未来T+1个时间步，应该训练一个RNN，50个节点要训练50个RNN，但是文章为了简化模型，对所有节点应用一个RNN模型，右边中间的黑色方块，是把RNN展开了，代表T个时间步，最后输出一个时间步，即融合为一张图。（其实共享权重的RNN效果肯定是不如对每个节点训练一个RNN效果好的，但是文章中说了这样做的原因：区域间共享RNN是为所有区域找到一个通用的聚合规则，从而促进模型的泛化，降低模型的复杂度）
下面对此部分详细解释。
此部分提出了一种基于上下文门控的循环神经网络(CGRNN)来模拟不同时间点下观测值之间的相关性。CGRNN利用具有上下文感知门控机制的RNN将上下文信息集成到时态建模中，其体系结构如图4所示。
首先，将相关区域的信息视为上下文信息，利用对应的图健忘的太阳矩阵，通过K阶图卷积运算进行卷积(公式6)。上下文门控机制的设计是先进行图卷积再进行池化，以使池化操作包含拓扑信息。
其次，我们使用全局平均池化Fpool将所有节点的信息汇总为一个节点 (公式7)。
然后利用注意力运算对向量z进行非线性变换，生成自适应权值s （公式8）, W1和W2相应的权重,δσ是分别ReLU和sigmoid函数。
最后，将s应用于对每个时间步进行加权(公式9)。
得到对时间步进行加权后的多张图后，使用权值共享RNN将多张图融合为一张图 (公式10); 区域间共享RNN是为所有区域找到一个通用的聚合规则，从而促进模型的泛化，降低模型的复杂度。
6、总结展望本文模型应用到了北京和上海的滴滴网约车上，实验部分不再介绍，其中的POI数据，路网数据等感觉处理起来会比较麻烦。
总的来说，本文就是先提取三张关系图，即三个不同的健忘的太阳矩阵L，再将每张关系图的多个时间步融合为一个时间步，即一张图，融合后得到只含有一个时间步的三张图，对该三张图分别进行图卷积，再将结果进行特征融合即可得到预测值。
在未来的工作中，我们计划研究以下几个方面:(1)评估所提出的模型对其他时空预测任务的影响;(2)扩展了多步序列预测方法。
关注微信公众号《当交通遇上机器学习》，
后台回复“数据”即可获取高达175G的四个月的滴滴GPS数据和滴滴订单数据的获取方式，以及从数据处理（Oracle数据库）、模型构建（机器学习）、编程实现（python）到可视化（ArcGIS）等一系列视频教程。
后台回复“纽约”获取美国纽约10年的出租车轨迹数据以及7年的共享单车轨迹数据下载地址。
后台回复“芝加哥”获取美国芝加哥6年的共享单车轨迹数据下载地址。
后台回复“加州”获取美国加州近20年的交通流量监测数据下载地址。
公众号以交通大数据为主线，专注于人工智能、机器学习、深度学习在道路交通和轨道交通领域内的科研前沿与应用，在交通大数据与机器学习的道路上越走越远！