劉攀登，李 川，李曉娟

四川大學(xué) 計算機(jī)學(xué)院，成都 610065

1 引言

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

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

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

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

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

綜上，現(xiàn)存方法均未能系統(tǒng)考慮用戶的位置轉(zhuǎn)移因素、位置轉(zhuǎn)移所體現(xiàn)的真實(shí)的時間規(guī)律，亦未考慮用戶群體的影響。

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

2 簇標(biāo)記轉(zhuǎn)移矩陣

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

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

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

Fig.1 Generation of cluster marker transfer matrix sequence圖1 簇標(biāo)記轉(zhuǎn)移矩陣序列

3 基于簇標(biāo)記轉(zhuǎn)移序列的向量自回歸

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

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

多變量時間序列的VAR模型，從變量序列的數(shù)據(jù)出發(fā)，探討相互之間的動態(tài)變化規(guī)律，即滯后結(jié)構(gòu)關(guān)系，設(shè)yt=(y1t,y2t,…,ykt)為k維內(nèi)生變量向量，εt=(ε1t,ε2t,…,εkt)為k維隨機(jī)擾動向量，則滯后階數(shù)為p的VAR模型（記為VAR（p））表達(dá)式為：

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

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

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

同理，可進(jìn)行多步預(yù)測，預(yù)測出未來多個時刻的簇標(biāo)記轉(zhuǎn)移向量。

4 基于向量自回歸位置轉(zhuǎn)移時空規(guī)律學(xué)習(xí)

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

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

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

輸入：用戶簽到數(shù)據(jù)集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分別表示用戶簽到點(diǎn)的緯度、經(jīng)度和簽到時間；聚類個數(shù)k；預(yù)測步數(shù)s。

5 實(shí)驗(yàn)分析

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

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

Table 1 Statistics of datasets表1 數(shù)據(jù)集的統(tǒng)計信息

5.2 評價指標(biāo)

本文預(yù)測未來10個時刻的簇標(biāo)記轉(zhuǎn)移向量，為使向量分量誤差之間具有可比性，即向量分量的誤差在同一個數(shù)量級上。本文采用離差標(biāo)準(zhǔn)化對誤差進(jìn)行歸一化處理，則未來10個時刻的向量分量vj誤差轉(zhuǎn)換函數(shù)如下：

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

其中，k為簇標(biāo)記轉(zhuǎn)移向量的維數(shù)。

5.3 參數(shù)配置

針對每個數(shù)據(jù)集，本文設(shè)置聚類個數(shù)為4。因?yàn)橛脩艉灥綌?shù)據(jù)在時間上是不連續(xù)的，所以選取的時間粒度不同，得到的簇標(biāo)記轉(zhuǎn)移向量序列不同，算法的預(yù)測性能也會不同。本文設(shè)置時間粒度分別為1,2,…,8（單位：h），學(xué)習(xí)不同的時間粒度δ對算法預(yù)測性能的影響。本文用預(yù)測的未來10個時刻的平均誤差來度量算法的預(yù)測性能。

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

Fig.2 Time granularity adjustment圖2 時間粒度參數(shù)調(diào)整

滯后期對于構(gòu)建VAR模型至關(guān)重要。AIC值越小，表明模型越能有效反映變量之間的關(guān)系。階數(shù)參數(shù)調(diào)整結(jié)果見圖3。其中橫坐標(biāo)表示滯后階數(shù)，縱坐標(biāo)是赤池信息量準(zhǔn)則，選取使AIC值最小的階數(shù)。針對3個數(shù)據(jù)集，本文將階數(shù)分別設(shè)定為5、11和6。

5.4 VAR有效性驗(yàn)證

為驗(yàn)證本文所使用的技術(shù)方案的有效性，對不同學(xué)習(xí)方法進(jìn)行較深入的探索與辨析，將VAR模型的預(yù)測性能與AR、SMA和SES分別進(jìn)行對比。

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

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

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

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

Fig.3 Order determination圖3 定階

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

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

指數(shù)平滑法是一種特殊的加權(quán)移動平均法，其加權(quán)的特點(diǎn)是對離預(yù)測期近的歷史數(shù)據(jù)給予較大的權(quán)數(shù)，對離預(yù)測期遠(yuǎn)的歷史數(shù)據(jù)給予較小的權(quán)數(shù)，權(quán)數(shù)由近到遠(yuǎn)按指數(shù)規(guī)律遞減。

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

5.5 對比實(shí)驗(yàn)

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

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

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

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

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

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

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

預(yù)測結(jié)果如圖7所示。在3個真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文提出的算法準(zhǔn)確率分別達(dá)到73.86%、79.25%和76.58%。相對于W3，LTE的準(zhǔn)確率分別提升8.76%、21.31%和4.43%。與PMM相比，LTE的準(zhǔn)確率分別提升28.97%、38.50%和25.07%。LTE的預(yù)測性能有明顯優(yōu)勢。這是因?yàn)楸疚乃惴▽r間對于用戶訪問位置變化的影響真實(shí)、量化地反映出來，真正將時間因素真實(shí)地建模至移動性規(guī)律中，此外，本文算法還考慮位置轉(zhuǎn)移、位置轉(zhuǎn)移時序特征以及大多數(shù)用戶群體的意見，這些因素的考慮都有利于提高位置預(yù)測的準(zhǔn)確性。

Fig.7 Location prediction accuracy of PMM,W3 and LTE圖7 位置預(yù)測算法PMM、W3和LTE的準(zhǔn)確度對比

6 相關(guān)工作

基于位置的社會網(wǎng)絡(luò)推薦系統(tǒng)使用的主要方法分為以下3類：

（1）基于內(nèi)容的推薦系統(tǒng)

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

基于內(nèi)容的方法的主要優(yōu)點(diǎn)是，這樣的系統(tǒng)克服了新用戶和新地點(diǎn)的冷啟動問題。只要新添加的用戶或位置有適當(dāng)?shù)拿枋鲂詢?nèi)容，這種推薦系統(tǒng)都能有效地處理。然而，基于內(nèi)容的推薦系統(tǒng)也有很多弊端：①基于內(nèi)容的推薦系統(tǒng)沒有考慮用戶群體的意見，這可能會導(dǎo)致低質(zhì)量的推薦；②基于內(nèi)容的推薦系統(tǒng)需要用戶和位置的結(jié)構(gòu)化信息，這些信息的獲取代價是很大的。

（2）鏈接分析算法

鏈接分析算法（如PageRank和HITS）廣泛應(yīng)用于網(wǎng)頁排名。這些算法分析復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)并提取具有高影響力的節(jié)點(diǎn)。Zheng等人[17]擴(kuò)展HITS算法來發(fā)現(xiàn)LBSN中有經(jīng)驗(yàn)的用戶和有趣的位置。每個位置有受歡迎程度的評分，每個用戶有旅行經(jīng)驗(yàn)評分，最終得到用戶經(jīng)驗(yàn)度和位置流行度的排名。Raymond等人[18]擴(kuò)展基于隨機(jī)游走的鏈接分析算法進(jìn)行位置推薦。

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

（3）協(xié)同過濾推薦

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

協(xié)同過濾模型的優(yōu)點(diǎn)是：①不需要位置或用戶的結(jié)構(gòu)化描述；②吸取用戶群體的意見提高推薦的質(zhì)量。

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

在大多情況下，用戶興趣內(nèi)容、社會網(wǎng)絡(luò)關(guān)聯(lián)信息或位置特征等信息很難獲取，僅具備用戶的簽到點(diǎn)及相應(yīng)簽到時間，這使得上述方法都很難適用。本文的研究為該方向進(jìn)行了有效的補(bǔ)充，能在信息獲取代價相對較小的前提下有效準(zhǔn)確地預(yù)測用戶簽到位置。

7 結(jié)束語

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