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

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

流量相似性图 (similarity graph)

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

流量相似性：现实世界的地铁系统中，距离很远或没有直接相连的两点（如B/C），可能因为具有相似功能性而具有类似流量分布特性，可以用虚拟边连接它们。
步骤1： 构造该图使用的是Dynamic Time Warping（DTW [1]），利用 DTW 计算各站点的相似性得分矩阵 S ( i , j ) = exp ⁡ ( − DWT ⁡ ( X i , X j ) ) S(i, j)=\exp \left(-\operatorname{DWT}\left(\boldsymbol{X}^{i}, \boldsymbol{X}^{j}\right)\right) S(i,j)=exp(−DWT(Xi,Xj))。

[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 ) S(i, j) S(i,j) 做 row normalization W s ( i , j ) = S ( i , j ) ∑ k = 1 N S ( i , k ) ⋅ L ( E s , i , k ) W_{s}(i, j)=\frac{S(i, j)}{\sum_{k=1}^{N} S(i, k) \cdot L\left(\mathcal{E}_{s}, i, k\right)} Ws(i,j)=∑k=1NS(i,k)⋅L(Es,i,k)S(i,j)，其中如果点 i / k i/k i/k 相连 L ( E s , i , k ) = 1 L\left(\mathcal{E}_{s}, i, k\right)=1 L(Es,i,k)=1 ，反之 L ( E s , i , k ) L\left(\mathcal{E}_{s}, i, k\right) L(Es,i,k) E s = 0 \mathcal{E}_{s}=0 Es=0

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

流量相关性图 (correlation graph)

流量相关性：现实出行中，可能存在A出发大部分流向B的情况，该情况视为A/B站点具有高相关性。
步骤1： 计算相关性得分， C ( i , j ) = D ( i , j ) ∑ k = 1 N D ( i , k ) C(i, j)=\frac{D(i, j)}{\sum_{k=1}^{N} D(i, k)} C(i,j)=∑k=1ND(i,k)D(i,j) 其中 D ( i , j ) D(i, j) D(i,j) 表示站点 i → j i→j i→j 所有乘客数量
步骤2： 建立虚拟边
步骤3： 对相关性得分矩阵 C ( i , j ) C(i, j) C(i,j) 做 row normalization W c ( i , j ) = C ( i , j ) ∑ k = 1 N C ( i , k ) ⋅ L ( E c , i , k ) W_{c}(i, j)=\frac{C(i, j)}{\sum_{k=1}^{N} C(i, k) \cdot L\left(\mathcal{E}_{c}, i, k\right)} Wc(i,j)=∑k=1NC(i,k)⋅L(Ec,i,k)C(i,j)

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

Model

Graph Convolution Gated Recurrent Unit (GC-GRU)

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

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

步骤2：放到GRU中捕捉时空关系 Θ r x \Theta_{r x} Θrx 表示 R t R_t Rt 和 X t X_t Xt 的图卷积系数， Θ r h \Theta_{r h} Θrh 表示 R t R_t Rt 和 H t − 1 H_{t-1} Ht−1 的图卷积系数

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

综上，GC-GRU可以表示为 H t = G C G R U ( I t , H ~ t − 1 ) H_{t}=\mathrm{GCGRU}\left(I_{t}, \tilde{H}_{t-1}\right) Ht=GCGRU(It,H~t−1)

Fully-Connected Gated Recurrent Unit (FC-GRU)

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

步骤1：Embedding 先将 I t I_t It 和上一时间段的隐藏层输出 H ~ t − 1 \tilde{H}_{t-1} H~t−1，放到全连接层中 I t e = F C ( I t ) , H t − 1 e = F C ( 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) Ite=FC(It),Ht−1e=FC(H~t−1)
步骤2：放到GRU中捕捉时空关系 GC-GRU可以表示为 H t g = F C G R U ( I t e , H t − 1 e ) H_{t}^{g}=\mathrm{FC}\mathrm{GRU}\left(I_{t}^{e}, H_{t-1}^{e}\right) Htg=FCGRU(Ite,Ht−1e)

Collaborative Gated Recurrent Module (CGRM)

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

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

Physical-Virtual Collaboration Graph Network (PVCGN)

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

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

Experiments

Experiments Settings

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

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

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 层的模型对比测试

论文笔记《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

相关推荐