鄧小燕，張曉彬

1(重慶醫(yī)藥高等?？茖W校 醫(yī)學技術(shù)學院，重慶 401331)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 評分數(shù)據(jù)處理

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

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

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

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

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

2.2 用戶信任度

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

表1 用戶信任度表示形式

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

(1)評分數(shù)量權(quán)重

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

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

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

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

采用式(14)計算.

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

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

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

2.3 評分預測

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

2.4 推薦流程

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

圖1 本文算法推薦流程

3 實驗分析

3.1 實驗設(shè)計

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

3.2 評估指標

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

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

3.3 實驗結(jié)果分析

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

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

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

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

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

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

4 總結(jié)和展望

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