融合用戶相似度與信任度的協同過濾推薦算法

蔣宗禮+李慧

摘要：傳統的協同過濾算法難以解決“稀疏性”和“冷啟動”等問題。鑒于此，提出一種融合用戶相似度和信任度的方法。首先根據用戶對共同項目的評分創建初始信任度，通過信任關系的傳遞規則，建立沒有直接信任關系的用戶之間的信任關系，然后融合用戶相似度與信任度，用于傳統的協同過濾推薦系統，找出用戶的最近鄰居集，進行項目的評分預測，從而產生推薦列表。實驗表明，改進后的算法能有效提高系統推薦的準確性。

關鍵詞：協同過濾；推薦系統；信任度；用戶相似度

DOIDOI：10.11907/rjdk.162798

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2017）006-0028-04

0 引言

隨著互聯網的迅猛發展，信息過載問題越發嚴重。為了緩解該問題，在海量信息中找到真正所需的信息，Goldberg等[1]在1992年首次提出了協同過濾推薦算法。該算法利用用戶對項目的評分記錄，計算與目標用戶有著相似興趣愛好的最近鄰居用戶集，并根據該鄰居集對目標項目的評分情況，計算目標用戶對目標項目的預測評分值，最終把N個最高預測評分值的項目推薦給目標用戶。協同過濾推薦算法簡單高效，已經成為目前最流行的個性化推薦算法之一。然而，隨著系統規模的擴大，協同過濾算法會出現數據稀疏性（Data Sparsity）、冷啟動（Cold Start）、可擴展性等問題，使得協同過濾算法容易受到這些問題的困擾[2]。

針對稀疏性問題，Sarwar等[3]提出使用矩陣奇異值分解的方法對評分矩陣進行降維以減少稀疏性。鄧愛林等[4]提出首先根據基于項目的協同過濾算法預測部分項目評分，減少評分稀疏性，再根據基于用戶的協同過濾算法為用戶推薦。Herlocker等[5]將信任引入商品推薦系統中，該系統通過維護用戶對其他用戶的信任或不信任列表來建立用戶間的信任關系，基于信任的推薦系統認為用戶會傾向于采取受信任的身邊用戶的建議，目前，基于信任的推薦系統已經得到了廣泛研究與應用。經過驗證，融合信任的推薦算法可以取得比傳統協同過濾算法更好的效果，尤其是在緩解用戶“冷啟動”和數據“稀疏性”等方面[6-7]。

周林軻[8]提出無需用戶主動地給出對其他用戶的信任評分，而是通過挖掘用戶間的社交信息從而預測出用戶的信任度。Victor P等[9]則利用信任網絡特征計算信任度，并構建基于信任的推薦系統。林韶娟等[10]提出使用GenTrust算法，利用二值的信任網絡來預測擴展信任網絡， 提高了算法準確率。

還有一些學者利用信任傳播的方法計算信任度，也起到了改善數據稀疏性的作用。文獻[11]提出了一種基于信任傳播的加權平均方法計算信任度。文獻[12]則是利用信任傳播過程中信任值的衰減，設計了3種信任度計算方法。

本文提出信任度的構建方法是基于用戶共同評論的項目，而不依賴用戶主動給出對其他用戶的信任評分。有共同評論項目的用戶之間可以直接計算出信任值，沒有共同評論項目的用戶之間雖然不存在直接信任關系，但是可以通過信任的傳遞，間接地建立信任關系，而間接信任關系的建立在一定程度上解決了數據稀疏問題。最后將用戶信任度與相似度結合起來，引入到傳統的協同過濾推薦系統中，找出用戶的最近鄰居集，進行項目的評分預測，從而產生推薦列表。實驗表明，本文提出的相似度與信任度相融合的方式能有效地提高系統推薦的準確性。

1 相似度計算

1.1 用戶模型建立

協同過濾推薦算法的根本出發點是任意用戶的興趣不是孤立存在的，也即假如兩個用戶對一些項目的評價比較相似，那么他們對其它項目的評價也會比較相似。因此，協同過濾推薦算法的核心是計算用戶之間的相似度，根據相似度找出最近鄰居集，通過他們對項目的評分，預測評分較高的項目并推薦給用戶?？梢杂靡粋€m*n的用戶-項目評分矩陣A來對用戶相似度進行建模。如表1所示，矩陣A中的m行代表m個用戶，n列代表n個項目，第i行第j列元素Ri，j表示第i個用戶對第j個項目的評分（如果用戶對項目沒有進行評分，則Ri，j=0）。

計算得到用戶對項目的預測評分值后，將預測的評分值從大到小排序，將評分值大于指定閾值或前N個評分最高的項目推薦給目標用戶。

融合相似度與信任度的協同過濾推薦算法的推薦過程如圖1所示。

4 實驗

本文提出了融合相似度與信任度的協同過濾算法，為了證明本方法的有效性，做了一系列實驗，其中也包括對傳統基于相似度的協同過濾算法相關實驗。

4.1 數據集選取

本文所有實驗均在公開的MovieLens數據集上進行，該數據集包含了943位用戶對1 682部電影的100 000條評分記錄，每個用戶至少有20條評分記錄。評分有5個等級，用1～5的整數表示，數值越大表示用戶對該電影的喜愛程度越高。

將整個MovieLens數據集進一步劃分為訓練集和測試集。為此，引入變量x作為測試集占整個數據集的百分比。本文選用x=0.2，即在整個數據集中，訓練集占80%，測試集占20%，即訓練集為100 000*80%=80 000條數據，測試集為100 000*20%=20 000條數據。

4.2 評價標準

本文采用度量標準平均絕對誤差（ MAE） 作為評價標準來評價推薦系統的推薦效果。在推薦算法研究中，MAE是最常用也是應用最廣泛的評價指標。MAE的基本思想是計算系統對項目的預測評分與用戶對項目的實際評分之間的平均絕對偏差，MAE值越小表示推薦系統的推薦精度越高。MAE的計算公式如下所示：

4.3 結果分析

在計算信任度矩陣時，λ值的選取以及信任傳遞的深度MPD會影響整個信任矩陣的計算，因此針對這兩個重要參數進行了實驗，找出最佳的參數組合，利用參數組合對各種不同的推薦方案進行實驗比較。

首先，對λ的取值進行實驗，實驗結果如圖2所示。

圖3中的Sim&Trust表示將相似度與信任度相結合的推薦方案，Trust表示只利用信任度的推薦方案。實驗結果是在MPD=2，最近鄰居數量為20的前提下所得出。從實驗結果中可以看到，當λ值在0～0.1時，推薦方案的MAE值比較穩定，在0.05時，Sim&Trust推薦方案取得最小值，大于0.1后MAE有上升趨勢。因此，可以認為0.05對于系統而言是一個比較好的參數，在后面的推薦系統對比實驗中，也是將λ值設置為0.05。

確定λ的取值之后，對信任傳遞深度進行實驗，實驗結果如圖3所示。

實驗中一共設置了5組對比實驗，實驗結果是在λ=0，最近鄰居數量為20的前提下所得出。

當信任傳遞的深度小于3時，隨著MPD的增加，MAE的值逐漸減小，當超過3之后趨于平穩，考慮到算法的復雜度和運行時間，認為MPD取值為3比較合適。

當決定信任度矩陣的λ和信任度最大傳播深度MPD的值確定后，對傳統協同過濾算法的3種計算相似度的方法以及基于信任度的協同過濾算法中只有信任度和信任度與相似度相結合的方法進行實驗比較。實驗結果如圖4所示。

從圖4可以看出，本文提出的相似度與信任度相融合的方法在MAE表現來看，其效果優于傳統推薦方案。從鄰居數量的選取對MAE的影響來看，隨著鄰居數量的增加，除Pearson外，所有推薦系統都會有性能上的提升。從現實意義上講，給你提建議的人越多，你值得信任的人就可能越多，綜合給出的推薦效果就會越好。但并不是鄰居越多越好，到達一定程度，對實驗結果的影響就會越來越不明顯。如圖4所示，當最近鄰居的數量超過100之后，MAE的值趨于穩定，那是因為鄰居到達一定程度后，新擴展的鄰居與目標用戶相關性太低，以至于無法產生影響。

5 結語

融合用戶相似度和信任度的方法選擇余弦相似度和Jaccard相似度相結合的方式計算用戶間的相似度，在計算用戶信任度時分為直接信任度和間接信任度。之后將信任度和相似度融合，通過融合后的用戶相關度找出與某用戶相關性最強的用戶群作為該用戶的鄰居集，用于傳統的協同過濾推薦系統中，找出用戶的最近鄰居集，進行項目的評分預測。實驗表明，改進后的算法能有效提高系統推薦的準確性。鑒于相同地區相似年齡的同性人群對事物的觀點可能類似的假設，下一步的工作是，將用戶的個人信息加入到相似度的構建之中，希望可以進一步提高推薦系統的準確性。

參考文獻：

[1]D GOLDBERG，D NICHOLS，D TERRY.Using collaborative filtering to weave an information tapestry[C].Communications of the ACM，1992.

[2]范永全，杜亞軍.一種融合用戶偏好與信任度的增強協同過濾推薦方法[J].西華大學學報，2015，34（4）：8-12.

[3]B SARWAR，G KARYPIS，J KONSTAN.Item-based collaborative filtering recommendation algorithms[C].In Proceedings of the 10th International Conference on World Wide Web，New York，USA，2001：285-295.

[4]鄧愛林，朱揚勇，施伯樂.基于項目評分預測的協同過濾推薦算法[C].軟件學報，2003，14（9）：1621-1628.

[5]MASSA P，AVESANI P.Trust metrics in recommender systems[M].Computing with Social Trust.London：Springer，2009：259-285.

[6]U SHARDANAND，P MAES.Social information filtering： algorithms for auto mating "word of mouth"[C].in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems，Denver，Colorado，USA，1995：210-217.

[7]D GOLDBERG，D NICHOLS，D TERRY.Using collaborative filtering to weave an information tapestry[C].Communications of the ACM，1992.

[8] 周林軻.電子商務中基于信任的推薦算法研究[D].長沙：湖南大學，2011.

[9]VICTOR P，CORNELIS C，TEREDESAI A M，et al.Whom should I trust？ the impact of key figures on cold start recommendations[C].Proceedings of the 2008 ACM Symposium on Applied Computing，2008：2014-2018.

[10]林韶娟，陶曉鵬.基于二值信任網絡的推薦算法改進[J].計算機應用與軟件，2012，29（12）：157-160.

[11]CHAKRABORTY P S，KARFORM S.Designing trust propagation algorithms based on simple multiplicative strategy for social networks[J].Procedia Technology，2012：534-539.

[12]SCHAFER J B，KONSTAN J A，RIED J.E-commerce recommendation applications[J].DataMining and Konwledge Discovery，2001，5（1-2）：115-153.

（責任編輯：孫 娟）