高 雅，江國華，秦小麟，王鐘毓

南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

1 引言

隨著以全球定位系統(tǒng)（global position system,GPS）為代表的定位技術(shù)的日趨成熟和普及，通過移動定位設(shè)備獲取到的移動對象軌跡數(shù)據(jù)越來越多。位置信息是用戶最為重要的上下文信息之一，可為各類服務(wù)和應(yīng)用提供重要支持，如智能交通系統(tǒng)（intelligent transport system，ITS）、智能導(dǎo)航系統(tǒng)、路線規(guī)劃、推薦系統(tǒng)[1]、公共設(shè)施規(guī)劃[2]和公共安全[3]等。大規(guī)?？捎眯詷O高的數(shù)據(jù)和基于位置服務(wù)（location based service，LBS）的應(yīng)用的發(fā)展，使移動對象的軌跡信息逐漸成為研究熱點(diǎn)。其中，位置預(yù)測是基于位置的服務(wù)的重要組成部分，提出有效方法以分析和預(yù)測移動對象位置具有重要意義。例如，在導(dǎo)航系統(tǒng)中，通過用戶的車載GPS記錄其歷史軌跡信息，挖掘其運(yùn)動模式并預(yù)測用戶的目的地，推薦不擁堵的最優(yōu)路線或尚有空位的停車場。在交通系統(tǒng)中，對城市車輛軌跡的位置預(yù)測有助于了解市民的出行規(guī)律，提前預(yù)知某一時(shí)段某一路線的交通狀況。在基于位置的信息投遞中，通過用戶的手持移動設(shè)備獲取用戶的歷史簽到數(shù)據(jù)，分析并預(yù)測用戶下一步的位置，手機(jī)應(yīng)用中的廣告推送功能可用此對其進(jìn)行相關(guān)的廣告投放。

移動對象位置預(yù)測的方法的實(shí)現(xiàn)步驟一般為：首先，抽象化真實(shí)數(shù)據(jù)，將地理位置信息和時(shí)間信息以易于處理的方式表示；然后，對抽象化后的軌跡數(shù)據(jù)建模，進(jìn)一步挖掘其運(yùn)動模式[4]；最后，對當(dāng)前用戶的輸入軌跡，根據(jù)習(xí)得的運(yùn)動模式，預(yù)測該用戶下一步最可能到達(dá)的位置。

基于移動對象軌跡數(shù)據(jù)的位置預(yù)測問題得到了廣泛的研究，其中，應(yīng)用較為廣泛的方法有：馬爾可夫鏈（Markov chain，MC）模型、軌跡頻繁模式挖掘和循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network，RNN）等。馬爾可夫模型通過計(jì)算用戶位置之間的轉(zhuǎn)換概率建立轉(zhuǎn)移矩陣，以推測下一步最可能到達(dá)的位置[5-6]。軌跡模式挖掘通過挖掘頻繁模式找出典型運(yùn)動模式[7]。循環(huán)神經(jīng)網(wǎng)絡(luò)通過隱藏層神經(jīng)元的連接性處理序列數(shù)據(jù)以學(xué)習(xí)運(yùn)動模型[8]。

雖然上述方法已經(jīng)在一些應(yīng)用場景中得到了很好的效果，但它們針對的都是短時(shí)間軌跡序列，沒有考慮到過長的歷史信息會帶來的維數(shù)災(zāi)難，不能解決長序列軌跡的位置預(yù)測問題。用戶的軌跡數(shù)據(jù)會隨時(shí)間的增長而變多，GPS的采樣周期短，收集到的數(shù)據(jù)多且連續(xù)，在學(xué)習(xí)預(yù)測模型前，應(yīng)對位置序列進(jìn)行預(yù)處理，通過網(wǎng)格化和分布式表示的方法，降低位置向量的維數(shù)。并且，傳統(tǒng)的方法如軌跡頻繁模式挖掘，普遍都是先將原始軌跡按密度聚類，將軌跡線段劃分到不同的類簇中，以聚類序列表示軌跡。這雖然能在保證劃分意義的前提下縮短序列長度，但基于密度的聚類方法不僅時(shí)間復(fù)雜度大，而且會忽略聚類區(qū)域之外的離散軌跡。

軌跡數(shù)據(jù)是有時(shí)間順序的時(shí)空數(shù)據(jù)，而神經(jīng)網(wǎng)絡(luò)被證明在處理時(shí)序數(shù)據(jù)的數(shù)據(jù)挖掘和預(yù)測方面效果最佳。但歷史信息具有時(shí)效性，考慮失效的歷史信息會產(chǎn)生梯度消失或梯度爆炸問題[9]，而忽略有效的歷史信息會導(dǎo)致模型精確度下降。長短期記憶網(wǎng)絡(luò)（long short-term memory，LSTM）[10]被證明是這一問題很好的解決方法。但LSTM也要求輸入低維度的向量，否則循環(huán)神經(jīng)網(wǎng)絡(luò)隱藏層和輸入層的神經(jīng)元之間的全連接屬性會導(dǎo)致嚴(yán)重的維數(shù)災(zāi)難，增大開銷，降低模型的學(xué)習(xí)效率。

針對上述問題，為了對移動對象的時(shí)空數(shù)據(jù)進(jìn)行更精確的建模從而進(jìn)一步預(yù)測其未來位置，本文提出了位置分布式表示模型（location distributed representation model，LDRM），將難以處理的高維位置onehot向量轉(zhuǎn)化為包含移動對象運(yùn)動模式的低維位置嵌入向量。在LDRM模型基礎(chǔ)上，與基于LSTM的位置預(yù)測算法結(jié)合為LDRM-LSTM移動位置預(yù)測算法。該算法在考慮移動對象行為具有相似性和時(shí)效性的基礎(chǔ)上，對歷史軌跡位置向量進(jìn)行降維，從而有效提高了預(yù)測模型的效率和精確度。

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

（1）提出了一種位置分布式表示模型LDRM，將難以處理的高維位置one-hot向量轉(zhuǎn)化為包含移動對象運(yùn)動模式的低維位置嵌入向量。在不忽略移動對象運(yùn)動規(guī)律的同時(shí)，有效降低了位置序列數(shù)據(jù)的維數(shù)，提高了訓(xùn)練模型的效率。

（2）考慮軌跡數(shù)據(jù)的時(shí)效性和移動對象行為的相似性，采用LSTM模型作為訓(xùn)練模型，學(xué)習(xí)一個(gè)全局的位置預(yù)測模型，提高了長序列軌跡數(shù)據(jù)的預(yù)測精度。

（3）實(shí)驗(yàn)所用的GPS軌跡數(shù)據(jù)為微軟亞洲研究院提供的真實(shí)數(shù)據(jù)集Geolife，并使用一系列量化指標(biāo)來評估預(yù)測得到的結(jié)果。實(shí)驗(yàn)結(jié)果證明，與現(xiàn)有的算法相比，提出的LDRM-LSTM算法的預(yù)測精度得到了明顯提升。

2 相關(guān)工作

隨著基于位置的服務(wù)的發(fā)展，移動對象位置預(yù)測的工作逐漸成為研究的熱點(diǎn)，國內(nèi)外研究者針對移動對象位置數(shù)據(jù)挖掘與預(yù)測已經(jīng)展開了相關(guān)研究。在移動對象位置預(yù)測中，通常的方法是通過移動對象歷史數(shù)據(jù)，預(yù)測移動對象的位置。

Koren等人[11]提出了基于矩陣因子分解的方法，通過分解包含地理位置信息的用戶行為矩陣判斷用戶最可能訪問的位置。Xiong等人[12]改進(jìn)了這一算法，通過張量分解（tensor factorization，TF）的方式，同時(shí)考慮歷史軌跡信息中的地理位置信息和時(shí)間信息。上述算法都基于對移動對象歷史訪問記錄的挖掘，沒有考慮當(dāng)前移動對象位置及軌跡，得到的預(yù)測精度不高。

Monreale等人[13]提出了WhereNext方法，從歷史軌跡數(shù)據(jù)中提取對象的軌跡模式，借此預(yù)測用戶頻繁訪問的位置，同時(shí)利用T-pattern tree查詢最佳匹配軌跡。Ying等人[14]提出了基于地理和軌跡的語義特征預(yù)測移動對象下一時(shí)刻位置信息的方法，該方法通過挖掘同類用戶的常見行為特性來預(yù)測其未來位置。Morzy[15]采用改進(jìn)的Apriori算法來生成關(guān)聯(lián)規(guī)則，并在后來的研究中利用改進(jìn)的PrefixSpan算法[16]通過移動軌跡序列頻繁項(xiàng)集來預(yù)測移動對象的位置[7]。然而，頻繁軌跡挖掘算法效率低下，數(shù)據(jù)每次更新都要重新挖掘頻繁軌跡，使預(yù)測效率降低。

馬爾可夫鏈（MC）模型利用移動對象的歷史軌跡預(yù)測位置，考慮軌跡的順序特征，使用馬爾可夫鏈描述移動對象在位置之間的轉(zhuǎn)移概率，Rendle等人[17]提出一種用因式分解轉(zhuǎn)移概率矩陣的方法擴(kuò)展了MC模型，在時(shí)空數(shù)據(jù)的位置預(yù)測上取得了很好的效果。Mathew等人[18]使用隱馬爾可夫模型（hidden Markov model，HMM）計(jì)算移動軌跡序列中的隱狀態(tài)來計(jì)算移動對象概率最高的下一個(gè)位置。但多階MC模型尤其是高階MC模型，當(dāng)數(shù)據(jù)增加時(shí)狀態(tài)會呈爆炸式增長，轉(zhuǎn)移概率矩陣規(guī)模的膨脹增加了預(yù)測的復(fù)雜度。

近年來，神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘與預(yù)測中的應(yīng)用逐漸廣泛。在神經(jīng)網(wǎng)絡(luò)模型中，RNN最適用于時(shí)序數(shù)據(jù)的預(yù)測。Liu等人[8]提出了ST-RNN（spatial temporal-RNN）算法，用移動對象歷史時(shí)空數(shù)據(jù)訓(xùn)練RNN網(wǎng)絡(luò)，預(yù)測用戶在某個(gè)時(shí)間點(diǎn)的位置。Al-Molegi等人[19]改進(jìn)了該算法，其提出的STF-RNN（spatial temporal featured-RNN）算法獲得了更好的預(yù)測準(zhǔn)確率。

然而傳統(tǒng)的RNN無法處理大量歷史數(shù)據(jù)的軌跡序列，過多的歷史數(shù)據(jù)會導(dǎo)致參數(shù)訓(xùn)練時(shí)的梯度消失、梯度爆炸和歷史信息損失等問題，改進(jìn)的LSTM則可以解決這些問題。LSTM在很多領(lǐng)域已經(jīng)獲得了一定的成果，如機(jī)器翻譯[20]、信息檢索[21]和圖像處理[22]等方面。Sutskever等人[20]提出了基于LSTM的神經(jīng)網(wǎng)絡(luò)語言模型，并運(yùn)用于自然語言處理方面，實(shí)現(xiàn)序列到序列（sequence to sequence）框架用于機(jī)器翻譯。Malhotra等人[23]將LSTM模型運(yùn)用于時(shí)序數(shù)據(jù)異常檢測領(lǐng)域，解決了無監(jiān)督環(huán)境下采集到非傳感器數(shù)據(jù)從而導(dǎo)致時(shí)間序列不可預(yù)測的問題，在對不可預(yù)測的時(shí)間序列和長時(shí)間序列的異常檢測中，取得了很好的效果。

Wu等人[24]提出了一種基于LSTM的時(shí)空語義算法（spatial-temporal-semantic neural network algorithm，STS-LSTM）對移動對象進(jìn)行位置預(yù)測。該算法提出一種特征提取的方法將路網(wǎng)軌跡轉(zhuǎn)化為離散位置點(diǎn)并用LSTM模型進(jìn)行位置預(yù)測，較傳統(tǒng)算法精確度有了明顯的提升，但該算法并沒有考慮到長時(shí)間序列的數(shù)據(jù)壓縮問題。

針對以上不足，本文提出一種基于LSTM的移動對象位置預(yù)測方法，利用LSTM模型解決長序列的位置預(yù)測問題，在學(xué)習(xí)預(yù)測模型前，先對歷史數(shù)據(jù)進(jìn)行了預(yù)處理，使軌跡的時(shí)空數(shù)據(jù)轉(zhuǎn)化為具有上下文信息且維數(shù)較低的神經(jīng)網(wǎng)絡(luò)輸入向量。擺脫了傳統(tǒng)位置預(yù)測算法的弊端，有效提高了預(yù)測精度和效率。

3 算法描述

LDRM-LSTM算法整體框架如圖1所示，算法由三部分組成，即用于將軌跡數(shù)據(jù)轉(zhuǎn)化為位置序列的預(yù)處理部分，對高維位置向量進(jìn)行降維處理的位置分布式表示模型LDRM部分和基于LSTM的根據(jù)歷史位置序列學(xué)習(xí)運(yùn)動模式的預(yù)測模型部分。下面將用3節(jié)對這三部分進(jìn)行詳細(xì)的說明。

本章所用的軌跡數(shù)據(jù)的符號表示及說明如表1所示。

Table 1 Description of symbol definition表1 符號定義說明

3.1 軌跡數(shù)據(jù)預(yù)處理

移動對象軌跡數(shù)據(jù)通常由GPS采集?？紤]軌跡數(shù)據(jù)的結(jié)構(gòu)，經(jīng)過采樣生成的一條軌跡可以表示為一系列的位置點(diǎn)的集合。由于采集的點(diǎn)的序列，在時(shí)間空間上相對緊密，難以從中挖掘出其運(yùn)動的模式。如圖2中的兩條軌跡P（實(shí)線軌跡）與P′（虛線軌跡），很難從中發(fā)現(xiàn)明顯的普遍特征，那么對于大量的如此表現(xiàn)形式的軌跡，就更難挖掘出其中的模式進(jìn)行預(yù)測。因此在移動對象位置預(yù)測之前，必須對原始軌跡數(shù)據(jù)進(jìn)行預(yù)處理。

網(wǎng)格化是研究移動對象軌跡常用的方式，其核心思想是將移動對象所在平面劃分為網(wǎng)格，將精確但冗余的經(jīng)緯度信息轉(zhuǎn)化為抽象的網(wǎng)格信息，以便對移動對象軌跡進(jìn)行預(yù)測。如圖2右圖所示，通過網(wǎng)格將復(fù)雜的軌跡P與P′轉(zhuǎn)化為相同的軌跡L1→L2→L4→L3，更能抽象地表示移動對象的運(yùn)動過程。

Fig.1 Overall framework of LDRM-LSTM圖1 LDRM-LSTM算法整體框架

Fig.2 Trajectory data gridding圖2 軌跡數(shù)據(jù)網(wǎng)格化

采用Geohash編碼對軌跡進(jìn)行網(wǎng)格化。Geohash由Niemeyer提出，最初用于geohash.org服務(wù)中，目的是為地球上每一個(gè)位置提供一條短URL作為唯一標(biāo)識[25]。Geohash編碼的基本原理是將地球視為二維平面，把該平面沿經(jīng)度和維度的方向遞歸二分為更小的子平面，使平面被網(wǎng)格化為子平面的集合，每個(gè)子平面在一定經(jīng)緯度范圍內(nèi)擁有相同的Geohash編碼。根據(jù)Geohash編碼方案，其編碼具有唯一性，即Geohash的每個(gè)單元網(wǎng)格在地球表面均有唯一空間區(qū)域與之對應(yīng)，這種特性便于對軌跡數(shù)據(jù)進(jìn)行無歧義的網(wǎng)格序列化。

使用Geohash編碼將軌跡所在地區(qū)分為n個(gè)網(wǎng)格，第i個(gè)網(wǎng)格編碼為Li(1≤i≤n)，每個(gè)網(wǎng)格代表一個(gè)位置。由于GPS數(shù)據(jù)采集的時(shí)候可能有誤差，有些網(wǎng)格只有極少數(shù)軌跡點(diǎn)存在其中，需要將其作為離群點(diǎn)剔除。因此，設(shè)計(jì)算軌跡經(jīng)過編號為Li的網(wǎng)格的軌跡點(diǎn)個(gè)數(shù)為，若大于網(wǎng)格最小有效軌跡點(diǎn)數(shù)δ，則將該網(wǎng)格編碼Li與來到該網(wǎng)格的時(shí)刻ti構(gòu)成的二元組加入帶時(shí)間屬性的位置序列T，如式（1）所示。

根據(jù)式（1），將原始軌跡數(shù)據(jù)轉(zhuǎn)化為帶時(shí)間屬性的位置序列T。然而，GPS軌跡采集過程通常是連續(xù)很長一段時(shí)間，導(dǎo)致T過長，并且其中有些二元組之間的時(shí)間間隔過大，對位置預(yù)測有較大影響。因此，需要通過時(shí)間閾值將位置序列T分段。設(shè)第k段帶時(shí)間屬性的位置序列Tk={＜Lk,tk＞,＜Lk+1,tk+1＞,…,＜Lk+l,tk+l＞},其中存在時(shí)間點(diǎn)ti，有ti+1-ti＞γ，則將位置序列Tk分為Ta和Tb兩個(gè)子序列，用時(shí)間點(diǎn)ti分割原序列，分割后的兩個(gè)子序列Ta={＜Lk,tk＞,＜Lk+1,tk+1＞,…,＜Li,ti＞},Tb={＜Li+1,ti+1＞,＜Li+2,ti+2＞,…,＜Lk+l,tk+l＞}，其中，k＜i＜l。

通過上述算法，將移動對象原始軌跡數(shù)據(jù)轉(zhuǎn)化為h個(gè)位置序列，構(gòu)成位置序列集合H={T1,T2,…,Th}。同時(shí)，構(gòu)建n個(gè)移動對象位置組成的集合S={L1,L2,…,Ln}。移動對象位置預(yù)測問題如定義1所示。

定義1（移動對象位置預(yù)測問題）設(shè)h個(gè)歷史位置序列組成的歷史軌跡集合H={T1,T2,…,Th}，當(dāng)前軌跡為T′={＜Li,ti＞},0≤i≤t，預(yù)測移動對象在t+1所在的位置Lt+1。

3.2 位置分布式表示模型LDRM

將移動對象軌跡數(shù)據(jù)轉(zhuǎn)化為位置序列后，由于位置信息是離散的Geohash編碼，無法直接進(jìn)行訓(xùn)練，需要將編碼轉(zhuǎn)化為向量。通用的離散值轉(zhuǎn)為向量的方法是one-hot編碼，即對于n個(gè)位置的集合S={L1,L2,…,Ln}，對于每一個(gè)位置Li，構(gòu)建一個(gè)零向量，將其第i維賦值為“1”，即只有這一位有效，其他位均為“0”。如位置L1的可表示為：(1,0,0,0,…)，這個(gè)稀疏的向量即為該位置的one-hot編碼。這種編碼將離散的位置編碼轉(zhuǎn)化為向量，解決了模型無法處理離散數(shù)據(jù)的問題。但是這種編碼也存在著問題：（1）在數(shù)據(jù)量大、不同位置多的情況下，容易受維數(shù)災(zāi)難的困擾；（2）不能很好地描述位置之間的關(guān)系，也不能體現(xiàn)出移動對象的運(yùn)動模式。

針對one-hot存在的問題，采取分布式表示（distributed representation）的方法，提出了位置分布式表示模型LDRM，將包含位置信息的one-hot編碼通過神經(jīng)網(wǎng)絡(luò)轉(zhuǎn)化為低維度的含有位置上下文信息的位置嵌入向量（location embedding vector，LEV），避免了由于位置過多帶來的維數(shù)災(zāi)難問題。

移動對象的運(yùn)動往往存在某種隱藏的規(guī)律，即某些移動對象序列會以較高概率出現(xiàn)。設(shè)一個(gè)長度為N的位置序列出現(xiàn)概率為P=(L1,L2,…,LN)，在理想狀態(tài)下，即移動對象出現(xiàn)在每個(gè)位置的概率相互獨(dú)立時(shí)，計(jì)算公式如式（2）所示。

但這樣的假設(shè)太過理想化，因?yàn)橐苿訉ο螽?dāng)前位置與其之前位置是相關(guān)的。假設(shè)在一段位置序列中，移動對象的位置和前t個(gè)位置有關(guān)，如式（3）所示。

LDRM模型在對位置one-hot向量降維的同時(shí)，從軌跡未知序列中挖掘位置之間的關(guān)系，使得P(Li|Li-t,Li-t+1,…,Li-1)最大化，從而將序列中的運(yùn)動模式隱含到位置嵌入向量中。

設(shè)移動對象位置序列共有n個(gè)位置，則每個(gè)位置構(gòu)成一個(gè)n維的one-hot向量l，每個(gè)one-hot向量對應(yīng)一個(gè)m維的位置嵌入向量。LDRM模型神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示。

Fig.3 Structure of LDRM neural network圖3 LDRM神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

設(shè)當(dāng)前位置編號為i，對應(yīng)的one-hot向量為li，和當(dāng)前位置相關(guān)的位置為{li-t,li-t+1,…,li-1}。假設(shè)當(dāng)前存在輸入矩陣V∈Rm×n，根據(jù)式（4）可計(jì)算投影層每個(gè)位置嵌入向量{ei-t,ei-t+1,…,ei-1}。

在移動對象位置序列中，不同位置的重要程度不同，比如熱門景點(diǎn)、商場、學(xué)校、醫(yī)院等對下一個(gè)位置的影響要明顯高于一般位置。故給每一個(gè)位置根據(jù)其在所有軌跡中出現(xiàn)的次數(shù)賦予一個(gè)權(quán)值wi，計(jì)算方式如式（5）所示。

將前i個(gè)位置的嵌入向量通過式（6）計(jì)算出當(dāng)前位置的嵌入向量ei。

設(shè)輸出矩陣U∈Rn×m，當(dāng)前位置的嵌入向量經(jīng)過輸出矩陣的變換成為n維輸出向量。輸出層將嵌入向量轉(zhuǎn)化為輸出向量的計(jì)算方式如式（7）所示。

為n維輸出向量，理想狀態(tài)下的輸出向量oi應(yīng)該和當(dāng)前位置的one-hot向量相等，即oi=li。在這種情況下，該模型的損失函數(shù)交叉熵（cross entropy）的計(jì)算方式如式（8）所示。

由于模型輸出為離散的one-hot向量，若直接使用交叉熵作為目標(biāo)函數(shù)，會造成模型泛化性嚴(yán)重下降。因此，定義該模型的目標(biāo)函數(shù)如式（9）所示。其中，ui為輸出矩陣U的第i行，表示li的輸出向量。

使用梯度下降的方法，計(jì)算ui和ei，即可得到矩陣V和U。通過公式e=Vl，即可計(jì)算每個(gè)one-hot向量對應(yīng)的位置嵌入向量。位置嵌入向量的總體計(jì)算流程如算法1所示。

算法1LDRM算法

輸入：每個(gè)位置one-hot向量集合Sonehot，軌跡序列集合Strajectory，相關(guān)位置數(shù)t。

輸出：每個(gè)位置對應(yīng)的位置嵌入向量構(gòu)成的集合SLEV。

1.Trainingset=[];//構(gòu)建訓(xùn)練數(shù)據(jù)集及其標(biāo)簽，初始值為空

2.For eachliinSonehot//遍歷one-hot向量集合

3.For eachTjinStrajectory//遍歷軌跡序列集合

4.IfliinTjand the order ofliisk//如果當(dāng)前位置在當(dāng)前軌跡序列中出現(xiàn)，且是當(dāng)前軌跡序列中第k個(gè)位置

5.Thendata={li-t,li-t+1,…,li-1}，label=li//當(dāng)前位置的前t個(gè)位置為訓(xùn)練數(shù)據(jù)，當(dāng)前位置為標(biāo)簽

6.add{data,label}intoTrainingset//存儲訓(xùn)練數(shù)據(jù)與標(biāo)簽

7.Whileepoch＜epochround//當(dāng)訓(xùn)練未完成時(shí)

8.For each{data,lable}inTrainingset//遍歷構(gòu)建的數(shù)據(jù)集

9.Input{data,lable}into Nerual Network//將數(shù)據(jù)與標(biāo)簽放入神經(jīng)網(wǎng)絡(luò)

10.Calculate functionJ//計(jì)算目標(biāo)函數(shù)

11.Backpropagation parameterUandV//反向傳播調(diào)整參數(shù)U和V

12.For eachliinSonehot

13.ei=U?li//對于每一個(gè)one-hot向量，計(jì)算對應(yīng)的位置嵌入向量

14.AddeitoSLEV//存儲計(jì)算結(jié)果

算法1計(jì)算了每個(gè)位置one-hot向量構(gòu)成的位置嵌入向量。計(jì)算過程分為三個(gè)主要部分：首先通過遍歷位置one-hot向量集合和軌跡序列集合構(gòu)建訓(xùn)練集；然后使用該訓(xùn)練集訓(xùn)練LDRM神經(jīng)網(wǎng)絡(luò)參數(shù)U和V；最后通過該參數(shù)計(jì)算每個(gè)位置的位置嵌入向量。

3.3 基于LSTM的位置預(yù)測算法

LSTM模型是一種RNN的變型，由記憶單元（memory cell）和多個(gè)調(diào)節(jié)門（gate）組成。LSTM使用記憶單元的狀態(tài)（state）來保存歷史信息，使用輸入門（input gate）、輸出門（output gate）和遺忘門（forget gate）來控制記憶單元。利用調(diào)節(jié)門來選擇信息，可表示為y(x)=σ(Wx+b)，其中W表示權(quán)重矩陣，b表示偏移向量。由于傳統(tǒng)的RNN展開后相當(dāng)于多層的前饋神經(jīng)網(wǎng)絡(luò)，層數(shù)對應(yīng)于歷史數(shù)據(jù)的數(shù)量，過多的歷史數(shù)據(jù)會導(dǎo)致參數(shù)訓(xùn)練時(shí)的梯度消失、梯度爆炸和歷史信息損失等問題，在處理大量歷史數(shù)據(jù)的預(yù)測問題上，LSTM被證明比RNN具有更好的表現(xiàn)。

LSTM的單元結(jié)構(gòu)如圖4所示，設(shè)xt、ht為t時(shí)刻的輸入和輸出數(shù)據(jù)，i、f和o分別為輸入層、遺忘層和輸出層，Ct為t時(shí)刻記憶單元的狀態(tài)值。LSTM單元的更新可分為如下幾個(gè)步驟。

Fig.4 Structure of LSTM network圖4 LSTM單元結(jié)構(gòu)圖

（1）決定從上一狀態(tài)中丟棄什么信息。遺忘門是用于控制歷史信息對當(dāng)前記憶單元狀態(tài)值的影響的，因此通過遺忘門來計(jì)算ft，如式（10）所示。其中Wf表示遺忘門的權(quán)重矩陣，bf表示遺忘門的偏移向量。σ是logistic sigmoid激活函數(shù)，取值在（0,1）之間，1表示“全部保留”，0表示“全部丟棄”。

（2）決定什么信息被存入當(dāng)前狀態(tài)中。輸入門是用于控制當(dāng)前輸入對記憶單元狀態(tài)值的影響的，因此通過輸入門來計(jì)算it，如式（11）所示。按照傳統(tǒng)的RNN公式計(jì)算當(dāng)前時(shí)刻的候選記憶單元值C?t，其中函數(shù)tanh的取值范圍在（-1,1）之間。

（3）決定好丟棄和更新什么信息后，執(zhí)行記憶單元的更新，計(jì)算當(dāng)前時(shí)刻記憶單元的狀態(tài)值Ct，如式（12）所示，⊙是點(diǎn)乘運(yùn)算。

（4）確定輸出值。輸出門用于控制記憶單元狀態(tài)值的輸出，用sigmoid函數(shù)計(jì)算決定輸出的部分，如式（13）所示。將通過tanh函數(shù)處理的記憶單元狀態(tài)與結(jié)果ot相乘，得到LSTM單元在t時(shí)刻的輸出ht。

經(jīng)過LSTM根據(jù)訓(xùn)練數(shù)據(jù)調(diào)整神經(jīng)元之間的權(quán)重的學(xué)習(xí)過程[26]，得到一個(gè)全局的位置預(yù)測模型。通過上述門控機(jī)制，LSTM解決了RNN處理長序列容易發(fā)生的梯度消失、梯度爆炸和歷史信息損失等問題，在移動對象位置預(yù)測方面有更好的表現(xiàn)。

使用LDRM模型對位置序列進(jìn)行降維后，難以處理的高維one-hot向量被轉(zhuǎn)化為低維度的含上下文信息的位置嵌入向量，從而使得基于LSTM的位置預(yù)測算法可以更好地處理移動對象位置預(yù)測問題。

設(shè)降維后的位置嵌入向量集合為SLEV={e1,e2,…,en}，則移動對象位置序列可以轉(zhuǎn)化為由嵌入向量組成的序列。但放入LSTM模型中的每個(gè)序列的長度必須相同，因此采取滑動窗口的方式，將所有的軌跡轉(zhuǎn)化為可訓(xùn)練的固定長度的輸入與輸出樣本集，如圖5所示。

Fig.5 Generate sample set using sliding window method圖5 滑動窗口法生成樣本集

將經(jīng)過LDRM模型降維的歷史位置嵌入向量作為LSTM模型的輸入，訓(xùn)練出針對移動對象位置預(yù)測問題的LSTM模型。將待預(yù)測位置嵌入向量序列輸入模型得到輸出向量eoutput，將eoutput與E中所有位置嵌入向量計(jì)算歐式距離，與eoutput距離最小的位置嵌入向量即為預(yù)測結(jié)果eresult。模型的位置預(yù)測結(jié)果即為eresult對應(yīng)的位置one-hot向量lresult。

算法2LSTM位置預(yù)測算法

輸入：位置嵌入向量集合SLEV，軌跡序列集合Strajectory，待預(yù)測位置序列Ttest。

輸出：預(yù)測結(jié)果的one-hot向量lresult。

1.Trainingset=[]；//構(gòu)建訓(xùn)練數(shù)據(jù)集及其標(biāo)簽，初始值為空

2.For eachTiinStrajectory

3.For slide windowTs={la,la+1,…,lb}inTi//通過滑動窗口方式構(gòu)建子序列

4.Extractdata={ea,ea+1,…,eb-1l},abel=ebfromTs//將子序列中one-hot向量轉(zhuǎn)化為位置嵌入向量，并構(gòu)建訓(xùn)練數(shù)據(jù)與標(biāo)簽

5.Add{data,label}toTrainingset//保存訓(xùn)練數(shù)據(jù)與標(biāo)簽

6.Whileepoch＜epochround//當(dāng)訓(xùn)練未完成時(shí)

7.For each{data,lable}inTrainingset

8.Input{data,lable}into LSTM neural network//將訓(xùn)練數(shù)據(jù)與標(biāo)簽輸入LSTM網(wǎng)絡(luò)

9.Calculate bias function of LSTM//計(jì)算誤差函數(shù)

10.Backpropagation parameters//反向傳播調(diào)整網(wǎng)絡(luò)參數(shù)

11.InputTtestinto LSTM Network get result embedding vectoreoutput//將測試數(shù)據(jù)輸入網(wǎng)絡(luò)得到輸出的位置嵌入 向量

12.For eacheiinSLEV

13.Finderesult=ei,for which distance ofeiandeoutputis minimum//在位置嵌入向量集中尋找距離最近的向量

14.Output correspondinglresultoferesult//將距離最近的向量轉(zhuǎn)化為one-hot向量并輸出

LSTM位置預(yù)測算法的流程如算法2所示。首先通過滑動窗口將軌跡數(shù)據(jù)分割并轉(zhuǎn)化為訓(xùn)練集。然后通過訓(xùn)練集訓(xùn)練LSTM神經(jīng)網(wǎng)絡(luò)，最后將待預(yù)測軌跡輸入LSTM神經(jīng)網(wǎng)絡(luò)中，得到輸出的位置嵌入向量，并篩選與該向量距離最近的位置嵌入向量，該向量對應(yīng)的位置即為預(yù)測的位置。

由算法1與算法2可見，LDRM-LSTM算法采用了離線訓(xùn)練在線預(yù)測流程結(jié)構(gòu)，即在預(yù)測前將模型參數(shù)訓(xùn)練完成，在預(yù)測時(shí)僅需要計(jì)算預(yù)測結(jié)果即可。這種方式的優(yōu)點(diǎn)為將耗時(shí)操作在預(yù)測前完成，預(yù)測時(shí)的時(shí)間復(fù)雜度極低。本文中，LDRM降維模型和LSTM預(yù)測模型均由歷史軌跡數(shù)據(jù)離線訓(xùn)練得出，在進(jìn)行軌跡數(shù)據(jù)預(yù)測時(shí)只需將待預(yù)測軌跡數(shù)據(jù)進(jìn)行預(yù)處理后輸入模型即可得到預(yù)測結(jié)果，具有很強(qiáng)的實(shí)用性。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

為了驗(yàn)證移動對象位置預(yù)測算法的預(yù)測準(zhǔn)確性，使用微軟亞洲研究院的Geolife project數(shù)據(jù)進(jìn)行測試。該數(shù)據(jù)集包括182個(gè)用戶5年間（從2007年4月到2012年8月）的運(yùn)動軌跡數(shù)據(jù)。數(shù)據(jù)集覆蓋中國、美國和歐洲的不同城市，大部分?jǐn)?shù)據(jù)是在北京采集的。軌跡數(shù)據(jù)數(shù)量為18 670條數(shù)據(jù)，覆蓋長達(dá)50 176 h的時(shí)間和1 292 951 km的距離。軌跡是通過帶GPS功能的手機(jī)采集而來，每隔1到5 s采集一次位置數(shù)據(jù)。軌跡信息中包含經(jīng)緯度、時(shí)間等信息。

實(shí)驗(yàn)操作系統(tǒng)為ubuntu14.04（64 bit），CPU為Intel Core i5-3470，內(nèi)存為16 GB，顯卡為NVIDIAGTX970，實(shí)驗(yàn)代碼用python編程語言實(shí)現(xiàn)。

4.2 預(yù)測評價(jià)標(biāo)準(zhǔn)

定義2絕對預(yù)測精度（absolute precision，AP）即預(yù)測結(jié)果和真實(shí)結(jié)果的差距。設(shè)共有K個(gè)測試樣本，第i個(gè)樣本的預(yù)測結(jié)果為pli，真實(shí)結(jié)果為li。絕對預(yù)測精度分?jǐn)?shù)ScoreAP如式（14）所示。

由于絕對預(yù)測精度的要求較為苛刻，無法對算法在預(yù)測不完全精確的情況下的預(yù)測結(jié)果優(yōu)劣進(jìn)行比較。因此實(shí)驗(yàn)同時(shí)使用相對預(yù)測精度來進(jìn)行預(yù)測精度度量。

定義3相對預(yù)測精度（relative precision，RP）即在預(yù)測不完全精確的情況下，對預(yù)測偏離度進(jìn)行量化度量的一種精度，計(jì)算方式如式（15）所示[27]。

由于每個(gè)位置是大小相等的網(wǎng)格，因此可以將每個(gè)網(wǎng)格視為坐標(biāo)軸上1×1的單元格。故式（15）中的距離函數(shù)dist采用曼哈頓距離計(jì)算兩個(gè)網(wǎng)格之間的距離。在預(yù)測結(jié)果非絕對精確時(shí)，設(shè)定相對預(yù)測精度可以通過其與真實(shí)位置的距離偏差來選擇相對精確的預(yù)測點(diǎn)，ScoreAP越低，表示預(yù)測精度越高。

4.3 軌跡數(shù)據(jù)預(yù)處理與樣本集生成

從原始數(shù)據(jù)中，提取出在北京的13 101條軌跡，使用6位Geohash編碼對軌跡進(jìn)行網(wǎng)格化（約600 m×600 m網(wǎng)格），共生成14 777個(gè)不同的位置。將經(jīng)緯度軌跡轉(zhuǎn)化為位置序列并分段，設(shè)分段時(shí)間閾值為30 min，位置包含最小有效軌跡點(diǎn)數(shù)為10。

通過上述方式，將原始軌跡轉(zhuǎn)化為21 740條位置序列。對提取出的位置序列，使用滑動窗口的方式生成樣本集。設(shè)滑動窗口長度len=8，滑動步長step=3，除去長度小于len的位置序列后，得到69 537個(gè)樣本，隨機(jī)取其中的5 000個(gè)樣本作為測試集，其余數(shù)據(jù)作為訓(xùn)練集。軌跡預(yù)處理的參數(shù)選擇總結(jié)如表2所示。

4.4 LDRM模型性能分析

Table 2 Parameters of trajectory preprocess表2 軌跡預(yù)處理參數(shù)

通過預(yù)處理與樣本集生成，將原始Geolife數(shù)據(jù)轉(zhuǎn)化為軌跡位置序列訓(xùn)練集與測試集。在進(jìn)行預(yù)測之前，需要使用軌跡位置序列訓(xùn)練集對LDRM位置降維模型進(jìn)行訓(xùn)練。由于數(shù)據(jù)集中存在14 777個(gè)位置，即輸入的位置one-hot向量的維度n=14 777。設(shè)LDRM降維得到的位置嵌入向量的維度為m。位置嵌入向量維度m對預(yù)測結(jié)果有較大影響，過大的位置嵌入向量維度仍然會導(dǎo)致一定程度的維數(shù)災(zāi)難問題，過小的位置嵌入向量維度會造成大量的信息在降維中損失，都會導(dǎo)致預(yù)測維度下降。因此，將m的取值范圍預(yù)設(shè)為50到500，步長為50。通過對訓(xùn)練集進(jìn)行交叉驗(yàn)證計(jì)算絕對精度與相對精度，計(jì)算m的取值對LDRM-LSTM位置預(yù)測算法的效果的影響，實(shí)驗(yàn)結(jié)果如圖6和圖7所示。

由圖6和圖7可見，位置嵌入向量在100～150維之間時(shí)，預(yù)測結(jié)果與真實(shí)結(jié)果的絕對差距最小，相對偏離度最小，即絕對精度和相對精度均達(dá)到最佳，預(yù)測效果最好。由于絕對精度與相對精度相比更為重要，因此取絕對精度最高的100維作為降維后位置嵌入向量的維度。為了方便觀察嵌入向量空間分布，將位置嵌入向量經(jīng)過主成分分析（principal component analysis，PCA）降維到二維后，部分位置嵌入向量在二維向量空間中的分布如圖8所示。每個(gè)位置點(diǎn)上的標(biāo)簽為各自的Geohash編碼，圖中越接近的兩個(gè)空間向量，代表其在運(yùn)動軌跡中越相關(guān)。

Fig.7 Relative precision of LDRM-LSTM in different dimensions圖7 不同維度下LDRM-LSTM預(yù)測的相對精度

Fig.8 Graph of location embedding representation圖8 位置嵌入向量空間分布示意圖

4.5 LSTM位置預(yù)測算法結(jié)果與分析

在確定了最優(yōu)的嵌入向量維度并在將訓(xùn)練集與測試集中位置序列均轉(zhuǎn)化為位置嵌入向量序列后，使用訓(xùn)練集中降維后的位置嵌入向量序列對LSTM神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，再使用訓(xùn)練后的模型對測試集中的待預(yù)測的位置嵌入向量序列進(jìn)行位置預(yù)測。將預(yù)測結(jié)果與真實(shí)值相對照，計(jì)算絕對精度與相對精度，并與HMM、MC、XGBoost（extreme gradient boosting）[28]、LSTM以及STS-LSTM等現(xiàn)有算法在同一樣本集上進(jìn)行對比。這些算法均為離線訓(xùn)練在線預(yù)測算法，離線訓(xùn)練時(shí)間和參數(shù)相關(guān)，在線預(yù)測時(shí)間復(fù)雜度幾乎一致。實(shí)驗(yàn)結(jié)果如表3所示。

Table 3 Results of location prediction表3 位置預(yù)測結(jié)果

由表3可見，LDRM-LSTM算法的絕對預(yù)測精度和相對預(yù)測精度遠(yuǎn)遠(yuǎn)高于未采用降維算法的LSTM模型，證明LDRM降維模型較好地解決了維度災(zāi)難問題。同時(shí)，LDRM-LSTM預(yù)測絕對精度和相對精度均高于所列出的經(jīng)典位置預(yù)測算法，說明在解決長序列位置預(yù)測的問題上，LDRM-LSTM算法可以克服現(xiàn)有算法存在的弊端，得到較好的預(yù)測結(jié)果。

5 結(jié)束語

移動對象位置預(yù)測與運(yùn)動模式挖掘一直是研究的熱點(diǎn)，可為各類基于位置的服務(wù)和應(yīng)用提供重要支持，如智能交通系統(tǒng)、智能導(dǎo)航系統(tǒng)、路線規(guī)劃等，具有很高的實(shí)用性和現(xiàn)實(shí)意義。傳統(tǒng)的基于Markov概率模型的位置預(yù)測算法和基于神經(jīng)網(wǎng)絡(luò)的位置預(yù)測算法無法處理位置過多帶來的維數(shù)災(zāi)難問題。提出了LDRM模型，通過神經(jīng)網(wǎng)絡(luò)挖掘移動對象軌跡數(shù)據(jù)中的隱含規(guī)律，將原始的高維one-hot向量轉(zhuǎn)化為低維度的位置嵌入向量，再通過基于LSTM的移動對象位置預(yù)測算法進(jìn)行位置預(yù)測。實(shí)驗(yàn)證明本文提出的LDRM-LSTM算法預(yù)測準(zhǔn)確率高于經(jīng)典的MC、HMM、RNN及XGBoost等算法。同時(shí)，算法采用離線訓(xùn)練在線預(yù)測的流程結(jié)構(gòu)，使用歷史數(shù)據(jù)訓(xùn)練的模型進(jìn)行位置預(yù)測，在實(shí)際應(yīng)用中有較高的價(jià)值。