基于置信度傳播的協同過濾推薦算法

潘燕梅

隨著大數據和人工智能的發展，個性化推薦系統已在人們的日常生活中得到廣泛應用［1］.然而，現有個性化推薦系統的精確度與現實要求仍有一定的差距［2-3］.在個性化推薦系統中，推薦算法決定精確度的大小，是系統的核心.協同過濾推薦算法作為目前應用的主流算法，可利用相似用戶（相似購買喜好）的評分對目標用戶進行推薦［4-6］.

傳統協同過濾推薦算法復雜度較低，但精度不高.本文首先分析了傳統協同過濾推薦算法精度不高的原因，然后引入用戶重要性程度因子和項目重要性程度因子，并提出置信度傳播算法對重要性程度因子進行迭代更新，最終實現評分預測.最后，利用MovieLens數據集，在Matlab 仿真平臺上對所提算法進行了性能仿真.仿真結果表明，基于置信度傳播的協同過濾推薦算法相較于傳統算法精確度可提升5.09%.

1 傳統協同過濾推薦算法

傳統協同過濾算法主要過程為：首先確定一個用戶ID（目前活躍用戶）和評分數據集作為原始參考數據，找出存在相似愛好的用戶集合，這些用戶有時也被稱為對等用戶或近鄰.然后，算法利用近鄰對當前用戶未評分產品p 的評分進行預測.這種方法的潛在假設是：①若近鄰用戶過去存在類似的喜好，他們以后也存在類似的喜好；②用戶喜好不會改變.

如表1 所示，目前五個用戶按1～5 分的標準評出的分值.分值越大表示用戶對該物品項目的興趣越大.

表1 協同推薦的評分數據庫

系統在得到這樣的一個評分矩陣后，就會預測特定用戶對未知產品的喜好程度.在這里，系統的任務就是要預測用戶Alice 對物品5 的評分情況，進而確定是否要把物品5 列入Alice 的推薦列表.

為方便表述，約定下述符號含義：U={u1,…,un}表 示 用 戶 集，P= {p1,…,pm}表 示 產品 集，Rn×m表 示n行m列 的 評 分 矩 陣，其 中，Rn×m中 的 元 素 為rij，i∈1,…,n;j∈1,…,m表示用戶i對產品j的評分值.如果某個用戶i對產品j沒有評分，那么對應的矩陣項rij為空.從而，傳統協同過濾推薦算法根據以下兩個步驟，預測目標用戶對產品的喜好程度.

確定相似用戶集.在當前推薦系統中，Pearson 相關系數法為確定相似用戶集的一般方法.由評分矩陣Rn×m，用戶a和用戶b的相似度sim(a,b)可以表示為：

其 中：分 別 表 示 用 戶a和 用 戶b的 平 均 評分.Pearson 相關系數取值從+1（強正相關）到-1（強負相關）.例如根據式（1）可以計算得到Alice 和其他用戶的相似度分別為0.85、0.70、0.00 和-0.79.如果指定Alice 的近鄰有兩個，則Alice 的近鄰為Bob 和Carey.

評分預測.根據式（1）的相似度測量，參照用戶相似度越大評分決定作用越大的原則，可以定義如下預測值公式：

其中：pred(a,p)表示用戶a對產品p的評分.

2 基于置信度傳播的協同過濾推薦算法

2.1 重要性程度因子的引入

根據上述分析可知，協同過濾推薦算法的關鍵在于對相似度和預測評分的計算.在傳統協同過濾推薦算法中，所有用戶和項目都是視為等效的，即沒有考慮不同用戶和項目的重要性在實際應用中的影響.實際生活中，用戶—項目評分矩陣中，不同的用戶u和項目p在這個評分矩陣中代表的重要性程度是不一樣的.比如網上書店的推薦系統中，用戶ui一共買了1 000 本不同的書，而用戶uj一共買了10 本不同的書，那么用戶ui在推薦過程中的作用要大于uj，即用戶ui的評分更具有權威性.因此在ui和uj與目標用戶u具有同樣相似度時，用戶ui對目標項目的評分作用要大于uj的評分作用.同樣，如果同一本書被更多的用戶購買過，這本書的影響性也就更大.在現實生活中，假設兩個用戶對一本很盛行的書有相同的評分，并不能說明這兩個用戶有相同的興趣愛好.反之，如果兩個用戶對兩本不是很流行的書有相同的評分，那么這兩個用戶就很大可能有相同的品味，因此項目（物品）的重要性程度同樣會對用戶的相似性程度產生一定的作用［7］.

為此，系統通過引入項目重要性程度因子和用戶重要性程度因子來進一步提高用戶對目標項目的評分精確度.

定義用戶u的重要性程度因子為UR( )u，項目i的重要性程度因子為IR( )i.在越重要的用戶對推測評分結果的影響程度越大，越重要的項目對用戶相似度影響程度越小的原則下，用戶u和v的相似度計算，以及用戶u對項目i的評分預測可改進為：

其中：為用戶u的平均評分，α、β為自由參數.

公式（3）和公式（4）為改進的預測評分方法，從公式可知，要得到用戶u對項目i的評分，必須首先計算出用戶u的重要性程度因子UR(u)和項目i的重要性程度因子IR(i).

為此，需要構建計算UR(u)和IR(i)的算法模型.該模型中，所有的用戶和項目都將視作一個節點，且每個節點都有一定的重要性程度.那么，可利用一個二分圖（圖1）描述用戶和項目之間的作用聯系，其中a、b、c分別代表對應項目的初始重要性程度值.該二分圖也可用式（5）所示的二元稀疏矩陣表示：

其中：行對應用戶節點，列對應項目節點，1 表示用戶對項目有評分，而0 表示用戶對項目無評分.

圖1 中的二分圖以及個性化推薦過程中用戶—項目評分矩陣的稀疏性，與通信糾錯碼領域的低密度奇偶校驗碼（LDPC 碼）十分類似.借鑒并改進LDPC 碼中的置信傳播譯碼算法，可對用戶和項目的重要性程度因子進行計算.為完整性起見，先對LDPC 碼和置信度傳播譯碼算法作簡要介紹.

圖1 初始重要性程度

2.2 LDPC 碼

1948 年，香農（Shannon）提出信道編碼定理，該定理指出在信息傳輸速率低于信道容量時，對信息采用一定編碼方法，可使通信的誤碼率任意小［8］.

LDPC 碼（分組糾錯碼）于1962 年由麻省理工學院的Gallager R G.提出，并在1993 年由MACKAY D J C，NEAL R M 等人對其進行了重新研究.基于LDPC 碼校驗矩陣的稀疏特性［9-10］和低復雜度的置信度傳播譯碼算法，LDPC 碼的性能可無限逼近香農限［11］.

(n,k)LDPC 碼的校驗矩陣H(n-k)×n具備下述性質：①所有行中1 的個數為ρ；②所有列中1的個數為γ；③ρ相對于碼長n的比值，以及和γ相對于校驗位數(n-k)的比值都遠小于1；④任意兩行（或兩列）間都存在1 的位置個數不大于2.

根據第③條性質可知，H矩陣中1 的密度很小.正因如此，H稱之為低密度奇偶校驗矩陣.第④條性質則使得H矩陣中不存在長度為4 的短環，從而保證了該H矩陣對應的碼字有較好的糾錯性能.文獻［11］、文獻［12］和文獻［13］對LDPC 碼的置信度傳播譯碼算法進行了研究.

2.3 重要性程度因子迭代更新算法

借鑒LDPC 碼的BP 譯碼算法，引入的重要性程度因子則可利用置信度傳播算法進行迭代更新，算法表述如下：其中，Igvu,（i1 ≤u≤U，1 ≤i≤I）表示用戶u傳遞給項目i的置信度，Ivgi,u（1 ≤u≤U，1 ≤i≤I）表示項目i傳遞給用 戶u的置信度，{Si} ,1 ≤i≤I表 示與項目i有連接的用戶集，{Siu} ,1 ≤i≤I表示除去用戶u之外與項目i有連接的用戶集，{Tu} ,1 ≤u≤U表示與用戶u有連接的項目集，{Tui} ,1 ≤u≤U表示除去項目i之外與用戶u有連接的項目集，|Tu|表示與用戶u有連接的項目數目.UR(u)表示用戶u的重要性程度因子，IR(i)表示項目i的重要性程度因子.

3 實驗仿真分析

為驗證所提算法的預測評分能力，本文基于MovieLens100K 數據集，利用Matlab 仿真平臺，進行了仿真實驗.其中，MovieLens 數據集的電影評分數據是GroupLens Research 在20世紀90 年末到21 世紀初采集的，由MovieLens用戶提供（含943 個用戶以及1 682 部電影，共100 000 個評分數據）.仿真過程中，公式（3）和公式（4）中的α因子和β因子分別取值為-0.5 和0.5.

GroupLens Research 給出 的MovieLens 數據集如表2 所示.第一列表示用戶編號，從1～943；第二列表示電影編號，從1～1 682；第三列表示為用戶對相應電影的評分值，分值為1～5 分；第四列是時間戳.

表2 MovieLens 原始數據集示例

為了對所預測的評分進行驗證，現將該數據分成u1_base 和u1_test 兩部分.u1_base 進行預測評分，u1_test 用來測試預測評分的精確度，其中，算法的準確性定量表述如公式（6）所示，err越大，算法準確度越低，反之則越高.

其中：v∈{R(u,v)≠0} 表示在測試數據集u1_test 中用戶u對項目v評分不等于0 的項目，|{R(u,v)≠0} |表示測試數據集u1_test 中用戶u對項目v評分不等于0 的項目數量，Pu,v表示測試數據集中用戶u對項目v的實際評分，P′u,v表示預測評分.

為了進行對比，傳統協同過濾推薦算法的預測精度也進行了仿真.仿真發現，傳統協同過濾推薦算法的預測平均絕對誤差為0.814 6 分.其中，第一個用戶的前20 組預測評分和實際評分數據對比如表3 所示（表中的數據表示預測評分值或是實際評分值，評分值為1～5 分；下同）.可以看出，在這20 組評分中就有5 組評分誤差達到了1 分以上.

基于同樣的數據集，對本文所提算法的預測評分結果進行分析后，發現它們的預測評分平均誤差為0.773 1 分.因此，本文所提算法的預測誤精度要比傳統的協同過濾推薦算法提升約（0.814 6-0.773 1）/0.814 6=5.09%.表4 還給出了第一個用戶的前20 組預測評分和實際評分數據對比結果.從表4 的數據可以看出，在這20 組評分中只有3 組評分誤差達到了1 分以上.

以下一次迭代更新后的重要性程度因子值與前一次迭代更新后的重要性程度因子值的差值平方和作為指標，圖2 展示了重要性程度因子迭代更新的收斂情況.從圖2 可以看出，算法在25 次迭代后已基本收斂.

圖2 重要性程度因子迭代收斂情況

表3 傳統協同過濾算法預測評分與實際評分對比表

表4 基于置信度傳播的協同過濾推薦算法預測評分與實際評分對比表

4 結論

本文在傳統協同過濾推薦算法的基礎上引入了重要性程度因子，并基于LDPC 碼的置信度傳播算法對協同過濾推薦算法進行了改進.仿真實驗結果表明，改進的推薦算法收斂速度較快，且有5.09%的準確度提升.