一種融合信任度和相似度的推薦算法

劉 群，陳 陽

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

0 引言

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

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

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

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

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

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

1.1 合并信任鄰居集的評(píng)分

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

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)仿真和分析

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

2.1 實(shí)驗(yàn)數(shù)據(jù)介紹

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

2.2 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中，我們使用如下的方法與融合算法進(jìn)行比較。

·TrustAll:將所有用戶對(duì)某個(gè)項(xiàng)目評(píng)分的平均分作為源用戶對(duì)該項(xiàng)目的預(yù)測(cè)評(píng)分。

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

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

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

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

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

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

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

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

·Niche Items:表示被評(píng)分少于5次的項(xiàng)目。

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

2.3 融合算法的性能

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

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

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

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

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

2.4 相似性閾值θ

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

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

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

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

3 結(jié)束語

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

圖2 Epinions上相似性閾值實(shí)驗(yàn)結(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］李勇軍，代亞非.對(duì)等網(wǎng)絡(luò)信任機(jī)制研究［J］.計(jì)算機(jī)學(xué)報(bào)，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ì)算方法［J］.計(jì)算機(jī)學(xué)報(bào)，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.