融合地理位置與社交關系的興趣點推薦算法

王三軍　王玉姣

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

關鍵詞關鍵詞：地點推薦；社交關系；地理因素；GSMF算法

DOIDOI：10.11907/rjdk.171342

中圖分類號：TP312

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

0引言

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

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

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

1相關研究

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

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

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

2GSMF算法模型

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

2.1地理位置建模

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

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

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

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

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

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

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

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

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

2.2用戶社交關系建模

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

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

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

其中，η∈[0，1]，是一個可調節參數。i，f表示用戶ui和他朋友uf是否為好友關系，若是好友關系則i，f=1，否則，i，f=0。Fi是用戶ui的朋友數據集，Ff是用戶uf的朋友數據集。

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

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

2.3GSMF推薦算法

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

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

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

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

3實驗結果與分析

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

3.1實驗數據集與實驗環境

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

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

本文實驗環境為：Windows7（64位）操作系統，4GB DDR3內存，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表示測試數據中用戶的數量。在實驗中，選擇P@5、P@10、R@5和R@10作為評價指標。

3.3對比算法設計與參數設置

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

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

3.4實驗結果分析

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

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

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

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

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

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

4結語

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

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

參考文獻參考文獻：

[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.

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