基于SDZ-RNN的出租车出行目的地预测方法

张国兴，李亚东，张磊，樊庆富，李想

中国矿业大学计算机科学与技术学院，江苏徐州221116

基于SDZ-RNN的出租车出行目的地预测方法

张国兴，李亚东，张磊，樊庆富，李想

中国矿业大学计算机科学与技术学院，江苏徐州221116

1 引言

随着城市化进程加快，城市中出租车数量在急剧增加，大大方便了人们出行。出租车所带来的一系列问题也成为城市化建设中不可忽略的部分。其中，出租车目的地预测问题颇为引人关注，正确预测出租车出行目的地对于城市交通合理规划起着至关重要的作用。城市中许多出租车都搭载全球定位系统GPS（Global Positioning System），出租车在运行过程中产生了大量GPS轨迹数据，使得预测出租车目的地成为可能。

出租车目的地预测方法有多种，Mahmassani H S[1]基于滚动式预测模型，通过时间序列方法预测出租车出行目的地，但是此方法具有一定的滞后性。Tang J等[2]将出租车目的地预测问题转换为动态规划问题，但是此方法需要耗费大量资源。Xue A Y等[3]运用低阶马尔科夫方法进行出租车目的地预测，但是马尔科夫预测方法仅仅依赖于前面2到3个GPS点，当一条轨迹中相互依赖点的个数较多时，马尔科夫预测方法并不能很好地解决这种轨迹点之间的长期依赖关系[4]。

为了解决这种长期依赖关系，de Brébisson A等[5]采用循环神经网络RNN（Recurrent Neural Network）等预测方法来对出租车出行目的地进行预测，取得了不错的效果。因为RNN的层与层之间是有关联的，所以RNN的隐藏层能够在预测过程中储存这种轨迹点之间的长期依赖关系[6]，从而很好地解决轨迹点之间的长期依赖问题。Hochreiter[7]也针对需要解决的长期依赖问题，在RNN的基础上提出了一种LSTM[8]（Long Short-Term Memory）模型，被广泛应用于时间序列数据来解决长期依赖关系。而Tang S[9]针对用户可能需要的短期兴趣，提出了一种BLSTM（Bidirectional Long Short-Term Memory）模型，在MovieLens[10]数据集上效果显著。

但是RNN预测方法在解决长期依赖过程中，随着数据量的增大，RNN的隐藏层对较小的扰动变得十分敏感，较小的扰动就会导致RNN产生的中间状态中的错误成分在传播过程中被指数级放大，最终导致预测的准确率不够高。

为了限制这种状态中错误成分的传输，保证正确成分的传输，Hinton[11]等提出了dropout，概率性地完全保留或者直接舍弃某些输出状态。dropout虽然能在一定程度上遏制错误状态的传输[12]，但它设置某一些神经元的激活函数为0，一定程度上舍弃了正确的输出状态。Krueger D[13]提出了一种改进的方法zoneout[13]。zoneout用它本身激活函数随机地代替一些神经元激活函数，并不能很好地根据状态本身来做出合适的选择。2017年，Rocki K[14-15]等在zoneout的基础上提出了一种概率化舍弃或保留前一次迭代所产生的输出状态的方法SDZ（Surprisal-Driven Zoneout）[14]，SDZ能够根据状态本身来确定该状态的传输情况，以此来最大限度地保证状态中正确成分的传输，遏制错误成分的传输。

由于SDZ能够根据状态本身来最大限度地保证该状态中正确成分的传输，所以将SDZ应用于RNN中，提出一种基于SDZ-RNN的出租车目的地预测方法：SRTDP。该方法采用SDZ来概率化神经元状态在隐藏层的传输，遏制状态中错误成分的传输，保证状态中正确成分的传输，从而降低扰动对RNN的影响，使得预测出的状态与实际状态更加接近，提高预测的准确率。同时，SDZ的使用使得SRTDP中参数更新变成了部分更新，而不是像普通RNN预测方法中需要更新全部参数，降低了训练完成所耗费的时间。

2 基于SDZ-RNN的出租车目的地预测

2.1 出租车目的地预测

出租车目的地预测以出租车GPS轨迹数据为输入，通过轨迹数据的内在关系，预测出租车目的地。

定义1出租车轨迹序列Tk。Tk={Pk1,Pk2,…,Pki,…,Pkn}，轨迹序列Tk中共有n个GPS点，其中Pki(n≥i≥1)代表轨迹序列中每一个GPS数据点，每一个GPS点包含经纬度信息。

定义2预测的目的地x。预测目的地就是通过RNN预测出轨迹序列目的地的GPS点，其中包括对出租车目的地预测的经度λx和纬度φx，即x(λx,φx)。

定义3Haversine距离DH和等距形公式距离DE。半正矢距离公式可以计算出预测目的地x和真实目的地y之间的距离：

其中λy,λx分别代表真实目的地y和预测目的地x的经度，φy,φx分别代表其纬度，R代表地球半径取值为6 371 km。通过计算DH(x,y)返回真实目的地y和预测目的地x两地之间的距离，单位为km。

为简化计算，使用近似的等矩形公式来计算两地之间的距离：

2.2 基于SDZ-RNN的出租车目的地预测

2.2.1 SDZ（Surprisal-Driven Zoneout）

在SDZ中，通过Zt来控制状态的传输。Zt的生成以及Zt如何影响神经元输出如图1所示。

图1 SDZ结构

SDZ是在原始LSTM上增加了一个反馈环，如图1中虚线所示。这个反馈环能够根据当前获得的前一次迭代神经元输出pt-1，产生一个参数Zt来影响该神经单元的记忆状态ct（可以理解通过Zt来过滤ct）。

在图1中，st定义如下：

其中ft,it,ot代表相应门限的输出状态，ut代表在激活函数tanh的作用下处理输入数据和隐藏层状态形成的值。W,U,V代表各个分支的权重，ht-1代表在t-1时刻隐藏层的状态，b代表各个门限的偏移量。

设置一个变量St，使得这个变量等于t-1时刻输出层的输出pt-1减去t时刻的输入数据xt。由变量St作用产生zt，公式如下：

其中公式（10）中τ代表一个阈值参数，用于保持数值稳定，WTet是一个隐藏层状态h→神经元输出et的权重矩阵。同时zt携带参数更新的信息，由zt可以确定哪些参数需要更新而不是更新全部参数。根据zt的值简化成一个参数zt，当zt≤0时，表明误差较大，将其舍去，故取zt为0；当zt＞0，表明相邻状态之间的差距较小，故取Zt=zt，公式如下：

Zt决定了神经单元的记忆状态ct。特殊的，当Zt=0时，St将不会参与决定神经单元的记忆状态，也就意味着没有参数需要更新，公式如下：

从公式（12）中可以看出反馈环作用于t-1时刻神经单元的记忆状态ct-1，形成t时刻的神经单元记忆状态ct。在预测过程中，反馈环的加入使得SRTDP能够最大限度地传输状态中的正确成分，从而很好地消除扰动，增强SRTDP的鲁棒性。

公式（13）、（14）表明激活函数tanh作用于ct，作用后的ct点乘输出门限控制后的输出状态ot，从而得到在t时刻隐藏层状态ht。由隐藏层到输出层的输出et：

Softmax回归即为公式（16）得到概率分布p，进而得出预测目的地点x。

其中C为聚类点的个数。

2.2.2 基于SDZ-RNN的目的地预测方法框架

本文基于SDZ-RNN的目的地预测方法的关键在于：如何将SDZ整合到RNN中。基于SDZ-RNN的出租车目的地预测方法如图2所示。

图2中基于SDZ-RNN的目的地预测方法在输入层将轨迹序列Tk和轨迹相关的嵌入数据包括出租车编号、一年的周数、一周的天数、一天的刻数、日期类型、站台叫车起点和电话叫车起点共7种嵌入数据结合作为输入数据，其中轨迹序列按顺序输入到上述模型中，每个GPS点又包含经纬度；从7种嵌入数据中各随机选取10个。轨迹相关的嵌入数据充当了轨迹的特征，原始轨迹数据和相应的特征共同作为该方法的输入。轨迹特征的加入使得预测过程中分类更加准确从而提高了预测的准确率。

图2 基于SDZ-RNN的出租车目的地预测方法

隐藏层采用M个ReLU（Rectified Linear Unit）神经元，对应的激活函数也为ReLU。该函数将小于0的值过滤掉，大于0的值保持不变。通过激活函数将非线性元素加入到SRTDP中，增加了SRTDP的非线性映射学习能力。

输出是对每个聚类点产生概率估计后所计算出的预测目的地。所以在原始输出层神经元的个数N由对轨迹数据聚类后产生的聚类个数C来确定，聚类算法采用的MeanShift（详见theano）。假设在原始输出层每个输出神经元对应的原始输出为ei(i≤N)，在Softmax层将ei转变成一个对应聚类点的概率分布pi，见公式（16），进而得出预测的目的地。

整合SDZ到RNN中如图2所示。在计算过程中，前一次迭代输出层神经元的输出pt-1和xt（xt代表在t时刻模型的输入数据）作为后一次迭代输入层神经元的输入，Zt由SDZ根据pt-1产生，输入层神经元的输入在激活函数ReLU和Softmax的作用下产生神经元输出pt，pt又通过SDZ产生下一次迭代的Zt。如此循环，在迭代完一次batch（训练的一次样本）之后，将公式（3）得出的值作为损失函数来计算预测目的地和实际目的地之间的差距。由于Zt中携带参数更新信息，通过更新部分参数而不是全部参数使得SRTDP的训练时间减少；同时SDZ中的反馈环的加入提高了SRTDP的鲁棒性，使之在隐藏层能够轻松地应对小的扰动，从而提高预测准确率。

2.2.3 SRTDP提高精度和速度

传统的RNN预测方法不能根据输出层神经元的输出pt进行动态调整隐藏层神经元的输出ht，单纯地将前一次迭代输出层神经元的输出pt-1直接作为后一次迭代输入层神经元的输入。应用SDZ使得SRTDP加入一个反馈环，可以根据pt-1来设置一个参数Zt，动态调整pt-1传入后一次迭代过程，同时携带参数更新信息，这样做的好处在于当pt-1较小时（即预测结果越正确），相邻的数据点也会被充分利用来预测目的地，进而可以提高预测准确率，同时部分参数的更新也节约了时间。把SDZ应用于文献[5]中RNN来预测出租车出行目的地，改变神经元输出pt的影响方式。

在使用SRTDP预测方法时，改进了文献[5]中RNN预测方法输出神经元的输出pt在相邻两次迭代之间的传递方式，通过设置Zt来过滤前一次迭代神经元的输出pt-1，并且最大限度地保证pt-1中正确成分的传播以及遏制错误成分的传播，以此来保证神经单元的记忆状态ct能够更加契合真实的单元状态，提高预测的准确率；SDZ中Zt携带参数更新的信息，由Zt可以确定哪些参数需要更新而不是更新全部参数，降低了训练完成时间。同时，SDZ由LSTM构成，在解决长期依赖问题方面比RNN预测方法更有优势。

3 实验及分析

3.1 实验数据与实验环境

本文以波尔图出租车轨迹数据[5]为实验数据集。该数据集包含了2013年7月1日到2014年6月30日期间，在波尔图（葡萄牙）采集的442辆出租车的轨迹数据，轨迹数据包括：GPS点集合、出租车编号、一年的周数、一周的天数、一天的刻数、日期类型、站台叫车起点和电话叫车起点。

首先随机抽取原始数据集中15万条轨迹数据作为训练数据集，然后对抽取的轨迹数据做非空检查，若该轨迹GPS点集合为空，则删除该条轨迹数据。经过处理，共获得149 259条轨迹。

测试数据采用文献[5]中所用的320条轨迹数据。

实验程序采用Python2.7编写，使用theano、fuel、blocks等第三方库。实验操作系统采用Ubuntu16.04。实验硬件环境：CPU四核，Core i5处理器2.3 GHz，内存为8 GB。

3.2 实验及结果分析

3.2.1 实验内容

首先，采用MeanShift聚类算法对提取到的149 259条轨迹训练数据的GPS点集合进行聚类得到1 379个簇，即公式（16）中，C=1 379。隐藏层神经元个数M取值为500，原始输出层神经元个数。设置一个固定的学习率η=0.01，设置一个较低的学习率是为了保持训练过程的相对稳定；动量系数α=0.9，主要为了改变梯度变化的幅度；权重初始值W为0.1，偏移量初始值b为0.01，设置较小的参数初始化是为了打破层与层之间的对称性；batch_size为200，即每次训练在训练集中取200个样本进行训练。在确定好初始参数之后，将GPS轨迹数据和对应的嵌入数据共同作为SRTDP算法的输入，SDZ-RNN开始训练。

模型训练完成之后，采用3.1节中测试数据集来测试训练好的模型。

3.2.2 结果分析

为了评估SRTDP在出租车目的地预测上的性能，将SRTDP预测方法的精度和速度与文献[5]中的RNN预测方法作比较。使用平均距离误差（Average Distance Error，ADE）和预测准确率（Prediction Accuracy，PA）来量化SRTDP的性能。平均距离误差（ADE）通过平均化每条轨迹的真实目的地和预测目的地之间的距离计算得出。真实目的地和预测目的地之间的距离在1.0 km之内视为预测正确。

SRTDP预测方法和文献[5]中的RNN预测方法的比较结果如图3和图4所示。

图3 平均距离误差比较

图4 预测准确率比较

在图3中，SRTDP预测方法和文献[5]中RNN预测方法的平均距离误差（ADE）都随着迭代次数的增加而降低，并且SRTDP预测方法的平均距离误差（ADE）明显低于文献[5]中RNN预测方法。从图3中还可以得出，SRTDP预测方法的最小平均距离误差是2.24 km，而文献[5]中RNN预测方法的只有3.14 km[5]。在最小平均距离误差方面，SDZ-RNN比RNN降低了28%。在图4中，SRTDP预测方法的预测准确率（PA）明显高于文献[5]中RNN预测方法。SRTDP预测方法的最大预测准确率是0.731，而文献[5]中RNN预测方法只有0.611。在预测准确率方面，SRTDP预测方法比文献[5]中RNN预测方法提高了大约12%。SRTDP预测方法的精度优于文献[5]中RNN预测方法，因为SDZ的使用保证了隐藏层状态中的正确成分的传输，遏制了错误成分的传输，使得预测出的状态与真实状态更加接近，进而提高预测的准确率。

由公式（12）可知Zt参与决定了ct的形成，从而影响了预测的准确率，在SRTDP预测方法中通过对Zt取不同的值来观察Zt的敏感性，如图5所示。

图5 Zt取值不同时预测的平均距离误差

在图5中，Zt的取值越低使得平均距离误差越低。当Zt取0.3时，最小的平均距离误差为2.55 km。当Zt取值较低时意味着相邻状态之间的差距很小，预测出的状态与真实状态之间变化不大，进而降低了预测的平均距离误差。

为了验证SRTDP预测方法在解决长期依赖方面的优势，从数据集中挑选出GPS点多于200个的轨迹。SRTDP预测方法和文献[5]中RNN预测方法在解决长期依赖方面的比较如图6和图7所示。

图6 长期依赖的平均距离误差比较

图7 长期依赖的预测准确率比较

在图6和图7中，SRTDP预测方法在解决长期依赖方面明显好于文献[5]中RNN预测方法，预测准确率明显提高，平均距离误差大幅度降低。这是因为SRTDP预测方法中SDZ是由LSTM构成的，在数量增大时仍然能够很好地解决长期依赖。

最后，比较SRTDP预测方法和文献[5]中RNN预测方法针对同样的数据集模型训练完成所需要的时间，比较结果如图8所示。

图8 两种方法的时间比较

在图8中，SRTDP预测方法和模型训练完成的时间耗费明显低于文献[5]中RNN预测方法，SRTDP预测方法的最好结果是17 837 s，而文献[5]中RNN预测方法的最好结果只有19 205 s，SRTDP预测方法在时间耗费方面比文献[5]中RNN预测方法降低了7%，因为SRTDP预测方法通过每次更新部分参数，而并不是像文献[5]中RNN预测方法一样每次更新全部的参数，从而节省了时间。

为了进一步验证SRTDP在精度和速度方面的优势，将SRTDP与采用dropout的RNN预测方法（dropout-RNN）和采用zoneout的RNN预测方法（zoneout-RNN）在预测准确率，平均距离误差，解决长期依赖和训练完成时间方面进行比较。

在图9中，SRTDP预测方法的平均距离误差（ADE）低于dropout-RNN方法和zoneout-RNN方法。对比三种方法的平均距离误差的最小值，dropout-RNN为2.90 km，zoneout-RNN为2.73 km，而SRTDP只有2.24 km。在图10中，SRTDP预测方法的预测准确率（PA）也明显高于dropout-RNN方法和zoneout-RNN方法，dropout-RNN的最大预测准确率为0.645，zoneout-RNN为0.690，而SRTDP高达0.731。SRTDP能够使得预测产生的状态与真实状态更加接近，提高预测准确率。

图9 平均距离误差比较

图10 预测准确率比较

SRTDP、dropout-RNN和zoneout-RNN在解决长期依赖方面的比较如图11和图12所示。

图11 长期依赖的平均距离误差比较

图12 长期依赖的预测准确率比较

在图11和图12中，SRTDP预测方法在解决长期依赖方面明显好于dropout-RNN方法和zoneout-RNN方法，预测准确率明显提高。

在图13中，SRTDP、dropout-RNN和zoneout-RNN的训练完成时间相差不大。对比三种方法的最短训练完成时间，SRTDP为17 837 s，dropout-RNN为18 000 s，zoneout-RNN为17 900 s。三种方法在训练完成时间上基本一致。

图13 训练完成时间比较

从实验可以得出，SRTDP预测方法在精度和速度上都优于文献[5]中RNN预测方法。在时间耗费相差不大的基础上，SRTDP预测方法比dropout-RNN和zoneout-RNN降低了预测的平均距离误差，提高了预测的准确率，在解决长期依赖方面也更有优势。

4 结束语

本文利用轨迹数据，对出租车出行目的地进行预测，对比文献[5]中已有的RNN预测方法，提出了一种将基于SDZ-RNN的出租车目的地预测方法：SRTDP。SRTDP预测方法能够动态地改变神经元输出状态在相邻神经元之间的传输，并且通过设置Zt来过滤前一神经元的输出状态，以此来保证神经元记忆单元状态能够更加契合真实的单元状态，进而提高预测的准确率；同时Zt携带的参数更新信息确定了哪些参数需要更新而不是更新全部参数，节约了时间。实验表明，SRTDP预测方法降低了预测的平均距离误差，提高了预测的准确率，在解决长期依赖方面也更有优势。

[1] Mahmassani H S.Dynamic network traffic assignment and simulation methodology for advanced system management applications[J].Networks and Spatial Economics，2001，1（3/4）：267-292.

[2] Tang J，Song Y，Miller H J，et al.Estimating the most likely space-time paths，dwell times and path uncertainties from vehicle trajectory data：A time geographic method[J].Transportation Research Part C：Emerging Technologies，2016，66：176-194.

[3] Xue A Y，Zhang R，Zheng Y，et al.Destination prediction by sub-trajectory synthesis and privacy protection againstsuchprediction[C]//IEEEInternationalConference on Data Engineering，2013：254-265.

[4] Besse P C，Guillouet B，Loubes J M，et al.Destination prediction by trajectory distribution based model[J].IEEE Transactions on Intelligent Transportation System，2016.

[5] de Brébisson A，Simon É，Auvolat A，et al.Artificial neural networks applied to taxi destination prediction[J].arXiv preprint arXiv：1508.00021，2015.

[6] Baskar M K，Karafiát M，Burget L，et al.Residual memory networks：Feed-forward approach to learn long-term temporal dependencies[C]//2017 IEEE International ConferenceonAcoustics，SpeechandSignalProcessing（ICASSP），2017：4810-4814.

[7] Hochreiter S，Schmidhuber J.Long short-term memory[J].Neural Computation，1997，9（8）：1735-1780.

[8] Endo Y，Nishida K，Toda H，et al.Predicting destinations from partial trajectories using recurrent neural network[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining.Cham：Springer，2017：160-172.

[9] Tang S，Wu Z，Chen K.Movie recommendation via BLSTM[C]//International Conference on Multimedia Modeling.Cham：Springer，2017：269-279.

[10] MovieLens[EB/OL].[2017-03-20].https：//grouplens.org/datasets/movielens/Keogh.

[11] Hinton G E，Srivastava N，Krizhevsky A，et al.Improving neural networks by preventing co-adaptation of feature detectors[J].Computer Science，2012，3（4）：212-223.

[12] Tan Y K，Xu X，Liu Y.Improved recurrent neural networks for session-based recommendations[C]//Proceedings of the 1st Workshop on Deep Learning for Recommender Systems，2016：17-22.

[13] Krueger D，Maharaj T，Kramár J，et al.Zoneout：Regularizing rnns by randomly preserving hidden activations[J].arXiv preprint arXiv：1606.01305，2016.

[14] Rocki K，Kornuta T，Maharaj T.Surprisal-driven zoneout[J].arXiv preprint arXiv：1610.07675，2016.

[15] Rocki K M.Surprisal-driven feedback in recurrent networks[J].arXiv preprint arXiv：1608.06027，2016.

ZHANG Guoxing,LI Yadong,ZHANG Lei,et al.Taxi travel destination prediction based on SDZ-RNN.Computer Engineering andApplications,2018,54（6）：143-149.

ZHANG Guoxing,LI Yadong,ZHANG Lei,FAN Qingfu,LI Xiang

College of Computer Science and Technology,China University of Mining and Technology,Xuzhou,Jiangsu 221116,China

In the prediction of the taxi destination,the traditional Markov prediction method relies only on the first 2 to 3 GPS points,and does not apply to trajectories that have very long dependencies.In order to solve the long-term dependencies,this paper uses Recurrent Neural Network（RNN）to predict the taxi destination,this is because the multiple hidden layers of RNN can store this dependencies.However,with the increasing amount of data,the hidden layers of RNN is very sensitive to small perturbations and the perturbations will be exponentially enlarge in the latter part of prediction,reducing the prediction accuracy.In order to improve the prediction accuracy of taxi destination and reduce the training time,this paper applies SDZ to RNN,and proposes a new taxi destination prediction method based on SDZ-RNN（SRTDP）.SDZ can not only improve the robustness of SRTDP,but also reduce the training time by adopting partial update instead of full update.Experiments show that SRTDP is superior to RNN prediction method in accuracy and speed,the prediction accuracy is improved by 12%,and the training completion time is reduced by 7%.

taxi destination prediction;recurrent neural networks;SRTDP method;prediction accuracy

在预测出租车目的地时，传统的马尔科夫预测方法仅仅依赖于前面2到3个GPS点，对于那种具有很长依赖关系的轨迹并不适用。为了解决这种长期依赖关系，采用循环神经网络（RNN）进行出租车目的地预测，因为RNN的多个隐藏层能够存储这种依赖关系。但是随着数据量的增大，RNN的隐藏层对较小的扰动变得十分敏感，较小的扰动就会被指数级放大，最终导致预测准确率降低。为了提高预测准确率，同时缩短训练时间，将SDZ应用到RNN中，提出一种基于SDZ-RNN的出租车目的地预测方法（SRTDP）。SDZ不但能够提高SRTDP的鲁棒性，而且SDZ采用局部更新而不是全部更新的方式，降低了训练时间。实验表明，SRTDP在精度和速度上都优于RNN预测方法，预测准确率提高了12%，训练完成时间降低了7%。

出租车目的地预测；循环神经网络；SRTDP方法；预测准确率

2017-07-07

2017-09-12

1002-8331（2018）06-0143-07

A

TP312

10.3778/j.issn.1002-8331.1707-0110

中央高校基本科研业务费专项资金（No.2014XT04）；教育部博士点基金（No.20110095110010）；江苏省自然科学基金（No.BK20130208）。

张国兴（1993—），男，硕士研究生，研究领域为移动对象轨迹数据挖掘，E-mail：zhangguoxing@cumt.edu.cn；李亚东（1993—），男，硕士研究生，研究领域为移动对象轨迹数据挖掘；张磊（1977—），男，博士，副教授，研究领域为移动对象轨迹数据挖掘；樊庆富（1993—），男，硕士研究生，研究领域为移动对象轨迹数据挖掘；李想（1993—），女，硕士研究生，研究领域为移动对象轨迹数据挖掘。