基于長短期記憶網絡的移動軌跡目的地預測*

晉廣印,趙旭俊,龔藝璇

(太原科技大學計算機科學與技術學院,山西 太原 030024)

1 引言

隨著嵌入式GPS設備(如手機和智能手表)的普及,基于位置服務和應用LBSA(Location-Based Services and Applications)極大改善了人們的生活體驗,同時這些設備也記錄了海量的軌跡數據,促進了LBSA領域的發展。近幾年,LBSA邁入了一個新的階段,在推薦系統、智能交通系統和智能導航系統等方面起到了不可替代的重要作用[1-3],而這些服務和應用都需要對軌跡的目的地以及未來的路徑進行預測,如何快速準確地預測移動軌跡的目的地逐漸成為眾多學者關注和研究的熱點問題。

現有的軌跡目的地預測方法是將真實軌跡數據抽象為易于處理的抽象表達方式[4],在此基礎上構建合適的預測模型,以實現預測。目的地預測任務的實現需要海量的歷史軌跡作為數據支撐,現實中收集到的軌跡往往不能包含所有可能的查詢軌跡(數據稀疏問題)[5],即由于道路的復雜性導致當前查詢軌跡并不存在于歷史軌跡庫中,或者是當前查詢的前綴軌跡與歷史軌跡庫中的一部分軌跡相似度很高,但目的地卻不相同。現有解決稀疏問題的方法主要包含2類:一類是將軌跡映射到二維平面上,通過調節粒度的方式緩解數據稀疏問題,但是粒度的調節受數據集影響較大,在面對新數據集時實施困難。另一類是將軌跡進行網格劃分,但沒有考慮軌跡網格之間的地理拓撲關系,而不考慮空間因素勢必會降低預測結果的準確性。因此,數據稀疏問題如果不能得到有效的解決,會嚴重影響預測準確性。此外,軌跡數據特征更偏向于序列數據,前綴軌跡點對預測結果的影響是不同的(長期依賴問題),現有的研究工作只關注了前綴軌跡整體對預測結果的影響,而忽略了一些關鍵點。

針對以上問題,本文提出了基于長短期記憶LSTM(Long Short-Term Memory)網絡的移動軌跡目的地預測方法。在軌跡表征方面,提出了軌跡分布式表示方法,通過geohash算法對分段后的軌跡進行網格劃分,之后通過Base2vec模型對劃分后的網格進行訓練,將由二進制表示的網格轉化為具有地理拓撲關系的向量表示。然后對目的地進行聚類,為軌跡添加偽標簽,縮小相似軌跡的差異,放大不相似軌跡的特征,將序列預測問題轉化為序列分類,以克服數據稀疏問題帶來的負面影響。同時提出了基于LSTM網絡的移動軌跡目的地預測模型SATN-LSTM(Self-ATteNtion-LSTM),對LSTM網絡結構進行優化,將自注意力機制引入LSTM網絡中,挖掘序列中的關鍵點并根據其重要程度分配權重,較好地解決了長期依賴問題。

2 相關工作

2.1 數據稀疏問題

數據稀疏問題是目的地預測任務中容易被忽略且較為常見的問題,由于現實中收集到的軌跡遠不能包含所有可能的查詢軌跡,會影響最終的預測精度。造成數據稀疏問題的原因可分為以下2點:(1)現實中收集到的軌跡數據集有限;(2)由于嵌入式GPS設備采樣頻率不同,導致相同的軌跡存在較大的差異。為了解決數據稀疏問題,江婧等人[6]提出了一種基于卷積神經網絡CNN(Convolutio- nal Neural Network)的軌跡目的地預測方法。該方法首先對軌跡進行分段,然后將軌跡序列表示為二維黑白圖像,并為圖像添加標簽,采用卷積神經網絡提取軌跡圖像特征,將目的地預測問題轉化為圖像分類問題。隨后Lü等人[7]在此基礎上對原始軌跡序列進行多粒度分析,并將整個前綴軌跡轉化為圖像,驗證了軌跡起始位置對預測結果具有非常重要的作用。Wang等人[8]通過負抽樣策略對原始數據進行低維表示,利用帶有注意力機制的卷積神經網絡在不同的數據集上也得到了類似的結論。此外,Song等人[9]提出的基于循環神經網絡的方法,在將軌跡進行網格劃分并轉化為向量表示來解決數據稀疏問題時,沒有考慮軌跡點之間的地理拓撲關系。多數目的地預測方法在解決軌跡數據稀疏問題上具有明顯的局限性,對此本文對原始軌跡進行了分段處理,并將分段后的軌跡轉化為軌跡網格表示,采用分布式表示方法,賦予軌跡網格地理拓撲關系,縮小相似軌跡的差異,放大不相似軌跡的特征,以克服數據稀疏問題帶來的負面影響。

2.2 長期依賴問題

長期依賴問題是指目的地預測的準確性不僅僅依賴較近時間的前綴節點,而且對較遠時間的前綴節點具有長期依賴關系,時間較早的前綴軌跡點往往被忽略,這與實際情況不符,且會降低預測的準確性。Zhang等人[10]提出了一種名為數據驅動的集成學習方法來預測目的地,首先確定最可能的未來位置,并通過馬爾科夫轉移矩陣得到2個位置之間的轉移概率,然后通過貝葉斯推理,結合轉移概率來預測目的地,但概率統計學模型具有嚴重的長期依賴問題。Yang等人[11]通過數據嵌入的方法對數據進行降維處理,在特征選擇之前將數據嵌入二維空間,并使用數據驅動的集成學習方法進行移動軌跡的目的地預測,獲得了較好的預測性能。近幾年,以神經網絡為基礎的深度學習技術引起了眾多研究人員和學者的關注,并在軌跡目的地預測任務中得到了廣泛的應用。Xu等人[12]在LSTM網絡結構中引入了時間門和距離門結構,以捕獲連續位置之間的時空關系,但是不相鄰位置之間的關系并沒有考慮。Gui等人[13]提出的一種基于位置語義的注意力感知長短期記憶網絡模型,在LSTM中引入了注意力感知模塊。Rossi等人[14]從司機的角度出發,為司機的行為進行建模,同樣采用了LSTM網絡并加入了注意力機制以緩解軌跡序列的長期依賴性問題,但是傳統的注意力機制參數量大,調整困難。此外,有一種興趣點預測方法與軌跡目的地預測方法類似,興趣點預測是對用戶的歷史興趣點簽到記錄進行信息挖掘,來預測下一個時間片用戶最有可能訪問的位置。Qian等人[15]提出了一種新的基于協作注意力的興趣點預測網絡,該網絡使用了內外軌跡相關性,獲得了較好的預測效果。Huang等人[16]開發了基于自注意力的時空LSTM網絡,使用時空上下文信息選擇性地關注嵌入序列中的相關歷史嵌入記錄,得到了更好的表現。興趣點預測與軌跡目的地預測相比,預測模式相同,即通過對歷史信息的學習來預測未來一段時間內移動對象的目的地。不同之處在于興趣點預測以時間片為單位,關注的是下一個時間片最有可能訪問的位置,也可稱作下一個興趣點推薦。軌跡目的地預測是根據現有未完成的軌跡(前綴軌跡)來預測此次出行的目的地。并且興趣點預測多用于人的軌跡,而軌跡目的地預測多用于網約車的軌跡。本文將自注意力機制引入LSTM網絡中,挖掘軌跡序列中的關鍵點并根據其重要程度分配權重,以解決了長期依賴問題。

3 軌跡數據處理

3.1 相關定義及軌跡數據處理流程

定義1(第k條軌跡Tk的序列表示)Tk={Pk1,Pk2,…,Pkn-1,Pkn},軌跡序列Tk由一系列按時間順序排列的GPS點組成,每個GPS點Pki包含經緯度和時間信息。

定義2(前綴軌跡序列Tf)Tf={Pk1,Pk2,…,Pki}(2

定義3(軌跡網格序列GT) 軌跡點所在的網格稱為該軌跡點的軌跡網格,軌跡網格代替軌跡序列中的所有軌跡點形成的新序列稱為軌跡網格序列GT={G1,G2,…,Gn}。

定義4(軌跡完成比例) 將分段后的軌跡看做完整軌跡序列,前綴軌跡序列占完整軌跡序列的比重,即Tf/Tk,稱作軌跡完成比例。

定義5(軌跡目的地預測) 給定前綴軌跡序列Tf={Pk1,Pk2,…,Pki}(2

軌跡數據處理的整體流程如圖1所示,首先對原始軌跡進行分段處理,詳見3.2節;然后對分段后的軌跡進行網格劃分和分布式表示,詳見3.3和3.4節;最后對訓練集軌跡的目的地進行聚類并添加偽標簽,詳見3.5節。

Figure 1 Overview of trajectory data processing圖1 軌跡數據處理流程

經過處理后,最終得到以向量表示的軌跡數據以及具有標簽的訓練集。

3.2 軌跡分段

由于位置設備的采樣周期較短,收集到的位置數據多且連續,為了方便處理軌跡數據,需要對收集到的軌跡數據進行分段處理。軌跡數據分段是指在軌跡序列中找出某些屬性值變化較大的特征點,根據特征點對軌跡進行分段。

為了得到最佳軌跡分段,本文提出了權重化最小描述長度WMDL(Weighted Minimum Description Length)的軌跡分段方法。將原始軌跡看作數據D,原始軌跡分成的段看作假設H,αL(H)表示假設的軌跡長度,(2-α)L(D|H)表示在此假設的前提下原始軌跡的權重化最小描述長度,當αL(H)+(2-α)L(D|H)最小時的假設H被稱為能夠描述原始軌跡的最優假設,此時的分段即為軌跡的最佳分段。其中,α為權重參數(0<α<2,α∈R),可通過調節權重參數α的值在簡潔性和準確性之間進行取舍。當L(H)所占權重小于L(D|H)時,分段的準確性更高,適用于數據量較小的情況;當L(H)所占權重大于L(D|H)時,分段的簡潔性更高,適用于數據量較大的情況。L(H)和L(D|H)的計算方法分別如式(1)和式(2)所示:

(1)

1)+lb(dθ(PcjPcj+1,PkPk+1)+1)]

(2)

其中,pari表示第i條原始軌跡段的長度,len(·)用于求解2個軌跡點之間的距離,cj表示當前原始軌跡的第j個軌跡點的編號,P*表示軌跡點,d⊥表示2個軌跡點連成的線段與另外2個軌跡點連成的線段之間的歐氏距離,dθ表示一條線段相對于另一條線段成銳角的相對距離。

對于任意軌跡T,第1步計算T中任意2個點之間的αL(H)+(2-α)L(D|H),將計算出的值作為這2個點之間的權重;第2步求出P1點到其它各點之間的權重之和,權重之和最小的點可作為整條軌跡的關鍵點,然后按此關鍵點進行分段;第3步把關鍵點之后的后一個點看作P1點,重復第2步和第3步,直至軌跡分段完畢為止。軌跡分段示例如圖2所示,其中,實線為真實軌跡,虛線為近似軌跡,利用WMDL方法進行軌跡分段的過程可以看作求解無向完全圖的最短路徑問題。

Figure 2 Trajectory segmentation example using WMDL圖2 基于WMDL的軌跡分段示例

3.3 軌跡網格劃分

對于分段后的軌跡,除時間戳和經緯度外,沒有額外的輔助信息,為了克服數據稀疏問題,本文采用geohash算法對軌跡進行網格劃分,軌跡網格劃分的核心思想是把移動對象的活動范圍看作一個矩形平面,然后用網格對該平面進行分割,以網格編碼代替網格內軌跡點的經緯度信息。

按精度需求對所在區域進行網格分割后對網格進行編碼,緯度分割遵循上1下0的原則,經度分割遵循左0右1的原則對經緯度依次進行分割,直到滿足精度需求為止;然后將由二進制組成的網格編號從右向左進行32進制的Base32編碼(0～9,b～z,去除a,i,l,o)。如軌跡點(-8.610 88, 41.145 57),編碼長度設為7時所映射到的網格編碼為ez3fh43。

在將軌跡序列進行網格劃分后,由于相鄰的軌跡點采樣頻率高而導致距離較近,可能會發生多個相鄰軌跡點映射到相同的網格內的情況,從而造成網格編碼序列的冗余。為了解決該問題,本文提出了序列偏移算法來去除冗余數據,序列偏移算法是根據軌跡編碼序列G向右移位產生序列S,通過對比序列G和序列S對應位置是否相同來判斷序列是否冗余。如果對應位置相同則產生冗余,為判斷序列K相應位置賦值0;如果對應位置不相同,則未產生冗余,為判斷序列K相應位置賦值1。最后根據判斷序列K,生成非冗余序列G′;若判斷序列K某個位置上為1,則將G中對應位置的值賦值給G′,若判斷序列K某個位置上為0,則不為G′賦值,由此可得到去除冗余數據的編碼序列G′。

3.4 軌跡分布式表示方法

將分段后的二維軌跡序列抽象表示為一維的網格編碼序列,簡化了軌跡序列的表示,然而網格編碼序列屬于字符串型數據,不能直接輸入到模型中進行訓練。雖然常用的獨熱碼(One-Hot Encoding)能將其轉化為向量,但是面對數量巨大的網格時會導致維度災難,且獨熱編碼也不能反映出網格之間實際的地理拓撲關系。

針對上述問題,本文提出了Base2vec模型,它是由小型多層感知機網絡構成的,采用無監督的學習方法,能在歷史軌跡中學習網格之間的實際地理拓撲關系,距離越近的網格,表征后的向量越相似。

對于網格編碼表征任務而言,需要低維的表示以及保留網格之間的地理拓撲關系這2點要求,因此本文采用與Skip-gram類似的方法對軌跡的網格編碼序列進行表征,如圖3所示。其中,Gg表示當前網格的獨熱碼,維度為M,N表示隱藏層的神經元的個數(N?M)。在正向傳播的過程中,輸入向量與嵌入矩陣WM×N相乘得到隱藏層神經元的值;再通過與解碼矩陣W′N×M相乘輸出一個M維的向量,每一維均與一個網格編碼相對應;最后利用SoftMax函數計算出與當前網格相似度最大的前k個網格編碼,并將其與真實值進行對比,反向傳播調整嵌入矩陣和解碼矩陣的權重以得到最佳參數。最終目的是輸入已知的軌跡點Gg,使模型預測結果為該軌跡點的上下序列的概率p(tra(Gg)|Gg)的乘積最大,目標函數如式(3)所示:

(3)

其中,T表示所有軌跡點,tra(Gg)表示與Gg相鄰的軌跡點。

Figure 3 Structure of Base2vec network圖3 Base2vec網絡結構

此時的嵌入矩陣即為最佳的映射矩陣,此后將每一個網格的獨熱編碼與該嵌入矩陣相乘即可獲得低維且蘊含地理拓撲關系的位置向量。

為了驗證Base2vec模型的有效性,本文將編碼為ez3fhk的網格作為測試網格輸入到調整好參數的Base2vec模型中,此時輸出與網格“ez3fhk”相似度最大的8個網格與該網格的地理拓撲關系如圖4所示。根據實驗結果可知,Base2vec存在微小的誤差,但整體上保留了網格之間的地理拓撲關系。

Figure 4 Base2vec training effect visualization圖4 Base2vec訓練效果可視化圖

3.5 目的地聚類和偽標簽添加

根據歷史軌跡和查詢軌跡的匹配契合度來預測當前軌跡最有可能的目的地時可能會出現以下3種特殊情況:(1)不同起點的軌跡終點相同;(2)相同起點的軌跡終點不同;(3)相同起點和終點的軌跡相似度不同。因此,根據匹配契合度來預測目的地具有一定的局限性。由于經緯度屬于連續性數值,并且歷史軌跡數量和可用于輔助預測的附加信息有限,直接對查詢軌跡的目的地經緯度坐標進行預測可行性不高,具有很大的預測難度。

為了提高預測任務的可行性,降低預測難度,本文對預測任務進行了如下改進:

Step1提取訓練集中所有軌跡的目的地并對其進行Mean Shift聚類,將目的地分為多個密集簇,記錄每個簇的聚類中心。

Step2將聚類中心坐標按3.3節和3.4節的方法轉化為包含位置信息的嵌入向量。

Step3以Step 2的結果作為標簽,分別給對應的分布式表示后的軌跡進行標記。

以上改進將無監督訓練的移動軌跡目的地預測轉化為有監督訓練的分類問題,很大程度上提高了任務的可行性。

4 移動軌跡目的地預測模型

SATN-LSTM軌跡目的地預測模型主要包含軌跡處理、LSTM、自注意力機制、Softmax分類器和geohash解碼器5個模塊,如圖5所示。軌跡處理模塊對原始軌跡進行分段和網格劃分并通過Base2vec模型將其轉化為神經網絡可以處理的向量形式,同時賦予向量之間實際的地理拓撲關系;LSTM模塊對向量進行特征提取;自注意力模塊根據每個時間步提取特征對預測結果的影響來進一步分配特征權重,然后通過Softmax函數對其進行分類,最后將可能性最大的目的地聚類中心通過geohash解碼器反解出經緯度坐標,該經緯度坐標即為預測結果。

Figure 5 Prediction model of moving trajectory destination圖5 移動軌跡目的地預測模型

4.1 長短期記憶(LSTM)網絡

經過處理后,軌跡序列被表示為包含地理拓撲關系的嵌入向量,之后將其按照時間的先后順序依次輸入LSTM網絡中進行特征提取。LSTM的神經元如圖6所示,其中,ft、it和Ot分別表示t時刻的遺忘門、輸入門和輸出門,Gt表示t時刻的長期記憶的細胞態,Ct表示等待存入長期記憶的候選態。表示位置的嵌入向量在LSTM中的更新過程主要包括以下4個步驟:

(1)將上個時間步中提取的表示位置的特征選擇性遺忘。控制上個時間步提取的特征對當前細胞態Ct的影響程度,該過程由當前時刻的輸入和上個時刻的輸入共同決定,計算公式如式(4)所示:

ft=σ(Wf·[ht-1,xt]+bf)

(4)

其中,σ(·)表示Sigmoid激活函數,作用是把結果控制在0～1,Wf表示遺忘門的待訓練參數矩陣,bf表示遺忘門的待訓練偏置項,ht-1為t-1時刻的輸出,xt為t時刻的輸入。

(5)

其中,Wc和Wi表示輸入門的待訓練參數矩陣,bi和bc表示輸入門的待訓練偏置項。

Figure 6 Structure of LSTM neuron圖6 LSTM神經元結構

(3)更新表征長期記憶的細胞態Ct。通過遺忘門和輸入門的篩選,將需要保存的特征存入細胞態Ct,完成特征的更新,更新公式如式(6)所示:

(6)

其中,it表示t時刻的總輸入信息,Ct-1表示t-1時刻的細胞態。

(4)將細胞態中的特征選擇性地進行輸出。輸出門對Ct中的特征進行選擇性輸出,再與經過tanh函數處理的Ct相乘得到當前時間步的輸出ht,計算公式如式(7)所示:

(7)

抽象化表示的前綴軌跡序列經過LSTM網絡后得到t時刻的輸出特征Ot以及表征整個前綴軌跡的總輸出特征ht。

4.2 自注意力機制

LSTM網絡的輸入是按時間步依次進行的,對于距離較遠且關系密切的特殊點,需要經過多個時間步迭代才能聯系到一起,這種聯系會隨著距離的增加而減小。因此,本文將自注意力機制引入LSTM網絡中,通過計算每個時間步輸出特征之間的關系,為各個特征分配相應的權重,能夠很好地解決遠距離軌跡點之間的特征依賴關系,計算過程如圖7所示,共包括3個階段。

Figure 7 Calculation process of weight allocation圖7 權重分配的計算過程

第1個階段將每一個特征中的查詢Q和其它所有特征的鍵K進行相似度計算得到權重分值。相似度計算常用的方法有向量點積、余弦相似度或構建神經網絡,本文采用向量點積來求權重分值,如式(8)所示:

(8)

其中,Q和K表示某個輸入x(對應圖7中的x1,x2,…,xn)進行不同線性變化之后的結果,dx為特征向量x的維度。

由于第1階段計算的權重分值的取值范圍不固定,因此本文第2階段引入Softmax函數對第1階段的權重分值進行數值轉換,如式(9)所示。此方法不但可以將所有特征的權重分值進行歸一化處理,而且還能突出重要特征的權重。

(9)

第2階段計算的結果即為每個特征向量對應的權重系數,因此第3個階段將與其對應的值V進行加權求和后的結果即為當前軌跡序列的抽象表示,如式(10)所示:

(10)

4.3 Softmax分類器和geohash

由于3.4節對軌跡添加了偽標簽,因此本文將自注意力機制提取出的特征通過Softmax函數進行分類,即將該軌跡分類到其所屬的簇中,以實現目的地的預測。在實際部署在線預測系統中,為了提高命中率和預測的精度,可以輸出前k個可能性較高的目的地以作為參考,計算公式如(11)所示:

(11)

其中,cx表示軌跡目的地的聚類中心,Zl表示軌跡序列l的抽象表示。

“各學段的閱讀教學都要重視朗讀和默讀。加強對閱讀方法的指導，讓學生逐步學會精讀、略讀和瀏覽。”（小學語文課程標準）告訴我們默讀既是教學目標，也是閱讀教學中的一個非常重要的方式方法。因此，教科書從二年級下學期，一般在中段起，開始安排默讀的訓練。可筆者卻驚訝的發現，在筆者所接觸的語文教師的課堂中，平均默讀時間每節課大約2-3分鐘，有的甚至根本沒有設計默讀時間；所在學校學生的默讀能力普遍較差，甚至到了高年級還不知道怎樣默讀。默讀如此被忽視，與當前在小學語文閱讀教學中較普遍重視朗讀教學有關。而教師側重朗讀教學則源于新課程倡導讓學生動起來，讓課堂活起來。

最終預測的目的地為向量表示,通過geohash解碼器將其反解為經緯度表示,該過程即為Base2vec和geohash編碼的逆向過程。

5 實驗與結果分析

本文使用2個真實的出租車軌跡數據集Porto和T-driver來驗證提出模型SATN-LSTM的有效性和效率,并與Subsyn[18]、MLP[17]、T-CONV-LE-MUL[7]和LSI-LSTM[13]模型進行比較,以證實SATN-LSTM模型具有更高的準確性。

Porto數據集收錄了葡萄牙波爾圖市442輛出租車2013年全年的行車軌跡,共170多萬條完整的行程。本文從數據集中隨機選取10萬條軌跡作為實驗數據,經分段處理后共得到164 862條軌跡,按照20%～80%的軌跡完成比例對這些軌跡進行隨機截取,將其中的60%作為訓練集,20%作為驗證集,另外的20%作為測試集。

T-driver數據集收錄了北京市10 357輛出租車2008年2月2號到2008年2月8號一周的行車軌跡,約1 500萬個軌跡點,軌跡總距離達到了900萬公里。隨機選取其中2 000輛出租車的完整軌跡,經分段處理后得到222 047條軌跡,剩余處理方法與Porto一致。

對比模型的介紹如下:

(1)Subsyn[17]:該模型利用馬爾科夫鏈模型建立每條軌跡中位置之間的轉移關系,并遵循貝葉斯推理框架。

(2)MPL[18]:該模型是一種基于多層感知機的神經網絡模型。輸入層接收帶有相關上下文信息的前綴軌跡表示,并采用標準隱藏層來訓練軌跡。

(3)T-CONV-LE-MUL[7]:該模型采用多尺度多范圍的卷積神經網絡(CNN)模型。輸入層接收轉化為黑白圖像的前綴軌跡表示,對目的地進行聚類并為圖像添加偽標簽,將目的地預測問題轉化為圖像分類問題。

(4)LSI-LSTM[13]:該模型在長短期記憶網絡中引入注意力感知模塊,輸入層接收前綴軌跡表示,并反向傳播更新參數。

5.1 預測評價指標

定義6(平均絕對預測誤差MAPE(Mean Absolute Prediction Error)[7]) 平均絕對預測誤差是指預測目的地經解碼后與真實目的地之間距離的平均值(單位為km),能直觀反映出預測效果。計算公式如式(12)所示:

(12)

(13)

(14)

定義7(平均相對預測誤差MRPE(Mean Relative Prediction Error)[12]) 由于平均絕對預測誤差比較苛刻,且在預測之前將軌跡映射到了相同大小的網格之中,因此本文引入平均相對預測誤差來量化預測的偏離度,計算公式如式(15)所示:

(15)

5.2 樣本集生成及Top-k分析

本文采用6位編碼對分段后的軌跡進行網格劃分,網格大小約為610 m×610 m,Porto數據集共生成225 106個網格,T-driver數據集共生成310 866個網格。

根據式(11),SATN-LSTM模型可以輸出前k個最有可能的目的地。預測誤差取前k個可能性最大的預測目的地到真實目的地的最短距離,k值的取值范圍與平均絕對預測誤差之間的關系如圖8所示。由圖8可知,較大的k可以很明顯地降低預測誤差,因為k值越大,輸出預測目的地的數量就越多,命中真實目的地的概率相對也就越大。在T-driver數據集上預測誤差隨k值的增大下降較為明顯,而Porto數據集上預測誤差隨k值的增大下降并不明顯。經過對數據的分析可知,T-driver數據集相比Porto數據集更加復雜,預測精度也不及Porto數據集上的高,因此在T-driver數據集上隨著k值的增大,預測誤差下降較為明顯。

Figure 8 Relationship between parameter k and prediction error圖8 參數k和平均絕對預測誤差之間的關系

當k大于5時,Porto和T-drive數據集上的預測誤差下降態勢趨于平緩,因此綜合開銷與收益考慮,在實際部署在線預測系統中將k的值取5,即可以使用前5個預測的目的地進行基于位置的推薦,以提高命中的概率。

5.3 不同模型預測結果對比

將訓練集、測試集和驗證集中的軌跡序列轉化為帶有地理拓撲關系的向量表示,然后將訓練集輸入到模型中進行訓練,用驗證集調整模型參數,經多次調整后模型最優參數值如表1所示。最后根據預測評價指標對測試集的預測結果進行對比,并與Subsyn、MLP、T-CONV-LE-MUL和LSI-LSTM等現有的模型在相同的數據集上進行比較,這些模型均采取離線訓練在線預測的方式。實驗結果如圖9和圖10所示,在2種評價指標上,本文模型相較于Subsyn、MLP、T-CONV-LE-MUL等預測模型總體預測精度具有顯著的提升,相較于LSI-LSTM模型在Porto數據集上具有顯著優勢,而在T-driver數據集上優勢并不明顯。根據對數據集的分析發現,相較于Porto,T-driver中軌跡數據的時間跨度較短,并且不同軌跡之間的空間距離跨度較大,軌跡數據相較于Porto數據集更加復雜和多樣化,且LSI-LSTM模型也具有較高的準確性,因此在T-driver數據集上相較于LSI-LSTM模型預測精度提升有限。

Table 1 Model parameters表1 模型參數

Figure 9 MAPE of different models圖9 不同模型的平均絕對預測誤差

Figure 10 MRPE of different models圖10 不同模型的平均相對預測誤差

在軌跡數據處理方面,Subsyn模型將子軌跡進行合成,通過增加軌跡數量的方式來解決數據稀疏問題;MPL模型將子軌跡轉化為不包含地理拓撲關系的向量表示;T-CONV-LE-MUL模型則是將子軌跡映射為二維圖像,但粒度選擇困難;LSI-LSTM模型把更多的語義信息融入子軌跡網格向量中,卻沒有考慮軌跡網格之間的地理拓撲關系。在軌跡的處理和表示方面都存在諸多不足,本文提出的軌跡分布式表示方法盡可能地彌補了現有方法的缺點。在預測方法方面,Subsyn和MLP模型沒有考慮軌跡的長期依賴問題;T-CONV-LE-MUL模型只截取了軌跡的開始和結束位置的部分軌跡,有很大程度的局限性;LSI-LSTM模型的注意力感知模塊參數較多,導致調整困難;本文將自注意力機制融入LSTM網絡中,挖掘序列中的關鍵點并根據其重要程度分配權重,較好地解決了長期依賴問題。根據實驗結果可知,本文提出的預測模型和軌跡處理方法具有更好的性能表現。

5.4 軌跡完成比例對預測結果的影響

除了上述驗證外,本文在固定軌跡完成比例的情況下也進行了相關實驗,引入軌跡完成比例的概念以測試各模型在不同軌跡完成比例下的預測性能,從多角度驗證模型的魯棒性。固定軌跡完成比例分別取10%～80%,在Porto和T-driver數據集上對固定軌跡完成比例的軌跡進行實驗驗證,實驗結果如圖11和圖12所示。

Figure 12 MAPE on T-driver dataset圖12 T-driver數據集的MAPE

隨著軌跡完成比例的增加,所有模型的預測誤差都是逐步下降的,即前綴軌跡越接近目的地,可提供的軌跡信息越多,預測結果也就越準確。與此同時,本文模型相較于LSI-LSTM等模型在較短的軌跡完成比例下更具優勢,尤其是在20%的軌跡完成比例下具有明顯的優勢,證明了自注意力機制較好地解決了長期依賴問題。此外,結合圖9和圖10,相較于現有的預測模型,在混合軌跡完成比例和固定軌跡完成比例下,本文提出的模型相較于其它模型都有更好的表現。

6 結束語

軌跡的目的地預測在智能交通系統、智能導航系統和推薦系統等領域具有廣泛的應用。本文提出了一種基于LSTM網絡的移動軌跡目的地預測模型,對軌跡進行網格劃分,用Base2vec對軌跡進行分布式表示,緩解了數據稀疏問題帶來的影響。針對長期依賴問題,引入了自注意力機制,通過計算LSTM網絡任意2個時間步輸出之間的相關關系,為每個輸出分配相應的權重。之后的工作將考慮在軌跡信息中嵌入時間、車輛ID等更多的語義信息,通過這些信息來加強前綴軌跡與真實目的地之間的聯系,以提高預測的精度。