交通预测新视角 - 基于 GCN 的出租车 OD 需求预测

本文由 简悦 SimpRead 转码, 原文地址 https://mp.weixin.qq.com/s?__biz=Mzg4MTE4ODQ3MA==&mid=2247484047&idx=1&sn=7f47b3acc84d59d8272f392ae77ec263&chksm=cf688996f81f0080a9bb6e533d80acabd07dc52f494b805cfdfdc7f8bc9ba736302155abe242&scene=0&xtrack=1&key=dd5051400a9fb58fd42734976fb4891e399d9a8fd01a1d26d1e8a711b3810cc7d2455721ebf91add938a0e646769762f781adc1da3a01ef3ca49c3dcf8dc252eb7994f9850f2d5d6a6674405053cd854&ascene=1&uin=Nzc5NjI3Njgx&devicetype=Windows+7&version=62060833&lang=zh_CN&pass_ticket=0D2i7tjRttrD043Y7F4kCHwZJzqgJzkLTPsgkirjBZi1ERON%2Bm%2FzBZkrpJsAOSE5

今天周末啦,明天又是新的一周,时间过得好快哦,晚上和同学出去吃了饭,很开森!发完文章就休息啦,晚安~

1、文章信息

《Origin-Destination Matrix Prediction via Graph Convolution: a New Perspective of Passenger Demand Modeling》。

北航计算机学院发在 2019KDD 上的一篇论文。

2、摘要

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

3、简介

除了预测某一区域内可能的乘客需求数量外,了解每次出行的来源地和目的地的乘客需求也很重要。因为不同时段两个区域之间的需求量不仅承载着乘客需求的强度,而且有利于挖掘有用的出行模式。本文从一个新的角度研究了乘客需求模型,即 OD 矩阵预测(ODMP)。OD 矩阵包含两个方面的信息: (1) 不同的 OD 组合; (2) 每个 OD 对的旅客需求数量。ODMP 的目标是预测在给定时间段内从一个地理区域到另一个地理区域的叫车订单数量。为了同时兼顾出行产生量和目的地,时空特性以及数据稀疏性,本文提出了一种基于网格嵌入的单馈多任务学习模型 (GEML),以基于图对出行模式进行建模。具体来说,我们用图表示与地理区域相关的乘客订单记录,其中节点表示地理区域 (以网格形式定义),节点之间的边表示乘客需求,边权重表示订单数量。利用改进后的网格,可以构造出给定时间间隔内的 OD 矩阵。如图 1 所示,将区域划分为 16 个网格,订单记录汇总在相应的 OD 矩阵中。

upload successful

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

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

本文主要贡献如下:

(1)提出 OD 矩阵预测问题预测给定时间段内的 OD 乘客需求,这对于网约车平台运营管理具有重要意义。

(2)将研究区域划分为网格,设计了网格嵌入网络,通过在新定义的网格邻域 (地理和语义邻域) 之间的图卷积,对每个网格进行嵌入,该网络通过模仿 GCNs 中的信息传递模式来模拟不同网格之间的 OD 流关系。

(3)借助 LSTM 设计了一个多任务学习网络用于捕捉乘客需求的时间趋势。两个子任务预测网格中的单个流入流和流出流需求,而主任务预测每对网格之间的需求。

(4)在两个真实大规模叫车数据集上的大量实验表明提出的 GEML 模型性能优于基准模型。

4、模型框架

upload successful

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

4.1 Grid Embedding

在 ODMP 环境下,提出了网格嵌入部分的两种邻域,即地理邻域(地理上相邻的)和语义领域(通过 OD 流连接起来的)。前者用于度量一个网格与其邻域之间的内在紧密程度,后者用于对网络 OD 之间的交通流强度建模,如图所示。

upload successful

(1)Geographical Neighborhood

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

upload successful

(2)Semantic Neighborhood

如果两个区域之间至少有一个 OD 流 (可以是相反方向), 即可定义为两者为语义邻域。在任意时间段 t′= 1, 2,…,我们可以通过公式 2 获取网格 i 的语义邻域。由式 (2) 可知,不同网格在不同时间间隔的语义邻居个数是不确定的。由于 ODMP 问题对时间敏感,因此考虑不同网格在不同时间间隔的语义关系至关重要。

upload successful

(3)Pre-Weighted Aggregator for Grid Embedding

我们通过聚合地理邻域Φ和语义邻域Ω推断每个网格的向量表示,我们不是为每个网格训练一个不同的嵌入向量,而是训练一个聚合器函数,它学会从网格的邻域中积累和选择特征信息。在详细介绍用于网格嵌入的预加权聚合器之前,我们首先简要介绍 [10] 采用的朴素聚合器形式:

upload successful

vi 是网格 gi 的嵌入向量,MEAN(·) 表示对应元素均值,vj 是网格 gj 的嵌入向量, 朴素聚合方法即是计算 vi’和 vj’对应元素的均值,并将它们连接到之前的特性 vi’。 然而,尽管有一些基本聚合器的变体 (例如 pooling aggregator and LSTM aggregator),现有的图卷积聚合方法在 ODMP 场景下缺乏充分捕捉不同网格之间关系的能力,无法进行需求建模,原因是这些聚合器在融合每个网格邻居的所有特性时无法区分它们的重要性,直观地说,两个网格之间的地理距离越近,它们的属性就越相似。此外,在语义邻居集中,邻居网格的受欢迎程度应该对聚合过程产生影响,因为它保留了具有代表性的出行模式。

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

upload successful

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

upload successful

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

upload successful

4.2 Multi-Task Learning

本节出了一种具有 periodic-skip LSTM 的多任务学习方案,如图 4 所示。

upload successful

(1) Periodic-Skip LSTM

upload successful

为了全面了解乘客需求的动态模式,我们从 UCAR 数据集中随机抽取了 5 天,并在图 5 中绘制了每天的每小时乘客需求。

upload successful

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

upload successful

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

(2)main task

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

upload successful

upload successful

(3)Two Subtasks: Predicting the In- and Out-Degrees

在预测上述总体 OD 矩阵的主要任务的同时,我们还分别对流入流(p)和流出流(q)进行了建模。其中 Win 和 Wout 是用于将网格嵌入投影到标量的两个投影权重。损失函数为均方误差,G 是网格的个数。

upload successful

upload successful
(4)损失函数

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

upload successful

实验部分不再详述。

5、总结

总体而言,文章的研究角度确实很新,值得借鉴。但这篇文章仍有一个致命弱点,即没有考虑行程时间,由 O 点到 D 点需要一定的行程时间,因此实时的 OD 矩阵是不可能得到的,因此利用真实的历史 OD 矩阵作为输入在实时预测中是不可行的。


  目录