出租車目的地預測的深度學習方法*

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

(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模型的輸入進行最終預測。實驗表明，本文方法可有效提取軌跡數據的深度特征，提高出租車目的地預測的準確率。但是，由于數據量過大，本文方法學習時間較長，數據稀疏也會影響其預測準確率。