出租车目的地预测的深度学习方法*

崔淑敏，张 磊，李 允，邵长兴，朱少杰

(1.中国矿业大学计算机学院，江苏 徐州 221116;2.矿山数字化教育部工程研究中心，江苏 徐州 221116)

1 引言

出租车作为城市交通的重要部分，影响着人们日常出行，正确预测出租车目的地有重要现实意义。随着GPS技术的普及和应用，绝大多数出租车都配有GPS传感器，可以采集出租车的实时位置，形成轨迹序列。

早期出租车目的地预测研究多基于概率论，Comaniciu等[1]采用贝叶斯方法预测目的地。Ziebart等[2]和Rathore等[3]设计了基于马尔科夫的预测模型。Phithakkitnukoon等[4]使用出租车的时间日期和天气数据计算出租车出现的概率。这些预测方法便于计算，但当数据集噪声过大或过于稀疏时，准确率会大大降低。

随着深度学习技术的发展，也开始有研究将深度学习应用到出租车目的地预测中。Zhang等[5]用DBN(Deep Belief Network)改进了一个集成学习模型，以提高模型预测效果。Rossi等[6]和Xu等[7]等采用RNN(Recurrent Neural Network)模拟出租车司机的行为进行预测。Lü等[8]将轨迹转化为二维图像，并采用CNN (Convolutional Neural Networks)实现精确预测。Besse等[9]提出一种基于初始部分轨迹来预测车辆行程最终目的地的新方法。以上预测方法都可以取得不错的预测效果，但这些方法的重心多集中在神经网络的变换应用中，忽略了轨迹时空特征，造成轨迹时空信息缺失。

国内研究中，孙红等[10]使用聚类隐马尔可夫模型预测轨迹点。季学武等[11]和李明晓等[12]都是基于LSTM(Long Short-Term Memory)网络来对移动对象轨迹位置进行预测。康科[13]设计了建立分类器的方法,使用经典的MLP(Multi-Layer Perceptron)算法和KNN(K-Nearest Neighbor)算法对测试数据中的轨迹目的地进行了预测。王照生等[14]尝试构建多层感知、双向递归神经网络和记忆网络的模型来预测输出。但是，国内对于出租车目的地的预测研究相对缺乏，叶锋等[15]用回声状态网络算法预测出租车目的地。张国兴等[16]将SDZ(Surprisal-Driven Zoneout)应用于RNN中，提出一种基于SDZ-RNN的出租车目的地预测方法。以上方法同样存在对轨迹数据特征处理不充分的问题。

针对以上问题，本文提出了出租车目的地预测的深度学习方法DLDP(Deep Learning method for taxi Destination Prediction)。该方法首先采用滑动窗口，利用轨迹特征集合的统计量得到轨迹的高层特征。其次，利用自动编码器[17]学习高层特征，生成固定长度的潜在空间表示，得到轨迹的深度特征。最后，将得到的深度特征和原始特征相结合，一同作为LSTM模型的输入来进行最终预测。

2 轨迹深度特征的预测

2.1 出租车目的地预测

出租车目的地预测是根据出租车的相关数据，预测乘客的下车地点。

定义1出租车轨迹数据：T={T1,T2,…,Ti,…,TN}是1组输入数据，N表示轨迹数量。Ti∈T表示1条轨迹，表示为[x1,x2,…,xj,…，xMi]，xj代表第j个轨迹点，Mi代表第i条轨迹的轨迹点个数。xj包含3个元素(xjt,xjla,xjlo)分别代表时间、纬度和经度。

定义2高层特征：序列B={BT1,BT2,…,BTi,…,BTN}经过滑动窗口处理后的输出，同时也是自动编码器的输入，代表轨迹的移动行为特征。BTi=[b1,b2,…,bi,…,bMi],bi为每个窗口提取的特征。

定义3(深度特征Z) 自动编码器学习高层特征后得到深度特征，为1组空间向量。

(1)

其中，xlo和ylo分别表示真实目的地和预测目的地的经度，xla和yla分别代表其纬度，RE=6371 km,km代表地球半径。最终计算出x和y2地的距离,单位为km。

定义5预测的目的地y：模型预测后的输出，包括纬度和经度(xla，ylo)2个元素。

2.2 本文方法框架

DLDP预测方法框架如图1所示。

Figure 1 Framework of DLDP图1 DLDP方法框架

主要包括以下步骤：

(1)利用滑动窗口，计算连续2个点的速度和转角，提取轨迹的移动规律，得到轨迹的高层特征。

(2)使用自动编码器来学习提取的高层特征序列，生成固定长度的轨迹深度特征空间表示，减少时空信息缺失带来的预测误差。

(3)在原始轨迹序列中，分别取每条轨迹的前k个和后k个轨迹点，每个轨迹经过自动编码器生成的Z和2k个轨迹点一同作为LSTM模型的输入。经过Softmax层得到对应聚类点的概率分布，计算对轨迹目的地聚类点和目的地点的概率分布的乘积的累加和，得到预测目的地。

3 轨迹深度特征抽取

3.1 轨迹高层特征提取

原始轨迹不包含轨迹的时空特征，导致轨迹序列信息缺失，为此本文计算轨迹高层特征，以弥补原始序列的信息缺失。

将轨迹序列放入滑动窗口，窗口的偏移量设为窗口大小的一半。根据2个连续记录点xi,xi+1计算每个点的速度和转角。然后提取轨迹的移动规律，包括时间的变化Δti、位置的变化Δli、速度的变化Δsi和转角的变化Δri。得到R条记录的移动规律特征(Δt,Δl,Δs,Δr)。之后进一步计算这些特征的变化率。得到特征fi=(fΔli,fΔsi,fΔri)，分别代表平均速度fΔli=Δli/Δti，速度的变化fΔsi=Δsi,转角的变化fΔri=Δri。最终每个窗口得到1条轨迹的特征集f，用f的6个统计量即最大值、最小值、均值、上四分位数、中位数和下四分位数来计算每个窗口的特征，得到3×6=18维的特征b。所有b的集合就成为一条轨迹的移动行为特征序列BTi。然后对每条轨迹的特征序列进行归一化，形成集合B。

3.2 自动编码器学习深度特征

为了得到轨迹深度特征，利用自编码器强大的无监督学习能力来学习高层特征，得到轨迹深度特征的空间向量表示。

因数据存在一定的顺序依赖性，在训练时RNN很难学习具有长期依赖的序列，因此使用LSTM来解决这个问题，本文中自动编码器的编码器和解码器部分都是使用LSTM模型。如图1所示自编码模块的左边部分是编码器，右边是解码器。编码器按序列BTi输入顺序更新隐藏层，如式(2)所示。

ho=fLSTM(ho-1,bo)

(2)

其中，o表示模型内部迭代次数。

最后，隐藏层的输出ho将代表整个序列。之后，把ho作为解码器LSTM的初始隐藏层,得到第1个输出c1，更进一步得到输出{c2,c3,…,co}。此过程解码器LSTM的隐藏层更新如式(3)所示：

(3)

4 基于LSTM的轨迹预测

深度特征减少了轨迹空间信息缺失情况，并将轨迹序列表示成空间向量。将原始特征和深度特征相结合，尽可能地实现了轨迹特征表示。因轨迹序列存在一定的顺序依赖性，本文选择LSTM模型进行训练。在处理原始轨迹序列时，已有研究表明轨迹的中间序列对预测结果影响不大。故本文提取每条轨迹的前k和后k个轨迹点，每个轨迹点包含经度和纬度2个元素，作为轨迹的地理信息。

将深层特征进行嵌入并与位置信息结合起来得到的矩阵作为LSTM模型的输入。LSTM根据其输入门、遗忘门和输出门之间的控制来决定细胞状态的保留情况，保留依赖性强的数据之间的关系，解决长期依赖性问题。最终隐藏层的输出如式(4)所示。

(4)

其中，W为运行中模型的权重，Em是轨迹的特征表示。

另一方面，出租车目的地分布在城市各处，过于广泛，在预测之前，对目的地进行聚类以解决数据稀疏性问题。本文采用Mean-Shift聚类算法对所有轨迹的目的地进行聚类，得到聚类轨迹簇CLi。LSTM层的输出经过Softmax函数生成轨迹目的地聚类分布Pi，对轨迹目的地聚类点和目的地点的概率分布进行对应元素相乘并累加，得到轨迹目的地的预测目的地yi，主要过程如式(5)和式(6)所示。

(5)

(6)

其中,c代表Mean-Shfit聚类算法得到的轨迹簇的个数，yi是最终预测的目的地点。

5 实验及结果分析

5.1 实验数据和环境

本次实验采用波尔图出租车轨迹数据集。该数据集包含了2013/7/1到2014/6/30期间在波尔图采集的442辆出租车轨迹数据，通过预处理后共得到146 844条轨迹数据。

实验程序采用Python 2.7编写，并且使用深度学习库keras 2.2.1和深度学习框架Tensorflow 1.3.实验操作系统为Ubuntu 16.04，硬件环境采用CPU 8核，Intel(R)Xeon(R)Gold 5117 CPU @ 2.00 GHz,内存32 GB。

5.2 实验内容

为了说明本文方法的优势，与普通RNN和LSTM模型进行对比。选用平均距离误差ADE(Average Distance Error)和预测准确率作为评价标准，如果1条轨迹的预测和真实距离误差小于3 km,则认为预测准确。

为了证明深度特征在出租车目的地预测中的有用性，进行了3次对比实验：

(1)与文献[18]中直接使用RNN模型进行预测的方法做对比，在RNN模型参数相同的情况下，将文献[18]的方法和添加深度特征的方法(ARNN)做对比，得到1组准确率和ADE。

(2)将(1)中的RNN模型更换为LSTM，再比较方法预测的准确率和ADE。

(3)比较DLDP方法和(1)、(2)中胜出方法的预测准确率和ADE。

5.3 实验结果分析

图2所示为各个预测方法的预测准确率。

Figure 2 Accuracy comparison图2 准确率比较

使用LSTM和RNN进行预测，其准确率相差不大。ARNN与ALSTM与其对应的RNN和LSTM相比准确率有一定提升。文献[18]中的RNN模型预测准确率为61%；ARNN方法的最大准确率为70.48%；而DLDP方法的预测准确率最高，为80.11%，相比ARNN提高了9.63%。

可以看出，本文方法在准确率上一直高于其他对比模型，在迭代次数为800时，DLDP方法趋于稳定。

平均距离误差比较如图3所示。在图3a中，使用RNN模型直接进行预测的平均距离误差最低为3.14 km，使用自动编码器提取特征后再使用RNN模型进行预测的平均距离误差为2.3 km。相比ARNN模型,平均距离误差减少了0.84 km。图3b显示使用LSTM模型进行预测时，平均距离误差最低为2.8 km，ALSTM模型的最低平均距离误差为2.13 km，相比之下，ALSTM模型的距离误差减少了0.67 km。这是因为使用自动编码器可以提取轨迹信息中的特征信息并转换成空间向量表示，从而使模型预测更加准确。

由图4可知DLDP模型的平均距离误差为1.8 km，相比ARNN和ALSTM分别减少了0.5 km和0.33 km。所有预测方法的平均距离误差如表1所示。

Figure 3 ADE comparison图3 ADE比较

Figure 4 ADE comparison of 3 models图4 3种模型ADE比较

表1 不同方法的平均距离误差

从以上实验可以看出，DLDP方法在预测时，在平均距离误差和预测准确率上有明显优势。

6 结束语

本文方法主要应用于城市交通预测，正确地预测出租车目的地可以使出租车调度中心掌握出租车的流向，合理有效发布调度指令。本文提出的DLDP方法利用深度学习方法提取轨迹特征，来提高预测准确率。该方法首先采用滑动窗口，计算窗口内每个轨迹点的速度和转角的变化，根据数据的统计量得到轨迹的高层特征。然后，通过自动编码器学习得到轨迹的深度特征。最后，将轨迹原始特征和学习后的深度特征一同作为LSTM模型的输入进行最终预测。实验表明，本文方法可有效提取轨迹数据的深度特征，提高出租车目的地预测的准确率。但是，由于数据量过大，本文方法学习时间较长，数据稀疏也会影响其预测准确率。