基于改進加權二部圖和用戶信任度的協同過濾推薦算法①

鄧小燕，張曉彬

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

2(重慶農村商業銀行 科技信息部，重慶 400023)

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

1 基于加權二部圖的協同過濾推薦算法

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

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

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

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

1.1 基于參數化的加權二部圖算法

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

其中，函數f表示對圖中某一頂點有連邊的權值進行求和，即；.

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

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

1.2 基于比例的加權二部圖算法

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

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

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

2 基于改進加權二部圖和用戶信任度的協同過濾推薦算法

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

2.1 評分數據處理

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

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

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

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

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

2.2 用戶信任度

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

表1 用戶信任度表示形式

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

(1)評分數量權重

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

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

(2)評分準確度權重

衡量用戶uw對項目ik評分準確度權重Ew,k

采用式(14)計算.

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

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

其中，|χ|代表分類χ 內的項目數量，Tw,χ的取值范圍是[0，1].

2.3 評分預測

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

2.4 推薦流程

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

圖1 本文算法推薦流程

3 實驗分析

3.1 實驗設計

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

3.2 評估指標

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

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

3.3 實驗結果分析

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

圖2 采用MovieLens 數據集實驗結果

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

圖3 采用Eachmovie 數據集實驗結果

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

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

4 總結和展望

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