paper title
《Predicting origin-destination ride-sourcing demand with a spatio-temporal encoder-decoder residual multi-graph convolutional network》
导读
随着移动互联网技术的快速发展，网约车服务变得越来越受欢迎，并在很大程度上改变了人们的出行方式。需求预测是网约车平台供需管理系统中最基本的组成部分之一。通过对起点-目的地(OD)需求进行准确的短期预测，这些平台可以在实时匹配、闲置车辆重新分配和拼车车辆路线等方面做出精确和及时的决策。与基于区域的需求预测相比，基于OD的需求预测更具挑战性。这主要是由于不同OD对的需求之间存在复杂的空间和时间依赖关系。为了克服这一挑战，这篇文章提出了时空编解码器残差多图卷积网络(ST-ED-RMGC)，这是一种新的深度学习模型，用于预测不同OD对的乘车需求。该模型首先构造OD图，利用邻接矩阵来刻画不同OD对之间的非欧几里得成对的地理和语义相关性。其次，在构造的图的基础上，利用残差多图卷积(RMGC)网络对上下文感知的空间依赖进行编码，用长短期记忆(LSTM)网络将时间依赖性编码到稠密向量空间。最后，利用RMGC网络将压缩后的向量解码成OD图，并对未来OD需求进行预测。通过在纽约市曼哈顿的出租车数据集上进行的大量实验，提出的深度学习框架比最新的深度学习框架要好。
问题定义
（1）区域划分：在这篇文章中，根据下图所示的行政邮政编码，将纽约市曼哈顿划分为不同的不规则区域。在时间间隔上一天被平均划分为几个间隔(例如，24小时)。目标是在每个时间间隔内同时预测不同OD对的需求量。
（2）OD图：与传统的交通网络图中每个顶点代表一个交叉口或一个区域不同，本文构造了一个特定的OD图G=(V，E，A)，其中该图的每个顶点指的是一个OD对，如图所示。V是OD对的集合，N=|V|是每个时间间隔中的OD对的数量，E表示边的集合，并且A∈RN×N定义相邻矩阵，其元素表示顶点(即OD对)之间的连接。在这里，OD图是完全连接的，这表明任意两个OD对的边都存在连接。
（3）特征：设图片表示在第d天的时间间隔t的第i个OD对中的乘客需求(请求订单量)，其中i∈V(OD对的集合)，图片∈R+。设图片表示在第d天的时间间隔t的所有OD对中的乘客需求。为了预测图片，可以使用第d天的时间间隔t之前的所有OD需求作为特征。然而，由于计算资源的限制，将所有的历史OD需求都输入到模型中是不必要的，也是不可行的。考虑主要有两种时间相依性：趋势性(需求受过去几个区间的历史需求影响)和周期性(需求在几天和几周内重复类似的模式)。有了这些知识，构造以下历史数据的特征：
1）基于趋势的特征：OD图中最近两个时间间隔的需求
2）基于周期的一天内特征：前一天相同时间间隔的OD图中的需求
3）基于周期的一周内特征：OD图中上周同一天同一时间间隔的需求。
（4）问题定义：学习函数f(∙)：RN×T→RN，该函数将OD图上所有OD对的历史需求映射到下一个时间间隔内同一OD图上的所有OD对的需求：
模型方法
下图简要展示了提出的ST-ED-RMGC模型的体系结构，该模型使用编码器-解码器框架。有两个编码器：一个空间编码器和一个时间编码器。空间编码器利用多个RMGC从不同的角度对OD对之间的空间相关性(包括地理距离、功能相似性和移动性模式相关性)进行建模。时间编码器提出了一种空间LSTM模型来学习每个OD对的时间相关性。为了将空间和时间模型融合在一个端到端的学习框架中，将两个解码器的输出平坦化为两个稠密紧邻向量，然后将这两个向量连接起来。最后，在解码器部分，利用多个RMGC网络将压缩后的向量转换回OD图，用于预测目标OD需求。
模拟OD对之间的空间相关性：
本小节为多图建模，并定义相应的相邻矩阵。为了准确地预测OD需求，该模型使用OD对相关性的测量值，通过空间上相关OD对的历史需求数据来校准OD需求。这意味着探索OD对之间在地理和语义上的内在关系是至关重要的。从地理角度来看，如果两个OD对的始发地/目的地彼此相邻，我们自然可以预期这两个OD对的需求具有很强的相关性(因为需求可能源自共同的公交站、购物中心或小区等)。这促使我们设计一个邻里关系图，以指示起点或终点中是否有两个彼此相邻。我们还预计，具有较近起点或/和目的地的两个OD对的需求具有相对较强的相关性，这促使我们构造一个相邻矩阵，分别描述两个OD对起点和目的地质心之间的距离。从语义上看，一般认为两个功能相近的OD对(如商业区、娱乐区、住宅区)的需求往往有很强的关联性。此外，可以直观地预期，具有相似历史需求模式的OD对在未来将呈现类似的需求模式。因此，四种类型的相邻矩阵的定义如下：(1)邻域关系图Gn(V，E，An)，An∈RN×N；(2) 功能相似性图GF(V，E，Af)，Af∈RN×N；(3)质心距离图Gd(V，E，Ad)，Ad∈RN×N；(4)移动模式关联图GC(V，E，Ac)，Ac∈RN×N。
（1）邻域关系图。OD对中具有相邻起点或终点的需求更有可能具有相似的模式。文章定义两个相邻的矩阵来分别指示两个OD对是否具有相邻的起点或终点：
（2）功能相似图。城市中的不同区域可能具有不同的功能或土地使用属性。一些是商业区，有许多购物中心和饭店，一些是带公园的旅游区，有些是充满部门和房屋的住宅区。这篇文章中，使用土地属性来定义曼哈顿区域的功能。选择的属性涉及没有汽车的家庭，房屋密度，人口密度，就业密度，道路密度以及到最近公交站的平均距离，这与土地使用类型和出行方式的选择高度相关。由于行政区域具有不同的区域，因此将所有这些度量除以相应区域的面积。可以构建两个功能相似的相邻矩阵：
（3）质心距离图。由于不同大小的不规则区域，进一步引入两个质心距离图来表示OD对之间的地理关系。区域质心之间的直线距离（距离越短，关系越强），如下所示：
Haversine（∙）函数用于测量地球上两个位置之间的直线距离
（4）移动模式关联图。直觉上，具有类似移动性模式（历史需求趋势）的OD对共享一些相同的特征，因此可以相互指导预测。然后，移动模式相关图的相邻矩阵由下式表示：
其中Cov（∙，∙）计算两个向量之间的协方差，而var（∙）计算一个向量的方差。
残差多图卷积（RMGC）网络
接下来介绍结合多图卷积网络和残差模块的RMGC网络，以捕获OD对之间的空间相关性。在模型中，RMGC网络的基础是GCN，它是空间特征编码的主要工具。为了解决多图问题，通过重塑GCN层的架构来设计MGC网络。MGC充当此空间特征编码器的基本组件。然后，在深度学习网络中堆叠多个MGC层以提高训练性能，并引入残差网络以解决梯度爆炸问题，该问题构成了RMGC块。这种基于RMGC的编码器的输出是通过多层RMGC块生成的，并且被展平为一个一维特征。接下来，详细扩展上述RMGC网络的原理和结构。
在本文中，使用基于频谱的方法来构建基本的GCN模型，该模型实质上将原始图形信号（图形上的原始特征）映射到参数化的傅里叶域。然而，训练参数在计算上是昂贵的。为了解决这个问题，引入了切比雪夫多项式展开式（最高K阶）以获得有效逼近，后来，进一步将频谱滤波器简化为K = 1的切比雪夫多项式。后来的模型也称为一阶切比雪夫，具有以下形式：
接下来，为了能够从多个图形中学习，设计了如下图所示的训练架构。假设有K个相邻矩阵，并且让Ak∈RN×N表示第k个邻接矩阵，k∊ {1，⋯，K }。在批量大小为B的每个训练批次中，首先将每个邻接矩阵复制B次，然后将它们连接成张量A∈RB×（N * K）×N。给定输入和输出特征的维分别为F和O，则得到输入张量Hl∈RB×N×F，可学习权重矩阵W∈R（K * F）×O和输出张量Hl + 1∈RB×N×O。为了将输入张量H1映射到输出张量Hl + 1，首先在A¨和H1之间进行批处理，生成一个张量M∈RB×（N * K）×F。然后将生成的张量M重整为新的张量M∈RB×N×（F * K），最后M和W的批点积产生输出张量Hl + 1∈RB×N×O。
然后，为了在不遭受梯度爆炸的情况下在深层神经网络结构中训练网络，开发两种基于多图卷积网络（基于MGC）的残差块。一种在捷径上添加一个MGC，另外一种在捷径上不添加MGC。基本残差单位由下式表示：
其中，右侧的第一项指的是捷径，第二项指的是主路径。值得注意的是，通常的做法是在主路径中堆叠多个MGC层。此外，在输入张量H1和输出张量H1+1之间需要不同的特征维度的情况下，可以将MGC层添加到快捷路径以保持特征维度的一致性(如图)。这种残差块称为卷积块。
构造RMGC之后，堆叠多个两种模块，并将输出展平为具有一维特征的潜矢量，作为此RMGC编码器的最终输出：
其中，L1的维度为B×V1，其中B是批次大小，V1是RMGC编码器的潜在特征维度。
空间LSTM
本小节介绍了空间LSTM编码器，它主要捕获了时间特征。与常规LSTM稍有不同，本文中的空间LSTM需要同时处理具有空间和时间信息的输入张量。为此，文章开发了空间LSTM，它是编码器的一部分，其技术细节如下所示。
LSTM作为递归神经网络，被广泛用于许多交通需求预测问题中。在大多数以前的研究中，将一个区域或一个路段的历史特征作为输入，并预测下一个时间间隔对该区域或路段的需求。在这篇文章中，为了以一种更明智的方式将空间和时间模型整合到一个端到端的学习框架中，提出了一种空间LSTM，它从所有OD对中学习特征，并将高层信息输出到潜在向量中，而不是对每个OD对使用各种单独的LSTM。特征X的输入具有B×N×F的形状，即X∈RB×N×F，其中B是批处理大小，F是用于提取历史特征的切片窗口数。在RMGC编码器中，将F个历史观测值（即所有OD对随时间的需求）视为特征；OD对的数量（即N）是输出张量的目标尺寸。但是，使用空间LSTM训练时间序列数据，空间节点的信息应成为特征。因此，空间LSTM首先通过移置X的第二维和第三维来重塑X，从而形成形状为B×F×N的新张量X，即X∈RB×F×N。使用X作为输入张量，LSTM将F的第二维视为时间维，将N的第三维视为特征维。换句话说，所有OD对中的历史需求都被视为馈送到一个LSTM中的特征。
构建空间LSTM模块后，堆叠多个LSTM模块并将输出张量展平为潜矢量：
其中，L2具有B×V2的维度，其中V2是空间LSTM编码器的潜在特征维度
融合
文章只将上述两个编码器的输出串联在一起就可以将它们融合在一起：
潜向量L包含历史需求的时空特征。为了预测未来的OD需求，首先引入一个中间层，以将向量L的维数扩展为形状为B×N的新向量，然后，将新矢量重塑为形状为B×N×1的张量，这成为RMGC的有效输入格式。通过堆叠RMGC模块，最终可以在OD图上获得所有OD对的估计需求。形式上，解码器架构可以由
损失函数：
模型配置
在编码器中，文章堆叠了一个RMGC卷积块和一个RMGC标识块。RMGC卷积块的主路径包含三个MGC层(具有32、32、128个隐藏单元)，而快捷路径包含一个MGC层(具有128个隐藏单元)。RMGC标识块具有包含三个MGC层(具有32、32、128个隐藏单元)的主路径。另一方面，时间编码器包括两个LSTM层，分别具有128和64个隐藏单元。RMGC和LSTM编码器的输出被平坦化，然后分别变换成两个维数分别为900和100的潜在向量。解码器使用一个RMGC卷积块，然后使用一个RMGC标识块，具有与编码器中相同的设置，随后是生成估计OD需求的MGC层。隐藏层中的所有激活都是Relu函数，而最后输出中的激活函数是线性函数。模型中使用的优化器是Adam，学习率为5e-5，衰减率为1e-6。在训练阶段，将批大小设置为32。
创新点
（1）通过构造多个OD图来刻画不同OD对之间的成对关系，包括基于起点和终点的邻域关系图、基于起点和终点的功能相似图、基于起点和终点的距离图以及移动模式关联图。
（2）提出了一种新的深度学习模型，该模型具有良好的编解码器结构，既能模拟不同OD对之间的空间依赖关系，又能模拟OD对本身的时间依赖关系。该结构在端到端的学习框架中学习空间和时间特征。
