基于聚類和隨機森林的協同過濾推薦算法

楊興雨，李華平，張宇波

YANG Xingyu,LI Huaping,ZHANG Yubo

廣東工業大學 管理學院，廣州 510520

School of Management,Guangdong University of Technology,Guangzhou 510520,China

1 引言

互聯網的快速發展使其成為信息傳遞和商品流通日益重要的平臺。急劇膨脹的網絡資源在為用戶提供豐富多樣的信息的同時，也對用戶搜索信息的能力和精力提出了挑戰，用戶不得不投入更多時間和精力搜索其所需要的信息。推薦系統（Recommendation Systems，RS）由此而生，它利用用戶的偏好信息自動向用戶推薦符合其興趣特點的項目[1]，項目泛指商品、信息等被推薦給用戶的對象。

推薦系統分析的數據主要有兩種類型：一種是可通過矩陣表示的數值型數據，比如用戶對項目的評分、購買、瀏覽等，用戶是否購買商品或是否瀏覽網頁可用數字1和0表示。另一種類型的數據是文本數據，比如用戶對項目的評論、網頁的內容、電影的簡介等。根據所分析數據的類型，推薦技術可分為協同過濾（Collaborative Filtering，CF）推薦技術、基于內容（Content-based）的推薦技術和混合（Hybrid）推薦技術。協同過濾推薦算法分析數值矩陣；基于內容的推薦算法分析文本數據；而混合推薦算法則綜合前兩者的優勢。

協同過濾算法根據用戶-項目評分矩陣中已有的評分，利用用戶間或者項目間的相關關系預測評分矩陣中缺失的評分，然后根據評分的高低衡量用戶對項目的偏好程度。協同過濾算法可分為基于鄰近關系（Neighborhood-based）的推薦算法和基于模型（Model-based）的推薦算法。前者根據與目標用戶相似的用戶對某項目的評分，預測目標用戶對該項目的評分；或者在目標用戶已評分的項目中搜索與目標項目最相似的k個項目，根據目標用戶對這些項目的評分，預測其對目標項目的評分?；卩徑P系的推薦算法易于理解和實現，但每次進行推薦時都要查找目標用戶（項目）的k最鄰近用戶（項目）。當推薦系統面臨數以百萬甚至千萬級別的用戶和項目時，計算開銷非常龐大，算法的實時性將很難保證，相應的推薦系統將面臨可擴展性問題[2]。針對此問題，學者提出的解決方法主要分為兩類：一類是采用并行存儲和計算技術[3-5]，提高推薦系統的可擴展性；另一類方法則是采用基于模型的推薦技術，此類技術可離線根據用戶-項目矩陣構建模型，在線根據模型產生推薦，提高在線推薦效率?；谀Ｐ偷耐扑]技術常用的模型包括聚類模型[6]、貝葉斯網絡[7]、矩陣分解[8]等。

隨著推薦系統中用戶量和項目量的增長，在數據庫中查找相似用戶或項目會消耗大量的計算資源和時間。為此，Herlocker等人[9]提出一種基于項目聚類的協同過濾算法，該算法先對項目進行聚類，然后在各個簇中獨立應用基于鄰近關系的推薦算法，縮小了最鄰近用戶（項目）的搜索范圍，提高在線推薦的效率；Wei等人[10]提出的算法先對項目進行聚類，然后在每個簇中采用基于用戶的協同過濾算法進行推薦；Liao等人[11]在聚類后的每個項目簇中獨立應用隨機游走過程對項目進行排名；魏慧娟等人[12]先對用戶進行聚類，在線推薦時在目標用戶所屬簇的若干最鄰近簇中查找最鄰近用戶。Sarwar等人[13]提出基于二分k-means用戶聚類的協同過濾算法，該算法可以相對均勻地對用戶進行聚類；Koohi等人[14]提出基于模糊C-均值聚類模型的協同過濾算法；Tsai等人[15]提出基于聚類集成的協同過濾算法。在大數據背景下，部分學者[6，16]提出基于Hadoop分布式平臺的聚類協同過濾推薦算法，在云環境中具有良好的可擴展性。除了用戶-項目評分矩陣數據，郭弘毅等人[17]提出一種融合用戶社交網絡信息和興趣聚類的推薦算法；王媛媛等人[18]則結合用戶人口統計學信息和評分矩陣計算用戶之間的相似性，并使用分層近鄰傳播聚類算法對用戶進行聚類；Najafabadi等人[19]提出基于聚類和關聯規則挖掘的推薦算法，并結合項目屬性數據提高推薦效果。

以上基于聚類的協同過濾算法主要通過縮小最鄰近用戶或項目的搜索空間從而提高推薦的效率。本文提出一種基于聚類和隨機森林的協同過濾推薦算法（CRF）。首先通過聚類算法將用戶-項目評分矩陣轉換成適用于監督學習模型的數據；然后利用這些數據訓練隨機森林回歸模型，在線推薦時只需根據預先構建的隨機森林模型進行評分預測，無需查找最鄰近用戶或項目，提高了推薦的效率。

2 協同過濾算法

假設推薦系統中有n個用戶和m個項目，用戶對項目的歷史評分可由矩陣Rn×m表示（見表1）。評分矩陣中空缺的元素表示對應的用戶沒有給對應的項目評分。協同過濾推薦算法預測評分矩陣的空缺值，并向用戶推薦評分預測值較高的項目。

表1 評分矩陣的簡單例子

2.1 基于鄰近關系的協同過濾算法

基于鄰近關系的協同過濾推薦算法可分為基于用戶的協同過濾（User-based CF，UCF）算法和基于項目的協同過濾（Item-based CF，ICF）算法。前者的基本思想是，相似的用戶有共同的偏好，因此在向目標用戶推薦項目時，UCF算法在用戶集中查找與目標用戶最相似的若干用戶，并向目標用戶推薦最相似用戶所偏好的項目。而后者假設用戶會喜歡與其過去喜歡的項目相似的項目，因此ICF向用戶推薦與其過去喜歡的項目相似的項目。

在UCF算法中，目標用戶a對項目i的評分為：

其中，N(a)表示已經對項目i評分的用戶中，與目標用戶最相似的k個用戶；rui表示用戶u對項目i的評分；和表示用戶a和u歷史評分的均值；sim(a,u)表示兩用戶間的相似度。在UCF算法中，常用的相似度計算方式是Pearson相關系數（式（2））和余弦相似度（式（3）），C表示用戶a和u共同評分的項目集。

ICF算法通過目標用戶a過去對其他項目的評分預測該用戶對項目i的評分，即：

其中，N(i)表示用戶a已評分的項目中與項目i最相似的k個項目。

2.2 基于聚類的協同過濾算法

由于傳統基于鄰近關系的協同算法在進行推薦時，在所有用戶中查找與目標用戶最相似的k個用戶，推薦算法的效率隨著推薦系統中用戶數量的增加而降低。Sarwar等人[13]提出一種基于用戶聚類的協同過濾算法，算法首先將推薦系統的用戶劃分為多個不相交的用戶簇（集合），使得每個簇內用戶的相似度盡可能高，而簇間用戶的相似度盡可能低。在進行推薦時，僅需在目標用戶所屬的簇中應用UCF算法進行推薦即可，這縮小了最相似用戶的查找范圍，提高了推薦系統的效率。然而，搜索空間的縮小會導致評分預測精度的下降。

3 基于聚類和隨機森林的協同過濾算法

已有基于聚類的協同過濾算法主要通過縮小最鄰近用戶（或項目）的搜索空間提高推薦的效率。雖然聚類過程可離線完成，但最鄰近搜索仍然是一個在線的過程。本文對這一點進行了改進，對用戶和項目進行聚類后，計算每個用戶（項目）對每個簇的隸屬度，根據隸屬度和評分矩陣構造監督學習模型的訓練數據，并離線訓練隨機森林模型。在線推薦時根據預先構建的隨機森林模型進行評分預測，這個過程所需的時間遠小于最鄰近搜索過程。

3.1 聚類算法

聚類算法對數據中的對象進行分組，使得分組后同一組內的對象相似度盡可能高，而組間對象的相似度盡可能低[20]。聚類算法可分為三類：劃分聚類、基于密度的聚類、層次聚類[21]。這三類算法中最常用的分別為kmeans[22]、DBSCAN[23]和 BIRCH[24]。

本文采用二分k-means[25]聚類算法對用戶和項目進行聚類，該算法先將所有樣本劃分為兩簇，再對所有簇中樣本數最多的簇進行再次二分，重復此步驟直到簇數達到預先設定的正整數k為止。其具體流程如下：

（1）在樣本集中隨機選取兩個樣本作為初始簇中心；

（2）計算所有樣本與簇中心的相似度，并將這些樣本劃分到與其相似度最高的簇中；

（3）計算各簇中所有樣本的均值，作為新的簇中心；

（4）重復步驟（2）和（3），直到所有簇中心都不再改變；

（5）從劃分后的簇中選取樣本數最多的簇，對其進行步驟（1）至（4）的劃分；

（6）重復步驟（5）直到簇數達到k為止。

二分k-means算法的聚類效果會受到參數k的影響。實際應用中，最優簇數kopt需要經過多次試驗獲得。為了縮小搜索范圍，多數學者采用的經驗規則為：在區間內搜索kopt，n為樣本的數量。

3.2 隨機森林

監督學習是機器學習任務中根據帶標記的訓練數據推斷模型參數的過程[26]。訓練數據由訓練樣本組成，每個訓練樣本包含輸入變量（通常是一個向量）和輸出變量（數值或類別標簽）。通過訓練數據訓練得到的模型可用于預測新樣本（已知輸入變量）的輸出變量。

隨機森林是一種常用的監督學習模型，可以用于分類和預測，它利用Bootstrap重抽樣方法從原始樣本中有放回地抽取多個樣本集，利用每個樣本集進行決策樹建模。進行預測時，隨機森林取所有決策樹預測結果的均值作為最終預測結果。大量的理論和實證研究證明了隨機森林具有很高的預測準確率，對異常值和噪聲具有很好的容忍度，且不容易出現過擬合[27]。

3.3 數據轉換及評分預測

為了離線構建隨機森林模型，需要將用戶-項目評分矩陣轉換成適用于監督學習模型的數據。具體地，通過聚類算法對用戶進行聚類，聚類結束后，計算各個用戶對各個用戶簇的隸屬度，見表2。相應地，對項目向量進行同樣的轉換，得到表3所示的隸屬度矩陣。本文采用向量的余弦值表示樣本（用戶或項目）與簇中心的相似度，并以此作為樣本對簇的隸屬度，簇中心為該簇中所有樣本的均值。

表2 用戶隸屬度矩陣

表3 項目隸屬度矩陣

通過聚類得到的數據更適用于監督學習模型。一方面，用戶向量的維數得到大幅度降低。用戶-項目評分矩陣中用戶向量的維數等于項目的數量，而表2中用戶向量的維數等于用戶簇的數量，通常用戶簇的數量遠小于項目的數量。另一方面，經過數據轉換后的用戶向量不存在缺失值。同樣，轉換后的項目數據也具有以上兩個優點。

根據表1～表3的數據構造監督學習模型的輸入變量和輸出變量，得到如表4所示的數據。表1中每個元素對應表4中的一個樣本（一行），因此在用戶數和項目數各為n和m的推薦系統中，總共包含n×m個樣本。每個樣本的輸入變量隱含著該樣本對應的用戶和項目的信息，來自隸屬度矩陣；樣本的輸出變量對應著表1中的評分。

表4 監督學習模型的數據形式

數據轉換后，將輸出變量已存在的樣本作為隨機森林模型的訓練樣本，用于學習隨機森林的預測規則，這個訓練過程可離線完成。在線推薦時，系統根據隨機森林的預測規則進行評分預測，無需查找最鄰近用戶或項目，可提高實時推薦的效率。

4 實驗與分析

本文的實驗采用網站MovieLens（https：//grouplens.org/datasets/）提供的數據集ml-100k和Book-Crossing。其中ml-100k包含了來自943個用戶對1682部電影的100000次評分；Book-Crossing包含了278858個用戶對271379本書的1149780次評分，由于該數據集數據量較大，本文從中剔除評分次數少于20次的用戶和書籍，最后得到的實驗數據包含了23225次評分。對于每個實驗數據集，本文采用監督學習實驗中常用的方式，隨機抽取10%的樣本作為測試集，剩下的90%作為訓練集。訓練集用于訓練隨機森林模型，而測試集用于測試模型的預測精度。

本實驗將本文提出的算法CRF與UCF[28]、ICF[29]、基于聚類的推薦算法Clust[13]進行對比。以平均絕對誤差（Mean Absolute Error，MAE）和均方根誤差（Root Mean Square Error，RMSE）作為評分預測精度的評價標準：

其中，#T表示測試集中樣本的數量；r和r?分別表示評分的實際值和預測值。

圖1展示了各算法在兩個數據集上的表現（MAE和RMSE隨著k的變化情況，k為最鄰近用戶或項目的數量），MAE和RMSE越小說明評分預測的精度越高?？梢园l現，除了在Book-Crossing數據集上MAE值比ICF的大之外，本文提出的CRF在多數情況下表現最好。為了便于對比，圖1中Clust和CRF算法在聚類時，簇的數量設為10，后文會單獨分析簇的數量對推薦質量的影響。

圖2展示了Clust和CRF算法在兩個數據集上隨著簇數量的變化預測精度的變化情況。隨著簇數的增長，Clust的MAE和RMSE逐漸增長，而CRF的逐漸下降。不難解釋，隨著簇數的增長，每個簇中的樣本會減少，Clust算法在目標用戶所屬簇內查找得到的k個最鄰近用戶并非全局最近的k個用戶，因此預測精度會下降。而簇數一定程度增加反而有利于提升CRF算法的預測精度，因為這增加了隨機森林訓練數據的輸入變量的維度，可以訓練得到更加精確的隨機森林模型。

除了比較評分預測的精度之外，本文也對算法的在線推薦效率進行比較。圖3展示了各算法在線推薦所需時間隨著聚類簇數的變化情況。UCF和ICF算法沒有聚類的過程，因此在線推薦時長不受簇數變化的影響。隨著簇數的增長，Clust的在線推薦時長下降，因為最鄰近用戶的搜索范圍縮小。CRF的在線推薦時長幾乎不隨簇數的變化而變化，因為CRF在線推薦時無搜索最鄰近用戶（或項目）的過程，只需根據隨機森林模型預先得到的規則進行推薦即可，所以在線推薦時長遠小于其他模型。

圖1 評分預測精度比較

圖2 評分預測精度隨簇數的變化

圖3 在線推薦時長比較

5 結束語

針對基于鄰近關系的推薦算法在線推薦效率低的問題，本文提出了一種基于聚類和隨機森林的推薦算法。該算法通過聚類過程降低用戶和項目向量的維數，同時將用戶-項目評分矩陣轉換成適用于監督學習模型的數據，并用于訓練隨機森林模型。在線推薦時，系統只需根據離線時構造的隨機森林模型進行評分預測，不需要查找最鄰近用戶或項目，大幅提高了推薦的效率。此外，算法也保持了良好的預測精度，多數情況下比基于鄰近關系的推薦算法優越。