一種基于信任機制的概率矩陣分解協(xié)同過濾推薦算法

王建芳，苗艷玲，韓鵬飛，劉永利

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河南 焦作 454000)

1 引 言

推薦系統(tǒng)RS(Recommender Systems)為特定用戶推薦其可能感興趣的項目(例如書籍、新聞、美食和圖片等).目前，推薦系統(tǒng)的研究方法主要是根據(jù)用戶提供的反饋信息進行預(yù)測推薦[1].協(xié)同過濾CF(Collaborative Filtering)是該領(lǐng)域最常用的方法之一，核心思想是通過相似用戶或相似項目的評分信息來預(yù)測用戶偏好[2].協(xié)同過濾算法通常分為兩類：1)基于內(nèi)存的方法，主要包括基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾；2)基于模型的方法，主要是基于潛在因子模型，也稱矩陣分解模型，其基本思想是通過訓(xùn)練集的訓(xùn)練以構(gòu)建相關(guān)模型，然后使用該模型向用戶推薦項目[3].

盡管基于潛在因子模型的推薦系統(tǒng)取得了較好效果，但在實際應(yīng)用中仍遇到一些問題[4]，比如數(shù)據(jù)稀疏性和冷啟動問題.由于用戶有選擇地對部分項目評分，導(dǎo)致用戶項目評分矩陣數(shù)據(jù)稀疏，稀疏性使得模型很難從特征值中學(xué)習(xí)到用戶偏好[5].有學(xué)者對社會科學(xué)中的同伴選擇和社會影響進行深入研究[6，7]，發(fā)現(xiàn)用戶往往與具有相似愛好的用戶保持較緊密的聯(lián)系，信任關(guān)系恰恰能反映用戶之間的緊密程度，能進一步增強同一社交圈成員的相似性.近年來利用用戶之間的信任度提出的相關(guān)推薦算法，雖然提高了推薦質(zhì)量和覆蓋率，但是卻是以犧牲精確度為代價的，而且由于社交網(wǎng)絡(luò)中的信任稀疏難獲取，造成推薦精度不高.

基于此，本文提出了一種基于信任機制的概率矩陣分解協(xié)同過濾推薦算法TM-PMF (Probabilistic Matrix Factorization Algorithm of Collaborative Filtering Based on Trust Mechanism)，該方法根據(jù)每個用戶在信任網(wǎng)絡(luò)中的節(jié)點信息，計算其信任值，從而構(gòu)建用戶的信任網(wǎng)絡(luò)，最后基于用戶評分矩陣和信任矩陣建立提出的TM-PMF算法模型.

2 相關(guān)工作

傳統(tǒng)的矩陣分解模型有奇異值分解SVD(Sigular Value Decomposition)、概率矩陣分解PMF(Probabilistic Matrix Factorization)和非負(fù)矩陣分解模型NMF(Non-negative Matrix Factorization)等.文獻[8]提出了概率矩陣分解模型，該模型從概率生成過程角度描述矩陣分解過程，有效緩解了數(shù)據(jù)稀疏性問題；文獻[9]提出了基于鄰域相似性的矩陣分解模型，該模型考慮了用戶興趣相似度，進一步挖掘評分矩陣的有效信息，提高推薦精度.近年來，隨著使用社交平臺和社交網(wǎng)絡(luò)的用戶數(shù)量增多，依賴性增強，社交信息為協(xié)同過濾算法帶來了新的數(shù)據(jù)源[10]，如好友推薦和信任用戶推薦均有效促進了用戶的消費行為，因為在現(xiàn)實生活中相對于品牌、價格和銷量等參考標(biāo)準(zhǔn)，用戶更傾向于信任好友的推薦.文獻[11]顯示相對于系統(tǒng)給出的推薦，人們更喜歡來自友人的推薦，在線調(diào)查結(jié)果還顯示，76%的人們對其友人的在線評論：可信(13%)和有點可信(63%).鑒于此，大量研究人員開始運用社交信息來改進推薦算法.

文獻[12]給出了信任在推薦系統(tǒng)中的定義，即一個用戶對另一個用戶提供有價值評分的信賴程度.文獻[13]提出將社會信任融入推薦算法，來緩解數(shù)據(jù)稀疏性問題.文獻[14]提出基于用戶之間的距離對其信任值進行度量，根據(jù)信任關(guān)系進行評分預(yù)測.文獻[15]將社交信任信息融合到基于模型的協(xié)同過濾算法中.文獻[16]則提出了基于信任傳播的概率矩陣分解，該方法將信任傳播機制與PMF算法融合，使用直連信任用戶和間接信任用戶的信息進行推薦.但是該方法存在不足，其使用信任網(wǎng)絡(luò)預(yù)測用戶的潛在特征向量，然后聯(lián)合項目潛在特征向量進行評分預(yù)測，使得該算法的結(jié)構(gòu)計算復(fù)雜度較高，而且該算法使用的信任矩陣是二值矩陣，信任值只有0或1，忽略了用戶對于不同信任用戶的信任度是有差別的.

由此可見，基于信任的推薦算法能夠有效地緩解冷啟動和數(shù)據(jù)稀疏問題，但是其本身也存在缺點，如何更好地計算信任值，并將其融入推薦算法是接下來本文所研究的重點.

3 問題定義

在推薦系統(tǒng)中包含有一組N個用戶的用戶集U={u1，u2…uN}和M個項目集合I={i1，i2…iM}，用戶對項目的評分?jǐn)?shù)據(jù)用矩陣R=[Ru，i]N×M表示，Ru，i表示用戶u對項目i的評分，評分值一般是[1，5]中整數(shù)，數(shù)值越大表示用戶越喜歡該項目.本文在不失一般性的基礎(chǔ)上，通過歸一化方法將評分1-5映射到[0，1]范圍內(nèi).

在評分網(wǎng)絡(luò)中，每個用戶u有一組直接鄰居用戶集Nu，通常用戶之間的信任矩陣是一個二值矩陣T=[Tu，v]N×N，tu，v表示用戶u對用戶v的信任值，0表示不信任，1表示信任.

4 概率矩陣分解模型

(1)

其中N(x|μ，σ2)表示x服從均值為μ，方差為σ2的高斯分布；Ii，j是指示函數(shù)，Ii，j等于1說明用戶i已對項目j評分，否則為0；假設(shè)用戶和項目的特征向量矩陣都服從均值為0的高斯分布，如式(2)所示.

(2)

由貝葉斯公式推導(dǎo)可知用戶和項目特征向量的后驗分布，如式(3)所示.

(3)

經(jīng)過推導(dǎo)并進行整理得到最終的目標(biāo)函數(shù)，如式(4)所示.

(4)

5 TM-PMF算法

基于信任的推薦算法可以有效地緩解冷啟動和數(shù)據(jù)稀疏問題，如何更好地計算信任值，并將其融入推薦算法是研究的重點.本文提出的TM-PMF算法框架如圖1所示.

圖1 TM-PMF算法框架圖Fig.1 Algorithm framework of TM-PMF

5.1 信任值計算

社交網(wǎng)站上的信任信息，大部分是采用二值型的：信任與不信任，但是二值型的信任數(shù)值所表示的信息量不足，無法體現(xiàn)用戶對其信任用戶集中用戶的區(qū)別.例如：假設(shè)用戶U1的信任用戶集Tu包含四個用戶U2、U3、U4和U5，即Tu={U2，U3，U4，U5}，顯然在二值信任矩陣中用戶U1對四個用戶(U2，U3，U4，U5)的信任值相等均為1，然而現(xiàn)實生活中卻不一定，有可能用戶U1更加信任用戶U3，因此根據(jù)信任網(wǎng)絡(luò)數(shù)據(jù)，選擇一種計算方法，使得用戶U1對(U2，U3，U4，U5)的信任可以通過一個數(shù)值加以區(qū)分.如圖2(a)所示為信任網(wǎng)絡(luò)圖，每個用戶是圖中一個節(jié)點，用戶之間的信任值用圖中的邊來表示，一個簡單的信任網(wǎng)絡(luò)圖和信任矩陣如圖2所示.

對于U1來說，其入度(Indegree)為1，出度(Outdegree)為2，因此有用戶i對用戶j的信任值的計算方法如式(5).

(5)

其中Ti是指用戶i的直連信任用戶集合，例如：由圖2可知用戶U1的信任用戶集合Ti={U3，U4}，用戶U3的入度是2，用戶U4的入度是2，所以Trust(U1，U3)=√(2/(2+2))=0.707，根據(jù)此方法重新構(gòu)造信任網(wǎng)絡(luò)，且信任值的取值范圍為[0，1].但該方法的不足之處是如用戶U5的直連信任用戶只有U4，其信任值就為1，這與實際情況不符.因為即使用戶U5只有一個信任用戶U4，U5對U4也不可能100%信任，對于U4的推薦也不可能完全接受.

(a) 用戶之間信任網(wǎng)絡(luò)圖 (b) 用戶之間的二值信任矩陣

圖2 用戶之間的信任機制關(guān)系圖
Fig.2 Trust mechanism of users

同時由Massa和Avesani提出了基于距離的信任值計算，該方法雖然復(fù)雜度較低，但是遺漏了很多可用信息，造成信任的缺失.基于此，本文信任值的計算方法如公式(6)所示.

(6)

該方法根據(jù)用戶在信任網(wǎng)絡(luò)中的節(jié)點位置，從用戶角度出發(fā)，既考慮用戶被其他用戶信任的次數(shù)(入度)，又考慮了用戶信任別人的次數(shù)(出度)，而每個用戶的出度和入度信息在一定程度上反映了該用戶在社交網(wǎng)絡(luò)中的價值，可見，該方法能夠較好地利用用戶之間的信任關(guān)系，避免了基于距離的信任值計算方法常面臨的問題：只要兩個用戶之間的最短距離相等則他們的信任值相等，其信任值的取值范圍是[0，1].

5.2 TM-PMF算法

(7)

將式(7)展開成矩陣相乘形式可知，其實是將信任值作為權(quán)重加在對應(yīng)的直接用戶的潛在特征向量上，具體形式如式(8)所示.

(8)

實際評分與預(yù)測評分的誤差所服從的概率分布如式(9)所示.

(9)

(10)

所以融合信任信息后的用戶的潛在特征向量的概率分布如式(11)所示.

(11)

結(jié)合評分矩陣和信任矩陣的潛在特征向量的后驗概率為：

(12)

則對(12)取對數(shù)，得到的目標(biāo)函數(shù)形式如式(13)所示.

(13)

(14)

(15)

5.3 算法流程

輸入：用戶之間的信任矩陣TNN，用戶項目評分矩陣RNM，用戶潛在特征矩陣UNK，項目潛在特征矩陣VMK，算法最大迭代次數(shù)maxepoch，正則化系數(shù)λ，信任項的系數(shù)λT，學(xué)習(xí)速率α，讀入數(shù)據(jù)的總批次numbatches，以及每批次讀入數(shù)據(jù)的數(shù)量N.

輸出：用戶潛在特征矩陣U和項目潛在特征矩陣V，真實評分與預(yù)測評分的誤差E，以及隨著迭代次數(shù)變化的RMSE.

算法流程：

步驟1.讀入評分矩陣RNM并處理，取任意75%的數(shù)據(jù)作為訓(xùn)練集，剩下的25%作為測試集，用來驗證訓(xùn)練好的模型的魯棒性；

步驟2.讀入信任矩陣TNN，按照5.1提出的信任值計算公式(6)，計算用戶之間的信任值，重新構(gòu)建信任矩陣TNN；

步驟3.使用正態(tài)分布初始化用戶和項目潛在特征矩陣UNK和VMK，for循環(huán)分批讀入作為訓(xùn)練集的評分?jǐn)?shù)據(jù)，將每個用戶Ui的信任用戶特征向量與其信任值加權(quán)存儲；

步驟4.根據(jù)公式(13)，計算目標(biāo)函數(shù)E，然后根據(jù)公式(14)和公式(15)，通過批量梯度法更新變量和訓(xùn)練參數(shù)：

for 迭代次數(shù)=1：maxepoch

for 讀入評分?jǐn)?shù)據(jù)批次=1：numbatches

歸一化評分?jǐn)?shù)據(jù)；

計算預(yù)測評分?jǐn)?shù)據(jù)；

根據(jù)公式(13)計算目標(biāo)函數(shù)E；

根據(jù)公式(14) 公式(15)計算變量的偏導(dǎo)數(shù)；

end

計算訓(xùn)練數(shù)據(jù)的均方根誤差RMSE；

讀入作為測試集的評分?jǐn)?shù)據(jù)，利用訓(xùn)練集已經(jīng)訓(xùn)練好的Ui和Vj，計算測試數(shù)據(jù)的均方根誤差RMSE；

end

步驟5.根據(jù)每次選擇的學(xué)習(xí)速率、正則化系數(shù)和矩陣分解的維度K，將RMSE隨著迭代次數(shù)變化的曲線繪制出來，再根據(jù)曲線調(diào)整以上參數(shù)值，直到RMSE達到最優(yōu)值，從而獲取推薦列表.

算法結(jié)束.

6 實驗分析

實驗假設(shè)：1)不同用戶對同一項目有不同的偏好，且同一用戶對不同項目有不同的偏好；2)用戶會受其信任用戶的影響，從而更加偏向于信任用戶的推薦，即如果用戶U1越信任用戶U2，則這兩者的行為相似度越高.

不失一般性，為了減小算法復(fù)雜度，統(tǒng)一設(shè)置正則化系數(shù)λU=λV=0.001.

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

為了驗證本文提出算法的推薦效果，選擇了3個經(jīng)典的包含信任關(guān)系的數(shù)據(jù)集，分別是Filmtrust[17]數(shù)據(jù)集、Epinions數(shù)據(jù)集和Ciao數(shù)據(jù)集.3個數(shù)據(jù)集詳細信息如表1所示.

6.2 評估標(biāo)準(zhǔn)

為驗證本文所提出算法的推薦質(zhì)量，采用均方根誤差RMSE(Root Mean Square Error)作為度量標(biāo)準(zhǔn)，這是針對評分預(yù)測方向常用的推薦質(zhì)量度量標(biāo)準(zhǔn)之一，RMSE的定義如式(16)所示.

表1 3個不同數(shù)據(jù)集的統(tǒng)計信息表Table 1 General statistics of the Filmtrust， Epinions，and Ciao datasets

(16)

6.3 對比算法

為驗證本文所提算法的有效性，檢驗信任因子對于推薦效果的影響，本部分實驗分為兩個部分，第一部分是對比PMF算法和TM-PMF算法的效果；第二部分是分析參數(shù)λT對推薦質(zhì)量的影響.

1)PMF算法與TM-PMF算法

為了驗證信任因子對推薦質(zhì)量的影響，繪制了PMF算法和TM-PMF算法對應(yīng)的RMSE曲線變化圖.如圖3、圖4和圖5所示.

圖3 Filmtrust數(shù)據(jù)集上RMSE 隨迭代次數(shù)的變化Fig.3 Performance of PMF and TM-PMF in the Filmtrust dataset for RMSE

圖4 Epinions數(shù)據(jù)集上RMSE 隨迭代次數(shù)的變化Fig.4 Performance of PMF and TM-PMF in the Epinions dataset for RMSE

圖5 Ciao數(shù)據(jù)集上RMSE 隨迭代次數(shù)的變化Fig.5 Performance of PMF and TM-PMF in the Ciao dataset for RMSE

一般來說，RMSE的值越小推薦質(zhì)量越好，可以看出，在不同數(shù)據(jù)集上加入信任因子的算法TM-PMF較PMF算法的推薦效果有明顯提升.具體分析，在Filmtrust數(shù)據(jù)集上，如圖3所示，當(dāng)?shù)螖?shù)小于3次，PMF算法和TM-PMF算法隨著迭代次數(shù)增加，RMSE值迅速下降，PMF算法對應(yīng)的RMSE值小于TM-PMF算法的，說明這種情況下PMF算法的推薦效果較好，當(dāng)?shù)螖?shù)大于3次，TM-PMF算法的推薦效果開始優(yōu)于PMF算法，RMSE值仍然迅速下降，而PMF算法對應(yīng)的RMSE值下降速度減緩；當(dāng)?shù)螖?shù)增加到10之后，兩種算法均開始趨于穩(wěn)定，迭代增加到20次以后，RMSE值基本不變；類似在Epinions數(shù)據(jù)集和Ciao數(shù)據(jù)集上，兩種算法的RMSE曲線的收斂趨勢大致相同，但是在Epinions數(shù)據(jù)集上TM-PMF算法的推薦效果更明顯.根據(jù)表1所示，F(xiàn)ilmtrust數(shù)據(jù)集的評分密度是1.13%，Epinions數(shù)據(jù)集的評分密度是0.0097%，Ciao數(shù)據(jù)集的評分密度是0.036%，結(jié)合上圖對比結(jié)果可知，信任因子的加入對于稀疏數(shù)據(jù)集的推薦質(zhì)量影響更大.

2)參數(shù)λT的確定

參數(shù)λT控制信任因子對用戶行為的影響，λT的值越大代表信任因子對用戶的影響越大，越小說明我們的模型越接近概率矩陣分解模型；當(dāng)然λT的值并不是越大越好，λT的值特別大時，將會導(dǎo)致過擬合現(xiàn)象，即特征向量逼近訓(xùn)練階段RMSE值較低的近鄰用戶的特征向量模型.

圖6 不同數(shù)據(jù)集上參數(shù)λT對推薦效果的影響Fig.6 Impact of different values of λT on the performance of prediction in datasets

圖6描述了在不同數(shù)據(jù)集上不同的λT對RMSE值的影響.具體在Filmtrust數(shù)據(jù)集上，當(dāng)λT=0.01時，TM-PMF的推薦效果較好；在Epinions數(shù)據(jù)集上，λT=0.006；在Ciao數(shù)據(jù)集上，λT=0.0001.

7 結(jié)束語

本文提出了一種新穎的TM-PMF算法，該算法融合了用戶的歷史記錄信息和用戶之間的信任關(guān)系，更加真實客觀地為用戶推薦自己喜好的物品.實驗結(jié)果表明本文提出的TM-PMF算法，在3個數(shù)據(jù)稀疏的數(shù)據(jù)集上的推薦結(jié)果精度均有所提高.接下來將結(jié)合動態(tài)數(shù)據(jù)流進一步改進本文提出的算法.