宋傳東 李亞東 徐麗

摘要：近年來，隨著城市化進(jìn)程的加快，城市中的出租車數(shù)量越來越多，并且由于出租車的特殊性，一直活躍在城市路網(wǎng)中，在城市交通流中占比較大。準(zhǔn)確地預(yù)測出租車目的地，并合理地調(diào)度出租車，對城市交通管理、合理利用交通資源有重要的意義。出租車目的地預(yù)測中一直存在著長期依賴問題，即軌跡序列的預(yù)測結(jié)果與依賴前面點(diǎn)的距離較長，較長的距離使得在反向傳播的過程中，容易產(chǎn)生梯度消失或梯度爆炸，使得誤差較大。為了更有效地解決長期依賴問題，文章采用樹形存儲(chǔ)模塊（Tree Memory Module） 來增強(qiáng)LSTM，并將增強(qiáng)的LSTM應(yīng)用于出租車出行目的地預(yù)測。通過實(shí)驗(yàn)證明，TMM-LSTM相比較LSTM，預(yù)測精度能提升約6%。

關(guān)鍵詞：GPS軌跡;目的地預(yù)測;樹形存儲(chǔ)模塊;LSTM

中圖分類號：TP389.1? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2022）25-0033-04

開放科學(xué)（資源服務(wù)） 標(biāo)識碼（OSID） ：

隨著移動(dòng)設(shè)備的普及和全球定位系統(tǒng)（Global Positioning System） GPS的成熟，城市中許多出租車都搭載了GPS，出租車在運(yùn)行過程中產(chǎn)生了大量的GPS軌跡數(shù)據(jù)。軌跡數(shù)據(jù)包含的軌跡點(diǎn)按照時(shí)間順序進(jìn)行排列，近似表示出租車的運(yùn)行軌跡，這也使預(yù)測出租車軌跡目的地成為可能。已知出租車運(yùn)行的部分軌跡來預(yù)測出租車此次行駛的終點(diǎn)，即目的地預(yù)測。準(zhǔn)確預(yù)測出租車軌跡目的地對于城市交通合理規(guī)劃起著至關(guān)重要的作用[1-3]。

出租車目的地預(yù)測方法多種多樣，并且該研究廣受關(guān)注。2015年ECML/PKDD會(huì)議舉辦了出租車目的地預(yù)測挑戰(zhàn)。在這次競賽中，de Brébisson A等人[4]采用MLP（multi-layer perception） 模型進(jìn)行出租車軌跡目的地預(yù)測，該方法將軌跡數(shù)據(jù)與出租車運(yùn)行時(shí)產(chǎn)生的元數(shù)據(jù)融合，按時(shí)間順序輸入模型中，加強(qiáng)了軌跡點(diǎn)之間的聯(lián)系，通過聚類和分類來挖掘軌跡點(diǎn)之間隱藏的特征，進(jìn)而利用這種隱藏特征實(shí)現(xiàn)對應(yīng)軌跡的目的地預(yù)測;Endo Y[5]等將軌跡數(shù)據(jù)表示為網(wǎng)格空間中的離散特征，并將網(wǎng)格序列傳入RNN（循環(huán)神經(jīng)網(wǎng)絡(luò)） 中，預(yù)測下一個(gè)時(shí)間點(diǎn)的轉(zhuǎn)換概率，以此來進(jìn)行目的地預(yù)測;Yu等人[6]采用DCNN（深層卷積神經(jīng)網(wǎng)絡(luò)） 和LSTM（長短期記性模型） 進(jìn)行出租車目的地預(yù)測，文中同樣將出租車運(yùn)行時(shí)產(chǎn)生的元數(shù)據(jù)作為軌跡數(shù)據(jù)的補(bǔ)充，并使用DCNN來捕捉交通數(shù)據(jù)間的空間屬性特征;張國興等人[7]將Surprisal-Driven Zoneout[8]用于改進(jìn)LSTM單元，從而改進(jìn)了RNN模型，概率化舍棄或保留神經(jīng)元狀態(tài)在隱藏層的傳輸，以此保證正確狀態(tài)的傳輸;Li等人[9]基于LSTM，將提取的深度時(shí)空特征和原始軌跡結(jié)合，預(yù)測出行目的地;Jun Xu等人[10]使用LSTM預(yù)測紐約市不同區(qū)域的出租車需求，因?yàn)長STM能夠通過一個(gè)單元（cell） 保存軌跡之間的長期依賴狀態(tài)，并通過門（gate） 控制，以此解決長期依賴問題，該方法的預(yù)測誤差較小。

雖然上述方法能夠取得較好的預(yù)測準(zhǔn)確率，但是僅適用于較短的軌跡序列，對于較長的軌跡序列間的深層關(guān)聯(lián)并沒有很好的處理能力，無法解決軌跡序列建模中存在的長期依賴問題，即軌跡序列的預(yù)測結(jié)果與依賴前面點(diǎn)的距離較長，較長的距離使得在反向傳播的過程中，容易產(chǎn)生梯度消失或梯度爆炸，使得誤差較大。準(zhǔn)確合理地解決出租車軌跡建模中的長期依賴問題，對預(yù)測的結(jié)果準(zhǔn)確率提升有重要影響。而LSTM雖然可以在一定程度上解決軌跡序列中的長期依賴，但是如果序列很長，反向傳播過程中也會(huì)因?yàn)榫嚯x過長產(chǎn)生較大的偏差。為了更有效地解決長期依賴問題，本文采用樹形存儲(chǔ)模塊（Tree Memory Module） 來增強(qiáng)LSTM，并將增強(qiáng)的LSTM應(yīng)用于出租車出行目的地的預(yù)測。

1 相關(guān)工作

1.1 樹形存儲(chǔ)模塊

樹形存儲(chǔ)模塊結(jié)構(gòu)如圖1所示，從圖1中可以看到，父結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，并且可以通過子結(jié)點(diǎn)獲取下一層的信息，因?yàn)槭菢湫谓Y(jié)構(gòu)，使當(dāng)前結(jié)點(diǎn)和歷史結(jié)點(diǎn)的相隔層數(shù)變得更少，所以父結(jié)點(diǎn)可以更好地映射歷史信息。從圖中可以看到，存儲(chǔ)模塊可以根據(jù)輸入[ci]生成對應(yīng)的[zi]，[zi]為存儲(chǔ)模塊中與[ci]最相關(guān)的記憶單元。存儲(chǔ)模塊由S-LSTM構(gòu)成，它將LSTM中的一般順序結(jié)構(gòu)拓展成自上而下的樹形結(jié)構(gòu)，如圖1中，本文將S-LSTM結(jié)構(gòu)表示為二叉樹，即每個(gè)父結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)，實(shí)現(xiàn)了軌跡序列輸入之間長距離交互的辦法，優(yōu)化了LSTM模型處理長序列的問題。

一個(gè)S-LSTM的結(jié)構(gòu)如圖2所示，[fLn，fRn，in，on]各自表示左遺忘門、右遺忘門、輸入門和輸出門，[?]表示乘法。

在訓(xùn)練的過程中，存儲(chǔ)結(jié)構(gòu)的記憶更新是非常重要的。由圖2可以看出，隱藏的兩個(gè)子結(jié)點(diǎn)，[hLt-1、hRt-1]為左結(jié)點(diǎn)和右結(jié)點(diǎn)的輸出，這兩個(gè)子結(jié)點(diǎn)會(huì)作為當(dāng)前結(jié)點(diǎn)的輸入。輸入門[it]的輸入有四個(gè)：隱藏的向量（[hLt-1，hRt-1]） 和兩個(gè)子結(jié)點(diǎn)的單元向量（[cLt-1，cRt-1]） 。這四個(gè)參數(shù)同樣是左遺忘門[fLt-1]和右遺忘門[fRt-1]的輸入，用于產(chǎn)生門信號。左側(cè)和右側(cè)的遺忘門可以分別控制，允許從子結(jié)點(diǎn)向上傳遞信息。輸出門[ot]需要考慮隱藏層的子結(jié)點(diǎn)向量和當(dāng)前的記憶單元向量。通過這種方法，記憶單元通過遺忘門合并子結(jié)點(diǎn)可以直接和間接地影響多個(gè)子單元。因此，可以提取到結(jié)構(gòu)上的遠(yuǎn)距離的相互關(guān)系。在時(shí)間序列t時(shí)，存儲(chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)中的單元信息和門控信息的更新方式按照公式（1） 至公式（7）：

[it=σ（WLhihLt-1+WRhihRt-1+WLcicLt-1+WRcicRt-1）]? ?（1）

[fLt=σ（WLhflhLt-1+WRhflhRt-1+WLcflcLt-1+WRcflcRt-1）]? （2）

[fRt=σ（WLhfrhLt-1+WRhfrhRt-1+WLcfrcLt-1+WRcfrcRt-1），]? （3）

[xt=WLhchLt-1+WRhchRt-1]? ? ? ? ? （4）

[ct=fLi?cLt-1+fRi?cRt-1+it?tanhxt，]? ? （5）

[ot=σWLhohLt-1+WRhohRt-1+WPcoct，]? ? ? ? ? ? ? ? ? ? ? （6）

[ht=ot?tanh （ct）]。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7）

其中[σ]是sigmoid函數(shù)，用于將門信號限制在[0，1]之間;[fL]與[fR]分別代表左遺忘門和右遺忘門;W是網(wǎng)絡(luò)權(quán)重矩陣;U表示一個(gè)Hadamard積。權(quán)重矩陣[W]的下標(biāo)表示他們用于映射哪個(gè)向量到哪個(gè)門，比如，[Who]是一個(gè)映射隱藏向量到輸出門的矩陣。

在LSTM的重復(fù)模型中，當(dāng)序列變得太長時(shí)，輸出會(huì)偏向于最近的歷史狀態(tài)，而不是同等地考慮整個(gè)歷史狀態(tài)[11]。上述結(jié)構(gòu)中，用樹狀結(jié)構(gòu)表示內(nèi)存，使不同抽象級別的相鄰內(nèi)存單元之間保持了邏輯一致性，并成功地將相鄰區(qū)域的重要特征傳遞給上一層。

1.2 問題定義

出租車目的地預(yù)測就是基于采集到的出租車軌跡數(shù)據(jù)和其他數(shù)據(jù)，預(yù)測出租車行駛的目的地，本文中進(jìn)行如下定義：

預(yù)測目的地[Df]：預(yù)測目的地是模型通過輸入的軌跡序列對應(yīng)得出的預(yù)測結(jié)果，預(yù)測結(jié)果也是一個(gè)GPS點(diǎn)，即[Df=lon，lat]。

半正矢距離[DH]：半正矢距離是地球上的兩個(gè)坐標(biāo)點(diǎn)之間的實(shí)際距離，這兩個(gè)點(diǎn)都是由經(jīng)緯度的坐標(biāo)來表示。半正矢距離可以表示預(yù)測目的地[Df]和真實(shí)目的地[Dt]之間的距離，計(jì)算方法定義如公式（8） 所示：

[DHDf，Dt=2Rarctan（a（Df，Dt）aDf，Dt-1）]? ?（8）

其中[a（Df，Dt）]定義如公式（9） 所示：

[a（Df，Dt）=sin2lat2-lat12+coslat1cos （lat2）sin2（lon2-lon12）]? ? （9）

其中[lat1，lon1，lat2，lon2]分別是[Df]和[Dt]的經(jīng)緯度坐標(biāo)，R為地球半徑，值為6371km，計(jì)算得出半正矢距離[DH]，單位為km。

平均距離誤差[Qprepp]：計(jì)算測試集中對應(yīng)各條軌跡的預(yù)測目的地[Df]和實(shí)際目的地[Dt]之間的半正矢距離，并取平均值。計(jì)算過程如公式（10） 所示。

[Qprepp=∑X∈YDH（Df，Dt）γ]? ? ? （10）

其中，X代表測試集中的某條軌跡，Y代表整個(gè)測試集，[DH]為預(yù)測目的地和真實(shí)目的地間的半正矢距離，[γ]代表測試集中軌跡的數(shù)量。

預(yù)測準(zhǔn)確率[Pac]。本文設(shè)定當(dāng)預(yù)測目的地[Df]和真實(shí)目的地[Dt]之間的距離[DH]小于1km時(shí)則為預(yù)測正確，否則為預(yù)測失敗。計(jì)算公式定義如（11） 所示：

[Pac=∑X∈Y（Dh<1）γ×100%]? ? ? ? ?（11）

其中[γ]為測試數(shù)據(jù)集中軌跡的數(shù)量。

2 基于TMM-LSTM目的地預(yù)測方法

為了更好地捕捉軌跡點(diǎn)間的長期關(guān)系，從而解決出租車軌跡間的長期依賴問題，本文采用了具有樹形存儲(chǔ)模塊的LSTM模型（TMM-LSTM） 來進(jìn)行出租車目的地的預(yù)測，通過增加一個(gè)外部的樹形存儲(chǔ)模塊，可以更好地捕捉并處理軌跡間的長期關(guān)系，以提升模型的預(yù)測準(zhǔn)確率。

在圖3中，第一步：軌跡序列[Xi]和軌跡相關(guān)的元數(shù)據(jù)信息結(jié)合作為輸入數(shù)據(jù)[Ai]，如公式（12） 所示。元數(shù)據(jù)是波爾圖出租車數(shù)據(jù)集在采集行駛數(shù)據(jù)時(shí)采集到的其他和駕駛相關(guān)的數(shù)據(jù)，包括出租車編號、用戶編號，上車的時(shí)間點(diǎn)等信息。本文選取出租車軌跡序列中的前[k]個(gè)點(diǎn) {[x1，x2，…，x5， xk]}和后[k]個(gè)點(diǎn){[xT-k，xT-k+1，…，xT-1，xT]}，每個(gè)點(diǎn)包含經(jīng)緯度，即[xt=（lon，lat）]，這樣共得到2k個(gè)點(diǎn)，也就是有4k個(gè)數(shù)值。在此次實(shí)驗(yàn)中，本文設(shè)定k=6，所以輸入模塊的維度為30（6*2*2+6） ，其中前后各6個(gè)點(diǎn)，加上6個(gè)軌跡相關(guān)的元數(shù)據(jù)，其中前24個(gè)為經(jīng)緯度坐標(biāo)（前12個(gè)點(diǎn)為緯度坐標(biāo)，后12個(gè)點(diǎn)為經(jīng)度坐標(biāo)） 。

[Ai={Xi，ClientId，TaxiId，StandId…}]? ? ?（12）

第二步：通過一個(gè)LSTM層，將當(dāng)前的輸入生成一個(gè)可以表示當(dāng)前輸入的中間變量[ci]，如公式（13） ：

[ci=fLSTM（Ai）]? ? ? ? （13）

第三步：將[ci]作為存儲(chǔ)結(jié)構(gòu)的輸入，通過[fscore]注意力得分函數(shù)， 計(jì)算出當(dāng)前輸入和存儲(chǔ)結(jié)構(gòu)的相關(guān)性得分[mi]，其中[Mt-1∈Rk×（2l-1）]，是從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的鄰接矩陣，可以表示當(dāng)前存儲(chǔ)結(jié)構(gòu)的狀態(tài)，其中k表示隱藏層嵌入維度，[l]為樹形記憶結(jié)構(gòu)的深度（二叉樹的樹高） 。得分函數(shù)定義為公式（14） 、公式（15） ：

[mi=fscoreMt-1，ci]? ? （14）

[fscoreMt-1，ci=cΤiMt-1]? ? （15）

通過公式（16） 公式（17） ，本文得到存儲(chǔ)結(jié)構(gòu)中和當(dāng)前輸入最相關(guān)的記憶單元。

[α=softmax（mi）.]? ? ? ? ? （16）

[zi=Mt-1αT]? ? ? ? ? ? ?（17）

第四步：本文將[ci]與[zi]，按照公式（18） 進(jìn)行處理，按照權(quán)重融合，并通過ReLU函數(shù)得出預(yù)測目的地[Dfi]，其中[Wout]為權(quán)重。

[Dfi=Relu（Woutzi+（1-Woutci））]? ? ? ?（18）

3 實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)及數(shù)據(jù)預(yù)處理

本文采用的數(shù)據(jù)集是波爾圖出租車軌跡數(shù)據(jù)，該數(shù)據(jù)集是在2013-07-01到2014-06-30期間，在波爾圖市采集到的442輛出租車的軌跡數(shù)據(jù)。數(shù)據(jù)使用csv格式存儲(chǔ)，保留原始數(shù)據(jù)中的經(jīng)緯度信息和時(shí)間戳信息。

完整的訓(xùn)練集包括170萬條數(shù)據(jù)點(diǎn)集合，每一條代表一個(gè)完整的出租車軌跡。每一條完整的出租車軌跡由一系列間隔15秒的GPS點(diǎn)和采取到第一個(gè)點(diǎn)的時(shí)間戳，后面的采樣點(diǎn)時(shí)間戳一次加上15秒，最后一個(gè)GPS點(diǎn)代表目的地，并且不同的軌跡，GPS點(diǎn)的長度也是不同的。

3.2 實(shí)驗(yàn)分析

表1為不同模型在測試集的預(yù)測結(jié)果，平均距離誤差的單位是千米。由表1中可以看出，TMM-LSTM模型有著最好的預(yù)測結(jié)果，預(yù)測誤差比RNN和LSTM都要低不少，并且TMM-LSTM要比LSTM的平均半正矢距離低0.16km，預(yù)測效果提升了約6%。

圖4是不同模型在訓(xùn)練過程中平均距離誤差的對比試驗(yàn)結(jié)果。從圖中可以看到，TMM-LSTM和RNN模型在迭代40000次左右就可以達(dá)到近乎于最優(yōu)的預(yù)測結(jié)果，說明TMM-LSTM和RNN模型收斂較快。并且可以看到，TMM-LSTM模型的預(yù)測結(jié)果一直要優(yōu)于其他模型，說明TMM-LSTM模型在出租車目的地預(yù)測上效果更好。

圖5為TMM-LSTM模型預(yù)測準(zhǔn)確率[Pac]與迭代次數(shù)的關(guān)系和RNN、LSTM模型的對比試驗(yàn)結(jié)果。從圖中可以得出，在預(yù)測準(zhǔn)確率的收斂速度上，TMM-LSTM模型表現(xiàn)較好，說明TMM-LSTM模型可以更好地捕捉并處理長期依賴。在預(yù)測準(zhǔn)確率上，TMM-LSTM模型優(yōu)于其他模型，比LSTM模型的預(yù)測準(zhǔn)確率高1%。

圖6為TMM-LSTM、RNN、LSTM的預(yù)測目的地和真實(shí)目的地之間的半正矢距離的分布對比結(jié)果。從圖中可以看到，TMM-LSTM和LSTM模型的預(yù)測目的地和真實(shí)目的地的半正矢距離都集中分布在1.5km以內(nèi)，占比約為70%，這也說明了兩個(gè)模型在出租車目的地預(yù)測上都有較好的表現(xiàn)。TMM-LSTM相比于其他模型，半正矢距離在1.5km以內(nèi)的比重要高出很多，這也說明了，TMM-LSTM模型在更精準(zhǔn)的預(yù)測上表現(xiàn)更好。

4 總結(jié)

本文詳細(xì)地給出TMM-LSTM模型的介紹，給出了TMM-LSTM的理論依據(jù)，并介紹了樹形存儲(chǔ)模塊，使用樹形存儲(chǔ)模塊記憶軌跡點(diǎn)間的長期關(guān)系，增強(qiáng)LSTM模型，并將TMM-LSTM模型應(yīng)用于出租車出行目的地預(yù)測問題中以更好地解決軌跡中存在的長期依賴問題。通過實(shí)驗(yàn)結(jié)果的對比，可以發(fā)現(xiàn)，TMM-LSTM模型相比較于RNN、LSTM有著較大的提升。但是本文在處理軌跡數(shù)據(jù)時(shí)，沒有對其中的噪聲進(jìn)行處理，這也對本文的實(shí)驗(yàn)結(jié)果有一定的影響，后面會(huì)繼續(xù)對此工作進(jìn)行優(yōu)化。

參考文獻(xiàn)：

[1] Zhuang L J，Gong J F，He Z C，et al.Framework of experienced route planning based on taxis' GPS data[C]//2012 15th International IEEE Conference on Intelligent Transportation Systems.Anchorage，AK，USA.IEEE，2012：1026-1031.

[2] 唐爐亮，常曉猛，李清泉，等.基于蟻群優(yōu)化算法與出租車GPS數(shù)據(jù)的公眾出行路徑優(yōu)化[J].中國公路學(xué)報(bào)，2011，24（2）：89-95，126.

[3] Li Q Q，Zeng Z，Yang B S，et al.Hierarchical route planning based on taxi GPS-trajectories[C]//2009 17th International Conference on Geoinformatics.Fairfax，VA，USA.IEEE，2009：1-5.

[4] de Brébisson A，Simon ?，Auvolat A，et al.Artificial neural networks applied to taxi destination prediction[EB/OL].2015：arXiv：1508.00021.https：//arxiv.org/abs/1508.00021.

[5] 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. Springer， Cham， 2017：160-172.

[6] Yu H Y，Wu Z H，Wang S Q，et al.Spatiotemporal recurrent convolutional networks for traffic prediction in transportation networks[J].Sensors （Basel，Switzerland），2017，17（7）：1501.

[7] 張國興，李亞東，張磊，等.基于SDZ-RNN的出租車出行目的地預(yù)測方法[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（6）：143-149.

[8] Rocki K，Kornuta T，Maharaj T.Surprisal-driven zoneout[EB/OL].2016：arXiv：1610.07675.https：//arxiv.org/abs/1610.07675.

[9] Li Y D，Cui S M，Zhang L，et al.Taxi destination prediction with deep spatial-temporal features[C]//2021 International Conference on Communications，Information System and Computer Engineering （CISCE）.Beijing，China.IEEE，2021：562-565.

[10] Xu J，Rahmatizadeh R，B?l?ni L，et al.A sequence learning model with recurrent neural networks for taxi demand prediction[C]//2017 IEEE 42nd Conference on Local Computer Networks.Singapore.IEEE，2017：261-268.

[11] Qian Chen， Xiaodan Zhu， Zhenhua Ling， Si Wei， Hui Jiang， Diana Inkpen. "Enhanced LSTM for Natural Language Inference[C]// In Association for Computational Linguistics （ACL），2017.

【通聯(lián)編輯：唐一東】