基于編碼器-解碼器模型的人群移動預測分析

陳建偉 李建波

(青島大學計算機科學技術學院 山東 青島 266071)

0 引 言

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

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

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

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

1 相關工作

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

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

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

2 移動軌跡問題的LSTM模型

2.1 問題定義

本文首先收集每個用戶的移動軌跡，軌跡全部按照時間順序排列。因此，用戶ux軌跡定義為:

(1)

2.2 RNN和LSTM

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

在標準RNN結構中，隱藏層中的神經元建立權重連接，因此RNN擁有“記憶”。但是當序列太長時，早期的輸入對后來的輸入影響較小，這導致了梯度消失問題。為了解決這個問題，RNN的變體LSTM和GRU被提出?，F(xiàn)在，LSTM被廣泛用于長輸入問題。本文模型基于LSTM結構，式(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是各個控制門的權重矩陣；b為偏置向量，ct是t時刻存儲在神經元中的值；ht是隱藏層在t時刻的輸出；⊙表示點積。

3 基于編碼器-解碼器的位置預測模型

3.1 模型結構

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

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

圖1 編碼器-解碼器模型

ct=f(xt,ct-1)

(8)

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

(9)

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

p(y1)=z(ct,xt)

(10)

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

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

圖2 預測模型整體結構

3.2 訓練集準備

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

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

3.3 新的問題

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

3.4 改進方法

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

4 實 驗

4.1 數(shù)據集

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

表1 數(shù)據集信息

對于每一個數(shù)據集，本文都使用各個用戶80%的數(shù)據作為訓練集，20%的數(shù)據作為測試集。

4.2 實驗平臺

本文提出的神經網絡模型以及比較的所有神經網絡都基于Pytorch平臺運行，且使用了一個Nvidia GTX1080Ti GPU來加速訓練。

4.3 評價指標和參數(shù)設置

為了公平比較，本文使用了精確度Top@k、召回率Recall、F1分數(shù)(F1-score)和負對數(shù)似然Negative Log-Likelihood (NLL)來評價模型，其中NLL從損失函數(shù)角度來評價真實地點的分布和預測地點的分布之間的可能性。Recall和F1是分類問題中常用的兩個評價指標，Top@k可以描述為預測結果中前k個最高概率結果的準確率，定義l*(m)為輸入m的真實結果，Lk(m)為前k個預測的列表，那么Top@k可以描述為：

(11)

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

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

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

4.4 結果分析

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

圖4 各個模型在Foursquare 2010上的Top@k結果

圖5 各個模型在Foursquare 2012上的Top@k結果

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

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

圖6 各個模型在Gowalla上的Top@k結果

表3 各個數(shù)據集在其他指標上的表現(xiàn)

續(xù)表3

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

圖7 BiLSTM-LSTM與DeepMove箱形圖對比

圖8 p值變化曲線

本文還對比了各個模型的運行效率，如圖9所示。可以看出本文改進模型BiLSTM-LSTM最先收斂，且整體預測精度優(yōu)于改進方法和對比模型，而DeepMove收斂最慢，且耗時最長。這主要是因為該模型結構復雜，難以訓練。本文模型及其改進方法在前10個epoch中收斂都比較快，而后預測精度都趨于穩(wěn)定，這主要是本文模型結構簡單且易于訓練的結果。

圖9 各個模型的收斂曲線

5 結 語

本文的主要貢獻如下：

(1) 提出一個基于編碼器-解碼器的軌跡預測模型，該模型同時考慮歷史軌跡和當前軌跡，通過限制當前軌跡的長度，可以有效提高預測精確度。

(2) 針對冗長的歷史軌跡改進了編碼器的結構，即使用BLSTM結構。該結構有效地豐富了歷史信息，通過正向傳播考慮移動軌跡的順序轉換規(guī)律和時間依賴性關系，通過反向傳播考慮未來軌跡對當前和過去軌跡造成的影響，有效地豐富了解碼器的參考語義向量。

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

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