信任傳遞的矩陣分解推薦算法

楊　強(qiáng)，楊　有，余　平

(重慶師范大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院， 重慶　401331)

?

信任傳遞的矩陣分解推薦算法

楊強(qiáng)，楊有，余平

(重慶師范大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院， 重慶401331)

[摘要]針對協(xié)同過濾推薦系統(tǒng)中數(shù)據(jù)稀疏性導(dǎo)致推薦準(zhǔn)確性低下問題，提出信任傳遞的矩陣分解推薦算法.該算法利用用戶社交網(wǎng)絡(luò)的直接信任關(guān)系，基于信任傳遞思想，預(yù)測用戶在社交網(wǎng)絡(luò)中的間接信任關(guān)系，以解決社交網(wǎng)絡(luò)信任關(guān)系的稀疏性問題.該算法使用填充后的社交網(wǎng)絡(luò)信任數(shù)據(jù)，預(yù)測填充用戶評分?jǐn)?shù)據(jù)，以解決用戶評分?jǐn)?shù)據(jù)的稀疏性問題；將處理后的用戶評分?jǐn)?shù)據(jù)在基于正則化迭代最小二乘方法推薦系統(tǒng)中進(jìn)行應(yīng)用，取得良好效果.實(shí)驗(yàn)結(jié)果表明：使用Epinions數(shù)據(jù)集，相比傳統(tǒng)的矩陣分解算法，該算法的平均絕對誤差下降了10.77﹪.

[關(guān)鍵詞]推薦系統(tǒng); 信任傳遞; 矩陣分解

推薦系統(tǒng)是一個非常有用的工具，它不僅能夠幫助用戶找到自己可能感興趣的信息[1]，還能讓信息展現(xiàn)在需要它的用戶面前.在電子商務(wù)領(lǐng)域，推薦系統(tǒng)被廣泛使用.例如，國外的Amazon和Last.fm[2]. 然而，推薦系統(tǒng)仍然存在許多問題，如數(shù)據(jù)稀疏性和冷啟動.針對數(shù)據(jù)稀疏性問題，很多研究人員對此進(jìn)行了深入的探討[3-9].但是，以上研究都只使用了用戶評分?jǐn)?shù)據(jù)，僅僅使用用戶評分?jǐn)?shù)據(jù)的推薦系統(tǒng)不能提供現(xiàn)實(shí)的輸出[10].

推薦系統(tǒng)中使用用戶的社交網(wǎng)絡(luò)關(guān)系，不僅可以提高推薦系統(tǒng)的準(zhǔn)確性[11-13]，緩解數(shù)據(jù)稀疏性問題，而且還可以一定程度上解決冷啟動問題.

在上述基于社交網(wǎng)絡(luò)的推薦系統(tǒng)中，雖然都可以達(dá)到不錯的推薦準(zhǔn)確性，但他們沒有考慮用戶之間的信任傳遞.在用戶的信任數(shù)據(jù)中也存在數(shù)據(jù)稀疏性問題，如果僅憑用戶的少量直接信任關(guān)系進(jìn)行預(yù)測評分，容易導(dǎo)致推薦的準(zhǔn)確性不高.

針對用戶評分?jǐn)?shù)據(jù)和社交網(wǎng)絡(luò)信任數(shù)據(jù)稀疏性問題，提出基于信任傳遞的矩陣分解推薦算法(Matrix Factorization Recommender Algorithm Using Trust Propagation，TPMF).實(shí)驗(yàn)表明，TPMF算法比傳統(tǒng)的矩陣分解算法和文獻(xiàn)[14]的推薦算法具有更好的預(yù)測效果.

1問題定義

在推薦系統(tǒng)中，我們有用戶集合U={u1,u2,…,unu}和項(xiàng)目集合I={i1,i2,…,inm}.R={ri,j}nu×nm表示用戶評分矩陣，每個元素ri,j表示用戶i對電影j的評分，評分值為整數(shù)1到5，評分越高代表用戶越喜歡.評分為1表示不喜歡，評分5表示非常喜歡.nu表示用戶數(shù)量，nm表示電影數(shù)量.T= {ti,j}nu×nu表示用戶信任矩陣，每個元素ti,j表示用戶i對用戶j的信任度.信任度為0到1之間的數(shù).數(shù)值越大，信任程度越高.

推薦系統(tǒng)的任務(wù)是：給出一個用戶u∈U和項(xiàng)目i∈I，在用戶評分矩陣中，ru,i是未知的.然后使用R和T來預(yù)測用戶u對項(xiàng)目i的評分.

在用戶評分矩陣R中，每個用戶和項(xiàng)目都有一個特征矩陣，用戶對項(xiàng)目的評分就是用戶和項(xiàng)目的特征矩陣的內(nèi)積.令U=[ui]表示用戶特征矩陣.其中，ui∈Rnf,i=1,…,nu，表示矩陣U的第i列.令M=[mj]表示項(xiàng)目特征矩陣.其中，mj∈Rnf,j=1,…,nm，表示矩陣M的第j列.nf表示特征空間的維度.ui和mj的計(jì)算如(1)式和(2)式[7].

(1)

(2)

2信任傳遞的矩陣分解推薦算法

傳統(tǒng)的矩陣分解算法只使用了用戶的評分?jǐn)?shù)據(jù)，沒有考慮社交網(wǎng)絡(luò)的社會性因素，可能會導(dǎo)致推薦系統(tǒng)的推薦精度偏低.本文算法結(jié)合了社交網(wǎng)絡(luò)數(shù)據(jù)，利用信任傳遞思想.

2.1　社交網(wǎng)絡(luò)信任矩陣

信任是一種主觀概率，即對于一個給定的活動，一個用戶依賴于另一個用戶執(zhí)行的概率.本文采用的社交網(wǎng)絡(luò)數(shù)據(jù)是用戶之間的信任關(guān)系.用戶之間的信任關(guān)系形成一個信任矩陣T={ti,j}nu×nu.

其中，dout(i)表示用戶i的信任出度.每個元素ti,j表示用戶i對用戶j的信任度，大小由用戶i的信任出度決定.信任度為0到1之間的數(shù)，數(shù)值越大，信任程度越高.E為用戶之間的信任度集合.通常情況下，信任矩陣是非對稱的.

2.2　更新社交網(wǎng)絡(luò)矩陣

信任傳遞的思想類似于相似性傳播.相似性傳播的思想是：用戶在找到自己相似的用戶之后，認(rèn)為相似用戶的相似用戶也是自己相似的用戶.文獻(xiàn)[15]認(rèn)為：用戶A信任用戶B，用戶B信任用戶C，一定程度上可以推出，用戶A信任用戶C.由于社交網(wǎng)絡(luò)信任矩陣存在數(shù)據(jù)稀疏性問題，如果僅僅使用直接的信任關(guān)系容易導(dǎo)致推薦系統(tǒng)的準(zhǔn)確性不高.為了緩解社交網(wǎng)絡(luò)信任矩陣的稀疏性問題，更好地使用用戶的信任數(shù)據(jù)，利用信任傳遞的思想，獲取更多間接的信任鄰居很有必要.

在本文中，我們認(rèn)為ti,j的大小等于用戶i對用戶j的直接信任程度與用戶i對用戶j的間接信任程度之和:

其中，N為社交網(wǎng)絡(luò)中用戶的總數(shù)量.

采用信任傳遞思想更新信任矩陣T后，矩陣T的稀疏度與更新前的稀疏度對比如表1所示.其中，稀疏度為矩陣中未知元素的個數(shù)與所有元素個數(shù)的比值.

表1　矩陣T和矩陣R在更新前與更新后的稀疏度對比

2.3　使用信任度初步預(yù)測用戶評分

在用戶評分矩陣R中，由于已知的用戶評分很少，所以R是一個非常稀疏的矩陣.如果對一個非常稀疏的矩陣進(jìn)行分解，再用分解得到的用戶特征矩陣和項(xiàng)目特征矩陣來計(jì)算預(yù)測評分，容易導(dǎo)致推薦精度不高.

為了緩解評分矩陣的稀疏性，提高推薦的準(zhǔn)確性，我們借助于社交網(wǎng)絡(luò)信任矩陣對用戶評分矩陣R中的缺失值進(jìn)行初步預(yù)測，把用戶之間的信任度作為權(quán)值，然后用信任的用戶對項(xiàng)目的評分來預(yù)測用戶對此項(xiàng)目的評分，從而一定程度上緩解數(shù)據(jù)的稀疏性，如表1所示.預(yù)測評分公式[16]如下：

其中，tu,v>threshold.threshold是信任度閾值，表示大于此閾值的信任用戶才用來預(yù)測評分，小于或等于此閾值的信任度可忽略不計(jì).tu,v表示用戶u對用戶v的信任度.rv,i表示用戶v對項(xiàng)目i的實(shí)際評分.Pu,i表示用戶u對項(xiàng)目i的預(yù)測評分，V為用戶u的信任集合.

2.4　TPMF算法

TPMF算法的思想是，首先將社交網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)換成信任矩陣T，采用信任傳遞思想更新信任矩陣T.再根據(jù)信任矩陣T對用戶評分矩陣R中的缺失值進(jìn)行預(yù)測，使得用戶評分矩陣R的稀疏性得到一定程度的緩解.然后再對矩陣R進(jìn)行潛在因子分解，從而根據(jù)公式(1)和公式(2)計(jì)算出用戶特征矩陣U和項(xiàng)目特征矩陣M.最后，根據(jù)矩陣U和矩陣M計(jì)算預(yù)測評分.算法步驟如下：

Step1 讀取用戶評分訓(xùn)練數(shù)據(jù)和社交網(wǎng)絡(luò)信任數(shù)據(jù)，得到用戶評分矩陣R和信任矩陣T.

Step2 使用信任傳播原理，對信任矩陣T進(jìn)行預(yù)測填充.

Step3 使用填充后的信任矩陣對用戶評分矩陣進(jìn)行預(yù)測填充.

Step4 使用ALS-WR方法進(jìn)行迭代計(jì)算用戶特征矩陣U和項(xiàng)目特征矩陣M[7].

Step5 讀取測試數(shù)據(jù)集，根據(jù)用戶特征矩陣U和項(xiàng)目特征矩陣M來預(yù)測試數(shù)據(jù)集中用戶對電影的評分，計(jì)算MAE.

算法的工作流程示意圖如圖1.圖1中粗斜體部分為本文主要工作.

圖1　TPMF的工作流程示意圖

3實(shí)驗(yàn)

實(shí)驗(yàn)中包含了本文算法與傳統(tǒng)的矩陣分解算法(MatrixFactorization，MF)和社會矩陣分解算法[14](SocialMatrixFactorization，SMF)的實(shí)驗(yàn)結(jié)果對比分析.同時，因?yàn)楸疚乃惴ㄉ婕岸鄠€參數(shù)，所以實(shí)驗(yàn)中還包含各個參數(shù)在不同取值下的實(shí)驗(yàn)結(jié)果對比分析.

3.1　評價標(biāo)準(zhǔn)

平均絕對誤差(MeanAbsoluteError，MAE)是一種常用的統(tǒng)計(jì)精度測試方法.計(jì)算用戶實(shí)際評分和預(yù)測評分之間的MAE測量方式被廣泛運(yùn)用[17].ri表示實(shí)際評分.pi表示預(yù)測評分.假設(shè)測試數(shù)據(jù)集中有N個用戶的評分，我們首先計(jì)算測試集中每個評分與預(yù)測評分的差值，再對這些差值的絕對值求和，最后求得平均絕對誤差：

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

實(shí)驗(yàn)采用的是Epinions數(shù)據(jù)集(http://www.trustlet.org/wiki/Downloaded_Epinions_dataset).數(shù)據(jù)集包含社交網(wǎng)絡(luò)數(shù)據(jù)和用戶評分?jǐn)?shù)據(jù).社交網(wǎng)絡(luò)數(shù)據(jù)包含487 183條記錄，每條記錄包括source_user_id、target_user_id和trust_statement_value、trust_statement_value.值全部為1，表示ID為source_user_id的用戶對ID為target_user_id的用戶存在信任關(guān)系.用戶評分?jǐn)?shù)據(jù)包含664 824條記錄，每條記錄包括user_id、item_id和rating_value.表示ID為user_id的用戶對ID為item_id的電影評分值為rating_value.rating_value值的范圍是1~5.

由于數(shù)據(jù)量比較大，本實(shí)驗(yàn)采用的數(shù)據(jù)是用戶ID在2 000以內(nèi)(包括2 000)并且項(xiàng)目ID在4 000以內(nèi)(包括4 000)的社交網(wǎng)絡(luò)數(shù)據(jù)和評分?jǐn)?shù)據(jù).其中，用戶評分?jǐn)?shù)據(jù)的80﹪作為訓(xùn)練數(shù)據(jù)，20﹪作為測試數(shù)據(jù).社交網(wǎng)絡(luò)數(shù)據(jù)的100﹪作為訓(xùn)練數(shù)據(jù).

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

本實(shí)驗(yàn)采用聯(lián)想筆記本，在Matlab7.11.0平臺下運(yùn)行.由于只有TPMF算法才用到參數(shù)threshold,經(jīng)過多次實(shí)驗(yàn)，當(dāng)nf=2和λ=0.05時可以取得較好的效果.所以，在第一組實(shí)驗(yàn)中假設(shè)nf=2和λ=0.05，然后考察不同的threshold取值對實(shí)驗(yàn)的影響情況.實(shí)驗(yàn)結(jié)果如圖2所示.實(shí)驗(yàn)結(jié)果表明，隨著threshold值的增大，MAE逐漸增大，直到接近平穩(wěn).這表明隨著閾值的增大，只有信任度大于閾值的才加入預(yù)測.也就是說，當(dāng)閾值增大時，可用的信任度變少，從而導(dǎo)致能夠進(jìn)行初步預(yù)測的評分變少，不能夠很好緩解評分矩陣稀疏問題.這使得推薦準(zhǔn)確性逐漸變低直至平穩(wěn)，最后接近于沒有對用戶評分矩陣預(yù)測的情況.

圖2　threshold取值不同對TPMF算法MAE的影響

由于threshold決定了此信任度是否要加入計(jì)算，當(dāng)threshold值較小時引入此信任度反而會增大預(yù)測結(jié)果的誤差.所以，當(dāng)threshold比較小時對其忽略不計(jì).多次實(shí)驗(yàn)表明，當(dāng)threshold>0.1時可以使推薦算法取得最佳預(yù)測效果.因此在第二組實(shí)驗(yàn)中，本文考察了當(dāng)threshold>0.1、nf=2時，MF、SMF和TPMF 3種算法在不同λ取值下MAE的變化情況.實(shí)驗(yàn)結(jié)果如圖3.實(shí)驗(yàn)結(jié)果表明，當(dāng)λ取值較小時，相比MF和SMF算法，TPMF算法的MAE明顯更小.也就是說，當(dāng)λ取值較小時，TPMF算法有更高的推薦準(zhǔn)確度.

圖3　MF、SMF與TPMF在不同λ取值下的MAE對比

在第3組實(shí)驗(yàn)中，本文考察了threshold>0.1、λ=0.05時，MF、SMF和TPMF3種算法在不同nf取值下MAE的變化情況.實(shí)驗(yàn)結(jié)果如圖4.實(shí)驗(yàn)結(jié)果表明，MF和SMF算法的MAE隨著參數(shù)nf的增加先增大，然后接近平穩(wěn).也就是隨著特征數(shù)的增加，推薦的準(zhǔn)確性呈下降趨勢，直至接近平穩(wěn).相比MF和SMF算法，TPMF的MAE比較穩(wěn)定，而且明顯比MF的MAE小.這表明TPMF比MF具有更好的預(yù)測效果.

圖4　MF、SMF與TPMF在不同nf取值下的MAE對比

參數(shù)λ和nf的不同取值影響著MF、SMF和TPMF算法的MAE.在第2組實(shí)驗(yàn)中，實(shí)驗(yàn)取了9個不同的參數(shù)λ來測試對MAE的影響.在第3組實(shí)驗(yàn)中，實(shí)驗(yàn)取5個不同的參數(shù)nf.通過這兩組實(shí)驗(yàn)，實(shí)驗(yàn)中共包含兩種算法MF和TPMF的14個MAE.MF算法的這14個MAE總和為13.983 6，平均值為0.998 8.SMF算法的這14個MAE總和為15.016 1，平均值為1.072 6.TPMF算法的這14個MAE總和為12.476 7，平均值為0.891 2.相比MF算法，TPMF算法的MAE降低了10.77﹪，如表2所示.

表2　MF、SMF與TPMF算法的MAE綜合比較

4結(jié)語

本文提出信任傳遞的矩陣分解推薦算法，采用信任傳遞思想，預(yù)測填充社交信任關(guān)系矩陣，利用信任關(guān)系數(shù)據(jù)預(yù)測填充用戶評分，緩解了信任關(guān)系數(shù)據(jù)和用戶評分?jǐn)?shù)據(jù)的稀疏性，并將處理后的數(shù)據(jù)用于ALS-WR推薦系統(tǒng)中，預(yù)測的平均絕對誤差下降了10.77﹪，明顯提高了推薦系統(tǒng)的準(zhǔn)確性.

[參考文獻(xiàn)]

[1]MoghaddamMG,ElahianA.Anoveltemporaltrust-basedrecommendersystem[C]. 2014 22ndIranianConferenceonElectricalEngineering(ICEE).IEEE, 2014: 1142-1146.

[2]ShambourQ,LuJ.AneffectiverecommendersystembyunifyinguseranditemtrustinformationforB2Bapplications[J].JournalofComputerandSystemSciences,2015.

[3]ChujaiP,SuksawatchonU,RasmequanS,etal.Imputingmissingvaluesincollaborativefilteringusingpatternfrequentitemsets[C].ElectricalEngineeringCongress(iEECON)2014InternationalIEEE,2014:1-4.

[4]趙琴琴,魯凱,王斌.SPCF:一種基于內(nèi)存的傳播式協(xié)同過濾推薦算法[J]. 計(jì)算機(jī)學(xué)報(bào),2013(3):671-676.

[5]LopesARS,PrudencioRBC,BezerraBLD.Acolla-borativefilteringframeworkbasedonlocalandglobalsimilaritieswithsimilaritytie-breakingcriteria[C].2014InternationalJointConferenceonNeuralNetworks(IJCNN).IEEE, 2014: 2887-2893.

[6]JiH,ChenX,HeM,etal.Improvedrecommendationsystemviapropagatedneighborhoodsbasedcollaborativefiltering[C].ServiceOperationsandLogistics,andInformatics(SOLI), 2014IEEEInternationalConferenceonIEEE, 2014: 119-122.

[7]ZhouY,WilkinsonD,SchreiberR,etal.Large-scaleparallelcollaborativefilteringforthenetflixprize[M].AlgorithmicAspectsinInformationandManagement.SpringerBerlinHeidelberg, 2008: 337-348.

[8]SharifiZ,RezghiM,NasiriM.Anewalgorithmforsolvingdatasparsityproblembased-onnonnegativematrixfactorizationinrecommendersystems[C]. 2014 4thInternationaleConferenceonComputerandKnowledgeEngineering(ICCKE).IEEE, 2014: 56-61.

[9]CaiY,LeungH,LiQ,etal.Typicality-basedcollaborativefilteringrecommendation[J].IEEETransactiononKnowledgeandDataEngineering, 2014, 26(3): 766-779.

[10]ChenC,ZengJ,ZhengX,etal.Recommendersystembasedonsocialtrustrelationships[C].2013IEEE10thInternationalConferenceone-BusinessEngineering(ICEBE).IEEE, 2013: 32-37.

[11]OechsleinO,FleischmannM,HessT.AnapplicationofUTAUT2onsocialrecommendersystems:incorporatingsocialinformationforperformanceexpectancy[C].2014 47thHawaiiInternationalConferenceonSystemSciences(HICSS).IEEE,2014:3297-3306.

[12]QianX,FengH,ZhaoG.Personalizedrecommendationcombininguserinterestandsocialcircle[J].IEEETransactionsonKnowledgeandDataEngineering, 2013(26): 1763-1777.

[13]JiangM,CuiP,WangF,etal.Scalablerecommendationwithsocialcontextualinformation[J].IEEETransactionsonKnowledgeandDataEngineering, 2014, 11(26): 2789-2802.

[14]李衛(wèi)平, 楊杰. 基于隨機(jī)梯度矩陣分解的社會網(wǎng)絡(luò)推薦算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2014, 31(6): 1654-1656.

[15]GuoG,ZhangJ,ThalmannD.Mergingtrustincollaborativefilteringtoalleviatedatasparsityandcoldstart[J].Knowledge-BasedSystems,2014,57:57-68.

[16]FaridaniV,JahanMV,JalaliM.Combiningtrustincollaborativefilteringtomitigatedatasparsityandcold-startproblems[C].ComputerandKnowledgeEngineering(ICCKE), 2014 4thInternationaleConferenceonIEEE,2014:233-238.

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

(責(zé)任編輯穆剛)

Matrix factorization recommender algorithm using trust propagation

YANG Qiang, YANG You, YU Ping

(School of Computer and Information Science, Chongqing Normal University, Chongqing 401331, China)

Abstract：Due to the data sparsity problems which lead to inaccuracy of recommendation in collaborative filtering recommender systems, a matrix factorization algorithm was proposed, which uses the trust propagation. The proposed method used the direct trust relationship between users of social networks, based on the idea of trust propagation, predicted indirect trust relationship in social networks to solve the problem of sparse trust relations; the algorithm used social network trust data after filling for predicting and filling the user rating data to solve the problem of the sparsity of user rating data; It achieved good results in the recommender system based on the alternating-least-squares with weighted-λ-regularization method using user rating data that predicted and filled. The experimental results show that: the average absolute error of this algorithm decreases 10.77﹪ on the Epinions data sets, compared with the traditional algorithms.

Key words：recommender systems; trust propagation; matrix factorization

[中圖分類號]TP391.3

[文獻(xiàn)標(biāo)志碼]A

[文章編號]1673-8004(2015)05-0125-05

[作者簡介]楊強(qiáng)(1988—)，男，江西撫州人，碩士研究生，主要從事推薦系統(tǒng)方面的研究.

[基金項(xiàng)目]重慶市教委科技項(xiàng)目(KJ130646).

[收稿日期]2015-04-01