劉 群，陳 陽

(重慶郵電大學計算機科學與技術(shù)學院，重慶400065)

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，推薦系統(tǒng)［1］被廣泛地運用于在線網(wǎng)絡(luò)平臺中。協(xié)同過濾［2］是目前應(yīng)用最普遍的一種推薦技術(shù)，該方法僅僅依賴于用戶對項目的歷史評分，計算用戶之間的相似性，得到與源用戶相似的鄰居集合，最后為源用戶推薦其可能感興趣的項目。為了提高算法的性能，使推薦系統(tǒng)有更好的用戶體驗。近幾年，周濤［3-4］等利用物理動力學方面的知識，如物質(zhì)擴散理論，提出基于物質(zhì)擴散的推薦算法，劉建國［5］等在協(xié)同過濾算法中引入了物質(zhì)擴散動力學，這類算法的準確性明顯好于經(jīng)典的協(xié)同過濾算法，較大地提高推薦結(jié)果的準確性。但是，上述推薦技術(shù)在處理數(shù)據(jù)稀疏性，冷啟動等問題上存在先天的缺陷。

為了緩解上述算法的不足，基于信任模型的推薦系統(tǒng)［6-7］應(yīng)運而生。目前，信任已經(jīng)在推薦系統(tǒng)中得到了深入的研究。TidalTrust［8］利用一種改進的廣度優(yōu)先遍歷方法來計算用戶之間的信任度。文獻［9］介紹了MoleTrust，這種方法與 TidalTrust算法相似，只是在計算源用戶與目標用戶信任度時，信任的傳播距離是一個預(yù)先輸入的確定值。這類算法通過在用戶信任網(wǎng)絡(luò)中，計算源用戶與目標用戶之間的信任度，再利用信任度為源用戶做出推薦。這種方式能更合理地解釋為用戶做出的推薦結(jié)果，在克服數(shù)據(jù)稀疏性和緩解冷啟動問題上也起了很大的作用，使推薦結(jié)果有更高的準確度，同時覆蓋率也有了較大的提高，不過仍然需要進一步的提高。

實際上，在基于信任的推薦系統(tǒng)中，源用戶信任的鄰居傾向于分享各自的興趣。研究者們發(fā)現(xiàn)用戶之間的信任關(guān)系與用戶的偏好有很強的正相關(guān)關(guān)系，這種方法能有效地減少推薦結(jié)果的誤差。Ray和Mahanti［10］提出了在用戶的信任網(wǎng)絡(luò)中刪除那些相似性低于預(yù)先設(shè)定的閾值的信任鄰居，得到一個新的信任網(wǎng)絡(luò)，這種方法在推薦精度上有一定的提高，但卻犧牲了一定的覆蓋率。

針對上述問題，本文提出了一種結(jié)合物質(zhì)擴散和信任模型的融合推薦算法(merge method)。該算法根據(jù)源用戶直接信任的鄰居對項目的評分來表示源用戶的喜好，并利用信任鄰居評分過的項目集合，結(jié)合物質(zhì)擴散得到源用戶的相似鄰居，最后，合并信任鄰居和相似鄰居來計算源用戶對項目的預(yù)測評分。本文使用2個真實的數(shù)據(jù)集來評估融合算法的性能，實驗結(jié)果顯示，該混合算法和本文其他算法比起來有更高的準確性和覆蓋率，特別是對冷啟動用戶更有效。

1 融合信任度與相似度的方法

本文提出的融合直接信任鄰居集合與相似鄰居集合為源用戶做出推薦的方法，主要有以下3個步驟:①融合源用戶直接信任鄰居集合對項目的評分代表源用戶的個人喜好;②利用物質(zhì)擴散理論求出用戶之間的相似度，找出源用戶的相似鄰居集合;③利用信任鄰居和相似鄰居對給定項目進行評分，為源用戶計算對該項目的預(yù)測評分。

1.1 合并信任鄰居集的評分

記U和I分別表示推薦系統(tǒng)中所有用戶和項目集合，rv，i表示用戶v對項目i∈I的評分。對于任一源用戶u∈U沒有評分的項目j∈I，算法的任務(wù)就是為源用戶u對項目j計算得到一個預(yù)測評分，記為u，j。

首先，我們找出源用戶u直接信任的鄰居集合TNu。對于每一個信任鄰居v∈TNu，都與源用戶u有一個確定的信任值tu，v，表示用戶u對用戶v的信任程度。源用戶u對項目的評分準確代表了其個人喜好，因此，我們假定源用戶u是完全信任自己的，即TNu中包含源用戶u，且tu，u=1。

對于每個項目i∈I，如果被TNu中至少一個用戶評分過，我們就可以利用用戶u與v∈TNu之間的信任值合并u所有信任鄰居對項目i的評分，得到

1.2 合并基于物質(zhì)擴散的協(xié)同過濾算法

基于物質(zhì)擴散理論的協(xié)同過濾算法不考慮用戶和項目的內(nèi)容特性，而僅僅把它們都看成抽象的節(jié)點，算法利用的信息都藏在用戶和產(chǎn)品的選擇關(guān)系之中。在網(wǎng)絡(luò)中，所有的用戶記為集合U={u1，u2，…，um}，所有的項目記為集合 I={i1，i2，…，in}，整個推薦系統(tǒng)就可以定義成為一個鄰接矩陣A={aij}，如果用戶uj選擇過項目ii，則aij=1，相反則aij=0。對于每個源用戶，算法將為該用戶得到一個有序的推薦列表，推薦到表中的是源用戶沒有選擇過的項目。

根據(jù)上述用戶——項目矩陣A，利用物質(zhì)擴散動力學就可以構(gòu)建一個用戶相似性矩陣，得到每一對用戶之間的相似性。首先，假定項目二分圖網(wǎng)絡(luò)中每一個用戶具有確定的資源1(用戶具有的推薦能力為1)。然后，根據(jù)文獻［3-4］提出的基于物質(zhì)擴散的算法:第1步，每一個用戶先將自己的資源平均分配給他選擇過的項目;第2步，每一個項目將第1步中資源傳遞后自己得到的資源再平均地分配給選擇過它的用戶。資源傳遞完成后，每一對用戶之間都會得到一個權(quán)重su，v，它表示用戶u愿意分配給用戶v的那部分初始資源。利用1.1節(jié)中得到了合并評分后的項目集合～Iu，根據(jù)物質(zhì)擴散的過程，則用戶u和用戶v的相似性su，v可表示為

(2)式中:k(ij)表示項目ij的度;k(uv)表示用戶uv的度。利用(2)式就可以得到源用戶與其他用戶間的相似性，進而得出源用戶最相似鄰居集NNu為

(3)式中，θ是預(yù)先設(shè)定的相似性閾值。

根據(jù)前文所述，對于任一源用戶沒有評分過的項目j，我們利用源用戶與信任鄰居TNu間的信任度和最相似鄰居NNu的相似度作為權(quán)重，合并信任鄰居與相似鄰居對項目j的評分，則源用戶u對項目j的預(yù)測評分^ru，j可以表示為

(4)式說明了與源用戶u相似度高或者信任度高的鄰居對項目的預(yù)測評分有很大的影響，使推薦結(jié)果的質(zhì)量更高。

2 實驗仿真和分析

為了驗證本文提出的融合算法，我們在2個真實數(shù)據(jù)集上進行了實驗仿真。實驗的主要內(nèi)容包括:①融合算法與其他方法進行性能對比;② 信任的傳播距離對算法的性能有何影響;③ (3)式中的相似性閾值θ對算法性能的影響。

2.1 實驗數(shù)據(jù)介紹

本文實驗使用FilmTrust，Epinions這2個真實的數(shù)據(jù)。FilmTrust是一個基于信任的社交網(wǎng)站，該網(wǎng)站允許用戶對電影做出評分和評論。FilmTrust包括1 986個用戶，2 071部電影和35 497個評分(評分從0.5到4.0)，以及609個用戶做出的1 853條信任評分，信任評分是一個二進制數(shù)，1表示信任;0表示不信任。Epinions是一個用戶可以發(fā)表自己意見的網(wǎng)站，該網(wǎng)站允許用戶對電影、書籍、軟件等做出評論，也可以對這些產(chǎn)品進行評分(從1分到5分)，同時用戶也可以對其他用戶做出信任評分，信任則為1;反之則為0。該數(shù)據(jù)集包括49 290個用戶對39 738不同的產(chǎn)品至少有過一次評分，總共有664 824評分，用戶之間的信任評分有487 181條。

2.2 實驗設(shè)置

實驗中，我們使用如下的方法與融合算法進行比較。

·TrustAll:將所有用戶對某個項目評分的平均分作為源用戶對該項目的預(yù)測評分。

·user-based collaborative filtering(UCF):根據(jù)PCC計算用戶之間相似性，找出源用戶的最近鄰居集，對源用戶沒有評分的物品做出預(yù)測評分。

·massive diffusion-based collaborative filtering(MD-UCF):根據(jù)物質(zhì)擴散的過程，得到所有用戶最終的資源分配矩陣，用該矩陣的每一個元素代表2個用戶之間的相似性，找出相似性大于閾值θ的用戶，利用這個相似性作為權(quán)重，為源用戶未選擇過的項目做出預(yù)測評分。

·MTx(x=1，2，3)表示 MoleTrust算法［9］，x為信任的傳播距離，且只有源用戶的信任鄰居才能參與對項目的預(yù)測評分。

·Merge2:表示本文提出的算法Merge的信任傳播距離為2的情況，是為了檢驗信任傳播距離對算法性能的影響，該方法也是融合了信任鄰居和相似鄰居。

同時，我們對數(shù)據(jù)集中的用戶和項目做了如下定義［6］。

·All:表示整個數(shù)據(jù)集。

·Cold Users:表示評分過的項目數(shù)量少于5的用戶。

·Heavy Users:表示評分過的項目數(shù)量多于10的用戶。

·Niche Items:表示被評分少于5次的項目。

在本文實驗中，數(shù)據(jù)劃分為80%作為訓練集，20%作為測試集。為了檢驗算法的性能，我們使用平均絕對偏差(mean absolute error，MAE)來驗證算法的準確性，用評分覆蓋率(rating coverage，RC)來評價算法預(yù)測評分項目數(shù)量占總的項目的百分比。

2.3 融合算法的性能

首先，固定相似性閾值為0，然后，將融合算法與前文所述算法做比較，并根據(jù)實驗結(jié)果對算法的性能做出評價。表1，表2分別顯示了在數(shù)據(jù)集FilmTrust，Epinions的實驗結(jié)果。表1，表2中對應(yīng)算法的MAE值，該值越小表明該算法的準確性越高;對應(yīng)算法的RC值，該值越大表明該算法的覆蓋率越高，性能越好。

表1 FilmTrust上MAE與RC的實驗結(jié)果Tab.1 Experimental results of MAE and RC on FilmTrust

表2 Epinions上MAE與RC的實驗結(jié)果Tab.2 Experimental results of MAE and RC on Epinions

從表1，表2可以看出，UCF在2個數(shù)據(jù)集上得到的實驗結(jié)果有很大的不同，這是由于Epinions比FilmTrust的數(shù)據(jù)更稀疏，Epinions上冷啟動用戶覆蓋率僅為3.22%，而MAE值卻高達1.063。MD-UCF的準確性雖然比UCF要好些，但冷啟動用戶的評分覆蓋率也僅有3.86%。相對于UCF和MD-UCF，從2個表中可以看出，基于信任的推薦算法(MTx)，部分緩解了冷啟動問題，并且覆蓋率隨著信任傳播的距離增大而有所提高，但是算法整體的MAE值卻比MDUCF還要大，甚至有些方面比UCF還大。

前述的3種算法都存在準確性或者覆蓋率方面的缺陷，性能甚至比TrustAll還差。反觀Merge算法，有更好的準確性和覆蓋率。也證明了Merge在保證準確性的同時有效地緩解了冷啟動問題，達到了預(yù)期的實驗效果。同時，本文也比較融合算法Merge和Merge2，我們發(fā)現(xiàn)，Merge2的評分覆蓋率僅僅比Merge提高了不到1%，但Merge2的平均絕對偏差卻有明顯地上升。這是因為雖然隨著傳播距離增加，可以得到更多的信任鄰居來表示源用戶的個人喜好，但這并不意味著合并后的評分集合覆蓋了更多不同的項目，特別是當源用戶直接信任的鄰居本來就較多的情況下更是如此。此外，信任傳播的距離增加，不可避免地將引入臟數(shù)據(jù)，這樣就必然會降低算法的準確性。而且，融合算法已經(jīng)有了很高的評分覆蓋率，更沒有必要為了提升很小的覆蓋率而犧牲準確性。綜上所述，信任的傳播距離增加不會對Merge算法有很好的幫助。

2.4 相似性閾值θ

相似性閾值θ在UCF和MD-UCF算法中是一個非常重要的參數(shù)，它被用來選擇源用戶最相似的鄰居并參與計算源用戶對給定項目的預(yù)測評分。當相似性閾值設(shè)置較大時，只能得到很少的相似鄰居，這樣，雖然在準確性上有一定的提升，但犧牲了覆蓋率。因此，為了找到一個合適的相似性閾值，我們將θ從0到0.9按照每間隔0.1設(shè)置，實驗結(jié)果分別如圖1和圖2所示。

圖1 FilmTrust上相似性閾值實驗結(jié)果Fig.1 Experimental results of similarity threshold on FilmTrust

實驗結(jié)果顯示，UCF和MD-UCF的準確性隨著θ提高反而有所下降。這是由于UCF和MD-UCF計算相似性的方法所造成的，當數(shù)據(jù)稀疏性變大時，用戶之間共同評分的項目就會越來越少，UCF算法就很難有效地區(qū)別這些相似的用戶是否可靠，造成推薦結(jié)果不準確。而MD-UCF算法在面對數(shù)據(jù)稀疏性較大時，用戶與項目之間的關(guān)聯(lián)關(guān)系則越來越少，難以準確找到用戶的相似鄰居。本文提出的融合算法隨著θ的提高，準確性逐漸上升，但當θ＞0.4時，在FilmTrust上準確性又會降低。當相似性閾值分別達到0.4和0.8時，在FilmTrust和Epinions上融合算法達到最高的準確性，并且覆蓋率只是略有下降。

由于基于用戶信任關(guān)系的算法在提高準確性的同時也部分緩解了冷啟動問題，基于物質(zhì)擴散的協(xié)同過濾算法則在準確性上比協(xié)同過濾有較大的提高。因此，融合這2種算法的思想，既可以利用信任朋友的評分信息，豐富可用數(shù)據(jù)，提高推薦的可靠性;又可以利用物質(zhì)擴散傾向于推薦度大的項目，從而是混合算法整體的性能比起單個算法更優(yōu)秀。通過上文的實驗也證明了這種混合后算法可以有效地提高推薦系統(tǒng)的準確性，同時進一步提高系統(tǒng)緩解冷啟動問題的能力。

3 結(jié)束語

本文提出了一種簡單有效的融合推薦算法，該算法混合了基于信任鄰居和基于物質(zhì)擴散理論的協(xié)同過濾，為源用戶產(chǎn)生推薦。根據(jù)2個真實數(shù)據(jù)集上的實驗結(jié)果顯示，融合算法在準確性和覆蓋率上比其他對比算法有了較大的提高，很好地解決了數(shù)據(jù)稀疏性和冷啟動問題，也證明了該算法只需要根據(jù)直接信任的鄰居便可以得到很好的效果。同時，調(diào)整相似性閾值可以使融合算法的性能更進一步的提升，但是仍然不夠完善。該算法沒有考慮到將信任鄰居中與源用戶相似性低的用戶排除掉，這對算法的準確性有一定的影響。因為實驗數(shù)據(jù)非常稀疏，只有很少的信任鄰居對給定的項目有過評分，采用這些評分容易引入臟數(shù)據(jù)，難以準確表示源用戶的個人喜好，進而影響算法的整體性能。在以后的工作，我們將重點處理這些問題，進一步完善算法。

圖2 Epinions上相似性閾值實驗結(jié)果Fig.2 Experimental results of similarity threshold on Epinions

［1］LV Linyuan，CHI H Y，MATUS M，et al.Recommender systems［J］.Phys.Rep，2012，519(1):1-49.

［2］SU Xiaoyuan，KHOSHGOFTAAR M T.A Survey of Collaborative Filtering Techniques［J］.Journal Advances in Artificial Intelligence，2009(2009):421425-P1-421425-P19.

［3］ZHOU Tao，REN Jie，MEDO M.Bipartite network projection and personal recommendation［J］.Phys Rev E，2007，76(4):046115-P1-046115-P7.

［4］ZHOU Tao，JIANG L L，SU R Q.Effect of initial configuration on network-based recommendation［J］.Europhysics Letters，2008，81(5):58004-P1-58004-P6.

［5］LIU Jianguo，WANG Binghong.Improved Collaborative Filtering Algorithm via Information Transformation［J］.International Journal of Modern Physics C，2009，20(2):285-293.

［6］MASSA P，AVESANI P.Trust-aware Recommender Systems［C］//Proceedings of the ACM Conference on Recommender Systems.Minneapolis:ACM Press，2007:17-24.

［7］JAMALI M，ESTER M.Using a Trust Network to Improve Top-N Recommendation［C］//Proceedings of the third ACM conference on Recommender systems.New York:ACM Press，2009:181-188.

［8］GOLBECK J.Computing and applying trust in web-based social networks［D］.Washington D.C.:University of Maryland，2005.

［9］MASSA P，AVESANI P.Trust metrics on controversial users:balancing between tyranny of the majority and echo chambers［J］.International Journal on Semantic Web and Information Systems，2007，3(1):39-64.

［10］RAY S，MAHANTI A.Improving Prediction Accuracy in Trust-aware Recommender Systems［C］//Proceedings of the 43rd Hawaii International Conference on System Sciences.Hawaii:IEEE Press，2010:1-9.

［11］李勇軍，代亞非.對等網(wǎng)絡(luò)信任機制研究［J］.計算機學報，2010，33(3):390-405.LI Yongjun，DAI Yafei.Research on trust mechanism for peer-to-peer network［J］.Chinese Journal of Computers，2010，33(3):390-405.

［12］O’DONOVAN J，SMYTH B.Trust in Recommender Systems［C］//Proceedings of the 10th international conference on Intelligent user interfaces.New York:ACM Press，2005:167-174

［13］喬秀全，楊春，李曉峰，等.社交網(wǎng)絡(luò)服務(wù)中一種基于用戶上下文的信任度計算方法［J］.計算機學報，2011，34(12):2403-2413.QIAO Xiuquan，YANG Chun，LI Xiaofeng，et al.A Trust Calculation Algorithm Based on Social Networking Service Users’Context［J］.Chinese Journal of Computers，2011，34(12):2403-2413.