论文笔记《Physical-Virtual Collaboration Modeling for Intra-and Inter-Station Metro Ridership Prediction》

目录

• Abstract

• Introduction & Methodology

• • 物理图 (physical graph)
  • 流量相似性图 (similarity graph)
  • 流量相关性图 (correlation graph)

• Model

• • Graph Convolution Gated Recurrent Unit (GC-GRU)
  • Fully-Connected Gated Recurrent Unit (FC-GRU)
  • Collaborative Gated Recurrent Module (CGRM)
  • Physical-Virtual Collaboration Graph Network (PVCGN)

• Experiments

• • Experiments Settings
  • Comparison with State-of-the-Art Methods
  • Component Analysis

Abstract

本文主要工作有两方面，其一是基于地铁站点的流量预测，其二是在线OD预测。其中很值得学习的是三个图构造方式，也是论文题目中Physical-Virtual的体现，三个图分别是（后文详细说明）：

• 图1-传统的物理拓扑图 a physical graph
• 图2-流量相似性图 a similarity graph
• 图3-流量相关性图 a correlation graph

Introduction & Methodology

在引言部分，除了简单研究现状外，作者还主要介绍两方面内容：其一，针对流量相似性和相关性 的说明；其二，介绍用于构造**流量相似性图（similarity graph）**的方法 Dynamic Time Warping（DTW） ，下文结合文中METHODOLOGY一节中的图构造相关内容一起说明。

物理图 (physical graph)

基于现实站点的连通特性构造拓扑图，并做 row normalization

流量相似性图 (similarity graph)

流量相似性：现实世界的地铁系统中，距离很远或没有直接相连的两点（如B/C），可能因为具有相似功能性而具有类似流量分布特性，可以用虚拟边连接它们。

步骤1： 构造该图使用的是Dynamic Time Warping（DTW [1]），利用 DTW 计算各站点的相似性得分矩阵S(i, j)=\exp \left(-\operatorname{DWT}\left(\boldsymbol{X}^{i}, \boldsymbol{X}^{j}\right)\right)。

[1] D. J. Berndt and J. Clifford, “Using dynamic time warping to find patterns in time series.” in KDD workshop , vol. 10, no. 16. Seattle, WA, 1994, pp. 359–370.

步骤2： 随后利用预先设定的阈值 或 取top-k个站点对建立虚拟边

步骤3： 对相似性得分矩阵 S(i, j) 做 row normalization W_{s}(i, j)=\frac{S(i, j)}{\sum_{k=1}^{N} S(i, k) \cdot L\left(\mathcal{E}_{s}, i, k\right)}，其中 如果点 i/k 相连 L\left(\mathcal{E}_{s}, i, k\right)=1 ，反之 L\left(\mathcal{E}_{s}, i, k\right) \mathcal{E}_{s}=0

流量相关性图 (correlation graph)

流量相关性：现实出行中，可能存在A出发 大部分流向B的情况，该情况视为A/B站点具有高相关性。

步骤1： 计算相关性得分，C(i, j)=\frac{D(i, j)}{\sum_{k=1}^{N} D(i, k)} 其中 D(i, j) 表示站点 i→j 所有乘客数量

步骤2： 建立虚拟边

步骤3： 对相关性得分矩阵 C(i, j) 做 row normalization W_{c}(i, j)=\frac{C(i, j)}{\sum_{k=1}^{N} C(i, k) \cdot L\left(\mathcal{E}_{c}, i, k\right)}

Model

Graph Convolution Gated Recurrent Unit (GC-GRU)

• 步骤1：基于物理-虚拟图(physical-virtual graphs)计算图卷积 输入 I_{t}=\left\{I_{t}^{1}, I_{t}^{2}, \ldots, I_{t}^{N}\right\} ，I_{t}^{i} 可以为 t 时刻 i 站点的乘客数矩阵 X_t^i，或是相应特征矩阵。图卷积系数 均为可训练的参数，\Theta=\left\{\Theta_{l}, \Theta_{p}, \Theta_{s}, \Theta_{c}\right\} 分别表示自连接图的系数、物理拓扑图的系数、流量相似性图的系数和流量相关性图的系数。
  

• 步骤2：放到GRU中捕捉时空关系 \Theta_{r x} 表示 R_t 和 X_t 的图卷积系数， \Theta_{r h} 表示 R_t 和 H_{t-1} 的图卷积系数
  

综上，GC-GRU可以表示为H_{t}=\mathrm{GCGRU}\left(I_{t}, \tilde{H}_{t-1}\right)

Fully-Connected Gated Recurrent Unit (FC-GRU)

刚刚的GC-GRU用于捕捉局部的时空信息，该节中的FC-GRU用于学习全局时空信息

• 步骤1：Embedding 先将 I_t 和上一时间段的隐藏层输出 \tilde{H}_{t-1}，放到全连接层中 I_{t}^{e}=\mathrm{FC}\left(I_{t}\right), \quad H_{t-1}^{e}=\mathrm{FC}\left(\tilde{H}_{t-1}\right)
• 步骤2：放到GRU中捕捉时空关系 GC-GRU可以表示为H_{t}^{g}=\mathrm{FC}\mathrm{GRU}\left(I_{t}^{e}, H_{t-1}^{e}\right)

Collaborative Gated Recurrent Module (CGRM)

CGRM 即为将上述两个GRU模块以全连接形式连接起来，特征连接 \tilde{H}_{t}^{i}=\mathrm{FC}\left(H_{t}^{i} \oplus H_{t}^{g}\right)

Physical-Virtual Collaboration Graph Network (PVCGN)

模型使用 Seq2Seq 框架，中间部分使用上述提到的 CGRM 模块：

Experiments

Experiments Settings

• 数据集：上海地铁 杭州地铁
  

• virtual graphs 的构造：针对上海地铁，为了节省 GCN 计算开销，只选取 10-top 站点对构造虚拟边；针对杭州地铁，因为规模较小，设置 similarity/correlation thresholds 分别为0.1/0.02

Comparison with State-of-the-Art Methods

• 三类传统的时间序列模型：Historical Average、Random Forest、Gradient Boosting Decision Trees
• 三类传统深度学习模型：Multiple Layer Perceptron、Long Short-Term Memory、Gated Recurrent Unit
• 五类近年提出的图网络模型：ASTGCN、STG2Seq、DCRNN、GCRNN、Graph-WaveNet

在实验中也从不同角度进行对比：

• 整个测试集对比
• 测试集中的 rush-hour 时间段对比
• 高客流量站点对比
• 运算效率对比

Component Analysis

• 有无三类图的模型对比测试
• 有无 FC-GRU 层的模型对比测试