王 崢 張 成

（1.南京烽火星空通信發(fā)展有限公司 南京 210019）（2.武漢郵電科學(xué)研究院 武漢 430074）（3.南京烽火天地通信科技有限公司 南京 211161）

1 引言

近幾年，隨著智能手機(jī)的普及，基于位置的社交網(wǎng)絡(luò)LBSN（Location-Based Social Network）發(fā)展十分迅速，國外的Foursquare、Gowalla，國內(nèi)的微信、微博等社交網(wǎng)絡(luò)平臺(tái)，注冊用戶量已超千萬，微信注冊用戶量更是多達(dá)9.27億。LBSN使用戶可以用一種簽到的方式發(fā)布與當(dāng)前位置相關(guān)的信息（如評(píng)論、照片），與其他用戶分享自己的觀點(diǎn)。通過分析LBSN的用戶簽到數(shù)據(jù)，可以得到用戶的興趣傾向，從而衍生出一系列的社交網(wǎng)絡(luò)推薦服務(wù)，比較典型的應(yīng)用有好友推薦、興趣點(diǎn)推薦和活動(dòng)推薦，本文主要針對興趣點(diǎn)推薦進(jìn)行算法研究。目前常用的興趣點(diǎn)推薦算法可分為三類，分別是基于協(xié)同過濾的推薦算法［1］、基于矩陣特征化的方法［2］以及基于隨機(jī)游走的方法［3］。其中應(yīng)用最廣泛的是協(xié)同過濾算法，協(xié)同過濾推薦算法主要有基于用戶的User-CF算法［4］和基于項(xiàng)目的Item-CF算法［5］，這些方法在興趣點(diǎn)推薦中主要根據(jù)用戶已有的簽到行為數(shù)據(jù)來預(yù)測和推薦，但這些算法在引入社交網(wǎng)絡(luò)關(guān)系數(shù)據(jù)時(shí)運(yùn)用不夠充分。本文提出一種基于用戶興趣相似度和熟悉度的興趣點(diǎn)推薦算法，向用戶推薦一組用戶感興趣的地點(diǎn)（即興趣點(diǎn)POI）。該方法主要特點(diǎn)如下：

1）該方法在一定程度上克服了用戶簽到矩陣的稀疏性對用戶相似度計(jì)算的影響。采用非負(fù)矩陣分解將用戶簽到矩陣分解成用戶特征矩陣和地點(diǎn)特征矩陣，利用用戶特征矩陣來計(jì)算用戶之間的興趣相似性，使得最后的推薦結(jié)果更加精確。

2）引入六度分隔理論［6］和三度影響力規(guī)則［7］，完善用戶之間熟悉度的計(jì)算，提高推薦結(jié)果的精確度。

2 相關(guān)工作

最初，Ye等［8］將興趣點(diǎn)推薦引入到LBSN中，他們認(rèn)為朋友關(guān)系會(huì)對用戶的地點(diǎn)選擇有很大的影響，因此，提出了一種基于好友社交關(guān)系的協(xié)同過濾方法；隨后，Ye等［9］又分析了地理位置對用戶地點(diǎn)訪問行為的影響，他們假設(shè)用戶更喜歡訪問距離近的地點(diǎn)，從而建立冪分布模型來模擬地理距離與訪問可能性大小的關(guān)系；除了冪分布外，Cho等［10］和Cheng等［11］通過多中心髙斯分布來模擬地理位置的影響。Zhang［12］等利用核密度估計(jì)模型，將每個(gè)用戶的地理影響力建模為個(gè)性化的距離分布。

Shi Yue等［13］根據(jù)用戶歷史位置數(shù)據(jù)建立一個(gè)類別-正則矩陣，再基于這個(gè)矩陣進(jìn)行興趣點(diǎn)推薦；孫光福等［14］提出一種基于時(shí)序消費(fèi)行為的最近鄰建模方法，通過用戶（產(chǎn)品）的相互影響關(guān)系，產(chǎn)生更為精準(zhǔn)的推薦結(jié)果。還有一些學(xué)者在傳統(tǒng)的推薦方法基礎(chǔ)上進(jìn)行改進(jìn)并應(yīng)用于興趣點(diǎn)推薦中，如Berjani等［15］采用正則化奇異值分解（Singular Value Decomposition，SVD）模型對地點(diǎn)進(jìn)行評(píng)分預(yù)測；Leung等［16］將用戶、地點(diǎn)進(jìn)行劃分聚類，得到相似用戶類在相似地點(diǎn)類上的新的簽到矩陣，然后通過傳統(tǒng)的協(xié)同過濾方法進(jìn)行興趣點(diǎn)推薦。

以上的研究取得了一定的成果，但是還存在著不足之處。傳統(tǒng)的協(xié)同過濾算法關(guān)鍵是用戶相似性的計(jì)算，但用戶簽到矩陣往往是高稀疏性，導(dǎo)致推薦結(jié)果不理想：在引入社交網(wǎng)絡(luò)關(guān)系時(shí)上述方法都只考慮到用戶間距離為二的熟悉度，這與現(xiàn)實(shí)生活情況不符。根據(jù)六度分隔理論［6］，一個(gè)人與任何一個(gè)陌生人的距離不會(huì)超過六個(gè)人（距離為六），在此基礎(chǔ)上，Nicholasa A Christakis研究發(fā)現(xiàn)，相距三度之內(nèi)是強(qiáng)連接，強(qiáng)連接可以引發(fā)行為［7］，即兩個(gè)用戶之間不存在共同好友時(shí)，但兩個(gè)用戶間的距離為三時(shí)，仍然存在著一定的熟悉度。本文提出一種基于用戶興趣相似度和熟悉度的興趣點(diǎn)推薦算法，采用非負(fù)矩陣分解的方法計(jì)算用戶興趣相似度，根據(jù)三度影響力規(guī)則將用戶間距為三的熟悉度融入用戶熟悉度計(jì)算中，以改善用戶間的信任質(zhì)量，提高興趣點(diǎn)推薦精度。

3 興趣點(diǎn)推薦算法

用戶在接受他人推薦的一個(gè)陌生地點(diǎn)時(shí)，兩人之間的熟悉度和興趣相似性是最主要的考慮因數(shù)。本文通過分析用戶的好友關(guān)系數(shù)據(jù)來評(píng)估用戶之間的熟悉度，并根據(jù)用戶的簽到數(shù)據(jù)來評(píng)估用戶之間的興趣相似度，結(jié)合熟悉度和興趣相似度得到信任度，最終根據(jù)Top-N推薦得到推薦列表。推薦模型如圖1所示。

圖1 基于用戶興趣相似度和熟悉度的興趣點(diǎn)推薦模型

3.1 用戶熟悉度計(jì)算

為用戶進(jìn)行興趣點(diǎn)推薦時(shí)，用戶之間的熟悉度是一個(gè)很重要的參考因素，且兩人之間的熟悉度越高，推薦的地點(diǎn)越有可能被采納。在基于社會(huì)關(guān)系的推薦算法中，“朋友的朋友也有可能是我的朋友”是一條大眾普遍接受的假設(shè)。本文用戶之間的熟悉度也基于共同好友數(shù)來確定。但熟悉度不能單純地通過統(tǒng)計(jì)兩用戶間的共同好友數(shù)得到，因?yàn)槭煜ざ缺旧硎欠菍ΨQ的。如某用戶的交際范圍越廣，或在LBSN中越活躍，該用戶越有可能與其他用戶擁有很多共同好友。但一個(gè)人的精力是有限的，僅從熟悉度角度看，他們之間的熟悉度屬性并不高。綜上所述，本文采用的熟悉度計(jì)算公式如下：

式（1）中，F(xiàn)am（u，v）表示用戶u和用戶v的熟悉度，|Fu∩Fv|表示用戶u和v之間的共同好友數(shù)，| Fu|表示用戶u的好友數(shù)。該公式表明，用戶u和v之間的熟悉度與他們之間的共同好友數(shù)成正比，與用戶u的好友數(shù)成反比。即活躍度越高的用戶，在共同好友數(shù)相同的情況下，與其他用戶的熟悉度越低。

以上情況是兩用戶間存在共同好友時(shí)熟悉度的計(jì)算方法，但兩用戶間不存在共同好友時(shí)，根據(jù)文獻(xiàn)［15］提出的三度影響力規(guī)則，即兩用戶不存在共同好友時(shí)，但兩用戶之間的距離為三時(shí)，仍然存在著一定的熟悉度。本文兩用戶間不存在共同好友（距離為三）時(shí)熟悉度計(jì)算公式如下：

式（2）中，F(xiàn)am（u，v）表示用戶u和用戶v之間的熟悉度，a為不為用戶u和用戶v的任一其他用戶。

3.2 用戶興趣相似度計(jì)算

經(jīng)典協(xié)同過濾算法的關(guān)鍵問題是相似性的計(jì)算，其中用戶相似性準(zhǔn)確來說是用戶興趣相似性。在度量興趣相似性時(shí)會(huì)用到用戶對項(xiàng)目的評(píng)分矩陣，常用的方法有余弦相似性、相關(guān)相似性等計(jì)算方法。本文采用余弦相似性，其計(jì)算公式為

式（3）中，sim（u，v）表示用戶u和用戶v的相似性，和v→分別表示用戶u和用戶v的評(píng)分向量，n為評(píng)分矩陣中的項(xiàng)目數(shù)，Rui和Rvi分別表示用戶u和用戶v對項(xiàng)目i的評(píng)分。

但因?yàn)橛脩粼u(píng)分矩陣的稀疏性，直接利用余弦相似性計(jì)算用戶間的興趣相似性效果不佳。本文采用非負(fù)矩陣分解（NMF）的方法，將用戶地點(diǎn)簽到矩陣 Rm×n分解成兩個(gè)非負(fù)矩陣Wm×k和 Hk×n的乘積，其中k為特征數(shù)，Wm×k為用戶特征矩陣，Hk×n為地點(diǎn)特征矩陣，使得 Rm×n=Wm×k?Hk×n。NMF求解過程中，假設(shè)噪聲矩陣為E∈Rm×n且服從高斯分布，則E=R-WH，求解過程就是找到合適的W和H使得‖‖E最小。因?yàn)樵肼暦母咚狗植迹敲吹玫阶畲笏迫缓瘮?shù)為

假設(shè)各數(shù)據(jù)點(diǎn)噪聲的方差一樣，使對數(shù)似然函數(shù)取最大值時(shí)，以下目標(biāo)函數(shù)取最小值。

3.3 用戶推薦信任度計(jì)算

將用戶熟悉度和用戶興趣相似度統(tǒng)一起來，得到用戶推薦信任度，其計(jì)算公式為

3.4 個(gè)性化興趣點(diǎn)推薦

根據(jù)協(xié)同過濾的思想，基于統(tǒng)一后的用戶推薦信任度搜索目標(biāo)用戶u的鄰近用戶集合Ts（取前S個(gè)，S即為鄰近用戶長度），取集合Ts中用戶簽到地點(diǎn)集合，去除目標(biāo)用戶u已簽到的地點(diǎn)后作為待推薦地點(diǎn)集合L，然后根據(jù)鄰近用戶的簽到信息來預(yù)測目標(biāo)用戶對為簽到地點(diǎn)的偏好程度，計(jì)算公式如下：

式（14）中Int（u，i）為目標(biāo)用戶u對地點(diǎn)i的偏好程度，S為鄰近用戶長度，Tuv為用戶v對目標(biāo)用戶u的推薦信任度，Cvi為用戶v在地點(diǎn)i的簽到次數(shù)。根據(jù)Int（u，i）的值進(jìn)行排序，輸出前Top-N個(gè)地點(diǎn)作為推薦地點(diǎn)。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本實(shí)驗(yàn)使用Gowalla數(shù)據(jù)集。Gowalla數(shù)據(jù)集由 斯 坦 福 大 學(xué) （http：∕snap.stanford.edu∕data∕loc-gowalla.html）提供。該數(shù)據(jù)集主要包括用戶的簽到日志記錄和用戶的好友關(guān)系，其中簽到數(shù)據(jù)6442890條，朋友關(guān)系數(shù)據(jù)中節(jié)點(diǎn)（用戶）有196591個(gè)，邊（好友關(guān)系）950327條。我們抽取了904個(gè)用戶關(guān)于8120個(gè)地點(diǎn)的51578條簽到數(shù)據(jù)，稀疏性為99.30%。對每個(gè)用戶，隨機(jī)選取80%的簽到數(shù)據(jù)作為訓(xùn)練集，其他的20%的簽到數(shù)據(jù)作為測試集。表1～2分別是Gowalla數(shù)據(jù)集簽到數(shù)據(jù)、好友關(guān)系數(shù)據(jù)樣本。

表1 Gowalla數(shù)據(jù)集簽到數(shù)據(jù)示例

表2 Gowalla數(shù)據(jù)集好友關(guān)系數(shù)據(jù)示例

4.2 評(píng)測方法

本實(shí)驗(yàn)選擇查全率（Recall）、查準(zhǔn)率（Precision）和F1-Measure作為評(píng)價(jià)實(shí)驗(yàn)結(jié)果的評(píng)價(jià)指標(biāo)，其中F1-Measure為調(diào)和均值，是根據(jù)查全率和查準(zhǔn)率得到的一個(gè)綜合指標(biāo)。計(jì)算公式如下：

其中，R（u）為根據(jù)訓(xùn)練集推薦給用戶u的地點(diǎn)列表，T（u）為測試集中用戶u簽到過的地點(diǎn)列表。

4.3 實(shí)驗(yàn)結(jié)果與分析

本文將實(shí)驗(yàn)結(jié)果與文獻(xiàn)［2］中的矩陣特征化MC算法和文獻(xiàn)［14］中的奇異值分解SVD算法進(jìn)行比較。本文提出的基于用戶興趣相似度和熟悉度的算法在后面的圖表中用MF表示。我們首先考慮參數(shù)α對MF算法推薦結(jié)果的影響，將推薦列表長度固定為10，鄰近用戶數(shù)量固定為10，α在［0，1］區(qū)間內(nèi)取值，以0.1的間隔進(jìn)行遞增，圖2是參數(shù)a取不同值時(shí)對應(yīng)的F1-Measure。可以看到，隨著α的增大，F(xiàn)1-Measure的值先逐漸增大，當(dāng)a為0.4時(shí)，F(xiàn)1-Measure值達(dá)到最大，說明此時(shí)綜合推薦效果最佳；當(dāng)α繼續(xù)增大時(shí)，F(xiàn)1-Measure值逐漸減小。

圖2 參數(shù)α對推薦效果的影響

圖3 是取不同的鄰近用戶數(shù)量S時(shí)對應(yīng)MF算法的F1-Measure值，實(shí)驗(yàn)中固定a值為0.4，推薦列表長度N為10，鄰近用戶長度S在2～16之間取值。從圖中可以看出，隨著S值得增大，F(xiàn)1-Measure的值逐漸增大，在S取值為10時(shí)達(dá)到最大值，說明此時(shí)的綜合推薦效果最佳，隨后F1-Measure經(jīng)歷一個(gè)短暫的下降后繼續(xù)緩慢增長并趨于平穩(wěn)。

圖3 鄰近用戶數(shù)量對推薦結(jié)果的影響

圖4 Precision指標(biāo)結(jié)果對比

圖4 ～6是取不同推薦列表長度N時(shí)，各個(gè)算法的Precision指標(biāo)、Recall指標(biāo)和F1-Measure指標(biāo)的對比圖，實(shí)驗(yàn)中固定a值為0.4，鄰近用戶的長度為10。結(jié)果對比顯示，當(dāng)推薦列表長度N取值較小時(shí)，查準(zhǔn)率較高而查全率較低；隨著N值地增大，查準(zhǔn)率逐漸下降而查全率逐漸上升；在取不同N值時(shí)，MF的各項(xiàng)指標(biāo)都優(yōu)于MC算法和SVD算法，說明相較于傳統(tǒng)的MC算法和SVD算法，本文提出的算法鄰近搜索的效果更佳。主要原因是傳統(tǒng)的MC和SVD算法都只是利用了用戶的簽到信息，未能充分利用社交網(wǎng)絡(luò)關(guān)系數(shù)據(jù)，所以推薦效果較差；而本文首先利用非負(fù)矩陣分解得到用戶-特征矩陣，再利用用戶-特征矩陣計(jì)算用戶之間的興趣相似性，融入用戶之間的熟悉度后再進(jìn)行推薦，這樣算法的魯棒性較好。

圖5 Recall指標(biāo)結(jié)果對比

圖6 F1-Measure指標(biāo)結(jié)果對比

5 結(jié)語

本文提出了一種基于用戶興趣相似度和熟悉度的地點(diǎn)推薦算法。該方法首先根據(jù)用戶社交網(wǎng)絡(luò)關(guān)系計(jì)算用戶之間的熟悉度；然后采用非負(fù)矩陣分解的方法將用戶地點(diǎn)簽到矩陣分解成用戶特征矩陣和地點(diǎn)特征矩陣，再根據(jù)用戶特征矩陣計(jì)算用戶之間的興趣相似度；最終將用戶間熟悉度和興趣相似度融合成用戶間推薦信任度，利用融合后的推薦信任度搜索鄰近用戶，根據(jù)鄰近用戶的簽到信息來計(jì)算目標(biāo)用戶對未簽到地點(diǎn)的偏好，并選擇前Top-N個(gè)地點(diǎn)推薦給目標(biāo)用戶。經(jīng)過實(shí)驗(yàn)對比分析表明，本文提出的方法能夠獲得更加理想的推薦效果。

在以后的工作中，我們將融合多源信息進(jìn)行深層次的推薦，并考慮推薦地點(diǎn)與目標(biāo)用戶之間的距離，如推薦地點(diǎn)與目標(biāo)用戶活躍區(qū)域中心的距離，來調(diào)整地點(diǎn)推薦列表中的排序，進(jìn)一步提高推薦效果。