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

潘燕梅

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

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

1 傳統(tǒng)協(xié)同過濾推薦算法

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

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

表1 協(xié)同推薦的評分?jǐn)?shù)據(jù)庫

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

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

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

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

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

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

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

2.1 重要性程度因子的引入

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

為此，系統(tǒng)通過引入項目重要性程度因子和用戶重要性程度因子來進(jìn)一步提高用戶對目標(biāo)項目的評分精確度.

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

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

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

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

其中：行對應(yīng)用戶節(jié)點，列對應(yīng)項目節(jié)點，1 表示用戶對項目有評分，而0 表示用戶對項目無評分.

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

圖1 初始重要性程度

2.2 LDPC 碼

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

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

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

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

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

借鑒LDPC 碼的BP 譯碼算法，引入的重要性程度因子則可利用置信度傳播算法進(jìn)行迭代更新，算法表述如下：其中，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有連接的項目數(shù)目.UR(u)表示用戶u的重要性程度因子，IR(i)表示項目i的重要性程度因子.

3 實驗仿真分析

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

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

表2 MovieLens 原始數(shù)據(jù)集示例

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

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

為了進(jìn)行對比，傳統(tǒng)協(xié)同過濾推薦算法的預(yù)測精度也進(jìn)行了仿真.仿真發(fā)現(xiàn)，傳統(tǒng)協(xié)同過濾推薦算法的預(yù)測平均絕對誤差為0.814 6 分.其中，第一個用戶的前20 組預(yù)測評分和實際評分?jǐn)?shù)據(jù)對比如表3 所示（表中的數(shù)據(jù)表示預(yù)測評分值或是實際評分值，評分值為1～5 分；下同）.可以看出，在這20 組評分中就有5 組評分誤差達(dá)到了1 分以上.

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

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

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

表3 傳統(tǒng)協(xié)同過濾算法預(yù)測評分與實際評分對比表

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

4 結(jié)論

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