Deep Multi-View Spatial-Temporal Network for Taxi Demand Prediction

论文题目：深度多视图时空网络用于出租车需求预测

摘要

传统的需求预测方法大多依赖于时间序列预测技术，这些技术无法对复杂的非线性时空关系建模。现有的交通预测方法只考虑了空间关系（例如，使用CNN）或时间关系（例如，使用LSTM）。我们提出了一个深度多视图时空网络（DMVST-Net）框架来对时空关系进行建模。

提出的模型包含三个视图：

  • 时间视图（通过LSTM建模具有近时间点的未来需求值之间的相关性）
  • 空间视图（通过本地CNN建模局部空间相关性）
  • 语义视图（在共享相似时间模式的区域之间建模相关性）

介绍

  • 出租车需求预测问题：如何通过使用历史出租车请求数据来预测未来时间戳中某个地区的出租车请求数量。

  • 本文利用联合模型捕获CNN和LSTM的功能，该模型捕获了时空的复杂非线性关系。 但是，我们不能简单地将CNN和LSTM应用于需求预测问题。

  • 将相关性较弱的区域包括在内以预测目标区域实际上会损害性能。 为了解决这个问题，我们提出了一种新颖的局部CNN方法，该方法仅考虑空间附近的区域。

  • 这种本地的CNN方法是受《第一地理学》的启发：“近处的事物比远处的事物更相关”，并且根据真实数据的观察结果也证明了需求模式与空间紧密区域的相关性更高。

  • 尽管localCNN方法过滤的边远地区相关性较弱，但这未能考虑到两个位置在空间上可能相距遥远但需求模式相似（即在语义空间上）的情况。

  • 建议使用区域图来捕获这种潜在的语义，其中边缘代表需求的相似性 之后，通过图嵌入方法将区域编码为向量，并将这些向量用作模型中的上下文特征。最后，使用完全连接的神经网络组件进行预测。

  • 通过滴滴出行的大规模真实世界滑行需求数据进行了验证。 该数据集包含两个月内通过中国广州市的滴滴服务的出租车需求请求，平均每天约300,000个请求。

本文的贡献：

  • 提出了一个统一的多视图模型，该模型共同考虑了空间，时间和语义关系。
  • 提出了一个local CNN模型，该模型捕获相对于其邻居的区域的局部特征。
  • 基于需求模式的相似性构建了一个区域图，以便对相关但空间上遥远的区域进行建模。通过图嵌入学习区域的潜在语义。
  • 对滴滴出行的大型出租车请求数据集进行了广泛的实验。 结果表明，我们的方法始终优于竞争基准。

前提条件

  • 不重叠的位置集 $L = {l_1,l_2,…,l_i,…,l_N}$作为城市的矩形分区【也可以使用更复杂的分区方式，例如通过路网划分空间或六角形分区。】
  • 时间间隔集 $ I = { I_0,I_1,…,I_t,…,I_T}$

Taxi request:
出租车请求$o$定义为元组$(o.t，o.l，o.u)$
其中

  • $o.t$是时间戳
  • $o.l$代表位置
  • $o.u$是用户标识号。请求者标识用于过滤重复的和垃圾邮件的请求。

Demand:
定义为每个时间点在一个位置的出租车请求的数量,即$y_t^i = | {o:o_t \in I_t \bigwedge o_l \in l_i} |$

  • 其中$|·|$表示集合的基数
  • 使用$I_t$代表它的时间间隔t的索引
  • $l_i$代表位置$i$处的的位置索引

Demand prediction problem:

  • 目的：给定直到时间间隔t的数据来预测在时间间隔$t +1$处的需求。
  • 除了历史需求数据之外，我们还可以合并上下文特征，例如时间特征，空间特征，气象特征。
  • 将位置$i$和时间点$t$的那些上下文特征表示为向量$e_t^i \in \mathbb R^r$
    • 其中$r$是特征的数量。

最终目标是预测：

$$
y_{t+1}^i = F( \displaystyle y_{t-h,…,t}^L, \displaystyle \varepsilon_{t-h,…,t}^L)
$$

  • $i \in L$
  • $y_{t-h,…,t}^L$ 历史需求
  • $\varepsilon_{t-h,…,t}^L$ 表示在从$t_h$到$t$的时间间隔内，所有位置$L$的上下文特征，其中$t_h$表示开始时间间隔。
  • 在所有区域和直到$t_h$的先前时间间隔上定义了预测函数$F(·)$，以捕获它们之间的复杂时空相互作用。

模型

Deep Multi-View Spatial-Temporal Network(DMVST-Net)

image.png

  • 空间组件使用本地CNN捕获附近区域之间的空间依赖性。 本地CNN包含几个卷积层。 最后使用一个完全连接的层来获得低尺寸的表示。
  • 时态视图采用LSTM模型，该模型从空间视图中获取表示，并在相应的时间将它们与上下文特征连接起来。
  • 语义视图首先构建区域的加权图（权重代表功能相似性）。 节点被编码为向量。 最后使用完全连接的层进行联合训练。 最后，将完全连接的神经网络用于预测。

Spatial View : Local CNN

  • 存在的问题：将相关性较弱的区域包括在内以预测目标区域实际上会损害性能。

  • 解决方案：提出了一种local CNN方法，该方法仅考虑空间上附近的区域。

    • 受到地理第一法则的启发（Tobler 1970）的：“近处的事物比远处的事物更相关”

  • 在每个时间间隔$t$，将一个位置$i$及其周围的邻域视为具有一个需求值通道的一个$S×S$图像

    • $i$位于图像的中心
    • 大小$S$控制着空间的粒度
    • 在城市边界使用零填充。

  • 对于每个位置$i$和时间间隔$t$，我们都有一个图像作为张量（具有一个通道）$Y_t^i \in \mathbb R^{S×S×1}$

  • local CNN将$Y_t^i$作为输入$Y_t^{i,0}$，并将其馈入K个卷积层。
    每层$k$的变换定义如下：
    $$
    Y_t^{i,k} = f(Y_t^{i,k-1} * W^k_t + b^k_t)
    $$

  • $*$表示卷积操作

  • $f(·) $一个激活函数

  • 使用整流器函数作为激活，即$f(z)= max(0,z)$

  • $W^k_t$和$b^k_t$是第$k$个卷积层中的两个参数集

  • 参数$W^{1,…,K}_t$ 和 $b^{1,…,K}_t$在所有区域$i \in L$上共享，以使计算易于处理。

  • 在K个卷积层之后，我们使用flatten层将区域i和时间间隔t的输出$Y_t^{i,K} \in \mathbb{R}^{S \times S \times \lambda}$转换为特征向量$s_t^i \in \mathbb R^{S^2\lambda}$

  • 最后，我们使用一个完全连接的层来减小空间表示的尺寸$s_t^i$，其定义为：
    $$
    \hat{s}_t^i = f(W^{fc}_t s_t^i + b^{fc}_t)
    $$

  • $W^{fc}_t$ 和 $b^{fc}_t$是在时间间隔t的两个学习参数

  • 最后，对于每个时间间隔t，我们得到$\hat{s}_t^i \in \mathbb R^d $作为区域$i$的表示。

Temporal View : LSTM

  • 时间视图对需求时间序列中的顺序关系进行建模。本文建议使用长短期记忆（LSTM）网络作为时间视图组件。

  • LSTM（1997）是一种神经网络结构，它通过递归将过渡函数应用于输入的隐藏状态向量，提供了一种很好的方法来建模顺序依赖关系。

  • 有人提出解决经典递归神经网络（RNN）在长序列训练中梯度爆炸或消失的问题（Hochreiter et al。2001）。

  • LSTM通过在时间间隔$t$中维护一个存储单元$c_t$来稳定地学习顺序相关性，这可以看作是先前顺序信息的累积。

  • 在每个时间间隔中，LSTM在此工作中取一个输入$g^i_t$，$h_{t-1}$和$c_{t-1}$，然后在激活输入门$i^i_t$时，所有信息都累积到存储单元中。

  • LSTM具有遗忘门功能。如果忘记门被激活，则网络可以忘记先前的存储单元$c_{t-1}^i$。 同样，输出门$o_t^i$输出控制存储单元的输出。

本文LSTM结构的公式如下：
image.png

  • $◦$表示Hadamard积(哈达玛积)
  • $tanh$是双曲正切函数。 这两个功能都是基于元素的。
  • $W_a,U_a,b_a（a \in {i,f,o,g}）$都是可学习的参数。
  • LSTM中时间间隔的数量为$h$
  • $t$时间间隔之后LSTM的区域$i$的输出为$h^i_t$

时间分量从空间视图中获取表示并将它们与上下文特征连接起来。
$$
g_t^i = \hat{s}_t^i \oplus e_t^i
$$

  • $\oplus$表示串联运算符
  • $g_t^i \in \mathbb R_{r+d}$

Semantic View : Structural Embedding

  • 直觉上，共享相似功能的位置可能具有相似的需求模式，
  • 类似区域不一定在空间上紧密。
  • 本文构造了一个表示区域之间功能（语义）相似性的位置图。

将位置的语义图定义为$G =(V，E，D)$

  • 位置$L$的集合是节点$V = L$
  • $E \in V×V$是边集
  • $D$是所有边的相似性集合。

使用动态时间规整（DTW）来测量节点（位置）$i$和节点（位置）$j$之间的相似度$w_{ij}$。
$$
w_{ij} = exp(- \alpha DTW(i,j))
$$

  • $\alpha$是控制距离衰减率的参数（在本文中，$\alpha = 1$）
  • $DTW(i,j)$是两个位置的需求模式之间的动态时间规整距离

使用每周平均需求时间序列作为需求模式。根据实验中的训练数据计算平均值。
因为可以访问每两个区域则该图已完全连接

为了将每个节点编码为低维向量并保持结构信息，我们在图上应用了图嵌入方法。 [嵌入是压缩的表示]

  • 图嵌入（Graph Embedding，也叫Network Embedding）是一种将图数据（通常为高维稠密的矩阵）映射为低微稠密向量的过程，能够很好地解决图数据难以高效输入机器学习算法的问题。
  • 对于每个节点$i$（位置），嵌入方法输出嵌入的特征向量$m^i$。
  • 此外，为了将嵌入式$m^i$与我们的整个网络体系结构共同训练，我们将特征向量$m^i$馈送到完全连接的层

FC层定义为：
$$
\hat{m}^i = f(W_{fe} m^i + b_{fe})
$$

  • $W_{fe}$ 和$b_{fe}$ 是学习参数
  • 使用LINE用于生成嵌入

注：大规模信息网络(large-scale information Network)无论在存取性，使用性上比起普通的信息处理方式更加复杂，更加多变，例如航空公司网络，出版物网络，社会和通信网络以及万维网。LINE模型致力于将这种大型的信息网络嵌入到低维的向量空间中，且该模型适用于任何类型(有向、无向亦或是有权重)的信息网络。

Prediction Component

本文的目标是在给定数据直到$t$的情况下预测$t + 1$处的需求。
本文通过将$\hat{m}^i$与LSTM的输出$h_t^i$连接起来将三个视图结合在一起：
$$
q_t^i = h_t^i \oplus \hat{m}^i
$$
LSTM $h_t^i$的输出同时包含时间和空间视图的影响。
然后，本文将$q_t^i$馈入全连接网络，以获得每个区域的最终预测值$\hat{y}{t+1}^i$
定义最终的预测函数为：
$$
\hat{y}{t+1}^i = \sigma(W_{ff} q_t^i + b_{ff})
$$

  • $W_{ff}$和$b_{ff}$是学习参数
  • $\sigma(x)$ 是S形函数并定义为$\sigma(x) = \frac{1}{1+e^{-x}}$
  • 模型输出范围在[0,1]（需求之已标准化）
  • 将该预测反规范化以获得实际需求值。

Loss function

本部分提供有关用于联合训练我们提出的模型的损失函数的详细信息。

我们使用的损失函数定义为：
image.png

  • θ是DMVST-Net中所有可学习的参数，
  • γ是超参数。

损失函数由两部分组成：

  • 均方损失

  • 均值绝对百分比损失的平方

  • 实际上，均方误差与大值的预测更相关。 为了避免训练以大样本为主导，我们还使平均绝对百分比损失最小化。

  • 在实验中，所有比较的回归方法都使用方程中定义的相同损失函数进行公平比较。

算法1中概述了训练管道。
image.png

  • 使用Adam（Kingma and Ba 2014）进行优化。
  • 使用Tensor fl ow和Keras（Chollet等，2015）来实现我们提出的模型。

实验

数据集描述：

  • 使用didi出行数据
  • 从02/01/2017 到 03/26/2017 ，广州

评价指标：

  • MAPE
  • RMSE

基线：

  • HA
  • ARIMA
  • LR
  • MLP
  • XGBoost
  • ST-ResNet

不同视图组件的效果:

  • Temporal view
  • Temporal view + Semantic view
  • Temporal view+Spatial (Neighbors) view
  • Temporal view + Spatial (LCNN) view
  • DMVST-Net

两种比较方式：

  • 与基线（最新方法）比较
  • 与自己提出的方法的变体进行比较

总结

  • 将空间，时间和语义视图进行了整合，并以本地CNN为模型 ，LSTM和语义图嵌入。
  • 在大型出租车需求数据集上评估了我们的模型。 实验结果表明，我们提出的方法明显优于几种竞争方法。
  • 由于在本文中对语义信息进行了隐式建模，我们计划在未来的工作中纳入更多的显式信息（例如POI信息）。