融合動(dòng)態(tài)K 近鄰Slope_One 的協(xié)同過濾推薦算法?

李靈慧 王 遜 王云沼 黃樹成

（1.江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）（2.陸軍通信訓(xùn)練基地 北京 102400）

1 引言

信息時(shí)代在逐步地改變?nèi)藗兊纳罘绞剑o人類的生活帶來(lái)便利，但也出現(xiàn)了信息過載等負(fù)面信息。而推薦系統(tǒng)能夠協(xié)助人類在眾多繁雜的數(shù)據(jù)中高效、精準(zhǔn)地找到其感興趣或者有用的信息［1］。在眾多的推薦算法中，協(xié)同過濾算法憑借其獨(dú)特的優(yōu)勢(shì)，一直是領(lǐng)域內(nèi)關(guān)注的焦點(diǎn)。但是協(xié)同過濾算法面臨著數(shù)據(jù)稀疏性的問題［2］，這也是導(dǎo)致推薦質(zhì)量下降的重要原因。

為了解決數(shù)據(jù)稀疏的問題，國(guó)內(nèi)外學(xué)者對(duì)此進(jìn)行了大量的研究，岳希［3］等針對(duì)用戶在單一項(xiàng)目上活動(dòng)較少而導(dǎo)致推薦質(zhì)量不佳的問題，提出將基于項(xiàng)目和用戶的推薦方法相結(jié)合進(jìn)行推薦。Ahmadian 等［4］研究出一種提升用戶評(píng)分信息的算法，該算法將多角度可靠性度量考慮進(jìn)去，首先加大可靠性比較低的用戶的評(píng)分?jǐn)?shù)據(jù)，然后再次計(jì)算出這些用戶的數(shù)據(jù)，進(jìn)而改善稀疏的問題。王家華等［5］提出融合改進(jìn)加權(quán)Slope One的協(xié)同過濾算法。該算法通過預(yù)測(cè)評(píng)分并填充評(píng)分矩陣的方式來(lái)提高推薦效果。張艷菊等［6］將直覺模糊C 均值聚類考慮進(jìn)推薦算法中，將其與傳統(tǒng)的協(xié)同過濾算法相融合，進(jìn)而提升算法的推薦效果。羅辛［7］、王威［8］等將用戶之間共同評(píng)分的項(xiàng)目數(shù)量考慮到用戶最近鄰的計(jì)算中，通過將不同用戶針對(duì)相同產(chǎn)品的評(píng)分?jǐn)?shù)據(jù)加上權(quán)重，引入到用戶相似度的計(jì)算中來(lái)實(shí)現(xiàn)推薦算法的改進(jìn)。針對(duì)協(xié)同過濾算法中的數(shù)據(jù)稀疏問題，本文將Slope_One 算法與基于物品的協(xié)同過濾算法相結(jié)合，提出融合動(dòng)態(tài)K 近鄰Slope_One 的協(xié)同過濾推薦算法：1）首先利用改進(jìn)余弦相似度公式計(jì)算用戶相似度，為每個(gè)用戶篩選出K 個(gè)近鄰用戶。利用該用戶的K 個(gè)近鄰用戶的數(shù)據(jù)進(jìn)行平均評(píng)分偏差計(jì)算。2）改進(jìn)物品相似度計(jì)算方法，將物品相似度加權(quán)到預(yù)測(cè)評(píng)分方法中，預(yù)測(cè)用戶的評(píng)分，并利用該評(píng)分對(duì)評(píng)分矩陣進(jìn)行有效填充。3）在新的評(píng)分矩陣上，利用基于物品的協(xié)同過濾算法進(jìn)行推薦。經(jīng)實(shí)驗(yàn)結(jié)果證明，本算法在一定程度上對(duì)推薦效果有明顯的提升。因?yàn)楸舅惴▽⒂脩艏拔锲废嗨贫榷技訖?quán)到Slope_One 算法中，提升算法預(yù)測(cè)的準(zhǔn)確度，同時(shí)改善了數(shù)據(jù)稀疏的問題，進(jìn)而提升協(xié)同過濾推薦算法的效果。

2 相關(guān)工作

2.1 基于物品的協(xié)同過濾推薦

協(xié)同過濾推薦算法是目前業(yè)內(nèi)比較受歡迎的推薦算法，可以實(shí)現(xiàn)預(yù)測(cè)及推薦［9］。該算法分為兩大類：一個(gè)是基于用戶的協(xié)同過濾推薦算法，另外一個(gè)是基于物品的協(xié)同過濾推薦算法［10］。算法利用用戶的歷史使用記錄等信息獲取用戶的喜好信息，通過喜好信息將用戶劃分成不同的群組，并把相似群組的使用記錄推薦給群組內(nèi)的其他用戶。例如喜歡商品A 的用戶都喜歡商品B，用戶Q 喜歡商品A，則給用戶Q推薦商品B［11］。

由于本文研究的對(duì)象是用戶數(shù)量多于商品數(shù)量的圖書數(shù)據(jù)，所以本文使用基于物品的協(xié)同過濾推薦算法。并且在計(jì)算商品的相似度時(shí)，使用改進(jìn)余弦相似度來(lái)計(jì)算。

2.2 Slope_One算法

Slope_One 算法［12］，其本質(zhì)是一種協(xié)同過濾算法，優(yōu)點(diǎn)是實(shí)現(xiàn)操作性比較簡(jiǎn)單，可以實(shí)時(shí)動(dòng)態(tài)更新，推薦結(jié)果的準(zhǔn)確率也比較高［13～14］。算法的基本點(diǎn)是基于物品間受歡迎的度的差異，所以Slope_One 算法預(yù)測(cè)評(píng)分分為兩步，首先計(jì)算不同物品之間的受歡迎的差異，然后根據(jù)差異值計(jì)算評(píng)分［15］。

第一步：計(jì)算不同物品評(píng)分差的均值。

第二步：根據(jù)物品之間的評(píng)分差值以及用戶的歷史評(píng)分?jǐn)?shù)據(jù)，預(yù)測(cè)用戶對(duì)未評(píng)分物品的評(píng)分。

上式中表示用戶u 對(duì)項(xiàng)目i的評(píng)分預(yù)測(cè)，是項(xiàng)目j對(duì)項(xiàng)目i的偏值加上用戶對(duì)項(xiàng)目的評(píng)分。

基礎(chǔ)的Slope_One算法在預(yù)測(cè)評(píng)分時(shí)考慮的是平均評(píng)分差，沒有考慮用戶物品同時(shí)出現(xiàn)次數(shù)這個(gè)數(shù)據(jù)，因此造成預(yù)測(cè)評(píng)分?jǐn)?shù)據(jù)不夠精確。因此預(yù)測(cè)評(píng)分時(shí)引入共同出現(xiàn)次數(shù)這個(gè)懲罰因子。這就是加權(quán)Slope_One算法（WSO）。該算法認(rèn)為一個(gè)物品和目標(biāo)物品同時(shí)出現(xiàn)的次數(shù)越多，則該物品有更高的置信度。改進(jìn)后的預(yù)測(cè)評(píng)分算法的公式如下所示。

其中cij是通過評(píng)價(jià)過物品i和物品j的用戶數(shù)。

3 融合動(dòng)態(tài)K 近鄰Slope_One 的協(xié)同過濾算法

由于傳統(tǒng)的協(xié)同過濾算法會(huì)面臨數(shù)據(jù)稀疏的問題，所以本文將Slope_One 算法與協(xié)同過濾算法相結(jié)合，利用改進(jìn)的用戶相似性計(jì)算獲取每個(gè)用戶的K 近鄰。利用用戶的K 近鄰評(píng)分計(jì)算評(píng)分偏差，然后將改進(jìn)的物品相似性加權(quán)到預(yù)測(cè)評(píng)分計(jì)算中。再獲取到預(yù)測(cè)評(píng)分后將預(yù)測(cè)評(píng)分填充到原評(píng)分矩陣中，最后利用新的評(píng)分矩陣進(jìn)行基于物品的協(xié)同過濾推薦。 因?yàn)楸疚臄?shù)據(jù)使用的是Book-Crossing數(shù)據(jù)庫(kù)，該數(shù)據(jù)庫(kù)為每個(gè)用戶采樣了一個(gè)未監(jiān)視的圖書并標(biāo)記為0。本文主要是針對(duì)未監(jiān)視的圖書進(jìn)行預(yù)測(cè)評(píng)分。圖1 是本文算法的流程圖。

圖1 算法流程圖

3.1 基于改進(jìn)動(dòng)態(tài)K近鄰的評(píng)分偏差

在Slope_One算法中，預(yù)測(cè)評(píng)分分為兩步，第一步是計(jì)算評(píng)分偏差，第二步是計(jì)算評(píng)分。因?yàn)樵趯?shí)際的評(píng)分?jǐn)?shù)據(jù)中，數(shù)據(jù)雖然稀疏但是數(shù)據(jù)量依舊很大，所以在計(jì)算評(píng)分偏差時(shí)計(jì)算量很大，導(dǎo)致算法性能降低。此外，在計(jì)算評(píng)分偏差時(shí)，并不是所有用戶的評(píng)分信息的置信度都一樣高，無(wú)差別地引入所有用戶的數(shù)據(jù)可能使最后的計(jì)算結(jié)果產(chǎn)生較大的誤差。因此本文在計(jì)算用戶評(píng)分偏差時(shí)考慮用戶之間內(nèi)在聯(lián)系，引入動(dòng)態(tài)K 近鄰的思想，利用少數(shù)置信度較高的用戶評(píng)分?jǐn)?shù)據(jù)計(jì)算評(píng)分偏差，不僅可以降低計(jì)算量，而且可以減少誤差。本章采用修正的余弦相似度來(lái)獲取用戶K 近鄰。基于用戶的修正余弦相似度公式如下所示。

其中，I 為用戶x 和用戶y 同時(shí)評(píng)過分的圖書集合，Rx,i代表用戶x對(duì)圖書i的評(píng)分，Rˉx代表用戶x的平均評(píng)分。

因?yàn)樵谟?jì)算用戶相似度時(shí)，利用的數(shù)據(jù)是用戶x 和用戶y 共同評(píng)過分的圖書數(shù)據(jù)，如果某本書很暢銷或者必需性比較強(qiáng)，那么即使兩個(gè)用戶都對(duì)這本書有過行為，也不代表這兩個(gè)用戶比較相似。相反，當(dāng)兩個(gè)用戶都對(duì)一本長(zhǎng)尾圖書有過評(píng)分行為時(shí)，說(shuō)明這兩個(gè)用戶有較大的相似度。本文將懲罰因子加入到用戶相似度計(jì)算的考量中，使推薦結(jié)果更加準(zhǔn)確。具體公式如下所示：

公式中|N(i) |是對(duì)圖書i 有過評(píng)分動(dòng)作的用戶量，數(shù)據(jù)就會(huì)越高，用戶之間的相似度就會(huì)越高。當(dāng)對(duì)該圖書有過評(píng)價(jià)動(dòng)作的用戶量越少，計(jì)算數(shù)據(jù)就會(huì)越高，兩個(gè)用戶之間的相似度就會(huì)越高。這種方法可以減少熱門書籍對(duì)相似度的影響。

3.2 改進(jìn)預(yù)測(cè)評(píng)分方法

加權(quán)Slope_One算法雖然將用戶物品之間出現(xiàn)次數(shù)這個(gè)數(shù)據(jù)考慮進(jìn)去，但是沒有考慮物品之間的相關(guān)性。在預(yù)測(cè)評(píng)分的時(shí)候，相似度高的物品沒有較高評(píng)分，相似度低的物品也不會(huì)被區(qū)分開，從而造成較大的計(jì)算偏差。所以在計(jì)算用戶評(píng)分時(shí)不僅應(yīng)該考慮用戶同時(shí)對(duì)物品評(píng)分的數(shù)量，同時(shí)也將物品相似度這個(gè)權(quán)重考慮進(jìn)去，既兼顧了物品用戶同時(shí)出現(xiàn)的次數(shù)對(duì)預(yù)測(cè)評(píng)分的影響，同時(shí)也兼顧了物品之間的內(nèi)在關(guān)聯(lián)。

其中i，j代表兩個(gè)圖書，u代表用戶，Ru,i代表用戶u對(duì)圖書i 的評(píng)分，Rˉu代表用戶u 對(duì)所有圖書評(píng)分的均值。

融合物品相似度的評(píng)分預(yù)測(cè)計(jì)算公式如下所示。

在計(jì)算評(píng)分時(shí)加入懲罰因子sim(i,j)，當(dāng)兩本圖書的相似度較高時(shí)，評(píng)分?jǐn)?shù)據(jù)也會(huì)增大，而當(dāng)兩本圖書的相似度較低時(shí)，評(píng)分?jǐn)?shù)據(jù)就會(huì)相應(yīng)地降低。

3.3 算法融合

我們假定為用戶推薦N 本圖書，ListBook 為最終給用戶推薦的圖書結(jié)果集。在計(jì)算用戶目標(biāo)近鄰時(shí)選定近鄰數(shù)為K。算法先將原用戶-圖書數(shù)據(jù)集分為兩個(gè)數(shù)據(jù)集，一個(gè)是評(píng)分非0 數(shù)據(jù)集AllNo-ZeroSet，一個(gè)評(píng)分為0 數(shù)據(jù)集ZeroSet。評(píng)分非0 矩陣為Sh*g；評(píng)分為0 矩陣為Tq*w；新的用戶物品評(píng)分矩陣為R'm*n。AllNoZeroSet 集合用來(lái)計(jì)算評(píng)分偏差以及用戶物品相似度，ZeroSet 集合即需要預(yù)測(cè)評(píng)分的數(shù)據(jù)。

本章算法描述如下。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用Book-Crossing 數(shù)據(jù)集，因該數(shù)據(jù)集是顯式反饋數(shù)據(jù)，在實(shí)驗(yàn)時(shí)需轉(zhuǎn)換成隱式反饋數(shù)據(jù)，數(shù)據(jù)集內(nèi)所有記錄記有數(shù)字1，用于表達(dá)用戶對(duì)該圖書為正面評(píng)價(jià)，同時(shí)為用戶標(biāo)記一個(gè)未監(jiān)視的圖書，將其設(shè)置為0。此外，由于該數(shù)據(jù)集比較稀疏，未設(shè)置肯定評(píng)分閾值。

表1 Book-Crossing數(shù)據(jù)集信息

4.2 實(shí)驗(yàn)環(huán)境

處理器為英特爾酷睿i5 系列，主硬盤為12.0GB，數(shù)據(jù)運(yùn)行的環(huán)境為Python 3.7。

4.3 評(píng)價(jià)指標(biāo)

本文使用召回率（Recall）以及MAE 值評(píng)價(jià)算法的推薦效果。

召回率（Recall）表示正確預(yù)測(cè)出正樣本占實(shí)際正樣本的概率。

其中FN 表示樣本的真實(shí)類別為正，預(yù)測(cè)的結(jié)果卻為負(fù)。

平均絕對(duì)誤差(Mean Absolute Error,MAE) ，表示預(yù)測(cè)值與真實(shí)值之間的整體偏差：

其中，T 表示測(cè)試數(shù)據(jù)集的樣本數(shù)量，ri表示測(cè)試數(shù)據(jù)集中樣本的真實(shí)值，p?i表示推薦算法的預(yù)測(cè)值。

4.4 實(shí)驗(yàn)結(jié)果分析

因?yàn)槭侨诤蟿?dòng)態(tài)K 近鄰算法推薦，所以先將K作為變量，顯示不同K 值下的推薦結(jié)果。K 值分別設(shè)置為5、10、15、20、25、30、35 分別做實(shí)驗(yàn)，每個(gè)數(shù)值做5 次實(shí)驗(yàn)取平均值。本次實(shí)驗(yàn)協(xié)同過濾算法選取Top-N 的N 值為10，定義相似圖書的個(gè)數(shù)為20。圖2 和圖3 是本算法在不同K 之下的MAE 及召回率的對(duì)比圖。

圖2 不同K值下的MAE曲線

圖3 不同K值下的召回率曲線

圖2是不同K值下的MAE的曲線分布圖，可以看出曲線整體呈下降趨勢(shì)，在K=15 時(shí)趨向穩(wěn)定。圖3 是不同K 值下召回率的曲線分布圖，曲線整體呈上升趨勢(shì)，在K=15時(shí)達(dá)到頂峰，之后一定穩(wěn)定在0.0505左右。這兩幅圖可以看出來(lái)，不管是召回率還是MAE，本算法在K 小于15 時(shí)，質(zhì)量逐步上升，在K等于15達(dá)到效率最高，之后逐漸趨向穩(wěn)定。

圖4 是不同K 值算法運(yùn)行時(shí)間柱狀圖，時(shí)間度量單位是秒，可以看出，當(dāng)K 值增大時(shí)，運(yùn)行時(shí)間逐漸增加，且增加的速率逐步增加。綜合來(lái)說(shuō)，當(dāng)K值大于15 時(shí)，運(yùn)行效率趨于穩(wěn)定，但運(yùn)行時(shí)間指數(shù)增加，所以當(dāng)K值等于15時(shí)，本章算法達(dá)到最優(yōu)。

圖4 不同K值算法運(yùn)行時(shí)間柱狀圖

上面的實(shí)驗(yàn)是在N 值確定、K 值變化的前提下進(jìn)行的，下面本章將在K 值確定、N 值變化的前提下進(jìn)行實(shí)驗(yàn)。由于K=15 是最優(yōu)結(jié)果，所以本章將在K=15 的前提下，判斷N 值為多少時(shí)最優(yōu)。本次的算法N 值選取10、20、30、40，每個(gè)數(shù)據(jù)運(yùn)行5 次取平均值。為了更好地判斷本章算法KSOCF 的效果，與傳統(tǒng)IBCF 算法、加權(quán)SO 算法（WSO）、考慮物品屬性的Slope One 算法（UIASO）［16］以及融合改進(jìn)Slope_One的協(xié)同過濾算法［5］（SOCF）進(jìn)行比較。圖5 和圖6 是五種算法在不同N 之下的MAE 及召回率的對(duì)比圖。

圖5 不同N值的MAE曲線

圖6 不同N值的Recall曲線

從圖5 我們看出，除了WSO 及SOCF 算法以外，其他幾個(gè)算法隨著N 值增加，MAE 值都有所下降。在N=10 時(shí)，加權(quán)SO 算法的MAE 值最小，在N大于等與20 時(shí)，本章算法的MAE 值最小，且在N大于等于20時(shí)趨向穩(wěn)定。從圖6我們可以看出，隨著N 值的增加，除了WSO 算法發(fā)揮穩(wěn)定以外，其它四種算法的召回率均有所增加。但是不管是N 值多大，本節(jié)算法都有較大的召回率，說(shuō)明了本文算法的質(zhì)量較好。

本節(jié)算法在不同近鄰K 值下有不同的表現(xiàn)，在N 值確定，K值不同時(shí)，運(yùn)行時(shí)間隨著K值的增加呈指數(shù)增加，但是MAE 值及召回率都在K 大于等于15 趨向穩(wěn)定，所以本節(jié)算法動(dòng)態(tài)近鄰等于15 時(shí)算法質(zhì)量最好。在K值等于15，推薦數(shù)量N 作為變量變化時(shí)，可以看出MAE在N等于20時(shí)，變化趨向穩(wěn)定，但是MAE 值是四種算法中值最小的，說(shuō)明算法精確度較高。召回率隨著N值變大而提升，與其他四種算法對(duì)比，本節(jié)算法召回率具有一定優(yōu)勢(shì)。綜上所述，本節(jié)算法在用戶相似近鄰值等于15，推薦數(shù)量等于20 時(shí)，算法效果最好，且具有一定的優(yōu)勢(shì)。

5 結(jié)語(yǔ)

本文主要針對(duì)協(xié)同過濾算法數(shù)據(jù)稀疏性問題，提出融合動(dòng)態(tài)K 近鄰Slope_One 的協(xié)同過濾算法，首先在原評(píng)分矩陣上利用改進(jìn)的余弦計(jì)算方法計(jì)算得到用戶的K 個(gè)近鄰，然后利用自身以及K 個(gè)近鄰的用戶-物品交互數(shù)據(jù)計(jì)算物品評(píng)分差值，利用改進(jìn)的評(píng)分計(jì)算方法預(yù)測(cè)評(píng)分。之后將預(yù)測(cè)評(píng)分填入原評(píng)分矩陣，在填充后的評(píng)分矩陣上利用基于物品的協(xié)同過濾推薦算法計(jì)算推薦結(jié)果。經(jīng)實(shí)驗(yàn)證明本算法具有一定優(yōu)勢(shì)。