融合社區結構和興趣聚類的協同過濾推薦算法

郭弘毅　劉功申　蘇　波　孟　魁

(上海交通大學電子信息與電氣工程學院　上海　200240)

?

融合社區結構和興趣聚類的協同過濾推薦算法

郭弘毅劉功申蘇波孟魁

(上海交通大學電子信息與電氣工程學院上海200240)

(king-guo@sjtu.edu.cn)

傳統的協同過濾推薦算法受限于數據稀疏性問題，導致推薦結果較差.用戶的社交關系信息能夠體現用戶之間的相互影響，將其用于推薦算法能夠提高推薦結果的準確度，目前的社交化推薦算法大多只考慮了用戶的直接社交關系，沒有利用到潛在的用戶興趣偏好信息以及群體聚類信息.針對上述情況，提出一種融合社區結構和興趣聚類的協同過濾推薦算法.首先通過重疊社區發現算法挖掘用戶社交網絡中存在的社區結構，同時利用項目所屬類別信息，設計模糊聚類算法挖掘用戶興趣偏好層面的聚類信息.然后將2種聚類信息融合到矩陣分解模型的優化分解過程中.在Yelp數據集上進行了新算法與其他算法的對比實驗，結果表明，該算法能夠有效提高推薦結果的準確度.

重疊社區；興趣聚類；推薦算法；協同過濾；矩陣分解

近年來，隨著信息技術和互聯網的飛速發展，人們逐漸從信息匱乏的時代走入了信息過載的時代, 如何從海量數據中篩選出有價值的信息是信息消費者和信息提供者都要面對的挑戰.推薦系統作為聯系用戶和信息的工具由此應運而生，它能夠使得信息消費者獲取對自己感興趣的信息，同時使得信息提供者能夠有針對性地向目標用戶投放信息，實現兩者的共贏.目前，推薦系統已經不同程度地運用到了多個互聯網領域中[1].

推薦算法是推薦系統的關鍵部分.其中，協同過濾推薦算法是目前應用最為成功的推薦技術之一[2].其主要思想是利用目標用戶的消費記錄，基于消費行為或者評分相似的用戶具有相似消費偏好的假設，找到與目標用戶偏好相似的用戶集合，根據用戶集合的喜好給目標用戶推薦其可能感興趣的項目.相較于基于內容的推薦算法，盡管協同過濾推薦算法不依賴于項目的特征信息，不受限于內容分析技術的局限，但是受限于數據稀疏性問題[3].互聯網規模的急速擴張帶來了用戶數量和項目數量的急劇增長，用戶-項目評分信息稀疏，用戶間共同消費的項目很少，直接導致推薦結果的準確度下降.

隨著Web2.0的迅速發展，互聯網用戶能夠扮演愈發活躍的角色，除了常規的購買和評分行為，還能夠與信賴的或志同道合的用戶建立信任關系.用戶的消費行為也不再僅僅是其個人的興趣偏好的體現，而且在一定程度上也受到與其具有社交關系的用戶的影響.社交網絡分析的研究表明，網絡社區中，受到社交因素的影響，有社交關聯的用戶往往會體現出相似的興趣愛好和行為特征[4].因此，融入用戶社會屬性的社交化推薦系統成為近年來推薦系統領域的研究熱點.其中傳統的社交化推薦算法采用了基于信任的模型，利用了用戶間的直接信任關系，然而隨著互聯網規模的不斷擴大，用戶間的直接信任關系不可避免地出現數據稀疏性的問題.此外，基于信任模型的社交化推薦算法的基本假設是用戶的興趣偏好與其所信任的用戶相似或者受到這些用戶的影響[5].然而在現實生活中，用戶的興趣偏好是多方面的，其信任的個體間的興趣偏好也存在差異，單一的直接社交關系并不能刻畫出針對不同領域的項目時用戶與好友的興趣偏好的差異性.

基于上述原因，本文提出一種融合社區結構和興趣聚類的協同過濾推薦算法.通過重疊社區發現算法挖掘用戶的社交網絡結構中蘊含的社區信息，避免了使用直接社交關系引起的數據稀疏性問題，量化不同用戶在社區中的影響力的差異.此外，考慮到同一社區中用戶群體的興趣偏好的差異，利用項目類別信息，挖掘用戶興趣偏好層面的聚類信息.將2種聚類信息融合到基于矩陣分解的協同過濾算法中，通過對矩陣分解過程中的隱式特征向量進行約束來優化目標函數.

1　相關工作

傳統的協同過濾推薦算法分成基于內存的方法和基于模型的方法2類[6].近年來，基于矩陣分解模型的協同過濾推薦算法作為基于模型的方法中的一個分支被廣泛應用到了推薦系統中.它能夠把高維的用戶-項目評分矩陣轉化成表示用戶和項目隱式特征向量的低維矩陣乘積的形式，實現高維數據的降維，在緩解數據稀疏性造成的推薦結果準確度下降問題方面有非常好的效果.文獻[7]首先提出了矩陣分解技術在推薦系統領域的應用，文獻[8]提出了概率矩陣分解模型，從條件概率最優的角度進行矩陣的概率優化分解，得到了相同的矩陣分解模型.

在社交化推薦算法中，矩陣分解技術融合了用戶的各種社會屬性信息，基于用戶與所信任的用戶群體具有相似的興趣偏好或者受其影響的假設，通過在矩陣優化分解的過程中添加相關約束得到更優的用戶隱式特征向量.文獻[9]提出了SoRec模型，它是一種社會譜正則化的變形方法，把矩陣分解技術同樣作用在信任矩陣上，用戶隱式特征向量同時從用戶-項目評分矩陣和信任矩陣的優化分解過程中得到.文獻[10]提出了STE模型，把用戶-項目評分矩陣中的項看作是用戶個人偏好以及用戶信任好友喜好的組合，在優化分解過程中將用戶對項目的評分和用戶的朋友對項目的評分加權平均，使得推薦結果擁有了可解釋性.文獻[11]提出了SocialMF模型，假設用戶的隱式特征向量是由其朋友的隱式特征向量決定的，在優化分解過程中引入了信任傳播的概念.這些社交化推薦算法只利用了用戶的直接社交關系，當直接社交關系稀疏時會導致推薦結果不理想.文獻[12]首次在社交化推薦算法中引入了重疊社區發現算法，關注對目標函數中的正則項的約束.提出了2種模型旨在減小用戶與其所在社區其他用戶的偏好的差異.文獻[13]在SocialMF模型的基礎上進行改進，區分了對于不同項目類別，用戶對不同好友的信任度的差異.算法直接根據項目類別劃分用戶的好友，因此可能會進一步加劇數據稀疏性問題.文獻[14]考慮到信任多樣性的特點.對用戶信任關系和用戶興趣進行建模識別出目標用戶信任且興趣接近的用戶，改進SocialMF模型.但算法仍可能受限于直接社交關系稀疏問題.

2　融合社區結構和興趣聚類的推薦算法

本文提出的融合社區結構和興趣聚類的協同過濾推薦算法的流程如圖1所示.1)利用重疊社區發現算法挖掘用戶社交網絡中存在的社區結構，得到基于網絡結構的用戶集合；2)利用針對數據特性改進的模糊C均值聚類算法，根據項目類別信息和用戶行為記錄得到基于興趣偏好相似度的用戶集合，分別量化目標用戶對其所屬的2類不同用戶集合的感興趣程度；3)將2種用戶聚類信息融合到矩陣分解模型的優化分解過程中，通過在目標函數中引入新的正則項試圖得到更優的分解結果，最終獲得用戶對項目的預測評分.

Fig. 1　The flow chart of co-clustering recommendation algorithm.圖1　融合雙重聚類的推薦算法流程圖

2.1準備工作

設U={u1,u2,…,um}表示推薦系統中所有用戶的集合，V={v1,v2,…,vn}表示推薦系統中所有項目的集合，C={c1,c2,…,cq}表示推薦系統中所有項目類別的集合，其中m,n,q分別表示用戶總數、項目總數、類別總數.R=(Ri j)m×n表示用戶-項目評分矩陣，其中Ri j∈{1,2,3,4,5}表示用戶ui對項目vj的評分.T=(Ti j)m×m,Ti j∈{0,1}表示用戶的社交關系矩陣，Ti j=1表示用戶ui與用戶uj之間存在好友關系.本文采取雙向確認的用戶的社交關系，因此矩陣T為對稱矩陣.

2.2基于社區結構的聚類

推薦系統中的用戶集合以及用戶間的社交關系構成了龐大的社交網絡，用戶往往與其直接好友具有相似的興趣偏好或者受其影響，一些研究[9-10,15]即根據這個假設在傳統的協同過推薦算法加入用戶的社交關系信息進行優化.然而在大型社交網絡中普遍存在著長尾效應[16]，即社交關系多的用戶占總量的少數，而絕大多數用戶只有很少的社交關系.因此，有必要在網絡中挖掘其他有價值信息.社交網絡中總是存在社區結構，同一個社區內的用戶具有某些相同的特性，如地理位置相近、行業領域相同、關注的內容主題相近等.社區內的其他用戶或多或少地會對用戶的選擇產生影響.社交網絡中的用戶往往同屬于多個社區，比如用戶與其所在城市相同的用戶屬于一個社區，與喜愛科幻類電影的用戶同屬于另外一個社區.這些重疊社區信息體現了用戶的不同特性.

對于社交網路中的重疊社區發現的研究是近年來社區發現領域的研究熱點，本文直接采用其中效果突出的重疊社區發現算法來劃分推薦系統中的用戶社交網絡.BIGCLAM算法是一種適用于大型網絡的重疊社區發現算法[17]，它基于社區間重疊部分中的節點緊密連接的假設，在非負矩陣分解模型的基礎上進行改進.文獻[12]的實驗比對結果表明使用BIGCLAM算法得到的社區信息作為社交化推薦算法的約束條件能夠取得較好的推薦結果.因此，本文選擇BIGCLAM算法劃分用戶社交網絡中的重疊社區.

顯然，用戶對于其所在的不同社區的感興趣程度存在差異，文獻[12]中設定某個社區內所有用戶對應在用戶-評分矩陣內的用戶評分向量的平均值作為社區評分向量，計算屬于該社區的某用戶對應的用戶評分向量與該社區評分向量的相似度作為該用戶對該社區的感興趣程度.然而社區中的每個用戶對該社區做出的貢獻是不同的.相對于處于社區結構邊緣的用戶，在社區中擁有更多與其有直接社交關系的好友的用戶更能夠代表這個社區.基于該假設考慮社區中所有用戶的評分向量和社區好友數量，從而獲取帶權重的社區評分向量:

(1)

(2)

由此，我們得到了基于社交網絡結構的用戶社區信息，用戶評分向量與所屬社區的社區評分向量的相似度即表示用戶對該社區的感興趣程度.處在同一社區中的用戶具有相同的特性或相互影響.

2.3基于興趣偏好的聚類

重疊社區發現算法將用戶集合根據其社交網絡結構進行劃分，屬于同一社區內的用戶存在相同的特性或相互影響.然而同一社區內的用戶依然可能存在不同的興趣偏好.如喜愛科幻電影的用戶被劃分入一個社區，但他們對于音樂、游戲、飲食的偏好卻存在很大差異，因此有必要對同一社交網絡社區中的用戶進行進一步的劃分.基于以上原因，提出了基于興趣偏好的模糊聚類算法，該算法利用用戶的行為記錄以及項目所屬的類別，尋找與目標用戶在泛化層面的興趣偏好相似的用戶集合.

1) 定義用戶類別偏好向量

用戶評分過的項目可能屬于不同的類別，用戶對某一類別中的項目的評分數量占的比例與該用戶對該類別感興趣的程度成正比.用戶ui評分過的所有項目的所屬類別的分布向量可描述如下：

(3)

2) 定義聚類目標函數

模糊C均值聚類(fuzzy C-means)[18]作為模糊聚類分析中的一個比較成熟的算法，在各個領域都有著廣泛的應用.其通過優化目標函數來獲取每個樣本點屬于某個類簇的隸屬度，即樣本點可以同時屬于多個類簇，符合推薦系統中用戶興趣偏好的性質.模糊C均值聚類在計算樣本點向量和類簇中心點向量的相似度時通常采用的是閔可夫斯基距離.即

(4)

當p=1時，D(X,Y)為曼哈頓距離，當p=2時為歐幾里得距離.然而推薦系統中的用戶-項目評分矩陣數據稀疏，用戶大多只對某幾個類別的項目產生過評分行為，導致用戶類別偏好向量也存在稀疏性問題，直接使用閔可夫斯基距離公式計算得出的相似度可能會影響聚類的效果.

基于以上原因，需要設計能夠處理用戶類別偏好向量存在的數據稀疏性問題的相似度測量方式.可描述如下：

(5)

式(5)表示樣本點向量與類簇中心向量的相似度.我們假設類簇的數量為l.式(5)中gj表示某個類簇中心點j(j=1,2,…,l)的向量.gj,k為gj中的第k個元素.Dsparse在用戶類別偏好向量中選取非零元素即用戶產生過評分行為的類別元素計算相似度.

有了相似度表達式，我們接著定義目標函數的表達式:

(6)

3) 聚類算法過程

基于興趣偏好的模糊聚類算法通過迭代運算，更新用戶類簇隸屬度矩陣B和類簇中心矩陣G的值，逐步減小目標函數的誤差值，當目標函數的誤差值收斂至預設閾值時迭代終止.具體過程如下：

② 更新類簇中心矩陣G

(7)

其中，j=1,2,…,l.

③ 更新用戶類簇隸屬度矩陣B

(8)

其中，i=1,2,…,m;j=1,2,…,l.

由此，我們得到了基于興趣偏好的用戶模糊聚類，用戶類簇隸屬度矩陣B中的元素μi j即表示用戶ui對興趣類簇Ψj的感興趣程度.處在同一類簇中的用戶具有相似的泛化興趣偏好.

2.4融合雙重聚類的矩陣分解方法

1) 矩陣分解模型

矩陣分解模型是在協同過濾推薦算法中應用最為廣泛的模型之一.其主要思想是將用戶-項目評分矩陣R近似地分解成2個低維矩陣乘積的形式：

(9)

(10)

其中,Ii j為指示函數，用戶ui對項目vj產生過評分，則Ii j=1，否則Ii j=0.由于用戶-項目評分矩陣的稀疏程度很大，在矩陣分解過程中容易出現過擬合問題，因此需要在目標函數中添加合適的正則項.

(11)

2) 融合雙重聚類的矩陣分解模型

在現實生活中，我們所做的決定往往受到好友或者領域權威人士的影響.在2.2節、2.3節中我們得到了用戶社交網絡社區聚類信息和用戶泛化興趣偏好聚類信息，其中前者將相互影響并且特性相同的用戶聚類在一起，后者將多領域興趣偏好相似的用戶聚類在一起.顯然目標用戶與同一集合中的用戶的相似度要高于與之不共享任一集合的用戶的相似度，用戶的興趣偏好和與其同在一個集合中的所有用戶的平均興趣偏好接近，并且用戶對不同集合的感興趣程度不同.基于以上假設，我們在文獻[20]中提出的矩陣分解模型基礎上進行改進，引入新的正則項:

(12)

由此，我們提出了一種新的融合雙重聚類的矩陣分解模型，記為CCMF(co-clustring based matrix factorization).目標函數如式(13)所示.

(13)

通過隨機梯度下降方法得到用戶隱式特征矩陣U和項目隱式特征矩陣V的局部最優解.相應的偏導數如式(14) (15)所示.

(14)

(15)

通過不斷迭代，沿梯度下降方向更新U和V中的元素直至收斂來訓練模型.

3　實驗與評估

3.1數據集

本文使用Yelp數據集對算法進行測試.Yelp.com是全球最大的本地商家點評網站之一，它不但允許用戶對商家進行點評或者評分，還是一個社交特征明顯的互聯網公司，鼓勵用戶之間積極互動，其平臺上的用戶能與其他用戶建立雙向確認的好友關系.我們在本文中使用的Yelp數據集是Qian等人在文獻[21]中使用的數據集.數據集由8 351位用戶、84 653個項目、263 777條項目評分信息以及524 120條用戶雙向好友關系信息組成.其中，項目評分為[1,5]之間的整數，所有項目總共分為8個類別.表1中是對 Yelp數據集中分類別信息的統計數據.

Table 1　Statistic of Per Category表1　數據集分類別統計量

3.2對比算法

為了驗證本文提出的算法與其他算法在推薦結果準確度上的差別，我們選擇5種算法作為對比算法進行實驗.

BaseMF：文獻[6]提出的適用于推薦系統的矩陣分解基本模型，沒有加入用戶的社交關系信息或項目類別信息.

SocialMF：文獻>[11]提出的融入用戶信任關系信息的矩陣分解模型，假設用戶向量是由其好友的用戶向量決定的，在優化分解過程中引入了信任傳播的概念.

SoReg：文獻[20]首次提出了在矩陣分解模型中加入社交化正則項的概念，通過加入社交化正則項使得用戶的偏好與其好友偏好的平均值相似.

MFC：文獻[12]在矩陣分解模型中引入了重疊社區發現算法，在SoReg算法的基礎上區分了用戶所在社區不同的差異.

CircleCon：文獻[13] 依據針對不同的項目類別，用戶對其好友的信任關系存在差異的假設，在SocialMF算法的基礎上根據項目類別劃分了用戶信任網絡.

3.3評價指標

本文使用五重交叉驗證作為實驗方法.將數據集隨機分為5份，每次選擇其中的4份即數據集的80%作為訓練集，選擇余下的一份即數據集的20%作為測試集，將5次的評估結果取平均值得到最終的評估數據.

由于本文提出的協同過濾算法的目標是為了提高推薦結果的準確度，因此我們采用平均絕對誤差(mean absolute error,MAE)和均方根絕對誤差(root mean square error,RMSE)作為實驗的評估方法.

(16)

(17)

3.4實驗結果及分析

1) 確定興趣類簇l的值

Fig. 2　Impact of parameter l.圖2　興趣類簇l的值對準確度的影響

興趣類簇l的值代表了根據所有用戶的行為記錄以及項目的類別信息劃分的泛化興趣類簇數量.在實驗中我們選擇將l的值從5～25以步長5增加，記錄推薦結果的MAE值和RMSE值隨不同l值的變化情況.為了更加清楚地了解l值對推薦結果產生的影響，我們根據正則項系數λZ值的不同，分5組進行實驗.實驗結果如圖2所示：

從圖2中可以看到，對于不同的λZ值，推薦結果的準確度隨不同l值的變化情況基本相同，使用l值過大或者過小都會對推薦結果產生負面的影響.當l=15時，推薦結果的MAE值和RMSE值同時達到最小.分析其可能原因，如果興趣類簇的數量設定得過小，經過模糊聚類劃分出的類簇結果并不能清晰地劃分用戶在不同興趣愛好的層面的分布情況；而興趣類簇的數量設定得過大時，經過模糊聚類劃分出的類簇過多，可能削弱了其對用戶泛化興趣愛好的表達.

2) 確定正則項系數λZ的值

Fig. 3　Impact of parameter λZ.圖3　正則項系數λZ的值對準確度的影響

正則項系數λZ表示用戶社交網絡重疊社區信息以及興趣偏好模糊聚類信息在矩陣分解模型中參與的比重，當λZ=0時本文提出的模型即相當于基本的矩陣分解模型.將λZ的值分別取值為{0.0001,0.001,0.01,0.1,1}進行實驗.記錄推薦結果的MAE值和RMSE值隨不同λZ值的變化情況.同樣地，為了更加清楚地了解λZ值對推薦結果產生的影響，我們根據不同的興趣類簇l的值，分5組進行實驗.如圖3所示：

從圖3中可以看到，對于不同的l值，推薦結果的準確度隨不同λZ值的變化情況基本相同.當λZ取值較小時，推薦結果的MAE值和RMSE值相對較高，隨著λZ取更大的值，MAE值和RMSE值減小，當λZ=0.01時同時達到最優的準確度.而繼續增加λZ的值后，準確度再次降低.分析其可能原因，當λZ取值過小時，算法引入的附加信息對結果造成的影響微弱，不足以體現其在獲得更優的用戶隱式特征向量中所做的貢獻；而λZ取值過大時，附加信息在優化向量過程中的權重過大造成過度影響.

3) 不同推薦算法的推薦效果對比

通過之前實驗的對比和分析，可知當興趣類簇l=15，正則項系數λZ=0.01時，本文提出的CCMF算法能夠獲得最優的推薦結果.為了進一步驗證CCMF算法的有效性，我們將CCMF算法與3.2節中介紹的相關算法進行了對比實驗.首先通過五重交叉驗證確定實驗中所有算法的參數.常規正則項系數λU和λV均取值為0.01，用戶和項目的隱式特征向量維數均取10.在SocialMF，SoReg，MFC，CircleCon算法中，社交正則項系數λZ分別設為0.01,0.01,0.001,0.01.SoReg中的β值設為0.5.實驗結果如表2所示：

Table 2　Comparison of CCMF and Other Methods表2　CCMF算法與其他算法的實驗結果對比

從表2中可以看到，本文提出的融合社區結構和興趣聚類的協同過濾算法相較于其他算法，推薦結果的準確度更高.分析其可能的原因，BaseMF算法由于沒有考慮任何用戶-項目評分矩陣以外的信息所以推薦效果最差.SocialMF，SoReg，MFC算法沒有同時利用用戶社交信息和項目類別信息.CircleCon算法直接將用戶根據其評分過的項目所屬類別進行劃分，然而單個項目類別下的用戶的社交關系可能存在數據稀疏問題.本文提出的CCMF算法一方面使用用戶重疊社區信息，一定程度上緩解了用戶的社交關系的稀疏性問題；另一方面，針對泛化興趣偏好的模糊聚類為用戶隱式特征向量提供了更有利的約束條件.因此能夠得到更好的推薦效果.

4　結束語

基于直接社交關系的傳統社交化推薦算法面臨用戶社交信息稀疏的問題，而且沒有考慮用戶興趣偏好對社交關系造成的影響，導致推薦結果不理想.為了解決這一缺陷，本文提出了一種在矩陣分解模型中融合社區結構和興趣聚類的協同過濾推薦算法.利用重疊社區發現算法挖掘用戶的社交關系層面的聚類，同時根據項目類別信息設計算法實現對用戶興趣偏好的模糊聚類，并且能夠量化用戶對不同社區或類簇的感興趣程度.通過實驗證明該算法比現有算法能夠得到更優的推薦結果.

[1]KantorPB,RokachL,RicciF,etal.RecommenderSystemsHandbook[M].Berlin:Springer, 2011: 1-2

[2]SuX,KhoshgoftaarTM.Asurveyofcollaborativefilteringtechniques[J//OL].AdvancesinArtificialIntelligence, 2009[2016-02-25].http://dl.acm.org//citation.cfm?id=1722966

[3]AdomaviciusG,TuzhilinA.Towardthenextgenerationofrecommendersystems:Asurveyofthestate-of-the-artandpossibleextensions[J].IEEETransonKnowledgeandDataEngineering, 2005, 17(6): 734-749

[4]KrebsV.Socialnetworkanalysis:Anintroduction[J//OL]. 2015 [2016-02-25].http://www.orgnet.com//sna.html

[5]YangX,GuoY,LiuY,etal.Asurveyofcollaborativefilteringbasedsocialrecommendersystems[J].ComputerCommunications, 2014, 41: 1-10

[6]BobadillaJ,OrtegaF,HernandoA,etal.Recommendersystemssurvey[J].Knowledge-BasedSystems, 2013, 46: 109-132

[7]KorenY,BellR,VolinskyC.Matrixfactorizationtechniquesforrecommendersystems[J].Computer, 2009, 42(8): 30-37

[8]SalakhutdinovR,MnihA.Probabilisticmatrixfactorization[C] //Procofthe20thNeuralInformationProcessingSystems(NIPS’07).Cambridge:MITPress, 2007

[9]MaH,YangH,LyuMR,etal.Sorec:Socialrecommendationusingprobabilisticmatrixfactorization[C] //Procofthe17thACMConfonInformationandKnowledgeManagement(CIKM’08).NewYork:ACM, 2008: 931-940

[10]MaH,KingI,LyuMR.Learningtorecommendwithsocialtrustensemble[C] //Procofthe32ndIntACMSIGIRConfonResearchandDevelopmentinInformationRetrieval(SIGIR’09).NewYork:ACM, 2009: 203-210

[11]JamaliM,EsterM.Amatrixfactorizationtechniquewithtrustpropagationforrecommendationinsocialnetworks[C] //Procofthe4thACMConfonRecommenderSystems(RecSys’10).NewYork:ACM, 2010: 135-142

[12]LiH,WuD,TangW,etal.Overlappingcommunityregularizationforratingpredictioninsocialrecommendersystems[C] //Procofthe9thACMConfonRecommenderSystems(RecSys’15).NewYork:ACM, 2015: 27-34

[13]YangX,SteckH,LiuY.Circle-basedrecommendationinonlinesocialnetworks[C]//Procofthe18thACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining(KDD’14).NewYork:ACM, 2012: 1267-1275

[14]GuoLei,MaJun,ChenZhumin.Truststrengthawaresocialrecommendationmethod[J].JournalofComputerResearchandDevelopment, 2013, 50(9): 1805-1813 (inChinese)

(郭磊, 馬軍, 陳竹敏. 一種信任關系強度敏感的社會化推薦算法[J]. 計算機研究與發展, 2013, 50(9): 1805-1813)

[15]MassaP,AvesaniP.Trust-awarecollaborativefilteringforrecommendersystems[C] //ProcofonOntheMovetoMeaningfulInternetSystemsConfederatedIntConf.Berlin:Springer, 2004: 492-508

[16]FortunatoS.Communitydetectioningraphs[J].PhysicsReports, 2010, 486(3): 75-174

[17]YangJ,LeskovecJ.Overlappingcommunitydetectionatscale:Anonnegativematrixfactorizationapproach[C] //Procofthe6thACMIntConfonWebsearchandDataMining(WSDM’13).NewYork:ACM, 2013: 587-596

[18]BezdekJC,EhrlichR,FullW.FCM:Thefuzzyc-meansclusteringalgorithm[J].Computers&Geosciences, 1984, 10(2): 191-203

[19]XuR,WunschD.Surveyofclusteringalgorithms[J].IEEETransonNeuralNetworks, 2005, 16(3): 645-678

[20]MaH,ZhouD,LiuC,etal.Recommendersystemswithsocialregularization[C] //Procofthe4thACMIntConfonWebSearchandDataMining(WSDM’11).NewYork:ACM, 2011: 287-296

[21]QianX,FengH,ZhaoG,etal.Personalizedrecommendationcombininguserinterestandsocialcircle[J].IEEETransonKnowledgeandDataEngineering, 2014, 26(7): 1763-1777

GuoHongyi,bornin1992.Master.Hismainresearchinterestsincluderecommendersystemanddatamining(king-guo@sjtu.edu.cn).

LiuGongshen,bornin1974,PhD,associateprofessorandmastersupervisor.MemberofChinaComputerFederation,Hisresearchinterestsincludeinformationsecurityanddatamining(lgshen@sjtu.edu.cn).

SuBo,bornin1972.Associateprofessorandmastersupervisor.Hisresearchinterestsincludeimageprocessingandmachinelearning(subo@sjtu.edu.cn).

MengKui,bornin1973.PhD.Herresearchinterestsincludeinformationsecurityandprivacyprotection(mengkui@sjtu.edu.cn).

Collaborative Filtering Recommendation Algorithm Combining Community Structure and Interest Clusters

Guo Hongyi, Liu Gongshen, Su Bo, and Meng Kui

(ShoolofElectronicInformationandElectricalEngineering,ShanghaiJiaoTongUniversity,Shanghai200240)

Traditional collaborative filtering recommendation algorithms suffer from data sparsity, which results in poor recommendation accuracy. Social connections among users can reflect their interactions, which can be mixed into recommendation algorithms to improve the accuracy. Only straightforward social connections have been used by most current social recommendation algorithms, while users’ latent interest and cluster information haven’t been considered. In response to these circumstances, this paper proposes a collaborative filtering recommendation algorithm combining community structure and interest clusters. Firstly, overlapping community detection algorithm is used to detect the community structure existed in user social network, thus users in the same community have certain common characteristics. Meanwhile, we design a customized fuzzy clustering algorithm to discover users’ interest clusters, which uses item-category relationship and users’ activity history as input. Users in the same cluster are similar in generalized interest. We quantify users’ preference for each social community and interest cluster they belong to respectively. Then, we combine this two types of user group information into matrix factorization model by adding a clustering-based regularization term to improve the objective function. Experiments conducted on the Yelp dataset show that, in comparison to other methods including both traditional and social recommendation algorithms, our approach gets better recommendation results in accuracy.

overlapping community; interest cluster; recommendation algorithm; collaborative filtering; matrix factorization

2016-03-17；

2015-05-24

國家“九七三”重點基礎研究發展計劃基金項目(2013CB329603)；國家自然科學基金項目(61472248, 61431008)

TP311; TP181

This work was supported by the National Basic Research Program of China (973 Program) (2013CB329603) and the National Natural Science Foundation of China (61472248,61431008).