鄧小燕，張曉彬

1(重慶醫(yī)藥高等專科學(xué)校 醫(yī)學(xué)技術(shù)學(xué)院，重慶 401331)

2(重慶農(nóng)村商業(yè)銀行 科技信息部，重慶 400023)

協(xié)同過濾算法通過計(jì)算用戶的興趣相似性，篩選興趣最相近的用戶為鄰居為用戶推薦商品，是推薦系統(tǒng)研究的熱點(diǎn)[1，2].有學(xué)者將物質(zhì)擴(kuò)散和熱傳導(dǎo)理論[3-5]應(yīng)用于協(xié)同過濾推薦技術(shù)，取得了很好的效果，典型的是基于二部圖的協(xié)同過濾推薦研究，該算法令能量在“用戶-項(xiàng)目”以及“項(xiàng)目-其他用戶”間擴(kuò)散，擴(kuò)散完成后即獲取到準(zhǔn)確的鄰居用戶，預(yù)測評分更加準(zhǔn)確，已經(jīng)成為協(xié)同過濾領(lǐng)域研究的一個新方向[6]，不斷有學(xué)者在此基礎(chǔ)上研究新的改進(jìn)措施來進(jìn)一步提高推薦的準(zhǔn)確度.文獻(xiàn)[7]提出了一種基于隨機(jī)森林修正的加權(quán)二部圖推薦算法，首先建立評分權(quán)重矩陣，再用二部圖做能量分配，獲取到初始推薦結(jié)果，最后采用隨機(jī)森林對推薦結(jié)果進(jìn)行再次修正，提高了推薦的準(zhǔn)確度；文獻(xiàn)[8]提出了一種利用差異路徑權(quán)重控制能量傳遞的二部圖算法，該算法在第一階段能量傳遞時采用用戶相似性作為路徑權(quán)重，使與目標(biāo)用戶相似的用戶節(jié)點(diǎn)獲得更多的能量；在第二階段采用項(xiàng)目屬性的相似性作為路徑權(quán)重，使與目標(biāo)用戶已購項(xiàng)目具有相似屬性的項(xiàng)目獲得更多的能量，達(dá)到了提高推薦結(jié)果多樣性的目標(biāo)；文獻(xiàn)[9，10]綜合考慮項(xiàng)目度、用戶評分標(biāo)準(zhǔn)信息和時間動態(tài)因素，對二部圖上的用戶-項(xiàng)目關(guān)聯(lián)關(guān)系做了加權(quán)處理，推薦列表的平均絕對偏差和均方根誤差都有明顯下降.

1 基于加權(quán)二部圖的協(xié)同過濾推薦算法

二部圖是圖論中的一種特殊的無向圖，圖中頂點(diǎn)集合V 被劃分成V1 和V2 兩部分，且V1∩V2=φ，圖中的每條邊所關(guān)聯(lián)的兩個頂點(diǎn)都分別屬于這兩個頂點(diǎn)集[11-13].二部圖應(yīng)用于協(xié)同過濾推薦研究時，將用戶U={u1,u2,u3,···,up}和項(xiàng)目I={i1,i2,i3,···,iq}作為圖中兩個不相交的集合，用戶uw選擇過項(xiàng)目ik則在用戶和項(xiàng)目間連一條邊awk[14].基于二部圖的協(xié)同過濾推薦算法[3](BNCF)通過兩次能量分配計(jì)算鄰居用戶，假定每個用戶有一單位的能量，第一次分配時用戶把自己的能量平均分配給與其有連邊的項(xiàng)目；第二次分配時每個項(xiàng)目把自己獲得的能量平均分配回與其有連邊的用戶；經(jīng)過兩次能量分配后，用戶能量被分散到與其有共同項(xiàng)目頂點(diǎn)連邊的用戶節(jié)點(diǎn)上，用戶獲得的能量越多，說明用戶間興趣越相似[15]，用戶uv從用戶uw獲得的能量用engwv表示，計(jì)算方法如式(1)所示.

其中，d(uv)代表用戶uv選擇過的項(xiàng)目數(shù)，即二部圖中uv頂點(diǎn)的度；d(ik)代表項(xiàng)目ik被多少用戶選擇過，即二部圖中ik的度；awk代表用戶uw和項(xiàng)目ik間是否有連邊，若有，則awk=1；若沒有，則awk=0.engwv越高表示用戶uv和用戶uw共同選擇過的項(xiàng)目數(shù)越多，興趣越相似.按照engwv由高到低排列，選取前M個用戶作為鄰居用戶.最后，由鄰居用戶對當(dāng)前用戶進(jìn)行推薦，計(jì)算用戶uw對項(xiàng)目ik的評分rwk的方法如式(2)所示.

按rwk值由高到低排列，取前N項(xiàng)作為對用戶的最終推薦.

BNCF 算法在建立用戶-項(xiàng)目模型時僅考慮用戶是否選擇過項(xiàng)目，用戶選擇過某一個項(xiàng)目則說明用戶對該項(xiàng)目有偏好.這種假設(shè)具有很大的局限性，僅適用于粗略的用戶偏好統(tǒng)計(jì)，在基于用戶評分的體系中，用戶偏好劃分更加精細(xì)，BNCF 算法的推薦結(jié)果就不再準(zhǔn)確.例如在一個5 分等級的評價系統(tǒng)中，用戶對某一個項(xiàng)目給出5 分的評價說明用戶喜歡該項(xiàng)目，若用戶對某一個項(xiàng)目給出2 分的評價，則不能再認(rèn)為用戶喜歡該項(xiàng)目.為避免低分評價對判斷用戶偏好的影響，部分學(xué)者提出忽略低分評價、只考慮高分評價的算法，這種算法更加符合用戶偏好的實(shí)際，能取得更加準(zhǔn)確的評分預(yù)測結(jié)果.更進(jìn)一步地，部分學(xué)者認(rèn)為低分評價中也具有參考意義，不應(yīng)該直接丟棄，提出基于加權(quán)二部圖的協(xié)同過濾推薦算法，其中典型的是基于參數(shù)化的加權(quán)二部圖算法(PB-BNCF)和基于比例的加權(quán)二部圖算法(RB-BNCF).

1.1 基于參數(shù)化的加權(quán)二部圖算法

基于參數(shù)化的加權(quán)二部圖算法對圖中每條用戶—項(xiàng)目的連邊賦予一個權(quán)值e，當(dāng)用戶uw未評價過項(xiàng)目ik時，ewk=0；當(dāng)用戶uw對項(xiàng)目ik評分大于等于3時，ewk=1；當(dāng)用戶uw對項(xiàng)目ik評分小于3時，ewk=λ，其中λ 為可調(diào)因子，用于調(diào)節(jié)低分對推薦結(jié)果的影響，取值在 0 和1 之間，當(dāng) λ取值為0時，算法變成忽略低分評價的算法；當(dāng) λ取值為1時，算法變成只考慮用戶是否評價過項(xiàng)目的算法.用戶uv和用戶uw相似性使用式(3)計(jì)算.

其中，函數(shù)f表示對圖中某一頂點(diǎn)有連邊的權(quán)值進(jìn)行求和，即；.

計(jì)算用戶uw對項(xiàng)目ik的評分rwk的方法如式(4).

PB-BNCF 算法使用參數(shù) λ作為調(diào)節(jié)因子，控制低分評價對用戶偏好的影響，起到了提高推薦準(zhǔn)確度的效果，λ取值大小與數(shù)據(jù)集關(guān)系較大，需要通過大量數(shù)據(jù)分析取得適合具體數(shù)據(jù)集的最佳λ 值.

1.2 基于比例的加權(quán)二部圖算法

基于比例的加權(quán)二部圖算法考慮用戶評分習(xí)慣問題，部分用戶可能習(xí)慣性地給所有項(xiàng)目高分，而部分用戶習(xí)慣性地給所有項(xiàng)目低分，單純地以某一個絕對分值來判定用戶偏好不準(zhǔn)確，因此提出先對用戶評分?jǐn)?shù)據(jù)按照式(5)進(jìn)行處理.

計(jì)算用戶uw對項(xiàng)目ik的評分rwk的方法如式(7).

RB-BNCF 算法通過數(shù)據(jù)預(yù)處理消除了用戶評分習(xí)慣對分析用戶偏好的影響，并且不需要輸入控制參數(shù)，對不同數(shù)據(jù)集都有較高的推薦準(zhǔn)確度.

2 基于改進(jìn)加權(quán)二部圖和用戶信任度的協(xié)同過濾推薦算法

PB-BNCF 算法和RB-BNCF 算法根據(jù)用戶對項(xiàng)目的評分為用戶-項(xiàng)目的連邊賦予一定的權(quán)重，當(dāng)邊上權(quán)重較小時，通過這條邊傳遞的用戶能量就較少，達(dá)到弱化低分評價對判斷用戶偏好的影響的目的.這兩種算法的共同點(diǎn)將用戶共同喜歡的項(xiàng)目作為衡量是否有共同的興趣偏好的量化標(biāo)準(zhǔn)，對于用戶不喜歡的項(xiàng)目采取的是忽略或弱化影響的處理方式.但是，不難想象，兩個用戶如果共同不喜歡的項(xiàng)目較多，也能說明兩個用戶興趣偏好相似，用戶的低分評價也蘊(yùn)含著用戶偏好信息，需要進(jìn)行挖掘和分析.

2.1 評分?jǐn)?shù)據(jù)處理

在本文的改進(jìn)算法中，為體現(xiàn)用戶評分對用戶喜歡或不喜歡某一個項(xiàng)目的判斷，需要對用戶的評分用式(8)進(jìn)行預(yù)處理.

計(jì)算用戶uv和用戶uw相似性的時候需要分別計(jì)算uv沿正值邊獲取的能量eng+wv和uv沿負(fù)值邊獲取的能量eng-wv，計(jì)算公式如式(10)和式(11)所示.

函數(shù)f+表示從某一頂點(diǎn)出發(fā)的所有邊上權(quán)值為正值的權(quán)值加和，即，其中tvk＞0；f+(ik)=，其中tvk＞0.

函數(shù)f-表示從某一頂點(diǎn)出發(fā)的所有邊上權(quán)值為負(fù)值的權(quán)值加和的絕對值，即其中tvk＞0.，其中tvk＜0；

用戶uv和用戶uw相 似性采用式(12)計(jì)算.

2.2 用戶信任度

為進(jìn)一步提高推薦準(zhǔn)確度，眾多學(xué)者在推薦過程中引入用戶信任度.比較有代表性的是盧竹兵等人提出的基于信任網(wǎng)絡(luò)的協(xié)同過濾推薦算法[16]，算法認(rèn)為用戶的信任度具有傳遞性，用戶A 信任用戶B，用戶B 信任用戶C，則認(rèn)為用戶A 也信任用戶C.根據(jù)用戶的信任關(guān)系結(jié)合用戶評分構(gòu)建鄰居用戶模型，可以得到更加準(zhǔn)確的推薦結(jié)果.分析此類算法后發(fā)現(xiàn)，學(xué)者還隱含地認(rèn)為用戶信任度具有全局性，即如果AB 間有信任關(guān)系，則對用戶A 推薦所有領(lǐng)域的項(xiàng)目時都采用B 做鄰居用戶，這與實(shí)際情況不符，現(xiàn)實(shí)情況是很難有一個用戶對所有領(lǐng)域都熟悉，用戶A 在選擇不同領(lǐng)域的項(xiàng)目時更傾向于咨詢具體領(lǐng)域內(nèi)的可信用戶.因而本文將用戶信任度的形式定義如表1所示.

表1 用戶信任度表示形式

若用戶uw在領(lǐng)域cχ下信任度Tw,χ比較高需滿足兩個條件，一是用戶uw在該領(lǐng)域內(nèi)的評分?jǐn)?shù)量比較多，二是用戶的評分比較準(zhǔn)確.

(1)評分?jǐn)?shù)量權(quán)重

本文定義評分?jǐn)?shù)量因子ωw,χ來衡量用戶uw在領(lǐng)域χ下的權(quán)重，如式(13)所示.

其中，nw,χ代表用戶uw評價過并且屬于領(lǐng)域χ的項(xiàng)目數(shù)量，H為常量，通常取該領(lǐng)域下項(xiàng)目數(shù)量的一定比例(如領(lǐng)域下項(xiàng)目數(shù)量的80%)，若用戶uw評價過領(lǐng)域χ的項(xiàng)目數(shù)達(dá)到H時，認(rèn)為用戶uw比較可信，否則，不太可信，評分?jǐn)?shù)量因子等于用戶uw評價過的項(xiàng)目數(shù)量與H的比值.

(2)評分準(zhǔn)確度權(quán)重

衡量用戶uw對項(xiàng)目ik評分準(zhǔn)確度權(quán)重Ew,k

采用式(14)計(jì)算.

其中，S為項(xiàng)目的評分范圍，若項(xiàng)目評分采用5 分制，則S=5；代表所有用戶對項(xiàng)目ik評分的平均值.

由評分?jǐn)?shù)量因素ωw,χ和評分準(zhǔn)確度因素Ew,k確定的用戶uw在領(lǐng)域χ 內(nèi)的信任度Tw,χ以式(15)計(jì)算.

其中，|χ|代表分類χ 內(nèi)的項(xiàng)目數(shù)量，Tw,χ的取值范圍是[0，1].

2.3 評分預(yù)測

綜合以上用戶相似性和用戶信任度的因素，計(jì)算用戶uw對某一未評分項(xiàng)目ik的預(yù)測評分時用式(16)計(jì)算.

2.4 推薦流程

用戶在某一領(lǐng)域內(nèi)的信任度相對比較穩(wěn)定，因此采用離線方式計(jì)算用戶信任度，在線推薦時將信任度矩陣作為算法輸入，算法推薦流程如圖1所示.

圖1 本文算法推薦流程

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文采用美國Minnesota 大學(xué)的GroupLens 項(xiàng)目MovieLens 和Eachmovie 兩個真實(shí)的電影評分?jǐn)?shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中MovieLens 數(shù)據(jù)集中包括943個用戶對1682 部電影的100 000個評分記錄，每個用戶至少對20 部電影進(jìn)行了評分，評分范圍為1-5；Eachmovie數(shù)據(jù)集中有72 916個用戶對1628 部電影的2811 983個評分記錄，評分范圍為0-1，為使不同數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果具有可比性，將Eachmovie 數(shù)據(jù)集中的用戶評分進(jìn)行線性處理，使評分落在1-5 之間.隨機(jī)選取每個數(shù)據(jù)集中的80%作為訓(xùn)練集，構(gòu)建協(xié)同過濾推薦模型，剩余20%作為測試集，檢驗(yàn)推薦效果.

3.2 評估指標(biāo)

由于改進(jìn)算法著眼于提高推薦的準(zhǔn)確度，因此采用學(xué)者最常使用的平均絕對偏差(MAE)來評估算法的效果.MAE表示算法預(yù)測評分與用戶實(shí)際評分之間的差距，計(jì)算對單個用戶推薦準(zhǔn)確度的方法如式(17).

其中，N為測試集中某一用戶uw評過分的項(xiàng)目數(shù)量；rwk為算法預(yù)測用戶uw對項(xiàng)目ik的評分；為用戶uw對項(xiàng)目ik的實(shí)際評分.計(jì)算測試集中所有用戶的MAEw值后再取平均值即得到算法的平均絕對偏差MAE，算法的MAE值越小，說明推薦結(jié)果越準(zhǔn)確.

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

實(shí)驗(yàn)對傳統(tǒng)二部圖算法、基于參數(shù)化的加權(quán)二部圖算法、基于比例的加權(quán)二部圖算法以及本文改進(jìn)算法進(jìn)行了對比分析，采用兩種數(shù)據(jù)集時各算法的推薦準(zhǔn)確度對比情況如圖2 和圖3所示，圖中縱軸是不同算法的MAE值，橫軸是實(shí)驗(yàn)中設(shè)置的鄰居用戶數(shù).

圖2 采用MovieLens 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

從圖2 縱向來看，BNCF 算法在MovieLens 數(shù)據(jù)集中預(yù)測評分結(jié)果偏差比較大，PB-BNCF 算法和RB-BNCF算法MAE值明顯低于BNCF 算法，本文提出的算法則在不同鄰居用戶數(shù)情況下均優(yōu)于對比算法；從橫向來看，BNCF算法隨著鄰居用戶數(shù)從5 增加到40，推薦準(zhǔn)確度呈現(xiàn)不穩(wěn)定的表現(xiàn)，PB-BNCF 算法、RB-BNCF 算法以及本文提出的算法在鄰居用戶數(shù)較少(5-10)時MAE值相對較高，在鄰居數(shù)為15-20時達(dá)到最佳的推薦效果，在鄰居數(shù)超過30時，MAE值趨向于穩(wěn)定.

圖3 采用Eachmovie 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

從圖3 可以看出，BNCF 算法在Eachmovie 數(shù)據(jù)集上預(yù)測評分結(jié)果偏差仍然比較大，說明BNCF 算法在基于評分的推薦系統(tǒng)上推薦效果不佳，對路徑進(jìn)行加權(quán)處理后可以明顯提高推薦的準(zhǔn)確度；RB-BNCF 在Eachmovie 數(shù)據(jù)集上MAE值略有升高，可能和Eachmovie數(shù)據(jù)集評分稀疏度比MovieLens 數(shù)據(jù)集高有關(guān)；PBBNCF 算法在Eachmovie 數(shù)據(jù)集上的MAE值遠(yuǎn)高于在MovieLens 數(shù)據(jù)集上的結(jié)果，可能原因是PB-BNCF 算法對不同數(shù)據(jù)集的最佳參數(shù) λ取值不同，本實(shí)驗(yàn)為進(jìn)行實(shí)驗(yàn)對比分析，統(tǒng)一取λ值為0.5，這一參數(shù)更適合MovieLens數(shù)據(jù)集.而本文提出的算法在Eachmovie 數(shù)據(jù)集上依然最優(yōu).

對比各種算法在Eachmovie 和MovieLens 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果來看，本文提出的算法在不同的數(shù)據(jù)集上MAE值均低于其它算法，推薦效果準(zhǔn)確且穩(wěn)定.

4 總結(jié)和展望

為了提高協(xié)同過濾推薦的準(zhǔn)確度，本文提出了一種基于改進(jìn)的加權(quán)二部圖和用戶信任度的協(xié)同過濾推薦系統(tǒng).算法充分挖掘了用戶低分評價中包含的用戶興趣信息，在二部圖進(jìn)行能量擴(kuò)散過程中同時擴(kuò)散“喜歡”和“不喜歡”的能量，并結(jié)合用戶在具體領(lǐng)域中的信任度對項(xiàng)目進(jìn)行預(yù)測評分.實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在兩種數(shù)據(jù)集上均能取得更準(zhǔn)確的推薦結(jié)果，算法表現(xiàn)穩(wěn)定.由于算法充分挖掘了隱藏的用戶的興趣信息，因而可以更進(jìn)一步地解決協(xié)同過濾數(shù)據(jù)稀疏性的問題，筆者將在接下來的工作中在此方面進(jìn)行研究和探討，不斷優(yōu)化算法的推薦效果.