一種帶偏置的專家信任推薦算法

王建芳,劉冉東,劉永利

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

1 引 言

推薦系統(tǒng)[1,2]的基本功能是利用用戶對項目的歷史評價信息產(chǎn)生推薦,大數(shù)據(jù)[3]時代用戶接觸的信息呈指數(shù)級,實際操作過程中,由于用戶精力有限,造成大量項目未得到評分,導(dǎo)致評價矩陣極為稀疏.傳統(tǒng)協(xié)同過濾[4]算法的稀疏用戶(評價項目相對較少的用戶)評分預(yù)測準(zhǔn)確度較低,如何提高稀疏用戶的推薦準(zhǔn)確性成為比較熱門的研究課題.

針對稀疏用戶評分預(yù)測問題,常采用的處理方法有:

1)數(shù)據(jù)平滑算法[5]:對用戶尚未評分的項目進行填充.文獻[6]運用其他用戶對該項目的評分均值填充缺省值.文獻[7]將用戶信息聚類后,以分類用戶的評分來填充缺省值.

2)專家算法:把項目按類別劃分,找到每個類別的專家,利用專家評分預(yù)測用戶對項目評分.文獻[8]提出了把專家算法與傳統(tǒng)協(xié)同過濾技術(shù)相結(jié)合.文獻[9]提出了“明星用戶”的算法,在評分預(yù)測階段加權(quán)平均所有“明星用戶”的評分.

以上兩類算法,一定程度上緩解了稀疏用戶評分預(yù)測準(zhǔn)確性不高的問題,但是計算得到稀疏用戶與用戶,稀疏用戶與各個“專家”之間的相似度區(qū)分不明顯,無法合理利用用戶與專家的預(yù)測信息.鑒于此,本文提出IBETA算法(Improved With Biased Expert Trust Algorithm,IBETA),該算法在專家算法的基礎(chǔ)上添加專家信任,在評分形成的過程中區(qū)別對待不同級別專家的預(yù)測值,同時將獨立于用戶-項目評分以外的因素添加到評分預(yù)測公式中,使預(yù)測值更加合理.

2 相關(guān)工作

2.1 專家算法

定義1.對于A類項目,專家Ec被定義為:

Iu≤Iv(?u∈U-Ec,?v∈Ec)

(1)

其中,Iu是指用戶u評價所有項目的集合,Iv是指“專家”v評價的項目集合,U是所有用戶集合.統(tǒng)計每個用戶評價A類項目數(shù)量,當(dāng)用戶評價項目的數(shù)量使公式(1)成立時,該用戶被定義為“專家”.

2.2 生成推薦值

Cho[10]提出的“專家算法”在計算預(yù)測評分時,采用無條件相信專家的策略-EA(Expert Algorithm,EA),評分預(yù)測采用公式(2).

(2)

需要預(yù)測的項目屬于多個類別時,采用公式(3)計算評分值.

(3)

其中,Ci是項目所屬的類數(shù),Pu,i,c是每一類預(yù)測的值.

以上預(yù)測評分算法的運行時間復(fù)雜度較低,但稀疏用戶評分預(yù)測準(zhǔn)確性較低,原因是該算法在項目確定的情況下,對于不同用戶的預(yù)測分?jǐn)?shù)幾乎是一樣的,因為專家的選擇只考慮了當(dāng)前用戶需要預(yù)測的項目;在選定專家集合中,同等對待每個專家的預(yù)測值.專家的專業(yè)水平有高有低,以上算法顯然有失偏頗.

Breeze[10]提出“專家與相似結(jié)合算法”在計算預(yù)測評分時,采用把專家看成某種意義上的近鄰,在預(yù)測評分時根據(jù)專家與當(dāng)前用戶相似度[11]的大小賦予不同的權(quán)重值ESA(Expert Similarity Algorithm,ESA),評分預(yù)測采用公式(4).

(4)

其中,Su,v表示專家與當(dāng)前用戶的相似度,與EA算法相比ESA算法對于不同的專家賦予了不同的權(quán)重值.隨著稀疏性的增加,稀疏用戶與各個專家的鄰近程度區(qū)分不明顯,計算量增加的同時稀疏用戶的推薦準(zhǔn)確性并沒有實質(zhì)性的提高.

2.3 Baseline 預(yù)測

評估一個策略的性能好壞,需要建立一個對比基線,在對比基線[13]的基礎(chǔ)上觀察后續(xù)試驗效果的變化.觀測到的評分?jǐn)?shù)據(jù)有一些和用戶無關(guān)的因素產(chǎn)生的效果,即一部分因素是和用戶對物品的喜好無關(guān)而只取決于用戶或物品本身的特性,例如,樂觀積極的用戶對于一些項目的評分普遍較高,而悲觀消極的用戶對項目的評分普遍較低,也就是說即使這兩類用戶對同一項目的評分相同,但是對物品的喜好程度確是不一樣的.對于項目來說道理是一樣的,受用戶歡迎的項目評分普遍較高,不受用戶歡迎的項目評分較低,加入偏執(zhí)信息[14]的評分預(yù)測公式如公式(5)表示:

R*(i,j)=μ+bu(i)+bu(j)

(5)

其中R*(i,j)表示用戶i對項目j的預(yù)測評分,μ為數(shù)據(jù)集的總體偏置信息,bu(i)表示用戶i的偏置信息,bu(j)表示項目j的偏置信息.假設(shè)項目的總體偏置為a,項目1的口碑普遍高于其他項目的值為b,如果u1是悲觀嚴(yán)謹(jǐn)?shù)?其bu(i)值為c,那么u1對項目1的預(yù)測值為a+b-c.

計算b(i)和b(j)的值,采用公式(6)、(7)求解.

(6)

(7)

其中,i表示用戶,j表示項目,I表示用戶i評價過的項目集合,μ為數(shù)據(jù)集的總體偏置信息,I表示集合的個數(shù),Ui表示評價過項目j的用戶集合,Ui表示集合的個數(shù),參數(shù)λ1,λ2需要實驗確定的值.

3 改進專家算法

從專家算法提出至今,許多研究人員都圍繞著利用專家與用戶、項目的關(guān)系提升推薦準(zhǔn)確度.但是現(xiàn)實生活中人們在參考權(quán)威人士的意見時,必然要考慮權(quán)威人士的可信度.到目前為止推薦系統(tǒng)沒有對“信任”[15]給出一個具體的概念.在可查資料中,信任是指接收推薦者對提供推薦者特定行為的主觀可能性預(yù)測.在社交網(wǎng)絡(luò)中信任需要考慮的因素有很多,完整的考慮各個方面難度很大且通常沒有太大必要,在面對同一個用戶時,只需要對該用戶所處的情形進行相應(yīng)的加強和減弱,以便于對對象之間的信任程度進行較好的量化.

3.1 改進專家信任

在推薦系統(tǒng)中存在著各種各樣的數(shù)據(jù),其中包括了評分?jǐn)?shù)據(jù)、項目屬性數(shù)據(jù)、用戶屬性數(shù)據(jù)等,這些數(shù)據(jù)基本構(gòu)成了本文需要的信任度量情境.充分考慮專家及用戶所在環(huán)境,本文用以下定義量化專家信任中涉及的重要概念.

定義2.專家評價可信度

一個專家評價的項目數(shù)量越多,可以從一定程度上反應(yīng)出其評價項目的質(zhì)量、可信度,度量專家評價可信度可以采用公式(8).

(8)

其中,Qall是指所有用戶,Qu代表專家u評價過的所有項目的集合,max(Qall)是指所有專家中評價項目的最大值.

定義3.專家專業(yè)度

咨詢專家意見之前,人們通常會考慮專家的專業(yè)度,專家并不是對所有種類的項目都具有全面的專業(yè)知識,在某種情況下,一名專家顯然只會對一個或者很少種類的項目上投入比較多的精力,具體表現(xiàn)為在某一類項目上評價比較多的項目,因此專家專業(yè)度用公式(9)表示.

(9)

其中,Tui表示專家已評價且屬于某一種類的所有項目集合,T為系統(tǒng)中獲得過用戶評價且屬于這一主題的所有項目集合.

定義4.專家評價偏差度

專家計算的預(yù)測評分與真實評分之間的差值為專家評價偏差度,如公式(10)所示.

(10)

基于以上表述專家的Du,Pu,Ru,權(quán)重系數(shù)w1,w2,w3及公式(11)計算專家信任值.

TRu=w1·Du+w2·Pu+w3·Ru

(11)

式(11)中權(quán)重系數(shù)需要采用原始專家算法CE矯正,調(diào)節(jié)原理是設(shè)置一個初始RMSE值,利用評分預(yù)測公式計算預(yù)測值并計算一次RMSE值,當(dāng)前RMSE值大于設(shè)定RMSE值時,利用控制變量法更新一次權(quán)重系數(shù),記錄每個參數(shù)達到最優(yōu)RMSE值時的值,最后歸一化處理三個參數(shù)得到最終權(quán)重系數(shù)值.

3.2 評分形成

由于傳統(tǒng)相似度計算對稀疏用戶基本失效,本文把專家可信度,用戶、項目偏置與專家算法相結(jié)合,如公式(12)所示生成預(yù)測值.

fu,c+bu(i)+bi(j)

(12)

其中,TRu表示專家可信度,Ci表示當(dāng)前項目所屬類別總數(shù),fu,c表示用戶u評價的c類項目占所有c類項目的百分比,bu(i)、bi(j)分別表示用戶U及項目i的偏置.該算法對于每個電影類別的專家評分,根據(jù)專家在此類別評價項目中信任值,加權(quán)計算預(yù)測評分,有效避免了不同類別專家對項目的評分同等對待的問題,根據(jù)專家信任值賦予不同專家不同的權(quán)重,在一定程度降低了預(yù)測誤差.確定專家依據(jù)的是用戶的歷史評價信息,在該過程中主觀因素起決定性作用,為了提升算法的健壯性,在形成評分的過程中需要考慮獨立于評分以外的客觀因素,本文把用戶、項目偏置引入到評分預(yù)測公式中,在改進專家算法形成評分的基礎(chǔ)上引入用戶、項目偏置,進一步提升了預(yù)測準(zhǔn)確性及合理性.

3.3 算法描述

輸入:評分矩陣R及項目類別矩陣T,RMSE閾值0.98,Round值.

輸出:預(yù)測矩陣Rpred.

算法步驟:

步驟1.數(shù)據(jù)預(yù)處理;baseline預(yù)測確定數(shù)據(jù)集上λ1,λ2的值;初始化w1,w2,w3.

步驟2.利用定義(1)確定每個類別的專家.

步驟3.根據(jù)評分偏差修正一次w1,w2,w3,直到出現(xiàn)最優(yōu)RMSE值.

fori=1:round

根據(jù)公式(2)計算預(yù)測值并計算RMSE值.

if(當(dāng)前RMSE值>設(shè)定RMSE值)

修正一次w1,w2,w3的值(控制變量法);

end

i++;

end

步驟4.根據(jù)公式(6)、(7)計算用戶、項目偏置.

步驟5.根據(jù)步驟2尋找到的專家及公式(12),形成預(yù)測值.

步驟6.產(chǎn)生預(yù)測矩陣Rpred.

4 實驗結(jié)果與分析

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

本實驗分別在Epinion、Ciao、Movielens三個數(shù)據(jù)集進行,這三個數(shù)據(jù)集都包含了用戶對項目的評分且分值分為1-5的離散值,數(shù)據(jù)集的具體信息如表1所示:

表1 實驗數(shù)集
Table 1 Data sets

數(shù)據(jù)集用戶數(shù)目項目數(shù)目評分?jǐn)?shù)MovieLens9431682100000Ciao7375106797284086Epinion22166296277922267

4.2 評估標(biāo)準(zhǔn)

評估推薦系統(tǒng)預(yù)測準(zhǔn)確性的標(biāo)準(zhǔn)分為決策精度標(biāo)準(zhǔn)和統(tǒng)計精度標(biāo)準(zhǔn)兩類.本文采取了對特大或特小誤差反應(yīng)敏感的均方根誤差(RMSE),在推薦系統(tǒng)中RMSE作為一種常用度量誤差標(biāo)準(zhǔn)被廣泛使用,其原理是通過計算用戶關(guān)于項目的預(yù)測值與真實值之間的偏差平方和與用戶個數(shù)n比值的平方根,如公式(13)所示.

(13)

其中,xi是代表預(yù)測值,x0代表與預(yù)測值對應(yīng)的真實值.

圖1 MovieLens數(shù)據(jù)集Baseline預(yù)測Fig.1 Baseline prediction of MovieLens 1M dataSets

圖2 Ciao數(shù)據(jù)集Baseline預(yù)測Fig.2 Baseline predictions of ciao data sets

圖3 Epinion數(shù)據(jù)集Baseline預(yù)測Fig.3 Baseline prediction of ciao data sets

4.3 實驗結(jié)果及分析

4.3.1 BaseLine預(yù)測

首先將數(shù)據(jù)集的90%作為訓(xùn)練集,其余的10%作為測試集,首先根據(jù)項目評分的平均值確定為數(shù)據(jù)集的總體偏置μ,其次根據(jù)公式(6)、(7)及初始化的λ1,λ2計算用戶及項目的偏置,調(diào)整λ1,λ2的值提高BaseLine預(yù)測RMSE值,選擇BaseLine預(yù)測的目的在于該算法的訓(xùn)練時間短,預(yù)測精度高,可以通過實驗訓(xùn)練得到最優(yōu)參數(shù).

如圖1是在Movielens數(shù)據(jù)集上做的Baseline預(yù)測,經(jīng)實驗發(fā)現(xiàn)當(dāng)λ1=3,λ2=6,RMSE達到最優(yōu),最小為值為0.964.

如圖2是在Ciao數(shù)據(jù)集上做的Baseline預(yù)測,經(jīng)實驗發(fā)現(xiàn)當(dāng)λ1=58,λ2=43,RMSE達到最優(yōu),最小為值0.976.

如圖3是在Epinions數(shù)據(jù)集上的Baseline預(yù)測,經(jīng)實驗發(fā)現(xiàn)當(dāng)λ1=53,λ2=56,RMSE達到最優(yōu),最小為值0.998.

4.3.2 用戶可信度指標(biāo)分布與分析

以MovieLens 1M數(shù)據(jù)集為例,圖4給出用戶專業(yè)度、評價可信度、評價偏差度的分布情況.其中58.21%的用戶專業(yè)度分布在[0,0.2]之間,56.4%的用戶評價可信度分布在[0,0.1]之間,說明多數(shù)用戶的專業(yè)度、評價可信度兩種指標(biāo)較低,少數(shù)用戶評價可信度能在全體的用戶評價可信度中體現(xiàn)個性化的特質(zhì).從圖4可以看出,用戶的評價偏差度分布幾乎成正態(tài)分布,評價偏差度分布在[0.2,0.6]的用戶所占比例為77.6%,說明用戶大多數(shù)用戶的評價偏差度就比較高(評價比較接近真實評分),以上足以說明選定專業(yè)用戶以后(專家),該專家對項目的評分信任度可以由以上三種指標(biāo)體現(xiàn).

圖4 評價指標(biāo)分布圖Fig.4 Distribution of evaluation index

4.3.3 稀疏用戶分布

對于大型數(shù)據(jù)集,稀疏用戶的數(shù)量比較大,圖5按照用戶評價項目數(shù)量,把MovieLens 1M數(shù)據(jù)集、Ciao數(shù)據(jù)集、Epinion數(shù)據(jù)集的用戶分為4類,可以看出三種數(shù)據(jù)集第一類用戶(本文視為稀疏用戶)占全部用戶的比例較大.

4.3.4 專家可信度分布與分析

以MovieLens1M數(shù)據(jù)集為例,圖6表示專家信任值隨著矯正次數(shù)的變化情況.在實驗開始階段,專家可信度指標(biāo)之間系數(shù)是初始化值,所以專家可信度比較低,隨著矯正次數(shù)的增加的專家信任值從100次矯正的0.12提升到0.63共經(jīng)過了400次的矯正,從400次開始專家信任值穩(wěn)定在[0.63,0.69]之間, 此時得出w1,w2,w3值分別為 0.31、0.46、0.23,在后續(xù)計算專家對此類別項目評分時,可以直接利用此訓(xùn)練后的系數(shù)值,但是對于不同類別的專家信任因子系數(shù)值不同,需要同樣的方法訓(xùn)練得到.

圖5 用戶評價項目數(shù)量分布圖Fig.5 Distribution of users who evaluate items

圖6 專家可信度分布圖Fig.6 Distribution of expert′s reliability

圖7 MovieLens 1M數(shù)據(jù)集上三種算法對比Fig.7 Three algorithms on MovieLens 1M DataSets

圖8 Ciao數(shù)據(jù)集上三種算法對比Fig.8 Three algorithms on Ciao DataSets

圖9 Epinion 數(shù)據(jù)集上三種算法對比Fig.9 Three algorithms on Epinion DataSets

4.3.5 在不同數(shù)據(jù)集上稀疏用戶預(yù)測對比

本文選定三中數(shù)據(jù)集的第一類為測試集,從圖8-圖9三幅圖可以明顯看出,在實驗開始階段三種算法針對稀疏用戶的預(yù)測準(zhǔn)確度較低,隨著專家人數(shù)的增加,相比于傳統(tǒng)的EA、ESA算法,本文提出的IBETA算法在三種數(shù)據(jù)集下RMSE有普遍提高,這其中的原因是隨著獨立于用戶與項目的偏置信息的加入,預(yù)測稀疏用戶的項目評分增加了客觀的預(yù)測值.隨著稀疏用戶評價項目的增多三種算法的預(yù)測準(zhǔn)確性都有明顯的上升趨勢,原因是隨著用戶評價項目的增多,相似性計算能夠更加明確的區(qū)分出用戶與專家之間的相似性,由近鄰算法的特點不難理解預(yù)測準(zhǔn)確性提升.

5 結(jié)束語

本文研究了專家算法的產(chǎn)生與改進,IBETA算法在ESA算法和EA算法的基礎(chǔ)上加入專家信任度用戶、項目偏置信息.實驗表明,改進后的帶偏置專家信任協(xié)同過濾推薦算法在稀疏用戶的預(yù)測準(zhǔn)確性方面有較大提高,但是,在算法的改進過程中專家信任指標(biāo)的融合還不夠完善.所以,下一步工作的重心將放在信任的動態(tài)調(diào)整及建立有效的信任傳遞機制,使信任度量更加合理.

[1] Adomavicius G,Tuzhilin A.Toward the next generation of recommender system[J].IEEE Transactions on Knowledge & Data Engineering,2005,17(6):734-749.

[2] Zhu Yang-yong,Sun Qian.Research progress of recommendation system[J].Computer Science and Exploration,2015,9(5):513-525.

[3] Mcafee A,Brynjolfsson E.Big data:the management revolution[J].Harvard Business Review,2012,90(10):60-66.

[4] Piao C H,Zhao J,Zheng L J.Research on entropy-based collaborative filtering algorithm and personalized recommendation in e-commerce[J].Service Oriented Computing & Applications,2009,3(2):147-157.

[5] Yu Feng-quan,Wang Xu-ming,Xie Yan-hong.Comparison of data smoothing algorithms for flight data processing[J].Command Control and Simulation,2015,(1):116-119.

[6] Deng Ai-lin,Zhu Yang-yong,Shi Bo-le.Collaborative filtering recommendation algorithm based on project score predicts[J].Journal of Software,2003,14(9):1621-1628.

[7] Wang Q M,Liu X,Zhu R,et al.A new personalized recommendation algorithm of combining content-based and collaborative filters[J].Computer & Modernization,2013,1(8):64-67.

[8] Hwang W S,Lee H J,Kim S W,et al.On using category experts for improving the performance and accuracy in recommender systems[C].ACM International Conference on Information and Knowledge Management,2012:2355-2358.

[9] Liu Qiang.Research on the key algorithm in collaborative filtering recommendation system[D].Zhejiang University,2013.

[10] Breese J S,Heckerman D,Kadie C.Empirical analysis of predictive algorithms for collaborative filtering[C].Fourteenth Conference on Uncertainty in Artificial Intelligence,2013:43-52.

[11] Cho J,Kwon K,Park Y.Collaborative filtering using dual information sources[J].IEEE Intelligent Systems,2007,22(3):30-38.

[12] Gouya G,Arrich J,Wolzt M,et al.Antiplatelet treatment for prevention of cerebrovascular events in patients with vascular diseases[J].A Journal of Cerebral Circulation,2014,45(2):492-503.

[13] Marinho L B,Hotho A,J?schke R,et al.Baseline techniques[M].US:Springer US,2012.

[14] Peng Fei,Deng Hao-jiang,Liu Lei.Add user ratings offset recommendation system model[J].Journal of Xi ′an Jiaotong University,2012,46(6):74-78.

[15] Shen Li-men,Wang Li-hua,Li Feng.An adaptive trust model based on time series analysis in opportunistic networks[J].Journal of Chinese Computer Systems,2015,36(7):1553-1558.

附中文參考文獻：

[2] 朱揚勇,孫 婧.推薦系統(tǒng)研究進展[J].計算機科學(xué)與探索,2015,9(5):513-525.

[5] 于鳳全,王旭明,謝彥宏.面向飛參數(shù)據(jù)處理應(yīng)用的數(shù)據(jù)平滑算法對比[J].指揮控制與仿真,2015,(1):116-119.

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

[9] 劉 強.協(xié)同過濾推薦系統(tǒng)中的關(guān)鍵算法研究[D].浙江大學(xué),2013.

[14] 彭 飛,鄧浩江,劉 磊.加入用戶評分偏置的推薦系統(tǒng)排名模型[J].西安交通大學(xué)學(xué)報,2012,46(6):74-78.

[15] 申利民,王立華,李 峰.機會網(wǎng)絡(luò)中基于時間序列分析的自適應(yīng)信任模型[J].小型微型計算機系統(tǒng),2015,36(7):1553-1558.