基于信任和近鄰評分填充的協(xié)同過濾算法

羅 群，鄧開發(fā)

(1. 上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093；2. 上海工程技術(shù)大學(xué) 藝術(shù)設(shè)計(jì)學(xué)院，上海 200093)

基于信任和近鄰評分填充的協(xié)同過濾算法

羅 群1，鄧開發(fā)2

(1. 上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093；2. 上海工程技術(shù)大學(xué) 藝術(shù)設(shè)計(jì)學(xué)院，上海 200093)

在傳統(tǒng)協(xié)同過濾推薦算法中隨著用戶的增多和商品數(shù)量急速增長，數(shù)據(jù)的稀疏性造成用戶相似度的計(jì)算準(zhǔn)確度越來越低。文中從考慮用戶之間的信任度出發(fā)，并在預(yù)測評分前，填補(bǔ)未評分項(xiàng)并再次迭代預(yù)測。以此提高協(xié)同過濾算法中計(jì)算用戶相似度的準(zhǔn)確度及預(yù)測準(zhǔn)確度。實(shí)驗(yàn)數(shù)據(jù)表明，該方法在一定程度上緩解了傳統(tǒng)協(xié)同過濾算法中數(shù)據(jù)稀疏性帶來的問題。

信任；評分填補(bǔ)；迭代預(yù)測

互聯(lián)網(wǎng)技術(shù)的發(fā)展使個(gè)性化推薦系統(tǒng)可以根據(jù)用戶本身的行為數(shù)據(jù)，分析用戶的興趣偏好，個(gè)性化地向用戶推薦他們感興趣的內(nèi)容。同時(shí)，個(gè)性化推薦系統(tǒng)具有重要的應(yīng)用價(jià)值，能為社會(huì)經(jīng)濟(jì)帶來一定的商業(yè)利益。據(jù)估計(jì)，亞馬遜電子商務(wù)推薦系統(tǒng)為其商品銷售量提高了35%[1]。協(xié)同過濾推薦算法使用廣泛，但也面臨諸多像評分?jǐn)?shù)據(jù)稀疏、冷啟動(dòng)、惡意評分等問題[2]。隨著社交網(wǎng)絡(luò)的發(fā)展，許多電子商務(wù)網(wǎng)站、社交網(wǎng)站和博客系統(tǒng)引入了信任機(jī)制，以克服傳統(tǒng)協(xié)同過濾算法中面臨的問題。

1 協(xié)同過濾算法中的信任

隨著Web2.0的興起，社交網(wǎng)絡(luò)蓬勃發(fā)展，引入信任機(jī)制也成為解決傳統(tǒng)協(xié)同過濾技術(shù)中問題的新方法。協(xié)同過濾推薦系統(tǒng)推薦效果的好壞在于其預(yù)測準(zhǔn)確性，影響準(zhǔn)確性的一個(gè)重要因素來自于近鄰選擇，在傳統(tǒng)協(xié)同過濾算法中近鄰的選擇只考慮用戶之間的相似性，實(shí)際上在人們生活中，人們更愿意從信任的朋友或有權(quán)威性的人那里獲得推薦，因此信任也是一個(gè)重要的有效參數(shù)。

在評價(jià)數(shù)據(jù)極端稀疏的情況下，加入信任機(jī)制的重難點(diǎn)就在于信任度如何度量。目前針對在協(xié)同過濾過程中考慮信任機(jī)制，國內(nèi)外已有了不少研究成果，但這些研究成果有一大部分是以相似性本身作為信任值的度量，例如基于信任模型的協(xié)同過濾推薦算法[3]，如文獻(xiàn)[3]，在文獻(xiàn)[4]中，將信任度加入了傳統(tǒng)協(xié)同過濾算法，其將信任度分為局部信任度和全局信任度進(jìn)行計(jì)算，最后將信任度和相似度進(jìn)行混合[4]，在一定程度上緩解了數(shù)據(jù)稀疏性問題，但其對信任度的度量方式不夠全面。本文將從直接信任度和間接信任度的角度來計(jì)算用戶間的信任度。其中，直接信任度考慮兩方面的因素：用戶價(jià)值度和用戶評價(jià)權(quán)威度。這兩點(diǎn)的度量參考標(biāo)準(zhǔn)來自于用戶本身的評分記錄，通過一定的方法分析用戶的評分記錄，得到用戶價(jià)值度和用戶評價(jià)權(quán)威度，進(jìn)而得到用戶的綜合信任值，在此基礎(chǔ)之上通過代表用戶本身屬性的綜合信任值，在用戶之間建立起相互的直接信任度；根據(jù)信任的傳遞性，兩個(gè)沒有直接交互關(guān)系的用戶之間也可能因?yàn)楣餐男湃螌ο蠼⑵痖g接信任度，本文中利用Golbeck的信任繁殖算法計(jì)算用戶之間的間接信任度。

2 協(xié)同過濾算法

算法基本思路流程圖，如圖1所示。

圖1 基于信任和近鄰填補(bǔ)的協(xié)同過濾算法流程圖

步驟1 建立用戶-評分矩陣。將用戶對項(xiàng)目的評分，用矩陣進(jìn)行表示，未評分項(xiàng)目用0填充；

步驟2 采用Pearson相似度計(jì)算公式計(jì)算用戶相似度，得到用戶相似度矩陣SM×M,相似度計(jì)算公式如下

(1)

步驟3 (1)計(jì)算用戶間的直接信任度，考慮因素：用戶價(jià)值度，用戶評價(jià)權(quán)威性；

1)用戶價(jià)值度。首先，在現(xiàn)實(shí)生活中，當(dāng)人們詢問他人意見時(shí)，會(huì)遇到兩種情況：很熱情，愿意回復(fù)問題并給出建議的人會(huì)慢慢贏得更多的信任；而相反，不喜歡回應(yīng)問題的人將會(huì)逐漸不再被信任。同樣的，一些用戶在系統(tǒng)中是活躍的，愿意給項(xiàng)目做評分；而一些用戶是懶惰和被動(dòng)的，往往不愿為系統(tǒng)作一個(gè)貢獻(xiàn)提供評價(jià)，而僅希望得到系統(tǒng)的建議。因此，在協(xié)同過濾推薦系統(tǒng)中，可認(rèn)為積極活躍的用戶比懶惰被動(dòng)的用戶承擔(dān)的信任因素更多[5]。同時(shí)，根據(jù)“見多識廣”的說法，一個(gè)用戶對系統(tǒng)中項(xiàng)目的評分越多，其評價(jià)將更有參考價(jià)值，對其他用戶來說其信任度也越高。所以，用戶在系統(tǒng)中的評分?jǐn)?shù)量決定了用戶的價(jià)值度。

用戶價(jià)值度定義用H表示，“||”表示集合中元素的個(gè)數(shù)，則用戶價(jià)值度的計(jì)算公式如下

(2)

其中，H∈[0,1]，Au={i∈I|ru,i≠0}是用戶u已經(jīng)評分的項(xiàng)目集合，I為系統(tǒng)項(xiàng)目集合。當(dāng)用戶在系統(tǒng)中的評分?jǐn)?shù)量超過閾值，則此用戶的可信度較高，其價(jià)值度為1；當(dāng)用戶在系統(tǒng)中的評分?jǐn)?shù)量沒有達(dá)到一定數(shù)量，則此用戶的價(jià)值度為其評價(jià)數(shù)量與閾值的比值；當(dāng)用戶在系統(tǒng)中的評分?jǐn)?shù)量非常稀疏遠(yuǎn)小于閾值，則其參考價(jià)值較低，其用戶信任度無限接近于0；

2)用戶評價(jià)權(quán)威度。逐個(gè)評估用戶評分項(xiàng)目的評分質(zhì)量，有效的減小惡意評分帶來的不良影響。評分質(zhì)量高的用戶，其權(quán)威性高，同時(shí)其可信任度高。

用戶評價(jià)權(quán)威度用A表示，則用戶權(quán)威度計(jì)算公式如下

(3)

3)綜合信任值。以上獲得了用戶的價(jià)值度H和用戶的評分權(quán)威度A，綜合兩點(diǎn)因素，可得用戶的綜合信任值Trust，計(jì)算公式為

Trust=λ×H+(1-λ)×A

(4)

4)相互信任度。以上的計(jì)算都是針對于用戶自身，而信任的一大特點(diǎn)是非對稱性，因此，在此基礎(chǔ)上，應(yīng)該對兩個(gè)用戶u和v進(jìn)行交互，以此來建立對對方的信任度[6]。交互行為必須建立在兩個(gè)用戶u和v均進(jìn)行過評分的項(xiàng)目上，因此假設(shè)Iuv={i∈|ru,i≠0＾r(nóng)v,i≠0}。

同時(shí)，假設(shè)在建立相互信任度過程中，用戶u向用戶v詢問建議，當(dāng)用戶v給與的建議與用戶u自身的想法大致相同時(shí)，該建議就被視為有效建議，用戶u對用戶v的信任感就會(huì)加強(qiáng)。而如何判斷用戶v給的建議與用戶u自身的想法的偏差度呢 ，在此可利用綜合信任度Trust函數(shù)來得到用戶v本身的綜合信任值，在此基礎(chǔ)上，對用戶u進(jìn)行項(xiàng)目評分預(yù)測，預(yù)測函數(shù)如下

(5)

基于上述的這一過程，定義雙方的信任度函數(shù)

(6)

(2)計(jì)算間接信任度。信任傳播[7]是信任的一個(gè)重要的特征關(guān)系。在一個(gè)推薦的系統(tǒng)中，用戶的數(shù)目通常是較大的；用戶間直接互動(dòng)的機(jī)會(huì)是較小的，導(dǎo)致只有極少的用戶與目標(biāo)用戶直接相關(guān)聯(lián)。利用信任傳播可找到更多的鄰居同時(shí)解決數(shù)據(jù)稀疏的問題[1]。在實(shí)際環(huán)境中，用戶的評分項(xiàng)目通常較少，兩個(gè)用戶同時(shí)評價(jià)一個(gè)項(xiàng)目的情況更加罕見，因而需將少數(shù)的已經(jīng)存在的直接信任關(guān)系進(jìn)行繁殖，這樣可拓寬信任關(guān)系，也可在一定程度上緩解傳統(tǒng)協(xié)同過濾算法中的數(shù)據(jù)稀疏性問題。由于信任具有一定傳遞性[8]，假設(shè)，用戶u信任用戶m，用戶m信任用戶v，則可推測用戶u對用戶v具有一定的信任值。本文以此為基礎(chǔ)，參考Golbeck創(chuàng)建的信任繁殖算法，用戶m對用戶v的間接信任度ITrust計(jì)算公式如式(7)

(7)

在式(7)計(jì)算中，也保證了在信任繁殖過程中，用戶之間的直接信任是用戶間最重要的信任來源。

(3)計(jì)算綜合信任度。結(jié)合用戶u,v的直接信任度MTrust(u，v)和間接信任度ITrust(u,v)，得到用戶u和用戶v之間的最終信任度[9]

ZTrust(u,v)=α×MTrust(u,v)+(1-α)×ITrust(u,v)

(8)

其中，協(xié)調(diào)因子α也是動(dòng)態(tài)取值，在實(shí)際運(yùn)行中條件的改變引起其值得變化，這樣也增強(qiáng)了適應(yīng)性，α的取值表達(dá)式如下

(9)

根據(jù)綜合計(jì)算度計(jì)算公式計(jì)算出兩兩用戶間的信任值，得到信任矩陣TM×M；

步驟4 合并相似矩陣SM×M和信任矩陣TM×M，得到信任相似矩陣STM×M；

用戶相似矩陣和用戶信任矩陣均具有一定的稀疏性，通過一定規(guī)則，將兩者進(jìn)行合并得到信任相似矩陣，可在一定程度上降低矩陣的稀疏性；同時(shí)將相似度和信任度同時(shí)考慮，可提高尋找近鄰的準(zhǔn)確性，提高用戶對推薦效果的滿意度，合并規(guī)則為

(10)

步驟5 選擇最近鄰居；

根據(jù)矩陣 ,選擇與目標(biāo)預(yù)測用戶信任相似度最高的前N個(gè)用戶作為目標(biāo)用戶的近鄰集合U[10]；

步驟6 預(yù)測評分。

根據(jù)已經(jīng)確定的近鄰集合及其對目標(biāo)評分項(xiàng)目的評分記錄，根據(jù)以下公式預(yù)測評分[11]，由于選擇出的大多數(shù)近鄰很有可能對目標(biāo)項(xiàng)目也沒有進(jìn)行評分，而這些近鄰?fù)瑫r(shí)又與目標(biāo)用戶信任相似度較高，即其對預(yù)測評分權(quán)重很高，影響較大，若在計(jì)算時(shí)直接用0來作為其評分，會(huì)給推薦結(jié)果帶來很大的誤差[12]，所以在這里考慮對其使用本文中的算法，迭代預(yù)測評分來填補(bǔ)近鄰中未評分項(xiàng)目

(11)

步驟7 產(chǎn)生推薦。

根據(jù)最終的預(yù)測評分，選擇目標(biāo)用戶未評分項(xiàng)目中，預(yù)測評分最高的前N個(gè)項(xiàng)目推薦給用戶[13]。

3 實(shí)驗(yàn)分析

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

為驗(yàn)證本文方法的有效性，實(shí)驗(yàn)選取網(wǎng)上公開數(shù)據(jù)集MovieLens 數(shù)據(jù)集中的100 kB數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù), MovieLens數(shù)據(jù)集中收集了943 個(gè)用戶對1 682部電影的100 000條評分記錄, 評分范圍在1～5之間代表了用戶對電影的喜愛程度。通過式(12)計(jì)算數(shù)據(jù)稀疏度為93.7%，可見該實(shí)驗(yàn)數(shù)據(jù)較為稀疏

(12)

3.2 度量標(biāo)準(zhǔn)

將數(shù)據(jù)集劃分為訓(xùn)練集和測試集，80%的數(shù)據(jù)做為訓(xùn)練集，20%作為測試集[14]。用Java 編程實(shí)現(xiàn)上述算法。本文中使用廣泛使用的度量標(biāo)準(zhǔn)平均絕對誤差(MAE)[15]來驗(yàn)證推薦方法的性能，平均絕對誤差( MAE)代表了預(yù)測值的誤差，其具體計(jì)算方法就是測試集中的項(xiàng)目的預(yù)測評分與項(xiàng)目實(shí)際評分之間的差值絕對值的平均值。給定測試集中所有可用的N個(gè)項(xiàng)目的實(shí)際/預(yù)測評分?jǐn)?shù)據(jù)對，MAE 可表示為

(13)

3.3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)時(shí)，分別將鄰居用戶數(shù)量設(shè)置為 20、 30、40、 60、70、80 時(shí), 測試傳統(tǒng)協(xié)同過濾算法與基于信任和近鄰填補(bǔ)的協(xié)同過濾算法的平均絕對誤差 MAE 的變化情況。

圖2 MAE值的變化折線圖

在圖 2 中, 橫坐標(biāo)表示選取近鄰的個(gè)數(shù)，縱坐標(biāo)表示平均絕對誤差MAE。 由圖可知，利用所選數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，在鄰居數(shù)量為20時(shí)，因?yàn)猷従觽€(gè)數(shù)過少，MAE值較大，因此預(yù)測準(zhǔn)確率低，推薦效果較好。但隨著鄰居用戶數(shù)量的不斷增加，平均絕對誤差 MAE逐漸降低。但近鄰數(shù)達(dá)到一定數(shù)量時(shí)，MAE值不再明顯降低，推薦效果改變較小。從圖2數(shù)據(jù)可知，與傳統(tǒng)協(xié)同過濾算法相比，同時(shí)引入信任度和近鄰的填補(bǔ)能在一定程度上降低MAE，提高推薦精確度。

4 結(jié)束語

本文在傳統(tǒng)的協(xié)同過濾算法中引入信任，介紹了通過信任度和相似度兩個(gè)因素的結(jié)合來確定鄰居用戶，又將綜合信任度和相似度的混合值作為傳統(tǒng)計(jì)算時(shí)的推薦權(quán)重。從直接信任度和間接信任度兩個(gè)方面來計(jì)算信任度，接信任度通過用戶價(jià)值度和用戶評價(jià)權(quán)威度兩個(gè)角度度量，間接信任度通過直接信任度繁殖得到。并在找到鄰居用戶后對鄰居用戶的未評分項(xiàng)目用預(yù)測評分進(jìn)行填補(bǔ)，最后得到目標(biāo)用戶的目標(biāo)項(xiàng)目的最終預(yù)測評分。通過實(shí)驗(yàn)證明,本文提出的直接信任度度量方法合理，通過間接信任度的計(jì)算，也在一定程度上提高了綜合信任度的準(zhǔn)確度。且改進(jìn)后的算法能為目標(biāo)預(yù)測用戶找到更加精確的近鄰用戶，提高預(yù)測評分的準(zhǔn)確率，有效緩解數(shù)據(jù)稀疏問題, 提升推薦系統(tǒng)的推薦效果。

[1] Jun T, Ning Z. Collaborative filtering algorithm introduced factor of authority and trust[C]. PF,USA:International Conference on E-Business and E-Government,IEEE, 2010.

[2] 馬宏偉,張光衛(wèi),李鵬.協(xié)同過濾推薦算法綜述[J].小型微型計(jì)算機(jī)系統(tǒng),2009(7):1282-1288.

[3] 夏小伍,王衛(wèi)平.基于信任模型的協(xié)同過濾推薦算法[J].計(jì)算機(jī)工程,2011,37(21):26-28.

[4] 吳慧,卞藝杰,趙喆,等.基于信任的協(xié)同過濾算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,23(7):131-135.

[5] Guo Y, Cheng X, Dong D, et al. An improved collaborative filtering algorithm based on trust in e-commerce recommendation systems[C].MA,USA:International Conference on Management and Service Science,IEEE, 2010.

[6] 周璐璐.融合社會(huì)信任關(guān)系的改進(jìn)推薦系統(tǒng)[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(7):31-35.

[7] 譚學(xué)清,黃翠翠,羅琳.社會(huì)化網(wǎng)絡(luò)中信任推薦研究綜述[J].現(xiàn)代圖書情報(bào)技術(shù),2014(11):10-16.

[8] 陸坤,謝玲,李明楚.一種融合隱式信任的協(xié)同過濾推薦算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016(2):241-245.

[9] 吳應(yīng)良,姚懷棟,李成安.一種引入間接信任關(guān)系的改進(jìn)協(xié)同過濾推薦算法[J].現(xiàn)代圖書情報(bào)技術(shù),2015(9):38-45.

[10] 王國霞,劉賀平.個(gè)性化推薦系統(tǒng)綜述[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(7):66-76.

[11] 鄧愛林,朱揚(yáng)勇,施伯樂.基于項(xiàng)目評分預(yù)測的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào),2003,14(9):1621-1628.

[12] 楊興耀,于炯,吐爾根·依布拉音,等.基于信任模型填充的協(xié)同過濾推薦模型[J].計(jì)算機(jī)工程,2015(5):6-13.

[13] 郭艷紅.推薦系統(tǒng)的協(xié)同過濾算法與應(yīng)用研究[D].大連:大連理工大學(xué),2008.

[14] 夏培勇.個(gè)性化推薦技術(shù)中的協(xié)同過濾算法研究[D].青島：中國海洋大學(xué),2011.

[15] 張秀杰.基于信任偏好的個(gè)性化推薦[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,23(1):109-113.

CollaborativeFilteringAlgorithmBasedonTrustandNeighborsFilledRatings

LUO Qun1，DENG Kaifa2

(1. School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China; 2. School of Art and Design, Shanghai University of Engineering Science, Shanghai 200093, China)

As the number of users and items increases immediately, the sparsity of data decreases leading to lower calculation accuracy of user similarity. In this paper, the degree of trust between users is taken as the start point of consideration, pre-filling a prediction score for the selected neighbor-users’ ungraded items followed by a second iteration to improve the accuracy of calculating the user similarity and the prediction accuracy. Experimental data show that the method solves the traditional collaborative filtering algorithm problems caused by data sparsity.

trust; rating fill; iterative prediction

2016- 04- 07

羅群(1994-)，女，碩士研究生。研究方向：計(jì)算機(jī)應(yīng)用技術(shù)。鄧開發(fā)(1965-)，男，博士，教授，碩士生導(dǎo)師。研究方向：光信息與計(jì)算機(jī)處理等。

10.16180/j.cnki.issn1007-7820.2017.02.015

TP

A

1007-7820(2017)02-058-05