Artificial Neural Networks Applied to Taxi Destination Prediction 总结
论文：Artificial Neural Networks Applied to Taxi Destination Prediction
论文背景：ECML/PKDD会议上关于预测出租车目的地的挑战赛。
任务：基于出租车初始轨迹及各种相关的元数据（出发时间、司机ID、乘客信息）预测其目的地。
模型：多层感知器网络(MLP)、双向循环神经网络(BRNN)、记忆网络(MN)
数据集：数据集由442辆出租车在葡萄牙波尔图市行驶一整年（2013-07-01至2014-06-30）的所有完整轨迹组成
共有170万个数据项 ，每个数项包含以下属性：
1、出租车完整的路径：每15秒测量一次GPS位置（纬度和经度）
2、与出租车相关的元数据（出发时间、司机ID、乘客信息）
测试集：由320条前缀轨迹及其相关元数据组成。
数据集处理
“我们的任务是根据给出的前缀轨迹预测出租车的目的地。由于数据集是由完整的轨迹组成的，因此我们必须以正确的方式切割轨迹来生成前缀轨迹。”
所提供的训练数据集由170万条完整的轨迹组成，通过分割生成了83480696（8000多万）个可能的前缀轨迹。(平均1条完整轨迹约分割出50条前缀轨迹)
分割前缀轨迹算法：
- Maximum=100。
- 如果如果轨迹小于或等于Maximum个GPS点，则生成所有可能的前缀。
(例如该完整轨迹有30个GPS点，则生成29条前缀轨迹)
- 否则，选择Maximum个前缀的随机子集。
(例如该完整轨迹有150个点，则有149条前缀轨迹，从中随机选出100条前缀轨迹)
模型
1、多层感知器网络(MLP)
多层感知器（multi-layer perceptron，mlp）是一种神经网络，前一层每个神经元都与下一层的所有神经元相连。
输入层接收出租车的前缀轨迹与相关的元数据，输出层预测出租车的目的地（纬度和经度 ）。
(1)输入层
Q:我们首先遇到的问题之一是，轨迹前缀是gps点的变长序列，这与mlp的固定大小输入不兼容。
A:我们选择只考虑前缀轨迹的前k个点和最后k个点，这将为我们的输入向量提供总共2k个。
选择2K个点的算法：
当前缀轨迹大于2k个点时，取前K个点和后K个点
|
…… |
当前缀轨迹包含小于2k大于K个点时，前K个点和后K个点是重叠的。
当前缀轨迹小于等于k点时，我们通过重复第一个或最后一个点来填充输入的gps点。
将客户ID、出租车ID、日期和时间等元数据嵌入模型进行训练。
元数据（Client ID[1~57106] 、Taxi ID[1~448]、Stand ID[1~64]、Quarter hour of the day[1~96]、Day of the week[1~7]、Week of the year[1~52]）
例如：1571533200（2019-10-20 09:00:00）==》
Quarter hour of the day：36
Day of the week：7
Week of the year：42
(2)目的地集群和输出层
Q:由于我们要预测的目标是由两个标量值（纬度和经度）组成的，但是直接预测经纬度这样的模型很难训练（很难收敛）。
A:为了解决这个问题，我们用mean-shift聚类算法对目的地进行聚类，返回一组c=3392个聚类。网络输出每个预测每个目的地的概率Pi, 计算预定义目的地集群中心的加权平均值：
举个例子，例如C=3，C1，C2，C3的簇心经纬度分别为（115，30），（110，35），（120，40），
网络预测每个目的地的概率为P1=0.2, P2=0.5, P3=0.3，则最终结果输出的ŷ=（115*0.2+110*0.5+120*0.3，30*0.2+35*0.5+40*0.3）=（114，35.5）
(3)代价函数和训练算法
模型的代价函数(即x，y点的距离)定义如下（λx为x点的经度，φx为其纬度，r为地球半径）：
d越小，代价损失值就越小。
2 RNN
RNN网络结构，其中GPS点在前缀的前向上逐个读取，滑动窗口为5。（架构的其余部分与之前相同，为了清楚起见，省略了该部分。）
如前所述，mlp受其固定长度输入的约束，这使得我们无法充分利用整个轨迹前缀。
3.2BRNN
我们注意到前缀最相关的部分是它的开始和结束，因此我们尝试了双向rnn[11]（brnn）来关注这两个特定的部分。
3.3 记忆网络
我们从训练数据集中提取m条完整的轨迹（我们称之为候选轨迹）。然后我们使用两个神经网络编码器分别对前缀和候选者进行编码（所有候选者使用相同的编码器）。
换句话说，前缀的最终目的地预测是由softmax概率关系加权的候选目的地的质心。这类似于我们在前面描述的体系结构中组合集群的方式。
4 实验结果
测试数据集：19770条轨迹
上表测试模型的误差。与模型1相反，模型2在不使用集群的情况下直接预测目的地。模型3只使用前缀作为输入，没有任何元数据。模型4只使用元数据作为输入，没有前缀。当模型6的brnn在每个时间步取一个gps点时，模型7的brnn在每个时间步取五个连续的gps点。
5 结果分析
我们成功的ecml/pkdd挑战模型是使用目的地集群的mlp模型。然而，在我们的自定义测试中，它不是最好的模型，它是带有窗口的brnn。
实验结果还证明了嵌入和聚类对模型的显著改进。
MeanShift聚类算法：
（1）在未被标记的数据点中随机选择一个点作为中心center；
（2）找出离center距离在bandwidth之内的所有点，记做集合M，认为这些点属于簇c。同时，把这些求内点属于这个类的概率加1，这个参数将用于最后步骤的分类
（3）以center为中心点，计算从center开始到集合M中每个元素的向量，将这些向量相加，得到向量shift。
（4）center = center+shift。即center沿着shift的方向移动，移动距离是||shift||。
（5）重复步骤2、3、4，直到shift的大小很小（就是迭代到收敛），记住此时的center。注意，这个迭代过程中遇到的点都应该归类到簇c。
（6）如果收敛时当前簇c的center与其它已经存在的簇c2中心的距离小于阈值，那么把c2和c合并。否则，把c作为新的聚类，增加1类。
（7）重复1、2、3、4、5、6直到所有的点都被标记访问。
后续工作：
- 调研轨迹预测（变种）模型。
- 继续丰富师兄出租车目的地论文，将步骤理清。