Origin-Destination Matrix Prediction via Graph Convolution a New Perspective of Passenger Demand Modeling

论文题目：基于图卷积的起点-终点矩阵预测：旅客需求建模的新视角

参考笔记：https://cloud.tencent.com/developer/article/1619218

摘要

  • 为了获得乘客的出行模式，打车平台需要提前预测一个地区到另一个地区的乘客需求数量，即OD矩阵预测(ODMP)问题。OD矩阵预测比普通需求预测更具挑战性。
  • 除了要预测一个地区的需求产生量，还需要预测需求的目的地。此外，数据稀疏性是一个严重的问题。
  • 因此本文提出了一种基于网格嵌入的单馈多任务学习模型(GEML)。该模型主要包含两个部分，分别提取时间信息和空间信息。
  • 网格嵌入部分是为了对乘客的空间移动模式和不同区域的相邻关系进行建模，其预加权聚合器的目的是感知数据的稀疏性和范围；
  • 多任务学习部分则侧重于时间属性建模和捕获ODMP问题目标。两个数据集UCAR和Didi的结果表明GEML方法优于基准模型。

介绍

除了预测某一区域内可能的乘客需求数量外，了解每次出行的来源地和目的地的乘客需求也很重要。因为不同时段两个区域之间的需求量不仅承载着乘客需求的强度，而且有利于挖掘有用的出行模式。

本文从一个新的角度研究了乘客需求模型，即OD矩阵预测（ODMP）

Origin-Destination Matrix Prediction（ODMP）

OD矩阵包含两个方面的信息:

  1. 不同的OD组合
  2. 每个OD对的旅客需求数量。

ODMP的目标：预测在给定时间段内从一个地理区域到另一个地理区域的叫车订单数量。

为了同时兼顾出行产生量和目的地，时空特性以及数据稀疏性，本文提出了一种基于网格嵌入的单馈多任务学习模型(GEML)，以基于图对出行模式进行建模。具体来说，我们用图表示与地理区域相关的乘客订单记录，其中节点表示地理区域(以网格形式定义)，节点之间的边表示乘客需求，边权重表示订单数量。利用改进后的网格，可以构造出给定时间间隔内的OD矩阵。如图1所示，将区域划分为16个网格，订单记录汇总在相应的OD矩阵中。
image.png

本文模型的灵感来自于最近大火的GCNs，然而如果我们直接将已有的GCNs应用到OD矩阵所生成的图上，由于数据稀疏，学习到的具有很少订单的网格嵌入往往是不可靠和无效的，此外，如果没有任何历史订单记录的孤立节点(例如，新建社区)，学习到的网格嵌入也是不可行的(无论作为O点还是D点)。为了缓解数据的稀疏性问题，我们提出基于地理学第一定律探索网格的地理相关性，即所有的东西都是相关的，但附近的东西比遥远的东西更相关。例如，在两个地理位置相近的网格中，乘客需求的数量往往接近彼此。特别地，我们考虑了网格嵌入部分的两种邻域，即地理邻域（地理上相邻的）和语义领域（通过OD流连接起来的）。前者用于度量一个网格与其邻域之间的内在紧密程度，后者用于对网络OD之间的交通流强度建模。

基于网格嵌入学习得到的网格的表示，结合乘客需求的重要时间信息，设计了一个面向ODMP的多任务神经网络。受既有工作的启发，我们对一个网格的流入流和流出流分别建模，预测每个网格在不同时间段的流入和流出需求数量。引入这两个子任务的基本原理是，我们能够在每个网格上单独捕获更多的动态出行模式。通过补充两个单独的子任务，总体需求预测任务可以捕获更强的内在时间模式，因为每个网格中的总体需求具有更大的规模或粒度。例如，在早高峰时段，当网格划分的粒度很小时，网约车需求的目的地可能存在很大不同，导致数据稀疏性问题，这意味着乘客需求的目的地可能分布得非常广泛，但这些网格的总流入流和流出流是非常大的。

本文的主要贡献：

  • 提出了一种新颖的问题ODMP，即OD矩阵预测问题。预测给定时间段内给定起点和终点的乘客需求，这可以极大地帮助乘车平台准备汽车和调度订单。
  • 通过将感兴趣的区域划分为地图上的网格来制定ODMP问题。然后设计网格嵌入网络，以通过新颖定义的网格邻域（地理和语义邻居）之间的图卷积为每个网格执行嵌入，该模型通过模仿GCN中的消息传递模式来建模不同网格之间的流量传输关系。
  • 设计了一个多任务学习网络，该网络依靠长期短期记忆循环网络（LSTM）来捕获旅客需求的时间趋势。两个子任务预测网格中的单个流入流和流出流需求，而主任务预测每对网格之间的需求。
  • 在两个真实大规模叫车数据集上的大量实验表明提出的GEML模型性能优于基准模型。

前提条件

定义

  1. Grid（网格）：整个感兴趣的空间区域（例如特定城市）被划分为n个不重叠的网格，表示为$G = {g_1，g_2，…，g_n}$。一个网格示例其中区域分为16个网格，每个网格的范围由最大和最小坐标定义。

  2. Time Slot:将时间划分为t个时隙序列,表示为${Slot_1,Slot_2,…,Slot_t}$。任何两个连续时隙之间的间隔是恒定的。

  3. OD Matrix:定义OD矩阵为$M \in \mathbb{N}^{G \times G}$，每个输入$m_{i,j}\in M$表示从网格 $g_i$到网格 $g_j$的乘客需求数量。

    • 在每个时隙中，对于任何两个网格$g_i, g_j \in G $，从$g_i$到$g_j$的旅行需求总数表示为$m_{i,j}$。

OD矩阵预测

问题定义：

  • 对于t个时隙，给定t个观察到的OD矩阵${M1，M2，…，Mt}$的序列和一组辅助特征$X_aux$（根据可用性可选），起源-目标矩阵预测（ODMP）是一个回归任务以预测下一个时隙$Slot_{t + 1}$中的OD矩阵$M_{t + 1}$。

方法

image.png

步骤：

  • OD矩阵可以从乘车服务提供商的出行记录中提取,(如果可获得)外部数据源将用于产生辅助功能
  • GEML的网格嵌入部分通过两种邻域的信息聚合来学习每个网格的嵌入向量：地理邻域和语义邻域
  • 每个网格的顺序矢量表示将被馈入多任务神经网络，以学习最近时隙$t_a$中网格的表示。
  • 利用网格的矢量表示来生成预测的OD矩阵。

GEML模型能同时捕获空间和时间特性。

  • 从空间角度出发，提出了一种基于邻域的网格嵌入方法，通过聚集邻域信息来学习每个网格的向量表示。
  • 从时间的角度，我们设计了一个多任务学习框架来模拟乘客需求随时间的动态趋势。接下来，我们将介绍网格嵌入和多任务学习的技术细节。

Grid Embedding

  • 由于GCN在低需求网格上的局限性，我们在ODMP的背景下提出了两种邻域函数用于乘客需求建模，即地理邻域和语义邻域。
  • 它们被用来测量一个网格与其相邻网格之间的内在紧密度，并分别捕获网格网络中始发地与目的地之间的业务流的语义强度。
  • 前者用于度量一个网格与其邻域之间的内在紧密程度，后者用于对网络OD之间的交通流强度建模

Geographical Neighborhood

  • 两个区域中心点之间的距离小于一定的阈值可定义为地理邻域。

$$
\Phi_i = {g_i|dis(g_i,g_j) \leq L }
$$

  • $dis(g_i,g_j)$表示两个网格中心的空间距离

Semantic Neighborhood

  • 如果两个区域之间至少有一个OD流 (可以是相反方向), 即可定义为两者为语义邻域。
  • 在任意时间段$t′= 1, 2,…，t$我们可以通过公式获取网格i的语义邻域。

$$
\Omega_{t′}^i = {g_i|m_{i,j} > 0 || m_{j,i} > 0, m_{i,j} \in M_t′,m_{j,i} \in M_t′ }
$$

  • 由公式可知，不同网格在不同时间间隔的语义邻居个数是不确定的。由于ODMP问题对时间敏感，因此考虑不同网格在不同时间间隔的语义关系至关重要。

Pre-Weighted Aggregator for Grid Embedding

  • 通过聚合地理邻域$\Phi_i$和语义邻域$\Omega_{t′}^i$推断在时隙$t_k$时的每个网格$g_i$的向量表示
  • 不是为每个网格训练一个不同的嵌入向量，而是训练一个聚合器函数，它学会从网格的邻域中积累和选择特征信息

朴素聚合器形式：

$$
\mathbf v_i = \sigma \Big (\mathbf W \cdot MEAN({ \mathbf v_i’} { \mathbf v_j’,g_j \in N_i)}) \Big )
$$

  • vi是网格gi的嵌入向量

  • MEAN(·)表示对应元素均值

  • vj是网格gj的嵌入向量

  • 朴素聚合方法：计算vi’和vj’对应元素的均值，并将它们连接到之前的特性vi’

  • 尽管有一些基本聚合器的变体(例如pooling aggregator and LSTM aggregator)，现有的图卷积聚合方法在ODMP场景下缺乏充分捕捉不同网格之间关系的能力，无法进行需求建模，原因是这些聚合器在融合每个网格邻居的所有特性时无法区分它们的重要性，直观地说，两个网格之间的地理距离越近，它们的属性就越相似。此外，在语义邻居集中，邻居网格的受欢迎程度应该对聚合过程产生影响，因为它保留了具有代表性的出行模式。

在此基础上，提出了一种预加权聚合器，该聚合器可以选择性地将重点放在网格嵌入的重要邻域上。对于网格的地理邻域，我们利用相邻区域之间的距离作为聚合器的权重因子。因此，我们将地理邻域的预加权聚合器表示为：

image.png

对于语义邻域，degree代表OD流量，即两个区域之间的OD流（从i到j或从j到i），$\epsilon$是一个非常小的值接近于零,以防$degree(g_j) = 0$。

注意，两种表示都是随时间变化的，是一个动态指标。最后，将两种语义表示连接起来得到一个网格最终的语义表示。

Multi-TaskLearning

  • 一种具有periodic-skip LSTM的多任务学习方案

image.png

Periodic-Skip LSTM

ht = LSTM(xt,ht−1).

在预测下一小时的乘客需求时，LSTM中的序列建模方案将迫使模型从之前的连续小时中收集信息。这可能对需求预测没有多大帮助，因为不相关的输入会产生很多噪音。为此，为了更好地对周期性进行建模，我们取网格嵌入序列{vi1, vi2，…， vit}作为输入，进一步将Eq.(8)转换为Periodic-Skip LSTM，跳过不相关的顺序模式。

hi t = LSTMps(vi t,hi t−p)

  • 其中p是跳过的隐藏状态数

Main Task: Predicting the OD Matrix

由periodic-skip LSTM框架,我们可以得到在时间t网格gi的向量表示。为了得到OD矩阵中每一项mij的值，我们构造了一个过渡矩阵Wm∈R（d×d）以对OD流进行建模。此时，预测值m可由下式计算。损失函数为均方误差。

mi,j = (Wmhi t)⊤hj t, (10) andweusemeansquarederrortocomputethelossfunctionfor themaintask:
LODMP =
1 |Mt+1|×N
N Õ n=1||Mt+1− ˆ Mt+1||, (11) wheremi,j ∈ Mt+1 is the real value in the OD matrix at time t +1,n ≤ N istheindexofthetrainingsample.

Two Subtasks:Predicting the In-and Out-Degrees

在预测上述总体OD矩阵的主要任务的同时，我们还分别对流入流（p）和流出流（q）进行了建模。

  • Win和Wout是用于将网格嵌入投影到标量的两个投影权重
  • 损失函数为均方误差，G是网格的个数。

Loss Functions

针对上述三个任务，我们将主要任务的损失和两个子任务的损失结合起来，制定出总体损失函数。

评价

四个问题：

  1. GEML在ODMP任务上的效果如何？
  2. 模型的每个拟议组成部分如何对GEML的性能做出贡献？
  3. 每个主要超参数如何影响GEML的预测性能？
  4. GEML学习了哪些实际的移动性模式？

数据集

  • UCAR:北京，2016 8.1-8.31
  • Didi:成都 2016 11.1-11.30

基线

  • HA
  • LSTM
  • LSTNet
  • GCRN

变体：

  • GEML-S1
  • GEML-S2
  • GEML-S3
  • GEML-S4
  • GEML-AF

实验设置

指标

  • RMSE
  • SMAPE

相关工作

总结

  1. 定义了乘客需求的ODMP问题
  2. 不仅需要预测区域中的需求数量，还需要预测需求的目的地。
  3. 通过区域邻居的信息对区域的移动性模型进行建模，在此基础上设计了网格嵌入框架。
  4. 在其聚合过程中添加了预加权函数，以便它可以感知数据的范围和稀疏性。
  5. 利用具有非周期性跳过成分的多任务LSTM对时间趋势进行建模。
  6. 子任务可以通过扩大每个网格内总体需求的规模或粒度来协助主要任务捕获更强大的固有时间模式。
  7. 整个过程是一个端到端模型，称为基于网格嵌入的多任务学习（GEML）。
  8. 在两个现实世界和大规模的乘车数据集上评估了模型

缺点：有一个致命弱点，即没有考虑行程时间，由O点到D点需要一定的行程时间，因此实时的OD矩阵是不可能得到的，因此利用真实的历史OD矩阵作为输入在实时预测中是不可行的。