陳建偉 李建波

(青島大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 山東 青島 266071)

0 引 言

如今，許多移動(dòng)設(shè)備如手機(jī)和智能手環(huán)已成為人們出門(mén)必備的物品。這些設(shè)備往往內(nèi)置GPS，可以實(shí)時(shí)檢測(cè)人的位置。因此，人們的運(yùn)動(dòng)軌跡可以輕松獲得，從而為探索人類(lèi)的移動(dòng)規(guī)律帶來(lái)可能。此外，人類(lèi)移動(dòng)規(guī)律性的探索一直是自然、社會(huì)等領(lǐng)域長(zhǎng)期以來(lái)的研究熱點(diǎn)[1-2]。該研究對(duì)疾病傳播、交通流量控制有很大影響，它可以幫助解決很多城市問(wèn)題，如避免交通堵塞、預(yù)防疾病等。

本文通過(guò)分析人類(lèi)移動(dòng)模式，預(yù)測(cè)人群未來(lái)軌跡?，F(xiàn)有的人群軌跡預(yù)測(cè)任務(wù)主要面臨兩個(gè)問(wèn)題，一個(gè)是數(shù)據(jù)的稀疏性；另一個(gè)是冗長(zhǎng)的歷史軌跡。其中數(shù)據(jù)的稀疏性表現(xiàn)在兩個(gè)方面：(1)人們的軌跡從現(xiàn)實(shí)世界中獲取，由于人類(lèi)移動(dòng)的不確定性和個(gè)人隱私問(wèn)題，收集的數(shù)據(jù)量通常比較稀疏；(2)每個(gè)人的軌跡記錄的時(shí)間間隔在稀疏的數(shù)據(jù)中的分布也不均勻，這導(dǎo)致了軌跡的碎片化，加重了數(shù)據(jù)稀疏性的問(wèn)題。而冗長(zhǎng)的歷史軌跡表現(xiàn)為：收集的每個(gè)用戶的全部軌跡往往很冗長(zhǎng)，這為尋找有價(jià)值的移動(dòng)軌跡增加了難度?？偟膩?lái)說(shuō)，以上的兩個(gè)問(wèn)題使得預(yù)測(cè)任務(wù)更加困難。

人的移動(dòng)軌跡本質(zhì)上是一個(gè)空間分布的時(shí)間序列數(shù)據(jù)，早期RNN被提出用來(lái)處理時(shí)間序列數(shù)據(jù)，卻容易出現(xiàn)長(zhǎng)輸入導(dǎo)致的梯度消失問(wèn)題。LSTM的提出改善了這一問(wèn)題，其通過(guò)門(mén)控制結(jié)構(gòu)來(lái)處理長(zhǎng)輸入并且表現(xiàn)優(yōu)異。直觀地，單一的LSTM網(wǎng)絡(luò)可以直接用來(lái)處理軌跡預(yù)測(cè)問(wèn)題，然而卻不是有效的。首先，LSTM對(duì)于過(guò)長(zhǎng)的輸入依然有著遺忘的問(wèn)題[3]，冗長(zhǎng)的移動(dòng)軌跡使得單一的LSTM難以捕捉順序轉(zhuǎn)換規(guī)律。其次，數(shù)據(jù)的稀疏性也使得單一的LSTM更難以處理預(yù)測(cè)任務(wù)。這表現(xiàn)在稀疏的特征和丟失的數(shù)據(jù)使得LSTM難以訓(xùn)練。另外，LSTM網(wǎng)絡(luò)由于過(guò)長(zhǎng)的輸入丟失數(shù)據(jù)的長(zhǎng)期依賴關(guān)系，導(dǎo)致無(wú)法捕捉軌跡的歷史移動(dòng)模式。

為了解決上述問(wèn)題，本文提出一個(gè)基于LSTM的編碼器-解碼器模型。具體地，本文將用戶的軌跡劃分成歷史軌跡和當(dāng)前軌跡，隨后一個(gè)嵌入矩陣被用來(lái)處理軌跡的稀疏性。被嵌入的歷史軌跡輸入到編碼器中，得到語(yǔ)義向量和隱藏狀態(tài)。繼而，解碼器的輸入為來(lái)自編碼器的輸出和被嵌入的當(dāng)前軌跡，最后生成用戶未來(lái)軌跡。針對(duì)長(zhǎng)歷史軌跡，本文使用數(shù)據(jù)逆置和雙向長(zhǎng)短期神經(jīng)網(wǎng)絡(luò)作為編碼器的兩個(gè)方法，有效地緩解了LSTM對(duì)于早期軌跡遺忘的問(wèn)題。

1 相關(guān)工作

雖然人類(lèi)行為的預(yù)測(cè)有局限性，但Song等[4]發(fā)現(xiàn)了93%的潛在可預(yù)測(cè)性。在此基礎(chǔ)上，許多研究者探索人類(lèi)移動(dòng)模式和預(yù)測(cè)人類(lèi)移動(dòng)性。如文獻(xiàn)[5-6]通過(guò)數(shù)據(jù)挖掘探索了人類(lèi)移動(dòng)模式。具體地，Marta等[5]發(fā)現(xiàn)人類(lèi)軌跡顯示出高度的時(shí)間和空間規(guī)律性，每個(gè)人都有很大概率訪問(wèn)常去的地點(diǎn)，且每個(gè)人的移動(dòng)距離與時(shí)間無(wú)關(guān)。隨后，文獻(xiàn)[7-8]提出了與移動(dòng)模式結(jié)合來(lái)預(yù)測(cè)人類(lèi)的移動(dòng)性的方法，其中文獻(xiàn)[7]通過(guò)當(dāng)前觀察的歷史移動(dòng)模式提出了一個(gè)高斯混合模型來(lái)計(jì)算未來(lái)移動(dòng)地點(diǎn)的概率。與以上方法相比，本文模型可以在訓(xùn)練過(guò)程中學(xué)習(xí)用戶之間的移動(dòng)模式。

以上方法都取得了良好的結(jié)果，但預(yù)先定義的模式往往不能表達(dá)用戶移動(dòng)軌跡的順序轉(zhuǎn)換規(guī)律，因此后來(lái)的研究者們建立模型預(yù)測(cè)人類(lèi)的移動(dòng)性。如馬爾可夫鏈模型是一種經(jīng)典的統(tǒng)計(jì)模型，但此方法僅考慮上一步的狀態(tài)，這使得其難以捕獲到復(fù)雜的順序轉(zhuǎn)換規(guī)律。隨后，文獻(xiàn)[9]提出了隱馬爾可夫模型(HMM)來(lái)與隱藏的未知狀態(tài)結(jié)合，從而改進(jìn)馬爾可夫模型。雖然HMM表現(xiàn)優(yōu)異，但其忽略了軌跡的時(shí)間依賴關(guān)系。隨著深度學(xué)習(xí)技術(shù)的興起，RNN被用來(lái)捕捉時(shí)間依賴關(guān)系并預(yù)測(cè)用戶移動(dòng)軌跡[10-12]。Liu等[10]提出了ST-RNN，并對(duì)軌跡局部時(shí)間和空間上下文進(jìn)行建模。Yao等[11]提出了一個(gè)結(jié)合了語(yǔ)義信息的LSTM神經(jīng)網(wǎng)絡(luò)。與以上方法相比，本文模型同時(shí)考慮歷史軌跡和當(dāng)前軌跡來(lái)預(yù)測(cè)未來(lái)軌跡，且限制了當(dāng)前軌跡的長(zhǎng)度，使得預(yù)測(cè)精度得以提升。

編碼器-解碼器模型率先由文獻(xiàn)[13]提出，且已經(jīng)在軌跡預(yù)測(cè)的很多領(lǐng)域中取得優(yōu)異表現(xiàn)。Park等[14]提出基于編碼器-解碼器的車(chē)輛軌跡預(yù)測(cè)技術(shù)，該技術(shù)可以實(shí)時(shí)生成周?chē)?chē)輛的未來(lái)軌跡序列。Nguyen等[15]提出了一種序列到序列模型，根據(jù)歷史路線預(yù)測(cè)船舶的下一個(gè)位置。Feng等[16]提出了注意力機(jī)制循環(huán)神經(jīng)網(wǎng)絡(luò)來(lái)捕捉歷史軌跡的多層周期性。本文工作與文獻(xiàn)[14-15]思路有相似之處，與文獻(xiàn)[16]相比，改進(jìn)了模型結(jié)構(gòu)，提高了預(yù)測(cè)精度。

2 移動(dòng)軌跡問(wèn)題的LSTM模型

2.1 問(wèn)題定義

本文首先收集每個(gè)用戶的移動(dòng)軌跡，軌跡全部按照時(shí)間順序排列。因此，用戶ux軌跡定義為:

(1)

2.2 RNN和LSTM

神經(jīng)網(wǎng)絡(luò)(NN)由大量相互連接的節(jié)點(diǎn)組成，它本身是表示數(shù)據(jù)關(guān)系的近似函數(shù)。此外，NN經(jīng)常處理的任務(wù)大致分為分類(lèi)和回歸問(wèn)題，可以通過(guò)各種結(jié)構(gòu)來(lái)解決不同的問(wèn)題。NN中最常見(jiàn)的網(wǎng)絡(luò)結(jié)構(gòu)是擅長(zhǎng)處理圖像的卷積神經(jīng)網(wǎng)絡(luò)(CNN)和擅長(zhǎng)處理時(shí)間序列的RNN。

在標(biāo)準(zhǔn)RNN結(jié)構(gòu)中，隱藏層中的神經(jīng)元建立權(quán)重連接，因此RNN擁有“記憶”。但是當(dāng)序列太長(zhǎng)時(shí)，早期的輸入對(duì)后來(lái)的輸入影響較小，這導(dǎo)致了梯度消失問(wèn)題。為了解決這個(gè)問(wèn)題，RNN的變體LSTM和GRU被提出?，F(xiàn)在，LSTM被廣泛用于長(zhǎng)輸入問(wèn)題。本文模型基于LSTM結(jié)構(gòu)，式(2)-式(7)描述了LSTM的工作原理：

it=σ(Wii×xt+bii+Whi×ht-1+bhi)

(2)

ft=σ(Wif×xt+bif+Whf×ht-1+bhf)

(3)

gt=tanh(Wig×xt+big+Whg×ht-1+bhg)

(4)

ot=σ(Wio×xt+bio+Who×ht-1+bho)

(5)

ct=ft×ct-1+it×gt

(6)

ht=ot⊙tanh(ct)

(7)

式中：Wii、Whi、Wif、Whf、Wig、Whg、Wio、Who是各個(gè)控制門(mén)的權(quán)重矩陣；b為偏置向量，ct是t時(shí)刻存儲(chǔ)在神經(jīng)元中的值；ht是隱藏層在t時(shí)刻的輸出；⊙表示點(diǎn)積。

3 基于編碼器-解碼器的位置預(yù)測(cè)模型

3.1 模型結(jié)構(gòu)

編碼器-解碼器模型[13]最先應(yīng)用于自然語(yǔ)言處理的問(wèn)題上，如機(jī)器翻譯。在機(jī)器翻譯中，一種語(yǔ)言被翻譯成另一種語(yǔ)言，兩種語(yǔ)言的長(zhǎng)度通常不同。而傳統(tǒng)的RNN模型的輸入和輸出長(zhǎng)度相同，因此限制了翻譯的準(zhǔn)確性。隨后，編碼器-解碼器模型被提出。該模型由兩個(gè)單獨(dú)的RNN組成，分別稱為編碼器和解碼器，其工作機(jī)制是首先通過(guò)編碼器對(duì)源輸入進(jìn)行編碼并且獲得語(yǔ)義向量，接下來(lái)語(yǔ)義向量作為編碼器和解碼器的連接，最后通過(guò)解碼器分析語(yǔ)義向量并且預(yù)測(cè)目標(biāo)語(yǔ)言。

在本文模型中，如圖1所示，給出一個(gè)序列對(duì)(x1,x2,…,xt)和(y1,y2,…,yτ)，其中t和τ不一定相等。通過(guò)式(2)到式(7)，編碼器處理輸入(x1,x2,…,xt)。經(jīng)過(guò)t個(gè)時(shí)間步的處理，編碼器產(chǎn)生最終的語(yǔ)義向量ct。ct的計(jì)算過(guò)程可以表示為：

圖1 編碼器-解碼器模型

ct=f(xt,ct-1)

(8)

式中：f為編碼器的運(yùn)行函數(shù), 具體地，f是式(2)到式(6)的整合表示。隨后，它作為解碼器的輸入。解碼步驟為由xt作為初始的輸入，在隨后的τ個(gè)時(shí)間步中生成(y1,y2,…,yτ)?；贚STM的編碼器-解碼器模型的目標(biāo)是通過(guò)編碼器生成的語(yǔ)義向量ct計(jì)算輸出序列的條件概率p(y1,y2,…,yτ|x1,x2,…,xt)，該條件概率可以表示為：

(9)

由于本文使用xt作為解碼器的初始輸入，p(y1)的計(jì)算過(guò)程如下：

p(y1)=z(ct,xt)

(10)

式中：z是解碼器的運(yùn)行函數(shù)，同理z也是式(2)到式(6)的整合表示。為了與編碼器區(qū)分，此處使用了符號(hào)z。

兩個(gè)LSTM網(wǎng)絡(luò)分別在本文的模型中用作編碼器和解碼器，如圖1所示，編碼器首先對(duì)用戶的歷史軌跡進(jìn)行編碼并生成語(yǔ)義向量(Context)。注意到語(yǔ)義向量的大小由隱藏層的大小決定，因此語(yǔ)義向量的大小保持固定。隨后，解碼器對(duì)語(yǔ)義向量進(jìn)行解碼。最后從當(dāng)前軌跡中預(yù)測(cè)未來(lái)的軌跡。更清楚地來(lái)解釋?zhuān)僭O(shè)用戶的歷史軌跡是(x1,x2,x3,x4,x5)，當(dāng)前軌跡是(y1,y2,y3),將歷史軌跡作為編碼器的輸入，獲得編碼器最后一個(gè)時(shí)間步的隱藏狀態(tài)和Context。然后將編碼器的最后時(shí)刻的隱藏狀態(tài)作為解碼器的初始狀態(tài)，并將歷史軌跡的最后一個(gè)地點(diǎn)x5作為解碼器的初始輸入。在解碼器中，每更新一個(gè)時(shí)間步，將語(yǔ)義向量用作當(dāng)前位置的參考向量。最后，將y3輸入解碼器來(lái)預(yù)測(cè)下一個(gè)地點(diǎn)y4。以上是模型的核心工作流程，更具體地，每個(gè)地點(diǎn)首先通過(guò)嵌入網(wǎng)絡(luò)層來(lái)將稀疏的特征(如地點(diǎn)標(biāo)識(shí)、時(shí)間)表示為密集矩陣。嵌入層使用非常廣泛，在語(yǔ)義表達(dá)方面表現(xiàn)良好[17]。隨后，將一個(gè)完全連接層添加到解碼器的輸出層。最后，本文加入Softmax層根據(jù)上一層的輸出計(jì)算預(yù)測(cè)地點(diǎn)的概率分布。完整的網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。

圖2 預(yù)測(cè)模型整體結(jié)構(gòu)

3.2 訓(xùn)練集準(zhǔn)備

在3.1節(jié)中，注意到編碼器-解碼器模型使用的訓(xùn)練集是序列對(duì)。為了方便訓(xùn)練，本文制作了相似的訓(xùn)練集。

制作此訓(xùn)練集的方法是：分割每個(gè)用戶的全部軌跡為多個(gè)子軌跡；劃分子軌跡們?yōu)闅v史軌跡和當(dāng)前軌跡。示例描述如下：假設(shè)用戶u1有10個(gè)子軌跡，那么首先第一個(gè)子軌跡作為該用戶的歷史軌跡，而第二個(gè)子軌跡作為當(dāng)前軌跡，要預(yù)測(cè)的目標(biāo)地點(diǎn)是當(dāng)前軌跡的最后一個(gè)地點(diǎn)。隨后，將該用戶的第一個(gè)和第二個(gè)子軌跡作為歷史軌跡，第三個(gè)子軌跡為當(dāng)前軌跡。因此對(duì)于u1，可以生成9個(gè)數(shù)據(jù)對(duì)樣本。本文對(duì)其他用戶使用相同的方法，生成所有的訓(xùn)練集。

3.3 新的問(wèn)題

3.2節(jié)的訓(xùn)練集的制作方法會(huì)導(dǎo)致長(zhǎng)歷史軌跡的問(wèn)題。即使LSTM擅長(zhǎng)處理長(zhǎng)輸入問(wèn)題，神經(jīng)元存儲(chǔ)的“記憶”也會(huì)因輸入過(guò)長(zhǎng)而消失。因此，F(xiàn)eng等[16]提出將注意力機(jī)制添加到模型中以計(jì)算歷史軌跡與當(dāng)前軌跡的關(guān)聯(lián)，這在一定程度上解決了長(zhǎng)軌跡的問(wèn)題。然而，新增加的注意力機(jī)制在訓(xùn)練過(guò)程中計(jì)算當(dāng)前解碼器的輸入和編碼器的所有輸出之間的概率分布，這浪費(fèi)了很多時(shí)間。此外，基于現(xiàn)有的兩個(gè)網(wǎng)絡(luò)添加這種機(jī)制會(huì)增加參數(shù)數(shù)量，使訓(xùn)練更加困難。

3.4 改進(jìn)方法

先前的研究者們提出了許多方法解決過(guò)長(zhǎng)的輸入帶來(lái)的問(wèn)題[18]，本文使用兩種方法來(lái)提高預(yù)測(cè)的準(zhǔn)確性。具體地，從數(shù)據(jù)和模型兩個(gè)方面來(lái)改進(jìn)。在數(shù)據(jù)方面，參考文獻(xiàn)[19]中逆置數(shù)據(jù)的方法，這不僅沒(méi)有降低精度，反而提高了預(yù)測(cè)的準(zhǔn)確性。例如，如果原始訓(xùn)練集是(x1,x2,x3,x4,x5)和(y1,y2,y3)，將逆置的數(shù)據(jù)輸入到編碼器中，并且目標(biāo)數(shù)據(jù)不變，即新的訓(xùn)練集為(x5,x4,x3,x2,x1)和(y1,y2,y3)。分析認(rèn)為，逆置的數(shù)據(jù)使x1更接近y1，從而使其他位置相對(duì)而言更接近目標(biāo)位置。在模型方面，由于注意到編碼器可以通過(guò)逆置數(shù)據(jù)來(lái)學(xué)習(xí)早期的歷史數(shù)據(jù)，從而減輕了早期遺忘的問(wèn)題。因此，本文使用BiLSTM(Bidirectional LSTM)-LSTM結(jié)構(gòu)，即編碼器基于BiLSTM結(jié)構(gòu)。如上所述，過(guò)長(zhǎng)的輸入限制了LSTM的能力，因此編碼器的語(yǔ)義信息不能保存歷史軌跡的完整信息。根據(jù)數(shù)據(jù)的改進(jìn)方法，逆置的歷史軌跡提升了預(yù)測(cè)精度。因此，正向的歷史軌跡和反向的軌跡可以一起豐富語(yǔ)義信息。很方便地，本文采用了BiLSTM結(jié)構(gòu)作為編碼器來(lái)實(shí)現(xiàn)這種想法。改進(jìn)模型如圖3所示，在編碼器中，c1(x1,xn)和c2(xn,x1)分別是編碼器的前向傳播過(guò)程和后向傳播過(guò)程的神經(jīng)元向量。并且，本文提出使用c1和c2的簡(jiǎn)單加法作為更新后的參考語(yǔ)義向量，解碼器的初始狀態(tài)是前向傳播的隱藏狀態(tài)h1(x1,xn)。

4 實(shí) 驗(yàn)

4.1 數(shù)據(jù)集

本文使用三個(gè)不同的數(shù)據(jù)集，分別是Foursquare 2010、Foursquare 2012和Gowalla。Foursquare 2010數(shù)據(jù)集來(lái)自文獻(xiàn)[16]，F(xiàn)oursquare 2012[20]數(shù)據(jù)集是Foursquare于2012年4月12日至2013年2月16日在紐約市收集的長(zhǎng)期真實(shí)簽到數(shù)據(jù)。Gowalla[21]和Foursquare都是基于用戶位置信息的服務(wù)機(jī)構(gòu)，它們鼓勵(lì)用戶與他人共享有關(guān)其當(dāng)前位置的信息。數(shù)據(jù)格式如下：用戶ID；地點(diǎn)ID；類(lèi)別ID；類(lèi)別名稱；經(jīng)度；緯度；時(shí)間。數(shù)據(jù)集的信息如表1所示。

表1 數(shù)據(jù)集信息

對(duì)于每一個(gè)數(shù)據(jù)集，本文都使用各個(gè)用戶80%的數(shù)據(jù)作為訓(xùn)練集，20%的數(shù)據(jù)作為測(cè)試集。

4.2 實(shí)驗(yàn)平臺(tái)

本文提出的神經(jīng)網(wǎng)絡(luò)模型以及比較的所有神經(jīng)網(wǎng)絡(luò)都基于Pytorch平臺(tái)運(yùn)行，且使用了一個(gè)Nvidia GTX1080Ti GPU來(lái)加速訓(xùn)練。

4.3 評(píng)價(jià)指標(biāo)和參數(shù)設(shè)置

為了公平比較，本文使用了精確度Top@k、召回率Recall、F1分?jǐn)?shù)(F1-score)和負(fù)對(duì)數(shù)似然Negative Log-Likelihood (NLL)來(lái)評(píng)價(jià)模型，其中NLL從損失函數(shù)角度來(lái)評(píng)價(jià)真實(shí)地點(diǎn)的分布和預(yù)測(cè)地點(diǎn)的分布之間的可能性。Recall和F1是分類(lèi)問(wèn)題中常用的兩個(gè)評(píng)價(jià)指標(biāo)，Top@k可以描述為預(yù)測(cè)結(jié)果中前k個(gè)最高概率結(jié)果的準(zhǔn)確率，定義l*(m)為輸入m的真實(shí)結(jié)果，Lk(m)為前k個(gè)預(yù)測(cè)的列表，那么Top@k可以描述為：

(11)

本文的對(duì)比模型包括傳統(tǒng)方法和幾個(gè)最近被提出的深度學(xué)習(xí)方法，包括：Markov模型；單個(gè)RNN神經(jīng)網(wǎng)絡(luò)(simple_rnn)：以LSTM為默認(rèn)結(jié)構(gòu)，用戶的全部軌跡作為該神經(jīng)網(wǎng)絡(luò)的輸入；SERM[11]：Yao等提出的一個(gè)結(jié)合了語(yǔ)義信息的循環(huán)神經(jīng)網(wǎng)絡(luò)；DeepMove[16]：Feng等提出了一個(gè)注意力機(jī)制考慮歷史軌跡的多層周期性。為了方便表示，本文初始模型表示為L(zhǎng)STM-LSTM，數(shù)據(jù)改進(jìn)方法表示為data_reverse，模型改進(jìn)方法表示為BLSTM-LSTM。不失一般性，每個(gè)模型都試驗(yàn)了3次并取其中的最大值比較。

本文的模型由兩個(gè)LSTM組成，因此需要設(shè)置每個(gè)神經(jīng)網(wǎng)絡(luò)。具體地，首先設(shè)置兩個(gè)LSTM網(wǎng)絡(luò)都為1層。并且，使兩個(gè)LSTM隱藏層的大小相同，這可以使解碼器更方便地處理編碼器的輸出。隨后，由于數(shù)據(jù)的稀疏性，本文在每個(gè)地點(diǎn)進(jìn)入模型之前使用嵌入層嵌入，嵌入層的維度與兩個(gè)LSTM隱藏層的大小相同。由于本文將該預(yù)測(cè)問(wèn)題看作一個(gè)分類(lèi)問(wèn)題，因此使用了NLLLoss計(jì)算真實(shí)地點(diǎn)和預(yù)測(cè)地點(diǎn)之間的誤差，最后使用Adam[22]算法作為優(yōu)化器。由于各個(gè)數(shù)據(jù)集參數(shù)都不相同，本文給出各個(gè)數(shù)據(jù)集的參數(shù)設(shè)置如表2所示。

表2 各個(gè)數(shù)據(jù)集使用的模型參數(shù)

4.4 結(jié)果分析

在Foursquare的兩個(gè)數(shù)據(jù)集上,各模型的Top@k結(jié)果如圖4和圖5所示，LSTM-LSTM結(jié)構(gòu)與傳統(tǒng)方法Markov和簡(jiǎn)單的深度學(xué)習(xí)方法simple_rnn進(jìn)行比較，可以看到Markov的性能最差，因?yàn)樗慕Y(jié)構(gòu)特點(diǎn)是下一個(gè)預(yù)測(cè)的地點(diǎn)只與前一個(gè)地點(diǎn)有關(guān)。simple_rnn由于其對(duì)過(guò)去位置的記憶而具有更好的性能。LSTM-LSTM結(jié)構(gòu)限制了各個(gè)子軌跡的長(zhǎng)度，使得LSTM能力沒(méi)有受到限制，因此性能表現(xiàn)最好。此外，LSTM-LSTM結(jié)構(gòu)同時(shí)考慮歷史軌跡和當(dāng)前軌跡，有效地減弱了長(zhǎng)歷史軌跡造成的影響。在Foursquare2010和Foursquare2012兩個(gè)數(shù)據(jù)集上，BiLSTM-LSTM結(jié)構(gòu)的Top@1精確度比simple_rnn分別提升31%和33%，Top@5精確度比simple_rnn分別提升33%和33%。

圖4 各個(gè)模型在Foursquare 2010上的Top@k結(jié)果

圖5 各個(gè)模型在Foursquare 2012上的Top@k結(jié)果

本文的改進(jìn)方法與SERM和DeepMove兩個(gè)深度學(xué)習(xí)方法對(duì)比，可以看到SERM僅在Top@5結(jié)果上優(yōu)于simple_rnn，但由于長(zhǎng)歷史軌跡使得LSTM能力受到限制，因此導(dǎo)致Top@1結(jié)果與simple_rnn幾乎相同。DeepMove相比SERM在兩個(gè)數(shù)據(jù)集上表現(xiàn)優(yōu)異,但沒(méi)有超過(guò)data_reverse方法和BLSTM-LSTM方法，這驗(yàn)證了數(shù)據(jù)逆置以及改進(jìn)模型對(duì)預(yù)測(cè)的有效性。BiLSTM-LSTM結(jié)構(gòu)相比DeepMove在兩個(gè)數(shù)據(jù)集上的提升效果分別為T(mén)op@1:7%和9%；Top@5:12%和9%。分析認(rèn)為，本文的改進(jìn)模型相較DeepMove取得更好的效果。原因在于模型更加簡(jiǎn)潔，這使得訓(xùn)練起來(lái)更加容易；編碼器-解碼器的連接方式，歷史軌跡的最后一個(gè)地點(diǎn)作為解碼器的初始輸入；編碼器的改進(jìn)增加了語(yǔ)義向量的參考信息，同時(shí)考慮了未來(lái)和過(guò)去的軌跡的影響，使得解碼器預(yù)測(cè)未來(lái)軌跡更加準(zhǔn)確。

在Gowalla數(shù)據(jù)集上，實(shí)驗(yàn)結(jié)果如圖6所示，可以得出與Foursquare兩個(gè)數(shù)據(jù)集上相同的結(jié)論。DeepMove相比簡(jiǎn)單的模型有著更好的表現(xiàn)效果，而本文的改進(jìn)方法相比DeepMove有了一定的提升。BLSTM-LSTM結(jié)構(gòu)在Gowalla數(shù)據(jù)集上相比DeepMove的提升效果為T(mén)op@1:9%；Top@5：11%。此外，本文還比較了兩個(gè)改進(jìn)方法的Recall、F1分?jǐn)?shù)和NLL在各個(gè)數(shù)據(jù)集上的表現(xiàn)，結(jié)果如表3所示?？梢钥闯觯珺iLSTM-LSTM結(jié)構(gòu)的Recall和F1分?jǐn)?shù)都是最高的，這表明了其分類(lèi)結(jié)果的準(zhǔn)確性最好。此外，BiLSTM-LSTM結(jié)構(gòu)的NLL值最低，也從損失函數(shù)的角度說(shuō)明了本文模型預(yù)測(cè)的準(zhǔn)確性。

圖6 各個(gè)模型在Gowalla上的Top@k結(jié)果

表3 各個(gè)數(shù)據(jù)集在其他指標(biāo)上的表現(xiàn)

續(xù)表3

由于本文數(shù)據(jù)集為多用戶數(shù)據(jù)集，本文模型對(duì)每個(gè)用戶預(yù)測(cè)未來(lái)軌跡并得到其預(yù)測(cè)精度。本文選用最重要的實(shí)驗(yàn)指標(biāo)Top@1生成所有用戶預(yù)測(cè)結(jié)果數(shù)據(jù)，隨后介紹其統(tǒng)計(jì)意義上的合理性。如圖7所示，本文比較了改進(jìn)模型BiLSTM-LSTM和DeepMove箱形圖上的結(jié)果?？梢钥吹剑疚母倪M(jìn)模型總體Top@1結(jié)果優(yōu)于對(duì)比模型。本文模型的下四分位線高于DeepMove模型，表示本文模型可預(yù)測(cè)的用戶數(shù)相對(duì)更多。此外本文模型異常值相比DeepMove也更多，這表明本文模型高準(zhǔn)確率用戶的數(shù)量增加，同時(shí)通過(guò)中位數(shù)的位置也驗(yàn)證了本文模型總體結(jié)果優(yōu)于對(duì)比模型。緊接著，本文使用t檢驗(yàn)驗(yàn)證了兩組預(yù)測(cè)結(jié)果的差異性。其中t值為-2.585表明DeepMove模型多用戶預(yù)測(cè)均值小于本文模型，p值為0.01表明有95%的概率假設(shè)兩組預(yù)測(cè)結(jié)果在統(tǒng)計(jì)意義上有顯著的差異。為了更清楚地表示p值變化規(guī)律，本文繪制了p值隨用戶數(shù)增加的變化圖。如圖8所示，從兩條曲線交叉點(diǎn)可以得到，當(dāng)用戶數(shù)大于700左右時(shí)，p值小于0.05。通過(guò)以上結(jié)果可以得到，兩組預(yù)測(cè)結(jié)果在均值上差異是顯著的，從統(tǒng)計(jì)意義上解釋了結(jié)果的合理性。

圖7 BiLSTM-LSTM與DeepMove箱形圖對(duì)比

圖8 p值變化曲線

本文還對(duì)比了各個(gè)模型的運(yùn)行效率，如圖9所示。可以看出本文改進(jìn)模型BiLSTM-LSTM最先收斂，且整體預(yù)測(cè)精度優(yōu)于改進(jìn)方法和對(duì)比模型，而DeepMove收斂最慢，且耗時(shí)最長(zhǎng)。這主要是因?yàn)樵撃Ｐ徒Y(jié)構(gòu)復(fù)雜，難以訓(xùn)練。本文模型及其改進(jìn)方法在前10個(gè)epoch中收斂都比較快，而后預(yù)測(cè)精度都趨于穩(wěn)定，這主要是本文模型結(jié)構(gòu)簡(jiǎn)單且易于訓(xùn)練的結(jié)果。

圖9 各個(gè)模型的收斂曲線

5 結(jié) 語(yǔ)

本文的主要貢獻(xiàn)如下：

(1) 提出一個(gè)基于編碼器-解碼器的軌跡預(yù)測(cè)模型，該模型同時(shí)考慮歷史軌跡和當(dāng)前軌跡，通過(guò)限制當(dāng)前軌跡的長(zhǎng)度，可以有效提高預(yù)測(cè)精確度。

(2) 針對(duì)冗長(zhǎng)的歷史軌跡改進(jìn)了編碼器的結(jié)構(gòu)，即使用BLSTM結(jié)構(gòu)。該結(jié)構(gòu)有效地豐富了歷史信息，通過(guò)正向傳播考慮移動(dòng)軌跡的順序轉(zhuǎn)換規(guī)律和時(shí)間依賴性關(guān)系，通過(guò)反向傳播考慮未來(lái)軌跡對(duì)當(dāng)前和過(guò)去軌跡造成的影響，有效地豐富了解碼器的參考語(yǔ)義向量。

(3) 在兩種測(cè)試數(shù)據(jù)集和一個(gè)世界真實(shí)數(shù)據(jù)集上實(shí)驗(yàn)，并與傳統(tǒng)方法和幾個(gè)近年被提出的深度學(xué)習(xí)方法相比，結(jié)果顯示本文模型更有效。

本文通過(guò)用戶歷史軌跡預(yù)測(cè)未來(lái)的軌跡。但是，數(shù)據(jù)集的稀疏性和過(guò)長(zhǎng)的軌跡導(dǎo)致預(yù)測(cè)準(zhǔn)確性比較差。因此，本文將用戶全部軌跡劃分為歷史軌跡和當(dāng)前軌跡，并且使用編碼器-解碼器模型來(lái)解決這個(gè)問(wèn)題。對(duì)于過(guò)長(zhǎng)的軌跡，本文使用數(shù)據(jù)逆置和BiLSTM-LSTM結(jié)構(gòu)來(lái)緩解早期遺忘的問(wèn)題。與傳統(tǒng)的預(yù)測(cè)方法和近年被提出的深度學(xué)習(xí)方法相比，本文方法顯示出更好的結(jié)果。本文方法仍有許多不足，如數(shù)據(jù)的特征過(guò)少，只靠嵌入矩陣還遠(yuǎn)遠(yuǎn)不夠，未來(lái)會(huì)加入語(yǔ)義信息如興趣點(diǎn)等來(lái)豐富數(shù)據(jù)的特征。