融合社區結構和社交影響力的矩陣分解推薦

熊麗榮,沈樹茂,范 菁

(浙江工業大學 計算機科學與技術學院,杭州 310023)

1 引 言

推薦系統作為一種信息過濾工具,可以有效地緩解信息過載問題.幫助人們從大量繁雜的信息中找到自己感興趣的內容.協同過濾技術是現在最流行的推薦方法,其中的矩陣分解方法[1]受到了很多人的關注.

在社交網絡中,用戶的行為不僅會被自己的興趣愛好影響,也會被其他用戶影響.研究表明,擁有一定社交關系的用戶之間會在一些方面存在相似性[2].在矩陣分解推薦算法中引入用戶的社交關系可以增強推薦準確度[3,4].可是社交網絡中往往存在長尾效應[5],即只有少數的用戶擁有大量的社交關系,而大多數的用戶擁有很少的社交關系.在社交網絡中,擁有某些相似的特征和愛好的用戶會相互聚集成為社區,同一個社區內的用戶會對彼此的選擇產生影響.同時,在社區內與用戶擁有間接關系的用戶很多,增加間接社交關系的使用而不只是僅僅使用直接社交關系可以有效地緩解用戶好友稀疏問題.

本文提出一種融合社區結構和社交影響力的矩陣分解推薦算法SoInf.同時使用用戶評分信息和社會網絡結構信息來計算用戶之間的影響力,且將用戶之間的相互影響和用戶個人影響力相結合,更精確刻畫用戶間的相互影響.將社區結構和用戶間社交影響力結合到矩陣分解中,來增加推薦的準確度.

這篇論文的主要貢獻如下:

1)考慮社區內的其他用戶對用戶的影響,而不僅僅是用戶的直接鄰居的影響.基于社交網絡結構進行社區發現,將社區結構用于用戶之間的影響力計算和模型構建.

2)同時使用用戶評分信息和社會網絡結構信息來計算用戶之間的影響力.結合社區信息,計算用戶個人影響力.融合用戶之間的影響力和用戶個人影響力,得到非對稱的用戶之間的影響力.

3)用戶社區結構信息和用戶社交影響力結合到矩陣分解中,提出一種融合社區結構和社交影響力的矩陣分解推薦算法SoInf,緩解用戶評分的稀疏問題,同時提升推薦準確度.

2 相關工作

在社交網絡中,擁有較強的社交關系的用戶之間存在一定的相似性,彼此之間會相互影響.因此在矩陣分解推薦算法中引入社交關系可以增強推薦效果[6,7].引入社交關系的矩陣分解推薦算法可以分成兩類:

1)以用戶特征矩陣為紐帶,同時分解用戶評分矩陣和用戶社交關系矩陣[8,10-12].

2)優化用戶特征向量[13-23],通過與用戶之間擁有社交關系的用戶來優化用戶的特征矩陣.

同時分解用戶評分矩陣和用戶社交關系矩陣的推薦算法認為通過同步分解評分矩陣和社交矩陣可以獲取更準確的用戶隱式特征向量.在概率矩陣分解推薦模型[9]基礎上,Ma等人[8]提出了同時分解用戶評分矩陣和用戶社交關系矩陣的SoRec模型.而對信任與被信任行為的不同進行考慮,Yang等人[10]提出了TrustMF模型,分別刻畫了用戶受其信任用戶的影響與對信任他的用戶的影響.同時考慮局部社交信息和全局社交信息,Tang等人[11]提出了LOCABAL模型,引入不同視角的社交關系以提升推薦效果.

優化用戶特征向量的矩陣分解方法,用戶特征向量受到社交網絡中關聯用戶的影響.引入用戶社交關系,可以優化當前用戶的隱式特征向量.引入用戶好友的偏好信息,Ma等人[13]提出了一種融合社交信息的推薦模型RSTE,在一定程度上利用了社交信息.考慮社交網絡中的用戶的偏好信息會隨著用戶之間的相互交流而傳播,Jamali等人[14]提出了一種社交推薦模型SocialMF,利用信任傳播機制增強推薦效果.SoReg是Ma 等人[15]提出的一種社交正則化推薦模型,使用社交信息對推薦模型進行增強,考慮用戶的行為受到用戶好友的影響,且用戶之間社交關系越強兩個用戶的興趣愛好越相似.Guo等人[16]提出TrustSVD模型,將用戶顯式信任關系與評分信息都看作隱式反饋信息,使用隱式社交反饋信息對用戶特征矩陣進約束.把用戶之間的相似和各個用戶的重要性相結合,Davoudi等人[17]提出了一個社會信任模型,其中包含了偏好相似性、用戶的中心地位和社會關系,并使用矩陣分解來對項目進行評分預測.王等人[18]利用用戶評分過程中潛在存在的信任關系,提出一種基于信任機制的推薦算法TM-PMF.

雖然在上述優化用戶特征的推薦算法中,也有一些算法[14,17]使用了間接社交關系來計算用戶間相似度,但是在構建矩陣分解模型時只利用了用戶的直接相連用戶,即只利用了直接社交關系.直接社交關系存在用戶好友數據稀疏問題.社交網絡中存在社區結構,將社區結合到推薦模型中可以有效地緩解用戶好友稀疏問題.Yang等人[19]提出了CircleCon模型,考慮用戶在不同領域會擁有不同的信任用戶集合,根據評分信息和社交網絡數據推斷出特定分類的社交信任圈,提出基于圈子的推薦模型.Ma等人[20]在SR+模型中認為用戶的隱式特征向量同時依賴于用戶的朋友和與用戶非常相似的其他用戶.然而SR+需要通過預先設定一個相似閾值來過濾與用戶相似的其他用戶.Li等人[21]在社交化推薦算法MFC中引入了重疊社區發現算法,通過計算用戶與社區的相關度和用戶與其他用戶的相似度,來獲取各個用戶間興趣的差異,并對目標函數中的正則項進行約束,使用間接社交關系來增強推薦效果.考慮社交關系中具有同構關系,將興趣愛好相似的用戶分配到同一個社區,在此基礎上Tang 等人[22]構建了推薦模型SoDimRec.Ahmadian等人[23]提出了一種基于自適應鄰居選擇機制的社會推薦算法SRANS.為用戶選擇合適的鄰居,可以提高推薦過程中評分預測的準確性.

本文也是增加了間接社交關系的使用,考慮社區內用戶間的相互影響,來增加推薦準確度.與上述工作不同的是,我們將社區結構和社交影響力融合到矩陣分解推薦模型中.同時使用用戶評分信息和社交網絡結構信息來計算用戶之間的影響力,且將用戶之間的影響力和用戶個人影響力相結合,更精確刻畫用戶間的相互影響,從而提升推薦效果.

3 推薦算法SoInf

3.1 相關定義

U={u1,u2,…,um}表示推薦系統中用戶的集合,V={v1,v2,…,vn}表示推薦系統中項目的集合.將用戶對項目的評分矩陣表示為R=(Rij)m×n,其中Rij∈{1,2,3,4,5}表示用戶ui對項目vj的評分.T=(Tij)m×m表示用戶的社交關系矩陣,Tij=1表示用戶ui和用戶vj之間存在好友關系,否則Tij=0,與用戶ui的直接相連的好友集合為Ni.假設有x個社區,g={g1,…,gx}是社區集合.對于用戶ui,設ui∈gi，C(i)∈(gi∪Ni)表示用戶好友和其所屬社區的其他用戶的集合.矩陣分解推薦算法將用戶評分矩陣R近似地分解成低階的用戶特征矩陣U∈Rl×m和低階的項目特征矩陣V∈Rl×n,其中l是隱特征向量的維數.

3.2 社區發現

用戶的偏好受到社區內其他用戶的影響.采用社區發現算法將用戶集合根據其社交網絡結構進行劃分,屬于同一社區內的用戶存在相同的特性或愛好.簡單隨機塊模型[24]假設生成鏈接的概率只與兩個端點的社區相關,社區選擇各節點的概率相同.而實際的鏈接生成過程與很多因素有關,如有些節點是權威的節點,其被社區選擇的概率相對要大.

Karrer和Newman[25]提出度糾正隨機塊模型DCBM.DCBM使用了Kernighan-Lin算法[26],這是一種基于貪婪原理的啟發式算法.首先將網絡隨機地劃分為x個社區的初始集合.然后重復地將一個頂點從一個集合移動到另一個集合,在每一次移動中選擇目標函數增加最大的移動結果,或者目標函數減少最小的移動,且每個頂點只能移動一次.當所有頂點都被移動后,檢查移動過程中從開始到結束所經過的狀態,選擇目標分數最高的那個移動狀態,并使用這個狀態作為相同過程的新迭代的起點.當目標函數沒有增加時,一個完整的迭代過程結束,并得到最終的網絡的社區劃分結果.

相比于簡單隨機塊模型,DCBM在發現社區的過程中考慮節點度的影響,可以更好地識別網絡中的非重疊廣義社區.本文使用DCBM對用戶網絡進行社區發現,將每個用戶被劃分到各個社區中.

3.3 影響力計算

本文的影響力計算從兩個方面進行考慮.一方面,通過用戶評分信息和社交網絡結構信息來計算用戶之間的影響力.另一方面,通過社交網絡拓撲結構分析用戶在社交網絡中的個人影響力.用戶個人影響力,即用戶影響其他用戶的能力[27],類似于可信度.研究表明在社交網絡中,越重要的人越能快速擴散和放大輿論[28].本文將用戶之間的影響力和用戶的個人影響力相結合,計算非對稱的用戶之間的影響力.

3.3.1 使用用戶評分信息計算用戶之間的影響力

用戶之間的影響力是指任意兩個用戶之間的相互影響的大小,在計算的時候我們同時使用用戶歷史評分信息和社交網絡結構信息.通過用戶歷史評分信息,我們可以分析得到用戶之間的相似性,本文采用皮爾遜相似性來計算相似度.與其他同樣使用用戶評分計算相似度的方法相比較,皮爾遜相關系數中對用戶評分做了處理.在實際情況中,每個用戶的打分習慣和對評分檔位的理解存在差異,導致有些用戶打分整體偏高,而有些整體偏低的情況.而皮爾遜相關系數可以很好的去除這種差異,更準確的衡量用戶之間的相似性.其公式如下:

(1)

3.3.2 使用社交網絡結構信息計算用戶間影響力

但是通過用戶評分計算出的相似度只利用了評分信息,沒有充分利用用戶之間的信息,所以本文同時使用社交網絡結構信息來計算用戶之間的影響力.

使用社交網絡結構數據,通過SimRank算法[29]計算用戶間的影響力.定義兩個用戶i和k之間的SimRank相似度infs(i,k).SimRank基于相似的用戶則鄰居也相似的思想來計算用戶間的相似度,計算方法如下:

1)infs(i,k)=0,當I(i)=φ或I(k)=φ;

2)在其他情況下,

(2)

其中,I(i)表示所有指向用戶a的用戶集合,d∈(0,1)是一個阻尼系數.

在社交網絡中,用戶尋求建議時更容易受到個人影響力大的其他用戶的影響.而且用戶在選擇其他用戶進行交流時,會更傾向于選擇與其同一個社區的用戶,而不是社區外的用戶.

定義社區中各個用戶的局部影響力為si，S為由社區中所有用戶的局部影響力組成的個性化向量.在每個社區中,使用PageRank[30]求出社區中各個用戶的局部影響力si.

定義用戶個人影響力fi，F為網絡中用戶影響力得分向量,fi∈F.

本文通過社區信息計算出的個性化向量S結合到Personalized PageRank[31],計算得到的用戶個人影響力,見公式(3):

F=aPTF+(1-a)S

(3)

P為網絡圖的轉移矩陣,a為跳轉因子.在整個社交網絡中使用Personalized PageRank算法,可以計算出每個用戶的全局個人影響力fi.然后對用戶的全局個人影響力進行數據標準化將影響力映射到[0,1]區間上.

計算出來的用戶之間的影響力基本都呈對稱性,直接用來描述用戶之間的影響會有一定偏差.在實際情況中,用戶i對用戶k的影響力可能與用戶k對用戶i的影響力不同.個人影響力大的用戶更容易影響其他用戶.將用戶的個人影響力與用戶之間的影響力相結合,得到使用社交網絡結構信息計算的非對稱的用戶i與用戶k之間的影響力:

(4)

3.3.3 計算綜合的用戶之間的影響力

把使用用戶歷史評分信息計算的用戶之間的影響力sim(i,k)和使用社交網絡結構信息計算的用戶之間的影響力inf(i,k)相結合,得到綜合的用戶i對k的影響力:

(5)

3.4 融合社區結構和用戶影響力的推薦算法

本文在Ma等人[15]提出的SoReg的基礎上提出一種融合社區結構和社交影響力的矩陣分解推薦算法SoInf,利用用戶之間的影響力信息和用戶評分信息進行推薦,其模型如圖1所示.

圖1 SoInf模型圖Fig.1 Graphical model of SoInf

我們使用用戶在社區中的間接社交關系來增強我們的模型,根據社區內其他用戶和用戶好友的偏好來獲得用戶的偏好信息.與SoReg中用戶ui只受到用戶好友的影響不同,在SoInf中,用戶ui的隱式特征向量受到用戶的好友Ni和其所屬社區gi中其他用戶的影響.在SoReg中,用戶與好友之間的相互影響關系受到通過用戶歷史評分信息計算的相似度的影響.而在SoInf中,同時使用用戶評分信息和社交網絡結構信息來計算用戶之間的影響力f(i,k),并融合用戶之間的影響力和結合社區信息計算的用戶個人影響力.用戶ui的隱式特征向量Ui和用戶uk的隱式特征Uk受到用戶之間的影響力f(i,k)的約束:

(6)

假設Ui，Vj先驗概率服從高斯分布且相互獨立,則有:

(7)

(8)

給定用戶的同社區內的其他用戶和用戶的直接鄰居的隱式特征,在用戶隱式特征空間執行優化任務,得到用戶隱式特征的條件分布:

(9)

預測評分值的條件分布如下:

(10)

利用貝葉斯規則,特征矩陣U和V的后驗分布可通過如下方法計算:

(11)

對后驗分布取對數,可得:

(12)

其中Con是常量.最大化上述對數后驗概率,等價于最小化如下目標函數:

(13)

(14)

(15)

本文給出我們的算法,如下所示:

Algorithm1:learningSoInfInput:RatingsintrainingsetR,usersocialmatrixT,Learningrateγ,α,λU,λVOutput:userlatentprofilematrixUanditemlatentprofilematrixV1 InitializeUandV;2 repeat3 forrij∈Rdo4 updateUi←Ui—α?E?UibasedonEq.(14);5 updateUj←Uj—α?E?VjbasedonEq.(15);6 untilconvergence;7 returnUandV;

4 復雜性分析

5 實 驗

5.1 數據集

豆瓣1https://www.douban.com是一個中國社交網絡平臺,主要是對圖書、電影和音樂進行評論和推薦.每個人可以根據自己的喜好對圖書、電影和音樂進行評分,評分從1到5.我們使用Zhong等人[32]分享的數據集,僅僅使用其中電影相關的數據,并且移除評分為零的數據.實驗中使用的豆瓣數據集共包含6164個至少評分過一次的用戶,28781部電影,715204條評分和8728條好友關系.

CiaoDVD是Guo等人[33]爬取的一個英國DVD社交網站Ciao2http://dvd.ciao.co.uk的公開數據集.評分從1到5,共包含17615個用戶,16121部電影,72665條評分和22484條信任關系.

5.2 對比算法

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

PMF[9]:僅僅使用了評分信息,沒有加入用戶的社交關系信息.

SoRec[8]:屬于同步分解評分矩陣和社交關系矩陣的方法,同時將其分解為用戶特征矩陣與社交特征矩陣.

TrustMF[10]:屬于同步分解評分矩陣和社交關系矩陣的方法,將每一個用戶映射為信任者特征向量和被信任者特征向量.

SocialMF[14]:屬于利用直接社交關系對用戶特征矩陣進行優化的方法,使用用戶好友信息和信任傳播機制來增強推薦效果.

SoReg[15]:屬于利用直接社交關系對用戶特征矩陣進行優化的方法,通過加入社交正則項使得用戶的偏好與其好友的偏好相似.

MFC[21]:屬于利用間接社交關系對用戶特征矩陣優化的方法.在矩陣分解模型中引入了重疊社區發現算法,區分用戶所在社區不同的差異.

為了說明我們的SoInf模型的效果,我們分別進行以下三組實驗比較:

1)使用社區中間接社交關系,對推薦的增強效果.把我們的僅僅添加社區信息的模型命名為SoInfc.將它與上述其他算法進行比較.

2)同時使用用戶評分信息和社交網絡結構信息來計算用戶之間的影響力,對推薦的增強效果.把在SoInfc模型基礎上,同時使用用戶評分信息和社交網絡結構信息來計算用戶之間的影響力的模型命名為SoInfs.將它和SoInfc以及其他算法進行比較.

3)結合用戶個人影響力,對推薦的增強效果.在SoInfs模型基礎上,結合用戶個人影響力來計算用戶之間的影響力的模型就是本文提出的SoInf.將它與SoInfs以及其他算法相比較.

5.3 評價指標

本文的實驗采用五重交叉驗證方法,即隨機把數據集分成5份,每次選擇其中的4份作為訓練集,選擇剩下的1份作為測試集,對5次的評估結果取平均值得到最終的評估結果.為了分析本文提出的算法對推薦結果的精確度,采用平均絕對誤差(Mean Absolute Error,MAE)和均方根絕對誤差(Root Mean Square Error,RMSE)作為實驗結果的評估方法.MAE值和RMSE值越小表示預測評分和真實評分的差距越小,推薦結果越準確.

(16)

(17)

5.4 參數選擇和分析

實驗參數的設置影響著算法的最終準確度.根據文獻[8,9,10,14,15,21]中的參數設定規則,將所有算法的隱特征向量個數l設為10,迭代計算的步長(學習率)γ設為0.0001,迭代的終止條件設為前后兩次迭代誤差小于0.00001,將λu和λv設置為0.001.在我們的算法中,正則項系數α表示用戶社交網絡社區信息以及用戶之間的影響力信息在矩陣分解模型中參與的比重,將α的值分別取值為{0.01,0.1,1,10,50,100}進行實驗.記錄我們的算法SoInf的推薦結果的MAE值和RMSE值隨不同α值的變化情況,如圖2和圖3所示.

圖2 SoInf算法的 MAE值隨α值的變化Fig.2 MAE of the SoInf algorithm varies with parameter α

由圖2和圖3可知,對于Douban數據集,當α為10時MAE和RMSE最小, 也就是推薦準確度最高, 所以在我們的算法中設α為10.而對于ciaoDVD數據集,當α為50時MAE和RMSE最小.依據文獻[8,9,10,14,15,21]對于其他算法的參數進行設定,見表1.

圖3 SoInf算法的RMSE值隨α值的變化Fig.3 RMSE of the SoInf algorithm varies with parameter α

表1 不同社交推薦方法參數設定
Table 1 Parameters for different social recommendation methods

方法參數設定PMFλu=0.001,λv=0.001,SoRecλu=0.001,λv=0.001,α=1TrustMFλu=0.001,λv=0.001,α=1SoRegλu=0.001,λv=0.001,α=0.001SocialMFλu=0.001,λv=0.001,α=1MFCλu=0.001,λv=0.001,α=0.001SoInfλu=0.001,λv=0.001,α=10

5.5 實驗結果比較和分析

在為每個算法選擇最優的參數以后,通過實驗我們可以比較各個矩陣分解的預測效果.表2里顯示的是在Douban和CiaoDVD數據集中各個算法的MAE和RMSE.在圖4和圖5中分別顯示了各個算法的MAE和RMSE的對比.

表2 SoInf算法與其他推薦算法的實驗結果對比
Table 2 Comparison ofMAEandRSMEfor SoInf algorithm and other recommendation algorithms

算法DoubanCiaoDVDMAERMSEMAERMSEPMF0.63970.83170.79541.0930SoRec0.60350.76700.76341.0311TrustMF0.60120.76170.76311.0303SocialMF0.61490.77570.76381.0337SoReg0.60360.76180.76321.0321MFC0.59960.76080.75941.0299SoInfc0.59930.75990.75791.0295SoInfs0.59840.75960.75591.0286SoInf0.59810.75950.75531.0268

通過觀察和分析,我們可以得到以下幾個結論:

1)使用社區中間接社交關系,對推薦效果的分析.相對于利用直接社交信息進行用戶特征矩陣優化的模型(SoReg,SocialMF)和同步分解評分矩陣和社交關系矩陣的模型(SoRec,TrsutMF),基于社區的社交推薦模型(MFC,SoInfc,SoInfs,SoInf)準確度更高.這表明社區信息的引入可以緩解用戶好友稀疏的問題,提升推薦效果.

圖4 各個算法的MAE指標比較Fig.4 Comparison of MAE for different algorithms

2)同時使用用戶評分信息和社交網絡結構信息來計算用戶之間的影響力,對推薦效果的分析.和僅僅使用用戶評分信息來計算用戶之間的影響力的SoInfc算法相比較,同時使用評分信息和社交網絡結構信息來計算用戶之間的影響力的SoInfs準確度更高,說明同時使用評分信息和社交網絡結構信息來計算用戶之間的影響力可以更加準確地刻畫用戶間的相互影響,更加有效地使用用戶評分信息與社交信息.

3)結合用戶個人影響力來計算有差異的用戶之間的影響力效果分析.結合用戶個人影響力來計算非對稱的用戶之間的影響力的模型SoInf相比沒有結合用戶的個人影響力的SoInfs推薦準確度更高.說明使用結合用戶個人影響力得到的非對稱的用戶之間的影響力,可以獲得更好的推薦結果.

與PMF相比較,我們提出的推薦模型SoInf在Douban數據集上對于MAE和RMSE分別提升了6.50%和8.68%,在ciaoDVD上數據集分別提升了5.04%和6.06%.對比其他算法,我們的模型SoInf在準確度方面有一定的提升.與MFC通過重疊社區來增強基于社區的推薦的效果不同,我們考慮通過更精確地刻畫用戶之間的關系,得到用戶之間的影響力來對基于社區的推薦進行增強.SoInf與MFC相比準確度更高,說明將社區結構和社交影響力相融合到矩陣分解模型中,同時使用用戶的評分信息和社交網絡結構信息,可以更加充分合理的利用推薦數據,達到更好的推薦效果.

圖5 各個算法的RMSE指標比較Fig.5 Comparison of RMSE for different algorithms

6 總 結

本文提出了一種融合社區結構和社交影響力的矩陣分解推薦算法SoInf.為了減少好友的稀疏,我們采用間接社交關系來代替直接社交關系.進行社區發現,然后結合社區信息進行用戶個人影響力計算.考慮社區內其他用戶對用戶的影響,來提高推薦的準確度.使用社區內用戶之間的影響力和用戶的個人影響力,得到非對稱的用戶之間的影響力.通過在Douban和ciaoDVD數據集上的實驗結果表明,算法在推薦準確度上比一些已有的基于矩陣分解的算法更好.未來,我們將研究使用社交影響力和評分信息來構建用戶畫像,使用用戶畫像來提升推薦效果.