融合社交關系和局部地理因素的興趣點推薦

夏 英，張金鳳

重慶郵電大學 計算機科學與技術學院，重慶 400065

目前，隨著智能手機、移動互聯(lián)網(wǎng)等技術的發(fā)展，LBSN 得到廣泛應用，如國外的Gowalla、Foursquare，國內(nèi)的大眾點評、美團等。在LBSN 平臺，用戶可對當前訪問的POI（如餐廳、書店、旅游景點等）進行簽到、評論等操作，并能與社交好友分享自己的簽到信息。在LBSN除了用戶簽到信息，還包含社交關系、興趣點、用戶評論等海量數(shù)據(jù)，充分挖掘這些數(shù)據(jù)，可以更好地分析用戶的簽到行為，把握用戶群體興趣特征和訪問規(guī)律，有利于提高個性化POI推薦服務質量。

在LBSN平臺，POI的規(guī)模龐大且分布廣泛，而每個用戶訪問并簽到過的POI往往很少，這使得用戶簽到數(shù)據(jù)十分稀疏，給POI推薦帶來挑戰(zhàn)。

針對用戶簽到數(shù)據(jù)的稀疏性問題，本文提出基于社交關系和局部地理因素的POI推薦算法，通過融合社交關系、地理位置信息來豐富有效數(shù)據(jù)，提高推薦質量。本文的主要貢獻有以下三點：

（1）在構建社交關系影響模型時，綜合考慮用戶間的共同簽到和距離關系，提出一種用戶相似性度量方法，減少相似性計算誤差。

（2）在構建地理因素影響模型時，通過為每個用戶劃分一個局部活動區(qū)域，分析用戶所屬區(qū)域內(nèi)尚未訪問POIs 間的簽到相關性，更加充分地剖析出每個用戶簽到的地理偏好。

（3）在進行興趣點推薦時，將上述考慮的社交關系和局部地理因素融合到加權矩陣分解模型中，構建一個更加符合用戶偏好的POI推薦模型，在一定程度上緩解了數(shù)據(jù)稀疏性問題。實驗表明，本文所提出的算法具有更高的準確率和召回率。

1 相關工作

POI推薦是LBSN 中重要的個性化服務，旨在為用戶推薦符合他們興趣但尚未訪問過的POI列表。目前，針對位置社交網(wǎng)絡的POI推薦已展開大量的研究工作，一些特定場景的應用也開始大量涌現(xiàn)，如餐廳推薦[1]、旅游路線推薦[2]等。

目前，大多數(shù)的POI推薦都是通過用戶簽到數(shù)據(jù)結合豐富的上下文信息來緩解數(shù)據(jù)稀疏性，挖掘用戶對尚未訪問POIs 的偏好程度。如Cheng 等人[3]采用多中心高斯分布來建模POIs 間距離分布，并結合社交關系進行POI 推薦。Zhang 等人[4]為避免所有用戶采用統(tǒng)一分布造成的誤差，采用核密度估計模擬任意兩個POIs 間的距離分布，構建地理因素影響模型。Zhang 等人[5]從位置序列中挖掘順序模式，并將序列影響、社交影響和地理因素影響融合在統(tǒng)一的推薦框架中。Yali等人[6]在基于朋友協(xié)同過濾基礎上，綜合考慮社交關系和地理位置特征，提出個性化的興趣點推薦模型。Zhang 等人[7]對標簽、社交和地理因素分別進行建模，并將它們?nèi)诤系揭环N矩陣分解方法中。Zhang等人[8]利用BPR模型對矩陣分解進行優(yōu)化，并結合用戶社交關系和地理位置信息進行POI推薦。

除此之外，也有很多研究利用其他上下文信息進行POI推薦，如Gao等人[9]將一天劃分為多個時間段，分別構建不同時間段下的User-POI簽到矩陣，然后使用矩陣分解法獲取不同時間段的用戶偏好。Zhang等人[10]對用戶評論進行語義分析和情感計算，根據(jù)用戶的情感傾向預測用戶偏好。Wu等人[11]將POI流行度特征融入基于用戶協(xié)同過濾方法中，并結合社交關系和地理因素進行POI推薦。

盡管通過融合豐富的上下文信息可以有效緩解數(shù)據(jù)稀疏性問題，但現(xiàn)有融合上下文信息的POI推薦算法中仍存在以下一些問題：在研究社交關系影響時，用戶相似性影響因素選取往往比較單一，對于那些擁有較少簽到信息的用戶難以構建社交影響模型；在分析地理因素影響時，現(xiàn)有計算全局POIs 間地理相關性的方法不能充分剖析每個用戶的地理偏好。因此，本文提出融合社交關系和局部地理因素的POI推薦算法，可以有效地提高推薦的準確率和召回率。

2 興趣點推薦模型

POI 推薦的任務是給用戶推薦一個其感興趣但尚未訪問過的POIs列表。本章通過深入分析社交關系和地理因素對用戶簽到行為的影響，構建更加符合用戶偏好的POI推薦模型。

2.1 相關符號及定義

為方便后續(xù)討論，表1 給出了相關符號及其含義。同時，對簽到矩陣和簽到熱點進行了定義。

表1 相關符號描述Table 1 Relevant Symbols description

定義1（簽到矩陣）根據(jù)用戶歷史簽到記錄，構建簽到矩陣R||U×||I，矩陣中每個元素rui表示用戶u對POIi的簽到次數(shù)。

定義2（簽到熱點）用戶u簽到次數(shù)最高的POI。

2.2 社交關系影響模型的構建

在LBSN中，用戶的簽到行為在一定程度上受到其社交關系的影響，進而促使用戶訪問一些未去過的POIs。例如，在日常生活中去過一個體驗很好的餐廳或書店后，很可能會邀請或推薦自己的朋友前去，這些都可能使得用戶在相同的POI產(chǎn)生共同簽到，社交用戶間存在一定的行為相似性。因此，考慮用戶的社交關系對用戶簽到行為的影響有利于提高POI推薦質量。

對于用戶尚未訪問過的POIs，本文使用基于用戶的協(xié)同過濾方法[12]計算社交關系信息對用戶簽到行為的影響程度，其計算公式如下：

其中，cvi的定義如下：

其中，sui表示用戶u對POIi的偏好程度。Fu表示用戶u在社交網(wǎng)絡上的所有朋友集合，用戶v是用戶u的社交好友，cvi表示好友v對POIi的簽到情況，simuv表示用戶u和v的相似度。

對于式（1）中的用戶相似度simuv，不同的研究采用的方法不同[3-6]。大多數(shù)研究中，只考慮了基于共同簽到的用戶相似度，這對那些擁有較少簽到信息的用戶無法有效計算其社交偏好。因此，本文考慮在以往基于共同簽到的相似性研究基礎上，同時通過用戶間距離關系來度量用戶間的興趣差異，減小用戶相似度的計算誤差。

一方面，通常認為用戶間的共同簽到越多，他們的偏好就越相似。在基于行為相關性的相似性度量方法中，Jaccard 方法[13]在計算效率和推薦準確率上效果更好，基于Jaccard方法計算用戶簽到相似度公式如下：

其中，Ru和Rv分別表示用戶u和v簽到的POIs集合。

另一方面，考慮到相距較近的用戶擁有更多的共享興趣點，會產(chǎn)生較多的共同簽到。因此，對于距離越近的用戶，其簽到行為的相似度越高。本文通過改進Sigmod函數(shù)計算用戶距離相似度。

Sigmod函數(shù)是常見的S型函數(shù)，公式定義如下：

該函數(shù)連續(xù)、光滑、嚴格單調(diào)，關于點（0，0.5）中心對稱，在區(qū)間[-∞,+∞]上呈非線性增長?；谏鲜黾僭O中距離相似度隨著用戶間距離應呈遞減狀態(tài)，因此考慮改進Sigmod 函數(shù)來衡量基于用戶距離的相似度，改進后的用戶距離相似度計算公式如下：

其中，dis(u,v)表示用戶u與v間的距離，其根據(jù)用戶簽到熱點的經(jīng)緯度信息，利用Haversine方法[14]計算得出。計算公式如下：

其中，R為地球半徑，φ1和φ2分別表示用戶u和v簽到熱點的緯度，σ1和σ2分別表示用u和v簽到熱點的經(jīng)度。

綜合以上設計，本文對用戶簽到相似度和距離相似度行線性加權，得到用戶u和v的最終相似度，計算公式如下：

其中，α為調(diào)節(jié)用戶簽到相似度和距離相似度影響權重的參數(shù)。

將式（8）代入式（1）即可得到在社交關系影響下用戶對興趣點的社交偏好矩陣S。

2.3 局部地理因素影響模型的構建

在位置社交網(wǎng)絡中，地理位置信息是其特有的語境信息，是提升POI 推薦質量的重要因素。目前，考慮地理因素影響的模型主要是通過分析用戶所有簽到POIs的分布情況，通過POIs 間距離關系計算用戶對POIs 的簽到概率，如常用的高斯分布[3]及核密度估計[4]等。為了進一步研究地理因素的影響，這里發(fā)現(xiàn)用戶簽到呈現(xiàn)出空間聚類現(xiàn)象[15]，表明用戶喜歡訪問鄰近POIs，如用戶去某個城市旅行，往往會對相鄰區(qū)域集中的POIs 都進行訪問，鄰近POIs 間的簽到情況具有一定的關聯(lián)性[16]。因此，本文考慮為每個用戶劃分一個局部活動區(qū)域，充分剖析區(qū)域內(nèi)尚未訪問POIs間的簽到相關性，構建更加符合用戶偏好的局部地理因素影響模型。

步驟1劃分用戶活動區(qū)域

首先，找到用戶u的簽到熱點，然后為用戶u劃分一個距離簽到熱點半徑為β的局部活動區(qū)域。

步驟2尋找區(qū)域內(nèi)用戶尚未訪問的POIs

在步驟1所劃分用戶活動區(qū)域內(nèi)，尋找用戶u尚未訪問的POIs集合，分析與集合中POIi相距小于γ的鄰居POIs的簽到情況。

步驟3計算地理偏好程度

研究發(fā)現(xiàn)，用戶往往會對鄰近POIs進行集中訪問，針對鄰近POIs 的簽到影響已展開相關研究[16]。其中，Hossein等人[17]認為用戶對鄰近POIs的簽到數(shù)量會對用戶u簽到POIi產(chǎn)生一定影響，并構建出一個更加符合用戶偏好的地理偏好模型。因此，本文根據(jù)鄰居POIs的簽到情況，采用文獻[17]中的地理偏好定義，計算用戶u對POIi的簽到概率，公式如下：

其中，表示用戶u對POIi所有鄰居POIs 的簽到數(shù)量，Lu表示用戶u曾訪問過的所有POIs集合。

2.4 融合社交關系和局部地理因素的興趣點推薦模型

2.4.1 基礎模型

在LBSN 中，用戶社交關系、地理位置等上下文信息都會影響用戶的簽到行為，但最主要的是從用戶歷史簽到數(shù)據(jù)中反映出來的用戶自身偏好。在POI推薦中，矩陣分解技術[18]常用于挖掘用戶的自身偏好。但由于User-POI簽到矩陣中只能觀察到用戶訪問過的POIs，對于那些用戶尚未訪問過的POIs 會產(chǎn)生大量的缺失項，因此無法使用一般的矩陣分解技術來構建用戶自身偏好模型。Hu等人[19]首次在大規(guī)模隱式數(shù)據(jù)上提出加權矩陣分解（Weighted Matrix Factorization，WMF）模型，該模型通過對用戶已訪問的POIs 分配較大權重，對尚未訪問的POIs分配一個較小權重來解決User-POI簽到矩陣中存在的缺失項問題。

在POI 推薦中，WMF 方法將User-POI 簽到矩陣分解為兩個低維隱藏特征矩陣Pm×k和Qn×k，用戶對POI的自身偏好矩陣即為兩個隱藏特征矩陣的內(nèi)積。本文基于WMF 模型構建用戶自身偏好模型，其目標函數(shù)定義如下：

其中，pu和qi分別表示用戶u與POIi對應的隱特征向量，λ表示正則化系數(shù)。wui表示每個用戶簽到次數(shù)rui對應的權重，本文采用文獻[20]中權重設置方法，加權矩陣w的權重系數(shù)設置如下：

其中，ε是用來控制權重系數(shù)隨用戶訪問POI 次數(shù)增長的速率。

2.4.2 模型融合

在2.4.1節(jié)中，WMF模型根據(jù)用戶的簽到頻次信息提取用戶對POI的自身偏好，但沒有考慮社交關系和地理位置等影響因素。本文在WMF 模型上進行改進，將上述考慮的社交關系和局部地理信息融合到WMF 模型中，構建一個更加符合用戶偏好的POI 推薦模型SLGMF。該模型的目標函數(shù)如式（13）所示：

其中，eui表示用戶u對POIi的最終偏好，‖pu‖2和‖qi‖2分別表示用戶u和POIi的正則化項，加入目的是為了防止過擬合。

本文目標函數(shù)采用交替最小二乘法進行優(yōu)化，其主要思想是先依次固定矩陣P，優(yōu)化矩陣Q，然后再固定矩陣Q，優(yōu)化矩陣P，反復交替，不斷修正p和q分量，獲得最優(yōu)矩陣P和矩陣Q。

SLGMF模型的構建如算法2所示。

算法2SLGMF模型構建

3 實驗評估

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

實驗選取數(shù)據(jù)集Gowalla[21]，Gowalla收集了2009年2 月至10 月期間的所有簽到數(shù)據(jù)、用戶社交關系和POI信息。為使實驗數(shù)據(jù)更加有效，將數(shù)據(jù)集中用戶和POI簽到數(shù)量少于15條的低價值數(shù)據(jù)去除。處理后的標準數(shù)據(jù)集共有5 628個用戶，31 803個POIs和620 683條簽到記錄，以及46 001條社交關系。

3.2 評價指標

實驗選取常用的準確率(Precision)和召回率(Recall)作為評價指標來衡量推薦算法的性能，其定義分別如下：

其中，|U|表示用戶數(shù)量，Ru表示為用戶u推薦的POIs列表，Tu表示用戶u曾訪問過的POIs列表。

3.3 對比方法與參數(shù)設置

為了驗證所提SLGMF 算法的性能，實驗選取兩種均融合社交關系和地理因素的POI推薦算法：MGMPFM[3]和LORE[5]。另外，為了考察不同因素對POI 推薦的影響，本文將SLGMF 算法拆分為僅融合社交關系的推薦算法S-MF和僅融合局部地理因素的推薦算法LG-MF，并進行自身對比。

MGMPFM：利用多中心高斯模型建模地理因素影響，在概率矩陣分解基礎上融合社交和地理位置信息進行POI推薦。

LORE：從用戶簽到的位置序列中挖掘出序列模式，并融合社交和地理因素進行POI推薦。

S-MF：本文提出的模型，僅融合社交關系信息的推薦算法。

LG-MF：本文提出的模型，僅融合地理位置信息的推薦算法。

SLGMF：本文提出的模型，基于加權矩陣分解，綜合考慮社交關系和局部地理因素的推薦算法。

在參數(shù)設置上，所選用對比模型應盡量與原文獻保持一致，使各個算法性能達到最優(yōu)。對于本文提出的SLGMF 模型，分別設置隱藏特征矩陣維度K=25，用戶相似性影響因子α=0.6，地理因素影響因子β=30，γ=12，上述參數(shù)的取值使得推薦效果達到最優(yōu)。另外，地球半徑R取平均值為6 371。

3.4 實驗結果與分析

本文在相同數(shù)據(jù)集上對各個POI 推薦算法進行Top-N（N=5，10，15，20，25，30）推薦，圖1和圖2展示了Top-N推薦的準確率和召回率?？梢杂^察到準確率隨著N的增大而減小，召回率隨著N的增大而增大。這是由于返回的POIs 越多，越有可能發(fā)現(xiàn)更多用戶愿意訪問的POIs。

圖1 推薦的準確率Fig.1 Recommendation precision

圖2 推薦的召回率Fig.2 Recommendation recall

圖1和圖2可以看出，對比MGMPFM和LORE這兩種均融合社交關系和地理因素的POI推薦算法，無論N取何值，SLGMF算法在準確率和召回率上均有所提升，表明了本文所提出SLGMF算法的有效性。

另外，本文將SLGMF 模型拆分為僅融合社交信息的POI 推薦模型和僅融合地理位置信息的POI 推薦模型，通過實驗分析融合單一上下文信息的推薦效果，結果如圖1和圖2所示。當為用戶進行Top-5推薦時，在準確率上，SLGMF 算法相對S-MF 算法提升了14.6%，相對LG-MF 算法提升了11.2%。在召回率上，SLGMF 算法相對于S-MF 算法提升了24.3%，相對于LG-MF 算法提升了22.8%。這說明本文在加權矩陣分解基礎上融合多種上下文信息，確實可以有效地緩解數(shù)據(jù)稀疏性問題，提高推薦性能，并且融入有效的上下文信息越多，推薦效果越好。除此之外，對比S-MF和LG-MF算法可以發(fā)現(xiàn)，僅融合地理因素的LG-MF 推薦性能要優(yōu)于僅融合社交因素的S-MF，這表明地理因素對用戶簽到行為的影響要高于社交因素。

3.5 模型參數(shù)的影響

在2.4.1節(jié)中構建用戶自身偏好模型時，通過WMF將用戶簽到矩陣分解為兩個維度為K的隱藏特征矩陣P和Q，參數(shù)K的值決定用戶對POI 的自身偏好程度。本節(jié)選取不同的K值，對用戶進行Top-5 推薦，推薦結果如圖3所示?？梢钥闯?，當維度K=25 時，SLGMF推薦性能最好，且隨著K的不斷增加，推薦效果開始呈下降狀態(tài)，這是由于模型已經(jīng)出現(xiàn)過擬合的原因。

圖3 參數(shù)K 對準確率和召回率的影響Fig.3 Effect of parameters k on precision and recall

在式（8）中計算用戶最終相似度時，參數(shù)α決定著距離相似度和簽到相似度的影響程度。為了探究用戶間距離和共同簽到對用戶簽到行為的影響，實驗選取不同的α值對用戶u進行Top-5 推薦，結果如圖4 所示?？梢钥闯?，當α=0.6 時，推薦效果最佳，同時也表明用戶簽到行為相似度受用戶間距離的影響更大。

圖4 參數(shù)α 對準確率和召回率的影響Fig.4 Effect of parameter α on precision and recall

在2.3 節(jié)構建局部地理因素影響模型時，為每個用戶劃分一個局部活動區(qū)域，參數(shù)β是用來控制用戶活動范圍，參數(shù)γ用來判別區(qū)域內(nèi)尚未訪問POIi的鄰居POIs。因此，為探究用戶局部簽到規(guī)律，實驗選取不同的β和γ進行Top-5推薦，分析局部地理因素對用戶簽到行為的影響，推薦結果分別如圖5 和圖6 所示。可以看出，當β=30，γ=12 時，推薦效果達到最佳，也可以看出用戶比較傾向訪問離自己較近的POIs。

圖5 參數(shù)β 對準確率和召回率的影響Fig.5 Effect of parameters β on precision and recall

圖6 參數(shù)γ 對準確率和召回率的影響Fig.6 Effect of parameters γ on precision and recall

4 結束語

為了解決POI推薦中存在的數(shù)據(jù)稀疏性問題，本文提出一種融合社交關系和局部地理因素的POI 推薦模型SLGMF。首先，根據(jù)社交關系中用戶間的共同簽到和距離關系提出一種用戶相似性度量方法，并基于用戶的協(xié)同過濾得出社交關系對用戶簽到行為的影響程度；然后，為每個用戶劃分一個局部活動區(qū)域，充分剖析區(qū)域內(nèi)尚未訪問POIs 間的簽到相關性，計算局部地理因素對用戶簽到行為的影響程度；最后，基于加權矩陣分解構建用戶自身偏好模型，并結合上述考慮的社交關系和局部地理因素，構建更加符合用戶偏好的POI推薦模型，有效地緩解數(shù)據(jù)稀疏性問題；在Gowalla數(shù)據(jù)集上進行實驗，結果表明所提的SLGMF 算法具有良好的推薦性能。

現(xiàn)實生活中，影響用戶簽到行為的因素除了本文所考慮的社交關系和地理因素外，還有諸如時間、評論文本、圖像等豐富的上下文信息。在未來的研究工作中，將重點考慮如何利用更多的上下文信息來提高POI 推薦性能。