KDD2020|混合时空图卷积网络：更精准的时空预测模型
点击上方“小白学视觉”，选择加"星标"或“置顶”
重磅干货，第一时间送达
【导读】时空预测在天气预报、运输规划等领域有着重要的应用价值。交通预测作为一种典型的时空预测问题，具有较高的挑战性。以往的研究中主要利用通行时间这类交通状态特征作为模型输入，很难预测整体的交通状况，本文提出的混合时空图卷积网络，利用导航数据大大提升了时空预测的效果（本文作者高德机器学习团队，论文已被收录到KDD2020）。
日常通勤中的规律往往相对容易挖掘，但交通状况还会受很多其他因素影响，之前的研究主要利用通行时间这类交通状态作为特征，少量研究引入事件，不能很好地预测实际交通流量。
为解决这一问题，本文从高德导航引擎中获取了「计划中交通流量」，并将其扩充到机器学习模型当中。
计划中交通流量来自导航数据，反映了用户出行意图中蕴含的未来交通流量。由于拥有海量用户，高德地图中的导航规划数据能够较为全面地反应正在发生的通行需求，并且信息粒度较事件级别的特征更精细。
具体来说，规划的路线产生了计划中交通流量，而计划中交通流量可以用来指导对未来通行时间的预测。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的效果显著优于各种前沿模型。
混合时空图卷积网络，独创域转换器和复合邻接矩阵
整体框架
图 4 H-STGCN模型框架 模型输入与数据处理
H-STGCN中，与预测时间窗口相对应的理想未来流量和历史平均流量同时被输入：
其中是路段的索引号。
通行时间 。通行时间通过完成地图匹配的GPS点数据整合计算得到。H-STGCN中，通行时间及其与预测时间窗口相对应的历史均值同时被用于模型的输入：
其中是路段的索引号。
域转换器
域转换器由串联的两层网络组成，即逐路段卷积（segmentwise convolution）和路段间共享卷积（shared convolution），图 4 呈现了这一结构。
图 6 H-STGCN中的各种卷积运算共享卷积。路段及时间片间参数共享的卷积层位于域转换器的顶部，该卷积运算阐释如图 6a，旨在捕捉全局的三角形曲线映射关系。记这一层的输入和输出为与，则有：
其中为权重，为偏置项，为ELU（Exponential Linear Unit）激活函数。
逐路段卷积。为保证模型能够充分提取精细到路段级别的特征，路段参数个性化的卷积层位于域转换器的底部（共享卷积前面一层），该卷积运算阐释如图 6b。记这一层的输入和输出为与，则有：
其中，为权重，为偏置项，是ELU激活函数。
基于复合邻接矩阵的图卷积
复合邻接矩阵。以往研究[6,7]中的邻接矩阵假设节点间的接近性简单地依距离衰减：
其中为路段与的最短路距离，控制衰减速率，为控制矩阵稀疏性的截断阈值。我们将称为迪杰斯特拉矩阵（Dijkstra matrix）。在很多场景下，单纯的空间接近程度并不能反映真实的交通邻近性。更具体而言，交通拥堵对交通分流的影响取决于邻近路段的若干种属性，包括道路等级、路况等。可见，拥堵的传播在空间上并不均匀。由此，我们提出了复合邻接矩阵：
图卷积 。我们将交通路网视为一个以路段为节点的图。归一化图拉普拉斯（normalized graph Laplacian）矩阵和缩放变换的图拉普拉斯（scaled graph Laplacian）矩阵分别表示为：
其中为单位阵，为复合邻接矩阵，对角阵为的度矩阵（degree matrix），是的最大特征值。图卷积层通过的切比雪夫多项式（Chebyshev polynomials）参数化。记这一层的输入和输出为
则：
其中，是切比雪夫多项式第阶项，K是卷积核大小，为权重张量，为偏置项，是ELU激活函数。
时域门控卷积
如图 6c 所示，路段间参数共享的一维卷积将输入转化为张量：
其中表示一维卷积运算符。是卷积核，是卷积核的大小，是输入时序长度，是偏置项。和形状相同、通道数均为。我们使用GLU（gated linear unit）进一步引入非线性：
“”表示哈达玛积（Hadamard product）。
与STGCN的关系
时空图卷积网络（Spatio-Temporal Graph Convolutional Network，STGCN）[7]将空域图卷积层和时域门控卷积层交替地进行堆叠以同时捕捉时间和空间的依赖性。将H-STGCN的流量特征分支和邻接矩阵中的协方差项去掉，则H-STGCN退化为只有单个时空卷积块（ST-Conv block）的STGCN模型。
模型训练
数据扩充 。我们将高斯噪音叠加到流量通道中小于的值上，以提升模型的泛化能力。
优化目标 。对于本文中的多时间步预测，我们使用L1损失函数：
其中是模型的输出，为真值。
图 7 实验路网空间分布STGCN (Im)：换用复合邻接矩阵的STGCN（用于和原始的迪杰斯特拉矩阵对比。 H-STGCN (1)：将流量特征张量V全部设成1。
全测试集（如4.1节中所描述）。 高流量路段的拥堵时期，用C表示。 高流量路段的突发拥堵时期，用尾缀NRC表示。
，(a)为迪杰斯特拉矩阵，(b)为协方差矩阵，(c)为复合邻接矩阵。
未来将在主动交通管理方面发挥重要作用
好消息！
小白学视觉知识星球
开始面向外开放啦👇👇👇
下载1：OpenCV-Contrib扩展模块中文版教程 在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。 下载2：Python视觉实战项目52讲 在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。 下载3：OpenCV实战项目20讲 在「小白学视觉」公众号后台回复：OpenCV实战项目20讲，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。 交流群
欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~