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

潘燕梅

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 重要性程度因子的引入

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

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

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

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

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

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

其中：行對(duì)應(yīng)用戶節(jié)點(diǎn)，列對(duì)應(yīng)項(xiàng)目節(jié)點(diǎn)，1 表示用戶對(duì)項(xiàng)目有評(píng)分，而0 表示用戶對(duì)項(xiàng)目無(wú)評(píng)分.

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

圖1 初始重要性程度

2.2 LDPC 碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 傳統(tǒng)協(xié)同過(guò)濾算法預(yù)測(cè)評(píng)分與實(shí)際評(píng)分對(duì)比表

表4 基于置信度傳播的協(xié)同過(guò)濾推薦算法預(yù)測(cè)評(píng)分與實(shí)際評(píng)分對(duì)比表

4 結(jié)論

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