基于位置轉(zhuǎn)移時(shí)空規(guī)律的用戶簽到位置預(yù)測(cè)*

劉攀登，李 川，李曉娟

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

1 引言

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

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

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

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

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

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

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

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

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

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

基于定義1，可由T和T+δ（δ為簇標(biāo)記轉(zhuǎn)移矩陣序列的時(shí)間粒度）時(shí)刻的用戶簽到記錄的簇分布，生成T時(shí)刻簇標(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，則，對(duì)應(yīng)到圖1（d）中C01應(yīng)為1。再如，圖1（a）中簇0紫色圓圈和粉色圓圈在T1時(shí)刻都轉(zhuǎn)移到圖1（b）中的簇2，那么對(duì)應(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)移是相互影響的。如，用戶在某時(shí)刻到達(dá)簇A，那么該用戶在該時(shí)刻將不可能同時(shí)到達(dá)其他簇。向量自回歸模型（vector autoregression，VAR）描述多變量時(shí)間序列間的變動(dòng)關(guān)系，能夠揭示序列的變化規(guī)律受其他序列的影響。基于定義1，可獲取每個(gè)時(shí)刻簇標(biāo)記轉(zhuǎn)移矩陣，將它們按照時(shí)間先后順序排列，即可得到簇標(biāo)記轉(zhuǎn)移矩陣序列。為方便探索簇標(biāo)記轉(zhuǎn)移矩陣隨時(shí)間的變化規(guī)律，首先定義簇標(biāo)記轉(zhuǎn)移向量序列。

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

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

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

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

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

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

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

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

特定時(shí)刻的簇標(biāo)記轉(zhuǎn)移矩陣，描述的是該時(shí)刻由某簇轉(zhuǎn)移到其他簇的簽到記錄頻次分布情況。對(duì)每個(gè)用戶，將用戶的簽到記錄按時(shí)間升序排序，若該用戶某條簽到記錄和下一條簽到記錄在時(shí)間標(biāo)記上是連續(xù)的，則更新對(duì)應(yīng)的簇標(biāo)記轉(zhuǎn)移向量元素值。否則，認(rèn)為用戶在下一時(shí)刻仍停留在原地。更詳細(xì)地說(shuō)，對(duì)某用戶連續(xù)的兩條簽到記錄，若該用戶在t0時(shí)刻去往簇標(biāo)記為λ0的位置，在t1時(shí)刻去往簇標(biāo)記為λ1的位置，若t0和t1的時(shí)間標(biāo)記（分別為T(mén)0、T1）是連續(xù)的，那么更新T0時(shí)簇標(biāo)記轉(zhuǎn)移向量中表示從λ0轉(zhuǎn)移到λ1的元素值。否則，更新T0時(shí)簇標(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í)間；聚類個(gè)數(shù)k；預(yù)測(cè)步數(shù)s。

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

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

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

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

5.2 評(píng)價(jià)指標(biāo)

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

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

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

5.3 參數(shù)配置

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

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

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

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

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

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

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

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

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

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

Fig.3 Order determination圖3 定階

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 相關(guān)工作

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

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

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

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

（2）鏈接分析算法

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

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

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

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

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

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

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

7 結(jié)束語(yǔ)

本文提出基于向量自回歸的位置轉(zhuǎn)移演化算法對(duì)簇標(biāo)記轉(zhuǎn)移向量進(jìn)行處理，挖掘用戶位置轉(zhuǎn)移隨時(shí)間的動(dòng)態(tài)變化規(guī)律。簇標(biāo)記轉(zhuǎn)移矩陣的提出，幫助描述在特定時(shí)刻該城市用戶的位置轉(zhuǎn)移情況，通過(guò)加入用戶簽到行為的時(shí)間信息，有效支持簇標(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ù)測(cè)并與傳統(tǒng)的算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明，本文算法具有更高的位置預(yù)測(cè)準(zhǔn)確度。在未來(lái)的工作中，將針對(duì)具有相似位置轉(zhuǎn)移的用戶群體進(jìn)行移動(dòng)規(guī)律挖掘，從而提供更加精確的位置預(yù)測(cè)。