基于混合信任模型的協(xié)同過濾推薦算法

摘要：協(xié)同過濾技術在面臨評分數(shù)據(jù)稀疏性問題時，推薦效果較差。為了提高推薦系統(tǒng)的推薦精度，可以將用戶在社會網絡中的交互信息加入到推薦系統(tǒng)中來，彌補評分數(shù)據(jù)不足的問題。在本文中，提出一種基于混合信任模型的協(xié)同過濾推薦算法，該算法將用戶在社會網絡中的歷史評級信息和交互頻率合并計算用戶之間的直接信任度，并通過一定的信任傳遞規(guī)則將沒有直接關聯(lián)的用戶間的間接信任度也計算出來，組成稠密的用戶信任矩陣。最后基于用戶信任矩陣和用戶評分矩陣共同來計算用戶之間的相似度并預測目標用戶對未評分項目的評分，得到推薦集。實驗結果表明本文提出算法可以提高數(shù)據(jù)密度，改善協(xié)同過濾推薦技術的稀疏性問題，有效提高推薦精度。

關鍵詞：協(xié)同過濾；信任模型；基于信任的推薦算法；相似度；社會網路

中圖分類號：TP31 文獻標識碼：A 文章編號：1009-3044（2016）20-0257-04

Abstract： In the face of rating data's sparsity problem， the recommendation effect of collaborative filtering technology is not so good. In order to improve the accuracy of recommendation system， we can add the interaction with the user information in social networks into the recommended system， in order to make up for the shortage of data rates. In this paper， we set up a hybrid trust model based on collaborative filtering algorithm， which combine the user rating information and interaction frequency in a social network， and calculate direct-trust-relationship between users. Following， the indirect-trust-relationship is also calculated by using some certain trust rules， and at last it forms a dense matrix of user trust. Finally， we calculate the similarity between users and predict the target ratings based on user-trust-matrix and user-scoring-matrix and get recommended set. Experimental results show that the proposed algorithm can increase data density， improve the sparsity problem of collaborative filtering technology and effectively improve the recommendation accuracy.

Key words：Collaborative filtering； Trust model； Trust-based recommender algorithm； Similarity；Social networks

1 引言

一個社交網站，比如臉譜網、微博，已經成為互聯(lián)網用戶不可或缺的一部分。信息技術和互聯(lián)網技術的普及和迅猛的發(fā)展，加劇了信息過載問題，增加了用戶獲得有用信息的成本。推薦系統(tǒng)作為一種過濾技術，可以有效緩解信息過載問題，為用戶提供優(yōu)質的個性化服務[1]。在傳統(tǒng)的個性化推薦算法中，協(xié)同過濾算法無疑是最成功的一種算法。協(xié)同過濾推薦算法是基于某些特定項目的用戶之間的相似性偏好來預測推薦結果的。更一般而言，如果他們在某些項目上有類似的利益，他們最有可能對一些其他項目感興趣。基于協(xié)同過濾的方法首先基于項目或基于用戶的相似性度量計算發(fā)現(xiàn)鄰居項目或鄰居用戶，然后通過相似性的鄰居的歷史偏好來預測目標用戶的偏好。雖然協(xié)同過濾是有效的，但當評分數(shù)據(jù)稀疏，用戶沒有足夠的歷史評級數(shù)據(jù)來支撐相似性計算時，推薦效果表現(xiàn)不佳。此外，基于協(xié)同過濾的推薦系統(tǒng)忽略了用戶之間的社會關系或信任關系，很多研究者也考慮利用社會網絡關系信息來提高協(xié)同過濾推薦系統(tǒng)性能。

基于信任的推薦系統(tǒng)試圖通過引入信任度量解決數(shù)據(jù)稀疏性問題，采用用戶項目評分信息和用戶社會信任網絡信息來共同計算相似度[2]。如果兩個用戶有非常少的共同評分項目，只從他們的共同額定項目的評級信息計算的信任值可能會產生誤導性的信任。雖然傳統(tǒng)的基于信任的比照系統(tǒng)已經提出了基于評級的信任模型，或明確指定的信任指標，以獲得用戶的可信性，由于用戶間共同評分數(shù)據(jù)的極度稀疏性，造成信任值度量的誤差很大，對推薦系統(tǒng)精度的改良意義不大。所以本文提出一個新的混合信任度量模型，利用用戶的歷史評分數(shù)據(jù)和用戶在社會網絡中的互動交互頻率來共同計算直接信任值，再通過一定的信任傳遞規(guī)則來計算沒有直接聯(lián)系和沒有共同評分項目的用戶之間的間接信任值，合并得到用戶信任矩陣。最后基于信任矩陣和用戶評分矩陣來共同預測評分，得到推薦結果。

2 傳統(tǒng)協(xié)同過濾方法

2.1 傳統(tǒng)相似性計算方法

協(xié)同過濾推薦的關鍵點是不同用戶之間的相似性度量。廣泛采用的方法是基于用戶的共同歷史評分數(shù)據(jù)項量來進行相似度的計算。在相似性計算方法中，雖然各有其優(yōu)缺點，但最常用的相似性度量方法是余弦相似性、修正的余弦相似性和皮爾森相似性[3]。

2.2 基于信任的協(xié)同過濾算法

信任被定義為一個用戶對另一個用戶可靠性的主觀信念。信任可以分為直接信任和間接信任，直接信任是用戶間直接交互作用而建立的信任，而間接信任是一個用戶通過信任傳播的方式和別的沒有直接聯(lián)系的用戶間的信任關系。假設信任度量的目的是量化用戶之間的信任程度，如果信任關系沒有明確表示，可以從評級數(shù)據(jù)或其他間接信息中推斷出來。此外，許多研究人員將信任引入到基于用戶的協(xié)同過濾的推薦中，并提出了許多信任模型。例如，從邏輯的角度研究用戶之間的信任關系，Pitsilis提出了一種基于不確定概率理論的信任模型[6]。然而，由于不確定性是由用戶的平均評分計算得到，而評分矩陣的稀疏性導致信任模型的準確性是有限的。Kwon等人研究了一種多維信任模型來測量用戶間相似度，然后計算一個加權匯總選擇鄰居[7]。然而，盡管該模型在選擇鄰居的過程中有更多的多樣性，但它仍然缺乏抵抗攻擊的能力。為此，本文針對上述問題，在前人的研究基礎上提出了一種改進的基于信任的協(xié)同過濾推薦算法，探討了一種計算用戶間信任度的新思路，然后將信任度和相似度按照一定原則組合，根據(jù)組合的相似度來搜索最佳鄰居得到推薦。

3 基于混合信任模型的協(xié)同過濾推薦算法

本文提出的改進的基于信任的協(xié)同過濾算法將用戶評分矩陣和用戶之間的交互信息作為輸入并計算用戶間之間信任值，再基于一種信任傳遞規(guī)則來計算用戶間接信任值。將直接信任值和間接信任值組合成為較稠密的信任矩陣。信任矩陣和評價矩陣被共同用來尋找目標用戶的K近鄰，并計算目標用戶對未評分項目的預測評分，最后選擇預測評分較高的項目作為推薦列表反饋給目標用戶。

3.1 直接信任度量

信任權重是用戶對另一個用戶信賴程度的量化，信賴程度越高，其權重越大。但許多網站并沒有提供用戶表達的直接信任權重。因此，本文使用用戶的評級項目和用戶的互動來計算用戶之間的直接信任值。用戶之間交互頻率越高，他們之間的相互作用就越強，用戶的行為也更容易受到他們信任的朋友的影響，所以接下來我們定義了一個直接的信任度的度量方法。

（1）基于歷史評分等級的直接信任度量

基于歷史評分等級的直接信任度量主要是通過用戶-項評分矩陣中用戶對項目的評分數(shù)據(jù)來進行的，比如用一個用戶對某一項目的評分去預測另一個用戶的對該項目的評分，若預測評分與該用戶實際對該項目的評分差異較小，我們認為這個用戶推薦人是更可靠的，他們之間的直接信任值便相對較高。參考傳統(tǒng)的信任計算模型，我們可使用雷斯尼克的預測公式來計算出依賴于用戶得到目標用戶的預測評分，計算方法定義如下：

3.2 間接信任度量

在現(xiàn)實生活中，人們不僅信任自己的朋友，還可以與朋友的朋友建立新的信任關系，這就是信任的傳遞規(guī)則。如果用戶A信任用戶B，用戶B的信任用戶C，雖然用戶A，C之間沒有直接信任關系，但通過用戶B，用戶A，C之間便可以找到一種可達的信任關系，也就是說信任是可以繁殖傳播的。在本文中，我們將使用此功能擴展本地信任網絡。類似地，我們可以在網絡中獲得這種間接信任關系。

在一段時間內，用戶與用戶之間沒有任何交互聯(lián)系，也沒有一個共同的歷史評分項目，也就是說，沒有直接的信任關系。若用戶和用戶之間存在信任連通路徑，如，其中都是該可達路徑上的中間用戶，則用戶和用戶之間可能存在間接信任關系。用戶對用戶的間接信任值定義如下：

在這里，表示用戶和用戶之間的可到達路徑的長度。

根據(jù)上述方法，可以計算出所有用戶之間的信任值，并可以形成一個關于所有用戶之間的信任度矩陣，后面用到的信任相似度便是矩陣中用戶所在行向量中各元素取值。

3.3 組合信任值的相似度計算

在上節(jié)中，通過計算用戶之間的信任關系，反映了互動效應。因此，用戶之間的信任度越高，它們之間的相互作用越大，就越相似。信任關系在一定程度上也反映了用戶之間的相似性，因此本文提出的基于信任的協(xié)同過濾方法是用戶信任矩陣中的信任值和用戶評分相似性按照一定方式進行組合，組合后的權重作為新的相似度參與目標用戶對未評分項目的預測評分?；谌缟戏治?，我們提出了一種新的用戶評分相似度和用戶信任關系的評價方法，在最近鄰對象的選擇上，我們需要確定如何選擇推薦對象的預測目標。通過定義兩個相似度閾值，即用戶的評分相似度閥值和用戶信任度閥值。同時我們定義評分相似度大于相似度閥值的用戶集合為評分相似鄰居集記為，信任度大于用戶信任度閥值的用戶集合為信任鄰居集記為，后續(xù)會合并評分相似度鄰居集和信任鄰居集來為目標用戶作推薦。為評分相似度和信任度組合的權重因子，的最優(yōu)取值問題會在后續(xù)實驗中進行討論。

最終的推薦相似度可以組合計算如下：

3.4 最終的預測評分值計算

在獲得直接信任值和間接信任值后，本文提出方法通過目標用戶的評分相似度鄰居集合和信任鄰居集合的并集記為來對目標用戶未評分的所有項目進行預測評分。最后選擇預測評分值較高的項目作為推薦結果反饋給目標用戶。

4 實驗結果

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

為了驗證本文新提出的推薦算法比傳統(tǒng)的協(xié)同過濾算法具有更好的性能，我們收集了MovieLens站點的相關數(shù)據(jù)集來完成相應實驗。MovieLens數(shù)據(jù)集是最常用來測試推薦算法性能的標準數(shù)據(jù)集。此數(shù)據(jù)集包含100000個等級從1到5的評價數(shù)值，由943名用戶對1682部電影的評價。在這個數(shù)據(jù)集中，用戶被要求至少對20部電影進行評分，數(shù)據(jù)稀疏率是95%左右。在實驗中數(shù)據(jù)集被分為訓練和測試部分（80%用于訓練測和20%用于測試集）。

4.2 結果分析

1）實驗1：通過調節(jié)評分相似度和信任度組合的權重因子來對比推薦精度MAE的值

在本實驗中我們將測試參數(shù)取不同值對推薦精度MAE值的影響。∈[0，1]，的值從0開始，每次增加0.1，縱坐標為推薦精度MAE的值，觀察縱坐標MAE值的變化，并將本文提出算法和“基于用戶的CF” 以及“基于信任的CF”作對比，發(fā)現(xiàn)當參數(shù)取值為0.6時推薦效果最佳。

2）實驗2：本文算法與其他協(xié)同過濾推薦算法的比較

本實驗的目的是將本文提出算法與傳統(tǒng)的協(xié)同過濾算法以及近期業(yè)界比較領先的研究方法EMDP（Effective Missing Data Prediction）進行比較。我們使用相同的實驗數(shù)據(jù)，比較了該算法與傳統(tǒng)的協(xié)同過濾算法，如基于項目的CF”，“基于用戶的CF”，“基于信任的CF”以及文獻[5]中提出的EMDP算法在推薦精度方面的差異。在這個實驗中，取值為0.6，和“最近鄰數(shù)數(shù)目”取值范圍為[10，60]，每次增加5個鄰居。實驗結果如圖2所示。實驗結果表明，本文提出的方法可以得到較低的MAE值，因此推薦效果更好，隨著產品最近鄰居數(shù)目的增加，預測的質量也在不斷提升。

5 結論

協(xié)同過濾是目前推薦系統(tǒng)所使用的主流技術，但用戶項評分矩陣的稀疏性問題是協(xié)同過濾技術的主要限制之一。為了解決稀疏性問題，本文提出了一種改進的基于信任的協(xié)同過濾推薦算法。該算法使用用戶的評級數(shù)據(jù)和交互信息作為推斷，產生一個信任矩陣，代表用戶之間的信任值，然后將信任值是用來糾正傳統(tǒng)相似性計算并以此來尋找最近鄰居用戶得到未評分項目的預測評分。由于本文提出的改進算法能搜索到更優(yōu)的鄰居用戶，所以使得推薦算法的推薦精度有較大提升。實驗結果表明，該算法優(yōu)于最近鄰協(xié)同過濾的預測質量。與傳統(tǒng)的基于項目的協(xié)同過濾算法、基于用戶的協(xié)同過濾算法、基于上下文的協(xié)同過濾算法、基于信任的協(xié)同過濾算法以及目前業(yè)界比較先進的EMDP算法在推薦精度方面作了對比，推薦性能較好，能很好緩解數(shù)據(jù)稀疏性問題對推薦精度的影響。由于要計算用戶之間的信任度，會增加推薦系統(tǒng)的時間開銷，不過可以將信任度的計算離線進行，減少對系統(tǒng)響應時間的影響。未來的研究，以提高該算法的時間性能以及提高算法的抗惡意攻擊能力等。

參考文獻：

[1] 彭玉，程小平. 基于屬性相似性的Item-based協(xié)同過濾算法[J].計算機工程與應用，2007，43（14），144-147.

[2] 李湛，吳江寧.基于用戶行為特征分析的隱形信任協(xié)同過濾推薦方法[J].情報學報，2013，28（5），490-496.

[3] 鄧愛林.電子商務推薦系統(tǒng)關鍵技術研究|D|.上海：復旦大學.2003

[4] Herlocker J. Konstan J A， Riedl J. An empirical analysis of design choices in neighborhood-based collaborative filtering algorithms[J]. Information Retrieval， 2002， 5（4）： 287-310.

[5] Ma H， King 1， Lyu M R. Effective missing data prediction for collaborative filtering// Proceedings of the 30th Annual International ACM SIGIR Conference[C]. Amsterdam， The Netherlands， 2007： 39-46.

[6] Pitsilis， Georgios， and Lindsay Forsyth Marshall.A model of trust derivation from evidence for use in recommendation system[D].University of Newcastle upon Tyne， Computing Science， 2004.

[7] K. Kwon， J. Cho and Y. Park. Multidimensional credibility model for neighbor selection in collaborative recommendation[J]. Expert System with Applications， 2009，36（3）：7114-7122.