时空网络（CNN+LSTM）

SIGMA

本文主要从《Modeling Spatial-Temporal Dynamics for Traffic Prediction》这篇论文入手，主要介绍时空网络（CNN+LSTM）的原理以及demo实现。

背景

卷积神经网络 （Convolutional Neural Networks，简称 CNN）是一类特殊的人工神经网络，区别于神经网络其他模型（如，BP神经网络，RNN神经网络等），其最主要的特点是卷积运算操作（Convolutional operators）。因此，CNN 在诸多领域应用特别是图像相关任务上表现优异，诸如，图像分类，图像语义分割，图像检索，物体检测等计算机视觉问题。

卷积神经网络适合处理空间数据，一维卷积神经网络也被称为时间延迟神经网络（time delay neural network），可以用来处理一维数据。 CNN的设计思想受到了视觉神经科学的启发，主要由卷积层（convolutional layer) 和池化层（pooling layer）组成。卷积层能够保持图像的 空间连续性 ，能将图像的 局部特征 提取出来。池化层可以采用最大池化（max-pooling）或平均池化（mean-pooling），池化层能降低中间隐含层的维度，减少接下来各层的运算量，并提供了旋转不变性。

CNN提供了视觉数据的分层表示，CNN每一层的权重实际上学到了图像的某些成分，越高层，成分越具体。CNN将原始信号经过逐层的处理，依次识别出部分到整体。比如说人脸识别，CNN先是识别出点、边、颜色、拐角，再是眼角、嘴唇、鼻子，再是整张脸。CNN同一卷积层内权值共享，都为卷积核的权重。

循环神经网络（Recurrent Neural Networks,RNN）, 适合处理时序数据，在语音处理、自然语言处理领域应用广泛，人类的语音和语言天生具有时序性。但是，原始的循环神经网络存在梯度消失或梯度爆炸问题，无论利用过去多长的时间的信息，例如当激活函数是Sigmoid函数时，其导数是个小于1的数，多个小于1的导数连乘就会导致梯度消失问题。LSTM，分层RNN都是针对这个问题的解决方案。本文主要介绍的是 长短时记忆网络（Long short-term Memory,LSTM） .

长短时记忆网络（Long short-term Memory,LSTM） 用LSTM单元代替RNN中的神经元，在输入、输出、忘记过去信息上分别加入了输入门、输出门、遗忘门来控制允许多少信息通过。

论文介绍

时空预测在气候预报和城市规划等方面有着广泛的应用。特别是随着流量相关数据集的不断增长，时空预测在实际应用中越来越受到重视。例如，准确的的士流量预测可以协助的士公司预测分配的士运营路线规划，以应付交通拥挤问题。特别需要注意到的是： 流量预测的关键在于如何对复杂的时空依赖关系进行建模。

在论文中，作者提出了以下特征：

地理位置间的空间依赖是动态的。
时间依赖具有很强的周期性，但由于时间的动态变化，它不是严格周期性的。

在此基础上，文中作者提出了一个新的时空动态网络（Spatial-Temporal Dynamic Network，STDN）。该网络结果主要创新如下：

提出了一种流门机制（flow gating）来学习局部区域中的动态相似性。
设计了一种周期性转移的注意力机制来处理长期的周期依赖和周期性的时间转移。

准备工作

符号定义

将城市划分为 i\times j 个区域，定义网格中的区域集合为 L = \{l_{1} ,l_{2},...,l_{i \times j}\} 。同时，将时间划分为T个不重叠的时间间隔，并将时间间隔定义为 T=\{t_{s1},t_{s2},...,t_{sT} \} 。
使用二元组（a,b）定义时空坐标。其中a代表时间，b代表区域。将任意的一个对象的行程的起点和终点分别定义为： s=(a_{s},b_{s}) , e=(a_{e},b_{e})

特征定义

起/始交通流量。（start/end traffic volume）

在时间间隔t中，对每一个区域的起始交通流量（start traffic volume)为 y_{s,t}^{i} 。结束交通流量（end traffic volume）为 y_{e,t}^{i} 。

2、交通流。（traffic flow）

交通流这个特征主要描述的是区域间的动态相互作用关系。 F_{t}^{i,j} 代表在t时刻，从区域I流动到区域J的交通流量值。

目标定义

交通流量预测（traffic volume Prediction）：在拥有直到时间t的历史数据前提下，交通流量预测问题的目标是在t+1的时间间隔中，预测起始交通流量（start traffic volume）和结束交通流量（end traffic volume）。

数据集

1、交通流量数据。（traffic volume dataset）

纽约市的士出行的交通流量数据，并且将纽约市划分为10*20个区域。

维度：

train_data : 1920,10,20,2

test_data : 960,10,20,2

第一个维度代表时间间隔编号，10*20代表10*20个区域，2代表起始交通量，结束交通量。（start/end Traffic Volume)

2、交通流数据。（traffic flow dataset）

纽约市的10*20个区域中，各个区域间的交通流变化。

维度：

train_data：2，1920，10，20，10，20

test_data : 2,960,10,20,10,20

第一个2维度代表输入流和输出流。

输入流（inflow），即从区域I流入区域J的volume。

输出流（outflow)，即从区域J流入区域I的volume。

第二个维度代表时间间隔编号。

第一个10*20代表区域I，第二个10*20代表区域J

模型结构

局部空间依赖性（local spatial dependency）

文中利用卷积神经网络(CNN)捕捉空间相互作用。因为把整个城市的交通流量（start/end traffic volume）当作一个图像，简单地对整个城市的图像应用CNN可能无法取得最好的表现。并且，在使用卷积层抽取特征时，如果包含了与预测目标区域相关性较弱的部分，会损害特征性能。所以，文中使用局部图像作为卷积层的输入，从而得到局部空间的特征。

局部空间特征定义：对于每一个时间间隔t，文中将目标区域 i 及其周围的邻域看作具有两个通道的图像 Y_{t}^{i}\in R^{s \times s \times 2} 。一个通道为起始交通量的图片。一个通道为结束交通量的图片。目标区域位于图像的中心。

局部空间特征使用局部交通量图像（local traffic volume image）作为输入 Y_{t}^{i,0} ,每一个卷积层的公式定义如下：

其中，F代表激活函数。在对模型堆叠K层卷积后，使用Flatten层将多维特征转换为一维特征。接着使用全连接（fully connected layer）进行降维。最终得到了在时间间隔t中，区域 i 的空间表示（spatial representation）

时间间隔t内，结束交通量的图像（end traffic volume image）

时间间隔t内，起始交通量的图像 (start traffic volume image)

空间动态相似性：流门控机制（Spatial Dynamic Similarity: Flow Gating

Mechanism）

正如前面文中所描述的，局部CNN（local CNN）被用来捕捉空间依赖。CNN通过局部联接和权重分担来处理局部结构的相似性。在局部CNN中，局部空间依赖于历史交通量的相似性。然而，局部空间依赖是一种静态的依赖，不能充分反映目标区域与其他区域之间的关系。一种更直接的表示区域间相互作用的方法是 交通流 。如果两个区域之间存在更多的流动，它们之间的关系就会更强。交通流可以显式地控制区域间的流量传播。

所以，文中作者设计了一种 流控制机制（Flow Gating Mechanism，FGM）， 用于显式捕获层次结构中的动态空间依赖性。

定义 i \times j 矩阵为从区域 i 到区域 j 的流量图 f_{t}^{i,j} ，类似于交通流量图（traffic volume imag）。为了保护流的空间依赖性，在时间间隔t的范围内构造了每个区域的局部空间流图像。每个流动图像的大小也是S×S，并且目标区域位于中心。同时，每一个区域的流图像（flow Image）由两部分组成。分别为输入流（inflow）和输出流（outflow）。在每个时间间隔t，作者认为流动发生在时间t - r + 1到t之间。

基于以上，得到了 S \times S \times 2r 个流图像，然后与“局部空间依赖性”类似，使用cnn捕捉区域间流动的空间交互作用。将 F_{t}^{i,0} 作为在t时间间隔内，第i个区域的第0个卷积层的输入。则第K层网络层的公式为：

并且在每一层，使用 流信息通过流门压缩空间信息 ，显式地捕获区域间的动态相似性。具体而言，每个层由流门调制的特征表示为 G_{t}^{i,k} ，公式表达如下：

其中， G_{t}^{i,k+1} 代表第K+1层的值， F_t^{i,k} 代表在t时间间隔内，第k层区域流动性特征网络的输出。 \sigma 代表激活函数（sigmoid），作者之所以选用sigmoid作为激活函数，是因为sigmaid将 F_t^{i,k} 映射到[0,1]的范围内，类似于LSTM中的遗忘门，通过门机制来捕捉区域间的相互作用关系。