融合信任圈和移動模式的位置預(yù)測框架

魏盛杰,王 鑫,戴 勁,韓 楠

(1.四川音樂學(xué)院 實驗藝術(shù)學(xué)院， 成都 610021；2.成都信息工程大學(xué) 軟件工程學(xué)院， 成都 610225；3.四川音樂學(xué)院 美術(shù)學(xué)院， 成都 610021；4.成都信息工程大學(xué) 管理學(xué)院， 成都 610103)

0 引言

基于位置信息的社交網(wǎng)絡(luò)(location based social network，LBSN)在瞬息萬變的時代中應(yīng)運而生，得益于智能移動設(shè)備的廣泛普及與移動定位技術(shù)的飛速發(fā)展，個體用戶的位置信息數(shù)據(jù)比以往任何時候都更容易獲取。眾多基于位置的社交網(wǎng)絡(luò)(簡稱位置社交網(wǎng)絡(luò))平臺，如：Foursquare、Facebook Places以及微信、美團(tuán)、大眾點評等，它們將用戶的線上活動與線下生活建立聯(lián)系，有效地將現(xiàn)實生活與虛擬世界結(jié)合在一起，打破了存在于物理世界與網(wǎng)絡(luò)世界之間的信息鴻溝。

由于簽到數(shù)據(jù)集包含了豐富的信息，現(xiàn)階段有越來越多的研究者利用簽到數(shù)據(jù)來預(yù)測用戶的下一個簽到點。傳統(tǒng)的研究主要是利用用戶的個體移動模式來預(yù)測下一簽到位置，僅僅考慮歷史簽到記錄的預(yù)測模型性能是有局限性的，它的弊端在于沒有綜合考慮用戶的移動模式以及用戶的社會信任關(guān)系這兩類影響因子，缺乏考慮位置屬性與用戶特征之間的關(guān)聯(lián)性。

在部分情況下，用戶的社交關(guān)系在一定程度上會對用戶的時空行為構(gòu)成影響[1]，例如，當(dāng)用戶與信任度高的朋友在餐廳共進(jìn)晚餐的時候，下一步計劃更大概率會采取該朋友提出的建議，并且長期處于同一社交圈內(nèi)，不同用戶之間的興趣愛好會逐漸統(tǒng)一化。生物的移動模式通常會受到個體屬性以及群體屬性的影響，即用戶的移動行為并不是固定不變，而是會隨著環(huán)境變化而變化[2]。本文研究目標(biāo)旨在開發(fā)一個有效的位置預(yù)測框架，綜合考慮用戶的信任圈以及移動模式來精準(zhǔn)預(yù)測用戶的下一個簽到位置。

本文針對預(yù)測用戶下一個簽到位置問題提出了一種融合信任圈和移動模式的位置預(yù)測框架FTM(a location prediction framework based on trust circle and mobility pattern)。具體來說，該框架分為2個模塊：① 信任圈模塊；② 移動模式模塊。本文首先介紹了基于位置社交網(wǎng)絡(luò)的綜合研究。其次，本文利用信任關(guān)系對個體的影響挖掘出一種新型社會關(guān)系，接著根據(jù)用戶簽到模式表現(xiàn)出的周期性提出了直接訪問模式及多元訪問模式。最后，本文在真實數(shù)據(jù)集上評估了模型的性能。實驗結(jié)果證明，本文提出的模型可以很好地預(yù)測用戶下一個簽到位置。

綜上所述，本文的主要貢獻(xiàn)包括：

1) 基于位置社交網(wǎng)絡(luò)利用用戶的新型社交關(guān)系和移動模式預(yù)測下一個簽到位置。

2) 提出了信任圈的新概念，將信任圈按照不同群體劃分為三類社交關(guān)系，對用戶時空行為的影響進(jìn)行建模。

3) 將移動模式拆分為直接訪問模式及多元訪問模式，對不同訪問模式造成的影響進(jìn)行建模。

4) 在大規(guī)模真實數(shù)據(jù)集上評估了FTM預(yù)測框架，實驗在準(zhǔn)確率以及魯棒性上都優(yōu)于其他代表性方法。

1 相關(guān)工作

作為異構(gòu)網(wǎng)絡(luò)中的典型代表，位置社交網(wǎng)絡(luò)中蘊藏著十分復(fù)雜的結(jié)構(gòu)，位置社交網(wǎng)絡(luò)信息層次如圖1所示，主要可以分為4層。

圖1 位置社交網(wǎng)絡(luò)信息層次圖

圖1由下至上依次為時間信息層、地理信息層、社交信息層以及文本信息層，每一層包含了多個節(jié)點(例如時間節(jié)點、位置節(jié)點和用戶節(jié)點等)，位置網(wǎng)絡(luò)將多種不同類型的節(jié)點相互連接起來，構(gòu)成了多元的關(guān)聯(lián)關(guān)系(例如User1和User2之間的社交關(guān)聯(lián)以及User1和Location1之間的簽到關(guān)聯(lián))，從而可以更精準(zhǔn)地分析用戶的行為和特征。從圖1中可以發(fā)現(xiàn)：User1與User2分享位于Location1的簽到信息，不僅交換了地理層面的簽到信息，還額外產(chǎn)生了時間層面信息、文本層面信息以及社交層面信息，多個層面的上下文信息會在潛移默化中影響到User2下一步位置的選擇。位置社交網(wǎng)絡(luò)將不同層面的信息關(guān)聯(lián)起來，可以精準(zhǔn)快速地挖掘用戶的潛在興趣、用戶的行動規(guī)律以及不同用戶之間的社交關(guān)系等內(nèi)在信息。因此，利用大量的簽到數(shù)據(jù)為基于位置服務(wù)的研究提供了新的技術(shù)思路，如預(yù)測用戶的下一個簽到位置、POI推薦、城市計算等[3-4]。

當(dāng)前，位置預(yù)測已經(jīng)成為基于位置社交網(wǎng)絡(luò)的主要研究任務(wù)之一。位置預(yù)測指的是利用用戶在位置社交網(wǎng)絡(luò)中的歷史簽到記錄，捕捉用戶移動的規(guī)律性，進(jìn)而對用戶下一個可能訪問的興趣點進(jìn)行預(yù)測?？紤]到位置社交網(wǎng)絡(luò)中上下文信息的多樣性以及人類移動模式的特異性，具有不同特性的人群通常其規(guī)律性并不能完全吻合。因此，在滿足用戶個性化需求的情況下來挖掘用戶移動方式的規(guī)律性已經(jīng)成為改善用戶生活質(zhì)量以及提高位置服務(wù)市場效率的重要環(huán)節(jié)。

目前針對位置社交網(wǎng)絡(luò)中位置預(yù)測的研究主要集中在以下3個方面：

1) 基于序列模式的位置預(yù)測。按照時間順序?qū)⒂脩羲械臍v史簽到點記錄作為一個序列，通過計算某一地點在該序列中出現(xiàn)的頻率并且挖掘它與相鄰地點之間潛在關(guān)系來進(jìn)行位置預(yù)測。

2) 基于時間動態(tài)性的位置預(yù)測。通常情況下，用戶在簽到時會附帶時間戳信息。通過挖掘用戶簽到行為時呈現(xiàn)出的周期模式，分析地理位置變遷與時間推移的高相關(guān)性來進(jìn)行位置預(yù)測。

3) 基于社交關(guān)聯(lián)性的位置預(yù)測。采用用戶好友的簽到歷史記錄推斷用戶的簽到行為偏好，將時空關(guān)系和社交關(guān)系緊密結(jié)合在一起來進(jìn)行位置預(yù)測。

在基于序列模式的位置預(yù)測研究方面，Yin等[5]提出了簽到最高頻次模型，該模型主要應(yīng)用于僅收集到簽到歷史記錄但沒有上下文信息的情況，通過計算下一個的簽到位置在歷史記錄中出現(xiàn)的頻率來計算該位置在下一次出現(xiàn)的概率。在此基礎(chǔ)上，Gambs等[6]提出了K階馬爾可夫模型，該模型將下次簽到之前的K個簽到序列作為簽到上下文，然后計算簽到歷史記錄中上下文序列出現(xiàn)的頻率作為下一個簽到位置的概率。為了避免在歷史記錄中找不到簽到上下文序列的情況，動態(tài)改變K的大小，當(dāng)K=0時，該模型退化成簽到最高頻次模型。

在基于時間動態(tài)性的位置預(yù)測研究方面，Gao等[7]提出利用用戶簽到數(shù)據(jù)中體現(xiàn)的時間周期性進(jìn)行建模，對用戶將來簽到的位置進(jìn)行預(yù)測。Valverde-rebaza等[8]對時間周期性進(jìn)行了拓展，基于用戶活動的循環(huán)模式提出了一種應(yīng)用于簽到位置預(yù)測的通用型時間框架，該框架主要采用混合高斯模型來描述用戶在簽到位置的時間周期性特點。

在基于社交關(guān)聯(lián)性的位置預(yù)測研究方面，Li等[9]提出了基于序列的社交可移動模型，該模型通過分析好友簽到行為模式來推斷用戶的簽到行為偏好，并且結(jié)合時空信息，計算好友簽到序列對用戶當(dāng)前簽到可能性的大小，從而預(yù)測用戶下一個訪問的位置。

基于位置社交網(wǎng)絡(luò)的位置預(yù)測已經(jīng)取得一些研究成果，但是預(yù)測的準(zhǔn)確率無法滿足用戶的需求，如何更加全面地考慮和混合多源異構(gòu)信息是需要進(jìn)一步研究的問題[10-11]。本文所提框架的創(chuàng)新性在于不僅考慮了信任圈的影響，并且在此基礎(chǔ)上加入不同移動模式對位置預(yù)測的影響，與已有工作相比，本文提出的框架考慮更為全面，預(yù)測結(jié)果更加精準(zhǔn)。

2 問題表述與模型

2.1 信任圈的特征

通過分析流行位置社交網(wǎng)絡(luò)，如Gowalla數(shù)據(jù)，用戶的簽到行為可以分為以下2種情況：第一種是用戶只身一人的簽到行為，另一種是用戶與某一社會關(guān)系同時出現(xiàn)的簽到行為。與用戶在同一位置簽到的人群可以分為信任朋友、地理鄰居以及陌生人這三類群體?；诖耍疚奶岢隽诵湃稳Φ母拍?，并按照不同群體劃分出三類社交關(guān)系，為了更好地解釋信任圈對用戶產(chǎn)生的影響，下面分別對以下三類社交關(guān)系的特征進(jìn)行詳細(xì)描述。

定義3：共現(xiàn)關(guān)系(co-occurrence relation)。將位置社交網(wǎng)絡(luò)中在同一位置簽到的用戶定義為共現(xiàn)關(guān)系，并用符號Rc表示與用戶有共同簽到記錄的社交關(guān)系的集合。

圖2為三類社交關(guān)系在累計簽到數(shù)增加情況下的共現(xiàn)率分布變化圖。其中，x軸表示已統(tǒng)計到的用戶簽到數(shù)，y軸表示共現(xiàn)的概率。

圖2 信任圈的共現(xiàn)分布曲線

從圖中可以發(fā)現(xiàn)，在已統(tǒng)計到的簽到集中，1 500次累計簽到數(shù)內(nèi)每類社交關(guān)系的共現(xiàn)概率都在30%以內(nèi)；隨著累計簽到數(shù)量的增加，共現(xiàn)率也會增加，并且最終趨于穩(wěn)定。主要有以下3個原因?qū)е逻@種趨勢：① 用戶將POI分享給其社交關(guān)系導(dǎo)致共現(xiàn)行為；② 用戶在使用簽到程序的初期缺少歷史記錄導(dǎo)致起始階段的共現(xiàn)率較低；③ 隨著時間的推移，簽到數(shù)據(jù)逐漸完整，社交關(guān)系也逐漸穩(wěn)定，共現(xiàn)率最終呈現(xiàn)平穩(wěn)的狀態(tài)。

2.2 移動模式的特征

為了模擬信任圈的影響，本文同樣分析了Gowalla數(shù)據(jù)集上用戶的簽到模式。文獻(xiàn)[12]研究表明，人類的簽到模式主要以日模式和周模式表現(xiàn)出周期性的循環(huán)，即一天和一周代表人類活動的主要循環(huán)周期。因此，本文的分析沿用了這種時間周期模式，利用日模式和周模式在結(jié)構(gòu)上的相似性挖掘具有代表性的用戶移動模式。本文將一天按照小時進(jìn)行“切片”，將用戶所有的簽到記錄按照時間順序投影到24個片段內(nèi)，并且對每一個小時內(nèi)的簽到頻率進(jìn)行統(tǒng)計，從而得到了日模式下的用戶簽到頻率圖[13]，如圖3所示。

從圖3可以發(fā)現(xiàn)，用戶的簽到主要集中在早上8點至晚上8點之間，并且1 d中的簽到高峰期出現(xiàn)在晚上7點左右。本文將每天的簽到記錄按照日期順序投影到1周內(nèi)，得到了圖4所示的周模式用戶簽到頻率圖。

圖3 日模式用戶簽到頻率曲線

圖4 周模式用戶簽到頻率曲線

從圖4可以發(fā)現(xiàn)，在周模式下，用戶在工作日的簽到模式相對一致，而周末的簽到頻率相較于工作日有所下降，主要是由于用戶在周末更可能選擇居家休息[14]，說明用戶在周末的簽到存在不規(guī)律性，本文通過計算周模式的平均簽到頻率來解決周末位置預(yù)測相對困難的問題。由于用戶軌跡呈現(xiàn)出周期性的重復(fù)，所以本文利用Apriori算法[15]來提取用戶的移動模式。

定義4：個人移動模式(individual mobility pattern)。用戶U的移動模式是根據(jù)其簽到路線按照時間順序頻繁訪問的位置序列，其頻率不小于最小支持度Smin。第一步采用基于位置序列的方法挖掘用戶的軌跡序列，第二步從挖掘到的所有頻繁序列中找出最大頻繁子序列以確保具有大片相同片段的子序列是屬于不同時段的。

定義5：群體移動模式(crowedmobilitypattern)。表示所有個人移動模式的集合。由于人們經(jīng)常遵循相似的運動模式，所以利用可用用戶的軌跡來代表一群人的全局行為是可行的。利用每個用戶的歷史移動軌跡挖掘其移動模式，然后將它們合并以用于下一步的預(yù)測。

2.3 問題定義

用戶的下一簽到位置主要受到2個方面的影響：信任圈以及移動模式的影響。因此，將預(yù)測用戶下一個簽到位置問題形式化：當(dāng)已知集合Ct和Ch時，目標(biāo)是計算出用戶在t時間訪問下一個簽到位置l的概率?；谝陨闲问交x，本文將位置預(yù)測概率定義為：

P(l)=P(l|Ct,Ch)

(1)

信任圈以及移動模式的影響力可以作為2個獨立的模塊，采取類似于文獻(xiàn)[16]提出的組合方法來計算位置預(yù)測概率：

(2)

其中，λ表示一個控制信任圈關(guān)系以及個人歷史移動模式的影響權(quán)重的常數(shù)參數(shù)。

2.3.1信任圈的影響力

在本小節(jié)中，通過計算信任圈系數(shù)來測量三類社交關(guān)系對用戶的影響力。利用加權(quán)的方法，信任圈的模型可以進(jìn)一步展開為：

(3)

通過分析圖2，發(fā)現(xiàn)3個社交關(guān)系的函數(shù)曲線類似于S形函數(shù)，即：隨著累計簽到數(shù)量的增加，用戶之間的共現(xiàn)率隨之增加，并且最終趨于穩(wěn)定。因此，本文將相關(guān)系數(shù)θ1、θ2、θ3作為激活函數(shù):

(4)

其中，f1表示k階信任關(guān)系中的用戶簽到特征向量，W1表示特征向量f1的權(quán)重矩陣，b1表示偏置項。相關(guān)系數(shù)θ2和θ3的定義如下：

(5)

(6)

其中，f2表示n度鄰近關(guān)系中的用戶簽到特征向量，W2表示特征向量f2的權(quán)重矩陣，b2表示偏置項。f3表示共現(xiàn)關(guān)系中的用戶簽到特征向量，W3表示特征向量f3的權(quán)重矩陣，b3表示偏置項。

(7)

考慮到信任圈的多元性，本文融合信任圈關(guān)系和簽到位置關(guān)系來計算相關(guān)系數(shù)，如式(8)所示。

(8)

2.3.2用戶移動模式的影響力

用戶移動的模式可以分為兩類：一種是用戶u直接從目標(biāo)位置lj到侯選位置lk的情況，稱為直接訪問模式，用符號M表示；另一種是用戶u從目標(biāo)位置lj到侯選位置lk之前還訪問過其他位置的情況，稱為多元訪問模式，用符號M*表示。不同的移動模式在模型中占有不同的權(quán)重，因此，利用加權(quán)的方法，用戶移動模式模型進(jìn)一步展開為式(9)。

P(l|Ct)=ηP(l|M)+(1-η)P(l|M*)

(9)

其中，η表示一個控制不同移動模式權(quán)重的常數(shù)。

(10)

為了方便計算從位置lx到位置ly之間的移動概率，將觀察到的所有用戶uj在時間ti從當(dāng)前位置lx到目標(biāo)位置ly的移動轉(zhuǎn)換列舉出來，并利用式(11)計算群體移動模式。

(11)

因此，直接訪問模式下的概率模型可以擴展表示為：

(12)

2) 多元訪問模式：由于簽到集中可能存在數(shù)據(jù)缺失的情況，本文提出了多元移動模式，即用戶u從當(dāng)前位置lx到目標(biāo)位置ly的移動過程中額外至少經(jīng)歷過(n+1)個位置。

給定當(dāng)前位置ly時，計算在t時刻它作為目標(biāo)位置的概率，即數(shù)據(jù)集中所有其他位置在時間t到達(dá)位置ly的移動行為的概率，計算公式如下:

(13)

2.4 融合框架

本文提出了融合信任圈和移動模式的框架FTM用于預(yù)測用戶的下一個簽到位置。根據(jù)式(2)和(9)，框架FTM最終定義為式(14)。

θ3*P(l|Rc))+(1-λ)(η*P(l|M)+

(1-η)*P(l|M*))

(14)

3 實驗結(jié)果與分析

本節(jié)將介紹實驗環(huán)境、數(shù)據(jù)集、評價指標(biāo)、基準(zhǔn)方法、參數(shù)選取與實驗分析。為了驗證提出的FTM框架的性能，本節(jié)工作包括：分析了FTM框架中不同因素的影響權(quán)重，通過評估其在不同設(shè)置的實驗條件下的準(zhǔn)確率來確定實驗參數(shù)；與其他具有代表性的先進(jìn)算法對比預(yù)測結(jié)果的準(zhǔn)確率并分析造成差異的原因；通過改變空間閾值來分析FTM框架的魯棒性。

3.1 實驗環(huán)境

實驗硬件環(huán)境如表1所示。

表1 實驗環(huán)境

3.2 數(shù)據(jù)集介紹

為了評估FTM框架的性能，在公開數(shù)據(jù)集上進(jìn)行實驗。由于模型中使用了信任圈模塊，本文使用遞歸神經(jīng)網(wǎng)絡(luò)來計算用戶的家庭位置。為了保證實驗的有效性，實驗中篩選至少包含80條簽到記錄的用戶，并且刪除了不滿20條簽到數(shù)據(jù)的位置數(shù)據(jù)。為了避免實驗結(jié)果的偶然性，本文根據(jù)用戶的簽到時間將數(shù)據(jù)集劃分為訓(xùn)練集和測試集，按照時間順序，每個用戶的70%的簽到記錄用于訓(xùn)練，剩下30%用于測試，實驗數(shù)據(jù)集參數(shù)如表2所示。

表2 實驗數(shù)據(jù)集參數(shù)

數(shù)據(jù)集描述如下：

1) Gowalla數(shù)據(jù)集：該數(shù)據(jù)集包含3 112名用戶在3 298個地點27 149條附帶時間戳的簽到記錄，其中包括3 776條用戶社會關(guān)系記錄。

2) Foursquare數(shù)據(jù)集：該數(shù)據(jù)集包含來自923 506名用戶在4 960 482個地點35 289 629次附帶時間戳的簽到記錄，其中包括4 751 635條用戶社會關(guān)系記錄。

3.3 評價指標(biāo)

本文使用預(yù)測準(zhǔn)確率指標(biāo)Accuracy來評價模型的性能。計算每個候選位置的概率后，返回排名top-N作為預(yù)測的結(jié)果。只要用戶的實際簽到位置出現(xiàn)在top-N中就認(rèn)為預(yù)測是準(zhǔn)確的[18]。采用Accuracy@N表示不同N取值的預(yù)測準(zhǔn)確率，在實驗中N的取值為1、5、10。

3.4 基準(zhǔn)方法

為了說明FTM框架位置預(yù)測的性能，本文引入以下方法進(jìn)行比較。

1) MFC(mostfrequentcheck-inmodel)模型[19]是預(yù)測用戶下一簽到位置的經(jīng)典指標(biāo)，該模型將用戶u在位置l簽到的概率定義為位置l出現(xiàn)在用戶u的簽到歷史記錄中的概率。

2) FSM(feature-based supervised model)模型[20]提出了最直接競爭對手的概念，利用一組描述用戶運動模式的時空特征矩陣來預(yù)測下一簽到位置，在此基礎(chǔ)上將這些特征組合到監(jiān)督學(xué)習(xí)模型中。

3) FPM (feature-based personalized model)模型[3]基于矩陣分解的方法嵌入個性化馬爾可夫鏈。該模型不僅改進(jìn)了簽到序列中的個性化馬爾可夫鏈，還考慮了在局部區(qū)域內(nèi)用戶移動行為中存在的約束因素。

4) PSMM(periodic social mobility model)模型[21]通過觀察用戶在一天中的某些時間段表現(xiàn)出的強烈周期性行為，計算目標(biāo)用戶在目標(biāo)時間內(nèi)最有可能停留的區(qū)域，達(dá)到預(yù)測用戶下一個簽到位置的效果。

5) PRED(periodic region detection)模型[22]是貝葉斯非參數(shù)模型，通過混合地理信息和時間信息建模來發(fā)現(xiàn)用戶的周期性流動模式。由于其為非參數(shù)的模型，所以不需要關(guān)于個體流動性的先驗知識。

3.5 參數(shù)選擇

在選擇參數(shù)λ和η時，它們的取值在0～1變化，進(jìn)行了200次實驗，步長增量設(shè)置為0.05。

從圖5和圖6中可以發(fā)現(xiàn)，當(dāng)λ=0.25，η=0.75時FTM可以達(dá)到最佳性能。參數(shù)λ用于控制信任圈模塊的權(quán)重，將η固定為0.75，以0.05為步長將參數(shù)λ從0增加到1，從圖5中可以發(fā)現(xiàn)，當(dāng)λ=0.25時達(dá)到最高準(zhǔn)確率。當(dāng)λ=0.05時，這種情況幾乎只考慮用戶的歷史移動模式，沒有考慮信任圈的影響，實驗結(jié)果表明它的準(zhǔn)確性不是最佳，進(jìn)而表明不能僅考慮用戶的歷史移動模式，需要進(jìn)一步考慮額外的影響因素，個體用戶的時空行為并不是一塵不變的，具體來說需要重視社交關(guān)系對用戶判斷產(chǎn)生的影響，當(dāng)提高信任圈模塊的權(quán)重時，模型的準(zhǔn)確率會提升；當(dāng)λ=0.25時，預(yù)測準(zhǔn)確率最高，模型的預(yù)測性能達(dá)到最佳，說明它是信任圈和移動模式模塊的最佳權(quán)重。

圖5 不同λ值下的預(yù)測準(zhǔn)確性

圖6 不同η值下的預(yù)測準(zhǔn)確性

此外，從圖6中可以看出，用戶移動模式模塊具有更高的權(quán)重，說明模型在預(yù)測中用戶歷史移動模式比信任關(guān)系的影響更大；當(dāng)λ=0.95時，表明過度強調(diào)了信任圈的影響，導(dǎo)致預(yù)測的準(zhǔn)確率最差，說明僅僅考慮信任關(guān)系是不足以來預(yù)測用戶行為的。參數(shù)η用于控制用戶歷史移動模式模塊的影響，將λ固定為0.25，以0.05為步長將參數(shù)η從0增加到1。

從圖6中可以發(fā)現(xiàn)，當(dāng)η=0.75時達(dá)到最高準(zhǔn)確率，這表明直接訪問模式對于挖掘用戶的隱性移動模式有重要的影響。當(dāng)η=0.15時預(yù)測的準(zhǔn)確率較低但不為0，證實了考慮多元訪問模式的必要性，即通常情況下用戶的移動模式都屬于直接訪問，但因部分?jǐn)?shù)據(jù)集缺失或其他因素導(dǎo)致未能充分挖掘該用戶的移動行為，本文考慮潛在的多元訪問模式有效彌補了這一缺陷。

對于用戶的k階信任關(guān)系，本文將k設(shè)置成一個可變的參數(shù)，分別把k的取值設(shè)置為從1～20變化。圖7展示了在k的不同取值下預(yù)測準(zhǔn)確率的變化，可以觀察到隨著k值的增加，F(xiàn)TM的性能在不同的top-N下減少。因此可以得出結(jié)論，信任關(guān)系的等級對用戶的選擇有顯而易見的影響，信任等級越高造成的影響越大。

根據(jù)文獻(xiàn)[23]可知，個體用戶能與周圍用戶保持穩(wěn)定的社會關(guān)系的理論上限值，即任何人的社交關(guān)系都存在上限值。對于用戶的n度鄰近關(guān)系，本文將n的取值設(shè)置為1～5，因為只有部分社會關(guān)系與用戶真正保持緊密聯(lián)系，其他社會關(guān)系對用戶的影響幾乎可以忽略不計[24]。如圖8所示，F(xiàn)TM的性能隨著參數(shù)n取值的增加而減少，這是因為過多的社會關(guān)系削弱了親密朋友的影響力，從而降低了預(yù)測的準(zhǔn)確率。

圖7 不同k值下的預(yù)測準(zhǔn)確性

圖8 不同n值下的預(yù)測準(zhǔn)確性

3.6 位置預(yù)測準(zhǔn)確性對比

表3展示了在不同數(shù)據(jù)集上的不同算法的預(yù)測準(zhǔn)確率，可以看出FTM在所有模型中均表現(xiàn)最佳，平均準(zhǔn)確率可以達(dá)到92.6%以上。

表3 實驗結(jié)果

MFC模型雖然提供了較準(zhǔn)確的預(yù)測，然而，考慮了用戶的信任關(guān)系的FTM模型表現(xiàn)出更好的預(yù)測結(jié)果，尤其是在規(guī)模較大的Foursquare數(shù)據(jù)集上。FSM模型利用了描述用戶運動模式的時空特征矩陣，但準(zhǔn)確率相對較低，尤其是在數(shù)據(jù)集規(guī)模較小的Gowalla上。FSM模型比MFC模型的準(zhǔn)確率高出約4.2%，但其準(zhǔn)確率遠(yuǎn)低于FTM模型，原因在于僅考慮用戶的局部特征。PSMM模型的準(zhǔn)確率比FTM模型略差，因為其沒有考慮信任圈對用戶的影響，與FPM模型相比，它提高了大約20.6%的準(zhǔn)確率。PRED模型綜合考慮了地理信息和時間信息，也表現(xiàn)出較高的預(yù)測性能，但缺乏對用戶個體的考慮，所以準(zhǔn)確性較低于FTM模型。Gowalla和Foursquare這2個數(shù)據(jù)集的主要區(qū)別在于數(shù)據(jù)集的規(guī)模大小相差較大，所以在規(guī)模較小的數(shù)據(jù)集上，注重考慮局部信息的FPM模型準(zhǔn)確率較高，在規(guī)模較大的數(shù)據(jù)集上，考慮多元信息的PRED模型準(zhǔn)確率較高，而綜合考慮社交元素和個體因素的FTM模型在不同規(guī)模的數(shù)據(jù)集上性能表現(xiàn)都是最佳的。

從圖9可以更直觀地發(fā)現(xiàn)：FTM模型的性能優(yōu)于其他基準(zhǔn)方法，這是因為FTM不僅考慮個體特有的移動模式，還考慮了多元社交信息的影響。具體來說，從圖9(a)發(fā)現(xiàn)：由于Gowalla數(shù)據(jù)集規(guī)模較小，更多描述了用戶個人特有的行為，而不能代表人群的通用習(xí)慣，對某些用戶的信任圈的了解有限，導(dǎo)致FTM模型中的信任關(guān)系模塊不能充分發(fā)揮作用，所以模型在Gowalla上表現(xiàn)的性能較低于在Foursquare上的性能。相反，從圖9(b)發(fā)現(xiàn)：由于Foursquare數(shù)據(jù)集融合了更多描述人群規(guī)律的特征，適用于預(yù)測更廣泛的用戶群體行為規(guī)律[25]，挖掘到的移動模式序列更具體，因此預(yù)測準(zhǔn)確率更高。

圖9 位置預(yù)測率柱狀圖

本文進(jìn)行了另一組實驗來觀察空間閾值變化對FTM性能的影響[26]，將性能表現(xiàn)最好的Accuracy@10作為評價標(biāo)準(zhǔn)。

實驗結(jié)果如圖10所示，結(jié)果表明大部分模型的準(zhǔn)確率隨著空間閾值的增加而增加，F(xiàn)TM預(yù)測準(zhǔn)確率明顯優(yōu)于其他算法的同時，表現(xiàn)出了更高的魯棒性。

圖10 不同空間閾值下算法的預(yù)測準(zhǔn)確率曲線

從圖10(a)可以發(fā)現(xiàn)，F(xiàn)TM模型和PRED模型的準(zhǔn)確率增加的幅度更大，因為這2種算法都考慮多種影響因素，空間閾值的增大可以挖掘出更豐富的用戶行為信息。相反，F(xiàn)PM和PSMM模型的準(zhǔn)確率隨著空間閾值增加而減少，這是因為僅考慮個體的單一影響因素存在局限性，這類算法更適用于預(yù)測特定個體的位置。從圖10(b)可以發(fā)現(xiàn)，在Foursquare這種規(guī)模較大的數(shù)據(jù)集中，空間閾值的增大對預(yù)測準(zhǔn)確率的影響更大，因為它允許在更多情境中預(yù)測下一個位置。FPM模型受閾值變化的影響尤其明顯，與其他模型不同，該模型的準(zhǔn)確率隨著閾值的變化而減少，這是因為僅考慮局部因素導(dǎo)致的結(jié)果。同樣，僅使用個體特征的PSMM模型表現(xiàn)不佳，因為該方法無法利用信任關(guān)系來彌補空間閾值變化導(dǎo)致的差距。結(jié)合圖10可以發(fā)現(xiàn)，F(xiàn)TM模型、MFC模型以及FSM模型的準(zhǔn)確率都隨著空間閾值的增加而增加，而FTM模型的準(zhǔn)確率是最高的，這是因為MFC模型考慮的影響因素較少，僅僅分析簽到序列是不足以準(zhǔn)確預(yù)測下一個簽到位置的。FSM模型融入了直接競爭對手的概念，但是對其他社交關(guān)系的考慮頗為欠缺，導(dǎo)致預(yù)測的準(zhǔn)確率較低于FTM模型。綜合之前的實驗，F(xiàn)TM在規(guī)模大的數(shù)據(jù)集Foursquare上預(yù)測準(zhǔn)確率更高，因為用戶的信息更豐富從而挖掘得到的線索越精確。

4 結(jié)論

本文提出了一種新的融合信任圈和移動模式的位置預(yù)測框架。在信任圈模塊中，考慮了不同信任關(guān)系對用戶選擇的影響。在歷史移動模式模塊中，分別考慮了用戶的直接訪問模式和多元訪問模式。在真實數(shù)據(jù)集上評估了不同模型的性能，實驗結(jié)果表明，本文提出的FTM模型在準(zhǔn)確率指標(biāo)方面優(yōu)于其他算法，并且較其他先進(jìn)算法表現(xiàn)出更好的魯棒性。未來工作包括：進(jìn)一步拆分信任圈，從中挖掘其他社交關(guān)系對個體的影響并加入到預(yù)測模型中，并且在改進(jìn)移動模式模塊中挖掘用戶多元移動模式的算法，進(jìn)一步提高預(yù)測的準(zhǔn)確性。