Predicting Taxi Demand at High Spatial Resolution: Approaching the Limit of Predictability

论文题目：以高空间分辨率预测出租车需求：接近可预测性的极限

摘要

采用整体方法来预测高空间分辨率下的出租车需求。
使用两个真实的数据集（黄色出租车和纽约市的Uber行程）展示了我们的技术，并对曼哈顿的9,940个构建块进行了评估。

我们的方法包括两个关键步骤

首先，我们使用熵和人员流动的时间相关性来衡量构建模块级别的需求不确定性。
其次，为了确定哪种预测算法可以达到理论上的最大可预测性，我们实现并比较了三个预测器：
- Markov预测器（基于可概率性的预测算法）
- Lempel-Ziv-Welch预测器（基于序列的预测算法）
- 神经网络预测器*（使用机器学习的预测算法）

结果表明：

可预测性因构建基块而异，平均而言，理论上最大可预测性可高达83％。
预测器的性能也有所不同：神经网络预测器为可预测性较低的块提供更高的准确性，而马尔可夫预测器为可预测性较高的块提供更高的准确性。
在具有最高最大可预测性的区块中，马尔可夫预测器能够以89％的精度预测出租车需求，比神经网络预测器好11％，而仅需要0.03％的计算时间。
这些发现表明，最大可预测性可以作为选择预测算法的良好指标。

介绍

出租车服务是存在不平衡的问题的。

本文出租车需求预测问题的定义：

给定区域i中的历史出租车需求数据，希望预测下一个时间间隔内区域i内出现的出租车数量。

目标：

预测满足的出租车需求（met taxi demands）

使用接客数量来表示某个地区的出租车需求，并将其视为顺序数据
可以从满足的出租车需求中推断出未满足的需求

许多预测出租车需求的方法，包括不确定性分析，概率模型，时间序列，SVM和神经网络。

两个关键问题：

给定预测算法$\alpha$，同时考虑出租车需求序列的随机性和时间相关性，预测算法$\alpha$可以达到的潜在精度的上限是多少？
给定潜在精度的上限，考虑到计算时间和精度之间的权衡，哪个预测器具有更好的性能？

本文的解决方案：

本文通过分析某个地区出租车需求的最大可预测性（$\Pi^{max}$）来选择最佳预测器。
最大的可预测性由出租车需求序列的熵定义，同时考虑了随机性和时间相关性。
最大可预测性$\Pi^{max}$由Song等人首先提出，用于分析用户移动性[10]。
将最大可预测性$\Pi^{max}$定义为预测算法可以预测出租车需求的最高潜在精度。
最大的可预测性通过测量人员流动的规律性来捕获出租车需求序列的时间相关程度。
对于大多数地区，出租车需求受一定程度的随机性（例如，突发事件）和一定程度的规律性（例如，每周模式）支配，可用于预测。
例如，一个$\Pi^{max} = 0.3$的构建块表示在至少70％的时间中，此块的出租车需求似乎是随机的，并且只有30％的时间我们才能希望预测出租车的需求。
无论预测算法多么出色，我们都无法以$\Pi^{max} = 0.3$的精度预测高于30％的构建块的未来出租车需求。
$\Pi_{max}$表示构建块中出租车需求可预测性的基本限制。
出租车需求的时间相关性并不总是成立。不同的区域具有不同的功能，因此具有不同的可预测性。
假设要选择最佳预测器，必须分析每个地区出租车需求的最大可预测性（$\Pi^{max}$）

本文的贡献：

本文测量纽约市每个组成部分的出租车需求的理论最大可预测性。这代表了预测算法$\alpha$可以达到的潜在精度的上限。结果显示，出租车需求的最大可预测性平均可以达到83％。最大可预测性捕获了出租车需求序列的时间相关程度。所以根据结果可知，纽约市的出租车需求具有很强的时间格局。
本文实现并比较了三个预测变量的预测准确性：
- Markov预测变量（基于概率的方法）
- Lempel-Ziv-Welch（LZW）预测变量（基于序列的方法）
- 神经网络（NN）预测变量（一种基于机器学习的方法）
结果表明：
- NN预测器为具有低可预测性的构建块提供了更高的准确性
- 而Markov预测器为具有高可预测性的构建块提供了更高的准确性
- 最大可预测性是实现实际预测准确性的一个可行目标，并且具有多个功能的计算密集型NN预测器并不总是比简单的Markov预测器好。
在考虑准确性和计算成本的同时，了解每个构件的可预测性可以帮助确定使用哪个预测器。

出租车需求的可预测性

目标：以提议的最大可预测性回答之前的问题

问题1：考虑到出租车需求的随机性和时间相关性，在构建块i中，给定预测算法$\alpha$和从时间1,2，… n开始的出租车需求$D_n^{(i)}$的序列，我们想要找到预测算法$\alpha$可以达到的最大可预测性（最高潜在准确度）$\Pi^{max}$。

出租车需求

使用出租车乘客数$d_t^{(i)}$来代表在构建块i中t时候的出租车的需求

由于出租车需求可能会有很大的变化，因此很难预测$d_t^{(i)}$的确切值。
为简单起见，我们使用因子$q$对出租车需求的值取整。
将每q个出租车需求分组为一个出租车需求。
尝试预测每个q级别的出租车需求，
将q = 10设置为使预测更加宽松，同时保持较低的误差。至于q的影响力见下方论文。

K. Zhao, D. Khryashchev, J. Freire, C. Silva, and H. Vo, “Predicting taxi demand at high spatial resolution: Approaching the limit of predictability,”https://serv.cusp.nyu.edu/projects/demandprediction/ 2016taxidemand.pdf, Tech. Rep., July 2016.

熵（Entropy）

熵是表征可预测性程度的有效方法。通常低熵意味着较高的可预测性。
本文使用三种熵测度：
- 随机熵$S_{random}^{(i)}$
- 香农熵$S_{Shannon}^{(i)}$
- 实熵$S_{real}^{(i)}$

Random Entropy

$
S_{random}^{(i)} = \log_2 N^{(i)}
$

$N^{(i)}$是$D_n^{(i)}$中唯一出租车需求的数量
较低的熵意味着较高的可预测性。如果构建块i中的出租车需求较低，则随机熵$S_{random}^{(i)}$将很小，并且很容易预测出租车需求。

Shannon Entropy

$
S_{Shannon}^{(i)} = - \sum_{t=1}^{N^{(i)}} p(d_t^{(i)})\log_2 p(d_t^{(i)})
$

$p(d_t^{(i)})$是在第i个构建块上有$d_t^{(i)}$出租车需求的概率–它表征了出租车需求的不确定性。

注：随机熵和香农熵都与时间无关，并且不考虑时间模式。

Real Entropy

$
S_{real}^{(i)} = - \sum_{S_n^{(i)} \subset D_n^{(i)}} P(S_n^{(i)})\log_2 [P(S_n^{(i)})]
$

$P(S_n^{(i)})$表示在出租车需求序列$D_n^{(i)}$中找到特定时间顺序的子序列$S_n^{(i)}$的概率。

注：与香农熵和随机熵不同，真实熵不仅考虑构建块中不同出租车需求的频率，而且考虑出租车需求的时间模式的顺序。

查找给定集合的所有子集的问题具有指数复杂度（$O（2_n）$）
使用LempelZiv估计器来计算实际熵。 Lempel-Ziv估计器可以快速收敛到实际熵[16]。对于时间n之后的出租车需求序列，可以通过以下方式估算熵

$
S_{real}^{(i)} = \Big ( \frac{1}{n} \sum_t s_t^{‘(i)}\Big )^{-1} \ln n
$

$s_t^{‘(i)}$表示从时间t开始的最短子序列的长度，从1到t-1都没有出现。

最大可预测性（Maximum Predictability $\Pi^{max}$）

本文将可预测性$\Pi$定义为算法$\alpha$可以正确预测构建块中未来的出租车需求的成功率。
对于具有唯一出租车需求$N^{(i)}$的构件，可预测性度量取决于Fano不等式$\Pi
\leq \Pi^{max}$

给定熵$S$和构建块$i$中不同的出租车需求$N^{(i)}$，可以通过以下公式计算最大可预测性$\Pi^{max}$：

$$
S = - \Pi^{max} \log_2(\Pi^{max}) - (1-\Pi^{max})\log_2(1-\Pi^{max})+(1-\Pi^{max})\log_2(N^{(i)} - 1)
$$

最大可预测性$\Pi^{max}$为0到1之间的值。值越大，算法越准确。
通过不同的熵测度$S_{random}^{(i)}$，$S_{Shannon}^{(i)}$和$S_{real}^{(i)}$，我们具有不同的最大可预测性值$\Pi^{random}$，$\Pi^{Shannon}$和$\Pi^{real}$。
本文证明，$\Pi^{random}$≤$\Pi^{Shannon}$≤$\Pi^{real}$，因此$\Pi^{real}$是最大可预测性$\Pi^{max}$。

所以问题的回答是：给定一个预测算法α，$\Pi^{max}$是预测算法α可以达到的最大可预测性。

证明略

可扩展性（Scalability ）

\Pi^{max} \log_2(\Pi^{max}) - (1-\Pi^{max})\log_2(1-\Pi^{max})+(1-\Pi^{max})\log_2(N^{(i)} - 1) - S = 0
$
$S$和$N^{(i)}$是已知的
定义函数$f(\Pi^{max}) = - \Pi^{max} \log_2(\Pi^{max}) - (1-\Pi^{max})\log_2(1-\Pi^{max})+(1-\Pi^{max})\log_2(N^{(i)} - 1) - S$
由于$\Pi^{max}$是一个介于0到1之间的值，所以当$f(\Pi^{max})= 0$时找到交点可以求解$\Pi^{max} = \gamma$的方程。
求解所有方程$f(\Pi^{max})= 0$的计算时间为$O(m)$，其中$m$是积木总数。所以可以通过在多个处理器上为每个构件分配$f(\Pi^{max})= 0$的计算来进行缩放。

预测者

这一部分作者提出了三种预测器：

Markov预测器（基于概率的方法）
LZW预测器（基于序列的方法）
神经网络（NN）预测器（基于机器学习的方法）

用这三种预测器来预测出租车需求并比较它们的性能

问题2：给定构造块i的最大可预测性$\Pi^{max}$，考虑到计算时间和精度之间的折衷，我们希望找到一种性能更好的预测器。

Markov预测器

LZW预测器

神经网络预测器

数据集和预处理

数据集

出租车数据集：

the NYC yellow taxi data set
the NYC Uber taxi data set

Pluto(Primary Land Use Tax Lot Output)数据集：

NYC Pluto data set

数据预处理和可扩展性

结果

出租车需求的最大可预测性平均可以达到83％的准确性。

Limits of Predictability 可预测性的限制

由于Πmax捕获了出租车需求的时间相关性，因此，如果在我们的预测算法中考虑时间相关性，我们可以达到更高的潜在预测准确性。如果我们每天而不是按小时对出租车需求进行分组，也会发现类似的结果

Predictability of Different Functional Buildings 不同功能性建筑物的可预测性

不同的构造块表现出不同的最大可预测性。
住宅和工作场所都具有较高的可预测性，因此具有很强的时间格局。对于其他地方，例如旅馆，交通中心或办公室物业，其可预测性不如住宅或工作场所高。这些地区的出租车需求主要取决于白天发生的事件。

Uber Versus Yellow Taxi

研究了Uber和黄色出租车之间的可预测性差异。
由于Uber出租车的稀疏性，我们在邻域级别分析了这两个数据集的最大可预测性。我们将每个社区的每小时出租车需求分组，并检查每小时出租车需求序列的最大可预测性。
Uber出租车服务的最大可预测性高于黄色出租车。这可能是因为黄色的出租车通常采用随机巡航策略，而Uber的出租车在接到请求后便前往乘客所在的地方。 Uber出租车可以更好地捕获某个地区出租车需求的时间相关性。

评估

实验设置

使用三周的出租车接送数据作为训练数据，并以一周的出租车接送数据作为测试数据来比较这三个预测指标。
每小时对每个构建块的出租车需求进行分组
为了减少偏差，在上周的星期一，星期三和星期日的午夜（00:00），早晨（06:00），中午（12:00）和晚上（18:00）选择12个时间间隔作为预测目标。
根据最大可预测性Πmax对构建基块进行排名，并将它们分为十个1,000个构建基块组。我们选取每组的一组中位数构建基块进行调查（每组10个）
总共有60,480个训练样本和1,200个测试样本。

Error metrics

采用误差测量值对称平均绝对百分比误差（sMAPE）来评估预测算法。

评估

NN预测器为可预测性较低的构建块提供了更高的准确性。在最大可预测性Πmax= 72％最低的组中，NN预测器的预测精度为70％-在所有预测器中最高。这是因为NN预测器能够捕获多个特征，例如天气信息[7]，而其他两个预测器则无法捕获。马尔可夫预测器为具有高可预测性的构建块提供了更好的准确性，并迅速收敛到可预测性上限Πmax。这与以前的研究一致，即最大可预测性与马尔可夫预测器预测准确性之间存在高度正相关[12]。在具有最高最大可预测性的构造块中，马尔可夫预测器能够以89％的准确性预测出租车需求，比预测的要好11％。 NN预测器。除了。马尔可夫预测器的计算时间仅为0.5秒，仅为NN预测器的0.03％（见图6（b））。对于具有高可预测性的区域，马尔可夫预测器能够以更少的计算时间提供更好的预测精度。从实验中我们发现，最大可预测性Πmax可以帮助我们确定使用哪个预测器。在可预测性较低的区域中，我们可以使用NN预测器通过捕获多个特征来达到高精度，而在可预测性较高的区域中，马尔可夫预测器能够在保持较低计算时间的同时提供更好的预测精度。

总结

分析了纽约市超过1400万的黄色和Uber出租车接送样品。
出租车需求具有很高的可预测性（平均高达83％），这表明人类流动性与时间之间具有很强的相关性。
研究哪种预测算法可以达到最大的可预测性。
证明了计算密集型NN预测器并不总是比Markov预测器具有更好的预测精度。在可预测性较低的区域，NN预测器可以通过捕获其他特征（天气等）来达到高精度。
在具有高可预测性的区域中，马尔可夫预测器能够在保持较低计算时间的同时达到较高的预测精度。
可能由于不同的巡航策略，可以在Uber出租车数据中更好地捕获出租车需求的时间相关性。
本文的结果不仅限于出租车需求问题。可以将相同的方法用于其他时空数据集中的预测

未来的工作：

将针对时空预测问题提出一种基于可预测性的新预测器，例如，马尔可夫模型的输出可被视为NN预测器的功能。

日志总结：

从中了解了“最大可预测性”，本文作者是指预测算法可以预测未来出租车需求的成功率，即预测算法可以达到的最大预测性。
作者在本文通过比较三个预测器的预测准确性，从中发现某些规律，从而表明在考虑准确性和计算成本的同时，可以根据每个构件的最大可预测性来帮助确定使用哪个预测器。
作者是在纽约市的数据集上进行的实验，并且可知纽约市的出租车需求具有很强的时间格局。
了解了the unmet taxi demand,比如需要出租车但找不到出租车的人数。研究角度是可以从出租车数据集推断未满足的出租车需求