王三軍　王玉姣

摘要摘要：隨著位置社交網(wǎng)絡(luò)的快速增長，越來越多的人借助其分享他們的喜好和位置信息，利用這些信息的潛在規(guī)律和呈現(xiàn)出來的偏好特征能夠有效地幫助用戶發(fā)現(xiàn)他們真正感興趣的地點。然而，用戶歷史記錄數(shù)據(jù)存在著嚴重的稀疏性，導(dǎo)致推薦結(jié)果不準確。鑒于此，融合地理位置因素和用戶社交關(guān)系，利用矩陣分解模型提出了一種興趣點推薦（GSMF算法）。實驗結(jié)果表明，與主流的興趣點推薦算法相比，該方法在準確率和召回率等多項指標上均取得了更好的結(jié)果。

關(guān)鍵詞關(guān)鍵詞：地點推薦；社交關(guān)系；地理因素；GSMF算法

DOIDOI：10.11907/rjdk.171342

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2017）005003405

0引言

近年來，隨著Web2.0技術(shù)的快速發(fā)展，多種地理信息系統(tǒng)已成功實現(xiàn)，如Google公司的Google Earth、微軟的MSN Visual Earth等，位置服務(wù)和在線社交網(wǎng)絡(luò)趨于融合，基于位置的社交網(wǎng)絡(luò)（LBSNs）[13]也在日益興起，如：Foursquare、Facebook等。用戶通過基于位置的社交網(wǎng)絡(luò)平臺以簽到的形式分享他們根據(jù)自己的喜好而探索的興趣地點和各種信息。通過對這些豐富的簽到信息進行挖掘，可以將其與用戶的其它特征結(jié)合起來，形成基于用戶的歷史記錄的興趣庫。用戶既可以通過興趣庫為其他用戶（如朋友）推薦自己感興趣的位置點和社交場所，并且也可以幫助相關(guān)企業(yè)分析用戶的興趣從而為用戶提供更加個性化的服務(wù)。

目前，在已有的推薦算法中，較為普遍的是通過用戶的歷史簽到記錄尋找相似用戶來進行協(xié)同過濾推薦。然而，由于用戶簽到數(shù)據(jù)存在嚴重的稀疏性問題，相似用戶的識別一直很困難，導(dǎo)致已有的地點推薦方法效果都不好。為了提高推薦效果，有研究中采用一些簽到的輔助信息，例如用戶的社交信息[45]、地理位置[6]、情景因素[7]。然而，基于已有工作而建立的模型大多都只是從某一輔助信息出發(fā)，假設(shè)推薦對象之間相互獨立，從而建立一種靜態(tài)模型，忽略了相關(guān)輔助信息之間的內(nèi)在聯(lián)系在許多應(yīng)用場景下對最終推薦效果產(chǎn)生的影響，從而導(dǎo)致推薦結(jié)果不準確。

為了能更好地對推薦過程進行建模，從而體現(xiàn)出推薦對象間的關(guān)聯(lián)關(guān)系對推薦結(jié)果產(chǎn)生的影響。本文在已有的基于矩陣分解的經(jīng)典推薦算法基礎(chǔ)上，提出一種解決現(xiàn)有問題的新思路——融合地理位置和用戶社交關(guān)系的興趣點推薦算法，即Geographical and Social Matrix Factorization（GSMF）算法。實驗結(jié)果表明，與相關(guān)主流算法相比，該算法在推薦準確率、召回率等指標上得到了有效提高。

1相關(guān)研究

Ye等[8]受基于好友之間分享較多共同興趣的觀點啟發(fā)，深入研究基于LBSNs的地點推薦方法中用戶之間的好友關(guān)系，通過分析來自Foursquare的數(shù)據(jù)集，發(fā)現(xiàn)好友關(guān)系與地理位置之間的強關(guān)聯(lián)性，進而提出一種基于好友關(guān)系的協(xié)同過濾推薦方法，該方法通過概率模型體現(xiàn)好友社會關(guān)系對地點推薦的影響。Gao等[9]在LBSNs中將矩陣因式分解與位置和社交影響力融合起來進行研究，將社交信息、地理影響力融入到一個廣義矩陣分解的框架中，他們將用戶在位置上的簽到概率模型作為多中心高斯模型來捕獲地理影響力，該方法能夠有效改進推薦性能。

Cheng等[10]通過22萬用戶收集2 200萬個簽到數(shù)據(jù)，并從分析空間、時間、社交和文本等相關(guān)用戶足跡幾大方面定量評估用戶移動性模式，發(fā)現(xiàn)：①基于位置的社交網(wǎng)絡(luò)用戶遵循“Levy Flight”移動模式并采用周期性的行為；②地理和經(jīng)濟限制條件影響著移動的模式和用戶的社會地位；③與簽到相關(guān)的基于內(nèi)容和情感的微博分析能夠為更好地理解用戶參與這些服務(wù)并提供更加豐富的語境來源。Ye等[11]考慮到地理位置的影響，通過假設(shè)簽到概率和地理距離是冪律分布的，從而取得良好推薦效果。然而，用所提出的協(xié)同過濾方法在解決大規(guī)模數(shù)據(jù)集時存在時間耗費較長等缺點。Cheng等[12]將用戶社交關(guān)系融入概率矩陣分解框架中，但是他們首先通過建立用戶在位置上簽到的概率模型，繼而才將社交信息和地理信息融入一個廣義的矩陣分解模型中。Liu等[13]主要從地理的角度，因近鄰地點往往有著相似用戶的興趣愛好，所以將地理位置融入矩陣分解模型中，能夠更準確地預(yù)測用戶喜好。Brent Hecht等[14]對Twitter用戶資料中與位置領(lǐng)域相關(guān)的用戶行為進行研究，發(fā)現(xiàn)用戶的國家和地區(qū)事實上能夠很容易精準確定，從而表明通過用戶的隱含信息揭示位置信息與用戶偏好之間的聯(lián)系。

然而，利用輔助信息的協(xié)同過濾推薦方法時間耗費較長，單一信息利用矩陣模型進行推薦的方法其推薦結(jié)果不準確。鑒于此，本文融合多因素利用矩陣模型推薦的新思路能夠?qū)崿F(xiàn)更高效的推薦。

2GSMF算法模型

興趣點的矩陣分解，特別是針對隱式數(shù)據(jù)的矩陣分解的引入很重要，因為這不僅能夠幫助理解如何在給定位置信息情況下推薦興趣點，而且可以幫助解釋為何對于空間聚集效應(yīng)的建?？梢詰?yīng)對來自于矩陣分解稀疏性的挑戰(zhàn)，更重要的是，這可能會提升位置推薦的性能。為此，本文綜合地理位置和用戶社交關(guān)系兩種因素，提出一種基于地理位置和用戶社交關(guān)系的矩陣分解模型的興趣點推薦算法——Geographical and Social Matrix Factorization（GSMF）算法。

2.1地理位置建模

用戶在興趣點的簽到記錄包含著許多物理信息，因此引用了文獻[11]中一個真實數(shù)據(jù)集的用戶簽到活動空間分析，該數(shù)據(jù)集是眾所周知的Foursquare數(shù)據(jù)集。文獻[11]中距離和用戶興趣點的關(guān)系如圖1所示，其中橫軸表示用戶距離常居地的距離，縱軸表示在此距離上簽到記錄所占比例。線性部分占近90% 的簽到記錄，顯示了用戶簽到距常居地一般都很短，這也就形成了常居地附近地點類簇的現(xiàn)象。這一現(xiàn)象可以歸因于地理影響，可以直觀地作如下解釋：①人們往往訪問的興趣點接近于他們的家庭或者辦公室；②人們可能對某個興趣點周圍的興趣點也很感興趣，即使該興趣點距離其常居地較遠。因此，用戶的簽到地點往往是形成地理集群區(qū)域。根據(jù)用戶簽到的地理集群現(xiàn)象可以進行精確的興趣點推薦。下文將根據(jù)該現(xiàn)象研究地理位置對用戶簽到行為的興趣點推薦有何影響。

為了實現(xiàn)這一目標，對地理位置進行興趣推薦建模。如上分析，用戶大多數(shù)傾向于在離常居地近的地點簽到，因而本文只對距離當前用戶常居地近的興趣點進行考慮，對于過遠的地點則不加以考慮。

將用戶和地點映射到一個共享的潛在空間，矩陣分解能夠有效估計大多數(shù)近乎所有地點的整體關(guān)系。然而，經(jīng)典的矩陣分解忽略了地理近鄰位置之間的強關(guān)系。從用戶簽到表中分析得到，最近的近鄰地點更傾向于分享共同的用戶。受這一觀點的啟發(fā)，本文提出用戶ui對地點lj的偏好可用其對地點lj幾個近鄰地點的偏好表示，設(shè)R=ULT，因此本文修改i，j如下：

rnewi，j=αuilTj+（1-α）∑lk∈N（lj）sim（lj，lk）uilTk（1）

其中，i，j是矩陣中的一個元素，α∈[0，1]，是一個加權(quán)參數(shù)，用于控制近鄰地點的影響。該算法認為由于人的行動所限制，只考慮離當前用戶近的地點。比如，用戶在北京旅游，系統(tǒng)推薦廈門的旅游景點給他，那他是不會接受該推薦的。因此算法提出了一個距離限制的變量：N，N（lj）是地點lj的N組鄰近的地點，在實驗中，根據(jù)經(jīng)驗值設(shè)置N=10，如果待推薦的地點不在用戶當前位置的N（lj）中則不考慮該地點。N可以根據(jù)用戶或者應(yīng)用需求進行設(shè)置。

sim（lj，lk）表示近鄰地點lk在地點lj地理位置的權(quán)重，據(jù)前人研究表明，地理鄰近的的相似位置往往會有同一用戶的訪問，其可用如下的高斯函數(shù)來表示sim（lj，lk）兩個地點的相似度。

sim（lj，lk）=11+D（li，lj）σlk∈N（lj）（2）

其中xj、xk分別表示地點lj、lk的地理坐標（經(jīng)度和緯度），σ用來表示真實距離到地點位置相似度的放縮關(guān)系，設(shè)置為1。

本文方法不同于文獻[9]，本文考慮地點lj附近的近鄰地點N（lj）之間的關(guān)系，用戶ui對地點lj的偏好是由ui、lj和N（lj）決定。然而，文獻[9]用戶ui對地點lj的偏好預(yù)測是由地點lj與用戶ui訪問過的地點L（lj）之間的距離來預(yù)測的。一般地，N（lj）和L（lj）是完全不同的或者有很小的重疊，這是因為用戶ui簽到的地點只占到很小的比例。因此這兩種方法是由不同的地理位置來建模的。文獻[13]中同時考慮到了地點更遠的一些區(qū)域，而本文只考慮用戶一定范圍的區(qū)域，另外融入用戶社交關(guān)系進行多因素預(yù)測。

2.2用戶社交關(guān)系建模

文獻[18]表明，大多數(shù)用戶傾向于朋友對他推薦的東西，由此可見，朋友之間推薦的信任度非常高，因此社交影響對推薦系統(tǒng)的影響不可忽視。通常用戶間的社交因子可以通過他們是不是好友來決定。但是可以發(fā)現(xiàn)，社交網(wǎng)絡(luò)上的用戶并非與其所有好友的簽到行為具有相似性，就像現(xiàn)實生活中一樣，好友可能有很多，但興趣品味相一致的只有少數(shù)幾個。文獻[19]提出好友間的社交因子還與他們的共同好友相關(guān)。

用戶ui與其朋友uf之間的相似度因子s（i，f）由他們是否為好友和他們的共同好友計算得到。計算公式如式（3）所示。

s（i，f）=η×i，f+（1-η）×|Fi∩Ff||Fi∪Ff|（3）

其中，η∈[0，1]，是一個可調(diào)節(jié)參數(shù)。i，f表示用戶ui和他朋友uf是否為好友關(guān)系，若是好友關(guān)系則i，f=1，否則，i，f=0。Fi是用戶ui的朋友數(shù)據(jù)集，F(xiàn)f是用戶uf的朋友數(shù)據(jù)集。

基于用戶的朋友之間有著相似的興趣愛好，將這一因素融入矩陣分解模型中。因此，本文添加社交因素進一步優(yōu)化矩陣分解模型如下：

minU，L12||W⊙（R-）||2F+λ12||U||2F+λ22||L||2F+λ32∑mi=1∑f∈Fis（i，f）||Ui-Uf||2（4）

2.3GSMF推薦算法

根據(jù)前面考慮的兩種因素，本文將地理位置和用戶社交關(guān)系這兩個因素融入矩陣分解模型中，提出GSMF算法。該算法不僅考慮了推薦地點與用戶當前位置的距離，同時也能根據(jù)用戶的社交關(guān)系使推薦的效果更好。

將上文中加入地理因素的式（2）和加入社交因素的式（3）帶入式（4）中，得到GSMF算法的最小化加權(quán)正規(guī)化的平方誤差損失公式優(yōu)化如下：

minU，LY（U，L）=12||W⊙（R-ULTPα）||2F+λ12||U||2F+λ22||L||2F+λ32∑mi=1∑f∈Fis（i，f）||Ui-Uf||2（5）

其中，W∈Rm×n是一個權(quán)重矩陣；⊙是兩個矩陣的Hadamard乘積；Pα=αI+（1-α）PT，I∈Rn×n是單位矩陣；P∈Rn×n，且Pj，k=sim（lj，lk）。s（i，f）是用戶ui和他朋友uf之間的相似度因子。λ1、λ2是控制用戶和地點矩陣的權(quán)重參數(shù)，λ3是控制社交關(guān)系的權(quán)重參數(shù)。||U||2F、||L||2F分別用來控制用戶和地點的過度擬合。

由于目標函數(shù)存在多個變量，可以用一個合適的算法來得到這兩個變量U和L。其核心思想就是固定其它參數(shù)變量，使目標函數(shù)最小化。該算法將會保持更新變量直至收斂或者達到最大的迭代次數(shù)。

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

實驗過程如下：搭建實驗環(huán)境、介紹實驗數(shù)據(jù)集、進行算法驗證。實驗使用了Foursquare以及Gowalla兩個數(shù)據(jù)集，分別從準確率和召回率兩個方面對不同的算法進行實驗，最后對實驗結(jié)果進行分析。從準確率和召回率兩個方面進行分析，結(jié)果表明，本文提出的GSMF推薦算法是有效的。

3.1實驗數(shù)據(jù)集與實驗環(huán)境

為了驗證推薦算法的準確性，對于兩個數(shù)據(jù)集都進行預(yù)處理，都僅保留了每天至少訪問5個位置的活躍用戶。同時將各種數(shù)據(jù)分為訓(xùn)練集和測試集，訓(xùn)練集用來學習或訓(xùn)練推薦方法中的相關(guān)參數(shù)，測試集用來驗證推薦的準確性。為了保證在訓(xùn)練集和測試集中都有評分數(shù)據(jù)，按一定的比例隨機地將兩個數(shù)據(jù)集分為訓(xùn)練集和測試集。本文實驗中按 8：2的比例將數(shù)據(jù)隨機地分為訓(xùn)練集和測試集。

本實驗使用的Foursquare數(shù)據(jù)集由亞利桑那州立大學計算機學院采集提供。Foursquare數(shù)據(jù)集主要包括的內(nèi)容有：用戶簽到記錄數(shù)據(jù)、用戶的常居地數(shù)據(jù)以及用戶的好友關(guān)系數(shù)據(jù)。在這里面，邊（好友關(guān)系）的數(shù)量為47 164條，朋友關(guān)系數(shù)據(jù)中節(jié)點數(shù)量（用戶）為11 326個，簽到數(shù)據(jù)的數(shù)量是1 385 223條。Gowalla數(shù)據(jù)集包含的簽到數(shù)據(jù)為456 988條，用戶數(shù)量為10 162，地點個數(shù)為24 250。

本文實驗環(huán)境為：Windows7（64位）操作系統(tǒng)，4GB DDR3內(nèi)存，Intel CPU i3 M350 2.27GHz CPU，實驗程序使用Matlab2014版本。

3.2評價指標

在本文中，使用準確率和召回率作為位置推薦的評價指標[1112]來評估 top-k推薦的性能。準確率和召回率分別用P@k和R@k來表示。對一個目標用戶ui，P@k表示前k個被推薦的興趣點會包括多少比例的測試訪問地點。R@k是指前k個被推薦興趣點中有多少比例是這個用戶訪問過的。LT（ui）表示用戶ui簽到過的地點，LR（ui）表示前k個被推薦的興趣點。P@k和R@k定義如下：

P@k=1|T|∑ui∈T|LT（ui）∩LR（ui）|k（8）

R@k=1|T|∑ui∈T|LT（ui）∩LR（ui）|LT（ui）（9）

其中，T表示測試數(shù)據(jù)中用戶的數(shù)量。在實驗中，選擇P@5、P@10、R@5和R@10作為評價指標。

3.3對比算法設(shè)計與參數(shù)設(shè)置

①USG：文獻[11]提出的融合用戶偏好、地理影響基于線性融合框架的POI興趣點推薦算法；②MFSR：文獻[18]提出的模型，將用戶的社交網(wǎng)絡(luò)關(guān)系考慮到推薦模型中，此方法沒有考慮產(chǎn)品之間的聯(lián)系；③PMF：文獻[20]提出的概率矩陣分解方法，此方法也沒有考慮產(chǎn)品之間的聯(lián)系；④MGMMF：文獻[12]提出的通過多中心高斯模型來捕獲地理影響力，繼而把社交信息和地理影響力融入到一個廣義矩陣因式分解的框架中。

k的值分別設(shè)置為5、10。每改變一次k值，為每一個算法計算準確率P@k和召回率R@k。在實驗中，考慮實驗的效果和有效性，設(shè)置隱式空間維數(shù)r為200。λ1、λ2是控制用戶和地點矩陣的權(quán)重參數(shù)，通過交叉驗證設(shè)置為0.015，λ3是控制社交關(guān)系的權(quán)重參數(shù)，設(shè)置為0.01。由文獻[12]可知，當只考慮距離用戶近的地點時，公式（1）中的地理位置權(quán)重α在為0.4時推薦效果最佳，因此本實驗設(shè)置α為0.4。

3.4實驗結(jié)果分析

實驗1：不同特征向量維度下的算法比較分析。

如圖2和表1可知，真實的Foursquare數(shù)據(jù)集和Gowalla數(shù)據(jù)集表明，由于分別加入對社交關(guān)系影響和地理位置因素的影響，PMF算法、MFSR算法和MGMMF算法比較而言，無論是在準確率還是召回率，都有更好的結(jié)果。因為MFSR算法是在PMF算法中融入了社交因素，而MGMMF算法是在PMF算法中融入了地理位置，同時該算法采用多中心高斯模型來對地理位置進行建模。而本文算法由于同時融合上述2種因素，相對于MFSR算法和MGMMF算法，在Foursquare數(shù)據(jù)集上（k=5）準確率分別提高了27.2%和16.6%，召回率分別提高了35.7%和11.8%，在Gowalla數(shù)據(jù)集上（k=5）準確率分別提高了30%和18.2%，召回率分別提高了36.6%和9.3%。而且本文提出的算法對地理位置建模和社交關(guān)系建模上都采用廣義矩陣分解的模型，因此無論是準確率還是召回率，與USG算法（采用線性融合框架）相比，在Foursquare數(shù)據(jù)集上（k=5）準確率和召回率分別提高了6.06%和5.56%，在Gowalla數(shù)據(jù)集上（k=5）準確率和召回率分別提高了4%和-3.52%。這個結(jié)果表明本文的算法雖然沒有十分顯著的提高，但是進一步說明地理信息和用戶之間的社會關(guān)系信息對傳統(tǒng)協(xié)同過濾算法精度的提高起著較大作用，同時說明基于矩陣分解模型的推薦算法優(yōu)于基于線性融合框架的推薦算法。

實驗2：不同稀疏度下的實驗結(jié)果比較。

為了研究數(shù)據(jù)稀疏對算法的影響，因此本文對原有的Foursquare數(shù)據(jù)集進行數(shù)據(jù)清洗，分別去掉10%、20%、50%的簽到記錄，這樣得到了3種不同的稀疏度，再按照標準情況的實驗流程進行實驗?？梢钥闯?，數(shù)據(jù)稀疏情況下，融合多種影響因素的協(xié)同過濾算法比基于用戶的協(xié)同過濾算法更能對好的推薦效果起主要作用。

本文在得出數(shù)據(jù)稀疏情況下算法的平均準確率后，與標準情況下的結(jié)果作比較，算出準確率降低的比例。數(shù)據(jù)稀疏情況下算法準確率降低比例的實驗結(jié)果如表1所示。

從圖3中可以看到，算法PMF的準確率下降最多，GSMF下降最少。GSMF算法在準確率上的降低比例相比USG算法降低了31%，能夠更好地處理數(shù)據(jù)稀疏的狀況，這說明基于矩陣分解模型的興趣點推薦算法比線性融合框架在數(shù)據(jù)稀疏情況下有更好的推薦效果。

4結(jié)語

本文提出了一種在興趣點推薦過程中考慮推薦對象的社會信息和地理信息的方法，并給出了將它們相結(jié)合的基于矩陣分解模型的推薦框架。真實數(shù)據(jù)集的實驗結(jié)果表明，推薦對象的社會信息和地理信息在推薦過程中起到了重要作用，對于提高推薦精度有著明顯的改善作用。另外，在興趣點推薦框架中，基于矩陣分解模型比基于線性融合模型框架更加高效。

未來工作中將進一步研究解決數(shù)據(jù)稀疏、冷啟動問題等給本文方法帶來的挑戰(zhàn)，并且研究如何將更多的信息，如時間信息、評論信息等加入到基于矩陣分解模型的推薦框架中，以進一步提高推薦效果。

參考文獻參考文獻：

[1]BACKSTROM L，SUN E，MARLOW C.Find me if you can：improving geographical prediction with social and spatial proximity[C].Proceedings of the 19th International Conference on World Wide Web，ACM，North Carolina，2010：6170.

[2]SCELLATO S，NOULAS A，MASCOLO C.Exploiting place features in link prediction on locationbased social networks[C].Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，San Diego，2011：10461054.

[3]MONREALE A，PINELLI F，TRASARTIR R，et al.Where next：a location predictor on trajectory pattern mining[C].In：Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，Paris，2009：637646.

[4]ZHENG V W，CAO B，ZHENG Y，et al.Collaborative filtering meets mobile recommendation：a usercentered approach[C].AAAI，2010：236241.

[5]MA H，ZHOU D，LIU C，et al.Recommender systems with social regularization[C].Proceedings of the Fourth ACM International Conference on Web Search and Data Mining.ACM，2011：287296.

[6]ZHENG V W，ZHENG Y，XIE X，et al.Collaborative location and activity recommendations with GPS history data[C].Proceedings of the 19th International Conference on World Wide Web.ACM，2010：10291038.

[7]李偉，陳毓芬，李萌，等.基于情境的POI個性化推薦方法研究[J].武漢大學學報：信息科學版，2015，40（6）：829833.

[8]YE M，YIN P，LEE W C.Location recommendation for locationbased social networks[C].Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM，2010：458461.

[9]GAO H，TANG J，HU X，et al.Contentaware point of interest recommendation on locationbased social networks[C].AAAI，2015：17211727.

[10]CHENG Z，CAVERLEE J，LEE K，et al.Exploring millions of footprints in location sharing services[C].SIGCHI Conference on Human Factors in Computing Systems.ACM，2011：237246.

[11]YE M，YIN P，LEE W C，et al.Exploiting geographical influence for collaborative pointofinterest recommendation[C].Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2011：325334.

[12]CHENG C，YANG H，KING I，et al.Fused matrix factorization with geographical and social influence in locationbased social networks[C].AAAI，2012：1723.

責任編輯（責任編輯：孫娟）