AAAI 2023 | 用于城市交通流量预测的空间传播延迟感知的动态长距离自注意力模型

科技

2023-05-07 15:05

©PaperWeekly 原创 · 作者 | 姜佳伟等

单位 | 北京航空航天大学

研究方向 | 时空数据挖掘

论文标题：

PDFormer: Propagation Delay-aware Dynamic Long-range Transformer for Traffic Flow Prediction

论文链接：

https://arxiv.org/abs/2301.07945

代码链接：

https://github.com/BUAABIGSCity/PDFormer

论文作者：

姜佳伟（共一），韩程凯（共一），赵鑫教授，王静远教授

通讯作者：

王静远教授

作者单位：

北京航空航天大学，中国人民大学

课题组：

北航智慧城市课题组 BIGSCity（https://www.bigscity.com/）

作为智能交通系统的一项核心技术，交通流预测有着广泛的应用。交通流量预测的基本挑战是如何有效地模拟交通数据中复杂的空间-时间依赖关系。空间-时间图谱神经网络（GNN）模型已经成为解决这一问题的最有希望的方法之一。

然而，基于 GNN 的模型在交通预测方面有三个主要的局限性：i）大多数方法以静态的方式建立空间依赖性模型，这限制了学习动态城市交通模式的能力；ii）大多数方法只考虑短距离的空间信息，无法捕捉长距离的空间依赖性；iii）这些方法忽略了交通系统中，交通状况在不同地点之间的传播有时间延迟的事实。

为此，我们提出了一种新型的传播延迟感知的动态长距离时空自注意力模型，即 PDFormer，用于准确的交通流预测。具体来说，我们设计了一个空间自我注意模块来捕捉动态的空间依赖关系。然后，引入两个图形遮蔽矩阵，从短距离和长距离的角度突出空间依赖性。此外，还提出了一个交通延迟感知的特征转换模块，使 PDFormer 有能力明确地模拟空间信息传播的时间延迟。

在六个真实世界的公共交通数据集上的广泛实验结果表明，我们的方法不仅可以达到最先进的性能，而且还表现出有竞争力的计算效率。此外，我们将学习到的空间-时间注意力地图可视化，使我们的模型具有高度的可解释性。

背景和贡献

城市是社会分工和生产力发展的结果，是人类文明的重要组成部分。据联合国的统计，全世界有 55% 的人口生活在城市。城市的安全运行对于人类发展至关重要。世界各国的大型城市普遍被人口过载、交通拥堵、安全事故、环境污染等“城市病”所困扰。在波及全球的新冠肺炎疫情中，甚至有 92% 的感染发生在城市。这些问题给人民生命财产和国民经济带来巨大损失，也反映出现有的城市运行管理存在着重大问题。

物联网传感器、GPS 终端、智能手机所收集的城市时空大数据为破解城市管理所面临的挑战问题提供了全新的思路。利用这些数据知识，结合人工智能技术（数据挖掘、机器学习等），可以实现城市业务升级。

城市时空预测是人工智能与智慧城市结合的“主战场”，相对于传统的统计学模型，基于深度学习的城市时空动态预测具有较高的准确性，是现在城市数据挖掘领域的主流方法。常见的城市数据预测任务包括交通路况预测、人口密度预测、乘车服务需求预测、空气质量预测等等。

城市时空预测的基本挑战是有效地建模时空数据中复杂的时空相关性。时空图神经网络模型已成为解决这一问题的最有前途的方法之一。然而，基于GNN的模型在城市时空预测方面有三个主要限制：

1. 大多数现有方法以静态方式对空间相关性进行建模，这限制了其学习城市动态时空模式的能力。时空数据中各空间位置之间的空间相关性是随时间变化的，而不是静态的，因为它们受到城市中的旅行模式和意外事件的影响。例如，两个空间节点 A 和 B 之间的相关性在早高峰期间变得更强，在其他时段则更弱。

而现有的方法主要是以静态的方式建模空间相关性的模型（无论是预定义的还是自适应的），这限制了学习动态城市时空模式的能力。

2. 大多数现有方法只考虑短距离的空间信息，无法捕捉长距离的空间相关性。由于城市的功能划分，两个遥远的地点 A 和 C，可能反映出类似的时空模式，这意味着地点之间的空间依赖关系是长距离的。

现有的方法往往是局部设计的，无法捕捉长距离的依赖关系。例如，基于 GNN 的模型存在过度平滑的问题，使其难以捕捉到长距离的空间依赖关系。

3. 在时空系统中，不同位置之间的空间信息传播可能会出现时间延迟的影响。例如，当一个地点发生交通事故时，需要几分钟时间（延迟）来影响邻近地点的交通状况。然而，在典型的基于 GNN 模型的即时信息传递机制中，这样的特征被忽略了。

为此，我们提出了一个传播延迟感知的动态长距离 Transformer 模型 PDFormer，用于准确的城市时空预测。具体来说，我们设计了一个空间自注意力模块来捕捉动态的空间相关性。然后，我们引入了两个图掩码矩阵，以突出短距离和长距离的空间相关性。此外，我们提出了一种空间传播延迟感知的特征变换模块，以增强 PDFormer 建模空间信息传播延迟的能力。

论文主要贡献如下：

1. 提出了基于时空自关注机制的 PDFormer 模型，用于精确的交通流量预测。解决了前面提出的复杂交通数据动态、长距离、时延的问题。

2. 设计了一个空间自注意力模块，该模块通过不同的 graph masking 方法对局部地理邻域和全局语义邻域进行建模，并进一步设计了一种交通延迟感知特征转换模块，该模型可以显式地对空间信息传播中的时间延迟进行建模。

3. 在六个真实公共数据集上进行了多步和单步交通流量预测实验。提出的方法效果优于最先进的模型，并且具有较高的计算效率，模型高度可解释。

符号说明

交通路网：我们把路网表示为一个图，其是个节点的集合 (，是边的集合，是图的邻接矩阵。

交通流量张量：我们使用表示个路网节点在时刻的交通流量。我们使用

表示所有个节点在个时间步的交通流量构成的三维张量。是交通流量的维度，当包含流入和流出流量时，。

交通流量预测：交通流量预测的目的是根据历史观测数据预测交通系统在未来的交通流量。从形式上看，给定交通系统上观察到的交通流量张量，我们的目标是学习一个映射函数，从之前步骤的流量观察值中预测未来步骤的交通流量：

模型结构

上图显示了我们提出的框架的结构，由一个数据嵌入层、堆叠的时空编码器层和一个输出层组成。我们在下面详细描述每个模块。

PDFormer 模型由数据嵌入层（Data Embedding Layer）、堆叠的 L 个时空编码层（Spatial-Temporal Encoder Layer）和输出层（Output Layer）组成。

3.1 数据嵌入层（Data Embedding Layer）

数据嵌入层将输入转换为高维表示。首先，通过完全连接层将原始输入转换为，是嵌入维度。然后，我们进一步设计了一种时空嵌入机制，将必要的知识融入到模型中，包括对道路网络结构进行编码的空间图拉普拉斯嵌入和对交通流周期性进行建模的时间周期嵌入。

1. 空间图拉普拉斯嵌入（Spatial Graph Laplacian Embedding）：使用图拉普拉斯特征向量作为空间嵌入。首先计算归一化拉普拉斯矩阵，是邻接矩阵，是度矩阵。然后进行特征分解，对个最小非平凡特征向量进行线性映射得到空间图拉普拉斯嵌入。

2. 时间周期嵌入（Temporal Periodic Embedding）：周周期和日周期函数和分别将时刻转换为周索引（1 到 7）和分钟索引（1 到1440），得到周周期和日周期嵌入。

3. 时间位置嵌入（Temporal Position Encoding）：使用原始 Transformer 中的位置编码方法，得到输入序列的时间位置编码。

通过求和得到数据嵌入层的输出：

将被送入以下的时空编码器模块，为了方便起见，我们下文用代替。

3.2 时空编码层（Spatial-Temporal Encoder Layer）

我们设计了一个基于自我注意机制的空间-时间编码器层，以模拟复杂和动态的空间-时间依赖关系。编码器层的核心包括三个部分。第一个是空间自我注意模块，由地理空间自我注意模块和语义空间自我注意模块组成，以同时捕捉短距离和长距离的动态空间依赖。第二个是延迟感知的特征转换模块，它扩展了地理空间自我注意模块，以明确地模拟空间信息传播的时间延迟。此外，第三个是时间自我注意模块，捕捉动态和长距离的时间模式。

3.2.1 空间自注意力（Spatial Self-Attention, SSA）模块

首先计算每个时间片自注意力机制中的 Q、K、V 矩阵：

其中是可学习参数。

然后，我们在空间维度上应用自我注意操作来模拟节点之间的相互作用，并在时间上获得所有节点之间的空间依赖关系（注意分数）为：

节点之间的空间依赖性在不同时间片是不同的，即动态的。最后通过将注意力分数和矩阵相乘得到空间自注意力模块的输出：

上述简单的空间自注意力机制每个结点与所有节点交互，相当于将空间图视为完全图，但只有少数节点对之间的交互是必不可少的，包括距离近的节点对和距离远但功能相似的节点对。因此引入两个图 mask 矩阵和，以同时捕获交通数据中的短距离和长距离空间相关性。

geographic masking matrix ：当两个节点之间距离小于阈值时，权重为 1，否则为 0。
semantic masking matrix ：使用 DTW 方法计算节点之间历史交通流量的相似性，为每个节点选择具有相似度最高的个节点作为语义邻居。节点和语义邻居之间的权重设置为 1，否则为 0。

基于这两个 mask 矩阵，进一步设计了两个空间自注意力模块，即和，其可以定义为：

3.2.2 延迟感知特征转换（Delay-aware Feature Transformation, DFT）模块

在现实世界的交通状况中，存在着一个传播延迟。例如，当一个地区发生交通事故时，可能需要数分钟才能影响到邻近地区的交通状况。因此，我们提出了一个交通延迟感知的特征转换模块，从每个节点的短期历史交通流中捕捉传播延迟。然后，该模块将延迟信息纳入地理空间自我关注模块的键值矩阵中，以明确模拟空间信息传播的时间延迟。

首先从历史交通数据中识别出一组具有代表性的短期交通模式。具体地，使用大小为的滑动窗口对历史交通数据进行切片，并获得一组交通流序列。然后对这些交通流序列执行 k-Shape 时间序列聚类算法，使用每个簇的聚类中心代表改聚类，是长度为的时间序列。之后，我们使用代表聚类的结果。我们可以将视为一组短期交通模式。

我们将每个节点的历史流量序列与提取的流量模式集进行比较，将相似模式的信息融合到每个节点的历史流量序列表示中，如上图所示。

具体来说，给定节点从时间片到的步历史流量序列，我们首先使用嵌入矩阵得到高维表示为：

然后，我们用另一个嵌入矩阵将交通模式集中的每个交通流序列转换为一个记忆向量，即：

我们将节点的历史交通流量表示与交通模式记忆向量进行比较，得到相似性向量为：

然后，我们根据相似度向量对交通模式集进行加权求和，得到融合的历史序列表征为：

其中是一个可学习的参数矩阵。融合的历史序列表示包含节点从时间片到的历史交通流信息。最后，我们使用个节点的历史表征去更新注意力机制的键值矩阵：

这样，新的键值矩阵在时间片整合了所有节点从时间片到的历史交通流信息。当计算查询矩阵和新的键值矩阵进行乘积以获得时间片的空间依赖关系时，查询矩阵可以考虑到其他节点的历史交通状况。这个过程明确地模拟了空间信息传播中的时间延迟。

我们不在语义空间自我关注模块中加入这个模块，因为远方节点的短期交通流的传播延迟对当前节点的影响不大。

3.2.3 时间自注意力（Temporal Self-Attention, TSA）模块

在不同的时间片中，交通状况之间存在着依赖关系（周期性，趋势性）。因此，我们采用了一个时间自我关注模块来发现动态的时间模式。形式上，对于节点，我们首先获得查询、键和值矩阵为：

其中

是可学习参数。

我们在时间维度上应用自我关注的操作，得到节点的所有时间片之间的时间依赖关系为：

时间上的自我关注可以发现交通数据中不同节点的动态时间模式。此外，时间上的自我注意具有全局感受野，可以对所有时间片之间的长距离时间依赖关系进行建模。最后，我们可以得到时空自我关注模块的输出为：

3.2.4 异质注意力融合（Heterogeneous Attention Fusion）

在定义了三种类型的注意机制后，我们将异质性的注意融合到一个多头的自我注意块中，以降低模型的计算复杂性。具体来说，注意头包括三种类型，即地理、语义和时间头，分别对应于三种类型的注意力机制。这些头的结果被拼接并映射为输出，从而允许模型同时整合空间和时间信息。

此外，我们在多头自我注意块的输出上采用了一个位置全连接的前馈网络，以获得输出。

3.3 输出层（Output Layer）

为了进行多步预测，我们直接使用输出层将最终的隐藏状态转化为所需的维度：

其中是步的预测结果，和是 1×1 卷积。在这里，考虑到累积误差和模型效率，我们选择直接方式而不是递归方式进行多步预测。

实验

4.1 数据集

我们在六个真实世界的公共交通数据集上验证了模型的性能，包括三个基于图的高速公路交通流量数据集和三个基于网格的城市交通流量数据集。

统计信息如下：

4.2 总体性能

在这6个真实世界的数据集上，我们的模型与9个基线模型对比，在MAE/MAPE/RMSE等三个指标上都达到了最佳性能。

4.3 注意力权重可视化

在这一节中，我们分析了由 PDFormer 的空间-时间编码器学到的动态空间-时间注意力权重图，以提高其可解释性，并证明同时关注短距离和长距离空间依赖关系的有效性。我们比较了两种情况下的注意图，即有无两个空间遮蔽矩阵和的注意图，并使之可视化。在这里，为了简单起见，我们合并了地理自注意力和语义自注意力的注意力图。

如图（a）, （d）所示，如果没有掩码矩阵，模型会关注交通量大的城市主要环路（或高速公路），或者说注意力分布是分散的，几乎整个城市都会分享模型的注意力。然而，低流量的地点应该关注具有类似模式的地点，而不是热点地点。此外，太远的地点对当前地点的影响也不大。如果模型漫无目的地关注所有地点，其性能将被削弱。

相反，当掩码矩阵和被引入时，注意力会集中在周围的位置和遥远的类似模式的位置，如图（b）,（e）所示。

让我们以图（b）中的 592 号区域为例。高速公路 S12 经过这个区域，所以交通量一直很高。除了位于高速公路上下游的区域外，区域 592 还关注了区域 648 和 753。从图（c）中，我们可以看到这两个区域的历史交通量与 592 相似。此外，从图（h）（i）来看，这两个地区分别位于国贸立交桥和北京二环路附近，它们的城市功能与 592 类似，都是主要的交通枢纽。

在另一个案例中，区域 252 的交通量较低，但我们可以从区域 252 重点关注的区域 370、403 和 842 观察到类似的模式，即类似的功能和历史交通变化。

这个案例研究表明，在引入空间掩码矩阵后，模型不仅考虑了短距离的空间依赖性，而且还识别了全局功能区以捕捉长距离的空间依赖性。在我们的消融实验中也定量地表明了，去除掩码矩阵后，模型性能急剧下降，这支持了这里的观点。

4.4 模型效率

由于基于注意力的模型有更好的表现，我们将 PDFormer 的计算成本与其他基于自我注意力的基线在 PeMS04 和 NYCTaxi 数据集上进行比较。

上表报告了每个历时的平均训练和推理时间。我们发现，PDFormer 在短期和长期流量预测方面都达到了有竞争力的计算效率。与性能最好的基线 ASTGNN 相比， PDFormer 分别减少了超过 35% 和 80% 的训练和推理时间。GMAN 和 ASTGNN 保留了一个耗时的编码器-解码器结构，在 STTN 和 PDFormer 中被一个 FNN 取代。

总结

在这项工作中，我们提出了一个新的具有空间-时间自注意力的模型，用于交通流量的预测。具体来说，我们开发了一个空间自关注模块，以捕捉动态和长距离的空间依赖关系，以及一个时间自关注模块，以发现交通数据中的动态时间模式。我们进一步设计了一个延迟感知的特征转换模块，以明确地模拟空间信息传播的时间延迟。

我们在六个真实世界的数据集上进行了广泛的实验，以证明我们提出的模型的优越性，并将学习到的注意力权重进行可视化，以使模型可解释。作为未来的工作，我们将把模型应用于其他的时空预测任务，如风能预测。此外，我们还将探索交通预测中的预训练技术，以解决数据不足的问题。

引用

如果你觉得本文有用的话，请引用：

@inproceedings{pdformer,
  title={PDFormer: Propagation Delay-aware Dynamic Long-range Transformer for Traffic Flow Prediction},
  author={Jiawei Jiang and 
            Chengkai Han and 
            Wayne Xin Zhao and 
            Jingyuan Wang},
  booktitle = {{AAAI}},
  publisher = {{AAAI} Press},
  year      = {2023}
}

如果你觉得 LibCity 有用的话，请引用：

@inproceedings{libcity,
  author    = {Jingyuan Wang and
               Jiawei Jiang and
               Wenjun Jiang and
               Chao Li and
               Wayne Xin Zhao},
  title     = {LibCity: An Open Library for Traffic Prediction},
  booktitle = {{SIGSPATIAL/GIS}},
  pages     = {145--148},
  publisher = {{ACM}},
  year      = {2021}
}