面向出租车需求预测的多因素时空图卷积网络

路民超，李建波，逄俊杰，李 英，董学士

青岛大学 计算机科学技术学院，山东 青岛266071

1 引言

在城市计算宏观框架下，智能交通是重要的组成部分。而智能交通系统中最重要的任务之一就是如何精确地预测未来出租车需求。精确地预测出租车需求能够帮助出租车公司合理地分配出租车资源，减少司机和乘客的等待时间，从而实现出租车资源的供需平衡并缓解交通拥塞。

然而，出租车需求预测问题具有多重时空依赖性，因而解决这一问题充满挑战性。一方面，出租车需求会受多个历史序列的影响。区域的出租车需求与邻近几个时刻的需求密切相关并伴有周期性变化规律。与此同时，区域的历史流入量也会影响未来的出租车需求。一旦乘客乘坐出租车到达目标区域，那么乘客在未来就有可能乘坐出租车从目标区域离开。另一方面，目标区域的出租车需求也存在多种空间依赖关系。从真实数据中可观察到空间上相近的区域间具有较多的出租车流和相似的需求模式。目标区域的出租车需求也会受到具有潜在空间依赖性区域的影响而发生改变。这些区域在空间上可能并不接近。举例来说，工作日早高峰，居民区会产生大量去往工作区出租车请求，而在晚上下班时，居民区则会涌现大量来自工作区的出租车流。在这种情境下，如何有效捕捉问题的多重时空依赖性已成为精确预测未来出租车需求的关键所在。

交通预测包括交通流预测、出租车需求预测（本文工作）等交通数据预测问题。这些问题具有相似的时空依赖性，因而交通预测的研究能提供相当有价值的参考信息。目前，研究者已提出一系列工作用于捕捉各种依赖关系。按照其实现方法大致可分成三类：时间序列方法，如差分整合移动平均自回归（ARIMA）模型及其变体[1-2]；机器学习方法，如线性回归（LR）[3]、支持向量回归（SVR）[4-5]；深度学习方法，如卷积神经网络（CNN）[6-7]，全连接神经网络（FNN）[8-9]，长短时记忆网络（LSTM）[10-11]。近几年，学者[12-14]大多利用CNN和LSTM结合的方法预测交通，因为其能有效捕捉复杂的时空依赖性。然而，在现实世界中，城市区域的大小并不固定。虽然CNN能从规则的二维网格中提取深层的空间特征，但并不适合处理图结构数据。因而，一些工作[15-16]尝试用图卷积网络（GCNN）解决这一问题。例如，Chu 等[16]把城市交通网络建模成交通图结构，进而提出FlowFlexDP模型，将GCNN部署于空间轴，从而捕捉图中顶点间的空间依赖性。然而，大多数研究忽视了潜在空间依赖关系和历史流入量的影响，但这两种因素可能更加重要。

针对上述问题，本文提出多因素融合的时空卷积网（MFSTGCN）用于出租车需求预测。MFSTGCN模型从出租车轨迹中提取目标区域的历史出租车流入量序列、历史出租车需求序列以建模多重时间依赖性。与此同时，基于区域真实的地理分布以及目标区域每天的出租车需求总量，MFSTGCN模型通过构建区域间地理邻接矩阵和潜在依赖性邻接矩阵，来建模多重空间依赖关系。随后，MFSTGCN 模型以时空卷积块为基础，构建临近需求组件、日需求组件、潜在空间依赖性组件和历史出租车流入量组件，从而有效捕捉问题的多重时空依赖性。

2 出租车需求预测框架

2.1 出租车需求预测问题预定义

本文将城市定义为无向无权重图G=(V,E,A),V表示区域的集合，城市中的区域是图中的顶点。假定共有m个区域，则区域集可定义为V={v1,v2,…,vm},E代表区域间的连通性，区域间的邻接矩阵用A={Aadj,Arel}表示。其中Aadj∈Rm×m为地理邻接矩阵，Arel∈Rm×m为潜在依赖关系邻接矩阵。每个区域的出租车需求划分成τ个等长的时间间隔，则时间集可定义为I={i1,i2,…,iτ}。时间间隔设定为30 min。为了方便表示，在论文的剩余部分，vs和it分别用s和t表示。令表示出租车需求，即，在s区域t时刻请求出租车的乘客数量，则Xt={}为所有区域t时刻形成的出租车需求集。相似地，t时刻s区域的历史流入量即乘客在过去时刻从其他区域出发在t时刻到达s区域的数量。在t时刻，所有区域的历史流入量序列Pt为Pt={}。

基于历史出租车需求序列和历史区域流入量序列，本文的目标是在图G上学习一个映射函数h(⋅)，通过h(⋅)将数据输入映射为下个时刻所有区域出租车需求量的预测值。

2.2 出租车需求的多重时空依赖性

本节将会给出如何建模问题多重时空依赖性的细节性描述，包括局部空间依赖性、潜在空间依赖性，以及历史流入量序列，历史需求序列与未来出租车需求之间的时间依赖性。

2.2.1 局部空间依赖性

Tobler 等[17]通过研究地理事物相关性现象，得出地理上相近的事物往往关系更密切（地理学第一定律）的结论。与此同时，在真实数据中也观察到类似现象。如图1所示，空间上相邻的区域间存在较大的出租车往来流。大量的往来出租车流意味相邻的区域间具有较为密切的关系。受这一结论和现象的启发，依照真实空间邻接关系建立地理邻接矩阵以建模周围区域对于目标区域出租车需求的影响。具体来说，对于任意区域i和j，若它们在空间上相邻，设置为1，否则设置为0。通过这种方式，建立地理邻接矩阵Aadj：

2.2.2 潜在空间依赖性

表1～表3 分别展现了不同数据集中不相邻区域间出租车需求的互相关性（d、e、f 表示三个不同的区域）。从表中可知，不相邻区域间的出租车需求具有不同的相关性。部分区域间的出租车需求存在强相关性。这表明，存在一些与目标区域空间上不相邻的区域，其出租车需求会影响目标区域未来时刻出租车需求的变化，即不同区域间出租车需求存在潜在空间依赖性。

图1 相邻区域间往来出租车流

表1 曼哈顿区不相邻区域间出租车需求的互相关性

表2 布鲁克林区不相邻区域间出租车需求的互相关性

表3 海口市不相邻区域间出租车需求的互相关性

鉴于此，建立区域间潜在依赖邻接矩阵Arel建模区域间潜在空间依赖性。其中，Arel的每个元素值arel是由区域间相关性值和给定的阈值共同决定。具体来说，首先计算每个区域每天的出租车需求量，然后利用皮尔逊相关系数计算任意两个区域间的相关性值，并设定阈值δ。对于任意区域i,j，如果区域间相关性值大于δ，元素设置为1，否则被设置为0。形式化表达如下：

其中，Qi,Qj为区域i,j各自的每日出租车需求总量，corr(⋅)为皮尔逊相关系数的计算函数。

图2 区域出租车需求序列自相关性

2.2.3 历史需求序列与未来出租车需求的时间依赖性

出租车需求预测问题是典型的时空预测问题，临近时刻的出租车需求会影响目标区域未来的出租车需求。从图2中可以看出，区域的出租车需求与其临近时刻的出租车需求存在明显的相关性，并且相关性值会随着时间上的相邻程度发生改变。而且，通过分析区域每周出租车需求变化趋势，发现区域的出租车需求具有日周期性变化规律。正如图3 所示，在工作日，每天的出租车需求具有非常相似的变化曲线。即区域的出租车需求在上午到达最高峰，在午夜到达低谷。为了建模问题的日周期性和临近时刻的时间依赖性，MFSTGCN从出租车轨迹中抽取并建立日出租车需求序列和临近出租车需求序列。在t时刻两种序列集分别表示为{Xt-Oday×dayslot,…,Xt-dayslot} ，{Xt-Orecent+1,…,Xt} 。其中，Orecent和Oday分别为两种序列的长度。

2.2.4 历史流入量序列与未来出租车需求的时间依赖性

从时间角度上看，区域的出租车需求不仅受其历史需求序列的影响，而且依赖于区域的出租车历史流入量数据。出租车的流入流出量在一定程度反映了区域人流量的变化情况。而区域人流量的变化会促使区域未来的出租车需求量发生改变。特别是当一个区域涌入大量的乘客后，随着时间的推移，这些乘客在未来有很大的可能性乘坐出租车从该区域离开。正如图4所示，区域出租车需求量的快速增加和需求峰值出现于区域出租车流入量的增加之后，这说明随着流入该区域的出租车量增多，未来时刻的出租车需求会受到人流量增加的影响而增加。因此，本文依据出租车轨迹数据的下车位置以及下车时刻建立区域的历史流入量序列{Pt-Oin+1,…,Pt}，建模历史流入量对于未来出租车需求的影响，其中Oin是历史流入量序列的长度。

图3 出租车需求的周期性变化规律

图4 区域的出租车流入流出量

图5 MFSTGCN模型

图6 时空卷积块结构

2.3 MFSTGCN模型

本文提出MFSTGCN 模型用于出租车需求预测问题。如图5 所示，MFSTGCN 模型包括四个组件分别用于捕捉临近需求序列、日需求序列、历史流入量序列与未来出租车需求的时间依赖关系以及区域间潜在依赖关系对于该问题的影响。模型的四个组件具有完全相同的结构，由时空卷积块和输出层构成。

2.3.1 时空卷积块

经过上文的分析可知，出租车需求存在复杂的多重时空依赖性。而GCN 已广泛用于提取交通图结构数据在空间域的空间特征。在时间域，长短时记忆网络（LSTM）是多数的选择，但LSTM存在复杂的门控机制，这会带来耗时的迭代训练过程以及动态响应慢等问题。为了避免这些问题，Yu等[18]将CNN应用于时间域，并提出时空卷积块结构，从而在有效捕捉复杂时空依赖性的基础上实现模型的快速训练以及高效响应动态变化等。

鉴于基于时空卷积块（ST-Conv block）捕捉时空依赖性的优势，本文采用时空卷积块作为构建MFSTGCN模型的基础。ST-Conv block 的结构如图6 所示，包括两个时间门控卷积层和空间图卷积层，分别用于学习时间和空间依赖性。其中，时间门控卷积层由1维CNN和门控线性单元（GLU）组成。模型的输入X ∈Rm×O×Cin（m、O、Cin分别表示顶点数、时间步的长度、输入通道数）传入长度为Kw的一维卷积去捕捉相邻时间片对于当前时间片值的影响。在本文中，一维卷积的运算采用不填充的方式，因此，数据序列的长度会缩减Kw-1。定义一维卷积的卷积核为Γ ∈R1×Kw×Cin×2Cout，通过卷积运算将输入X 映射为单一输出[Y1,Y2]∈Rm×(O-Kw+1)×(2Cout)（其中Y1,Y2具有完全相同的维度）。将划分得到的Y1∈Rm×(O-Kw+1)×Cout和Y2∈Rm×(O-Kw+1)×Cout两个张量放入GLU中进一步提高模型学习非线性的能力。时间门控卷积层的计算公式如下：

之后，时间门控卷积层的输出Z传入到空间图卷积层中建模问题的空间依赖性。其中，图卷积的计算是采用谱图卷积的方法。该方法是对图的拉普拉斯矩阵L特征分解，以达到捕捉图结构数据空间依赖性的目的：

其中，U,Λ ∈Rm×m分别是归一化图拉普拉斯矩阵L 分解后的特征向量矩阵和特征值对角矩阵。gθ(Λ)=diag(θ)，θ 是通过训练网络得到的傅里叶系数向量。 A是关系邻接矩阵（在模型的区域潜在相关性组件中，A=Arel，在其他组件中，A=Aadj），D 是对角度矩阵，Dii=，Im∈Rm×m是单位矩阵。然而，随着图中节点数目的增多，图拉普拉斯矩阵特征分解过程的计算复杂度随之增加。鉴于此，模型应用K阶切比雪夫多项式近似求解，从而避免图拉普拉斯矩阵的分解过程，降低模型的计算复杂度：

其中，K是超参数，决定图卷积感受野的范围。θk为k阶的切比雪夫多项式系数，Tk(L͂)为kth阶的切比雪夫多项式。λmax为图拉普拉斯矩阵L 的最大特征值。经过谱图卷积的处理之后，空间图卷积层的输出放入到一层时间门控卷积层以实现空间图卷积层与时间门控卷积层间空间状态的快速传播并获得时空卷积块的输出X′∈Rm×(O-2(Kw-1))×C′out，完整的时空卷积块处理过程如下：

2.3.2 预测

每个组件的底部部署具有相同结构的输出层来获得组件最后的输出。输出层是由时间门控卷积层和全连接层构成。其中，时间门控卷积层将时空卷积块的输出映射为单步预测值X″∈Rm×1×C。而全连接层将单步预测值X″ 转化为每个组件最后的潜在时空表达y ∈Rm×1×1。之后，MFSTCGN 模型融合每个组件的潜在时空表达，从而生成下一时刻所有区域的出租车需求预测值：

其中，yadj,yday,yrel,ypast分别是临近序列组件，日序列组件，区域潜在相关性组件，历史流入量序列组件的潜在时空表达。

3 实验与结果分析

3.1 实验数据与评价指标

实验数据来自纽约城布鲁克林区，曼哈顿区FHV出租车以及海口市网约车数据集。其中，布鲁克林区数据范围从2018年1月1日到2018年3月31日，曼哈顿区数据范围从2018年5月1日到2018年7月31日，海口市数据范围从2017 年5 月1 日到2017 年7 月31 日。本文对缺失数据进行过滤，过滤后数据分别包含10 370 740、17 950 316、3 984 359 条轨迹记录。为了评估模型的表现，实验采用交通预测领域最常用的三个评估指标：均方根误差（RMSE），平均绝对误差（MAE），平均绝对百分比误差（MAPE）。具体地，三个指标计算公式如下所示：

其中，ζ为测试集样本数，Xt+1、分别为t+1 时刻的真实值和预测值。

3.2 预处理

城市区域的划分不是本文的研究重点，因而并未进一步地研究区域的选择问题。对于纽约市数据集，将纽约出租车和豪华轿车委员会提供的出租车区域图中的真实区域作为实验的目标区域，如图7 所示，布鲁克林区和曼哈顿区分别包括61 个区域和63 个区域（排除6个与其他区域空间不相邻的区域）。对于海口市数据集，追随Xu 等[19]采用的区域划分方法，利用geohash 库编码经纬度信息并获得最终要预测的区域。在本文中，设置geohash 的精度为6，从而将海口市划分出35 个区域。另外，上述数据集中的每个区域依据其索引值或编码值顺序排列并建立区域间的地理邻接矩阵和潜在依赖邻接矩阵。为了更好地训练MFSTGCN模型，在模型训练阶段对历史出租车需求和历史流入量序列进行z-score标准化操作。利用生成的模型进行预测评估时，再将数据还原到原始规模。当评估所有模型预测表现时，过滤掉小于10 的出租车需求[20]，这也是学术界和工业界的普遍做法。此外，训练集的前80%用于训练整个模型，而剩余20%的数据用于超参数的选择。当确定超参数值之后，再以完整的训练数据集训练MFSTGCN模型并产生未来出租车需求的预测，随后根据模型的预测结果评估表现。

图7 纽约城曼哈顿区和布鲁克林区的出租车区域图

3.3 定性分析

Tensorflow 框架用于构建本文的模型MFSTGCN。在模型的所有组件中，设置完全相同的超参数值。其中，K=3，Kw=3，dayslot=48，Orecent=7，Oday=7，Oin=7，δ=0.5。MFSTGCN模型的优化器为RMSProp，其初始学习率为0.001，每5 轮后衰减为原始学习率0.7倍。此外，在训练模型的过程中，每批数据的大小为28。

3.3.1 与交通预测常用的基准模型进行比较

为了证明MFSTGCN模型的有效性，本文选择五种基准模型作为对照。为了公平起见，机器学习模型OLSR、SVR 以及深度学习模型STGCN 采用完全相同的输入数据训练模型。此外，STGCN 模型的参数设置与MFSTGCN模型保持一致。五种基准模型的介绍如下：

（1）历史平均值模型（HA）将出租车需求预测问题建模成季节性过程，依照前几个周期的均值作为未来出租车需求的预测值。例如，预测一个区域在星期三下午三点到三点半的出租车需求，该模型就依照历史数据中几周的星期三下午三点到三点半的均值作为预测值。

（2）自回归整合移动平均模型（ARIMA）是一种经典的时间序列预测模型。该模型依据区域历史出租车需求序列拟合模型，确定p、d、q三个参数值，从而预测未来的需求值。

（3）最小二乘线性回归（OLSR）是一种经典的机器学习算法，旨在捕捉出租车需求预测问题与历史流入量序列、历史出租车需求序列间的线性依赖关系。

（4）支持向量回归模型（SVR）是一种广泛应用于交通预测的机器学习模型，该模型根据训练集中历史出租车需求和历史流入量数据训练模型，然后基于测试集评估模型的性能。另外，SVR模型中的核函数为线性核函数。

（5）STGCN分别使用GCN和CNN挖掘数据中的时空依赖性，其特殊的三明治结构让模型训练过程更加高效。

在基准模型中，ARIMA模型是通过调用statsmodels库提供的api实现。机器学习模型（OLSR，SVR）则是通过调用sklearn 库所提供的api 完成。另外，上述这些模型参数是由网格搜索方法依据拟合或训练模型的最优结果确定。

将本文提出的MFSTGCN 模型和五种基准模型应用于三个不同的数据集，预测出租车需求，其实验结果如表4所示。从表中可知，时间序列模型（HA，ARIMA）的预测表现较差（表4并未展示曼哈顿数据下HA模型，海口市数据集下HA、ARIMA 模型的预测结果，这是因为其实验结果不好）。OLSR和SVR等机器学习模型从多种特征中学习，能够捕捉未来出租车需求与四种因素间的依赖关系，因此，与时间序列模型相比，OLSR 和SVR的预测表现有所提升。然而，此类机器学习模型缺乏挖掘高度非线性时空依赖性的能力，故其预测误差普遍高于下列深度学习模型STGCN和MFSTGCN。STGCN模型通过时空卷积块结构有效捕捉出租车需求预测中复杂的时空依赖关系，因此，STGCN模型的预测结果优于上述时间序列模型和机器学习模型。然而，STGCN模型忽略了区域间潜在空间依赖关系以及区域历史流入量等因素的影响。MFSTGCN 模型设计多个组件分别捕捉这些因素，故MFSTGCN模型在实验中预测误差最小。基于RMSE、MAE、MAPE三个评估指标下，在布鲁克林区数据集MFSTGCN 模型的预测精度相较于STGCN模型有5.0%、4.6%、3.9%。类似地，在曼哈顿区数据集有9.0%、7.6%、7.5%的提升而在海口市数据集有13.4%、13.9%、10.2%的提升。

表4 与基准模型比较

3.3.2 与MFSTGCN模型的不同变体进行比较

研究模型的不同变体有助于获悉不同因素对模型预测能力的影响程度，因此，本文对MFSTGCN 模型的三种变体STGCN、MSTGCN、MSTGCN-D 进行实验。其中，STGCN 模型只包含临近序列组件。MSTGCN 模型加入区域潜在相关性组件，将建立的潜在空间依赖性矩阵传入GCN 中用于GCN 的计算过程。MSTGCN-D模型则是在MSTGCN 基础上融入日需求序列组件。MFSTGCN是最终的模型，其进一步整合历史区域流入量序列组件。图8～10分别展示了模型的不同变体的实验结果。从图中可知，融入不同的因素均能提高模型的预测精度，表明建模这些因素的有效性。值得注意的是，模型融入区域间潜在依赖关系组件能够大幅度地降低预测误差。这表明挖掘城市中的不同区域间潜在依赖关系对于预测未来出租车需求十分重要。此外，本文也研究了不同模型在每天的预测能力，其实验结果如图11 所示。由于空间有限，实验中仅选择RMSE 作为评价指标。从图中可观察到如下几个现象：（1）每一天，MFSTGCN模型的预测误差均为最低，这说明MFSTGCN模型具备更强大的预测能力。（2）不同数据集下，每一天的预测难度有所不同，这意味着仍然存在一些未知的因素（如季节等）影响未来出租车需求，需要进一步探索。

图8 MFSTGCN模型及其变体在Manhattan-FHV-Taxi数据集的实验结果

图9 MFSTGCN模型及其变体在Brooklyn-FHV-Taxi数据集的实验结果

图10 MFSTGCN模型及其变体在Haikou-Didi-Taxi数据集的实验结果

图11 纽约市曼哈顿区，布鲁克林区和海口市每一天的实验结果

4 结束语

本文提出一种多因素时空图卷积MFSTGCN 模型预测出租车需求。该模型通过建立地理邻接矩阵，区域间潜在依赖邻接矩阵、区域邻近时刻出租车需求序列、区域日出租车需求序列和区域历史流入量序列来建模问题的多重时空依赖性。为了评估MFSTGCN 模型的预测能力，在国内外公开数据集上进行对比实验。结果表明，MFSTGCN模型能达到更为精确的预测结果。

在未来的工作中，将会继续探索更多外在因素（例如节假日，天气）对出租车需求的影响。同时，考虑如何设计相应的结构来捕捉区域间出租车流量以及城市路网车流量的随时间动态变化的趋势，进一步提升MFSTGCN模型的预测能力。