基于位置轉移時空規律的用戶簽到位置預測*

劉攀登，李 川，李曉娟

四川大學 計算機學院，成都 610065

1 引言

隨著Foursquare、Gowalla、Micro-blogging、大眾點評網等基于位置的社交網絡（location-based social network，LBSN）的廣泛應用，基于LBSN的位置預測成為近年來的研究熱點之一。準確的位置預測在城市規劃[1-2]、交通預測[3-4]、廣告推送[5-6]以及疾病預防[7]等方面具有非常重要的應用價值。

現存用戶移動性規律發現方法，如馬爾科夫模型、PMM（periodic mobility model）、W3（who，when，where）等雖各有所長，但仍存在如下缺陷：（1）不能將時間對于用戶訪問位置變化的影響真實、量化地反映出來；（2）不能將地理位置間前后相繼、相互關聯的影響真實、量化地反映出來。

現實生活中，人類的移動行為在時間上是連續的，前一時刻的移動行為必然影響下一時刻的行為，前一狀態的位置必然影響下一狀態的位置。馬爾科夫過程與這種直觀的移動行為相吻合，被廣泛應用于位置預測模型中[8-11]。然而，該方法有如下缺陷：（1）難于實現復雜度和預測精度間的平衡：雖然馬爾科夫模型階數的增加會提高算法的準確率，但算法復雜度也會隨之增加。（2）忽略時間的影響：用戶移動行為和時間有著緊密的聯系，但使用馬爾科夫模型來預測用戶的位置會忽略時間的影響。如，工作日上午9:00，人們一般在公司上班，但周末的上午9:00，他們可能在家休息或者在旅行。（3）忽略移動軌跡的前后地理位置間的關聯：軌跡絕不是孤立的，它們彼此聯系。如，從家出發去商場，接著到辦公室（家庭—商場—辦公室）這條軌跡與（家庭—商場—餐廳）軌跡是有關聯的。但使用馬爾科夫模型建立轉移概率時，研究者則假設軌跡獨立。

2011年，Cho等人[12]提出PMM模型，針對單個用戶，將用戶簽到數據按時間分段，分別利用高斯混合模型對用戶不同時段的簽到數據進行建模從而實現位置推薦。但該模型只能對單一用戶逐個建模，缺乏通用性。其次，該模型必須基于特定用戶歷史數據進行建模，難以實現對新用戶的位置推薦。更值得注意的是，該模型未系統地考慮時間因素對用戶移動行為的影響，對每天相同時段進行相同位置推薦。

2013年，Yuan等人[13]提出概率模型——W4（who，where，when，what），該模型基于tweet數據內容（包括用戶ID、文本內容、時間、位置等），建立貝葉斯網絡，采用EM算法來估計模型的參數。然而此模型參數的調整較為復雜，且需要完備的結構化信息，這些信息在多數情況下不能完整獲取。更重要的是，該模型未考慮地理位置之間前后相繼的轉移影響。由于本文所采用的數據集中不包括tweet的文本內容，故本文與W4的變形——W3模型進行對比。

綜上，現存方法均未能系統考慮用戶的位置轉移因素、位置轉移所體現的真實的時間規律，亦未考慮用戶群體的影響。

為解決上述問題，本文提出挖掘用戶簽到位置轉移變化的規律性。為描述用戶位置的轉移變換，本文提出簇標記轉移矩陣，以描述在特定時刻用戶從某簇轉移到不同簇的簽到記錄頻次分布情況。借助簇標記轉移矩陣，本文提出基于向量自回歸的位置轉移演化算法（location transfer evolution algorithm based on vector autoregressive，LTE），挖掘簇標記轉移向量隨時間變化的規律。可根據規律預知未來某時刻或多個時刻的簇標記轉移向量，進而可以為用戶進行位置推薦或預測。然而，由于用戶的簽到行為是隨機的，用戶簽到數據在所選時間粒度上是不連續的，簇標記轉移矩陣序列的生成同樣是一項具有挑戰性的工作。基于Foursquare、Gowalla紐約、東京真實用戶簽到數據集，本文結合對比算法進行了大量、有效性對比分析。實驗表明，本文所提出的基于向量自回歸的位置轉移演化算法，具有更高的預測有效性和預測精度，能有效完成用戶位置的準確預測。

2 簇標記轉移矩陣

由于用戶簽到點具有隨機性和多樣性，為克服簽到點細微差異所造成的高維數據分析處理中的組合爆炸問題，本文對所有時刻的用戶簽到點按經緯度進行聚類。本文采用基于K-means的位置聚類算法[14]，遵循歐式距離最小化原則，把樣本點集劃分為若干個簇，使得簇內樣本點相似度盡可能高，且簇間樣本點相似度盡可能低。K-means聚類算法將用戶的簽到樣本集D劃分為k個不相交的簇{Cl|l=1,2,…,k}，其中相應地，用λ∈{1,2,…,k}表示樣本的簇標記。該算法將距離相近的簽到點劃分到同一個簇，最終將得到若干個獨立且緊湊的簇。

定義1（簇標記轉移矩陣C）設N為簇標記的總數，存在矩陣C(N×N)，對于任意1≤i,j≤N，矩陣元素Cij表示從簇標記λi到λj的簽到記錄頻次，則矩陣C(N×N)稱為簽到數據集D上的簇標記轉移矩陣。所有時刻簇標記轉移矩陣按時間的先后順序排列將形成簇標記轉移矩陣序列S={CT1,CT2,…,CTT}。

基于定義1，可由T和T+δ（δ為簇標記轉移矩陣序列的時間粒度）時刻的用戶簽到記錄的簇分布，生成T時刻簇標記轉移矩陣。如圖1所示。設用戶的簽到點簇標記總數N=4（即簇0、1、2、3），則簇標記轉移矩陣C為4×4矩陣。圖1（a）～（c）中不同顏色的圓圈表示不同用戶的簽到記錄。圖1（a）、（b）中相同顏色的圓圈表示某用戶的位置轉移情況。如，藍色圓圈從圖1（a）的簇0轉移到圖1（b）的簇1，則，對應到圖1（d）中C01應為1。再如，圖1（a）中簇0紫色圓圈和粉色圓圈在T1時刻都轉移到圖1（b）中的簇2，那么對應到圖1（d）中的C02應為2。

Fig.1 Generation of cluster marker transfer matrix sequence圖1 簇標記轉移矩陣序列

3 基于簇標記轉移序列的向量自回歸

用戶的簇轉移是相互影響的。如，用戶在某時刻到達簇A，那么該用戶在該時刻將不可能同時到達其他簇。向量自回歸模型（vector autoregression，VAR）描述多變量時間序列間的變動關系，能夠揭示序列的變化規律受其他序列的影響。基于定義1，可獲取每個時刻簇標記轉移矩陣，將它們按照時間先后順序排列，即可得到簇標記轉移矩陣序列。為方便探索簇標記轉移矩陣隨時間的變化規律，首先定義簇標記轉移向量序列。

定義2（簇標記轉移向量序列V）將簇標記轉移矩陣序列中的每一個矩陣CTi橫向展成向量Vi后所形成的向量序列V={V1,V2,…,VT}稱為簇標記轉移向量序列，Vi稱為i時簇標記轉移向量。

多變量時間序列的VAR模型，從變量序列的數據出發，探討相互之間的動態變化規律，即滯后結構關系，設yt=(y1t,y2t,…,ykt)為k維內生變量向量，εt=(ε1t,ε2t,…,εkt)為k維隨機擾動向量，則滯后階數為p的VAR模型（記為VAR（p））表達式為：

式中，yt是t時簇標記轉移向量；Φi(i=1,2,…,p)是第i個待估系數k×k維矩陣；εt～N(0,Ω)，εt每一維獨立同分布，但不要求不同維之間相互獨立，εt服從以E(εt)=0 為期望向量；cov(εt)=E(εtεt′)=Ω為方差的k維正態分布。

滯后階數的選擇對構建VAR模型至關重要，本文用赤池信息準則（Akaike information criterion，AIC）確定p值，確定p值的方法是在增加p值的過程中，使AIC值同時最小。AIC定義為：

其中，n=k(kp+1)是待估參數的個數，k是內生變量個數，T是樣本長度，p是滯后階數，l由下式確定：

同理，可進行多步預測，預測出未來多個時刻的簇標記轉移向量。

4 基于向量自回歸位置轉移時空規律學習

首先，采用K-means聚類算法對用戶的簽到數據按照經緯度進行聚類，并對每條簽到記錄賦以簇標記λ；然后，根據所選的時間粒度δ對簽到時間進行標記，為每條簽到記錄賦以對應的時間標記T。由此，每條簽到記錄都有對應的簇標記和時間標記。繼而得到隨時間變化的簇標記轉移向量序列，然后利用向量自回歸進行建模，從而預測下一時刻或未來多個時刻的簇標記轉移向量，如算法1所示。

特定時刻的簇標記轉移矩陣，描述的是該時刻由某簇轉移到其他簇的簽到記錄頻次分布情況。對每個用戶，將用戶的簽到記錄按時間升序排序，若該用戶某條簽到記錄和下一條簽到記錄在時間標記上是連續的，則更新對應的簇標記轉移向量元素值。否則，認為用戶在下一時刻仍停留在原地。更詳細地說，對某用戶連續的兩條簽到記錄，若該用戶在t0時刻去往簇標記為λ0的位置，在t1時刻去往簇標記為λ1的位置，若t0和t1的時間標記（分別為T0、T1）是連續的，那么更新T0時簇標記轉移向量中表示從λ0轉移到λ1的元素值。否則，更新T0時簇標記轉移向量中表示從λ0轉移到λ0的元素值。由此，可以生成簇標記轉移向量序列，最后，建立向量自回歸模型以挖掘用戶的位置轉移演化規律。

算法1基于向量自回歸的位置轉移演化算法（LTE）

輸入：用戶簽到數據集D={(u0,w0,j0,t0,λ0,T0),(u1,w1,j1,t1,λ1,T1),…,(um,wm,jm,tm,λm,Tm)}，其中u={u0,u1,…,ud}為用戶集，w、j、t分別表示用戶簽到點的緯度、經度和簽到時間；聚類個數k；預測步數s。

5 實驗分析

5.1 數據集

本文使用Foursquare（基于用戶地理位置簽到服務）中紐約和東京兩個城市的簽到數據，以及Gowalla數據集中紐約的簽到數據。每條簽到記錄都有對應的時間戳。時間跨度從2012年4月4日到2013年2月16日。數據集的統計信息如表1所示。本文將每個數據集的最后10個時刻的用戶簽到記錄作為測試集，之前的簽到記錄作為訓練集。

Table 1 Statistics of datasets表1 數據集的統計信息

5.2 評價指標

本文預測未來10個時刻的簇標記轉移向量，為使向量分量誤差之間具有可比性，即向量分量的誤差在同一個數量級上。本文采用離差標準化對誤差進行歸一化處理，則未來10個時刻的向量分量vj誤差轉換函數如下：

為評估算法的預測性能，本文采用平均絕對誤差（mean absolute error，MAE）和均方根誤差（root mean square error，RMSE）作為評價指標，表示預測t時簇標記轉移向量的誤差，公式如下：

其中，k為簇標記轉移向量的維數。

5.3 參數配置

針對每個數據集，本文設置聚類個數為4。因為用戶簽到數據在時間上是不連續的，所以選取的時間粒度不同，得到的簇標記轉移向量序列不同，算法的預測性能也會不同。本文設置時間粒度分別為1,2,…,8（單位：h），學習不同的時間粒度δ對算法預測性能的影響。本文用預測的未來10個時刻的平均誤差來度量算法的預測性能。

從圖2可知，雖然時間粒度對算法預測誤差的影響沒有固定的規律可尋，但是選取合適的時間粒度對算法的預測性能有著舉足輕重的地位。本文針對3個數據集，選取較為合適的時間粒度。針對Foursquare紐約城市簽到數據集，設置時間粒度為5 h，Foursquare東京城市簽到數據集，設置時間粒度為1 h，Gowalla紐約城市簽到數據集，設置時間粒度為1 h。

Fig.2 Time granularity adjustment圖2 時間粒度參數調整

滯后期對于構建VAR模型至關重要。AIC值越小，表明模型越能有效反映變量之間的關系。階數參數調整結果見圖3。其中橫坐標表示滯后階數，縱坐標是赤池信息量準則，選取使AIC值最小的階數。針對3個數據集，本文將階數分別設定為5、11和6。

5.4 VAR有效性驗證

為驗證本文所使用的技術方案的有效性，對不同學習方法進行較深入的探索與辨析，將VAR模型的預測性能與AR、SMA和SES分別進行對比。

自回歸模型（autoregressive model，AR），如果時間序列{yt}可以表示為它的前期值和隨機擾動項εt的線性函數：

則稱該序列{yt}是自回歸序列，上式為p階自回歸模型，簡記為AR（p）。式中的自變量是時間序列在不同滯后時期的取值，即時間序列{yt}的變化受其自身變化的影響。

一次移動平均法（single moving average，SMA），通過對時間序列逐期遞移求得平均數作為預測值的方法叫一次移動平均法，它是對時間序列進行修勻，邊移動邊平均以排除偶然因素對原序列的影響，進而測定長期趨勢的方法。已知時間序列為{yt}(t=1,2,…,T)，T為時間序列總期數，則一次移動平均法的公式為：

使用時間序列中最近一組歷史數據的平均值作為下一期的預測值，移動平均法的“平均”是指對歷史數據的“算術平均”，而“移動”是指參與平均的歷史數據隨預測期的推進而不斷更新。

Fig.3 Order determination圖3 定階

簡單指數平滑法（simple exponential smoothing，SES），是把本期實際觀察值和本期預測值的加權平均值直接作為下期預測值的預測方法。已知時間序列為{yt}(t=1,2,…,T)，T為時間序列總期數，則簡單指數平滑法的遞推公式為：

其中，α為平滑系數。由于，故依次遞推可得：

指數平滑法是一種特殊的加權移動平均法，其加權的特點是對離預測期近的歷史數據給予較大的權數，對離預測期遠的歷史數據給予較小的權數，權數由近到遠按指數規律遞減。

本文通過實驗充分驗證VAR模型為最佳技術方案，VAR實現較好的性能。具體實驗結果如圖4至圖6，針對Foursquare紐約城市數據集，在其中9個時刻，VAR模型的預測誤差低于其他方法。在Foursquare東京城市數據集，有8個時刻，VAR模型預測的準確度高于其他方法，Gowalla紐約城市數據集，在其中7個時刻，向量自回歸（VAR）模型的預測性能優于其他方法。這是因為VAR模型是基于簇標記轉移向量序列建模，而AR、SMA和SES是基于簇標記轉移向量的每個分量序列分別建模的，VAR模型相對于其他方法，考慮多個時間序列之間的相關性，將時間序列分析和多元回歸分析有機地結合在一起，有效地提高預測的精度。

5.5 對比實驗

本節將所提的基于向量自回歸的位置轉移演化算法LTE應用于位置預測，并將LTE算法的預測性能與W3和PMM算法進行對比。本節仍然使用以上3個真實的數據集，針對每個數據集，將每個用戶的按時間順序的簽到數據以8∶2的比例分為兩部分，分別作為訓練集和測試集。為評價不同模型的預測性能，本節采用預測的準確度（ACC）作為評價指標，即預測位置中包含多少比例的真實位置。

Fig.4 Prediction performance of different methods in Foursquare NYC圖4 Foursquare紐約數據集上不同方法的預測性能比較

Fig.5 Prediction performance of different methods in Foursquare TKY圖5 Foursquare東京數據集上不同方法的預測性能比較

Fig.6 Prediction performance of different methods in Gowalla NYC圖6 Gowalla紐約數據集上不同方法的預測性能比較

PMM[12]大多數人的運動具有周期性，其運動方式大多是圍繞幾個潛在位置按時間進行有規律的往返。該模型假設用戶的潛在位置有兩個，分別為家庭和辦公地，用戶的簽到數據是由隨時間變化的兩狀態的高斯混合模型生成的。針對單個用戶，將用戶的簽到數據按時間分段，并分別利用高斯混合模型對用戶的不同時間段的簽到數據進行建模，并使用EM算法進行參數估計，最終訓練出該用戶在不同時間段的高斯混合模型，從而相應地在不同的時間段為該用戶進行位置預測。

W3[13]是W4的變形，相對于W4而言，W3沒有考慮文本因素。由于本文所使用的數據集中不包含tweets的文本內容，故本文使用W3模型作為對比實驗。W4是一個概率移動性模型，利用tweets文本數據，包括文本內容、地理信息、發布時間和用戶ID，從空間、時間和活動三方面發現用戶移動行為規律。對于所有的候選位置，按照以下公式計算用戶出現在候選位置的概率，并選取概率值最大的Top-k個位置作為預測位置。

其中，s∈{0,1}，分別表示工作日和周末；u、t、r、z、l分別表示用戶、時間、區域、主題和地點。

預測結果如圖7所示。在3個真實數據集上的實驗表明，本文提出的算法準確率分別達到73.86%、79.25%和76.58%。相對于W3，LTE的準確率分別提升8.76%、21.31%和4.43%。與PMM相比，LTE的準確率分別提升28.97%、38.50%和25.07%。LTE的預測性能有明顯優勢。這是因為本文算法將時間對于用戶訪問位置變化的影響真實、量化地反映出來，真正將時間因素真實地建模至移動性規律中，此外，本文算法還考慮位置轉移、位置轉移時序特征以及大多數用戶群體的意見，這些因素的考慮都有利于提高位置預測的準確性。

Fig.7 Location prediction accuracy of PMM,W3 and LTE圖7 位置預測算法PMM、W3和LTE的準確度對比

6 相關工作

基于位置的社會網絡推薦系統使用的主要方法分為以下3類：

（1）基于內容的推薦系統

基于內容的推薦系統的依據是：用戶的興趣應該與系統所推薦位置的描述相匹配。用戶的興趣與位置的描述越相似，用戶對推薦的位置可能越感興趣。在基于內容的推薦方法中，計算出與用戶最相似的幾個位置，然后按照相似度的大小推薦這些位置。Park等人[15]、Ramaswamy等人[16]將從用戶基本資料中發現的用戶偏好與位置特征（如標簽和類別）進行匹配來做出推薦。這些系統需要用戶基本資料和位置功能信息來提高推薦的質量。

基于內容的方法的主要優點是，這樣的系統克服了新用戶和新地點的冷啟動問題。只要新添加的用戶或位置有適當的描述性內容，這種推薦系統都能有效地處理。然而，基于內容的推薦系統也有很多弊端：①基于內容的推薦系統沒有考慮用戶群體的意見，這可能會導致低質量的推薦；②基于內容的推薦系統需要用戶和位置的結構化信息，這些信息的獲取代價是很大的。

（2）鏈接分析算法

鏈接分析算法（如PageRank和HITS）廣泛應用于網頁排名。這些算法分析復雜的網絡結構并提取具有高影響力的節點。Zheng等人[17]擴展HITS算法來發現LBSN中有經驗的用戶和有趣的位置。每個位置有受歡迎程度的評分，每個用戶有旅行經驗評分，最終得到用戶經驗度和位置流行度的排名。Raymond等人[18]擴展基于隨機游走的鏈接分析算法進行位置推薦。

基于鏈接分析方法的優點是：①考慮用戶的經驗，并對經驗豐富的用戶進行評分；②解決冷啟動問題。然而，這類方法有一個主要的缺點：它們只能為所有用戶提供通用的推薦，忽略了用戶的個性化偏好。

（3）協同過濾推薦

在傳統的推薦系統中，協同過濾（CF）被廣泛使用。CF模型基于以下假設：用戶更可能訪問相似用戶訪問過的位置。Cheng等人[19]融合地域影響力和社交信息建立矩陣分解模型，從而進行個性化位置推薦。Jia等人[20]提出SeqRWR方法動態選擇在每個時間片對目標用戶最有影響力的N個朋友，然后利用所提的TSB模型對朋友影響力的特征建模，預測用戶在每個時間片的位置并進行推薦。Liu等人[21]提出IRenMF方法探究周邊地理位置的特征，學習用戶和位置的潛因子，以提高位置推薦的準確度。Lian等人[22]提出GeoMF模型，首先利用所提的加權矩陣分解解決隱式反饋協同過濾POI推薦的稀疏性，再將空間聚類現象融入到矩陣分解模型中以提高推薦性能。Bao等人[23]提出基于位置和偏好感知的推薦系統，既考慮用戶個體偏好又考慮本地專家的意見，從而為用戶進行位置推薦。

協同過濾模型的優點是：①不需要位置或用戶的結構化描述；②吸取用戶群體的意見提高推薦的質量。

然而，CF模型也有缺點：①當數據稀疏，例如用戶評分的數量很少，用戶-位置的評分矩陣是非常稀疏的，從而導致協同過濾模型做出的推薦是不準確的；②由于系統中有大量的用戶和位置，相似性模型的構建過程非常耗時，隨著LBSN的快速增長和不斷演化，該模型的擴展性不佳；③CF模型不能有效地解決冷啟動問題，難以為新用戶或新位置提供推薦。

在大多情況下，用戶興趣內容、社會網絡關聯信息或位置特征等信息很難獲取，僅具備用戶的簽到點及相應簽到時間，這使得上述方法都很難適用。本文的研究為該方向進行了有效的補充，能在信息獲取代價相對較小的前提下有效準確地預測用戶簽到位置。

7 結束語

本文提出基于向量自回歸的位置轉移演化算法對簇標記轉移向量進行處理，挖掘用戶位置轉移隨時間的動態變化規律。簇標記轉移矩陣的提出，幫助描述在特定時刻該城市用戶的位置轉移情況，通過加入用戶簽到行為的時間信息，有效支持簇標記轉移矩陣序列的生成。為驗證模型的有效性，本文利用真實的Foursquare和Gowalla簽到數據集進行實驗，結果表明VAR比AR、SES和SMA表現得更好。本文將所提的LTE算法用于位置預測并與傳統的算法進行對比，實驗結果表明，本文算法具有更高的位置預測準確度。在未來的工作中，將針對具有相似位置轉移的用戶群體進行移動規律挖掘，從而提供更加精確的位置預測。