Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting 阅读笔记

本人正式看的第一篇论文

Posted by LCY on May 1, 2018

论文链接: Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting

简介

时空数据的预测目前来说是有一定难度, 本文通过将GCN和RNN相结合, 对道路上的交通流量问题进行预测, 并取得了比较好的效果.

数据

采用一系列传感器采集道路上的交通流量, 那么这些传感器所在的位置可以看作图论里的一个个节点, 在这里, 图应该的一个有向图. 因为不同方向的车流量在同一时间可能相差很大. route 如图, 虽然road3和road1挨得很近, 但由于方向不同, 车流量的变化并不一致.

有了图数据, 我们还需要有特定节点在某一时间的车流量信息, 也就是这一时间的此节点的特征(feature). 根据输入的一个序列时间的特征, 我们预测下一个时间段的节点特征.

预测目标

目标

根据前一段的历史时间数据, 去预测下一段时间的数据.

算法

扩散卷积层

GCN的详细介绍, 我也在上一篇文章中说过了图编码算法汇总.

当然, 也可以看如何理解 Graph Convolutional Network(GCN)

总之, 这篇论文中采用的是有向图的双向GCN.

Lemma

是图的邻接矩阵, 那么有 作为图的出度的对角矩阵.

对了, 这个邻接矩阵的值并不是简单的两个节点的路径长度, 而是使用高斯核计算后的结果(至于为什么要用高斯核, 大概和谱聚类中的某些东西有关, 不是很懂).

那么状态转移矩阵就是

下式 在多次迭代后, 会趋向一个稳定的分布.

在实际应用中, k常取一个定值, 及k次截断后的结果进行计算.

扩散卷积(Diffusion Convolution)

每个节点都有一个维的特征(feature), 那么所有节点的输入特征就是.

那么我们的卷积定义为:

其中, 是入度的对角阵. 而 , 是卷积核的参数.

由于一般是给稀疏矩阵, 所以在实际的计算中, 针对此进行一些优化.

如果我们让, 那么, 我们有.

因此, 我们采用递归的方法, 可以把上式转换为稀疏矩阵的乘法, 大幅降低时间复杂度.

扩散卷积层

扩散卷积层就很简单了, 在扩散卷积的外头, 套一层最熟悉的非线性变换函数就OK了.

这里的, 可以是ReLU, sigmod等神经网络中常见激活函数.

动态模型(RNN)

我们要进行的是预测, 并产生一串时间序列, 因此, RNN是不可避免的.

在这篇论文里, 作者参考了GRU的结构, 将GRU线性表示的部分, 替换成了上文提到的扩散卷积.

普通GRU

对GRU的理解, 可以参考三次简化一张图: 一招理解LSTM/GRU门控机制

改良版GRU

而在这篇论文中, 作者没有直接把GRU往上面套, 而是把那几个$W\vec{x}$, 转换成了扩散卷积 即:

(第一次见这种骚操作, 真的很惊艳)

seq2seq

我们的目的是要产生一个时间序列, 那么sequence to sequence结构是必不可少的.

sequence to sequence

如图, 输入数据经过一系列的RNN变换, encode得到一个Thought Vector, 再由这个向量, decode得到我们预期的预测序列.

再放一张论文里的示意图

sequence to sequence2

论文中的实验和测试

作者测试了两个数据集, METR-LA和PEMS-BAY, 下面的对比只是针对某一数据集的.

与其他预测方式对比

首先与原有的FC_LSTM算法进行对比, 论文中说比原有方法更加平滑. 其实我自己看不出什么差别来, 不过感觉准确性挺好的.

平滑

高峰时期的对比, 这一张可以看出明显差别, 在高峰期要产生的时候, 明显新的算法下降更快, 但同时, 在斜率较大的情况下, 产生了较大的波动. 不过总体上比FC-LSTM效果好不少.

高峰时期对比

不同参数对比

作者测试了在不同扩散卷积的情况下的结果. 明显的, 在使用扩散卷积后, 误差有了大幅的下降, 而考虑入度的扩散卷积又比单纯的扩散卷积表达效果更好.

扩散卷积有无比较

比较扩散卷积的最大次数, 还有不同的RNN单元数. k&Units数量

链接

作者的源码 GitHub - liyaguang/DCRNN: Implementation of Diffusion

论文链接: Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting