基于聚類和隨機(jī)森林的協(xié)同過濾推薦算法

楊興雨，李華平，張宇波

YANG Xingyu,LI Huaping,ZHANG Yubo

廣東工業(yè)大學(xué) 管理學(xué)院，廣州 510520

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

1 引言

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

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

協(xié)同過濾算法根據(jù)用戶-項(xiàng)目評分矩陣中已有的評分，利用用戶間或者項(xiàng)目間的相關(guān)關(guān)系預(yù)測評分矩陣中缺失的評分，然后根據(jù)評分的高低衡量用戶對項(xiàng)目的偏好程度。協(xié)同過濾算法可分為基于鄰近關(guān)系（Neighborhood-based）的推薦算法和基于模型（Model-based）的推薦算法。前者根據(jù)與目標(biāo)用戶相似的用戶對某項(xiàng)目的評分，預(yù)測目標(biāo)用戶對該項(xiàng)目的評分；或者在目標(biāo)用戶已評分的項(xiàng)目中搜索與目標(biāo)項(xiàng)目最相似的k個(gè)項(xiàng)目，根據(jù)目標(biāo)用戶對這些項(xiàng)目的評分，預(yù)測其對目標(biāo)項(xiàng)目的評分。基于鄰近關(guān)系的推薦算法易于理解和實(shí)現(xiàn)，但每次進(jìn)行推薦時(shí)都要查找目標(biāo)用戶（項(xiàng)目）的k最鄰近用戶（項(xiàng)目）。當(dāng)推薦系統(tǒng)面臨數(shù)以百萬甚至千萬級別的用戶和項(xiàng)目時(shí)，計(jì)算開銷非常龐大，算法的實(shí)時(shí)性將很難保證，相應(yīng)的推薦系統(tǒng)將面臨可擴(kuò)展性問題[2]。針對此問題，學(xué)者提出的解決方法主要分為兩類：一類是采用并行存儲(chǔ)和計(jì)算技術(shù)[3-5]，提高推薦系統(tǒng)的可擴(kuò)展性；另一類方法則是采用基于模型的推薦技術(shù)，此類技術(shù)可離線根據(jù)用戶-項(xiàng)目矩陣構(gòu)建模型，在線根據(jù)模型產(chǎn)生推薦，提高在線推薦效率。基于模型的推薦技術(shù)常用的模型包括聚類模型[6]、貝葉斯網(wǎng)絡(luò)[7]、矩陣分解[8]等。

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

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

2 協(xié)同過濾算法

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

表1 評分矩陣的簡單例子

2.1 基于鄰近關(guān)系的協(xié)同過濾算法

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

在UCF算法中，目標(biāo)用戶a對項(xiàng)目i的評分為：

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

ICF算法通過目標(biāo)用戶a過去對其他項(xiàng)目的評分預(yù)測該用戶對項(xiàng)目i的評分，即：

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

2.2 基于聚類的協(xié)同過濾算法

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

3 基于聚類和隨機(jī)森林的協(xié)同過濾算法

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

3.1 聚類算法

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

本文采用二分k-means[25]聚類算法對用戶和項(xiàng)目進(jìn)行聚類，該算法先將所有樣本劃分為兩簇，再對所有簇中樣本數(shù)最多的簇進(jìn)行再次二分，重復(fù)此步驟直到簇?cái)?shù)達(dá)到預(yù)先設(shè)定的正整數(shù)k為止。其具體流程如下：

（1）在樣本集中隨機(jī)選取兩個(gè)樣本作為初始簇中心；

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

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

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

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

（6）重復(fù)步驟（5）直到簇?cái)?shù)達(dá)到k為止。

二分k-means算法的聚類效果會(huì)受到參數(shù)k的影響。實(shí)際應(yīng)用中，最優(yōu)簇?cái)?shù)kopt需要經(jīng)過多次試驗(yàn)獲得。為了縮小搜索范圍，多數(shù)學(xué)者采用的經(jīng)驗(yàn)規(guī)則為：在區(qū)間內(nèi)搜索kopt，n為樣本的數(shù)量。

3.2 隨機(jī)森林

監(jiān)督學(xué)習(xí)是機(jī)器學(xué)習(xí)任務(wù)中根據(jù)帶標(biāo)記的訓(xùn)練數(shù)據(jù)推斷模型參數(shù)的過程[26]。訓(xùn)練數(shù)據(jù)由訓(xùn)練樣本組成，每個(gè)訓(xùn)練樣本包含輸入變量（通常是一個(gè)向量）和輸出變量（數(shù)值或類別標(biāo)簽）。通過訓(xùn)練數(shù)據(jù)訓(xùn)練得到的模型可用于預(yù)測新樣本（已知輸入變量）的輸出變量。

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

3.3 數(shù)據(jù)轉(zhuǎn)換及評分預(yù)測

為了離線構(gòu)建隨機(jī)森林模型，需要將用戶-項(xiàng)目評分矩陣轉(zhuǎn)換成適用于監(jiān)督學(xué)習(xí)模型的數(shù)據(jù)。具體地，通過聚類算法對用戶進(jìn)行聚類，聚類結(jié)束后，計(jì)算各個(gè)用戶對各個(gè)用戶簇的隸屬度，見表2。相應(yīng)地，對項(xiàng)目向量進(jìn)行同樣的轉(zhuǎn)換，得到表3所示的隸屬度矩陣。本文采用向量的余弦值表示樣本（用戶或項(xiàng)目）與簇中心的相似度，并以此作為樣本對簇的隸屬度，簇中心為該簇中所有樣本的均值。

表2 用戶隸屬度矩陣

表3 項(xiàng)目隸屬度矩陣

通過聚類得到的數(shù)據(jù)更適用于監(jiān)督學(xué)習(xí)模型。一方面，用戶向量的維數(shù)得到大幅度降低。用戶-項(xiàng)目評分矩陣中用戶向量的維數(shù)等于項(xiàng)目的數(shù)量，而表2中用戶向量的維數(shù)等于用戶簇的數(shù)量，通常用戶簇的數(shù)量遠(yuǎn)小于項(xiàng)目的數(shù)量。另一方面，經(jīng)過數(shù)據(jù)轉(zhuǎn)換后的用戶向量不存在缺失值。同樣，轉(zhuǎn)換后的項(xiàng)目數(shù)據(jù)也具有以上兩個(gè)優(yōu)點(diǎn)。

根據(jù)表1～表3的數(shù)據(jù)構(gòu)造監(jiān)督學(xué)習(xí)模型的輸入變量和輸出變量，得到如表4所示的數(shù)據(jù)。表1中每個(gè)元素對應(yīng)表4中的一個(gè)樣本（一行），因此在用戶數(shù)和項(xiàng)目數(shù)各為n和m的推薦系統(tǒng)中，總共包含n×m個(gè)樣本。每個(gè)樣本的輸入變量隱含著該樣本對應(yīng)的用戶和項(xiàng)目的信息，來自隸屬度矩陣；樣本的輸出變量對應(yīng)著表1中的評分。

表4 監(jiān)督學(xué)習(xí)模型的數(shù)據(jù)形式

數(shù)據(jù)轉(zhuǎn)換后，將輸出變量已存在的樣本作為隨機(jī)森林模型的訓(xùn)練樣本，用于學(xué)習(xí)隨機(jī)森林的預(yù)測規(guī)則，這個(gè)訓(xùn)練過程可離線完成。在線推薦時(shí)，系統(tǒng)根據(jù)隨機(jī)森林的預(yù)測規(guī)則進(jìn)行評分預(yù)測，無需查找最鄰近用戶或項(xiàng)目，可提高實(shí)時(shí)推薦的效率。

4 實(shí)驗(yàn)與分析

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

本實(shí)驗(yàn)將本文提出的算法CRF與UCF[28]、ICF[29]、基于聚類的推薦算法Clust[13]進(jìn)行對比。以平均絕對誤差（Mean Absolute Error，MAE）和均方根誤差（Root Mean Square Error，RMSE）作為評分預(yù)測精度的評價(jià)標(biāo)準(zhǔn)：

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

圖1展示了各算法在兩個(gè)數(shù)據(jù)集上的表現(xiàn)（MAE和RMSE隨著k的變化情況，k為最鄰近用戶或項(xiàng)目的數(shù)量），MAE和RMSE越小說明評分預(yù)測的精度越高。可以發(fā)現(xiàn)，除了在Book-Crossing數(shù)據(jù)集上MAE值比ICF的大之外，本文提出的CRF在多數(shù)情況下表現(xiàn)最好。為了便于對比，圖1中Clust和CRF算法在聚類時(shí)，簇的數(shù)量設(shè)為10，后文會(huì)單獨(dú)分析簇的數(shù)量對推薦質(zhì)量的影響。

圖2展示了Clust和CRF算法在兩個(gè)數(shù)據(jù)集上隨著簇?cái)?shù)量的變化預(yù)測精度的變化情況。隨著簇?cái)?shù)的增長，Clust的MAE和RMSE逐漸增長，而CRF的逐漸下降。不難解釋，隨著簇?cái)?shù)的增長，每個(gè)簇中的樣本會(huì)減少，Clust算法在目標(biāo)用戶所屬簇內(nèi)查找得到的k個(gè)最鄰近用戶并非全局最近的k個(gè)用戶，因此預(yù)測精度會(huì)下降。而簇?cái)?shù)一定程度增加反而有利于提升CRF算法的預(yù)測精度，因?yàn)檫@增加了隨機(jī)森林訓(xùn)練數(shù)據(jù)的輸入變量的維度，可以訓(xùn)練得到更加精確的隨機(jī)森林模型。

除了比較評分預(yù)測的精度之外，本文也對算法的在線推薦效率進(jìn)行比較。圖3展示了各算法在線推薦所需時(shí)間隨著聚類簇?cái)?shù)的變化情況。UCF和ICF算法沒有聚類的過程，因此在線推薦時(shí)長不受簇?cái)?shù)變化的影響。隨著簇?cái)?shù)的增長，Clust的在線推薦時(shí)長下降，因?yàn)樽钹徑脩舻乃阉鞣秶s小。CRF的在線推薦時(shí)長幾乎不隨簇?cái)?shù)的變化而變化，因?yàn)镃RF在線推薦時(shí)無搜索最鄰近用戶（或項(xiàng)目）的過程，只需根據(jù)隨機(jī)森林模型預(yù)先得到的規(guī)則進(jìn)行推薦即可，所以在線推薦時(shí)長遠(yuǎn)小于其他模型。

圖1 評分預(yù)測精度比較

圖2 評分預(yù)測精度隨簇?cái)?shù)的變化

圖3 在線推薦時(shí)長比較

5 結(jié)束語

針對基于鄰近關(guān)系的推薦算法在線推薦效率低的問題，本文提出了一種基于聚類和隨機(jī)森林的推薦算法。該算法通過聚類過程降低用戶和項(xiàng)目向量的維數(shù)，同時(shí)將用戶-項(xiàng)目評分矩陣轉(zhuǎn)換成適用于監(jiān)督學(xué)習(xí)模型的數(shù)據(jù)，并用于訓(xùn)練隨機(jī)森林模型。在線推薦時(shí)，系統(tǒng)只需根據(jù)離線時(shí)構(gòu)造的隨機(jī)森林模型進(jìn)行評分預(yù)測，不需要查找最鄰近用戶或項(xiàng)目，大幅提高了推薦的效率。此外，算法也保持了良好的預(yù)測精度，多數(shù)情況下比基于鄰近關(guān)系的推薦算法優(yōu)越。