摘要：隨著互聯(lián)網(wǎng)的發(fā)展，個性化推薦系統(tǒng)在緩解信息過載、提升用戶體驗方面發(fā)揮著重要作用，但其依然存在許多缺陷。本文以如何提高用戶滿意度為主線，通過社交網(wǎng)絡將信任機制引入推薦系統(tǒng)并參考社會學相關知識，將人們之間的信任來源進行分類，提出層次化信任度計算模型。最終通過實驗對層次化信任度計算模型的推薦效果進行了比較研究。

關鍵詞：推薦系統(tǒng)；社交網(wǎng)絡；本地信任；全局信任；層次化信任

Abstract：With the development of Internet，Recommendation Systems（RSs）plays an important role on alleviating Information Overflow and improving user satisfaction.But RSs have a lot of defects.The paper’s main topic is how to improve user’s satisfaction.For the calculation of trust degree，this paper imports trust into RSs through social networking and references knowledge of sociology and identifies trust source among people，and propose a model of hierarchical trust.In the end，the paper compared the recommendation of hierarchical model with the parameters.

Keywords：Recommendation System；Local Trust；Global Trust；Hierarchical Trust

1.引 言

我國正處于電子商務蓬勃發(fā)展的時代，但是也面臨前所未有的挑戰(zhàn)：信息過載。而推薦系統(tǒng)根據(jù)用戶需求為其推薦商品，降低了商品信息過載問題[9]，幫助用戶花費最少的時間和精力購買到最符合需求的商品，但其存在著難以克服的缺點。通過社交網(wǎng)絡將信任機制引入推薦系成為研究新方向。目前，這方面的研究尚不成熟，本文根據(jù)信任的產(chǎn)生來源將人與人之間的信任分為三個層面，建立了基于層次的信任度計算模型，具有重要的理論價值與實踐價值。

本文第2節(jié)詳細討論層次信任度計算模型；第4節(jié)通過實驗對模型進行性能評估；第5節(jié)總結全文。

2.層次化信任度計算模型研究

如何通過社交網(wǎng)絡將信任引入推薦系統(tǒng)，在學術界仍未達成共識。Paolo Massa等人在文獻[1，2，4]中分別使用了本地信任和全局信任使用戶之間可以傳播信任，喬秀全等人從圖論的角度說明了用戶之間的信任產(chǎn)生方式。本文則提出一種層次化的信任產(chǎn)生方式。

2.1 社交網(wǎng)絡中的多層次信任來源

根據(jù)社會學交際過程，本文將社交網(wǎng)絡中人與人的信任來源分為三層。

外部來源：新用戶會選擇信任網(wǎng)絡中名譽值比較高的用戶。交互來源：通過在線交互（或線下交際），新用戶對其他用戶了解加深，他們開始信任網(wǎng)絡中其他用戶。內(nèi)部來源：隨著時間的推移，用戶會越來越信任與自己在內(nèi)在品質(zhì)方面有較多相似點的用戶。

定義1.聲譽信任/外部信任：是外部來源所產(chǎn)生的信任，是由一個人在公共環(huán)境中的整體聲譽或者公信力所產(chǎn)生的信任。它是一種全局信任，是一個系統(tǒng)中所有人對該用戶的“公認度”，獨立于任何單個的第三方用戶。即某一特定用戶的聲譽信任對于系統(tǒng)中的其他所有用戶來說都是相同的。

定義2.交互信任：交互信任即交互來源所產(chǎn)生的信任，它是一個系統(tǒng)或集體中人與人之間的交際活動所產(chǎn)生的信任關系。交互信任是一種本地信任，這種信任值因人而異。

定義3.內(nèi)部信任：內(nèi)部來源所產(chǎn)生的信任，是由于兩個人之間內(nèi)在品質(zhì)（如性格、品味、理想等）的相似性產(chǎn)生的信任關系。

2.2 層次化信任度計算模型

根據(jù)圖2.1得到層次化信任度計算模型的抽象數(shù)學表達式如等式（3.1）所示：

（2.1）

在公式（2.1）中，Trust（A，W）代表用戶A對用戶W的總體信任值，它由聲譽信任值、交互信任值和內(nèi)部信任值加權求和得到。a、b、c為經(jīng)驗參數(shù)，它們之間滿足：a，b，c>0，a+b+c=1；R（W）表示用戶W在系統(tǒng)中的聲譽信任值，使用E-PageRank對其進行計算；IT（A，W）表示用戶A和用戶W之間的交互信任值；Sim（A，W）表示用戶A用戶W由于相似性而產(chǎn)生的信任值，即內(nèi)部信任值。

2.3 社交網(wǎng)絡的抽象表示

本文參考文獻[6，10]中基于有向加權圖計算用戶之間信任值的做法，將社交網(wǎng)絡抽象成有向加權圖。從圖論的角度來看，一個社交網(wǎng)絡可以抽象表示為有向加權圖G（U，E，W），U為所有節(jié)點的集合代表所有的用戶；E為網(wǎng)絡中的有向邊集合，位于有向邊起點的節(jié)點稱為源節(jié)點，反之為目標節(jié)點，有向邊的方向表示相鄰節(jié)點之間的信任關系。W為權重，本文規(guī)定權重的范圍為[1，10]。

圖2.2中，節(jié)點B信任節(jié)點A，節(jié)點A信任節(jié)點D，那么節(jié)點B就會在一定程度信任節(jié)點D，節(jié)點B對節(jié)點的信任程度將在后文中使用E-PageRank和M-MoleTrust進行計算，在此不做贅述。

圖2.2 信任網(wǎng)絡初始狀態(tài)示意圖

2.4 聲譽信任值的計算

與傳統(tǒng)的PageRank不同，本文所涉及社交網(wǎng)絡中的每個外向鏈接（即信任關系）都有其權重，所以每一節(jié)點對其他節(jié)點貢獻的聲譽值應當按外向鏈接的權重比例去分配。將外向鏈接的權重引入后得到E-PageRank，如公式（2.2）所示：

其中 （2.2）

在公式（2.1）中，R（u）表示用戶u的聲譽值，Bu表示指向用戶u的所有用戶的集合，W（v，u）表示用戶v對用戶u的信任強度，O（v）表示節(jié)點v的某一外向鏈接的權重，∑O（v）表示節(jié)點v所有外向鏈接權重之和。c是取值[0，1]之間的一個標準化因子，E（u）是節(jié)點u的逃脫因子，本文取網(wǎng)絡中節(jié)點總數(shù)的倒數(shù)作為每一個節(jié)點的逃脫因子。經(jīng)計算得到聲譽值如表2.1所示：

表2.1 PageRank與E-PageRank聲譽值相比較

節(jié)點PageRankE-PageRank節(jié)點PageRankE-PageRank

A0.36570.3928G0.30740.3074

B0.25290.2598H0.36110.3698

C0.23950.2153J0.31190.3167

D0.28540.2938K0.24700.2281

E0.31460.3039W0.23900.2261

F0.25830.2608Z0.23970.2246

在圖2.2中節(jié)點A和H在連通整個圖的過程中起著更為重要的作用。在表2.1中節(jié)點A和H改進后的算法聲譽值更高，更符合社交網(wǎng)絡的實際情況。因此，本文將使用E-PageRank進行聲譽信任值的計算。

2.5 交互信任值的計算

交互是人的社會屬性，任何一個系統(tǒng)中的個體與他周圍的其它個體不斷地進行著交互，從而產(chǎn)生不同程度的信任。文獻[6]把用戶之間的通信次數(shù)作為兩個人之間信任度的度量依據(jù)，兩人之間通信次數(shù)越多，表示兩人越熟悉對方，他們之間的信任強度也就越強。本文基于帶權有向圖所表示的社會網(wǎng)絡，將源節(jié)點對目標節(jié)點的評分作為源節(jié)點對于目標節(jié)點的信任值。

圖2.3是修正的信任網(wǎng)絡，本文將該修正的信任網(wǎng)絡模型視為一個具有層次關系的有向圖。在圖的最上層是當前用戶（本例中為用戶A）。

圖2.3 經(jīng)MoleTrust修正的信任網(wǎng)絡

而M-MoleTrust基于以下思想：1.決定待計算用戶信任度的是他的直接上層用戶和當前用戶；2.隨著信任的逐層傳播，信任值會不斷衰減，即隨著人與人之間距離的增加，他們之間的相對信任度在降低。為實現(xiàn)上述目的，本文在MoleTrust的信任度計算公式中引入一個遞減因子ω，其計算方式如公式（2.3）所示，其中p代表predecessors。

，=，（2.3）

表2.2為用戶A對其他節(jié)點的信任值計算結果對比。可以看出M-MoleTrust所計算的用戶A對其他用戶的信任值從第2層開始迅速衰減，這符合人們的正常社交習慣。M-MoleTrust計算結果更貼近實際，所以本文采用M-MoleTrust計算交互信任值。

表2.2 MoleTrust與M-MoleTrust 結果對比

節(jié)點所在層MoleTrustModifed-MoleTrust

A01.00001.0000

B10.40000.4000

E10.50000.5000

C10.30000.3000

D10.60000.6000

F20.42220.3800

K20.10000.0500

G20.70000.2100

H20.60000.3600

J20.40000.2400

W30.40000.2280

Z30.46000.2760

2.6 內(nèi)部信任值的計算

用戶相似度反應兩個用戶在興趣愛好、審美品味、性格特征甚至價值觀等方面的相似程度，這些都屬于人的內(nèi)在屬性，很難在短時間內(nèi)改變。本文將其稱為內(nèi)部信任。

本文選擇比較成熟的皮爾森相關系數(shù)作為內(nèi)部信任度的衡量指標。計算如公式（2.4）示，其中n表示用戶A和用戶W共同評分的項目數(shù)，r（K，i）表示用戶K對項目i的評分。

Similarity（A，W）=[n]/[

（2.4）

3.實驗及推薦評估

3.1 實驗所用數(shù)據(jù)介紹

本實驗所使用數(shù)據(jù)集來自網(wǎng)站Epinions，用戶可以在該網(wǎng)站對任何主題發(fā)表評價，或者對別人發(fā)表的評價再進行評價。在Epinions中用戶對項目的評分范圍是[1，5]，用戶對用戶的信任描述只有三種情況：信任（1）、不信任（-1）、無直接信任記錄（0）。

本試驗隨機抽取20%（364619條）用戶-項目評分記錄作為測試數(shù)據(jù)集，剩余的1458556條用戶-項目評分記錄和所有的用戶-用戶信任描述記錄作為訓練數(shù)據(jù)集。

3.2 層次化信任度計算模型性能評估

3.2.1 經(jīng)驗參數(shù)的確定

本文針對每一類型用戶按事先估計的參數(shù)范圍隨機生成50組參數(shù)，選擇能使預測評分的MAE最小的一組參數(shù)。本文參照文獻[1，3]的經(jīng)驗，將參數(shù)Trust Threshold、trust _propagation_ distance和trust_threshold設置為0.2、3與0.3。

圖3.1 普通用戶的經(jīng)驗參數(shù)分析圖

圖3.2 冷啟動用戶的經(jīng)驗參數(shù)分析圖

圖3.3 存在爭議用戶的其他用戶的經(jīng)驗參數(shù)分析圖

從上面的圖中可以得出，對于普通用戶參數(shù)a，b，c的最優(yōu)取值分別是0.3539、0.4018和0.2443，此時MAE取值為0.7160；

對于冷啟動用戶，參數(shù)a，b，c 的最優(yōu)取值分別是0.4289、0.4080 和0.1631，此時MAE為0.7201；存在爭議用戶的其他用戶，參數(shù)a，b，c的最優(yōu)取值分別是0.2013、0.4108和0.3879，此時MAE取值0.7091。

3.2.2 模型預測推薦能力評估

下圖以MAE為縱坐標來比較不同算法對于不同用戶群體推薦結果的準確性。層次化信任模型對四類用戶的MAE值都有不同程度的降低，提高了預測的準確度。相對協(xié)同過濾而言基于信任的推薦算法在較大程度上提高了推薦的準確性，再次證明將信任機制引入推薦系統(tǒng)是解決推薦系統(tǒng)固有頑疾的嶄新思路。

圖3.4 四種推薦算法的準確性對比

本文使用衡量系統(tǒng)推薦能力的指標High Rating Coverage對本文所提模型的推薦能力進行評估。如圖3.5，對協(xié)同過濾而言，基于信任的推薦技術在推薦能力方面有小幅提升，特別是對冷啟動用戶，M-MoleTrust將其High Rating Coverage提高了30.70%，E-PageRank提高了61.30%，層次化信任模型提高了39.82%。

圖3.5四種推薦算法的推薦能力對比

4.結論與展望

本文通過研究得出以下結論：1.將信任機制應用到推薦系統(tǒng)能夠緩解冷啟動、數(shù)據(jù)稀疏等問題；2.本文所提出的層次化信任度計算能夠在較大幅度提高推薦系統(tǒng)推薦質(zhì)量的同時為更多的用戶提供推薦服務。由于學識和水平有限，本文的研究從廣度和深度上都有局限之處，在未來的研究中可以將不信任引入，以期達到更優(yōu)質(zhì)的推薦效果。

致 謝

感謝我的導師高迎副教授以及我的學長康永勝，他們的指導對提高本論文水平有很大幫助！

參考文獻：

[1] Massa P，Avesani P.Trust-aware collaborative filtering for recommender systems// International Conference on Cooperative Information Systems，Larnaca，Cyprus，2004：492-508

[2] Massa P，Bhattacharjee B.Using Trust in Recommender Systems：An Experimental Analysis//Second International Conference，Oxford，UK，2004：221-235

[3] Massa P，Avesani P.Trust metrics on controversial users：balancing between tyranny of the majority and echo chamber.International Journal on Semantic Web and Information Systems（IJSWIS），2007：39-64.

[4] Massa P，Avesani P.Controversial users demand local trust metrics：An experimental study on epinions.com community //Proceedings of the National Conference on artificial Intelligence，Pittsburgh，USA，2005：121-126.

[5] Page L，Brin S，Motwani R，et al.The PageRank citation ranking：bringing order to the web.1999.

[6] 喬秀全，楊春，李曉峰，等.社交網(wǎng)絡服務中一種基于用戶上下文的信任度計算方法，計算機學報.2011：2403-2413

[7] Massa P，Avesani P.Trust-aware bootstrapping of recommender systems，ECAI Workshop on Recommender Systems.2006：29-33.

[8] Massa P，Avesani P.Trust metrics in recommender systems，Computing with social trust Springer London.2009：259- 285.

[9] Massa P，Avesani P.Trust-aware recommender systems// Proceedings of the 2007 ACM conference on Recommender systems，ACM，Minneapolis，Minnesota，USA 2007：17-24.

[10] Lo S，Lin C.Wmr--a graph-based algorithm for friend recommendation//Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence，IEEE Computer Society，HK，China，2006：121-128.