晉廣印,趙旭俊,龔藝璇

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

1 引言

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

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

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

2 相關(guān)工作

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

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

2.2 長期依賴問題

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

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

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

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

3.2 軌跡分段

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

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

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

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

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

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

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

3.4 軌跡分布式表示方法

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

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

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

(3)

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

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

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

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

Figure 4 Base2vec training effect visualization圖4 Base2vec訓(xùn)練效果可視化圖

3.5 目的地聚類和偽標(biāo)簽添加

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

為了提高預(yù)測任務(wù)的可行性,降低預(yù)測難度,本文對預(yù)測任務(wù)進(jìn)行了如下改進(jìn):

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

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

Step3以Step 2的結(jié)果作為標(biāo)簽,分別給對應(yīng)的分布式表示后的軌跡進(jìn)行標(biāo)記。

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

4 移動軌跡目的地預(yù)測模型

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

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

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

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

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

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

(4)

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

(5)

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

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

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

(6)

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

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

(7)

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

4.2 自注意力機制

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

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

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

(8)

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

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

(9)

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

(10)

4.3 Softmax分類器和geohash

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

(11)

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

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

最終預(yù)測的目的地為向量表示,通過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]模型進(jìn)行比較,以證實SATN-LSTM模型具有更高的準(zhǔn)確性。

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

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

對比模型的介紹如下:

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

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

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

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

5.1 預(yù)測評價指標(biāo)

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

(12)

(13)

(14)

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

(15)

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

本文采用6位編碼對分段后的軌跡進(jìn)行網(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個最有可能的目的地。預(yù)測誤差取前k個可能性最大的預(yù)測目的地到真實目的地的最短距離,k值的取值范圍與平均絕對預(yù)測誤差之間的關(guān)系如圖8所示。由圖8可知,較大的k可以很明顯地降低預(yù)測誤差,因為k值越大,輸出預(yù)測目的地的數(shù)量就越多,命中真實目的地的概率相對也就越大。在T-driver數(shù)據(jù)集上預(yù)測誤差隨k值的增大下降較為明顯,而Porto數(shù)據(jù)集上預(yù)測誤差隨k值的增大下降并不明顯。經(jīng)過對數(shù)據(jù)的分析可知,T-driver數(shù)據(jù)集相比Porto數(shù)據(jù)集更加復(fù)雜,預(yù)測精度也不及Porto數(shù)據(jù)集上的高,因此在T-driver數(shù)據(jù)集上隨著k值的增大,預(yù)測誤差下降較為明顯。

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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