LBSN上基于興趣圈中社會關系挖掘的推薦算法

李 鑫 劉貴全 李 琳 吳宗大 丁君美

1(中國科學技術大學計算機科學與技術學院 合肥 230022)2(科大訊飛股份有限公司大數據研究院 合肥 230088)3(武漢理工大學計算機科學與技術學院 武漢 430070)4 (溫州大學甌江學院計算機科學與技術學院 浙江溫州 325035) (xinli2@iflytek.com)

LBSN上基于興趣圈中社會關系挖掘的推薦算法

李 鑫1,2劉貴全1李 琳3吳宗大4丁君美1

1(中國科學技術大學計算機科學與技術學院 合肥 230022)2(科大訊飛股份有限公司大數據研究院 合肥 230088)3(武漢理工大學計算機科學與技術學院 武漢 430070)4(溫州大學甌江學院計算機科學與技術學院 浙江溫州 325035) (xinli2@iflytek.com)

隨著帶有GPS定位功能的智能手機越來越普遍，人們喜歡分享他們的地理位置或者通過評論某個地方的商品從而留下用戶的足跡，這引發了以共同的興趣點(POIs)為中心，基于地理位置信息的社交網絡研究(location based social network, LBSN).社交網絡中的一類典型應用是推薦系統，而推薦系統中最常見的問題是冷啟動，即在用戶很少點評商家或分享評論時如何為他推薦感興趣的商家.為解決冷啟動問題，提出了一種在社交網絡中基于興趣圈的社會關系挖掘推薦算法.興趣圈是由所有訪問某一類別商品的用戶群及他們之間的社會關系構成的社交聯系，不同的用戶訪問同一類別商品表明他們對此類別具有相似興趣.該方法在傳統矩陣分解模型的基礎上考慮不同的興趣圈上的社會關系，使用的社會關系包括朋友關系(顯性關系)和相關專家(隱性關系)，并用它們作為規則化項來優化矩陣分解模型.實驗數據集來自第5屆Yelp挑戰賽和自己爬取的Foursquare數據集，提出的方法與已有模型進行了充分的實驗對比分析，結果表明，我們的模型特別是在解決冷啟動問題方面優于多種現有的方法.

興趣點；推薦；興趣圈；社會關系；冷啟動

近年來興起了基于地理位置信息服務的熱潮，如Foursquare和Yelp挑戰賽.用戶在這種在線服務上可以通過評論或者給商家評分分享他們的經驗.同時，他們可以加好友或者成為別人的粉絲，從而形成了社交網絡.上面的2個特性是基于位置的社交網絡(location based social network， LBSN)的基礎.推薦算法可以幫助用戶在LBSN中找到自己感興趣的商家，成為學術界和工業界關注和研究的熱點問題.

眾所周知，影響推薦系統性能的2個主要問題是用戶冷啟動和數據稀疏，而冷啟動問題研究的是在用戶很少點評商家或分享評論時如何為他推薦感興趣的商家.解決這類問題的可行性方案之一是將社會關系融入到推薦模型中.一個用戶的品味跟與他有社會關系的人比較相似或受他們影響，這被稱為社會學中的同質性.本文使用的社會關系包括朋友和專家關系.盡管現有的推薦系統在不斷改進，但在LBSN上對社會關系的挖掘還存在很大的空間可以提升推薦系統的性能.其一，當位置信息嵌入到社交網絡中形成新的LBSN時，社會聯系將會擴大.除了現有的2個用戶之間的關系外，另一個聯系則是用戶的位置信息.如2個用戶訪問了同一個商品時，說明他們共處于同一地理位置，那么他們很可能會被聯系起來[1].其二，除了受自身朋友影響外，用戶也可能會受到訪問過同類商品的專家的評分和評論影響.這是因為在某個商品的網頁上，專家的評論在這類商品中總是排名很高，從而影響后面的用戶.最后，傳統利用社會關系的方法解決冷啟動問題的假設是：雖然用戶訪問的商品比較少，但是他有足夠的社會關系，我們可以通過學習他的朋友或者這方面專家的意見來給他們推薦.但當用戶訪問商品很少時，他很可能也沒有豐富的社會關系.

本文針對上述冷啟動和稀疏問題，提出一種基于相同興趣圈的推薦系統，使用社交網絡為輔助信息來提高POI模型準確率.興趣圈是由所有訪問某一類別商品的用戶群及他們之間的社會關系構成的社交聯系，不同的用戶訪問同一類別商品表明他們對此類別具有相似興趣.模型同時采用了朋友和專家2種社會關系作為矩陣分解的2個正則化約束項.對一個具體用戶而言，朋友或者專家的正則化項對他的影響可能有所不同，所以對它們的處理也完全不同.尤其對于解決冷啟動情況，用戶評分數比較少很可能朋友數也不多，所以同一類商品下的專家用戶可能對推薦有很大幫助.這些朋友和專家都根據歷史評分記錄以及評論被劃分成不同的興趣圈后，他們對系統推薦都發揮著重要的作用.我們根據LBSN信息提出基于興趣圈中社會關系挖掘的POI推薦算法(circle-based and social connection embedded recommendation in LBSN, CSCR).CSCR算法使用朋友和專家2種社會關系作為規則化項來優化目標函數的學習.在真實數據集上的實驗結果表明我們的方法優于多種基于矩陣分解的經典方法.綜上所述，本文的貢獻如下：

1) 提出了一種基于不同興趣圈的推薦算法，同時利用LBSN上顯性和隱性的社會關系來提高推薦系統的性能，尤其對于解決冷啟動問題效果顯著.

2) 設計了基于朋友關系和基于專家用戶的2個正則化項，用它們作為矩陣分解目標函數的約束條件，并考慮到它們對不同的用戶的差異性影響.

3) 證明了2個等價定理.①無論2個用戶的相似性是以獨立方式還是平均值結合到正規化項中的，它們本質都是一樣的;②目標函數中所有正則化項可以被視為是不同高斯分布的組合.

4) 在Yelp和Foursquare數據集上進行了充分的實驗，結果表明CSCR算法優于現有的基于社會信息的推薦算法.

1 相關工作

在LBSN上對有相同興趣點的推薦，可以將POIs看做普通的項用通常的方法來解決.基本的低秩矩陣分解技術由Salakhutdinov等人[2]用概率給出以及被Koren[3]巧妙地應用并贏得了Netflix獎.低秩矩陣分解的前提是有一些潛在的因素分別控制用戶和商品的屬性.預測的評分由R=UVT給出，U和V分別是用戶-特征矩陣和商品-特征矩陣.模型訓練是通過最小化含有Frobenius范數規則化項的目標函數的誤差平方和.

Fig. 1 Description of interest circle圖1 在POIs不同類別下的基于興趣圈的模型描述

現在社交網絡信息較易獲得，許多模型通過結合社會關系提高推薦系統準確率，如SocialMF[4],SoReg (social regularization)[5],hTrust (homophily trust)[6],ASS (adaptive social similarity)[7].這些模型假設用戶的特征向量與他相似的鄰居的特征向量相近，即使用戶只訪問很少的商品也可以向鄰居學習.同時也有研究者將信任傳播機制結合到模型中[4,8]，或通過設計規則化項[5-6]以及通過調查不同的用戶相似度度量方法和同質性系數從本質上區分目標函數.然而這些方法中2個用戶的相似性度量計算是通過他們訪問的共同商品集得到的，并不是所用的文章都采用這種方法，如Yu等人[7]則沒有使用用戶潛在的特征向量來度量用戶間的相似程度.關于人際關系的影響和社會關系的研究[9-10]以及結合協同過濾的推薦算法的研究[11-12]也非常普遍.

然而，以上方法忽略了用戶社交關系的多類別性.Yang等人[13]提出了基于興趣圈的推薦方法，他們通過推斷特定類別的社交圈和設計這個興趣圈中不同朋友的不同權重，大量實驗驗證了這一方法優于SocialMF模型.在此基礎上Zhao等人[14]也基于興趣圈研究了人際關系和人與人之間興趣的相似度對模型的影響.本文的特色是在每個興趣圈內不僅利用了明確的社會關系(朋友),而且考慮了隱含的社會關系(專家)來解決冷啟動問題.Tang等人[15]利用了局部和全局的社會關系，同時考慮自己的朋友和所有用戶中具有較高聲譽的用戶，這篇文章的工作和我們的觀點比較相近，但其整個網絡中有影響力用戶的影響是通過在目標函數中設置權重明確對模型的影響，然后設計一個正則化項集成到模型中來.而本文是通過對目標函數的優化學習得到這些權重.

2 問題定義

本文研究的問題是以社交網絡信息為基礎的POI推薦.令U={u1,u2,…,uM}，V={v1,v2,…,vN}分別是用戶的集合和POIs的集合，其中M和N分別指用戶數和POIs數.用戶之間的關系可以用一個矩陣F∈M×M表示，當用戶ui是用戶uj的朋友時，矩陣元素fij值為1，否則為0.所以F是一個對稱矩陣，這也使得社交網絡中用戶間的連接是一個無向圖(如Facebook).每1個POI屬于1個類別c，例如飯店或者酒店.根據每個用戶的評級記錄，社交網絡可以被劃分成不同的興趣圈，而在每個興趣圈中用戶之間的社會連接是整個社交網絡的子圖，如圖1所示.具體定義如下：

有一些用戶會被網站選中并標記成“專家”，例如圖1(a)中的用戶u3，其表示u3在某個領域或興趣圈里經驗很高.而所有的專家用戶組成的集合我們定義為E.

我們目標是通過用戶關系F、專家集合E和POI類別c作為輔助信息，預測每一組(u,v)的評分.尤其當用戶的評分很少時即冷啟動情況，仍能給出令人滿意的推薦結果.

3 模 型

本文在LBSN上基于興趣圈中社會關系挖掘的POI推薦是在傳統矩陣分解模型基礎上引入朋友和專家關系作為規則化項來優化矩陣分解模型.新模型也可以視為CircleCon[13]增加了專家正則化項的延伸，這也是為了更好地解決冷啟動問題.

3.1 基本矩陣分解模型

基本的矩陣分解技術是將整個用戶評分矩陣R分解成2個矩陣U∈M×D和V∈N×D.通過對矩陣迭代學習，最大限度地減少有正則化項的平方誤差損失函數，直到收斂.其中U和V分別是用戶-特征矩陣和POI-特征矩陣，特征維數D?M,N.因為本文采用了興趣圈的概念，所以用戶評分矩陣R根據類別c被劃分成更小的塊，即Rc，而目標函數根據每個類別修改后為：

(1)

其中,?是Hadamard乘積;Uc，Vc分別是類別c下的用戶-特征矩陣和POI-特征矩陣;J是與矩陣Rc大小相同的指示矩陣，如果用戶對POI給出了評分，則J矩陣相應位置的值為1，否則為0.

3.2 基于朋友關系的正則化項

LBSN在模型中使用的前提是用戶與他的朋友有著相同的興趣而且他容易受朋友的影響，這分別被稱為同質性[16]和社會影響力[17].對于冷啟動情況，當用戶評分數很少但朋友較多，那么相同興趣圈內有相同愛好的朋友與他對某個商品的喜好程度可能比較相近，所以利用朋友關系設計正則化項具有一定的合理性.

(2)

通過歸一化矩陣Sc中每一行記錄得到新的矩陣S*，類別c下的朋友關系規則化項為：

(3)

3.3 基于專家的正則化項

相對于朋友關系，專家關系則是一種隱性的社會關系.專家關系是指人們有時也會受到一個領袖人物(專家)的影響，容易接受他們的觀點并對用戶自身行為產生影響.如果假設用戶的興趣應該與他們興趣圈中專家用戶的較為接近，那么我們就可以加入專家的影響.而且，當用戶的朋友數少時專家關系的參考性將更大.所以為了更好地解決冷啟動問題，我們在朋友關系的基礎上又提出了基于專家關系的規則化項.

在傳統的社交網絡分析中，往往通過影響力傳播的方法研究專家的影響，這種方法并不要求用戶之間有直接關系.然而LBSN可以提供額外的地理范圍信息，為我們研究專家的影響提供了新的方法.我們知道用戶在LBSN上的信息是以位置為中心的，同時專家的評論和評分在每個商家的頁面上等級很高，從而反過來影響普通用戶.因此來自專家的影響有2個前提：1)專家用戶影響普通用戶需要他們訪問了同一商品；2)一個專家不會受到其他專家的影響.基于上述前提，我們用矩陣Ec設計了2種定義專家對普通用戶的影響，定義如下：

(4)

因為有時候嚴格標記好的專家用戶這個信息是無法獲得的，所以我們又提出了一種方法來估計用戶的專業度.這個想法是專家用戶應該有更多的朋友，可以吸引更多的關注.我們使用每個用戶對他朋友的平均吸引力來定義他的專業.這種情況下的用戶影響力定義如下：

(5)

(6)

3.4 有2個規則化項的基于興趣圈的模型

目前為止，我們通過式(1)(3)(6)可以得到最終的模型如下：

(7)

其中α和β分別是2個正則化項的參數.

式(7)將朋友和專家的影響融合到了模型中，但這并不意味著它們兩者是同時有效的.如圖1(b)中，u3是標記的專家用戶，與u4和u5分別有聯系.對u4來說，只用專家的規則化項對他有影響，因為他與u3用戶訪問了同一個地方但是與他又沒有直接的聯系.而對u5而言，不管是專家的規則化項還是朋友的規則化項都對他有影響.

3.5 分析推斷

由于模型已經被分解成不同的興趣圈，所以每個類別下的訓練過程是獨立的.一般來說可以采用批處理梯度下降來最小化目標函數知道收斂.學習過程如下：

(8)

(9)

其中I為單位矩陣.一旦學習好每個類別c中的Uc和Vc之后，就可以預測這個類別下用戶-商品對(ui,vj)的評分.模型同時考慮了2種正則化項，即使對冷啟動用戶也可以給出有效的評分.具體如算法1所示.

算法1. 基于興趣圈中社會關系的推薦模型.

輸入：Rc,S*c,E*c；

輸出：Uc,Vc.

① 隨機輸入Uc,Vc；

② 循環從step=1到MAXSTEP：

⑥ 循環結束；

3.6 算法復雜度分析

3.7 等價定理

現在已經有很多模型假設用戶的興趣可能與他的鄰居比較接近，并結合了社交網絡信息設計不同的規則化項[4-6,13].實際上，無論2個用戶的相似性是獨立結合到正規化項中的還是以平均值結合到正規化項中的，它們的本質都是一樣的.

證明. 像文獻[6]中式(7)提到的一樣，L=D-S是一個拉普拉斯矩陣，其中，

我們需要做的就是以平均為基礎的正則化項與獨立的有相同的表示形式.

證畢.

定理2. 第二等價定理.目標函數中的所有正則化項可以被視為是由各種估計用戶興趣標準差的高斯分布的組合.

在i.i.d.(independent and identically distributed)假設下，這3個分布的線性組合是：

因此在我們的模型中，用戶的興趣服從均值為αμ1+βμ2的高斯分布.

4 實驗結果

本節將本文提出的CSCR模型與已經存在的一些模型比較,有BaseMF[2]，PRM[18]，CircleCon3[13]，SocialMF[4]，SR[19].所有的實驗將在Yelp和Foursquare數據集上進行.

4.1 數據集

我們采用第5屆Yelp挑戰賽的數據集①http://www.yelp.com/dataset challenge.根據商品類別可以劃分成10個類：Activelife，Arts，Beauty，Education，Hotels，Nightlife，Pets，Restaurants，Services，Shopping.數據集中所有用戶數為366 715，每個用戶或商品還包含很多信息，我們只提取一些對我們有用的數據.表1給出了10個類別下的用戶數和商品數的統計量，其中rc指的是用戶在類別c下的平均評分.

Table 1 Statistics of Various Categories on Yelp Dataset表1 Yelp數據集上各個類別記錄統計

另外，實驗還在自己爬取的Foursquare數據集的4個類別上做了對比.這4個類別分別是Hotels，Sports，Traffic，Arts.其中,Hotels類別下共有4 728個用戶和6 078種商品，用戶評分的商品數共有10 991次；Sports類別下含3 443個用戶和3 037種商品，用戶評分的商品數共有5 872次；Traffic類別下含2 590個用戶和2 791種商品，用戶評分的商品共有4 894次；Arts類別下含1 659個用戶和1 291種商品，用戶評分的商品數共2 812次.

4.2 評價指標

Yelp數據集的每個類別下，我們使用5-折交叉驗證訓練模型.每次使用80%的數據作為訓練集，剩下的20%作為測試集.實驗的度量標準采用的是平方根誤差(root mean squared error,RMSE)和平均絕對誤差(mean absolute error,MAE)，這也是推薦系統中常用的2種度量方法.RMSE的定義如下：

4.3 對比實驗

本節給出了我們的模型與已有模型的對比：

1) BaseMF[2].基本的矩陣分解方法通過將用戶-商品矩陣分解成用戶-矩陣和商品矩陣，該方法只用到了用戶的評分矩陣，沒用到任何的社交網絡信息.

2) PRM[18].這個模型考慮了用戶的個性和社交網絡信息，考慮了用戶和用戶之間以及用戶和商品之間的關系.

3) CircleCon3[13].基于興趣圈的推薦模型將朋友圈的新特征與評分結合起來推斷值得信任的興趣圈.

4) SocialMF[4].基于信任傳播的矩陣分解方法假設社交網絡連接了所有的用戶.在模型中加入了信任信息來提高推薦系統的準確率.

5) SR[19].基于社交網絡的推薦系統不僅使用了用戶對商品的評分信息而且增加了社交網絡中隱含的用戶與商品間的關系，而且包括了相同的和不相同的關系.

6) CSCR.這是我們提出的基于2種正則化項和興趣圈的模型.與CircleCon3相比增加了專家用戶對推薦的影響.

設置矩陣分解維度d=10，正則化項參數λ=0.01,α=β=1.在表2和表3中，我們展示了不同模型在Yelp數據集上2種評價指標下的結果.

Table 2 MAE Metric on Ten Categories表2 10個類別上的MAE度量結果

Table 3 RMSE Metric on Ten Categories表3 10個類別上的RMSE度量結果

從表2可以看出在MAE評價指標下，CircleCon3的準確率在前5個對比實驗中是最高的.但是文獻[18]中PRM模型的效果優于CircleCon3，這是因為：1)我們發現盡管PRM用的也是Yelp數據集，但是我們的數據量明顯多于他們使用的數據量；2)從PRM數據集可以看出他們使用的用戶量更少，而商品數更多，而且每個用戶平均對很多商品有評分.PRM方法更關注的是用戶與用戶之間以及用戶與商品之間的關系，所以在用戶可以評分很多商品時模型表現效果會很好.相應的CircleCon3考慮更多的則是用戶信任的朋友，所以當用戶量很多時，模型效果可能會較好.結合我們的數據特點，就可以理解為什么CircleCon3的效果好于PRM了.但是我們也可以看出在某些類別，PRM的性能也可能比CircleCon3要好(如Nightlife).

在表3的RMSE度量標準下，CircleCon3，SocialMF模型效果相對較好，而SocialMF的整體效果可能稍微比CircleCon3好一些.在Arts，Hotels，Pets這些類別下，SocialMF優于CircleCon3.這3個類別的數據特點是數據稀疏度相對較低.因為SocialMF使用的是所有可用的社會關系，所以它可能會表現較好.但是在其他的類別下，CircleCon3的效果則更好.

我們的模型在2種度量標準下分別是最優的.基于興趣圈的方法使用信任的朋友及專家信息來輔助推薦.通過實驗結果，可以看出加入專家群體的推薦效果是顯著的.因為當數據集中有更多的用戶而每個用戶平均評分的商品數又比較少時，在相同圈子的專家可能會對推薦有很大的影響.在表2中MAE的度量標準下我們方法的效果也并不總是最好的，在Education類別下CircleCon3的準確率更高.這可能是因為這個類別中的用戶數和商品數都比較少，所以受專家的影響并不明顯.但整體來說CSCR方法比前面提出的方法效果都好.

圖2(a)是baseMF，PRM，CircleCon3，CSCR這4個算法在Foursquare數據集的4個類別上MAE度量結果，圖2(b)則是RMSE度量結果.從圖2(b)中可以看出除了在Sports類別的RMSE度量上CircleCon3效果最好外，CSCR算法總體來說效果是最好的.而CircleCon3之所以在Sports類別下RMSE值最小可能是因為該類別下用戶的偏好更傾向于他們的朋友.

Fig. 2 Algorithm results on 4 categories of Foursquare圖2 算法在Foursquareo數據集4個類別上的結果

下面我們對比了模型中參數α,β,λ分別在MAE和RMSE度量下不同取值的模型效果.實驗選取了Activelife和Hotels兩個類別的數據.其中α取值為{0,0.001,0.01,0.1,0.3,0.5,1,5,10}，β取值為{0,0.001,0.01,0.1,0.3,0.5,1,5,10}，λ取值為{0,0.001,0.01,0.05,0.1,0.3,0.5,1,10}.

圖3展示了α變化對模型的影響.可以看出當α=1時在2種度量標準下的準確率都是最高的.當α=0時，模型不考慮朋友的影響，可以看出這時模型效果也不是最優的.隨著α值的增大，可以看出加入朋友信息可以提高推薦性能，直到達到最優點，然后再增加α值，模型效果將會下降，甚至在一個類別上會比不考慮朋友的影響還差.這是因為模型過擬合了U矩陣而對V矩陣又估計不足.

Fig. 3 The results of CSCR algorithm on two categories with the change of α圖3 CSCR算法在2個類別上隨α變化的結果

Fig. 4 The results of CSCR algorithm on two categories with the change of β圖4 CSCR算法在2個類別上隨β變化的結果

圖4給出了β值對模型的影響.當β=0時，模型不考慮專家群體對推薦的影響，這也就是CircleCon3模型，從圖4中可以發現這時的模型效果并不是最優的;隨著β值的增加模型準確率越來越高直到最優,這也說明了專家群體對推薦是有幫助的;但是再增加β值，模型準確率又會下降，所以更大的β值并不一定會使推薦效果更好.

圖5則給出了λ值對模型的影響.從2個類別的數據分別在MAE和RMSE度量標準下的表現來說，當λ值在0～0.01過程中，模型效果是越來越好的；在0.01～1的過程中，模型對λ值變化并不敏感；但是當其特別大(如λ=10)，模型的性能會迅速下降.所以對U，V的規則化的系數不應太大.

Fig. 5 The results of CSCR algorithm on two categories with the change of λ圖5 CSCR算法在2個類別上隨λ變化的結果

4.4 用戶冷啟動問題

冷啟動實驗在Yelp數據集Nightlife，Restaurants，Shopping三個類別上進行，對比用戶評分的商品數變化時不同算法的效果.最終給出的結果則是3個類別下的平均值.測試集根據用戶的評分數被分成了5組，分別是：0～10，11～20，21～40，41～80，>80.

圖6(a)和圖6(b)分別表現了在不同的用戶評分量下的這些算法效果.圖6橫軸上的數字表示用戶給多少商品評分了，如“0～10”表示用戶評分量在0～10之間，“11～20”表示用戶評分量在11～20之間，“80～”表示用戶評分數超過80，以此類推.圖6(a)的縱軸表示MAE值，圖6(b)的縱軸表示RMSE值.從這2幅圖可以看出，當用戶評分的商品增加時，算法的準確率也會提高；當用戶評分的商品很少時，BaseMF算法效果很差，但是隨著評分數目的增加，算法性能會變得越來越好.不管怎樣，從圖6(a)和圖6(b)都可以看出，我們提出的方法在Yelp數據集上MAE和RMSE的度量標準下值都最低.這是因為基于興趣圈的推薦不僅考慮了信任的朋友關系而且用到了專家群體的意見，這在推薦過程中確實是有用的.

Fig. 6 The impact on the model with different user rating counts圖6 用戶評分的商品數對模型的影響

我們的方法在5組冷啟動實驗組效果始終是最好的.因為我們的數據集中用戶數很多，商品數相對較少，而大部分用戶評分的商品數并不是很多，在這種情況下我們提出的基于用戶信任的朋友關系和專家的關系在推薦中就有重要的作用.從圖5中也可以得知，當用戶評分很多商品時，算法的性能也會變得越來越好，第5組實驗的結果彼此就非常接近了.所以用戶評分更多的商品對模型是有幫助的，但是也可以發現這個提升度是逐漸降低的.

5 結束語

本文的目標是解決冷啟動問題，文中提出了一種在LBSN上基于興趣圈中社會關系的模型來提高推薦效果.具體來說，社會關系有朋友關系和專家用戶，由此設計的2個規則化項作為矩陣分解目標函數的約束項.在CircleCon3模型的基礎上，我們不僅考慮了顯性的用戶信息而且考慮了隱含的關系來提高推薦系統的冷啟動問題.朋友或者專家都有自己的評分記錄，分別根據不同的興趣圈做出劃分，每個圈子中的所有商品都屬于同一類別.在Yelp和Foursquare兩個數據集上的實驗表明本文提出的使用混合社交網絡信息的方法整體優于已有方法.

[1]Bao Jie, Zheng Yu, Wilkie D, et al. Recommendations in location based social networks: A survey[J]. GeoInformatica, 2015, 19(3): 525-565

[2]Salakhutdinov R, Mnih A. Probabilistic matrix factorization[C] //Proc of the Int Conf on Machine Learning. New York: ACM, 2012: 880-887

[3]Koren Y. Factorization meets the neighborhood: A multifaceted collaborative filtering model[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 426-434

[4]Jamali M, Ester M. A matrix factorization technique with trust propagation for recommendation in social networks[C] //Proc of the 4th ACM Conf on Recommender Systems. New York: ACM, 2010: 135-142

[5]Ma Hao, Zhou Dengyong, Liu Chao, et al. Recommender systems with social regularization[C] //Proc of the 4th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2011: 287-296

[6]Tang Jiliang, Gao Huiji, Hu Xia, et al. Exploiting homophily effect for trust prediction[C] //Proc of the 6th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2013: 53-62

[7]Yu Le, Pan Rong, Li Zhangfeng. Adaptive social similarities for recommender systems[C] //Proc of the 5th ACM Conf on Recommender Systems. New York: ACM, 2011: 257-260

[8]Guo Lei, Ma Jun, Chen Zhumin. Trust strength aware social recommendation method[J]. Journal of Computer Research and Development, 2015, 52(9): 1805-1813 (in Chinese)(郭磊, 馬軍, 陳竹敏. 一種信任關系強度敏感的社會化推薦算法[J]. 計算機研究與發展, 2015, 52(9): 1805-1813)

[9]Huang Junming, Cheng Xueqi, Guo Jiafeng, et al. Social recommendation with interpersonal influence[C] //Proc of the 19th European Conf on Artificial Intelligence. Amsterdam, Netherlands: IOS Press, 2010: 601-606

[10]Jiang Meng, Cui Peng, Wang Fei, et al. Scalable recommendation with social contextual information[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(11): 2789-2802

[11]Yang Yongxiang. Recommendation algorithms based on combination of matrix factorization and random walk[D]. Beijing: Beijing Jiaotong University, 2014 (in Chinese)(楊永向. 基于矩陣分解和隨機游走相結合的推薦算法[D]. 北京: 北京交通大學, 2014)

[12]Wei Suyun, Xiao Jingjing, Ye Ning. Collaborative filtering algorithm based on co-clustering smoothing[J]. Journal of Computer Research and Development, 2013, 50(1): 163-169 (in Chinese)(韋素云, 肖靜靜, 業寧. 基于聯合聚類平滑的協同過濾算法[J]. 計算機研究與發展, 2013, 50(1): 163-169)

[13]Yang Xiwang, Steck H, Liu Yong. Circle-based recommendation in online social networks[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 1267-1275

[14]Zhao Guoshuai, Qian Xueming, Feng He. Personalized recommendation by exploring social users’ behaviors[C] //Proc of the Multi Media Modeling. Berlin: Springer, 2014: 181-191

[15]Tang Jiliang, Hu Xia, Gao Huiji, et al. Exploiting local and global social context for recommendation[C] //Proc of the Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2013: 264-269

[16]McPherson M, Smith-Lovin L, Cook J M. Birds of a feather: Homophily in social networks[J]. Annual Review of Sociology, 2001, 27(1): 415-444

[17]Sun Jimeng, Tang Jie. A survey of models and algorithms for social influence analysis[M] //Social Network Data Analytics. Berlin: Springer, 2011: 177-214

[18]Feng He, Qian Xueming. Recommendation via user’s personality and social contextual[C] //Proc of the 22nd ACM Int Conf on Information & Knowledge Management. New York: ACM, 2013: 1521-1524

[19]Ma Hao. An experimental study on implicit social recommendation[C] //Proc of the 36th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2013: 73-82

Li Xin, born in 1989. PhD. Received his PhD degree from the University of Science and Technology of China (USTC) in 2015. His main research interests include location based services, recommender system, machine learning.

Liu Guiquan, born in 1970. PhD. Associate professor in the University of Science and Technology of China (USTC). His main research interests include data and knowledge management systems, data and text mining, multiagent systems.

Li Lin, born in 1977. PhD. Professor in Wuhan University of Technology. Her current research interests include text mining, machine learning, information retrieval and recommender system (cathylilin@whut.edu.cn).

Wu Zongda, born in 1983. PhD. Associate professor in Wenzhou University. His research interests include information retrieval and personal privacy (zongda1983@163.com).

Ding Junmei, born in 1991. Master candidate in computer science at the University of Science and Technology of China(USTC). Her main research interests include machine learning and data mining.

2015年《計算機研究與發展》高被引論文TOP10

數據來源：CSCD，中國知網；統計日期：2016-12-05

Circle-Based and Social Connection Embedded Recommendation in LBSN

Li Xin1,2, Liu Guiquan1, Li Lin3, Wu Zongda4, and Ding Junmei1

1(SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei230022)2(BigDataResearchInstitute,iFlytekCo.,Ltd,Hefei230088)3(SchoolofComputerScienceandTechnology,WuhanUniversityofTechnology,Wuhan430070)4(SchoolofComputerScienceandTechnology,OujiangCollegeWenzhouUniversity,Wenzhou,Zhejiang325035)

With the pervasiveness of GPS-enabled smart phones, people tend to share their locations online or check in at somewhere by commenting on the merchants, thus arousing the prevalence of LBSN (location based social network), which takes POIs (point-of-interests) as the center. A typical application in social networks is the recommendation system, and the most common problem in recommendation system is cold start, that is, how to recommend for the users who rarely comment on the item or share comments. In this paper, we propose a recommendation algorithm based on circle and social connections in social networks. The circle is made up by all users who visit a particular category of items and their social connections. It means he is interested in this category that a user accesses the category of items. Our algorithm considers different social connections and circles on tradition matrix factorization. The social connections we use include the relationship between friends(explicit relation) and relevant experts(implicit), which are used as the rule to optimize the matrix factorization model. Experiments are conducted on the datasets from the 5th Yelp Challenge Round and Foursquare. Experimental results demonstrate that our approach outperforms traditional matrix factorization based methods, especially in solving cold-start problem.

point-of-interests (POIs)；recommendation; interest circle; social connection; cold-start

2015-09-01；

2016-06-30

國家自然科學基金項目(61202171)；浙江省自然科學基金項目(LY15F020020)；國家“八六三”高技術研究發展計劃基金項目(2015AA015403) This work was supported by the National Natural Science Foundation of China (61202171), the Natural Science Foundation of Zhejiang Province (LY15F020020), and the National High Technology Research and Development Program of China (863 Program) (2015AA015403).

劉貴全(gqliu@ustc.edu.cn)

TP181