随机OD矩阵预测

1、文章信息

《Stochastic Origin-Destination Matrix Forecasting Using Dual-Stage Graph Convolutional, Recurrent Neural Networks》。这是奥尔堡大学发表在ICDE2020上的一篇文章。

2、摘要

OD矩阵在广泛应用于交通和物流中，以记录一天中不同时间间隔内OD区域对之间的出行成本（例如，出行速度或温室气体排放）。本文将出行成本建模成一个分布，因为当在一对OD区域之间出行时，即使在相同的间隔内，例如由于不同的驾驶方式或交叉路口的不同等待时间，不同的车辆也可能有不同的速度。这产生了随机的OD矩阵。本文考虑一种合理的设置，其中一组车辆行程被用于实例化OD矩阵。由于行程无法在每个时间间隔内覆盖所有OD对，因此产生的OD矩阵可能很稀疏。接着处理从稀疏的、历史的OD矩阵预测预测完整的、将来的OD矩阵的问题。本文提出了一个通用的学习框架：(1)采用矩阵分解和图卷积神经网络，应对数据稀疏性，同时捕获空间关联；(2) 通过图卷积拓展的循环神经网络捕获时空动态。基于两个出租车轨迹数据集的实证研究证明了提出框架的有效性。

3、研究内容

图1  随机OD矩阵预测

随机OD矩阵：如图1 (b)，设置OD之间出行成本为速度的随机分布，M(i, j) 的一个可能的分布为 {([10, 20), 0.5), [20, 30), 0.3), [30, 40), 0.2)}，表示从区域 i 到区域 j 的出行速度概率分布：在 10-20 km/h 的概率系数是0.5，20-30 km/h 的是0.3，30-40 km/h的是0.2。

随机OD矩阵预测：如下公式和图1 (a)，给定 s 个稀疏的历史的OD随机张量，预测未来 h 个完整的OD随机张量：

3.1 挑战

(1) 数据稀疏：即使是庞大的trip数据集也难以覆盖所有时间段的所有区域对，从而产生稀疏的随机OD矩阵；稀疏体现在矩阵中一些元素是全为零的空向量（如图1(b)中的？）

(2) 时空关联：OD矩阵本身并不一定能捕获空间接近性，因为难以保证两个地理上相邻的区域在矩阵中是由相邻的行和列表示的。因此，需要一种单独的机制，能够考虑到在OD矩阵中很好地表示的区域的地理邻近性。此外，还应考虑时间依赖性。

3.2 贡献

(1) 确定了随机OD矩阵的预测问题；

(2) 提出了一个基于矩阵分解和RNN的通用框架来解决该问题；

(3) 通过GCN将空间关联嵌入矩阵分解和RNN的阶段扩展框架；

(4) 使用两个真实的出租车数据集进行实验，证明了框架的有效性。

 

4、方法

本文提出了2种预测框架：基础框架BF (base framework)和高级框架AF (advanced framework)。

4.1 基础框架

AF 包括三个步骤：分解、预测和恢复，在分解和恢复阶段中应对了数据稀疏性，在预测阶段捕获时间依赖性。

图2  基础预测框架

(1) 分解

将稀疏张量M分解为起点区域张量R和目的地区域张量C：

(2) 预测

通过seq2seqGRU模型分别对R和C张量进行预测：

(3) 恢复

将预测后得到的R和C张量点乘进行合并，得到未来时间段完整的M张量：

4.2 高级框架

AF框架该过程没有考虑区域之间的空间关联，但是这种关联很可能会影响出行速度。例如，如果区域x和y在附近，则从区域x和y到同一目的地区域的出行速度可能会相互关联。为了考虑这种空间关联，本文提出了BF，首先使用两个图捕获起点区域之间和目的地区域之间的空间关联；然后利用GCN将捕获的空间相关性用于分解。最后结合GCN和GRU对R和C张量分别进行时空预测。

(1) 捕获空间关联

采用DCRNN中的 proximity matrix 建模空间关联。

(2) 空间分解

图3 (a) 为M张量的分解过程，图3 (b) 以R张量为示例进行预测，C张量的预测过程同理。

图3  空间分解

(3) 时空预测

5、实验

(1) 实验数据

NYC：2013-11-01至2013-12-31纽约市曼哈顿的出租车数据。

CD：2014-08-03至2014-08-30成都市出租车数据。

图4  区域设置

(a) NYC 67个区域. (b) CD 79个区域.

(2) 比较结果

表1  模型构建和超参数选择

表2  预测准确度

1) 在大多数情况下，基于深度学习的方法的性能要优于其他基线算法；

2) 所提出的基本框架BF在大多数情况下比其他方法表现更好，这表明所提出的框架BF，其中包括矩阵分解和基于RNN的预测，对于数据稀疏情况下的OD矩阵预测是有效的；

3) 在所有设置下，提出的高级框架AF都明显优于其他方法，包括BF，这表明通过考虑使用两个GCNN的区域之间的空间关联，学习到的特征将变得更加有意义，从而提高了预测准确性；

4) NYC的结果优于CD，这是因为NYC中的区域（即在曼哈顿地区）比CD中覆盖更大，更多样化的区域更为均匀（即，在曼哈顿内）。反过来，这会使CD中的流量情况变得更加复杂，并且更难以预测；

5) 当改变h时，AF的精度变差，这表明对未来的预测变得更具挑战性；

6) 固定h时，比较了两个表，发现在s = 3时，AF的性能要好于s =6，这似乎表明交通流量的变化更多地取决于短期历史（即s = 3）而不是长期（即s = 6）。

6、总结

这是一项时空OD矩阵预测的工作，与传统的OD矩阵预测不同，矩阵中的元素不是单一的出行成本（例如，平均速度），而是通过成本分布来表示不确定的出行成本。这项工作解决了OD矩阵预测中的数据稀疏性和时空关联问题。城市不规则区域作为GCN中图的顶点，其具体划分方法没有展开，可能是篇幅限制的原因。

引用

Hu J, Yang B, Guo C, et al. Stochastic origin-destination matrix forecasting using dual-stage graph convolutional, recurrent neural networks[C]//2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020: 1417-1428.

先前工作

Hu J, Guo C, Yang B, et al. Stochastic weight completion for road networks using graph convolutional networks[C]//2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 2019: 1274-1285.

Attention

如果你和我一样是轨道交通、道路交通、城市规划相关领域的，可以加微信：Dr_JinleiZhang，备注“进群”，加入交通大数据交流群！希望本文共同进步！