TKDE | 图神经网络的停车位预测

2021 年 9 月 15 日 图与推荐

城市可用停车位预测对于帮助司机找到停车位、帮助政府进行城市规划、缓解城市交通拥堵具有重要意义。

在本项工作中，我们基于停车场周边的环境上下文数据（POI分布，人流量等）和部分停车场实时的可用停车位数据来进行全市范围的可用停车位的预测。在这项工作中我们主要解决了以下挑战：（1）空间关联性。停车场的可用性不仅受到附近停车场占用情况的影响，而且还可能与远处的停车场相关。第一个挑战就是如何对不规则且非欧几里得的停车场之间的空间关联性进行建模（2）时间关联性。停车场未来的可用停车位与它过去的时间段的可用停车位相关，包括短期和长期的时间依赖性。而且，停车场之间的空间关联性可能随时间不断变化。如何对停车场的长短期动态时间关联性进行建模是第二个挑战。（3）可用停车位数据的稀疏性。只有一小部分的停车场拥有实时传感器，能够检测当前停车场的可用停车位数量。所以第三个挑战就是如何利用稀疏的实时可用停车位数据。

基于以上挑战，我们提出了半监督层次循环图神经网络SHARE-X。我们提出了一种层次图卷积模块建模停车场之间的空间关联性。在层次图卷积模块中，我们首先提出一种上下文图卷积模块建模停车场之间的动态局部相关性，其次我们设计了一种多分辨率软聚类图卷积模块用于建模停车场之间的全局空间相关性。之后为了建模短期和长期时间关联性，我们提出层次注意力循环网络。最后我们采用可用停车位估计模块从时间和空间域分别对未安装传感器的停车场的可用停车位数量的分布进行估计，并通过一种基于熵的机制对两种估计值进行融合。我们在两个真实数据集上进行了实验，我们的模型超越了所有基线方法。

本文工作由中国科学技术大学、百度商务智能实验室（BIL）与罗格斯大学联合完成，相关成果已被中国计算机学会推荐A类国际期刊IEEE TKDE录用，论文信息如下：

论文标题：

Semi-Supervised City-Wide Parking Availability Prediction via Hierarchical Recurrent Graph Neural Network

期刊名称：

IEEE Transactions on Knowledge and Data Engineering

论文作者：

Weijia Zhang, Hao Liu, Yanchi Liu, Jingbo Zhou, Tong Xu, Hui Xiong

1. 问题定义

考虑停车场的集合 $P=P_{l} \cup P_{u}=\left\{p_{1}, p_{2}, \ldots, p_{N}\right\}$ ，其中是总停车场数目， $P_{l}$ 和 $P_{u}$ 分别代表有和没有实时传感器的停车场集合。定义 $\mathrm{X}^{c, t}=\left[\mathrm{x}_{1}^{c, t}, \mathrm{x}_{2}^{c, t}, \ldots, \mathrm{x}_{N}^{c, t}\right] \in \mathcal{R}^{N \times M}$ 表示 $P$ 中所有停车场在 $t$ 时刻的 $M$ 维的上下文特征向量（比如POI分布和人流量）。接下来，我们先介绍可用停车位PA的定义，并且基于此定义PA预测问题。

定义1：可用停车位（PA）。给定一个停车场 $p_{i} \in P$ , 其 $t$ 时刻的可用停车位 $y_{i}^{t}$ ，表示在 $t$ 时 $p_{i}$ 的剩余空闲停车位数。

我们使用 $\mathbf{y}_{P_{l}}^{t}=\left[y_{1}^{t}, y_{2}^{t}, \ldots, y_{\left|P_{l}\right|}^{t}\right]$ 来表示在 $t$ 时刻 $P_{l}$ 的PAs。本文利用所有停车场 $P$ 的上下文数据和部分可观测的停车场 $P_{l}$ 的实时可用停车位数据，对全市范围所有停车场 $p_{i} \in P$ 的PAs进行了预测。

问题1：可用停车位预测。给定时间窗口 $T$ , 所有停车场的上下文特征 $\boldsymbol{X}^{c}=\left(\mathrm{X}^{c, t-T+1}, \mathrm{X}^{c, t-T+2}, \ldots, \mathrm{X}^{c, t}\right)$ 和部分可观测的实时可用停车位 $\boldsymbol{Y}_{P_{l}}=\left(\mathbf{y}_{P_{l}}^{t-T+1}, \mathbf{y}_{P_{t}}^{t-T+2}, \ldots, \mathbf{y}_{P_{l}}^{t}\right)$ ，我们的任务是去预测所有的 $p_{i} \in P$ 在接下来时间 $\tau$ 的PAs

其中 $\hat{\mathbf{y}}^{t+1}=\hat{\mathbf{y}}_{P_{l}}^{t+1} \cup \hat{\mathbf{y}}_{P_{u}}^{t+1}$ ， $f(\cdot)$ 是我们要学习的映射函数。

2. 模型概述

SHARE-X的框架如图1所示，其中输入是所有停车场 $P$ 的上下文特征和部分可观测的停车场 $P_{l}$ 的实时PAs，输出则是所有停车场在接下来的 $\tau$ 时间步的PAs预测值。整个框架主要由三个主要模块组成。第一，层次图卷积模块对停车场间的空间自相关性进行建模，包括上下文图卷积（CxtConv）模块和多分辨率软分类图卷积（MrscConv）模块，分别捕捉近距离和远距离的停车场之间的空间关联性。第二，我们设计了层次注意力循环网络（HARN）对每个停车场的长短期的时间依赖进行建模。第三，PA估计模块从时间（通过GRU）和空间上（通过PropConv）估计了 $P_{u}$ 中缺失的PAs分布，并通过一种基于熵的机制对两种估计值进行融合。

图1 SHARE-X的总框架

3. 层次图卷积

3.1上下文图卷积

在本节中，我们假设所有的图卷积操作都是在时间上执行，因此我们省略了符号的时间上标以方便表示。

在空间领域，邻近的停车场之间往往具有很强的相关性，并且常常相互影响。比如，当一个音乐厅正在举行一个音乐会，那么这个音乐厅及其附近的停车场的可用停车位往往会很少，并且停车的需求往往从该音乐厅附近逐渐向远处扩散。为了建模这种局部的空间相关性，我们对局部的停车场的空间联系建模成图 $G=(V, E, A)$ ，其中 $V=P$ 是停车场的集合， $E$ 是边的集合表示停车场之间连接性, $A$ 表示 $G$ 的邻接矩阵。具体来说，我们定义 $e_{i j} \in E$ 为:

其中 $\operatorname{dist}(\cdot)$ 是停车场之间的距离， $\epsilon$ 是距离阈值。

我们通过Attention机制，来计算不同停车场之间的权重系数

$W_{a}$ 则是被所有边共享的带权矩阵。 $\operatorname{Attn}_{c x t}(\cdot)$ 是共享的注意力函数。 $p_{i}, p_{j}$ 之间的邻近分数被定义为：

为避免二次的时间复杂度，我们在计算邻近分数时只关注与 $p_{i}$ 邻近的停车场 $p_{j} \in \mathcal{N}_{i}$ ，其中 $\mathcal{N}_{i}$ 是G中与 $p_{i}$ 邻近相连的停车场。需要注意的是，不同时间停车场之间的影响系数会发生变化，因此我们在不同时间动态学习不同的邻近分数。

一旦我们得到 $\alpha_{i j} \in A$ , 我们就可以利用上下文图卷积进行聚合并转换它的附近停车场表征，来更新当前停车场的表征：

我们可以堆叠L层相同的上下文图卷积，以捕获L-hop的局部依赖。

3.2多分辨率软聚类图卷积

为弥补局部空间建模的不足，我们对远距离的停车场间进行建模。对远距离的空间关系进行建模的动机是，相距很远但在相似功能区的停车场可能会有相似的PA，比如：商务区的停车场在办公时间可能有较低的PA，而住宅区此时可能有较高的PA。

因此，我们提出了多分辨率软聚类图卷积（MrscConv）来捕捉全局的停车场之间的相关性，如图2所示。

图2 多分辨率软聚类图卷积

3.2.1软聚类图卷积

首先介绍基础的软聚类图卷积，软聚合图卷积（SCConv）定义 $K$ 为潜在节点的数量， $N$ 为停车场的数目， $\mathbf{S} \in \mathcal{R}^{N \times M}$ 表示软分配矩阵， $\mathbf{S}_{i, j} \in \mathbf{S}$ 表示 $p_{i}$ 属于 $j \text { -th }$ 潜在节点的概率。

定义 $x_{i}^{c p}$ 为CxtConv 表征 $x_{i}^{c^{\prime}}$ 和估计的PA分布 $x_{i}^{p}$ （第6.3节介绍）的结合。则 $S$ 的每一行可以按如下计算：

一旦软分配矩阵 $S$ 得到了，我们就可以通过 $S^{T}$ 来计算每一个潜在节点 $\mathrm{x}_{i}^{s}$ 的表征：

给定每个潜在节点的表征，类似于CxtConv，我们也使用图卷积操作去捕捉潜在节点之间的依赖关系，生成新的潜在节点表征：

其中 $W_{l}$ 是可学习参数， $\sigma$ 是非线性激活函数， $\alpha_{i j}^{s}$ 是两个潜在节点之间的邻近分数。在这里，不同于CxtConv中引入额外的注意力函数，我们通过如下式子得到邻近分数：

当 $p_{m}$ 和 $p_{n}$ 连通时， $a_{m n}=1$ 。通过图卷积习得的潜在节点表征，我们可以为每一个停车场生成对应的表征：

3.2.2多分辨率泛化

我们扩展SCConv到多重分辨率，MrscConv通过对远距离的停车场的潜在层次关系建模来提高预测能力。

假设有层SCConv，考虑第 $f-1$ 和第 $f$ 层SCConv, $\mathrm{x}_{i}^{s^{\prime},(f-1)}$ 表示 $f-1$ 层的SCConv中的潜在节点的表征， $\mathbf{S}^{f} \in \mathcal{R}^{K_{f-1} \times K_{f}}$ 表示对应的软分配矩阵，其中 $K_{f-1},K_{f}$ 分别表示第 $f-1$ 和 $f$ 层的节点个数。我们可以按照4.2.1中的公式得到第 $f$ 层的软分配矩阵 $\mathbf{S}^{f}$ ，潜在表征 $\mathrm{x}_{i}^{s^{\prime}, f}$ 以及邻近分数 $\alpha_{i j}^{s, f}$ 。

在得到不同分辨率下的潜在节点表征后，一个需解决的任务是如何为每一个停车场生成一个统一的软聚类表征。为了达到这目的，对于第层 SCConv ，我们进一步定义软转移矩阵：

其中 $\mathbf{T}^{f} \in \mathcal{R}^{N \times K_{f}}$ ， $S^{i}$ 是第 $i$ 层的软分配矩阵 $(i \leq f)$ . $\mathbf{T}_{i, j}^{f} \in \mathbf{T}^{f}$ 可以被看做是停车场 $p_{i}$ 映射到第 $f$ 层SCConv中的第 $j$ 个潜在节点的概率。我们可以得到第 $f$ 层的潜在节点表示下的停车场的表征:

最后我们将不同分辨率的软聚类表征拼接，得到最终的软聚类表征：

4. 层次注意力循环神经网络

这部分内容我们设计了HARN同时对长短期的时间依赖进行建模，HARN的结构如图4所示：

图3 HARN的整体结构

4.1 基础循环神经网络

我们使用GRU作为HARN的基础模块，定义 $x_{i}^{t}$ 作为每个停车场在时间 $t$ 上整合的表示（ $x_{i}^{t}$ 将在第6.3节中讨论），给定 $t$ 时间之前的 $T$ 个时间步的停车场 $p_{i}$ 的表示序列 $\mathrm{x}_{i}^{t-T+1}, \mathrm{x}_{i}^{t-T+2}, \ldots, \mathrm{x}_{i}^{t}$ ，我们将在 $t-1$ 和 $t$ 时刻 $p_{i}$ 的隐状态表示为 $\mathrm{h}_{i}^{t-1}$ 和 $\mathrm{h}_{i}^{t}$ ，则有：

其中 $z_{i}^{t}$ 和 $\tilde{\mathrm{h}}_{i}^{t}$ 定义为：

4.2 层次注意力循环神经网络

然而单纯的使用GRU会出现两个问题：1）忽视了过去时间步的重要性差异；2）GRU在建模长期依赖时面临梯度消失的问题。为了解决第一个问题，我们引入了短时的注意力操作去量化应给予前 $T_{s}$ 个时间步每个时间步的注意力。

其中 $T_{s}$ 是短期时间步长， $\text { Attn }_{\text {short}}(\cdot)$ 是共享的短期注意力函数。因此我们可以得到 $p_{i}$ 的短期表征：

同时为了解决长期依赖建模中梯度消失的问题，我们考虑利用PAs的日周期性。具体来说，如果要预测接下来 $\tau$ 时间步的PAs，HARN只需要使用前 $D$ 天相同的时间步作为输入。此外，为了缓解时间偏移的问题（比如今天和昨天出现最低PA的时间可能会有所差别），HARN还需要多利用 $\tau$ 时间步的前后 $s$ 个时间步作为输入。也就是说，如果令 $s=2$ ，预测今天9:00-9:15的PAs，那么就需要前 $D$ 天的8:30-9:45的PAs作为输入。因此，对于第 $d$ 天，我们有： $\left(\mathrm{h}_{i}^{t^{d}-s+1}, \mathrm{h}_{i}^{t^{d}-s+2}, \ldots, \mathrm{h}_{i}^{t^{d}+s+\tau}\right)$ ，其中 $t^{d}$ 代表第 $d$ 天的第 $t$ 个时间步。由短期注意力操作可得：

然后我们通过 $G R U_{\text {long}}$ 建模前 $D$ 天的时间依赖：

再通过长期注意力操作，我们可以得到 $p_{i}$ 的长期表征：

其中 $\text { Attn }_{long}$ 是长期时间依赖模型的注意力函数。

最后，我们通过连接操作，得到最终表征：

$h_{i}^{o}$ 将用于预测 $p_{i}$ 接下来 $\tau$ 时间步的PAs:

5. 可用停车位估计

为了利用部分可观测的PAs，我们从空间和时间两个领域估计缺失的PAs。为了保存更多的信息量，我们不直接估计标量 $\operatorname{PA} \hat{y}_{i}$ ，而是学习 $\hat{y}_{i}$ 的分布 $x_{i}^{p}$ 。因此给定一个 $\operatorname{PA}{y}_{i}$ ，我们离散化其分布为 $p$ 维的独热编码 $\mathrm{y}_{i}^{p} \in \mathcal{R}^{p}$ 。PA估计模块的目标就是去缩小 $\mathrm{y}_{i}^{p}$ （实际PA）和 $\mathrm{x}_{i}^{p}$ （估计PA）的差别。

5.1 基于空间的PA估计

与CxtConv类似，对于每个 $p_{i} \in P_{u}$ ，PropConv操作可以定义为：

其中 $\mathrm{x}_{i}^{\mathrm{sp}}$ 是获得的PA分布， $a_{ij}$ 是 $p_{i}$ 和 $p_{j}$ 之间的邻近分数。与CxtConv不同，估计的PA只从拥有实时可观测PA的停车场 $P_{l}$ 的PA中聚合。同时，为了更充分的利用可观测的PAs，我们放宽了CxtConv中的连接限制：

5.2 基于时间的PA估计

我们再次使用GRU模块的隐藏状态从时间领域来估计PA分布：

5.3 PA估计融合

我们并不直接平均 $\mathrm{x}_{i}^{\mathrm{sp}}$ 和 $\mathrm{x}_{i}^{\mathrm{tp}}$ ，而是提出了一种基于熵的机制来融合这两个分布，也就是说，对于不确定性大的分布我们给到更小的权重，反之给予更大的权重。给定PA分布 $x_{i}$ ，其熵为：

我们按如下方式融合：

其中 $\mathbf{Z}_{i}=\exp \left(-H\left(\mathbf{x}_{i}^{s p}\right)\right)+\exp \left(-H\left(\mathbf{x}_{i}^{t p}\right)\right)$ 。得到的 $x_{i}^{p}$ 可与CxtConv的输出结合，即 $\mathrm{x}_{i}^{c p}=\left[\mathrm{x}_{i}^{c^{\prime}} \oplus \mathrm{x}_{i}^{p}\right]$ ，之后输入MrscConv模块学习潜在节点的表示，以及用于结合CxtConv和MrscConv的输出 $\mathrm{x}_{i}^{t}=\left[\mathrm{x}_{i}^{c^{\prime}, t} \oplus \mathrm{x}_{i}^{s c, t} \oplus \mathrm{x}_{i}^{p, t}\right]$ ，并用 $\mathrm{x}_{i}^{t}$ 作为HRAN的输入来学习 $p_{i}$ 的最终表达，参考图1。

6. 模型训练

因为只有部分停车场有可观测的PAs，按照图的半监督学习范式，SHARE-X旨在最小化 $P_{l}$ 中预测的PAs和可观测PAs的MSE:

并且，我们增加两个交叉熵(CE)误差项来增强PA估计的准确性：

最后，同时考虑MSE和CE误差，SHARE-X算法最小化以下联合损失：

其中 $\beta$ 为超参数。

7. 实验

7.1 数据集描述

实验的数据集来自北京和深圳两个城市的真实停车场数据。

7.2 总体实验结果

实验结果从各个指标上都打败了所有baseline，验证了模型的有效性，如表2所示：

7.3 消融实验

我们进行了消融实验。分别验证了空间，时间以及PA估计模块的有效性，如图4所示：

图4 消融实验

7.4 参数敏感性

此外我们针对模型中的一些可调参数做了充分的参数敏感性实验，如图5所示：

图5 参数敏感性实验

7.5 其他实验

除此之外我们还设计实验，从不同时间和空间上分别验证了模型的效果；以及对我们模型以及基线模型的运行效率进行了对比和分析。

8. 总结

在本文中，我们提出了SHARE-X，一个基于环境上下文数据和部分可观测的实时停车可用性数据的全市停车可用性预测框架。我们首先提出了一种层次图卷积模块来捕获局部和全局空间依赖关系。然后，采用分层注意力递归网络捕获每个停车场的短期以及长期时间依赖性。此外，我们还提出了一种针对无实时停车可用性信息的停车场的停车可用性近似模块。在两个真实世界数据集上的实验结果表明，SHARE-X在全市停车可用性预测方面的性能显著优于8个先进的基线模型。