文 凱，朱傳亮

(1.重慶郵電大學 通信新技術(shù)應(yīng)用研究中心，重慶 400065； 2.重慶信科設(shè)計有限公司，重慶 401121)

0 引言

推薦算法主要是幫助用戶從大量的商品中篩選出自己感興趣的商品，目前廣泛使用的推薦方法是協(xié)同過濾方法，該方法基于相似用戶有相似偏好來為用戶作出推薦[1]。然而在真實世界中，由于用戶偏好數(shù)據(jù)的稀疏性，導致協(xié)同過濾方法的推薦準確率不太高，并且對新用戶的推薦也無從下手。隨著社交網(wǎng)絡(luò)的發(fā)展，用戶間的交互越來越多，其中信任網(wǎng)絡(luò)成為了一個重要的研究方面，為了解決數(shù)據(jù)稀疏帶來的問題，許多學者提出了基于用戶間信任的推薦算法[2-3]，這種結(jié)合信任的推薦算法主要考慮的是用戶更喜歡他們的朋友所推薦的商品。同樣地，在真實的社交網(wǎng)絡(luò)中，顯示的信任數(shù)據(jù)也是十分稀疏的，需要對隱式關(guān)系進行挖掘。另外，在一些社交網(wǎng)絡(luò)中，用戶間不僅可以建立信任關(guān)系，還可以建立不信任關(guān)系，例如在Epinions網(wǎng)站中，允許用戶根據(jù)其他用戶的評論對其進行信任或不信任的評價，因此用戶間的不信任關(guān)系也是一個最近值得研究的方面。

本文針對信任關(guān)系稀疏的問題并且考慮到了用戶間的不信任關(guān)系，提出了一種結(jié)合社交網(wǎng)絡(luò)和用戶間興趣相關(guān)性的矩陣分解正則化推薦模型，該方法不僅擴展了信任關(guān)系，并且將不信任關(guān)系也融合到推薦系統(tǒng)中，在正則化過程中還考慮到了用戶間的興趣因素，本文的工作主要包括以下幾個方面：

1)針對含有不信任關(guān)系的社交網(wǎng)絡(luò)，提出一種修正的結(jié)合全局和局部信任的信任評估方法，擴展了用戶間稀疏的信任矩陣，并構(gòu)建了用戶間的不信任矩陣。

2)構(gòu)建用戶間的興趣相關(guān)性，對已有的社會正則化約束的矩陣分解方法進行了修正，加入信任和不信任關(guān)系矩陣以及用戶間的興趣相關(guān)性。

3)在Epinions數(shù)據(jù)集上的實驗證明了本文提出的方法在用戶-評分數(shù)據(jù)和信任關(guān)系數(shù)據(jù)都稀疏的情況下，相比其他類似的算法在推薦精度上有所提高。

1 相關(guān)工作

社交網(wǎng)絡(luò)環(huán)境下基于信任的推薦方法有很多的研究成果，Ma等[4]提出了一種SoRec方法將用戶間的信任關(guān)系和用戶對物品的評分信息融入概率矩陣分解；Wang等[5]提出一種基于矩陣因子的分解方法，將用戶間的相似關(guān)系作為信任關(guān)系的補充，綜合考慮了信任關(guān)系、項目間的相似關(guān)系來作為預測評分的權(quán)重；Yang等[6]提出了一種TrustMF算法，該算法結(jié)合矩陣分解框架，將評分矩陣和社交關(guān)系矩陣同時融合進矩陣分解中，反映了信任用戶間的關(guān)系對矩陣分解的評分預測的影響；Lai等[7]在基于信任的推薦系統(tǒng)上提出了一種混合的個人信任模型，并且考慮到具有相似偏好的用戶通常來自于同一組，用戶的偏好可能受組成員的影響，將個人信任和組信任混合，提高推薦的性能。以上提出的方法僅僅考慮了用戶間的信任關(guān)系而忽略了不信任關(guān)系。

最近幾年，也有一些學者嘗試將用戶間的不信任關(guān)系融入推薦系統(tǒng)中，印桂生等[8]提出一種結(jié)合受限信任關(guān)系的概率矩陣分解方法，利用用戶間的不信任關(guān)系對信任關(guān)系進行修正，然后聯(lián)合用戶的信任關(guān)系和評分信息進行聯(lián)合概率矩陣分解；Forsati等[9]提出一種PushTrust方法，該方法能夠同時利用信任、不信任和中立關(guān)系，并且對社交網(wǎng)絡(luò)的規(guī)模有著線性的依賴關(guān)系，將基于排序的社會正則化思想融入到矩陣分解算法中；李慧等[10]通過計算信任網(wǎng)絡(luò)中節(jié)點的聲望值與偏見值來發(fā)現(xiàn)信任網(wǎng)絡(luò)中的不可信節(jié)點,并通過對其評分權(quán)重進行弱化來減輕其對信任網(wǎng)絡(luò)產(chǎn)生的負面影響。Jang等[11]充分考慮顯式信任關(guān)系和顯示不信任關(guān)系，利用傳播特性擴展了用戶間的信任和不信任關(guān)系。

以上提出的方法雖然都利用了不信任關(guān)系，但大都只是利用不信任關(guān)系對信任進行修正，這樣沒有充分地利用不信任關(guān)系，因此本文將信任和不信任關(guān)系分開考慮，利用網(wǎng)絡(luò)的拓撲特性在信任網(wǎng)絡(luò)子圖和不信任網(wǎng)絡(luò)子圖中進行隨機游走得到用戶的全局影響力，結(jié)合局部信任度得到修正的用戶信任度矩陣，同時本文還定義了用戶間的不信任度，提出了一種定義用戶間的興趣相關(guān)性的方法，然后將這些同時作為正則化項對用戶-商品的矩陣分解進行約束。

2 融合社交網(wǎng)絡(luò)和興趣的正則化推薦算法

2.1 問題描述

表1 符號表

2.2 用戶信任關(guān)系矩陣的獲取

信任網(wǎng)絡(luò)是一種復雜的網(wǎng)絡(luò)關(guān)系，具有差異性、傳遞性、非對稱性等特點，信任的分類不同，其度量的方法也有所不同，包括集中與分布式、成對與成組式、全局與局部式，其中的全局和局部式是當前較流行的度量方法，因此本文采用一種基于改進的PageRank算法[12]的全局計算方法和基于多路徑傳播的局部信任計算方法。

2.2.1 PageRank全局信任度計算

全局信任指的是每個用戶在整個信任網(wǎng)絡(luò)中的地位和水平，代表了網(wǎng)絡(luò)中其他節(jié)點對其的綜合評價[13]，是從全局的角度出發(fā)的。PageRank算法最初應(yīng)用于計算網(wǎng)頁的重要性，因為該算法考慮到了網(wǎng)絡(luò)的全局拓撲特性，所以本文采用此算法來計算用戶的全局信任度。之前利用PageRank算法計算信任度時往往只考慮到了用戶間的信任關(guān)系，然而用戶之間也可能存在不信任關(guān)系，在網(wǎng)絡(luò)圖中一個用戶被越多人信任，其影響力越大；相反，一個用戶越不被人信任，其影響力越小，因此其全局信任度應(yīng)該是要綜合考慮這兩個因素的，本文將在網(wǎng)絡(luò)子圖G+中和G-中分別運行PageRank算法，利用不信任網(wǎng)絡(luò)子圖上游走的結(jié)果來修正用戶的全局影響力，得到最終的用戶影響力，即用戶的全局信任度。

根據(jù)文獻[14]中的描述，將計算網(wǎng)頁重要度的算法映射到兩個網(wǎng)絡(luò)子圖G+和G-中，將節(jié)點映射為網(wǎng)絡(luò)中的用戶，將邊映射為用戶間有信任關(guān)系或不信任關(guān)系的邊，在整個網(wǎng)絡(luò)中，一個用戶的全局信任度取決于所有信任他的用戶以及不信任他的用戶，其公式如下：

(1)

(2)

然而式(1)和式(2)中描述的PageRank算法在游走過程中游走到下一個相鄰節(jié)點時的概率是一樣的，未考慮到相鄰用戶之間的相似性，一個節(jié)點到下一個節(jié)點的概率必然是有所差別的，本文考慮到在游走過程中，從一個節(jié)點跳轉(zhuǎn)到下一個相鄰節(jié)點時的概率應(yīng)該是與相似性成正比的，在信任網(wǎng)絡(luò)中，由于彼此信任，則相似度越大的用戶之間轉(zhuǎn)移的概率就大；同樣地，在不信任網(wǎng)絡(luò)中，兩者之間相似度越小就越可能轉(zhuǎn)移到此不信任節(jié)點，因此，本文考慮擬將用戶間的相似性比值作為下次跳轉(zhuǎn)概率的權(quán)重，因此改進的計算公式分別如下：

(3)

(4)

式(3)、(4)中相似度的計算本文采用Person相似度，計算公式如下：

(5)

2.2.2 局部信任度計算

由于在最原始的信任度矩陣中，用戶之間的信任關(guān)系都是二進制的，因此本文首先使用用戶之間的相似度來作為兩個用戶之間的直接相似度，計算如式(4)，根據(jù)Golbeck[15]提出的用戶之間的共同信任鄰居越多，兩者之間的信任度越大，因此兩個非相鄰用戶之間的信任度計算公式如下：

(6)

2.2.3 綜合全局和局部信任度

通過對信任網(wǎng)絡(luò)的擴展，將用戶信任度矩陣變得稠密，然而，用戶的個人影響力也是在某種程度上也可以反映出用戶的信任度，因此本文考慮將用戶的全局信任度和局部信任度結(jié)合起來考慮用戶之間的信任度，公式如下：

(7)

其中：β的取值范圍是[0,1],該值表示局部信任度所占的比重,β的值越大,說明在整個網(wǎng)絡(luò)中，用戶之間的局部信任成為主要的因素，用戶有很強的主觀意識，而被信任人的個人影響力因素減弱，β最終的取值可以通過實驗數(shù)據(jù)觀察得出，將最后得到的信任度存入矩陣T中。

2.3 不信任關(guān)系矩陣的獲取

對于不信任矩陣的獲取問題，由于不信任關(guān)系與信任關(guān)系不同，其不具有很強的可傳遞性，不信任關(guān)系的擴展問題一直是一個難點，目前無法合理地計算其不信任度，根據(jù)文獻[16]中提出的敵人的敵人是朋友的可能性往往較大，并且這種思想傳遞的路徑長度也十分有限，因此為了簡化本文的計算，本文只考慮到敵人的敵人是朋友這樣一種情況，并且傳遞路徑長度只計算2步，因此提出根據(jù)不信任用戶之間的共同不信任鄰居數(shù)來定義兩個用戶之間的不信任值，對網(wǎng)絡(luò)子圖G-中的兩個用戶u和v，如果兩個用戶之間的共同不信任鄰居數(shù)越多，則他們之間的共同偏好可能相似，即他們之間的不信任度就會比較小，定義不信任度矩陣為D，則兩個用戶之間的不信任度計算公式如下：

(8)

其中：O(u)表示用戶u的不信任鄰居數(shù)，O(u)∩O(v)表示兩個用戶之間的共同不信任鄰居數(shù)，經(jīng)過對不信任度的計算，得到兩個用戶之間的不信任度，將其存入不信任度矩陣D中。一個簡單的不信任網(wǎng)絡(luò)子圖如圖1所示。

圖1 不信任網(wǎng)絡(luò)子圖

由式(7)的計算可以知道，用戶u和用戶v之間的不信任度為1-2/3=1/3，根據(jù)敵人的敵人是朋友這樣一個理論，用戶u和v之間共同敵人越多，則其是朋友的可能性越大，即兩者間的不信任度越小。

2.4 用戶間興趣相關(guān)性度量

用戶對某個項目的評分在某種程度上代表了用戶的興趣，但僅僅依靠項目評分來并不能準確定義用戶的興趣?？梢赃@樣假設(shè)如果兩個項目之間的關(guān)聯(lián)度高，那么同時對這兩個項目進行評分的用戶之間的興趣相似性就大，因此本文提出一種結(jié)合項目間的關(guān)聯(lián)度來量化用戶間興趣相關(guān)性的方法，根據(jù)文獻[17]的描述可以知道在數(shù)據(jù)挖掘中的項目的支持度(Support)和置信度(Confidence)都可以在某種程度上反映出兩個項目之間的相關(guān)性，支持度和置信度的計算公式分別如下：

Support(a,b)=(C(a)∩C(b))/|U|

(9)

Confidence(a,b)=(C(a)∩C(b))/C(a)

(10)

式(9)、(10)中：C(a)表示對物品i評分過的用戶數(shù),|U|表示評價過商品的用戶總數(shù)，可以看出支持度是從全局的角度出發(fā)來評估項目之間的關(guān)聯(lián)性，而置信度是從局部的角度來評估的，因此，與計算信任度的方法類似，本文考慮將這兩者結(jié)合起來，定義一個閾值ω，來均衡兩者的比例，具體的計算公式如下：

(11)

其中閾值ω的表示項目支持度占的比重。若ω=0則表示物品間的置信度就是兩個物品間的關(guān)聯(lián)度，隨著ω的增加置信度占的地位越來越大。其中ω的取值根據(jù)文獻[18]可以知道當ω取100時得到的效果是最好的，本算法得到了兩個項目之間的關(guān)聯(lián)相似性之后，根據(jù)如果兩個用戶對兩個相似物品有相似的評分，則表示這兩個用戶之間的興趣相似性大，因此定義兩個用戶之間的興趣相似性公式如下：

(12)

2.5 正則化推薦模型

(13)

同樣地，在不信任網(wǎng)絡(luò)中，兩個不信任用戶之間的隱特征向量之間的距離應(yīng)盡可能地大，將用戶之間的不信任矩陣和興趣不相似度(1-In(i,k))同時作為權(quán)重，其公式如下：

(14)

本文結(jié)合式(12)和式(13)構(gòu)造關(guān)于隱特征向量Ui的正則項，表達式如下：

(15)

矩陣分解過程中的主要目的就是求出特征矩陣U和V，通過將上一步構(gòu)造的正則項融入矩陣分解的過程中，得到矩陣分解的損失函數(shù)如下所示：

(16)

其中:第二項和第三項是正則化項，防止矩陣分解過擬合問題，參數(shù)λ和α是控制正則化項影響的參數(shù)。

為了最小化式(15)的函數(shù)，本文采用基于梯度下降的優(yōu)化方法，由于式(14)得到的值可能是非正的，導致目標損失函數(shù)的非凸性，因此本文定義了一個輔助的矩陣H∈Rm×k，在目標函數(shù)迭代優(yōu)化的過程中，令迭代次數(shù)為n，如果Ψ(Ui)>0，令Hi=1；否則，令Hi=0，因此加入輔助矩陣之后的目標損失函數(shù)如下所示：

(17)

添加了輔助矩陣H之后，函數(shù)變成凸函數(shù)，因此可以使用梯度下降法來求解，矩陣U和矩陣V的迭代求解過程如下所示：

(18)

(19)

(20)

(21)

3 實驗及評估

3.1 實驗數(shù)據(jù)和評價標準

本次實驗采用學術(shù)界普遍使用的Epinions數(shù)據(jù)集，該數(shù)據(jù)集中含有信任和不信任關(guān)系數(shù)據(jù)，本文對數(shù)據(jù)集進行了一次劃分，選取了其中對商品評價個數(shù)大于10并且至少有一個信任關(guān)系的用戶，經(jīng)過篩選之后的Epinions數(shù)據(jù)集的統(tǒng)計情況如表2所示。

表2 Epinions數(shù)據(jù)集統(tǒng)計

可以看出評分數(shù)和社交關(guān)系的稀疏度都是非常高的，為了評估本文提出的方法的有效性，從數(shù)據(jù)集中隨機選取80%的評分數(shù)據(jù)作為訓練集，剩下的20%作為測試集，本文采用五折交叉驗證的方法，取5次實驗結(jié)果的平均值作為本實驗的結(jié)果。由于本文提出的正則化推薦模型是為了提高推薦的準確度，因此采用平均絕對誤差(Mean Absolute Error, MAE)和均方根誤差(Root Mean Square Error, RMSE)來作為實驗的評估方法：

(22)

(23)

式(22)、(23)中‖K‖表示測試集中用戶-商品的評分數(shù)量，RMSE和MAE的值越小表示推薦的效果越好。

3.2 超參數(shù)對實驗的影響

在本文提出的方法中，求解用戶的全局信任度時，一般取d為0.85，ω取100；參數(shù)β表示局部信任所占的比重，表示在計算用戶的全局信任和局部信任的重要性；參數(shù)α表示信任和不信任關(guān)系的正則項，表示用戶的社交關(guān)系在推薦中的地位；參數(shù)λ表示用戶-商品矩陣的正則項系數(shù)；參數(shù)η表示梯度下降求解過程中的學習速率。在驗證參數(shù)某個參數(shù)對實驗的影響時固定其他參數(shù)，下面經(jīng)過實驗得出最優(yōu)的α、β、λ和η的值,各個參數(shù)的實驗結(jié)果如圖2所示,下面依次對各參數(shù)的實驗結(jié)果作進一步的分析。

圖2 不同參數(shù)值對推薦準確度的影響

1)確定局部信任所占的比重β。

局部信任所占的比重β表示了在信任矩陣度量時全局信任和局部信任各自的重要性，在實驗中本文將參數(shù)β的取值設(shè)置在0.1～0.9，以0.1為步長，記錄推薦結(jié)果的RMSE值隨β取值不同的變化情況。結(jié)果如圖2(a)所示。

從圖2(a)中可以看出，當β取0.3時得到的結(jié)果最好，說明在計算用戶信任度的時候，用戶的全局信任占主導地位，分析其原因就是用戶之間的信任關(guān)系數(shù)據(jù)稀疏，用戶只能更多地依靠其自身影響力來決定用戶的信任度，因此全局信任度占的比重較大。

2)確定正則項系數(shù)α。

社交關(guān)系正則化項系數(shù)α表示信任和不信任關(guān)系對矩陣分解的影響程度，當α=0時相當于基本的矩陣分解模型，本文設(shè)定α的取值范圍為0.1～0.9進行實驗。

從圖2(b)中可以看出，當α取值較小時，推薦的誤差較大，隨著α取值的增加，推薦誤差逐漸減小，當α=0.5時到達一個最小誤差值，再次增加α的值，誤差再次增加，分析其原因就是α取值過小說明社交關(guān)系的在推薦中的作用小，則由于評分數(shù)據(jù)稀疏性，則誤差大，α取值過大說明用戶的社交關(guān)系所占的比重超過了用戶的偏好所占的比重，則用戶偏好數(shù)據(jù)沒有被合理地利用，也會導致誤差過大。

3)確定參數(shù)λ。

參數(shù)λ的作用是防止模型的過擬合，在實驗中λ的取值分別為0.000 01，0.000 1，0.001，0.01，0.1，記錄推薦結(jié)果的RMSE隨λ取值的變化情況，如圖2(c)所示。從圖2(c)中可以看出，當λ取0.001時誤差最小，分析其原因就是當λ取值過小時，整個模型是欠擬合的，取值過大時，導致了整個模型的過擬合。

4)確定步長η。

步長η表示在梯度下降過程中的學習速率，η的值過大或過小都會導致最后求得的結(jié)果的不準確，在實驗中同樣取η的值為0.000 01，0.000 1，0.001，0.01，0.1，結(jié)果如圖2(d)所示。從圖2(d)中可以看出當η取值為0.000 1時效果最好，可以明顯看出當步長取值過大時，誤差較明顯，因為此時結(jié)果可能無法收斂到一個穩(wěn)定值，因此在求解過程中應(yīng)當選擇合適的步長。

3.3 對比實驗

為了更好地驗證本文提出的算法的有效性，本文選取了以下四種對比算法：SocialMF[19]、SoRec[4]、TrustMF[6]、CTRPMF[8]、RecSSN[20]，通過之前的實驗分析可知當正則化系數(shù)λ=0.001，步長η=0.000 1，社交網(wǎng)絡(luò)正則項系數(shù)α=0.5，全局信任的比例β=0.3時，算法有最好的推薦效果，因此本文的參數(shù)依此取值，用戶及項目的特征向量的維度均取10，算法的對比實驗結(jié)果如表3所示。

表3 不同算法MAE和RMSE對比

從表3可以看出，本文提出的融合信任和不信任網(wǎng)絡(luò)正則化推薦模型相比其他算法在推薦準確度上有所提高，分析其原因如下：SocialMF、SoRec算法和TrustMF算法僅僅考慮了用戶間的信任關(guān)系，而忽略了用戶間的不信任關(guān)系；CTRPMF算法只是簡單地利用不信任關(guān)系對信任關(guān)系進行修正，對信任關(guān)系進行了簡單的擴展，并未考慮全局和局部因素，而且也未對不信任關(guān)系作出評估；RecSSN算法沒有考慮用戶間興趣相關(guān)性的影響。本文提出的算法在擴展用戶間的信任關(guān)系時同時考慮到了用戶間的信任和不信任關(guān)系，緩解了社交關(guān)系稀疏的問題，另一方面利用信任和不信任關(guān)系為用戶-物品的隱特征矩陣提供了更多的約束條件，同時還考慮到了用戶間的興趣相關(guān)性作為約束，因此本文提出的算法有更好的推薦精度，其中RMSE值降低了1.1%～9.5%，MAE值降低了2%～10.1%。

4 結(jié)語

傳統(tǒng)的基于社交關(guān)系的推薦系統(tǒng)面臨著社交關(guān)系數(shù)據(jù)稀疏的問題，同時沒有考慮到用戶間的不信任關(guān)系對推薦結(jié)果的影響，因此本文提出一種在矩陣分解模型中融入用戶間的信任和不信任關(guān)系的正則化推薦模型，通過不信任關(guān)系度量信任值改善了社交關(guān)系稀疏的問題，然后結(jié)合矩陣分解技術(shù)改善了用戶評分數(shù)據(jù)稀疏的問題；但是隨著數(shù)據(jù)量的增加，推薦需要的開銷大、計算時間長，推薦的可擴展性成為了一個亟待解決的問題，因此本文下一步考慮如何利用信任和不信任關(guān)系進行更合理的聚類，減小計算開銷。