晉廣印,趙旭俊,龔藝璇

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

1 引言

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

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

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

2 相關(guān)工作

2.1 數(shù)據(jù)稀疏問題

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

2.2 長期依賴問題

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

3 軌跡數(shù)據(jù)處理

3.1 相關(guān)定義及軌跡數(shù)據(jù)處理流程

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

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

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

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

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

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

Figure 1 Overview of trajectory data processing圖1 軌跡數(shù)據(jù)處理流程

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

3.2 軌跡分段

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

為了得到最佳軌跡分段,本文提出了權(quán)重化最小描述長度WMDL(Weighted Minimum Description Length)的軌跡分段方法。將原始軌跡看作數(shù)據(jù)D,原始軌跡分成的段看作假設H,αL(H)表示假設的軌跡長度,(2-α)L(D|H)表示在此假設的前提下原始軌跡的權(quán)重化最小描述長度,當αL(H)+(2-α)L(D|H)最小時的假設H被稱為能夠描述原始軌跡的最優(yōu)假設,此時的分段即為軌跡的最佳分段。其中,α為權(quán)重參數(shù)(0<α<2,α∈R),可通過調(diào)節(jié)權(quán)重參數(shù)α的值在簡潔性和準確性之間進行取舍。當L(H)所占權(quán)重小于L(D|H)時,分段的準確性更高,適用于數(shù)據(jù)量較小的情況;當L(H)所占權(quán)重大于L(D|H)時,分段的簡潔性更高,適用于數(shù)據(jù)量較大的情況。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個點之間的權(quán)重;第2步求出P1點到其它各點之間的權(quán)重之和,權(quán)重之和最小的點可作為整條軌跡的關(guān)鍵點,然后按此關(guān)鍵點進行分段;第3步把關(guān)鍵點之后的后一個點看作P1點,重復第2步和第3步,直至軌跡分段完畢為止。軌跡分段示例如圖2所示,其中,實線為真實軌跡,虛線為近似軌跡,利用WMDL方法進行軌跡分段的過程可以看作求解無向完全圖的最短路徑問題。

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

3.3 軌跡網(wǎng)格劃分

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

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

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

3.4 軌跡分布式表示方法

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

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

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

(3)

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

Figure 3 Structure of Base2vec network圖3 Base2vec網(wǎng)絡結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 長短期記憶(LSTM)網(wǎng)絡

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

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

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

(4)

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

(5)

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

Figure 6 Structure of LSTM neuron圖6 LSTM神經(jīng)元結(jié)構(gòu)

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

(6)

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

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

(7)

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

4.2 自注意力機制

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

Figure 7 Calculation process of weight allocation圖7 權(quán)重分配的計算過程

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

(8)

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

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

(9)

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

(10)

4.3 Softmax分類器和geohash

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

(11)

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

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

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

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

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

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

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

對比模型的介紹如下:

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

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

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

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

5.1 預測評價指標

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

(12)

(13)

(14)

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

(15)

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

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

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

Figure 8 Relationship between parameter k and prediction error圖8 參數(shù)k和平均絕對預測誤差之間的關(guān)系

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

5.3 不同模型預測結(jié)果對比

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

Table 1 Model parameters表1 模型參數(shù)

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

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

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

5.4 軌跡完成比例對預測結(jié)果的影響

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

Figure 12 MAPE on T-driver dataset圖12 T-driver數(shù)據(jù)集的MAPE

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

6 結(jié)束語

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