基于聚類和用戶偏好的協同過濾推薦算法

王衛紅，曾英杰

浙江工業大學 計算機科學與技術學院，杭州310023

1 引言

隨著社會信息化的發展，互聯網中的數據飛速增長，為了幫助用戶在海量數據中找到滿足用戶需求的數據，大量的研究者和學者對相關方案進行了探索，由此便有了推薦技術的發展。

推薦算法主要有基于協同過濾的推薦[1]、基于內容的推薦[2]和基于關聯規則的推薦[3]。其中，基于協同過濾的推薦是眾多學者研究的一種主流的推薦算法，現實中應用也比較廣泛。

協同過濾算法中需要計算相似度，通常使用Pearson相關性相似度或余弦相似度作為度量標準。協同過濾算法的基本假設是：如果某用戶A在一個項目上與另一個用戶B具有相同的評價，那么用戶A對另一個項目的評價也可能與用戶B相同。由于協同過濾推薦算法使用的評分數據通常非常稀疏，導致協同過濾推薦算法的推薦性能顯著下降，為了解決這個問題，文獻[4]中總結了深度學習的最新進展（基于CF）提出協同深度學習（CDL）。在文獻[5]中，作者也結合深度學習提出了神經協同過濾方法。以上結合了深度學習的方法雖然改善了推薦效果，但是深度學習訓練神經網絡模型需要大量的時間開銷。為了解決協同過濾推薦算法中評分數據的稀疏性和可擴展性差的問題，許多研究者提出了填充稀疏數據集、矩陣分解、降維或聚類[6-8]等方法。矩陣分解是推薦系統最有效的方法之一，用于推薦任務的矩陣分解最先由Simon Funk3在Netflix競賽中設計用于評級預測。后來的研究改進了矩陣分解并提出了許多變種[9-10]。Slope One算法是由Lemire等人提出的一種基于內存的協同過濾推薦算法[11-12]。文獻[13]中提出了一種基于用戶聚類與Slope One填充的協同推薦算法，該算法可以降低數據的稀疏性，提高推薦精度。由于用戶評分矩陣具有很高的稀疏性，而有用的評分信息只包含與目標用戶相關聯的評分，為了避免使用整個用戶評分矩陣進行學習，文獻[14]中提出一種近鄰矩陣分解算法，該算法將用戶近鄰與項目近鄰評分信息融合成一個近鄰評分矩陣，然后在這個新的近鄰評分矩陣中預測目標用戶對目標項目的評分信息。文獻[15]中，作者通過矩陣分解對原始數據進行數據填充和降維，并通過K-means聚類算法對用戶和項目分別進行聚類以改善最終的推薦效果。為了改善推薦效果，也有研究者在計算用戶相似度的時候做了改進[16-17]。

針對上述相關研究中存在的問題，本文提出了一種基于聚類和用戶偏好的協同過濾推薦算法，該算法為了提高用戶相似度精度，以用戶對項目類型的平均評分作為度量標準引入了用戶對項目類型的偏好，并基于用戶自身屬性加入相似性權重；然后用使用Weighted Slope One算法填充評分矩陣中的未評分項以降低其稀疏性；接著通過融入密度和距離優化初始聚類中心的K-means算法聚類填充后的評分數據中的用戶；最后在聚類后的數據集中使用傳統的協同過濾推薦算法生成推薦結果。該算法在電影推薦、圖書推薦、音樂推薦場景下尤為適用。

2 相關工作

傳統的基于用戶的協同過濾推薦算法通過匯總一些類似用戶先前給予該項目的評級來預測用戶對目標項目的評級。主要步驟有：首先把評分數據轉化為m行n列的用戶-項目評分矩陣，記為：Rm,n；然后根據評分矩陣計算每個用戶與其他所有用戶之間的相似度，并按照相似度獲得目標用戶的前N個最近鄰用戶集Nu；最后通過目標用戶u最近鄰用戶集Nu中的用戶對目標項目i的評分預測目標用戶u對目標項目i的評分。

預測評分Pu,i計算公式表示如下：

2.1 用戶相似度計算

2.1.1 余弦相似度

余弦相似度通過用戶特征向量的夾角余弦值sim(u,v)來衡量用戶之間的相似程度[18]，假設有用戶u和用戶v，則用戶u和用戶v的余弦相似度sim(u,v)滿足：-1≤sim(u,v)≤1,sim(u,v)越大則說明用戶u和用戶v越相似，余弦相似度sim(u,v)用公式（2）表示：

2.1.2 基于Pearson相關系數的相似度

皮爾森相關系數法是使用的非常多的一種相似度計算方法[19]。相對于余弦相似度，Pearson相關系數相似度對變量進行了均值化（或去中心化）處理，降低了變量個體的數值差異對變量間相似度的影響，本文采用Pearson相關系數計算用戶間的相似度。假設有用戶u和用戶v，則他們共同評分的項目用集合S表示，ru,i和rv,i分別表示用戶u和用戶v對項目i的評分，和分別表示用戶u和用戶v對各自已評分項目的平均評分，則用戶u和用戶v之間的相似度sim(u,v)可以表示為公式（3）：

2.2 Weighted Slope One算法

由于協同過濾推薦算法中使用的用戶評分數據具有很高的稀疏性，使用Weighted Slope One算法填充用戶評分數據中用戶未評分的項目可以降低評分數據稀疏性。

定義用戶的評分矩陣為Rm,n，假設有用戶u，其已評分項目為i，Iu為用戶u所有已評分的項目集合，即i∈Iu，用戶u待預測評分的項目為j。首先計算項目i項目j之間的評分偏差disi,j，計算公式如下：

其中Ui,j為對項目i和項目j都評過分的用戶集合，u′是集合Ui,j中的用戶，ru′,i為用戶u′對項目i的評分，ru′,j為用戶u′對項目j的評分，numi,j為集合Ui,j中元素的數量。

然后根據評分偏差disi,j和目標用戶u對項目i的評分ru,i計算目標用戶u對項目j的預測評分preu,j，計算公式如下：

2.3 K-means算法

K-means算法根據相似性原則將具有較高相似度的數據對象劃分至同一類簇，一般采用歐式距離作為數據對象之間相似性的度量標準。假設有數據集D，其中的每個數據對象有n維，則兩個數據對象之間的歐式距離的d(x,y)可表示如下：

傳統的K-means算法隨機選擇初始簇心，通過相似度計算，把數據集中的數據樣本與最近的初始中心歸為一類，不斷重復這一過程，直到各個初始中心在某個精度范圍內不變。具體算法步驟如下：

（1）隨機選取K個中心點。

（2）遍歷所有數據對象，計算所有數據對象到中心點的距離，并將每個數據對象劃分到距離最近的中心點中。

（3）計算每個聚類簇的平均值，并作為新的中心點。

（4）不斷迭代，重復步驟（2）和步驟（3），直到K個中心點不再變化或達到最大迭代次數。

2.4 融入密度和距離優化K-means初始簇心

K-means算法雖然實現時簡單方便但也存在一些缺點。例如，聚類的數量K是根據人的經驗判斷的，因此給出一個合理的K值會比較困難。此外，K-means算法對初始簇心的選擇也是隨機的，每次聚類選取的初始簇心不同會導致不同的聚類效果，并且在聚類時如果選擇了孤立點作為聚類中心，則無法達到較好的聚類效果。

針對以上K-means算法存在的缺點，文中在應用K-means算法處理數據時結合密度和距離對初始聚類中心進行優化[20]。在選取聚類初始簇心時，首先通過貪心策略尋找數據對象的鄰域半徑和密度較大的簇；然后不斷選取密度較大且距離最遠的簇作為臨時初始簇，并將初始簇中支持度最高的核心數據對象作為初始簇的中心。具體步驟如下：

輸入：數據集的n個數據對象；聚類個數K；形成初始簇的最大簇內個數Cmax，最小支持度minPts。

輸出：K個作為初始簇中心的核心數據對象。

（1）根據公式（6）計算數據集中數據對象兩兩間的歐式距離dis。

（2）根據最小支持度minPts找出所有核心數據對象，并按密度排序。

（3）在步驟（2）得到的核心對象中選取密度最大的一個數據對象和相距該數據對象最遠的一個數據對象作為初始簇心。

（4）在剩余的核心數據對象中，選取密度次大并且距離已選為初始簇心的數據對象最遠的數據對象作為初始簇心。

（5）重復步驟（4），直至選取K個初始簇心。

通過以上步驟選取的初始簇密度很高，且初始簇心相距較遠，聚類效果穩定可靠。

3 本文算法

協同過濾算法使用評分數據作為學習的數據源，評分數據中的每條數據主要由用戶、項目和評分三部分組成。本文算法通過Weighted Slope One算法填充評分矩陣中的未評分項以降低評分數據的稀疏性；引入了以用戶對項目類型的平均評分為衡量標準的用戶偏好；使用K-means聚類，通過對用戶聚類縮減了目標用戶的最近鄰用戶計算范圍。

假設有用戶集合U={u1,u2,…,um}，項目集合I={i1,i2,…,in}，則評分矩陣為Rm,n，其中ru′,i為用戶u對項目i的評分，評分矩陣如公式（7）：

其中，對于每個用戶則有如表1所示的用戶-項目評分。

表1 用戶-項目評分

假設已知每個項目的類別或屬性，則用戶在對項目評分時也隱式地給項目的類別評了分。對于用戶u，具有已評分項目集合Iu，每個項目i具有一個或多個類別Tt(t=1,2,…,k)。則用戶u對類別Tt的平均評分ru,t可表示如下：

其中若項目i具有類別t，則it=1，否則it=0。numu,t表示用戶u已評分項目具有類別t的項目總數。根據公式（8）提取用戶對類別的平均評分，得到表2的用戶-類別評分表。

表2 用戶-類別評分

由于每個用戶的喜好不同，則對于每一個項目類別的評分也應該不同，甚至會出現某個用戶對某一類別從未有過評分。基于這上述假設，本文將用戶對類別的評分添加到評分矩陣。添加了用戶類別評分后，降低了數據的稀疏性，增加了每個用戶間評分向量的差異，在計算用戶相似度時能夠提高精度。加入用戶類型評分后，評分矩陣可由公式（9）表示：

同時，由于不同年齡段、不同性別和不同職業的用戶對項目類別的偏好也應該不同，基于這一假設，本文通過用戶的年齡、性別和職業這些自身屬性，計算用戶間的相似度simo(u,v)。用戶屬性表可表示如表3。

表3 用戶屬性和職業-類別評分

為了體現不同職業的類型偏好，本文算法引入職業對類型的平均評分。在實際應用場景中，用戶注冊時會填寫自身的一些信息，這些信息會存到數據庫中，因此可以從數據庫抽取用戶的屬性。

如表3所示。表中1代表男性；2代表女性，最終形成一個基于用戶自身屬性的向量，并基于該向量通過公式（3）計算用戶間的相似度simo(u,v)，則最終預測評分時使用的相似度sim(u,v)可表示為sim(u,v)=simr(u,v)×simo(u,v)，其中simr(u,v)為基于用戶-項目評分數據計算得到的用戶相似度。

本文算法描述如下：

輸入：用戶-項目評分矩陣Rm,n，聚類個數K；

輸出：N個推薦項目。

（1）通過用戶-項目評分矩陣Rm,n計算得出用戶-類別評分矩陣R1，并合并兩個評分矩陣，得到評分矩陣R2。

（2）使用公式（5）填充評分矩陣中用戶未評分的項，降低評分矩陣的稀疏性，得到評分矩陣R3。

（3）以評分矩陣R3為聚類輸入數據，找出融入密度和距離的K-means聚類初始簇心，并通過這些初始簇心結合K-means算法將用戶聚類得到K個簇。

（4）使用公式（6）計算目標用戶u和K個簇心之間的距離，并把目標用戶u添加到距離最近的簇中。

（5）在目標用戶u所在的簇中，根據公式（3）計算目標用戶u與簇中其他用戶的相似度sim(u,v)，得到用戶u的最近鄰居集Nu。

（6）根據目標用戶u最近鄰居集Nu中的用戶對項目的評分，使用公式（1）計算目標用戶u對其未評分項目的預測評分，并把預測評分最高的前N個未評分項目推薦給目標用戶u。

本文的算法流程圖如圖1所示。

圖1 本文算法流程圖

如圖1所示，獲取用戶-項目評分矩陣Rm,n、獲取用戶-類別評分矩陣R1和計算基于用戶自身屬性的相似度這三個步驟相對獨立，因此這三個步驟可以并行計算。

本文算法的時間復雜度主要體現在聚類、數據填充和計算用戶相似度這幾個步驟中，其中最大的時間復雜度為O(n2)，n是用戶的數量。在空間復雜度方面，算法輸入的評分數據需要O(i·n)，其中i是用戶平均評分個數，n是用戶的數量，另外算法中需要保存用戶相似矩陣，其空間復雜度為O(n2)。本文算法的時間復雜度和空間復雜度主要受用戶數量影響，通過聚類用戶可以縮小相似用戶的計算范圍，在后續的推薦過程中可以有效降低時間復雜度和空間復雜度。

4 實驗

4.1 實驗數據集與評估標準

實驗中采用美國明尼蘇達大學GroupLens項目組提供的MovieLens數據集對本文算法的性能進行測試。其中包括100 KB、1 MB、10 MB三個規模的數據集。本文采用100 KB的數據集進行實驗，其中包括943個用戶對1 682部電影的10萬條評分數據，電影類別總共有18種，評分標準為1到5之間的整數。數據集中用戶對某一電影的評分值越大說明用戶越喜歡這部電影。為了評估算法性能，將數據集的80%作為訓練集，其余的20%作為測試集。

實驗采用平均絕對偏差（Mean Absolute Error，MAE）和均方誤差（Root Mean Square Error，RMSE）來評估推薦效果。MAE和RMSE是推薦算法中常用的評價指標，兩個指標都是越小則推薦效果越好。MAE通過計算訓練集中的預測評分和測試集中真實評分之間的平均絕對偏差來度量評分預測的準確性。假設用戶u對N個項目的預測評分為P={p1,p2,…,pn}，對應的真實評分為R={r1,r2,…,rn}，則MAE和RMSE的計算公式如下：

4.2 實驗結果與分析

實驗中通過對初始評分數據中的未評分項進行填充，降低了評分矩陣的稀疏性，并引入了用戶對電影類型的評分和用戶自身的屬性；然后采用基于密度和距離優化初始簇心的K-means算法對用戶進行聚類，最后在目標用戶所在簇中用傳統的基于用戶的協同過濾推薦算法得出最終的推薦結果。實驗中將基于用戶的協同過濾推薦算法（UBCF）、基于K-means聚類的協同過濾推薦算法（K-meansUBCF）、基于Slop One填充稀疏矩陣的協同過濾（FUBCF）、基于用戶聚類和填充稀疏矩陣的推薦算法（CFUBCF）與本文中的算法進行了對比。通過實驗取最佳聚類簇數為7，設定目標用戶的最近鄰居個數從5遞增到50，遞增的間隔為5，得出的實驗結果如圖2和圖3所示。

由圖2和圖3可知，實驗中所用的UBCF、K-means UBCF、CFUICF和本文所提出的算法的MAE值都會隨著目標用戶最近鄰居個數的增加而降低并逐漸趨于一個穩定值。本文所提出的算法在不同最近鄰居個數下的MAE值都明顯低于其他兩種算法。以最近鄰居個數30為例，UBCF的MAE值為0.763，而本文所提出的算法的MAE值為0.727，推薦效果提升了3.6%。

圖2 MAE對比圖

圖3 RMSE對比圖

5 結束語

本文算法通過引入以用戶對項目類型的平均評分和用戶自身屬性作為衡量標準的用戶偏好，提升了計算用戶相似度時的準確度，使用Weighted Slope One算法填充評分數據中的未評分項以降低評分數據的稀疏性，并通過融入密度和距離優化初始聚類中心的K-means算法聚類填充后的評分數據中的用戶，提升了算法的可拓展性；最后在聚類后的數據集中使用傳統的協同過濾推薦算法生成目標用戶的推薦結果。通過使用MovieLens100K數據集實驗證明，本文提出的算法提升了推薦精度。由于本文的算法主要使用在離線情景下，在實際推薦系統中，實時推薦也尤為重要，因此下一步的工作是將該算法與實時計算框架結合，并融入時間因子，在實時推薦方向展開研究。