混合时空图卷积网络：利用导航数据改进交通预测效果 | KDD 2020
作者 | 高德机器学习团队
出品 | AI科技大本营（ID:rgznai100）
引言
时空预测（spatio-temporal forecasting）在天气预报、运输规划等领域有着重要的应用价值。交通预测作为一种典型的时空预测问题，具有较高的挑战性。日常通勤中的规律往往相对容易挖掘，但交通状况还会受影响于各种难以预知的事件（例如娱乐庆典活动的举办、恶劣天气等）。以往的研究中[1, 2, 3]，数据驱动的方法往往利用通行时间这类交通状态特征作为模型的主要输入。后续有研究[4, 5]提出利用事件相关的特征（例如利用推特文本或地图中热门POI搜索频次等数据）来将事件信息引入到模型中，但这类方法带来的效果提升仅限于事件发生的热点位置。
为解决这一问题，我们从高德导航引擎中获取了“计划中交通流量”（intended traffic volume），并将其扩充到机器学习模型当中。计划中交通流量来自导航数据，反映了用户出行意图中蕴含的未来交通流量。由于拥有海量用户，高德地图中的导航规划数据能够较为全面地反应正在发生的通行需求，并且信息粒度较事件级别的特征更精细。具体来说，规划的路线产生了计划中交通流量，而计划中交通流量可以用以指导对未来通行时间的预测。图 1 中， volf 代表当前可获取的导航路径在f个时间步后在此路段产生的计划中交通流量。计划中交通流量的迅速飙升意味着即将到来的交通拥堵。
图 1 北京某路段在2019年10月28日早高峰期间通行时间和计划中交通流量
为了将交通流量这一异质信号整合到通行时间预测模型当中，我们创新性地设计出一种域转换器（domain transformer）结构，用于将交通流量信息转化为通行时间信息。交通流理论中，路段的交通流量和车辆密度呈三角形曲线映射关系，而曲线的参数是因路段而异的。图2展示了现实世界中的例子。为了利用这一转换关系，我们设计了将流量转化为通行时间的转换器，该转换器由两层网络构成，分别用于提取全局共享信息和学习不同路段的精细化信息。
图 2 四个不同路段的流量时间曲线
另一方面，由于交通网络的非欧几里得特性，我们利用图卷积（graph convolution）结构提取空间依赖性特征，并设计了一种新的邻接矩阵用于更好地体现路段间的交通邻近性。在以往的文献中[6]，邻接矩阵的权重只按距离衰减，并没有考虑到路段间固有的交通邻近性（图 3 给出了距离近但交通状态相差较大的例子）。为解决这一问题，我们设计了一种复合邻接矩阵（compound adjacency matrix），在距离衰减的基础上进一步引入了路段通行时间的协方差。
图 3 相邻道路间拥堵不一定会传播
本文中，我们所提出的混合时空图卷积网络（Hybrid Spatio-Temporal Graph Convolutional Network，H-STGCN）是综合利用上述技术的交通预测框架。在H-STGCN中，转换器结构将未来交通流量信号转化为通行时间信号。路段间参数共享的门控卷积用于提取时间依赖信息。基于复合邻接矩阵的图卷积从合并后的通行时间信号中捕捉空间依赖信息。H-STGCN经由端到端的训练，可具备基于计划中交通流量信息预测未来拥堵的能力。利用真实交通数据集进行实验可验证，H-STGCN的效果显著优于各种前沿模型。
本文的主要贡献点概括如下：
-
我们提出了一种将计划中交通流量引入机器学习模型的交通预测方法。这一方法将基于数据驱动的交通预测方法和基于交通仿真的预测方法[8]加以结合，显著提升了预测的效果。
-
我们设计了域转换器结构，将交通流量这一异质信号加以转化整合。这一结构具有通用性，可以适配到各种基于神经网络的交通预测模型。
-
我们提出了一种新的复合邻接矩阵，可以编码路网中固有的交通接近性。
-
我们提出了H-STGCN这一多模态学习框架，并在真实数据集上取得了显著优于各种前沿模型的效果。
基础
给定一个由n个有向路段组成的交通网，按5分钟的间隔将时间离散化，训练集、测试集的时间范围分别表示为 [0, S train) 和 [ S train, S train+ S test) 。我们将数据集表示为张量 X ∈ R n ×( S train+ S test)× C (in) ，其中 C (in) 表示输入特征的维数。
通行时间（ travel time）/交通流量（traffic volume） 。通行时间 τi , t 定义为路段 si 在时间片t上的平均通行耗时（单位距离）。类似地，交通流量 vi , t 代表时间片t内进入到路段 si 的车辆数。
理想未来流量（ ideal future volume） 。给定时间片 t 0 ，理想未来流量 νi , t 0, f （f≥0）与交通流量 vi , t 0+ f 的值相对应，并且在下述两条假设成立时两者相等：1）仅考虑t0时刻正在使用导航服务的车辆；2）每辆车严格按照规划路线行驶，且速度与ETA（estimated time of arrival，预计抵达时间）相吻合。
历史均值（ historical average，HA） 。将一周内时间片的数量记为L（例如按每5min一个时间片计算，则每小时有12个时间片，每天只考虑06:00-22:00这16个小时，则L=7×16×12=1344。变量 ωi , t （可以是通行时间或理想未来流量）定义为
其中， W 是训练集时间跨度包含周的数量。
交通预测（ traffic forecasting） 。给定时刻t以及所有此时能够获取到的数据，交通预测模型输出交通网中各路段未来的通行时间。更具体地，给定前序交通特征 { X :, t − P +1,:,…, X :, t ,:} ，模型 H 对接下来几个时间片各路段的通行时间加以预测： H ( X :, t − P +1,:,…, X :, t ,:)={^ τ :, t +1,…,^ τ :, t + F } ，其中P表示输入时序的长度，F代表预测时间跨度（forecasting horizon）。
方法
3.1. 整体框架
图 4 展示了H-STGCN的整体框架。模型输入由两个特征张量组成，理想未来流量V和通行时间张量T。V和T均包含三个维度：空间维度、时间维度、通道维度，分别对应路段、所使用的时间片和特征。域转换器（模块a）首先将V转化为通行时间信号，输出“未来通行时间”张量X(g1)。接下来，两个独立的门控卷积（模块b）分别作用于X(g1)和T的时间维度以提取更高层级的时域特征。将每个路段视为一个节点，基于复合邻接矩阵的图卷积（模块c）作用在合并（concatenation）后的信号h=hν⊕hτ上。两个门控卷积继续扩大时域上的感知范围，并最终经由一个全连接层（FC）输出预测结果。
图4 H-STGCN模型框架
3.2. 模型输入与数据处理
输入特征张量X的每个切片对应了一个单独的时间片 t （ ≤ t 0 ）。每个切片又由两部分组成：理想未来流量和通行时间。
理想未来流量。 作为对真实未来流量这一无法获取信息的近似，理想未来流量 νi , t 0, f 可以通过在线导航引擎获取。图 5 示意了高德导航系统的架构。导航过程中，车辆每秒钟与云服务器同步自身坐标，与此同时，为保证用户获取到最新的交通状态信息，云服务器对ETA进行几乎实时的持续更新。
图 5 高德导航系统架构示意
高德导航引擎中原始数据的形式为
其中r是导航进程的索引号，ψr是导航r的发起时间， νi , t 0, f 代表规划路线中的第l个路段， δr , l 是到达 ρr , l 的预估时间， Mr 是路线中路段的总数量， N L 是导航进程的总数量。ETA来自机器学习模型的预测（利用历史轨迹等数据训练得到）。算法 1 展示了从导航路线集合中推算理想未来流量的方法。
H-STGCN中，与预测时间窗口相对应的理想未来流量和历史平均流量同时被输入：
其中 i 是路段的索引号。
通行时间 。通行时间 τi , t 通过完成地图匹配的GPS点数据整合计算得到。H-STGCN中，通行时间及其与预测时间窗口相对应的历史均值同时被用于模型的输入：
其中 i 是路段的索引号。
3.3. 域转换器
域转换器Λ由串联的两层网络组成，即逐路段1×1卷积（segmentwise 1×1 convolution）和路段间共享1×1卷积（shared 1×1 convolution），图 6 呈现了这一结构。
图 6 H-STGCN中的各种卷积运算
共享 1×1 卷积 。路段及时间片间参数共享的1×1卷积层Γ(c)位于域转换器的顶部，该卷积运算阐释如图6a，旨在捕捉全局的三角形曲线映射关系。记这一层的输入和输出为 X ( c ) i , t ,:∈ R C ( c in) 与 Y ( c ) i , t ,:∈ R C ( c out) ，则有：
其中F(c)∈RC(cin)×C(cout)为权重，b(c)∈RC(cout)为偏置项，σ为ELU（Exponential Linear Unit）激活函数。逐路段1×1卷积 。为保证模型能够充分提取精细到路段级别的特征，路段参数个性化的1×1卷积层Γ(s位于域转换器 的底部（共享1×1卷积前⾯⼀层），该卷积运算阐释如图 6b。记这⼀层的输⼊和输出为X(s)i,t,:∈RC(sin)与Y(s)i,t,:∈RC(sout) ，则有：
其中，F(c)∈RC(cin)×C(cout)为权重，b(c)∈RC(cout)为偏置项， σ是ELU激活函数。
3.4. 基于复合邻接矩阵的图卷积
复合邻接矩阵。以往研究[6,7]中的邻接矩阵假设节点间的接近性简单地依距离衰减：
其中dij为路段si与sj的最短路距离，σ控制衰减速率，ϵ为控制矩阵稀疏性的截断阈值。我们将W(d)称为迪杰斯特拉矩阵（Dijkstra matrix）。在很多场景下，单纯的空间接近程度并不能反映真实的交通邻近性。更具体而言，交通拥堵对交通分流的影响取决于邻近路段的若干种属性，包括道路等级、路况等。可见，拥堵的传播在空间上并不均匀。由此，我们提出了复合邻接矩阵W(c)：
其中(⋅)+=max{0,⋅}，τi=∑t∈[0,Strain)τi,t/Strain。
图卷积。我们将交通路网视为一个以路段为节点的图。归一化图拉普拉斯（normalized graph Laplacian）矩阵L和缩放变换的图拉普拉斯（scaled graph Laplacian）矩阵L分别表示为：
其中In为单位阵，W(c)为复合邻接矩阵，对角阵D为W(c)的度矩阵（degree matrix），λmax是L的最大特征值。图卷积层Θ通过L的切比雪夫多项式（Chebyshev polynomials）参数化。记这一层的输入和输出为X(Θ):,t,:∈Rn×C(Θin)和Y(Θ):,t,:∈Rn×C(Θout)，则：
其中，Tk(~L)是切比雪夫多项式第k阶项，K是卷积核大小，Θ∈RK×C(Θin)×C(Θout)Θ∈RK×C(Θin)×C(Θout)为权重张量，b(Θ)j为偏置项，σ是ELU激活函数。
3.5. 时域门控卷积
如图 6c 所示，路段间参数共享的一维卷积将输入X(g)∈Rn×P×C(gin)转化为张量：
其中 * 表示一维卷积运算符。F(g)∈RKt×C(gin)×2C(gout)是卷积核，Kt是卷积核的大小，P是输入时序长度，b(g)是偏置项。A和B形状相同、通道数均为C(gout)。我们使用GLU（gated linear unit）进一步引入非线性：
“⊙”表示哈达玛积（Hadamard product）。
3.6. 与STGCN的关系
时空图卷积网络（Spatio-Temporal Graph Convolutional Network，STGCN）[7]将空域图卷积层和时域门控卷积层交替地进行堆叠以同时捕捉时间和空间的依赖性。将H-STGCN的流量特征分支和邻接矩阵中的协方差项去掉，则H-STGCN退化为只有单个时空卷积块（ST-Conv block）的STGCN模型。
3.7. 模型训练
数据扩充。我们将高斯噪音叠加到流量通道中小于ϵn的值上，以提升模型的泛化能力。
优化目标。对于本文中的多时间步预测，我们使用L1损失函数：
其中 τi , t + f 是模型的输出， τi , t + f 为真值。
实验
4.1. 数据集
实验数据集分别记作W3-715和E5-2907，分别对应西三环附近的715个路段和东五环附近的2907个路段（如图 7 所示）。数据集的时间跨度为2018年12月24日至2019年4月21日（其中包含的节假日被移除，共十周数据），保留的时段为每天的06:00至22:00。前八周数据作为训练集，后两周作为测试集。
图 7 实验路网空间分布
4.2. 用于对比的方法
基线模型 。包括历史均值（HA）、线性回归（LR）、GBRT、MLP、Seq2Seq、STGCN（包含单个时空卷积块）。
用于对比实验的变种模型。
-
STGCN (Im)：换用复合邻接矩阵的STGCN（用于和原始的迪杰斯特拉矩阵对比。
-
H-STGCN (1)：将流量特征张量 V 全部设成1。
4.3. 评价指标
我们在三种测试集上进行模型效果的比对：
-
全测试集（如4.1节中所描述）。
-
高流量路段的拥堵时期，用C表示。
-
高流量路段的突发拥堵时期，用尾缀NRC表示。
4.4. 效果比较
表 1 展示了在全测试集、测试集C、测试集NRC上不同模型的表现。评估标准包括MAE（s/m）、MAPE（%）和RMSE（s/m）。H-STGCN在各项指标上均显著优于不同的对标模型，在突发拥堵的预测方面优势尤为明显。
表 1 模型效果对比
复合邻接矩阵。分析表 1 可知，和STGCN相比，STGCN (Im)在W3-715数据集上有着更低的MAE、MAPE，在E5-2907数据集上有着更低的MAE、MAPE及RMSE，证明了复合邻接矩阵的有效性。图 8 以E5-2907数据集为例，对不同邻接矩阵进行可视化。图中颜色代表的值为lg(wij+1)，(a)为迪杰斯特拉矩阵，(b)为协方差矩阵，(c)为复合邻接矩阵。
图 8 E5-2970的各种邻接矩阵
未来流量特征和域转换器。如表 1 所示，和STGCN (Im)相比，H-STGCN有着稳定的更优表现，从而证实了利用未来流量数据带来的收益。由于域转换器中逐路段卷积结构的存在，H-STGCN的模型表达能力是强于STGCN (Im)的。为了消除这一影响以针对未来流量特征带来的收益做更公平的分析，我们进一步将H-STGCN与H-STGCN (1)进行对比。在测试集C、测试集NRC上，不难发现未来流量特征在对拥堵的预测上有显著更优的表现。如图 9 所示，随着预测时间跨度的拉长，未来流量特征带来的收益会起主导作用。
图 9 测试集NRC上效果比对
为了更加直观地对H-STGCN的原理加以剖析，我们这里展示一个突发拥堵预测的案例（如图 10 所示）。这个案例来自2018年4月16日某一高速路段。GT代表真值，HA代表历史均值，τ(−f)是f个时间步以前对当前通行时间的预测值，νi,t,f是对f个时间步后的理想未来流量。17:30至18:00拥堵加剧的阶段，H-STGCN (1)提前多个时间步的预测结果和真值相比有明显的时间滞后。
相比之下，H-STGCN由于有理想未来流量中的信息，甚至有能力在30min以前就对拥堵有着准确的预测。我们可以这样理解这一现象：νi,t,3对应的曲线代表了对15min之后交通流量的近似推算，该曲线在17:15就开始拉升了。基于导航引擎中只有当前时刻已经发起的导航行程这一事实，实际的未来流量要比理想未来流量更高。所以，νi,t,3的飙升预示着有较大的交通流量正在涌来，这就使H-STGCN能够在没有历史数据做参考的情况下预知未来的拥堵。
图 10 突发拥堵预测案例
4.5. 模型可扩展性
模型在W3-715和E5-2097两数据集的预测时间不超过100ms。为了在实际线上应用场景中平衡推演效率和预测效果，我们将城市路网切分成最多包含几千个路段的子路网，每个子路网在线上部署一个模型。
应用
本⽂提出的⽅法已在高德驾车路线的旅行时间预测（ETA）（见图 11）中落地[9,10]，并将偏差严重的案例数量降低了15%。此外，本方法首次以数据驱动的方式建模了用户出行意图与交通路况演化之间的相互作用，未来可以广泛的应用在主动式的交通管理（proactive traffic management）领域，例如智能红绿灯调控（intelligent traffic light control）[9]、智能道路收费系统（intelligent toll systems for roads）[10]等。
图 11 ETA预测结果的展示
结论
本文中，我们提出了一种新的用于通行时间预测的深度学习框架：混合时空图卷积网络（H-STGCN），该框架利用从导航数据中推演出的计划中交通流量提升模型效果。我们设计了域转换器，以此整合异质模态的交通流量特征。我们设计了复合邻接矩阵使得图卷积层能够更好地捕捉路段间的接近性。在真实场景数据集上进行的实验证实H-STGCN和对标的模型相比取得了显著更优的效果，在突发拥堵的预测上优势尤为明显。这一框架提供了一种将物理知识嵌入数据驱动模型的新范式，可以较容易地推广应用于一般的时空预测任务当中。
主要参考文献
[1] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2018. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.
[2] YishengLv, YanjieDuan, WenwenKang, Zhengxi Li, Fei-Yue Wang, etal. 2015. Traffic flow prediction with big data: A deep learning approach. IEEE Trans. Intelligent Transportation Systems 16, 2 (2015), 865–873.
[3] Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2018. Spatio-Temporal Graph Convolutional Neural Network: A Deep Learning Framework for Traffic Forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI).
[4] JingruiHe, WeiShen, Phani Divakaruni, Laura Wynter, and Rick Lawrence. 2013. Improving Traffic Prediction with Tweet Semantics. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). 1387–1393.
[5] Binbing Liao, Jingqing Zhang, Chao Wu, Douglas McIlwraith, Tong Chen, Shengwen Yang, Yike Guo, and Fei Wu. 2018. Deep Sequence Learning with Auxiliary Information for Traffic Prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM.
[6] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2018. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.
[7] Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2018. Spatio-Temporal Graph Convolutional Neural Network: A Deep Learning Framework for Traffic Forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI).
[8] Moshe Ben-Akiva, Michel Bierlaire, Haris Koutsopoulos, and Rabi Mishalani. 1998. DynaMIT: A simulation-based system for traffic prediction. In DACCORD Short Term Forecasting Workshop. Delft, The Netherlands, 1–12.
[9] Wei, H., Zheng, G., Yao, H. and Li, Z., 2018. Intellilight: A reinforcement learning approach for intelligent traffic light control. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.
[10] https://en.wikipedia.org/wiki/Congestion_pricing
推荐阅读
你点的每个“在看”，我都认真当成了AI
About The Author
