The Simpler The Better:A Unified Approach to Predicting Original Taxi Demands based on Large-Scale Online Platforms

论文题目：越简单越好:基于大型在线平台的原始出租车需求预测的统一方法

摘要

翻译：
出租车呼叫应用程序因其为有需要的乘客调度闲置出租车的效率而越来越受欢迎。为了准确平衡出租车供需，网络出租车平台需要预测单位原始出租车需求(UOTD)，即单位时间(如每小时)和单位区域(如每个POI)提交的叫车需求数量。预测UOTD对于大型工业在线出租车平台来说不是小事，因为准确性和灵活性都是必不可少的。复杂的非线性模型，如GBRT和深度学习，通常是准确的，但需要劳动密集型的模型重新设计后，场景变化(例如，额外的约束，由于新的法规)。为了准确地预测UOTD，同时保持对场景变化的灵活性，我们提出LinUOTD，这是一个具有超过2亿个特征维度的统一线性回归模型。简单的模型结构消除了重复模型设计的需要，而高维特征有助于准确的UOTD预测。我们进一步设计了一系列优化技术，以提高模型的训练和更新效率。对来自一个工业在线出租车平台的两个大型数据集的评估证实LinUOTD在准确性上优于流行的非线性模型。我们设想在UOTD预测中采用具有高维特征的简单线性模型的经验，作为一项试点研究，可以提供一些见解

总结：

Unit Original Taxi Demand 简称 UOTD ，单位原始出租车需求
为了准确平衡出租车供需，网络出租车平台需要预测单位原始出租车需求(UOTD)，即单位时间(如每小时)和单位区域(如每个POI)提交的叫车需求数量。
为了准确地预测UOTD，同时保持对场景变化的灵活性，本文提出了LinUOTD，一个具有超过2亿个特征维度的统一线性回归模型。

介绍

出租车需求的代表性指标是单位原始出租车需求(UOTD)，即单位时间(如每小时)、单位区域(如每个POI)提交给网络出租车平台的叫车订单数量。
pick-ups 简称 PU 拾取器
UOTD不同于拾取器的数量(PU)。单位时间和单位区域的PU数是UOTD的子集，因为UOTD忽略了最终放弃打车的潜在乘客。相比之下，UOTD则反映了给定时间和空间内完整的原始乘客需求。

UOTD信息对网络出租车平台有三重好处。

拓展潜在市场。通过比较历史UOTD和对应的PU数，平台可以发现呼叫出租车动机强但最终打车次数少的时间和地区。
评估激励机制。UOTD反映了用户在采用新的折扣策略和动态定价后乘坐出租车出行的意愿。
指导出租车调度。在线出租车平台可以提前预测漫游出租车的流量，为乘客分配漫游出租车提供便利。

过去的出租车需求预测方面的重点是预测PU的数量。他们通常根据出租车轨迹与出租车轨迹之间的关系来预测出租车轨迹的数量。然而，出租车轨迹并不总是与uotd相关联。这样就不可能将PU预测扩展到UOTD预测，使得PU预测无法扩展到UOTD预测。

两种范式:

具有少量特征的复杂(非线性)模型：
- 优点:(在大多数时空预测研究中是首选的)
- 缺点:(需要连续不断地重复劳动密集型的模型重新设计过程)
具有大量特征集的简单(线性)模型
- 一个具有大量特征的线性模型，以统一的框架方便新信息的整合。

存在的问题以及解决的方案：

统一的简单线性模型是否能够准确地预测UOTD
- 本文通过整合来自异构数据集的高维特征来解决这个问题
- 首先调查多个真实数据集，包括原始出租车需求(OTD)，兴趣点(POI)和气象学
- 本文框架将在空间、时间、气象和事件域上处理四种基本特征，并基于在线出租车平台的业务逻辑生成大量组合特征。
高维特征也给在大规模数据集上训练高维特征模型带来了额外的挑战。
- 本文的LinUOTD框架通过一个基于参数服务器的分布式框架来解决这个问题，以并行化和加速模型训练，并通过一个基于hash的特征标记方案来实现并行和可扩展的特征工程。
- LinUOTD采用L1和L2正则化方法，设计了时空正则化方法，在避免过拟合的同时进行准确的预测。

本文提出的框架概述

本文的贡献：

首次尝试采用具有高维（数亿）特征的简单线性模型来预测UOTD，以满足大型在线出租车平台的准确性和灵活性要求。
将模型重新设计的开销转换为特征工程，并应用分布式学习框架来支持快速，并行和可扩展的特征更新和测试。
本文的方法在预测准确性方面优于经典非线性模型。

数据集

数据集描述：

数据集中包括原始出租车需求记录，地理信息和气象数据。
在中国的两个大城市（北京和杭州）收集的

原始出租车需求记录数据（Original Taxi Demand Record Data）

北京数据集

北京数据集的原始出租车需求记录是从中国的在线出租车平台按比例采样的。
原始数据集包含北京三个月连续75天的23,851,235原始出租车需求记录。
数据集中的每个记录都由用户ID，时间戳，起点和终点的位置，距离估计和折扣信息组成。

杭州数据集

杭州数据集的原始出租车需求记录是从同一在线出租车平台上按比例抽样的。
原始的杭州数据集包含三个月内连续75天的连续12,354,687张出租车的原始需求记录。
数据集中的每个记录都由用户ID，时间戳，起点和终点的位置，距离估计和折扣信息组成。

其中

用户ID，时间戳，起点和终点由用户提交。
出租车平台基于用户提交的信息来计算距离估计和折扣信息。
用户ID和目的地被省略，因为它们与UOTD预测无关。

数据集分析图分为6个部分:

所有原始出租车需求记录中起点位置的热图，可以观察到出租车需求集中的几个位置。(集中在市中心，密集的居民区和交通枢纽)
每天原始出租车需求记录的标准化数量的分布（三个月内）。可以表明出租车需求可能会受到动态时间因素（例如天气）的影响。
原始滑行需求的标准化数量相对于不同估计距离的分布（黄色曲线）和累积百分比（绿色曲线）。可以表明短途旅行占了出租车总需求的主导。
折扣的分布，可以看到大多数出租车需求在哪个区间内获得折扣。

因为不同城市间的气候、经济和城市规划存在差异，所以添加两种数据：

POI兴趣点空间分布图
每月天气分布图

POI Data

来自中国主要在线地图服务提供商的大规模地理信息数据集。
本文利用兴趣点（POI）的地理信息

北京：

北京POI数据集包含北京的55,447个不同的POI。
每个记录都包含一个职位，一个姓名，一个行政区和一个三级类别。

一条记录如下所示：
$\text{(116.49460 40.00057, Wangjing, Playground, Changyang District, Entertainment:OurdoorActivity:Playground)}$
其中

（116.49460 40.00057）代表POI的经度和纬度，
Wangjing Playground表示POI名称，
Changyang District是一个行政区在北京，
Entertainment:OurdoorActivity:Playground即娱乐：户外活动：游乐场，这是三个级别的类别。
- 三级类别分别由粗略级（娱乐），中级（户外活动）和子级（游乐场）组成。

总共将POI分为16个粗级别，83个中级别和155个子级别。
POI可以帮助解释出租车旅行的动机，从而解释UOTD的时空分布。

16种POI的粗略分类：

本文的目标是预测每个POI的UOTD，因此本文通过将每个原始出租车需求记录的坐标与最近的POI相关联来对其进行预处理。

杭州：
杭州的POI数据集，其中包含42965个杭州不同的POI，和北京有着相同的类别

Meteorology Data

通过中国政府的在线气象网站在相应的三个月内进一步收集北京的气象数据。
每个气象记录都包含一个时间戳以及每小时的天气状况，温度，风，湿度和空气质量信息。天气状况分为雨夹雪，薄雾，雪，雨，晴朗，多云，雾和阴天。
空气质量分为六个等级：良好，中等，轻度污染，中度污染，重度污染和重度污染。

存在的问题及解决方法：
问题：

在气象数据集中，有6％的记录不完整或为空。

解决方法：

通过将前几个小时和下几个小时的值进行平均，本文可以完成缺少的温度，风力和湿度。
对于缺少的天气状况和空气质量信息，我们使用与前一小时相同的值。

特征工程

采用高维特征来补偿简单线性模型的表达，从而使它们具有复杂非线性模型的预测能力。

基本特征

时间特征（Temporal Features）

Month
Day of month
Day of week
Hour
Holiday
Historical UOTD

平日，周末和全天的标准化每小时出租车需求分布图，可以看出需求在工作日和周末之间具有不同的时间模式。（工作日有两个高峰，分别代表早晨高峰和傍晚高峰。在周末，晚上只有一个高峰。）

空间特征（Spatial Features）

District
POI name
POI category
Distance distribution
16种粗略POI类别中的每一种的规范化出租车需求图。[属于“基础设施”类别（例如，火车站和机场）的POI和“住所”看到了更多的出租车需求。]
标准化的出租车平均需求量
短，中，长出租车行程图。 [长途骑行（> 20公里）的需求相对稳定，而对短途骑行（<8km）的需求在不同的日子里急剧波动,如果来自POI的滑行需求主要由长途行驶所控制，则从该POI开始的滑行需求很可能在一段时间内保持稳定。]

气象特征（Meteorological Features）

Weather condition
Temperature
Wind
Humidity
Air quality

活动特征（Event Features）【影响打车者的动机】

Discount pricing strategy
Even-odd license plate plan
Version of the App

组合特征

线性模型无法描述输入特征之间的相关性
将多样化的组合特征输入模型有助于从多尺度和多方面表征不同因素之间的相互作用，这是提高模型的预测能力的关键。

时时组合特征（Temporal-Temporal Combinational Features）

将一天中的小时和星期几作为一个组合功能

时空组合特征（Temporal-Spatial Combinational Features）

POI类别和“小时”的组合将捕获出租车需求的这种时空依赖性

居住类POI和基础设施类POI的平均每小时标准化出租车需求图

气象空间组合特征（Meteorological-Spatial Combinational Features）

结合气象和空间特征的理由是，气象信息对出租车需求的影响因功能不同的POI而异。
雨天和非雨天娱乐场所和机场的平均每小时标准化出租车需求图【降雨对机场的影响不明显。娱乐场所的需求对降雨敏感】

其他组合功能（Other Combinational Features）

将POI，小时和天气组合为时空气象特征

本文最终选择了100多种功能，这些功能包括2亿个维度。

本文的特征表：

模型和优化

LinUOTD模型，具有高维特征和时空正则化器的线性回归模型
为了有效地训练LinUOTD模型，本文采用了基于参数服务器的分布式学习框架和基于散列的令牌化方法

UOTD预测模型

原始数据集 $D= \lbrace (x_i,y_i)|i=1,2,…,N \rbrace$
$(x_i,y_i)$ 表示第i个样本的UOTD和相应的特征向量。
$p_i = w^\prime x_i$

$$
obj_{linear}(w) = \sum_{i=1}^N (y_i-p_i)^{2} + \lambda_1 ||w||_1 + \lambda_2 ||w||_2
$$

$y$ the UOTD in a specific hour at a given POI
$x \in \mathbb{R}^m $ the feature vector corresponding to $y$
一个具有超过两亿维的非常高维的向量。
real-world UOTD records close in space or time tend to be similar.
UOTD预测结果的这种平滑性要求导致本文设计以下目标函数来反映时空正则化：
$$
obj_{spatio-temporal}(w) = \sum_{X \subseteq D} \phi(X) var(\lbrace w^\prime x|x \in X\rbrace)
$$
$var()$ 表示方差
$X$ 是 $D$ 的子集
$\phi(X)$ 将POI和时间的子集映射为实值，该实值控制X中实例x的预测方差的正则化。

$$
\phi(X) = \prod_{x \in X} \frac{1}{\sigma \sqrt{2 \pi}} e^{- \frac{(x - \overline{X})^\prime((x - \overline{X})}{2\sigma}}
$$

$\overline{X} = \frac{1}{|X|} \sum_{x \in X} x$
$\overline{X}$表示X的均值

$$
obj_{LinUOTD}(w) =\sum_{i=1}^N (y_i-p_i)^2 + \lambda_1 ||w||1 + \lambda_2 ||w||_2 + \gamma \sum{X \subseteq D} \phi(X) var(\lbrace w^\prime x|x \in X\rbrace)
$$

其中

$\gamma$ 权衡参数，可以全局控制时空正则化的影响。

使目标函数$obj_{LinUOTD}(w)$最小化，采用了具有egulatized dual average (RDA)和AdaGrad的随机梯度下降算法，如FTR1算法。
在不考虑L1和L2正则化的情况下，我们可以使用基于minibatch的随机梯度下降来最小化：
$$
w_{t+1} = w_t - \eta_t g_t
$$

$t$表示迭代次数
$\eta_t$是第t次迭代的学习率
$g_t$表示第t次迭代的梯度。

从迭代t的数据中抽取一个小批量$X \subseteq D$

以矩阵形式$X_t = (x_1,…,x_l)^\prime$表示
定义$\overline{X_t} = (\overline{X_t},\overline{X_t},…,\overline{X_t})^\prime$

在$obj_{LinUOTD}(w)$中没有L1，L2损失的目标函数的导数是
$g_t = X^\prime_t(p_t - y_t) + \gamma \phi(X) (X^\prime_t X - \overline{X_t}^\prime\overline{X_t})$

其中$p_t$和$y_t$分别是$X_t$中数据的预测向量和标签向量。

RDA:解决正则化
$w_{t+1} = w_t - \eta_t g_t$的对偶如下：
$$
w_{t+1} = argmin_w(\sum_{s=1}^t g_s w + \frac{1}{2} \sum_{s=1}^t (\sigma_s ||w-w_s||_2^2 + \lambda_1 ||w||_1) + \lambda_2 ||w||_2)
$$

其封闭形式的求解器如下:

遵循AdaGrad，调整坐标的学习率以加快学习过程:
对于$g_t$的第i个坐标，
$$
\eta_{t,i} = \frac{\alpha}{\beta+\sum_{s=1}^t g_{s,i}^2}
$$
以上公式推导参考论文

B. McMahan, G Holt, D Sculley, M. Young, D. Ebner, J. Grady, L. Nie, T. Phillips, E. Davydov, D. Golovin, S. Chikkerur, D. Liu, M. Wattenberg, A. Hrafnkelsson, T. Boulos, and J. Kubica. 2013. Ad click prediction: a view from the trenches. In The 19th ACM International Conference on Knowledge Discovery and Data Mining, Chicago, IL, USA. 1222–1230.

实现和优化

LinUOTD的结构简单，有2亿维的功能
在一台机器上训练LinUOTD不可行。为了有效地学习高维特征，本文利用了一个基于参数服务器的分布式学习框架和一个基于散列的令牌化方法。

系统优化

用于训练LinUOTD的基于参数服务器的分布式框架的体系结构：

该框架由多个参数服务器和工作节点组成，适用于海量数据集上的并行机器学习。
所有模型参数均均匀地分布在参数服务器之间，而训练数据则在训练过程开始时分配到每个工作节点。
在训练过程中，每个工作节点运行多个并行工作程序（线程），这些工作程序以小批量分析训练样本，通过全局特征哈希函数从参数服务器中获取相应的参数，并计算预测值和梯度。
算法1+算法2

特征工程优化

通过特征标记化，可以为每个功能（可以是值，字符串或它们的组合）分配唯一的ID
由于分配全局唯一的功能ID需要所有线程共享一个锁，因此令牌化使并行计算变得困难且效率低下。

本文提出了一种基于哈希的令牌化方法，该方法以无锁的方式为每个功能分配一个ID，同时确保ID的全局唯一性。

通过诸如murmurhash和cityhash的哈希方案将每个离散功能哈希到64位空间。因此，即使对于十亿维特征，哈希冲突的速率仍然很低。
基于哈希的令牌化具有两个优点：
并行性。由于所有线程之间需要共享锁，因此无法并行化经典令牌化方案。相反，基于散列的令牌化是无锁的，因此可以进行并行计算。
可伸缩性。要对新数据特征维度进行令牌化，基于哈希的令牌化仅需要对新维度进行哈希处理，而无需重新分配ID。

上述基于散列的令牌化在我们的分布式并行学习框架中至关重要，可大大加快数据准备过程。

算法1总结了每个工人的梯度计算过程。

相同参数的梯度将首先通过工作人员内部聚合进行聚合
然后在工作节点之间转移以进行跨工作人员聚合
最后所有新计算的梯度将被推送到相应的参数服务器，并且每个参数服务器将使用接收到的梯度相应地更新参数。

算法2根据Sec中的公式详细说明了每个参数服务器上的参数更新过程

以上迭代将一直持续到训练过程结束。

实验研究

实验设置

在两个数据集上：北京和杭州
按时间顺序排列每个数据集，并使用前3/4进行训练，其余1/4进行测试。

基线

HA(Historical Average)：
历史平均值。使用同期内历史UOTD的平均值来预测UOTD
ARIMA(Auto-RegressiveIntegratedMovingAverage)：
自回归综合移动平均线。使用时间序列模型预测UOTD。
Markov(Markov Model)：
马尔可夫模型。通过基于15个最近对应周期的UOTD训练3阶马尔可夫预测器来预测UOTD。
GBRT(Gradient Boosted Regression Tree)：
梯度增强回归树。使用非参数回归预测UOTD。
NN(Neural Network)：
通过使用15个最近对应时间段的UOTD训练神经网络来预测UOTD
HP-MSI：
采用最先进的技术来预测UOTD，以预测要从每个自行车站出租或返还每个自行车站的自行车数量

指标

Error Rate (ER)
Symmetric Mean Absolute Percent Error (SMAPE)
Root Mean Squared Logarithmic Error (RMLSE)

$$ER = \frac{\sum_{i=1}^N |p_i-y_i|}{\sum_{i=1}^N y_i}$$
$$SMAPE = \frac{2}{N} \sum_{i=1}^N \frac{|p_i-y_i|}{p_i+y_i+1}$$
$$RMLSE = \sqrt{\frac{1}{N} \sum_{i=1}^N (\log (p_i+1)-\log(y_i+1))^2}$$

总体结果

朴素的HA在两个数据集上的表现都很差。但是，有时ARIMA和Markov甚至比单纯的HA方法还差。一个可能的原因可能是时间序列方法忽略了UOTD的空间变化。因此，它们倾向于对不同区域产生不稳定的预测精度，因此在大规模数据集上的总体性能不令人满意。
NN和GBRT是两种竞争方法。原因可能是这两种方法都是受监督的非线性模型，并且能够从多个异构数据源中提取时空特征。
专为时空预测而设计的方法（HP-MSI和我们的LinUOTD）可实现最佳整体性能。我们的LinUOTD在两个数据集上的几乎所有指标上均优于HP-MSI。唯一的例外是杭州数据集上的SMAPE指标，其中HP-MSI得出的SMAPE略低。

总之，LinUOTD通过采用简单的线性回归模型，通常优于所有基线（基于时间序列的方法和复杂的非线性模型），这表明正确选择的大量特征集可以弥补UOTD预测中模型的简单性。

特征贡献分析

最有帮助的功能是时间（星期几，小时），空间（POI名称，POI类别）和气象（天气状况，温度，空气质量）功能的多尺度组合。
最后两个主要特征是基本的时间特征，这与直觉是UOTD与不同时间尺度的最新历史UOTD高度相关。
具体而言，UOTD倾向于在短时间内（例如，与1天前的UOTD比较）平稳变化，并表现出某些周期性模式（例如，与7天前的UOTD比较）。

原型系统

技术：

使用flatty（基于引导程序的模板）来构建前端基本页面
使用mapbox API（自定义在线地图的较大提供者）来创建页面上与地图相关的元素
后端，使用flask（Web应用程序的python微框架）处理请求

功能：

用户为POI和当前时间提交关键字（顶部）后，将显示相关POI（左侧），并且POI的位置也会在地图上标记出来。
用户还可以通过选择“查看3D”来查看3D视图。
POI下一个小时的预测将由不同高度和颜色的条形表示。
当用户通过将光标放在某个POI附近来导航POI时，UOTD预测的详细信息将显示在灰色表中，其中包括接下来五个小时的预测以及最近五个小时的历史UOTD记录。

特征贡献分析表

总结

提出了LinUOTD，一种用于预测大型在线出租车平台的单位原始出租车需求（UOTD）的统一方法。
LinUOTD是具有超过2亿维特征的线性回归模型。【简单的模型结构便于模型修改，而高维特征则保证了准确的预测性能。】
设计了一个时空正则化方案，一个分布式学习框架和一个基于散列的令牌化方法，以在大规模数据集上实现有效，并行和可扩展的特征学习。
对来自工业在线出租车平台的两个大规模数据集的广泛评估验证了我们方法的有效性。

摘要

介绍

数据集