Dynamic Spatiotemporal Graph Convolutional Neural Networks for Traffic Data Imputation with Complex Missing Patterns

期刊：
关键字：交通数据归因·时空相关性·缺失模式·图卷积神经网络·循环神经网络

提示：该文章是应对缺失数据的动态图神经网络，

摘要

数据缺失Missing data是智能交通系统中交通数据采集不可避免且普遍存在的问题。尽管对交通数据的归因进行了大量的研究，但仍存在两方面的不足:一是现有方法未能捕获交通数据中复杂的时空相关性，尤其是随时间变化的动态空间相关性;其次，以往的研究主要集中在随机缺失模式上，而其他更复杂的缺失场景较少被讨论。为了填补这些研究空白，我们提出了一种新的深度学习框架，称为动态时空图卷积神经网络Dynamic Spatiotemporal Graph Convolutional Neural Networks(DSTGCN)，以估算缺失的交通数据。该模型将循环架构与基于图的卷积相结合，对时空相关性进行建模。此外，我们引入了一种图结构估计技术来模拟实时交通信息和道路网络结构的动态空间依赖性。基于两个公共交通速度数据集进行了广泛的实验，以比较我们提出的模型与最先进的深度学习方法在四种类型的缺失模式。结果表明，我们提出的模型在各种缺失场景下的性能优于现有的深度学习模型，图结构估计技术有助于模型性能的提高。我们进一步将我们提出的模型与一个张量分解模型进行比较，发现不同的模型族在不同的训练方案和数据可用性下有不同的行为。

1 Introduction

来自真实交通系统的交通数据在交通研究和应用中起着至关重要的作用，如交通状况预测、驾驶路线规划、交通流优化等。交通数据主要通过两种传感器采集，一种是固定传感器(如环路探测器)，另一种是移动传感器(如GPS探头)。然而，无论是静止还是移动传感器，数据缺失 都是一个不可避免的问题。固定传感器容易出现探测器故障、通信故障、停电等设备问题，而移动传感器采集的数据通常稀疏，空间和时间分辨率[1]非常不稳定。数据缺失问题严重影响了交通状况的实时监控，并进一步限制了其他下游应用。因此，如何估计缺失数据，或交通数据插补，成为一个关键问题。

交通数据的插补问题 traffic data imputation problem越来越受到人们的关注。早期研究主要将各个位置的交通数据建模为时间序列，忽略了交通数据的空间信息[2,3]。最近的研究利用邻域传感器/位置提供的局部空间信息来提高 imputation 精度[4,5]。虽然这些研究显示了利用空间相关性的有效性，但未能充分利用全局时空信息。最近，矩阵(或张量)分解方法被引入到交通数据的 imputation 中，并被证明在检索不同维度的相关性方面是有效的[6,7]。然而，这些方法仅依赖于全局低秩结构global low-rank structure，通常不明确地建模潜在的局部一致性，如道路网络的空间约束和时间平滑性。因此，这些模型在充分捕捉交通数据中时空相关性的复杂性方面可能受到限制。随着深度学习模型在广泛任务中被证明的成功，基于神经网络的方法也被用于数据 imputation 问题，包括Autoencoders[8,9]，递归神经网络(RNNs)[10,11]和卷积神经网络(CNNs)[12,13]。最近的研究已经开始使用图神经网络(GNN)来重构交通数据[14,15]，并证明了GNN在网络层面捕获空间依赖关系的有效性。尽管有大量的研究来解决数据缺失问题，我们认为仍然存在两个重要的研究空白。

首先，现有的方法无法捕获交通数据中复杂的时空相关性。尽管GNN的研究结果很有前景，但现有的研究通常假设空间依赖性是由距离决定的，且严格地随时间变化。然而，以往的研究表明，空间依赖性不仅由距离决定，还由道路等级、人的流动性等其他因素决定。此外，交通网络的空间依赖性不是恒定的，可以随着时间的推移而变化。近年来，人们提出了一些基于gnn的新方法来对交通数据中的真实依赖关系和动态依赖关系进行建模，但这些方法都是针对具有完整数据的预测任务开发的[17,18]。如何从不完整的异构数据中揭示动态变化的时空模式，准确地重构交通信息仍然是一个具有挑战性的问题。

其次，大多数现有方法都是针对随机缺失场景开发的，可能无法在其他复杂缺失模式中提供健壮的结果。随机缺失场景是基于缺失数据点彼此完全独立的假设，但缺失值有可能是时间或空间相关的。在这种情况下，连续时间间隔或空间相邻位置的值缺失，由于缺失值没有空间或时间上的相邻信息，imputation 将更加困难。

为了解决上述问题，我们提出了一种新的深度学习体系结构，称为动态时空图卷积神经网络(DSTGCN)，为不同的缺失模式提供准确和稳健的 imputation 结果。它由多个时空块组成，每个块包括一个捕获时间相关性的双向递归层、一个建模动态空间相关性的图结构估计层和一个捕获空间相关性的图卷积层。为了验证我们模型的有效性，我们在两个公共数据集上进行了实验，一个来自加利福尼亚州洛杉矶的高速公路网络，另一个来自华盛顿州西雅图的城市道路网络。我们进行了大量的实验，以比较我们提出的模型与几种最先进的深度学习模型在四种具有广泛缺失比例的缺失模式类型上的差异。结果表明，在不同的数据缺失场景下，DSTGCN 具有较好的性能。为了分析不同模型族的适用性，我们进一步将我们的模型与具有代表性的张量分解模型 BGCP [7]在两个实验设置下进行比较，并根据是否有完整的训练数据。研究发现，当训练数据足够多时，深度学习模型显示出明显的优势，而当训练数据稀疏且缺失模式相关时，张量分解方法更适合。

该研究的主要贡献如下:
1)提出了一种新的深度学习框架，用于揭示交通网络中复杂的时空相关性，并准确、稳健地重构缺失的交通数据;
2)我们设计了一种基于实时交通信息的图结构估计技术来估计网络结构的动态空间依赖性;
3)基于两类真实交通数据进行了综合实验，结果表明，在不同的缺失场景下，我们的模型显著优于现有的深度学习方法;
4)对深度学习模型和张量分解模型在不同实验设置下进行了比较分析，并说明了不同模型族在不同情况下的适用性。

2 Literature Review

以往的研究针对不同类型的交通数据开发了基于不同缺失模式的多种归责方法。特定的缺失模式或数据类型会极大地影响方法的性能。因此，在本节中，我们首先回顾交通数据插补的方法，然后总结文献中使用的不同缺失模式和交通数据。此外，我们还回顾了各种流量应用中基于GCN的模型，以更好地定位我们的论文。

2.1 Traffic Data Imputation Methods

早期的交通数据估算模型主要依赖于时间模式，很少利用交通数据的空间结构。最简单的方法是Historical Average，它基于过去[2]中相同时间间隔的平均值来填充缺失的值。[19]使用贝叶斯网络从观测数据中学习概率分布，并使用最佳拟合来估算缺失数据。[20]引入了一种概率主成分分析(PPCA)技术，利用交通数据的日周期性和间隔变化。最近的研究将空间信息融入到缺失数据重建中。[21]将支持向量回归(SVR)与遗传算法相结合，捕捉交通网络中的空间和时间关系。基于[4]算法，提出了一种改进的基于路段几何形状的k-最近邻(KNN)算法。[5]引入了一种空间上下文感知模型，利用周围传感器信息重构交通数据。这些模型表明，空间信息有助于交通数据的估算。然而，它们主要集中在利用邻域位置的局部空间信息，而未能充分利用全局时空信息。

近年来，矩阵(或张量)分解方法被引入到交通数据的 imputation 中，它将交通数据构造为一个多维矩阵，并对不完全矩阵进行低秩逼近 low-rank approximation。[6]将交通数据形成4向张量a 4-way tensor，并采用张量分解HaLRTC算法来恢复丢失的数据。[7]将贝叶斯概率矩阵分解扩展到高阶张量，并将其应用于不完全交通数据的估算。[22]将低秩矩阵分解与向量自回归过程相结合，提出了一种时间分解框架。与以往的模型相比，张量因子分解 更擅长捕获多维结构依赖关系，从而在网络层面进行估算。但它只适用于低秩的统计数据，需要对每一批新的不完整数据[23]从头学习。此外，考虑到交通数据时空相关性的非线性和复杂性，张量分解模型可能难以完全检索交通特征，并提供具有不同缺失模式和缺失比例的鲁棒 imputation。

随着深度学习的最新进展，许多深度神经网络模型也被开发出来，以解决交通数据的 imputation 问题。与 张量分解方法相比，深度学习模型不需要对数据进行额外的假设，当提供足够的训练数据时，可以进行预训练，用于在线应用。[10]采用双向RNN作为生成模型来填补文本数据的缺失。[8]引入了一种名为去噪叠加自编码器的神经网络模型来解决数据缺失问题。虽然这些方法证明了深度学习在数据imputation领域的有效性，但它们很少考虑空间信息。为了利用空间相关性，[11]提出了一种多视角学习方法，采用LSTM获取时间相关性，SVR获取空间相关性。[12]提出了一种卷积递归自编码器，利用多量程CNN来建模空间相关性。虽然在网格结构数据(如图像)中，CNN可以很好地处理欧氏相关性，但在不规则道路网络中，却没有考虑到非欧氏关系。近年来，GNN在嵌入交通系统的图结构方面表现出了良好的效果。在此基础上，[14]开发了一种基于图卷积网络(GCN)的模型来恢复未观测到的传感器数据(即kriging)，并使用由距离预定义的固定加权邻接矩阵来表示空间依赖关系。[15]采用图注意网络(GATs)自适应学习相邻传感器之间的空间依赖关系。然而，它们预先假定空间依赖只存在于距离较近的传感器/位置之间，无法捕捉整个交通网络的真实和动态关系。

2.2 Missing Patterns and Traffic Data Types in Previous Studies

缺少模式和数据类型会严重影响方法的性能。以往的研究一般将缺失数据的模式分为三类:完全随机缺失(missing at Random)、随机缺失(missing at Random)和不随机缺失(Not missing at Random)[24]。在此基础上，[11]将智能交通系统中的缺失模式分为四类:
1)Random missing随机缺失 (RM)(图1a)，其中缺失值相互独立;
2)时间相关缺失Temporallycorrelated Missing(TCM)(图1b)，缺失值具有时间相关性;
3)空间相关缺失Spatially correlated Missing(SCM)(图1c)，缺失值与其空间相邻读数相关;
4)块缺失(Block Missing, BM)(图1d)，缺失值在时间和空间上都是相关的，形成块。
我们的研究也采用了这种分类。根据缺失比例，缺失模式还可以分为不完全缺失和完全缺失。这项研究集中在非完全缺失模式，其中至少有一个观测数据在空间和时间维度存在。完全缺失的模式包括完全的TCM[14]和完全的SCM[25]。在完全 TCM 中，有些传感器/位置是完全观察不到的，而在完全 SCM 中，有些时点是观察不到信息的。本文不考虑这些情况。还可以区分交通数据类型。由于数据采集方法和底层道路网络的不同，交通数据一般可分为高速公路数据freeway data(FD)和城市道路网络数据urban road network data(UD)。FD 通常在高速公路网上用固定传感器采集，而 UD 则在城市公路网上用移动传感器(如探测车辆)采集。通常，前者具有更高的时间粒度，而后者具有更高的空间覆盖率。

表1总结了文献中的交通数据类型、缺失模式和缺失比例。我们可以发现，RM 是最常被研究的缺失模式，而其他具有时间或空间相关缺失值的缺失模式则较少被讨论。与 RM 相比，其他模式由于缺乏空间或时间上的相邻信息而更具挑战性。因此，为随机缺失值开发的方法可能不适用于其他缺失模式。此外，以往的研究通常是在高速公路网络或城市道路网络上进行的。但是，由于道路设计和功能的不同，这两类数据可能会表现出不同的交通特征。针对 FD 优化的方法不一定适用于 UD 。缺失比例也会影响模型的性能。以前的一些模型是针对低缺失率而开发的，当缺失率很高时可能无法显示稳定的性能。因此，需要一种通用的方法来为各种缺失比例下的不同缺失模式和数据类型提供准确和稳健的结果。

2.3 Graph Neural Networks in Traffic Research

GNN已成功应用于交通研究中的各种预测任务，包括交通速度预测[29]、网约车需求预测[30]、地铁客流预测[31]。为了联合提取隐藏在交通网络中的时空特征，研究人员通常使用GNN来捕获网络层面的空间关系，同时使用时间轴上的RNNs或CNNs来提取时间相关性。

• 通过将循环架构与扩散图卷积层相结合，[32]引入了一种用于交通预测的深度学习框架。
• [29]提出了一种纯卷积架构，利用图卷积提取空间特征和门控cnn提取时间特征。
• [30]将循环层与多图卷积网络结合起来，对区域之间的多层次空间相关性进行编码。