崔淑敏，張 磊，李 允，邵長興，朱少杰

(1.中國礦業(yè)大學(xué)計算機(jī)學(xué)院，江蘇 徐州 221116;2.礦山數(shù)字化教育部工程研究中心，江蘇 徐州 221116)

1 引言

出租車作為城市交通的重要部分，影響著人們?nèi)粘３鲂校_預(yù)測出租車目的地有重要現(xiàn)實意義。隨著GPS技術(shù)的普及和應(yīng)用，絕大多數(shù)出租車都配有GPS傳感器，可以采集出租車的實時位置，形成軌跡序列。

早期出租車目的地預(yù)測研究多基于概率論，Comaniciu等[1]采用貝葉斯方法預(yù)測目的地。Ziebart等[2]和Rathore等[3]設(shè)計了基于馬爾科夫的預(yù)測模型。Phithakkitnukoon等[4]使用出租車的時間日期和天氣數(shù)據(jù)計算出租車出現(xiàn)的概率。這些預(yù)測方法便于計算，但當(dāng)數(shù)據(jù)集噪聲過大或過于稀疏時，準(zhǔn)確率會大大降低。

隨著深度學(xué)習(xí)技術(shù)的發(fā)展，也開始有研究將深度學(xué)習(xí)應(yīng)用到出租車目的地預(yù)測中。Zhang等[5]用DBN(Deep Belief Network)改進(jìn)了一個集成學(xué)習(xí)模型，以提高模型預(yù)測效果。Rossi等[6]和Xu等[7]等采用RNN(Recurrent Neural Network)模擬出租車司機(jī)的行為進(jìn)行預(yù)測。Lü等[8]將軌跡轉(zhuǎn)化為二維圖像，并采用CNN (Convolutional Neural Networks)實現(xiàn)精確預(yù)測。Besse等[9]提出一種基于初始部分軌跡來預(yù)測車輛行程最終目的地的新方法。以上預(yù)測方法都可以取得不錯的預(yù)測效果，但這些方法的重心多集中在神經(jīng)網(wǎng)絡(luò)的變換應(yīng)用中，忽略了軌跡時空特征，造成軌跡時空信息缺失。

國內(nèi)研究中，孫紅等[10]使用聚類隱馬爾可夫模型預(yù)測軌跡點。季學(xué)武等[11]和李明曉等[12]都是基于LSTM(Long Short-Term Memory)網(wǎng)絡(luò)來對移動對象軌跡位置進(jìn)行預(yù)測?？悼芠13]設(shè)計了建立分類器的方法,使用經(jīng)典的MLP(Multi-Layer Perceptron)算法和KNN(K-Nearest Neighbor)算法對測試數(shù)據(jù)中的軌跡目的地進(jìn)行了預(yù)測。王照生等[14]嘗試構(gòu)建多層感知、雙向遞歸神經(jīng)網(wǎng)絡(luò)和記憶網(wǎng)絡(luò)的模型來預(yù)測輸出。但是，國內(nèi)對于出租車目的地的預(yù)測研究相對缺乏，葉鋒等[15]用回聲狀態(tài)網(wǎng)絡(luò)算法預(yù)測出租車目的地。張國興等[16]將SDZ(Surprisal-Driven Zoneout)應(yīng)用于RNN中，提出一種基于SDZ-RNN的出租車目的地預(yù)測方法。以上方法同樣存在對軌跡數(shù)據(jù)特征處理不充分的問題。

針對以上問題，本文提出了出租車目的地預(yù)測的深度學(xué)習(xí)方法DLDP(Deep Learning method for taxi Destination Prediction)。該方法首先采用滑動窗口，利用軌跡特征集合的統(tǒng)計量得到軌跡的高層特征。其次，利用自動編碼器[17]學(xué)習(xí)高層特征，生成固定長度的潛在空間表示，得到軌跡的深度特征。最后，將得到的深度特征和原始特征相結(jié)合，一同作為LSTM模型的輸入來進(jìn)行最終預(yù)測。

2 軌跡深度特征的預(yù)測

2.1 出租車目的地預(yù)測

出租車目的地預(yù)測是根據(jù)出租車的相關(guān)數(shù)據(jù)，預(yù)測乘客的下車地點。

定義1出租車軌跡數(shù)據(jù)：T={T1,T2,…,Ti,…,TN}是1組輸入數(shù)據(jù)，N表示軌跡數(shù)量。Ti∈T表示1條軌跡，表示為[x1,x2,…,xj,…，xMi]，xj代表第j個軌跡點，Mi代表第i條軌跡的軌跡點個數(shù)。xj包含3個元素(xjt,xjla,xjlo)分別代表時間、緯度和經(jīng)度。

定義2高層特征：序列B={BT1,BT2,…,BTi,…,BTN}經(jīng)過滑動窗口處理后的輸出，同時也是自動編碼器的輸入，代表軌跡的移動行為特征。BTi=[b1,b2,…,bi,…,bMi],bi為每個窗口提取的特征。

定義3(深度特征Z) 自動編碼器學(xué)習(xí)高層特征后得到深度特征，為1組空間向量。

(1)

其中，xlo和ylo分別表示真實目的地和預(yù)測目的地的經(jīng)度，xla和yla分別代表其緯度，RE=6371 km,km代表地球半徑。最終計算出x和y2地的距離,單位為km。

定義5預(yù)測的目的地y：模型預(yù)測后的輸出，包括緯度和經(jīng)度(xla，ylo)2個元素。

2.2 本文方法框架

DLDP預(yù)測方法框架如圖1所示。

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

主要包括以下步驟：

(1)利用滑動窗口，計算連續(xù)2個點的速度和轉(zhuǎn)角，提取軌跡的移動規(guī)律，得到軌跡的高層特征。

(2)使用自動編碼器來學(xué)習(xí)提取的高層特征序列，生成固定長度的軌跡深度特征空間表示，減少時空信息缺失帶來的預(yù)測誤差。

(3)在原始軌跡序列中，分別取每條軌跡的前k個和后k個軌跡點，每個軌跡經(jīng)過自動編碼器生成的Z和2k個軌跡點一同作為LSTM模型的輸入。經(jīng)過Softmax層得到對應(yīng)聚類點的概率分布，計算對軌跡目的地聚類點和目的地點的概率分布的乘積的累加和，得到預(yù)測目的地。

3 軌跡深度特征抽取

3.1 軌跡高層特征提取

原始軌跡不包含軌跡的時空特征，導(dǎo)致軌跡序列信息缺失，為此本文計算軌跡高層特征，以彌補(bǔ)原始序列的信息缺失。

將軌跡序列放入滑動窗口，窗口的偏移量設(shè)為窗口大小的一半。根據(jù)2個連續(xù)記錄點xi,xi+1計算每個點的速度和轉(zhuǎn)角。然后提取軌跡的移動規(guī)律，包括時間的變化Δti、位置的變化Δli、速度的變化Δsi和轉(zhuǎn)角的變化Δri。得到R條記錄的移動規(guī)律特征(Δt,Δl,Δs,Δr)。之后進(jìn)一步計算這些特征的變化率。得到特征fi=(fΔli,fΔsi,fΔri)，分別代表平均速度fΔli=Δli/Δti，速度的變化fΔsi=Δsi,轉(zhuǎn)角的變化fΔri=Δri。最終每個窗口得到1條軌跡的特征集f，用f的6個統(tǒng)計量即最大值、最小值、均值、上四分位數(shù)、中位數(shù)和下四分位數(shù)來計算每個窗口的特征，得到3×6=18維的特征b。所有b的集合就成為一條軌跡的移動行為特征序列BTi。然后對每條軌跡的特征序列進(jìn)行歸一化，形成集合B。

3.2 自動編碼器學(xué)習(xí)深度特征

為了得到軌跡深度特征，利用自編碼器強(qiáng)大的無監(jiān)督學(xué)習(xí)能力來學(xué)習(xí)高層特征，得到軌跡深度特征的空間向量表示。

因數(shù)據(jù)存在一定的順序依賴性，在訓(xùn)練時RNN很難學(xué)習(xí)具有長期依賴的序列，因此使用LSTM來解決這個問題，本文中自動編碼器的編碼器和解碼器部分都是使用LSTM模型。如圖1所示自編碼模塊的左邊部分是編碼器，右邊是解碼器。編碼器按序列BTi輸入順序更新隱藏層，如式(2)所示。

ho=fLSTM(ho-1,bo)

(2)

其中，o表示模型內(nèi)部迭代次數(shù)。

最后，隱藏層的輸出ho將代表整個序列。之后，把ho作為解碼器LSTM的初始隱藏層,得到第1個輸出c1，更進(jìn)一步得到輸出{c2,c3,…,co}。此過程解碼器LSTM的隱藏層更新如式(3)所示：

(3)

4 基于LSTM的軌跡預(yù)測

深度特征減少了軌跡空間信息缺失情況，并將軌跡序列表示成空間向量。將原始特征和深度特征相結(jié)合，盡可能地實現(xiàn)了軌跡特征表示。因軌跡序列存在一定的順序依賴性，本文選擇LSTM模型進(jìn)行訓(xùn)練。在處理原始軌跡序列時，已有研究表明軌跡的中間序列對預(yù)測結(jié)果影響不大。故本文提取每條軌跡的前k和后k個軌跡點，每個軌跡點包含經(jīng)度和緯度2個元素，作為軌跡的地理信息。

將深層特征進(jìn)行嵌入并與位置信息結(jié)合起來得到的矩陣作為LSTM模型的輸入。LSTM根據(jù)其輸入門、遺忘門和輸出門之間的控制來決定細(xì)胞狀態(tài)的保留情況，保留依賴性強(qiáng)的數(shù)據(jù)之間的關(guān)系，解決長期依賴性問題。最終隱藏層的輸出如式(4)所示。

(4)

其中，W為運(yùn)行中模型的權(quán)重，Em是軌跡的特征表示。

另一方面，出租車目的地分布在城市各處，過于廣泛，在預(yù)測之前，對目的地進(jìn)行聚類以解決數(shù)據(jù)稀疏性問題。本文采用Mean-Shift聚類算法對所有軌跡的目的地進(jìn)行聚類，得到聚類軌跡簇CLi。LSTM層的輸出經(jīng)過Softmax函數(shù)生成軌跡目的地聚類分布Pi，對軌跡目的地聚類點和目的地點的概率分布進(jìn)行對應(yīng)元素相乘并累加，得到軌跡目的地的預(yù)測目的地yi，主要過程如式(5)和式(6)所示。

(5)

(6)

其中,c代表Mean-Shfit聚類算法得到的軌跡簇的個數(shù)，yi是最終預(yù)測的目的地點。

5 實驗及結(jié)果分析

5.1 實驗數(shù)據(jù)和環(huán)境

本次實驗采用波爾圖出租車軌跡數(shù)據(jù)集。該數(shù)據(jù)集包含了2013/7/1到2014/6/30期間在波爾圖采集的442輛出租車軌跡數(shù)據(jù)，通過預(yù)處理后共得到146 844條軌跡數(shù)據(jù)。

實驗程序采用Python 2.7編寫，并且使用深度學(xué)習(xí)庫keras 2.2.1和深度學(xué)習(xí)框架Tensorflow 1.3.實驗操作系統(tǒng)為Ubuntu 16.04，硬件環(huán)境采用CPU 8核，Intel(R)Xeon(R)Gold 5117 CPU @ 2.00 GHz,內(nèi)存32 GB。

5.2 實驗內(nèi)容

為了說明本文方法的優(yōu)勢，與普通RNN和LSTM模型進(jìn)行對比。選用平均距離誤差A(yù)DE(Average Distance Error)和預(yù)測準(zhǔn)確率作為評價標(biāo)準(zhǔn)，如果1條軌跡的預(yù)測和真實距離誤差小于3 km,則認(rèn)為預(yù)測準(zhǔn)確。

為了證明深度特征在出租車目的地預(yù)測中的有用性，進(jìn)行了3次對比實驗：

(1)與文獻(xiàn)[18]中直接使用RNN模型進(jìn)行預(yù)測的方法做對比，在RNN模型參數(shù)相同的情況下，將文獻(xiàn)[18]的方法和添加深度特征的方法(ARNN)做對比，得到1組準(zhǔn)確率和ADE。

(2)將(1)中的RNN模型更換為LSTM，再比較方法預(yù)測的準(zhǔn)確率和ADE。

(3)比較DLDP方法和(1)、(2)中勝出方法的預(yù)測準(zhǔn)確率和ADE。

5.3 實驗結(jié)果分析

圖2所示為各個預(yù)測方法的預(yù)測準(zhǔn)確率。

Figure 2 Accuracy comparison圖2 準(zhǔn)確率比較

使用LSTM和RNN進(jìn)行預(yù)測，其準(zhǔn)確率相差不大。ARNN與ALSTM與其對應(yīng)的RNN和LSTM相比準(zhǔn)確率有一定提升。文獻(xiàn)[18]中的RNN模型預(yù)測準(zhǔn)確率為61%；ARNN方法的最大準(zhǔn)確率為70.48%；而DLDP方法的預(yù)測準(zhǔn)確率最高，為80.11%，相比ARNN提高了9.63%。

可以看出，本文方法在準(zhǔn)確率上一直高于其他對比模型，在迭代次數(shù)為800時，DLDP方法趨于穩(wěn)定。

平均距離誤差比較如圖3所示。在圖3a中，使用RNN模型直接進(jìn)行預(yù)測的平均距離誤差最低為3.14 km，使用自動編碼器提取特征后再使用RNN模型進(jìn)行預(yù)測的平均距離誤差為2.3 km。相比ARNN模型,平均距離誤差減少了0.84 km。圖3b顯示使用LSTM模型進(jìn)行預(yù)測時，平均距離誤差最低為2.8 km，ALSTM模型的最低平均距離誤差為2.13 km，相比之下，ALSTM模型的距離誤差減少了0.67 km。這是因為使用自動編碼器可以提取軌跡信息中的特征信息并轉(zhuǎn)換成空間向量表示，從而使模型預(yù)測更加準(zhǔn)確。

由圖4可知DLDP模型的平均距離誤差為1.8 km，相比ARNN和ALSTM分別減少了0.5 km和0.33 km。所有預(yù)測方法的平均距離誤差如表1所示。

Figure 3 ADE comparison圖3 ADE比較

Figure 4 ADE comparison of 3 models圖4 3種模型ADE比較

表1 不同方法的平均距離誤差

從以上實驗可以看出，DLDP方法在預(yù)測時，在平均距離誤差和預(yù)測準(zhǔn)確率上有明顯優(yōu)勢。

6 結(jié)束語

本文方法主要應(yīng)用于城市交通預(yù)測，正確地預(yù)測出租車目的地可以使出租車調(diào)度中心掌握出租車的流向，合理有效發(fā)布調(diào)度指令。本文提出的DLDP方法利用深度學(xué)習(xí)方法提取軌跡特征，來提高預(yù)測準(zhǔn)確率。該方法首先采用滑動窗口，計算窗口內(nèi)每個軌跡點的速度和轉(zhuǎn)角的變化，根據(jù)數(shù)據(jù)的統(tǒng)計量得到軌跡的高層特征。然后，通過自動編碼器學(xué)習(xí)得到軌跡的深度特征。最后，將軌跡原始特征和學(xué)習(xí)后的深度特征一同作為LSTM模型的輸入進(jìn)行最終預(yù)測。實驗表明，本文方法可有效提取軌跡數(shù)據(jù)的深度特征，提高出租車目的地預(yù)測的準(zhǔn)確率。但是，由于數(shù)據(jù)量過大，本文方法學(xué)習(xí)時間較長，數(shù)據(jù)稀疏也會影響其預(yù)測準(zhǔn)確率。