一种基于时空格兰杰因果的交通流预测方法

1.本发明属于交通流预测技术领域，尤其涉及一种基于时空格兰杰因果的交通流预测方法。


背景技术：

2.随着智能交通系统的不断发展，作为智能交通系统重要功能之一的交通预测得到了越来越多的关注。交通预测属于时间序列预测任务中的一种，需要根据交通传感器记录的历史交通数据对未来时刻的交通数据进行预测，包括流量预测、流速预测和高峰期预测等，能够为城市管理、交通规划、路径优化等决策提供帮助。
3.交通预测任务的基本假设是交通数据背后隐含着某种稳定的模式，因而可以从历史数据中发现这种模式并用于未来时刻的预测，近年来大量交通预测的研究涌现。基于统计学的方法最早被应用，包括历史平均值(historical average，ha)、向量自回归(vector autoregression，var)、整合移动平均自回归(autoregressive integrated moving average，arima)模型、卡尔曼滤波模型(kalman filtering model)等。随着深度学习的发展，前馈神经网络模型(feed forward neural network)深度信念网络(deep belief network，dbn)等回归模型被用于交通流预测，循环神经网络(recurrent neural network，rnn)及其变体长短时记忆网络(lstm)和门控循环单元(gated recurrent unit，gru)也被用于对交通流数据的时间依赖性建模。然而，上述方法仅仅建模了交通流数据的时间依赖性，却忽略了不同路网节点间的空间依赖关系。现有的观点普遍认为，交通预测任务不同于一般的时间序列预测任务，除了趋势性、周期性等时间动态模式的捕捉外，路网结构约束下的空间依赖关系更加重要。
4.为捕捉空间依赖关系，基于卷积神经网络(convolutional neural network，cnn)的模型被用于对路网节点的空间依赖性建模，然而这种模型只适用于欧几里德数据，不适用于非欧的路网数据。因此，能够对离散化的非规则数据进行表示的图神经网络(graph neural network，gnn)被用于对复杂路网进行建模，已经成为交通预测事实上的经典模型。这类方法主要从静态的路网拓扑结构中抽象出一种节点间局部的连接关系并建模为空间图输入到gnn结构中，通过gnn的消息传播机制实现交通信息在节点间的流动，比如时序图卷积网络(temporal graph convolutional network，t-gcn)、graph wavenet、时空图卷积网络(spatio-temporal graph convolutional networks，stgcn)等，也有方法考虑了空间依赖关系在时间轴上的效应，将空间图与时间图组合输入到gnn结构中，如stsgcn、stfgnn和stgode。
5.空间依赖关系的本质在于精确描述路网节点间的交通信息如何传递，即交通信息的传递如何受其他路网节点的影响。然而，微观交通工具的移动行为具有非常大的不确定性，使得追踪和预测交通信息在路网中的传递具有固有的困难，尤其是在长时预测时，交通信息的传递是一个全局的、动态的过程，空间图所刻画的静态的、局部的空间依赖关系无法表达路网节点间全局的、动态的交通信息(global-dynamic traffic information,gdti)
的传递。如何建模gdti在路网中的传递，并通过gnn的消息传播机制对未来时刻的交通信息进行预测，是长时预测中的关键问题。


技术实现要素：

6.有鉴于此，本发明提出一种新的假设：gdti的传递在微观层次上具有强的不确定性，但是在宏观层次上表现为一种稳定的交通流传递的因果关系(transmitting causal relationship，tcr)，在全局、动态的交通流经过长时的传递中是可逼近的，且可以通过时空格兰杰因果来建模。基于这一假设，本发明提出了一种时空格兰杰因果对gdti的长时传递进行逼近，从而捕获长时预测所需的全局、动态的空间依赖关系。在此基础上，本发明提出了一种使用时空格兰杰因果图的图神经网络交通流预测框架(stgc-gnns)，根据gdti的传递进行预测。
7.本发明公开的基于时空格兰杰因果的交通流预测方法，包括以下步骤：
8.全局动态交通信息gdti表达长时预测下路网的空间依赖关系，具体表现为交通流传递的因果关系tcr，将交通流传递的因果关系tcr建模为时空格兰杰因果关系图；
9.考虑全局动态交通信息gdti在传递时的时空耦合，根据时空对齐算法捕获tcr；所述时空对齐算法考虑tcr中因果关系从原因节点传递到结果节点的时间，根据路网中全局动态交通信息gdti全局传递的起始点的空间距离进行时间序列的对齐，建模tcr传递的时空滞后；
10.使用时空格兰杰因果检验方法从对齐后的时间序列中测试出哪两个节点间有gdti的传递，从而捕获动态交通流下稳定的tcr；
11.将得到的时空格兰杰因果检验图输入到基于gnn的交通预测模型中，同时捕获交通路网的时间依赖性和空间依赖性；所述基于gnn的交通预测模型包括两个模块，一个用于建模时间依赖性，一个使用gnn建模空间依赖性；其中，gnn结构传播和集成有空间依赖性的节点间的交通信息。
12.本发明的有益效果如下：
13.提出了一种时空格兰杰因果来建模tcr，这种因果关系能够表达一种全局、动态的空间依赖关系，能够捕获gdti从而提升长程预测效果。本发明首先通过时空对齐算法对tcr全局传递下的顺序性和滞后性进行建模，在此基础上使用格兰杰因果检验对节点间的tcr进行探测。
14.提出了一种使用时空格兰杰因果图的图神经网络交通流预测框架(stgc-gnns)用于提升长时预测效果，能够与所有使用空间图建模空间依赖关系的基于gnn的交通流预测模型相兼容。
15.在一个预测复杂性高的现实世界数据集上进行了性能对比实验，结果表现本发明的方法能够比骨干模型在45分钟和60分钟的长时预测上效果更好。可视化结果表明本发明能够在所有预测时长上提升对交通系统交叉点、边缘点和偏远点等具有高预测难度的点的预测，能够进一步验证本发明的有效性。
附图说明
16.图1本发明时间依赖性示意图；
17.图2本发明空间依赖性示意图；
18.图3本发明时空依赖性示意图；
19.图4本发明交通信息在时间轴和空间轴上的传递示意图；
20.图5本发明同一个交通路网进行15min预测时的示意图；
21.图6本发明同一个交通路网进行30min预测时的示意图；
22.图7本发明基于gnn的交通预测模型示意图；
23.图8本发明时空对齐前后对比示意图；
24.图9传统的格兰杰因果校验方法示意图；
25.图10本发明的时空格兰杰因果校验方法示意图；
26.图11本发明时空格兰杰因果校验方法捕获长程时空依赖性示意图。
具体实施方式
27.下面结合附图对本发明作进一步的说明，但不以任何方式对本发明加以限制，基于本发明教导所作的任何变换或替换，均属于本发明的保护范围。
28.对于主流的、被广泛使用的gnn-based方法来说，空间依赖关系的建模尤为重要。空间依赖关系的本质在于精确描述交通信息在路网间的传递，这一任务在复杂路网的交通流预测尤其是长期预测中非常困难。现有方法建模的局部的、静态的空间依赖关系无法描述交通信息在经过长程的、动态的传递导致的全局扩散的状态，即空间图无法建模姐路网中全局的、动态的交通信息(global-dynamic traffic information,gdti)的传递。如何建模gdti在路网中的传递，并通过gnn的消息传播机制对未来时刻的交通信息进行预测，是长期预测中的关键问题。
29.为了捕获gdti的传递，本发明提出了一种tcr假设，并进一步使用时空格兰杰因果对tcr进行表达，实现对全局的、动态的空间依赖关系的建模。
30.空间依赖关系的建模本质上是在捕捉交通信息在路网不同节点间的传递，而对于长期(long-term)交通预测任务来说，交通信息由于经过了长期的传递，导致其具有全局性和动态性，因此精确地捕捉具有困难。全局性描述了这种传递在空间尺度上跨越的距离具有长程性，动态性则描述了其在时间尺度上的不确定性和复杂性。为了尽可能地精确地建模出gdti在空间上的传递，本节提出了一种假设，传递性因果关系假设(transmitting causal relationship，tcr)，该假设认为长时预测的关键在于建模路网中全局的、动态的交通信息的传递，这种传递在微观上具有非常强的不确定性和复杂性，但在宏观上表现为一种稳定的因果关系。
31.由于现实世界中观测到的交通流数据是交通信息的动态变化和路网复杂拓扑约束共同作用下的结果，而交通信息的传递在时间尺度和空间尺度上并非独立，能够导出三种依赖关系的存在，使得交通流预测任务更具有挑战性.在本节中，为了使本发明的假设及后续方法的表达更加清晰，首先对三种依赖关系及其导出的滞后性(lag)进行了重定义，并描述了对现实交通系统中的三个观察，能够支撑本文方法的基本假设与动机.需要注意的是，在定义空间依赖性时，由于本发明想要捕捉的是一种传递的空间依赖关系，而这种依赖关系是有向的，因此引申出了对目标节点(target node)和源节点(source node)的定义，对于交通流预测领域是新颖的。
32.定义1：时间依赖性表示同一个节点在当前时间步的交通信息对未来时间步的交通信息所具有的影响。
33.定义2：时间滞后性是时间依赖的两个时间步中传输交通信息的时间间隔。
34.定义3：空间依赖性表示在当前时间步上，一个节点的交通信息对其他节点的交通信息所具有的影响。
35.定义4：空间滞后性是在一个时间步中两个空间依赖的节点间发送交通信息的距离。
36.定义5：目标节点与源节点
37.当一对节点具有空间依赖关系时，本发明将传递交通信息的节点称为出节点(out-node)，将接收交通信息的节点称为入节点(in-node)。如图3，节点4为源节点，节点1、2、3、5、7为目标节点。
38.定义6：时空依赖性表示一个节点在当前时间步的交通信息对其他节点在未来时间步的交通信息所具有的影响。
39.定义7：时空滞后性是被不同的时空依赖的节点传输交通信息消耗的时间滞后性。
40.观察结果1：
41.由于路网中的交通节点并非完全独立，而是随着交通工具的移动与其他节点产生交互，表现为交通信息的传递，会导致交互的节点间存在依赖关系，这种依赖关系存在于空间位置不同的节点之间，称为空间依赖关系。在基于gnn的模型中，对于待预测节点来说，如果能够正确地建模空间依赖关系，就能正确引入其他节点的信息，进而提升自身的预测。
42.本发明观察到，对于基于gnn的模型来说，由于节点间的空间依赖关系通过输入图(input graph)来建模，因此可以通过对比输入不同的输入图与输入仅自连接的图的预测结果来判断输入图中是否包含了有效的空间依赖关系。在metr_la数据集上，当输入图为空间距离图(用空间权重矩阵spatial weighting matrix描述)和自连接图(由单元矩阵identity matrix描述)时模型的预测结果。
43.对于不同的基于gnn的交通预测模型来说，在任意一种预测尺度(horizon)上，随着输入图中与目标节点连接的节点的变化，模型预测的结果也会改变。绝大部分情况下，输入空间权重矩阵的预测结果要优于输入单元矩阵的结果，这说明在进行交通预测时，考虑其他节点与目标节点间的空间依赖关系是必须且有效的；然而，在horizon＝45min时，stgcn在输入空间权重矩阵时的预测结果反而差于输入单元矩阵的结果，这说明，当捕捉的空间依赖关系有误或冗余时，可能会导致模型的预测结果不如仅使用目标节点本身信息的预测结果。本发明认为这一现象后面的原因是空间依赖性造成的。
44.因此，对于基于gnn的交通预测模型来说，建模空间依赖关系的输入图的构建会直接影响模型的预测效果，即使模型其他的设置全都保持一致。因此对于基于gnn的交通预测模型来说必须考虑空间依赖性。
45.观察结果2
46.在现实世界的交通系统中，由于交通工具从一个节点移动到另一个节点的过程，既需要跨越空间距离，同时又需要消耗时间，因此，交通流可以视为交通信息跨时空的传递过程。这种观察表明，交通路网中交通信息在时间轴和空间轴上的传递并非独立，而是相互影响的，这就是交通信息传输中的时空纠缠(spatial-temporal entanglement)。如图4，不
同时间切片间的箭头表示交通信息在时间轴上的传递，而不同节点间的箭头则表示这部分交通信息跨空间的传递。
47.交通预测的关键在于建模交通流在路网上的分布随时间的变化，即时空依赖关系。然而，由于交通信息传输中的时空纠缠，时空依赖关系不等于时间依赖关系和空间依赖关系的相加或拼接。因此，如果想从全局传递下的交通信息中捕获路网的空间依赖关系，就必须要考虑交通信息跨空间传递的时空滞后。本发明在算法1中考虑这个观察结果。
48.现有方法普遍认为路网节点的空间分布是度量空间依赖关系的重要指标，因此常常使用交通网络拓扑图(traffic network topology graph)或空间距离权重图(spatial distance weighting graph)作为空间图(spatial graph)输入到gnn结构中，本质上建模的是一种局部的、静态的依赖关系，即在一定区域内由固定的路网节点分布得到的空间依赖关系。然而，当交通信息在经过长期的传递时，会在空间上表现出全局性，而在时间上表现出复杂的动态性，本发明将这样传递的交通信息成为global-dynamic traffic information(gdti)。长期预测的关键就在于建模gdti的传递，因此无法被局部、静态的空间依赖关系描述。
49.图5、图6分别是针对同一个交通路网进行15min和30min的预测时的示意图。假设在该交通系统中，交通信息在相邻接的两个交通路口之间传递需要消耗的时间为15min。那么，当本发明预测目标路口后15min的交通特征(如流量、流速等)时，只需要追踪到1阶邻居节点的当前时刻的交通特征即可，因为这部分交通特征将消耗15min传递到目标节点。
50.同理可得，当预测目标节点30min的短时流量时，需要追踪到2阶邻居节点的交通特征。推断可得，在预测45min及更长的预测时长时，需要追踪的节点离目标节点的距离会更远，因此，需要捕捉传递时间为45min的gdti的传递，而现有的空间图难以捕获。
51.tcr假设
52.为了尽可能精准地捕捉长时预测下路网中gdti的传递，本发明提出了tcr假设，并根据上述观察，对tcr的性质进一步假设，以得到本发明。根据观察结果1和观察结果3，本发明认为长时预测下路网的空间依赖关系可以由gdti的传递表达，具体表现为一种tcr，因此本发明试图捕捉这种tcr并直接建模为图输入到gnn结构中；根据观察结果2，本发明在捕获tcr的过程中，考虑了gdti在传递时的时空耦合并设计了时空对齐算法。
53.如图7所示，基于gnn的交通预测模型总是可以形式化为一个捕获空间依赖关系的模块和一个捕获空间依赖关系的gnn.其中，空间依赖性被建模为图输入到gnn结构中。然而，现有的空间图描述的局部的、静态的空间依赖关系在长期预测时可能会失效。本发明提出了一个时空格兰杰因果检验(spatial-temporal granger causality test)方法，捕获一种全局的、动态的空间依赖关系并建模为时空格兰杰因果关系图输入到该框架中。
54.空间依赖关系的实质是精确捕获交通信息在路网间的传递，虽然微观层次上gdti的传递不确定性非常大因而难以捕捉，但在宏观层次上会趋于一种稳定的模式。本发明认为这种模式可以从长时观测的、动态变化的交通信息全局传递的过程中的检测出来，这种模式在宏观上表现为一种交通流传递的因果关系(transmitting causal relationship，tcr).这种关系被建模为时空格兰杰因果关系图。
55.根据tcr假设，本发明进一步了提出了一种时空格兰杰因果检验方法，能够捕获路网中全局的、动态的空间依赖关系。时空格兰杰因果关系预测方法进一步分为两个模块，时
空对齐模块考虑了tcr中因果关系从原因节点传递到结果节点的时间，根据路网中gdti全局传递的起始点的空间距离进行时间序列的对齐，建模tcr传递的时空滞后；格兰杰因果检验模块
56.(granger causality test module)能够从对齐后的时间序列中测试出哪两个节点间有gdti的传递，从而捕获动态交通流下稳定的tcr。
57.根据tcr假设，gdti传递的过程可以视为原因节点对结果节点产生因果关系的过程，即tcr的作用过程，根据观察结果2可以导出tcr具有两个显著的属性：
58.因果滞后性(causal lag)：结果发生和原因发生具有一个时间差，在交通路网中表现为原因节点和结果节点之间的时空滞后。
59.因果顺序性(causal order)：结果总是发生或被观测在原因之后，在交通路网中表现为结果节点接收(receive)gdti的时间总是发生在原因节点释放(release)gdti之后。
60.因此，本发明设计了一种时空对齐算法(spatial-temporal alignment algorithm)，分为两个步骤：
61.1)根据因果滞后性，计算出tcr从原因节点向结果节点传递所消耗的时间，即两者间的时空滞后
62.2)根据因果顺序性，本发明将原因节点的时间序列沿时间轴平移s个时间步，将tcr在原因节点(cause-node)上产生和在结果节点(effect-node)上作用的时间进行对齐，进而保证能够直接从观测到的结果中推断出因果机制.
63.根据前述中的定义，对于tcr来说，源节点为原因节点，而目标节点为结果节点。节点间的空间滞后性(spatial lag)是他们之间的空间距离，时空滞后性(spatial-temporal lag)则是gdti从原因节点流向结果节点需要消耗的时间，即tcr传递需要的时间。由于节点间的时空滞后性不仅与节点间的空间距离相关，还与交通信息流动的速度相关，这无法精确度量，本发明使用源节点的平均速度作为交通信息流速的逼近。
64.算法1.时空对齐算法
65.时空对齐算法是将源节点的时间序列沿着时间轴向后平移，步长等于源节点和目标节点间的时空滞后。时空滞后性等于源节点与目标节点间的空间滞后与源节点的平均交通速度的比值。
66.如图8，b为source-node，a为target-node，(a)为对齐前，(b)为对齐后。
67.对原因节点和结果节点进行了时空对齐后，本发明认为原因节点和结果节点在同一时刻包含了同一部分gdti，可以直接从两者的观测时间序列中推断是否有gdti的流动。因此，本发明需要解决另一个重要的问题，如何从长时观测的、动态变化的时间序列中检测出tcr。
68.基于对现实世界系统的观察，在交通流传递的过程中，下游节点的交通信息中会包含其上游节点的交通信息，因而上游节点的交通特征可以显著提升下游节点的交通特征预测。而格兰杰因果检验认为加入后能明显提升预测效果的时间序列变量为原因，而被提升的则为结果，这被本发明注意到。因此，本发明认为交通系统中的tcr可能表现为路网节点时间序列上存在格兰杰因果关系，利用格兰杰因果检验算法，能够从两节点对齐后的时间序列中检测出传递的起始关系，这种起始关系能表达一种全局的、动态的空间依赖。
69.granger因果分析是一种判断不同时间序列之间是否存在因果关系的方法，基本
思想是：若采用时间序列x和y的历史信息对y进行预测的结果优于仅采用y的历史信息对y进行预测的结果,即时间序列x有助于解释时间序列y的未来变化趋势,那么时间序列x是时间序列y的granger原因。
70.granger因果分析背后隐含着两个重要假设：
71.1)加入原因变量的信息能够为还原结果变量提供更多的信息：如果时间序列x是时间序列是时间序列y的原因，那么同时使用时间序列x和y的数据比仅使用时间序列y的数据要能够更好地预测时间序列y。
72.2)在使用过去数据预测未来数据时需要考虑时间滞后，无论是仅采用y的历史信息对y进行预测，还是加入时间序列x对y进行预测，都需要考虑当前时刻前m个步长的时间序列值，其中m为模型设定的时间滞后值。
73.根据以上假设，granger因果检验方法分别为以上两种预测建立向量自回归模型如下：
[0074][0075][0076]
其中x
t-j
和y
t-j
分别代表时间序列x和y在t-j时刻的交通流数据的数值，αj、aj和bj代表自回归模型的回归参数，εy和ε
y|x
分别代表两个自回归模型的残差，m代表模型的阶数，在这里也可以理解为时间滞后值(temporal lag)。如果υar(ε
y|x
)＜υar(εy)，则可以判断时间序列x对时间序列y具有统计意义下的granger因果关系，表示为：
[0077]
x granger-causes y
[0078]
根据granger因果分析方法对节点a的时间序列和节点b的时间序列进行granger因果检验时，本发明需要同时输入待检验的时间序列xa和xb：
[0079]h0 hypothesis：x
b does not granger-cause xa[0080]
将两个节点的时间序列输入进行granger因果检验，如果返回的p值低于显著性水平，则拒绝原假设，即得到的结论为：节点b是节点a的格兰杰因。图9是传统的granger因果检验方法：
[0081]
本发明将对齐后的两个节点的时间序列输入到granger因果检验模块，即使用时空granger因果检验方法对两个节点间的tcr进行测试，如图10。
[0082]
时空granger因果检验能够检测出两个交通节点之间的格兰杰因果关系，这种关系能够显示全局和动态的空间依赖性。为了将时空granger因果检验捕捉到的关系建模为输入图输入到基于gnn模型中用于预测，结合交通预测的实际观察，本发明做了以下设置：
[0083]
为了防止把长程时空依赖关系过滤掉，本发明不通过距离阈值(distance threshold)或拓扑相邻性(topological adjacency)来得到输入图，而是将节点间的距离建模为时空滞后性并使用时空格兰杰因果检验对全局传递下的空间依赖关系进行探测。需要注意：本发明不直接使用数据集中提供的成本“cost”(表示不同节点间的空间距离)，而
是计算路网中两个节点间最短距离并得到最小的cost，原因是尽可能保留检测到的空间依赖性，因为原始数据集不能提供任意两个节点间所有的cost，即使是两个非常近的节点。这样可以得到长程空间依赖性中的时空滞后性，因为原始数据集很可能不提供很远的节点间的cost。
[0084]
原因和结果的方向性：时空格兰杰因果关系作为节点间空间依赖关系的一种表现，描述一种交通信息传递的因果关系，在现实世界中可以理解为对交通信息的追踪。其中，原因节点对应交通流的源节点而结果节点对应交通流的目标节点。因此，不同于空间图中节点的依赖关系是无向的，时空格兰杰因果检验图中节点的关系是有方向的，且方向由原因节点指向结果节点。这不仅仅与现实世界的情况相符合，即交通信息总是由源节点流向目标节点，而且与gnn的消息传递机制也保持一致，即原因节点的信息能够传递到结果节点并且更新结果节点的特征，从而帮助结果节点进行更好的预测。
[0085]
最终，本发明将得到的时空格兰杰因果检验图输入到基于gnn的交通预测模型中，可以同时捕获交通路网的时间依赖性和空间依赖性。基于gnn的交通预测模型包括两个模块，一个用于建模时间依赖性如rnn及其变量参数，一个使用gnn建模空间依赖性。其中，gnn结构可以传播和集成有空间依赖性的节点间的交通信息，可以很好的描述gdti的传输。本发明将评价基于gnn的交通预测模型输出结果的预测交通能力。
[0086]
实验和结果
[0087]
本发明在真实世界数据集metr_la上进行了实验，metr_la是美国洛杉矶高速路数据集，是交通预测的基准测试集之一。对于该数据集，空间图的建模形式为空间权重图(也即空间距离图spatial distance graph，sd graph)，即使用高斯滤波将节点间的空间距离转换为权重。
[0088]
基于观察结果1，本发明对比了stgcn在美国两个高速公路数据集上使用自连接(邻接矩阵为单位矩阵)和sd graph(邻接矩阵为空间权重矩阵)作为输入的预测差异，前者代表仅使用节点的时间依赖性进行预测的情况，而后者则代表着引入了空间依赖性的情况，如下表：
[0089][0090]
可以发现，在pems_bay数据集上，基于gnn的模型在使用自连接图作为输入时的预测效果与使用sd graph的效果非常接近，而metr_la上两者差异则非常显著，且pems_bay整体的预测误差数值较小。这说明metr_la数据集具有较高的复杂性和预测难度，且能够更显著地对比不同的输入图对模型预测的影响，因而本论文选择该数据集进行实验和分析。
[0091]
metr_la数据集的基本信息如下。
[0092][0093]
为了更加直接地对比input graph itself对于时空依赖关系捕捉的有效性，本发明选择了三个基于gnn的模型直接使用输入图而不是如注意力机制那样作传输操作。这类模型能够使用gnn机制根据输入图表达的依赖关系进行消息的传递、聚合和更新，能够直接体现邻居节点信息对目标节点预测的提升。由于本发明的stgc graph是可插拔的，因此，本发明选择了具有代表性的gnn结构的模型t-gcn、stgcn和graph wavenet，能够统一到本发明提出的框架下进行对比。
[0094]
本发明将这三类模型作为主干模型，即基于gnn的交通预测模型。除此操作之外，为了对本文方法产生的效果进行公平、有效的评估，数据集的划分、模型的结构和训练的设置等都与原模型保持一致。
[0095]
为了本发明在交通流预测任务的效果进行评估，本发明使用以下指标作为真实交通流数据y
t
和预测数据差异的度量：
[0096]
(1)mean absolute error(mae):
[0097][0098]
(2)mean absolute percentage error(mape)：
[0099][0100]
(3)root mean squared error(rmse)：
[0101][0102]
本发明在15min,30min,45min和60min共4个预测维度(horizon)上分别进行了性能评估，对比结果如下，其中使用sd graph作为输入图的backbone使用原模型名，而stgc-代表使用时空格兰杰因果图作为输入图的模型。
[0103]
可见，对于同一个骨干模型来说，在15min和30min的短时预测上，sd graph在各个指标上都具有更好的预测效果，而在45min和60min的长时预测上，时空格兰杰因果图比sd graph具有更好的效果。这说明，由局部、静态的连接关系构建的空间依赖关系能够为目标节点捕捉到大部分短时间内有交互的节点，但是这种关系在长时预测时似乎会失效。长时预测更需要捕捉长程依赖性，这需要在交通信息的全局传输中被检测到。
[0104][0105][0106]
时空格兰杰因果关系图与sd图在控制变量设置下的对比实验已经能够说明时空格兰杰因果关系图在长时预测时相比于sd图更加有效。为了进一步说明时空格兰杰因果关系图的这种有效性是自身带来的而不仅仅是因为sd图的失效，本发明将输入图为仅自连接图(邻接矩阵为单位矩阵)的情况作为对比，实验表明时空格兰杰因果关系图在长时预测时能够取得比自连接图更好的效果，这说明时空格兰杰因果关系图建模了有效的空间依赖性。实验结果如下表，其中(-)代表输入图为仅自连接图的情况。
[0107]
node)的下游方向。可以发现，本发明检测到的原因(上游)和结果(下游)与地图上高速公路标注的方向一致。
[0118]
而sd graph中构建的局部的连接关系是一种从不变的路网空间结构(节点位置分布、路网拓扑等)生成的静态的关系，这种关系没有方向，不能够刻画动态的交通流导致的交互。高速公路的通行受到交通规则的约束，处于不同通行方向道路的节点间哪怕距离很近，如果不是在交叉路口，也很难直接有交互。然而，如果仅仅根据空间距离判断，而不考虑实际交互的可能性，则很可能引入错误的空间依赖。sd graph中捕获的空间依赖性实际上并不能产生交通流的交互，引入这部分节点的信息很难真正帮助目标节点进行预测，这是为什么空间距离并不代表一切。
[0119]
而时空格兰杰因果关系由于刻画的是由于交通流在路网全局传递下带来的空间依赖关系，因而能够更精准地建模这种交通流传递的方向，在一定意义上能够避免引入错误的信息。目标节点的时空格兰杰因果关系节点总是出现在其下游路段上，而空间连接的节点则可能出现在同行方向与其相反的道路上，是逆流或顺流。
[0120]
stgc捕获长程空间依赖性.在长程空间依赖性的捕捉上，时空格兰杰因果关系能够捕捉长程空间依赖性，而sd图建模的局部的连接关系往往只包括了空间距离较近的节点，这不会花更多时间在与预测的节点交互上。如图11，预测的节点在图11上图的左部，被时空格兰杰因果关系捕获的长程空间依赖性可以延伸到图11下图的右部。
[0121]
本节，本发明分析时空格兰杰因果关系能够在45min及更长的预测时长上超过sd graph的可能原因。
[0122]
空间距离不代表一切：在许多交通预测数据集中，节点间的空间距离并不是节点间实际的地理距离，而是一个节点到另一个节点沿路网传递的距离，这种距离需要实际测量，而不能仅靠节点的经纬度获取。因此，在原始数据集中，可能会存在数据缺失的问题，即两个邻近的节点距离值缺失。然而，sd graph的构建只考虑了数据集中记录的距离，因此可能出现：更近的节点在sd graph中没有连接，反而远的节点有连接，哪怕距离更近的节点间是可达的。
[0123]
此外，在高速公路这种方向不同的道路间具有明显的物理限制的交通系统中，两个节点哪怕空间距离非常近，但也可能需要花费很长的时间成本才能连接，如果这两个节点被判断为空间依赖，则可能为预测带来很差的效果。比如，在通过空间距离滤波生成的sd graph中，两个节点分别在通行方向相反的道路上的节点被判断为邻接。这种数据集中的错误信息可能会导致sd graph的预测效果变差，本发明相当于在直接使用这种信息的基础上再做了一次是否有gdti传递的判断，能够识别这种错误的连接，从而规避了negative的影响。
[0124]
本发明对路网中每一对节点的时空滞后性进行了统计，发现了一个有趣的现象。在理想情况下(即节点间交互以最短路径为规划，且保持以源节点的平均流速平稳传递)，大部分节点在30min之内可以完成交互(时空滞后性《＝6)，而相距最远的节点也能够在45min之内完成交互(时空滞后性《＝9)，这是sd图方法的能力边界范围。也就是说，当预测时长》45min时，可能有大量的交通流已经脱离了系统，而新进入系统的流量未知，因此，系统中整体的流量不能够保证恒定不变。在这种情况下，交通信息传递的不确定性进一步变大，预测所需要捕捉的空间依赖性仍然是长程依赖性，但是已经不能够仅仅根据空间位置
来推断，必须要从观测数据中挖掘一种稳定的关联。因此，本发明猜想，当预测时长超过了一个交通系统中的最大传递时间时，局部的、静态的连接关系不足以应对这种不确定性。本发明本质上是从长时间观测的、动态变化的全局传递的时间序列中挖掘一种稳定的空间依赖关系，一定程度上能够解决长时预测的问题。这种不确定性到底如何建模，交通流的传递如何追踪，是未来可以思考和解决的问题。
[0125]
空间依赖性是动态变化的还是不变的：交通流实际上是由大量微观层次的交通工具在路网中移动所生成的宏观层次上的可观测的数值，这些微观交通工具的轨迹具有非常高的不确定性，但是在宏观层面上则表现出了一系列规律/模式。其中，空间上模式的识别通过空间依赖关系来建立。sd graph的构建本质上是从静态的、空间结构不变的路网中建立空间依赖关系，背后的假设是空间上越相近、空间依赖关系越强，因此，这种空间依赖关系实际上是静态的、局部的。然而，正如本发明所观察的，交通时间序列实际上是随时间、空间动态变化的、复杂的，且潜在地受到环境、社会等多种因素的影响，静态的空间依赖关系已经不足以描述路网变化的空间依赖。本发明的方法观测数据，即交通信息在全局传递下生成的路网所有节点的时间序列着手，试图从中检测出路网的空间依赖。本发明假设路网的空间依赖虽然是动态变化的，但会存在一种平衡，即存在一种稳定的空间依赖关系，变化的空间依赖始终朝这种稳态逼近，因而这种稳态可以最大程度地解释路网的空间依赖关系，且有助于预测。本发明的方法则是从动态变化的交通时间序列中检测一种空间依赖关系，能够最大程度地接近这种稳态。因此，在某些时间段或预测尺度上，本发明的预测效果可能与真实情况存在偏差。未来可以选择分时间段输入，为每一个时间段检测出一张时空格兰杰因果关系图，实现空间依赖关系的动态建模，可能对于复杂的交通预测问题效果更好。
[0126]
时间图的作用是什么：在基于gnn的交通预测模型中还有一类模型将空间图与时间图进行组合作为输入。这类模型中，时间图往往选择将时间序列相似度更高的节点相连接，一定程度上能够弥补仅使用静态局部连接关系的空间图的不足。然而，这类模型最终在决策时，往往通过裁剪(cropping)或最大池化(maxpooling)等操作保证效果，实际上仍然主要依赖于空间图。本文没有针对这类模型做对比与改进，因为本发明的方法也是从观测时间序列中检测关系，可能会与时间图包含的信息形成冗余。本发明认为，时间图实际上是对空间依赖关系在时间轴上的效应进行建模，可以帮助更精确地建模空间依赖关系，但如何发挥它的作用是一个开放的、待讨论的问题。
[0127]
本发明的有益效果如下：
[0128]
本发明提出了一种时空格兰杰因果校验方法，能够对路网空间依赖关系进行建模，捕捉全局的、动态的交通信息在路网中的传递。不同于从路网空间分布中生成的局部连接的静态空间依赖关系，本发明提出的时空格兰杰因果校验方法能够捕捉长程依赖性，从长时观测的交通流的动态变化下逼近背后稳定的交通流传递的因果关系(tcr)，因而能够在45min和60min的长时预测表现更好。本发明从现实世界的3个观察出发，相比于现有的使用sd graph的空间依赖关系建模方式，主要做了以下改进：
[0129]
1)考虑到交通预测任务中空间依赖关系的重要性，结合图结构(graph structure)对关系的表达能力及gnn model对信息的传播和汇聚能力，本发明尝试构建一种空间依赖关系，能够嵌入到基于gnn的交通预测模型中帮助预测；
[0130]
2)考虑到交通流传递是一个时空交互的过程，交通信息的传递存在时空耦合，尤其是在全局传递中更不容忽略。本发明据此进一步导出了tcr的order和lag，并使用spatial-temporal align算法进行了建模；
[0131]
3)考虑到长期预测所需的长程依赖性，本发明选择从全局传递的交通流的动态变化中逼近一种稳定的因果关系，而不是从静态路网结构中捕获一种局部的关系。
[0132]
最终，本发明得到的因果关系具有方向性，能够很好地与现实世界中的交通信息传递的源节点和目标节点相对应。在metr_la数据集上的实验表明，本发明的方法能够在3个基于gnn的交通预测模型上在45min和60min上超过原模型的效果。在单个节点的预测水平上，本发明的模型能够在所有尺度上提升对交叉路口、边缘点和偏远点的预测。交叉路口节点处交通信息传递的上下游关系复杂，边缘节点往往仅依赖于上游或下游节点，偏远点则更多依赖于long-range dependence的捕捉，这也说明本发明的方法对于gdti传递捕捉相比于空间图(spatial graph)的有效性。
[0133]
本文所使用的词语“优选的”意指用作实例、示例或例证。本文描述为“优选的”任意方面或设计不必被解释为比其他方面或设计更有利。相反，词语“优选的”的使用旨在以具体方式提出概念。如本技术中所使用的术语“或”旨在意指包含的“或”而非排除的“或”。即，除非另外指定或从上下文中清楚，“x使用a或b”意指自然包括排列的任意一个。即，如果x使用a；x使用b；或x使用a和b二者，则“x使用a或b”在前述任一示例中得到满足。
[0134]
而且，尽管已经相对于一个或实现方式示出并描述了本公开，但是本领域技术人员基于对本说明书和附图的阅读和理解将会想到等价变型和修改。本公开包括所有这样的修改和变型，并且仅由所附权利要求的范围限制。特别地关于由上述组件(例如元件等)执行的各种功能，用于描述这样的组件的术语旨在对应于执行所述组件的指定功能(例如其在功能上是等价的)的任意组件(除非另外指示)，即使在结构上与执行本文所示的本公开的示范性实现方式中的功能的公开结构不等同。此外，尽管本公开的特定特征已经相对于若干实现方式中的仅一个被公开，但是这种特征可以与如可以对给定或特定应用而言是期望和有利的其他实现方式的一个或其他特征组合。而且，就术语“包括”、“具有”、“含有”或其变形被用在具体实施方式或权利要求中而言，这样的术语旨在以与术语“包含”相似的方式包括。
[0135]
本发明实施例中的各功能单元可以集成在一个处理模块中，也可以是各个单元单独物理存在，也可以多个或多个以上单元集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。所述集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，也可以存储在一个计算机可读取存储介质中。上述提到的存储介质可以是只读存储器，磁盘或光盘等。上述的各装置或系统，可以执行相应方法实施例中的存储方法。
[0136]
综上所述，上述实施例为本发明的一种实施方式，但本发明的实施方式并不受所述实施例的限制，其他的任何背离本发明的精神实质与原理下所做的改变、修饰、代替、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。

技术特征：
1.一种基于时空格兰杰因果的交通流预测方法，其特征在于，包括以下步骤：全局动态交通信息gdti表达长时预测下路网的空间依赖关系，具体表现为交通流传递的因果关系tcr，将交通流传递的因果关系tcr建模为时空格兰杰因果关系图；考虑全局动态交通信息gdti在传递时的时空耦合，根据时空对齐算法捕获tcr；所述时空对齐算法考虑tcr中因果关系从原因节点传递到结果节点的时间，根据路网中全局动态交通信息gdti全局传递的起始点的空间距离进行时间序列的对齐，建模tcr传递的时空滞后；使用时空格兰杰因果检验方法从对齐后的时间序列中测试出哪两个节点间有gdti的传递，从而捕获动态交通流下稳定的tcr；将得到的时空格兰杰因果检验图输入到基于gnn的交通预测模型中，同时捕获交通路网的时间依赖性和空间依赖性；所述基于gnn的交通预测模型包括两个模块，一个用于建模时间依赖性，一个使用gnn建模空间依赖性；其中，gnn结构传播和集成有空间依赖性的节点间的交通信息。2.根据权利要求1所述的基于时空格兰杰因果的交通流预测方法，其特征在于，所述时空对齐算法是将源节点的时间序列沿着时间轴向后平移，步长等于源节点和目标节点间的时空滞后，所述时空滞后等于源节点与目标节点间的空间滞后与源节点的平均交通速度的比值；所述时空对齐算法分为两个步骤：根据因果滞后性，计算出tcr从原因节点向结果节点传递所消耗的时间，即两者间的时空滞后；根据因果顺序性，将原因节点的时间序列沿时间轴平移s个时间步，将tcr在原因节点上产生和在结果节点上作用的时间进行对齐，进而保证能够直接从观测到的结果中推断出因果机制。3.根据权利要求1所述的基于时空格兰杰因果的交通流预测方法，其特征在于，所述因果滞后性为：结果发生和原因发生具有一个时间差，在交通路网中表现为原因节点和结果节点之间的时空滞后；所述因果顺序性为：结果总是发生或被观测在原因之后，在交通路网中表现为结果节点接收gdti的时间总是发生在原因节点释放gdti之后。4.根据权利要求1所述的基于时空格兰杰因果的交通流预测方法，其特征在于，节点间的空间滞后是节点之间的空间距离，时空滞后是gdti从原因节点流向结果节点需要消耗的时间，即tcr传递需要的时间。5.根据权利要求1所述的基于时空格兰杰因果的交通流预测方法，其特征在于，格兰杰因果检验方法建立的两个向量自回归模型如下：因果检验方法建立的两个向量自回归模型如下：其中x
t-j
和y
t-j
分别代表时间序列x和y在t-j时刻的交通流数据的数值，α
j
、a
j
和b
j
代表
自回归模型的回归参数，ε
y
和ε
y|x
分别代表两个自回归模型的残差，m代表模型的阶数，即时间滞后值；如果υar(ε
y|x
)＜υar(ε
y
)，则可以判断时间序列x对时间序列y具有统计意义下的格兰杰因果关系，表示为：x granger-causes y根据格兰杰因果分析方法对节点a的时间序列和节点b的时间序列进行granger因果检验时，本发明需要同时输入待检验的时间序列x
a
和x
b
：h
0 hypothesis：x
b does not granger-cause x
a
将两个节点的时间序列输入进行granger因果检验，如果返回的p值低于显著性水平，则拒绝原假设，即得到的结论为：节点b是节点a的格兰杰因。6.根据权利要求1所述的基于时空格兰杰因果的交通流预测方法，其特征在于，将对齐后的两个节点的时间序列输入到格兰杰因果检验模块，即使用时空格兰杰因果检验方法对两个节点间的tcr进行测试，其数学公式表示如下：检验方法对两个节点间的tcr进行测试，其数学公式表示如下：其中，p为时间滞后，s为时空滞后，其中a
t-i
代表时间序列a在t-i时刻的交通流数据的数值，b
t-s-i
代表时间序列b在t-s-i时刻的交通流数据的数值，a
j
和b
j
代表自回归模型的回归参数，代表自回归模型的残差。7.根据权利要求1所述的基于时空格兰杰因果的交通流预测方法，其特征在于，为了防止把长程时空依赖关系过滤掉，不通过距离阈值或拓扑相邻性来得到输入图，而是将节点间的距离建模为时空滞后并使用时空格兰杰因果检验对全局传递下的空间依赖关系进行检验；不直接使用数据集中的成本，所述成本表示不同节点间空间距离，而是计算路网中两个节点间最短距离并得到最小的成本；不同于空间图中节点的依赖关系是无向的，时空格兰杰因果检验图中节点的关系是有方向的，且方向由原因节点指向结果节点。

技术总结
本发明公开了一种基于时空格兰杰因果的交通流预测方法，包括步骤：将交通流传递的因果关系TCR建模为时空格兰杰因果关系图；根据时空对齐算法捕获TCR；使用时空格兰杰因果检验方法从对齐后的时间序列中测试出哪两个节点间有GDTi的传递，从而捕获动态交通流下稳定的TCR；将得到的时空格兰杰因果检验图输入到基于GNN的交通预测模型中，同时捕获交通路网的时间依赖性和空间依赖性。本发明提出时空格兰杰因果来建模TCR，能表达一种全局、动态的空间依赖关系，能捕获GDTi从而提升长程预测效果；使用时空格兰杰因果图的图神经网络交通流预测框架用于提升长时预测效果。预测框架用于提升长时预测效果。预测框架用于提升长时预测效果。


技术研发人员：李海峰 贺丝露 罗琴瑶 时天冬
受保护的技术使用者：中南大学
技术研发日：2023.03.15
技术公布日：2023/6/12