融合動態K 近鄰Slope_One 的協同過濾推薦算法?

李靈慧 王 遜 王云沼 黃樹成

（1.江蘇科技大學計算機學院 鎮江 212003）（2.陸軍通信訓練基地 北京 102400）

1 引言

信息時代在逐步地改變人們的生活方式，給人類的生活帶來便利，但也出現了信息過載等負面信息。而推薦系統能夠協助人類在眾多繁雜的數據中高效、精準地找到其感興趣或者有用的信息［1］。在眾多的推薦算法中，協同過濾算法憑借其獨特的優勢，一直是領域內關注的焦點。但是協同過濾算法面臨著數據稀疏性的問題［2］，這也是導致推薦質量下降的重要原因。

為了解決數據稀疏的問題，國內外學者對此進行了大量的研究，岳希［3］等針對用戶在單一項目上活動較少而導致推薦質量不佳的問題，提出將基于項目和用戶的推薦方法相結合進行推薦。Ahmadian 等［4］研究出一種提升用戶評分信息的算法，該算法將多角度可靠性度量考慮進去，首先加大可靠性比較低的用戶的評分數據，然后再次計算出這些用戶的數據，進而改善稀疏的問題。王家華等［5］提出融合改進加權Slope One的協同過濾算法。該算法通過預測評分并填充評分矩陣的方式來提高推薦效果。張艷菊等［6］將直覺模糊C 均值聚類考慮進推薦算法中，將其與傳統的協同過濾算法相融合，進而提升算法的推薦效果。羅辛［7］、王威［8］等將用戶之間共同評分的項目數量考慮到用戶最近鄰的計算中，通過將不同用戶針對相同產品的評分數據加上權重，引入到用戶相似度的計算中來實現推薦算法的改進。針對協同過濾算法中的數據稀疏問題，本文將Slope_One 算法與基于物品的協同過濾算法相結合，提出融合動態K 近鄰Slope_One 的協同過濾推薦算法：1）首先利用改進余弦相似度公式計算用戶相似度，為每個用戶篩選出K 個近鄰用戶。利用該用戶的K 個近鄰用戶的數據進行平均評分偏差計算。2）改進物品相似度計算方法，將物品相似度加權到預測評分方法中，預測用戶的評分，并利用該評分對評分矩陣進行有效填充。3）在新的評分矩陣上，利用基于物品的協同過濾算法進行推薦。經實驗結果證明，本算法在一定程度上對推薦效果有明顯的提升。因為本算法將用戶及物品相似度都加權到Slope_One 算法中，提升算法預測的準確度，同時改善了數據稀疏的問題，進而提升協同過濾推薦算法的效果。

2 相關工作

2.1 基于物品的協同過濾推薦

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

由于本文研究的對象是用戶數量多于商品數量的圖書數據，所以本文使用基于物品的協同過濾推薦算法。并且在計算商品的相似度時，使用改進余弦相似度來計算。

2.2 Slope_One算法

Slope_One 算法［12］，其本質是一種協同過濾算法，優點是實現操作性比較簡單，可以實時動態更新，推薦結果的準確率也比較高［13～14］。算法的基本點是基于物品間受歡迎的度的差異，所以Slope_One 算法預測評分分為兩步，首先計算不同物品之間的受歡迎的差異，然后根據差異值計算評分［15］。

第一步：計算不同物品評分差的均值。

第二步：根據物品之間的評分差值以及用戶的歷史評分數據，預測用戶對未評分物品的評分。

上式中表示用戶u 對項目i的評分預測，是項目j對項目i的偏值加上用戶對項目的評分。

基礎的Slope_One算法在預測評分時考慮的是平均評分差，沒有考慮用戶物品同時出現次數這個數據，因此造成預測評分數據不夠精確。因此預測評分時引入共同出現次數這個懲罰因子。這就是加權Slope_One算法（WSO）。該算法認為一個物品和目標物品同時出現的次數越多，則該物品有更高的置信度。改進后的預測評分算法的公式如下所示。

其中cij是通過評價過物品i和物品j的用戶數。

3 融合動態K 近鄰Slope_One 的協同過濾算法

由于傳統的協同過濾算法會面臨數據稀疏的問題，所以本文將Slope_One 算法與協同過濾算法相結合，利用改進的用戶相似性計算獲取每個用戶的K 近鄰。利用用戶的K 近鄰評分計算評分偏差，然后將改進的物品相似性加權到預測評分計算中。再獲取到預測評分后將預測評分填充到原評分矩陣中，最后利用新的評分矩陣進行基于物品的協同過濾推薦。 因為本文數據使用的是Book-Crossing數據庫，該數據庫為每個用戶采樣了一個未監視的圖書并標記為0。本文主要是針對未監視的圖書進行預測評分。圖1 是本文算法的流程圖。

圖1 算法流程圖

3.1 基于改進動態K近鄰的評分偏差

在Slope_One算法中，預測評分分為兩步，第一步是計算評分偏差，第二步是計算評分。因為在實際的評分數據中，數據雖然稀疏但是數據量依舊很大，所以在計算評分偏差時計算量很大，導致算法性能降低。此外，在計算評分偏差時，并不是所有用戶的評分信息的置信度都一樣高，無差別地引入所有用戶的數據可能使最后的計算結果產生較大的誤差。因此本文在計算用戶評分偏差時考慮用戶之間內在聯系，引入動態K 近鄰的思想，利用少數置信度較高的用戶評分數據計算評分偏差，不僅可以降低計算量，而且可以減少誤差。本章采用修正的余弦相似度來獲取用戶K 近鄰。基于用戶的修正余弦相似度公式如下所示。

其中，I 為用戶x 和用戶y 同時評過分的圖書集合，Rx,i代表用戶x對圖書i的評分，Rˉx代表用戶x的平均評分。

因為在計算用戶相似度時，利用的數據是用戶x 和用戶y 共同評過分的圖書數據，如果某本書很暢銷或者必需性比較強，那么即使兩個用戶都對這本書有過行為，也不代表這兩個用戶比較相似。相反，當兩個用戶都對一本長尾圖書有過評分行為時，說明這兩個用戶有較大的相似度。本文將懲罰因子加入到用戶相似度計算的考量中，使推薦結果更加準確。具體公式如下所示：

公式中|N(i) |是對圖書i 有過評分動作的用戶量，數據就會越高，用戶之間的相似度就會越高。當對該圖書有過評價動作的用戶量越少，計算數據就會越高，兩個用戶之間的相似度就會越高。這種方法可以減少熱門書籍對相似度的影響。

3.2 改進預測評分方法

加權Slope_One算法雖然將用戶物品之間出現次數這個數據考慮進去，但是沒有考慮物品之間的相關性。在預測評分的時候，相似度高的物品沒有較高評分，相似度低的物品也不會被區分開，從而造成較大的計算偏差。所以在計算用戶評分時不僅應該考慮用戶同時對物品評分的數量，同時也將物品相似度這個權重考慮進去，既兼顧了物品用戶同時出現的次數對預測評分的影響，同時也兼顧了物品之間的內在關聯。

其中i，j代表兩個圖書，u代表用戶，Ru,i代表用戶u對圖書i 的評分，Rˉu代表用戶u 對所有圖書評分的均值。

融合物品相似度的評分預測計算公式如下所示。

在計算評分時加入懲罰因子sim(i,j)，當兩本圖書的相似度較高時，評分數據也會增大，而當兩本圖書的相似度較低時，評分數據就會相應地降低。

3.3 算法融合

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

本章算法描述如下。

4 實驗及結果分析

4.1 實驗數據集

本文采用Book-Crossing 數據集，因該數據集是顯式反饋數據，在實驗時需轉換成隱式反饋數據，數據集內所有記錄記有數字1，用于表達用戶對該圖書為正面評價，同時為用戶標記一個未監視的圖書，將其設置為0。此外，由于該數據集比較稀疏，未設置肯定評分閾值。

表1 Book-Crossing數據集信息

4.2 實驗環境

處理器為英特爾酷睿i5 系列，主硬盤為12.0GB，數據運行的環境為Python 3.7。

4.3 評價指標

本文使用召回率（Recall）以及MAE 值評價算法的推薦效果。

召回率（Recall）表示正確預測出正樣本占實際正樣本的概率。

其中FN 表示樣本的真實類別為正，預測的結果卻為負。

平均絕對誤差(Mean Absolute Error,MAE) ，表示預測值與真實值之間的整體偏差：

其中，T 表示測試數據集的樣本數量，ri表示測試數據集中樣本的真實值，p?i表示推薦算法的預測值。

4.4 實驗結果分析

因為是融合動態K 近鄰算法推薦，所以先將K作為變量，顯示不同K 值下的推薦結果。K 值分別設置為5、10、15、20、25、30、35 分別做實驗，每個數值做5 次實驗取平均值。本次實驗協同過濾算法選取Top-N 的N 值為10，定義相似圖書的個數為20。圖2 和圖3 是本算法在不同K 之下的MAE 及召回率的對比圖。

圖2 不同K值下的MAE曲線

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

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

圖4 是不同K 值算法運行時間柱狀圖，時間度量單位是秒，可以看出，當K 值增大時，運行時間逐漸增加，且增加的速率逐步增加。綜合來說，當K值大于15 時，運行效率趨于穩定，但運行時間指數增加，所以當K值等于15時，本章算法達到最優。

圖4 不同K值算法運行時間柱狀圖

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

圖5 不同N值的MAE曲線

圖6 不同N值的Recall曲線

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

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

5 結語

本文主要針對協同過濾算法數據稀疏性問題，提出融合動態K 近鄰Slope_One 的協同過濾算法，首先在原評分矩陣上利用改進的余弦計算方法計算得到用戶的K 個近鄰，然后利用自身以及K 個近鄰的用戶-物品交互數據計算物品評分差值，利用改進的評分計算方法預測評分。之后將預測評分填入原評分矩陣，在填充后的評分矩陣上利用基于物品的協同過濾推薦算法計算推薦結果。經實驗證明本算法具有一定優勢。