基于長(zhǎng)短期記憶網(wǎng)絡(luò)的移動(dòng)軌跡目的地預(yù)測(cè)*

晉廣印,趙旭俊,龔藝璇

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

1 引言

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

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

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

2 相關(guān)工作

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

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

2.2 長(zhǎng)期依賴問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

3.2 軌跡分段

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

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

(1)

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

(2)

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

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

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

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

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

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

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

3.4 軌跡分布式表示方法

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

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

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

(3)

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

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

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

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

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

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

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

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

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

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

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

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

4 移動(dòng)軌跡目的地預(yù)測(cè)模型

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

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

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

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

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

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

(4)

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

(5)

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

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

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

(6)

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

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

(7)

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

4.2 自注意力機(jī)制

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

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

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

(8)

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

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

(9)

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

(10)

4.3 Softmax分類器和geohash

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

(11)

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

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

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

5 實(shí)驗(yàn)與結(jié)果分析

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

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

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

對(duì)比模型的介紹如下:

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

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

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

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

5.1 預(yù)測(cè)評(píng)價(jià)指標(biāo)

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

(12)

(13)

(14)

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

(15)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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