結(jié)合信任關(guān)系的用戶聚類協(xié)同過濾推薦算法①

孟 晗,高 岑,王 嵩,張琳琳,劉 念

1(中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)控制與工程學(xué)院,北京 100049)

2(中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所,沈陽(yáng) 110168)

引言

在大數(shù)據(jù)時(shí)代,互聯(lián)網(wǎng)給用戶帶來了大量信息,但隨著網(wǎng)絡(luò)的不斷發(fā)展和信息的迅速增長(zhǎng),用戶在浩瀚數(shù)據(jù)中想要找到所需信息將會(huì)愈發(fā)困難,出現(xiàn)了信息超載問題.目前,解決信息超載一個(gè)非常高效的方法就是推薦系統(tǒng).推薦系統(tǒng)簡(jiǎn)單來說就是一種信息過濾系統(tǒng),用于預(yù)測(cè)用戶對(duì)物品的喜愛程度.在推薦系統(tǒng)中,協(xié)同過濾(Collaborative Filtering)技術(shù)是推薦系統(tǒng)中應(yīng)用最早和最為成功的技術(shù)之一,其核心是用戶的評(píng)分?jǐn)?shù)據(jù),與被推薦的內(nèi)容無關(guān),即:在閱讀歷史中對(duì)新聞評(píng)分相似的用戶在將來也會(huì)相似,從而把推薦轉(zhuǎn)換為評(píng)分預(yù)測(cè)問題[1].同時(shí),由于協(xié)同過濾具備發(fā)現(xiàn)用戶隱藏興趣的能力,并且可以有效的使用其他相似用戶的反饋信息,加快個(gè)性化學(xué)習(xí)速度,因此逐漸成為最受歡迎的推薦算法.

雖然協(xié)同過濾推薦技術(shù)有著廣泛的應(yīng)用,但是也存在很多問題,比如冷啟動(dòng)、數(shù)據(jù)稀疏等,因此研究人員不斷的對(duì)其進(jìn)行創(chuàng)新和改善.Lokhande 等[2]提出一種附加的層次聚類技術(shù),并且將主成分分析用于數(shù)據(jù)降維,提高了傳統(tǒng)CFRA 輸出的準(zhǔn)確性.Bobadilla等[3]研究了神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法在冷啟動(dòng)問題中的應(yīng)用.Zhou 等[4]提出了功能矩陣分解模型(functional matrix factorization),利用決策樹和矩陣分解的結(jié)合,在冷啟動(dòng)過程中為用戶選擇合適的物品進(jìn)行打分,從而盡可能準(zhǔn)確地理解用戶的偏好.

上述研究都是依托于已有的評(píng)分?jǐn)?shù)據(jù)進(jìn)行分析,但依托的這些數(shù)據(jù)并沒有考慮用戶間的信任關(guān)系,而一個(gè)良好的信任關(guān)系模型能夠有助于尋找相似度更高的近鄰用戶,從而得到更準(zhǔn)確的推薦結(jié)果.基于此,Yang 等[5]采用矩陣分解將用戶映射到低維特征空間的信任關(guān)系,更準(zhǔn)確的反映了用戶之間的相互影響.Xue 等[6]提出將用戶間的信任關(guān)系依據(jù)方差大小進(jìn)行量化形成調(diào)節(jié)因子的思想,算法將調(diào)節(jié)因子納入用戶相似性計(jì)算,形成相似性用戶聚類簇,但是上述算法沒有在真實(shí)應(yīng)用場(chǎng)景中實(shí)驗(yàn),并且忽略了用戶隱式信任關(guān)系導(dǎo)致實(shí)驗(yàn)結(jié)果不完整.Du 等[7]創(chuàng)新了社會(huì)學(xué)領(lǐng)域的信任關(guān)系計(jì)算,用其代替?zhèn)鹘y(tǒng)的相似度計(jì)算方法,將信任度集成到最近鄰居選擇中.信任網(wǎng)絡(luò)是通過擴(kuò)展不同的路徑長(zhǎng)度來構(gòu)建的,用戶之間的信任值可以通過信任傳輸規(guī)則來獲得.

綜上所述,很多研究學(xué)者為了解決協(xié)同過濾存在的問題,都會(huì)考慮降維、矩陣分解、神經(jīng)網(wǎng)絡(luò)等方法.而本文從描述用戶關(guān)系入手,結(jié)合用戶屬性和信任傳遞設(shè)計(jì)了一種改進(jìn)的信任機(jī)制,然后融合到相似度算法中,使其能夠更好的反映用戶之間的關(guān)系,最后結(jié)合聚類算法,提高了推薦的精確度,同時(shí)解決了協(xié)同過濾的冷啟動(dòng)以及數(shù)據(jù)稀疏問題.

1 協(xié)同過濾推薦算法

協(xié)同過濾是目前應(yīng)用最廣泛的推薦算法,其基于系統(tǒng)中其他用戶的評(píng)分或行為進(jìn)行預(yù)測(cè)和推薦.這種方法認(rèn)為,如果兩個(gè)用戶對(duì)某些項(xiàng)目有著相同的評(píng)價(jià),那么他們可能會(huì)對(duì)其他項(xiàng)目也達(dá)成一致意見.

基本的協(xié)同過濾算法通常經(jīng)過以下幾個(gè)步驟:

步驟1.收集數(shù)據(jù)并建立用戶評(píng)分矩陣.矩陣中行代表用戶,列代表項(xiàng)目,元素值為具體的評(píng)分值,一般在0～5 之間,評(píng)分越大喜愛程度越高.

步驟2.計(jì)算每個(gè)用戶與其他用戶的相似度.皮爾遜相關(guān)系數(shù)是目前最常見的計(jì)算方式,其公式如下:

式中,a,b代表兩個(gè)用戶,Ra,i表示用戶a對(duì)項(xiàng)目i的評(píng)分,Ia,b表示用戶a,b共同評(píng)分的項(xiàng)目,,分別表示用戶a和b所有評(píng)分的平均值.

步驟3.尋找目標(biāo)用戶最近鄰.依據(jù)相似度選取與目標(biāo)用戶最相似的鄰居集合作為目標(biāo)用戶的最近鄰.

步驟4.生成推薦結(jié)果.根據(jù)確定好的鄰居集合,通過式(2)計(jì)算出預(yù)測(cè)值,最后依據(jù)預(yù)測(cè)評(píng)分的排序進(jìn)行推薦,得到最終的結(jié)果.

由上述算法可以看出,在整個(gè)計(jì)算過程中,最為核心的是相似度的計(jì)算以及最近鄰的選取,但是相似度計(jì)算公式中沒有考慮用戶間的隱性關(guān)系,也沒有考慮一個(gè)用戶本身的可信任度問題,更可預(yù)見的是,在推薦系統(tǒng)初始化時(shí),由于數(shù)據(jù)稀疏還會(huì)產(chǎn)生冷啟動(dòng)問題.同時(shí),最近鄰的選取上也過于簡(jiǎn)單化,容易出現(xiàn)推薦結(jié)果不準(zhǔn)確的情況.基于以上對(duì)傳統(tǒng)協(xié)同過濾算法的分析,本文將結(jié)合信任機(jī)制對(duì)相似度計(jì)算進(jìn)行改進(jìn),并且結(jié)合聚類算法對(duì)最近鄰的選取合理優(yōu)化.

2 信任關(guān)系

在推薦系統(tǒng)中,信任關(guān)系指的是目標(biāo)用戶對(duì)其他用戶評(píng)分可靠性的一種主觀認(rèn)可程度,認(rèn)可程度越高則信任關(guān)系越密切.一般來說,信任關(guān)系可以分為直接信任與間接信任.

2.1 直接信任

2.1.1 傳統(tǒng)的信任關(guān)系模型

已有的描述信任關(guān)系[8]是由初始信任度與交互權(quán)重相乘得到的,如式(3)所示.其中Init(a,b)為初始信任度,由式(4)表示,t表示用戶a和用戶b達(dá)到信任的最小交互次數(shù),參考文獻(xiàn)[8]的實(shí)驗(yàn)結(jié)果可設(shè)置t為80.Ia∩Ib表示兩個(gè)用戶的交互次數(shù).Cs表示成功交互次數(shù),所謂成功交互指兩個(gè)用戶在交互項(xiàng)目的評(píng)分差值小于2.Ca指的是交互總數(shù).

2.1.2 改進(jìn)的信任關(guān)系模型

改進(jìn)1.傳統(tǒng)的信任模型雖然可以成功表示兩個(gè)用戶的信任關(guān)系,但是忽略了惡意用戶或者傾向于給高低分的用戶,如果一個(gè)用戶比較嚴(yán)格,評(píng)價(jià)分?jǐn)?shù)普遍過高或者過低,則認(rèn)為其不是一般性用戶,此用戶在信任機(jī)制中的權(quán)重則應(yīng)該減少.因此這里我們引入一個(gè)用戶本身可信任度,公式如下:

其中,C(Rb=1,2)代表用戶b評(píng)價(jià)分?jǐn)?shù)為1和2的總次數(shù),C(Rb=4,5)代表用戶b評(píng)價(jià)分?jǐn)?shù)為4和5的總次數(shù).此式可以衡量出低分和高分之間的比例,若兩者相差較大證明該用戶趨向于高分或者低分,從而可信任度下降.將其融合到信任模型中得到式(6):

式(6)在原有的信任機(jī)制中引入用戶本身可信任度,經(jīng)過計(jì)算之后,如果打分比較正常的用戶,其信任度變化不大,而惡意用戶或者比較嚴(yán)格的用戶其信任度會(huì)有所下降,通過這種改進(jìn)有效地區(qū)分了兩種用戶對(duì)相似度計(jì)算的影響.

改進(jìn)2.增加兩個(gè)用戶的本身屬性到可信度中.一般而言,人們更傾向于相信與自己特征類似的群體.這里我們采取3 個(gè)用戶屬性融合到信任模型中,分別是用戶年齡、性別和職業(yè),這里參考文獻(xiàn)[9]及其實(shí)驗(yàn)結(jié)果,S(a,b),A(a,b),O(a,b)分別代表性別、年齡和職業(yè)的相似性,公式分別如下:

得到用戶之間的屬性相似性[9]如式(10)所示:

組合到信任模型最終得到直接信任公式為:

2.2 間接信任

由于評(píng)分矩陣一般都是稀疏矩陣,所以直接信任數(shù)據(jù)過于稀少,因此需要引入間接信任,即用戶間無直接信任關(guān)系,但存在至少一條可達(dá)路徑,從而建立的信任關(guān)系.間接信任用ITrust(a,b)來表示.根據(jù)六度分割理論可知信任傳遞最大路徑長(zhǎng)度為6,依據(jù)文獻(xiàn)[10]的研究設(shè)置信任傳遞最大路徑長(zhǎng)度d值為3.

假設(shè)用戶a和b之間存在至少一條路徑,則路徑集合表示為Paths(a,b)={p1(a,b),p2(a,b),···,pn(a,b)}每條路徑可表示為pi(a,b)=(ai,ci1,ci2,···,bi).每條路徑權(quán)重αi隨路徑長(zhǎng)度呈遞減趨勢(shì),計(jì)算方式如式(12)所示,其中dpi(a,b)表示第i條路徑的長(zhǎng)度:

則每條路徑的信任度可表示為:

由此得到間接信任模型如式(14)所示,其中n表示用戶a和用戶b可以可達(dá)路徑總數(shù),最終得到的用戶a和b的間接信任度通過取平均值的方式計(jì)算得出.

2.3 融合信任模型

融合信任模型指的是由直接信任和間接信任采用加權(quán)因子融合而成,用來綜合考慮用戶間信任關(guān)系的一種評(píng)估方式,其中的加權(quán)因子 λ取值在0?1 之間,用來衡量?jī)蓚€(gè)信任度的權(quán)重,其計(jì)算公式如式(15)所示:

最后通過計(jì)算參數(shù)值,得到最終的信任模型Trust(a,b)如式(16)所示:

3 相似度算法改進(jìn)

3.1 融合熱點(diǎn)的皮爾遜相關(guān)系數(shù)

由第1 節(jié)介紹可知目前大多是用皮爾遜相關(guān)系數(shù)進(jìn)行相似度的計(jì)算.但是該計(jì)算方式忽略了熱點(diǎn)新聞的影響程度,一條新聞越受歡迎,多個(gè)用戶共同點(diǎn)擊的概率就會(huì)越大,對(duì)相似度影響的權(quán)重就會(huì)越低,基于此,提出一種融合熱點(diǎn)的皮爾遜相關(guān)系數(shù)HS-P 如式所示:

其中,Ia,b代表用戶a和b共同評(píng)價(jià)過的項(xiàng)目集合Ra,i代表用戶a對(duì)項(xiàng)目i的評(píng)價(jià)值,為用戶a的評(píng)價(jià)平均值,Ci為用戶a和b共同評(píng)價(jià)的某個(gè)項(xiàng)目i的被評(píng)價(jià)次數(shù),為所有項(xiàng)目被評(píng)價(jià)次數(shù)的平均值.從上述,公式可以看出一個(gè)項(xiàng)目被評(píng)價(jià)的次數(shù)越多,則其在相似度計(jì)算中所占權(quán)重越低.

3.2 最終的用戶相似度公式

結(jié)合第2 節(jié)的用戶信任關(guān)系以及上述的HS-P 公式,得到最終改進(jìn)的衡量用戶間相似度公式為:

4 算法過程描述

4.1 用戶聚類迭代算法

依據(jù)之前對(duì)相似度算法的改進(jìn),可以將其用到聚類算法之中,通過不斷迭代的方式調(diào)整用戶聚類簇,讓其達(dá)到穩(wěn)定,這種方式可以更加準(zhǔn)確的尋找到目標(biāo)用戶的最近鄰.具體的算法步驟如算法1 所示.

4.2 推薦算法整體流程

本文的算法整體流程如圖1所示.當(dāng)用戶聚類算法迭代完成,也就是用戶聚類集合趨于穩(wěn)定之后,再尋找最近鄰的可靠性就會(huì)大大增加.假設(shè)查找目標(biāo)用戶a的k個(gè)鄰居,首先計(jì)算用戶a與所有聚類中心的相似度,然后優(yōu)先選取相似度最高的聚類,計(jì)算a與該聚類中各個(gè)用戶的相似度,選取前k個(gè)即為最近鄰,記為UKN(a),則用戶a對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分為:

圖1 算法整體流程圖

最終通過預(yù)評(píng)分公式預(yù)測(cè)出目標(biāo)用戶a對(duì)項(xiàng)目的評(píng)分值,選取評(píng)分值最高的前N個(gè)項(xiàng)目作為推薦結(jié)果.

算法1.用戶聚類迭代算法輸入:用戶集合U,評(píng)分矩陣Rm×n輸出:調(diào)整后的用戶聚類(1)首先用K-mean 聚類算法對(duì)初始的用戶集合進(jìn)行聚類,得到初始用戶聚類和初始用戶聚類中心為(2)//迭代得到最佳用戶聚類集合repeat for each user Ui∈U UC={UC1,UC2,···,UCk} C={C1,C2,···,Ck}for each user cluster Cj∈C計(jì)算Ui與聚類中心Cj的相似度USim(Ui,Cj)end for US im(Ui,Ct)=max{sim(Ui,C1),···,sim(Ui,Ck)}Ui 所屬聚類UCs=UCs-Ui UCt=UCt+Ui end for for each UCi∈UC更新聚類中心Ci until 聚類簇中元素不再變化或者達(dá)到設(shè)定迭代次數(shù)

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)選擇了明尼蘇達(dá)大學(xué)GroupLens 項(xiàng)目組收集的MovieLens 數(shù)據(jù)集,該數(shù)據(jù)包含了943 位用戶對(duì)1682 部電影的十萬(wàn)條打分記錄,打分標(biāo)準(zhǔn)從1 到5,經(jīng)過計(jì)算得到稀疏度達(dá)到了93.7%.另外,該數(shù)據(jù)集還包含了用戶的特征屬性信息,滿足本文對(duì)信任關(guān)系的改進(jìn)要求.實(shí)驗(yàn)時(shí)隨機(jī)選取數(shù)據(jù)集中的80%作為訓(xùn)練集,20%作為測(cè)試集.

5.2 實(shí)驗(yàn)評(píng)分標(biāo)準(zhǔn)

實(shí)驗(yàn)標(biāo)準(zhǔn)采取均絕對(duì)誤差MAE(Mean Absolute Error)進(jìn)行評(píng)估,該值是用來衡量預(yù)測(cè)值與真實(shí)值之間的誤差,值越小,誤差就越小,推薦的準(zhǔn)確率也就更高.其計(jì)算公式為:

其中,n表示預(yù)測(cè)的項(xiàng)目個(gè)數(shù),Pi表示預(yù)測(cè)的評(píng)分值,Ri表示真實(shí)的評(píng)分值.

5.3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)1.在聚類算法中,首先需要確定好聚類的數(shù)值大小.這里采取傳統(tǒng)的用戶聚類協(xié)同過濾算法進(jìn)行實(shí)驗(yàn),其中迭代時(shí)計(jì)算用戶間相似度采用原始的皮爾遜相關(guān)系數(shù).聚類數(shù)值從10 增加到50,查看對(duì)應(yīng)的MAE值大小,實(shí)驗(yàn)結(jié)果如圖2所示.

圖2 不同聚類次數(shù)對(duì)應(yīng)的MAE 值

從圖2可以看出MAE值的變化隨著聚類數(shù)值的增大而縮小,當(dāng)K達(dá)到50 時(shí)MAE有最低值,這里考慮到算法效率問題,選取聚類數(shù)為50 進(jìn)行后續(xù)實(shí)驗(yàn).

實(shí)驗(yàn)2.對(duì)于用戶聚類迭代算法,不容易判斷何時(shí)聚類簇穩(wěn)定,因此需要考慮迭代次數(shù)對(duì)MAE的影響.實(shí)驗(yàn)中設(shè)定相似度權(quán)重因子μ=0.5,鄰居個(gè)數(shù)設(shè)置N=10,調(diào)整聚類迭代次數(shù)從1 到10,觀察不同迭代次數(shù)對(duì)MAE的影響如圖3所示.

從圖中可看出當(dāng)?shù)螖?shù)從7 開始MAE值保持穩(wěn)定,此時(shí)可以設(shè)定聚類簇達(dá)到穩(wěn)定狀態(tài).因此后續(xù)實(shí)驗(yàn)中,設(shè)定迭代次數(shù)為7 次.

圖3 不同迭代次數(shù)對(duì)應(yīng)的MAE 值

實(shí)驗(yàn)3.該實(shí)驗(yàn)的目的是確定式(15)中權(quán)重因子μ的取值,實(shí)驗(yàn)中確設(shè)定迭代次數(shù)為7 次,鄰居個(gè)數(shù)取值為10,圖4比較了當(dāng)μ 取值在0–1 之間時(shí)MAE的相應(yīng)值.

圖4 不同權(quán)重因子對(duì)應(yīng)的MAE 值

從圖4中可以看出,μ的值不宜過大或者過小,當(dāng)μ=0.6 時(shí),即信任關(guān)系占據(jù)權(quán)重0.6,HS-P 相似度算法占據(jù)權(quán)重0.4 時(shí),MAE有最低值,此時(shí)推薦結(jié)果最準(zhǔn)確.

實(shí)驗(yàn)4.為了驗(yàn)證本文提出的結(jié)合信任關(guān)系的用戶聚類協(xié)同過濾推薦算法(K-TUBCF),實(shí)驗(yàn)選取了幾個(gè)傳統(tǒng)算法[10]比較它們的MAE值,算法包括傳統(tǒng)的基于用戶的協(xié)同過濾算法(UBCF),基于K-means 聚類的協(xié)同過濾推薦算法(K-UBCF),融入傳統(tǒng)信任關(guān)系的協(xié)同過濾算法 (TUBCF),融入用戶喜好度到信任關(guān)系中的協(xié)同過濾算法(WTUBCF),最終結(jié)合文獻(xiàn)[8,10]的數(shù)據(jù)得出實(shí)驗(yàn)對(duì)比結(jié)果如圖5所示.

從圖5中可以看出,這幾種算法隨著鄰居個(gè)數(shù)的增加MAE值逐漸下降,并且在鄰居個(gè)數(shù)達(dá)到30 時(shí)趨于穩(wěn)定,說明鄰居個(gè)數(shù)N=30 時(shí)會(huì)取得最好的推薦結(jié)果.

另外,本文提出的算法在MAE值上明顯低于之前的各類算法,說明本文這種基于改進(jìn)信任關(guān)系的用戶聚類算法可以有效的提高算法準(zhǔn)確度,產(chǎn)生更準(zhǔn)確的推薦結(jié)果.

圖5 不同算法之間的比較

6 結(jié)論

本文提出的結(jié)合信任關(guān)系的用戶聚類協(xié)同過濾推薦算法,在直接信任與間接信任兩個(gè)層面上都做了一定改進(jìn),并且有效的結(jié)合用戶的屬性特征.另外,對(duì)于傳統(tǒng)的皮爾遜相似度忽略熱點(diǎn)新聞的缺點(diǎn)進(jìn)行了補(bǔ)充,最后采用迭代的聚類算法求出最近鄰從而得到更為準(zhǔn)確的推薦結(jié)果.實(shí)驗(yàn)也證明所提出的優(yōu)化算法比之前的算法誤差值更小.但是文章沒有考慮到時(shí)間對(duì)推薦的影響,下一步將結(jié)合時(shí)間因子對(duì)推薦算法進(jìn)行更詳細(xì)的研究,使其更加滿足實(shí)際情況.