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

王衛(wèi)紅，曾英杰

浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023

1 引言

隨著社會信息化的發(fā)展，互聯(lián)網(wǎng)中的數(shù)據(jù)飛速增長，為了幫助用戶在海量數(shù)據(jù)中找到滿足用戶需求的數(shù)據(jù)，大量的研究者和學(xué)者對相關(guān)方案進(jìn)行了探索，由此便有了推薦技術(shù)的發(fā)展。

推薦算法主要有基于協(xié)同過濾的推薦[1]、基于內(nèi)容的推薦[2]和基于關(guān)聯(lián)規(guī)則的推薦[3]。其中，基于協(xié)同過濾的推薦是眾多學(xué)者研究的一種主流的推薦算法，現(xiàn)實(shí)中應(yīng)用也比較廣泛。

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

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

2 相關(guān)工作

傳統(tǒng)的基于用戶的協(xié)同過濾推薦算法通過匯總一些類似用戶先前給予該項(xiàng)目的評級來預(yù)測用戶對目標(biāo)項(xiàng)目的評級。主要步驟有：首先把評分?jǐn)?shù)據(jù)轉(zhuǎn)化為m行n列的用戶-項(xiàng)目評分矩陣，記為：Rm,n；然后根據(jù)評分矩陣計(jì)算每個(gè)用戶與其他所有用戶之間的相似度，并按照相似度獲得目標(biāo)用戶的前N個(gè)最近鄰用戶集Nu；最后通過目標(biāo)用戶u最近鄰用戶集Nu中的用戶對目標(biāo)項(xiàng)目i的評分預(yù)測目標(biāo)用戶u對目標(biāo)項(xiàng)目i的評分。

預(yù)測評分Pu,i計(jì)算公式表示如下：

2.1 用戶相似度計(jì)算

2.1.1 余弦相似度

余弦相似度通過用戶特征向量的夾角余弦值sim(u,v)來衡量用戶之間的相似程度[18]，假設(shè)有用戶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相關(guān)系數(shù)的相似度

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

2.2 Weighted Slope One算法

由于協(xié)同過濾推薦算法中使用的用戶評分?jǐn)?shù)據(jù)具有很高的稀疏性，使用Weighted Slope One算法填充用戶評分?jǐn)?shù)據(jù)中用戶未評分的項(xiàng)目可以降低評分?jǐn)?shù)據(jù)稀疏性。

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

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

然后根據(jù)評分偏差disi,j和目標(biāo)用戶u對項(xiàng)目i的評分ru,i計(jì)算目標(biāo)用戶u對項(xiàng)目j的預(yù)測評分preu,j，計(jì)算公式如下：

2.3 K-means算法

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

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

（1）隨機(jī)選取K個(gè)中心點(diǎn)。

（2）遍歷所有數(shù)據(jù)對象，計(jì)算所有數(shù)據(jù)對象到中心點(diǎn)的距離，并將每個(gè)數(shù)據(jù)對象劃分到距離最近的中心點(diǎn)中。

（3）計(jì)算每個(gè)聚類簇的平均值，并作為新的中心點(diǎn)。

（4）不斷迭代，重復(fù)步驟（2）和步驟（3），直到K個(gè)中心點(diǎn)不再變化或達(dá)到最大迭代次數(shù)。

2.4 融入密度和距離優(yōu)化K-means初始簇心

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

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

輸入：數(shù)據(jù)集的n個(gè)數(shù)據(jù)對象；聚類個(gè)數(shù)K；形成初始簇的最大簇內(nèi)個(gè)數(shù)Cmax，最小支持度minPts。

輸出：K個(gè)作為初始簇中心的核心數(shù)據(jù)對象。

（1）根據(jù)公式（6）計(jì)算數(shù)據(jù)集中數(shù)據(jù)對象兩兩間的歐式距離dis。

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

（3）在步驟（2）得到的核心對象中選取密度最大的一個(gè)數(shù)據(jù)對象和相距該數(shù)據(jù)對象最遠(yuǎn)的一個(gè)數(shù)據(jù)對象作為初始簇心。

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

（5）重復(fù)步驟（4），直至選取K個(gè)初始簇心。

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

3 本文算法

協(xié)同過濾算法使用評分?jǐn)?shù)據(jù)作為學(xué)習(xí)的數(shù)據(jù)源，評分?jǐn)?shù)據(jù)中的每條數(shù)據(jù)主要由用戶、項(xiàng)目和評分三部分組成。本文算法通過Weighted Slope One算法填充評分矩陣中的未評分項(xiàng)以降低評分?jǐn)?shù)據(jù)的稀疏性；引入了以用戶對項(xiàng)目類型的平均評分為衡量標(biāo)準(zhǔn)的用戶偏好；使用K-means聚類，通過對用戶聚類縮減了目標(biāo)用戶的最近鄰用戶計(jì)算范圍。

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

其中，對于每個(gè)用戶則有如表1所示的用戶-項(xiàng)目評分。

表1 用戶-項(xiàng)目評分

假設(shè)已知每個(gè)項(xiàng)目的類別或?qū)傩裕瑒t用戶在對項(xiàng)目評分時(shí)也隱式地給項(xiàng)目的類別評了分。對于用戶u，具有已評分項(xiàng)目集合Iu，每個(gè)項(xiàng)目i具有一個(gè)或多個(gè)類別Tt(t=1,2,…,k)。則用戶u對類別Tt的平均評分ru,t可表示如下：

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

表2 用戶-類別評分

由于每個(gè)用戶的喜好不同，則對于每一個(gè)項(xiàng)目類別的評分也應(yīng)該不同，甚至?xí)霈F(xiàn)某個(gè)用戶對某一類別從未有過評分?；谶@上述假設(shè)，本文將用戶對類別的評分添加到評分矩陣。添加了用戶類別評分后，降低了數(shù)據(jù)的稀疏性，增加了每個(gè)用戶間評分向量的差異，在計(jì)算用戶相似度時(shí)能夠提高精度。加入用戶類型評分后，評分矩陣可由公式（9）表示：

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

表3 用戶屬性和職業(yè)-類別評分

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

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

本文算法描述如下：

輸入：用戶-項(xiàng)目評分矩陣Rm,n，聚類個(gè)數(shù)K；

輸出：N個(gè)推薦項(xiàng)目。

（1）通過用戶-項(xiàng)目評分矩陣Rm,n計(jì)算得出用戶-類別評分矩陣R1，并合并兩個(gè)評分矩陣，得到評分矩陣R2。

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

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

（4）使用公式（6）計(jì)算目標(biāo)用戶u和K個(gè)簇心之間的距離，并把目標(biāo)用戶u添加到距離最近的簇中。

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

（6）根據(jù)目標(biāo)用戶u最近鄰居集Nu中的用戶對項(xiàng)目的評分，使用公式（1）計(jì)算目標(biāo)用戶u對其未評分項(xiàng)目的預(yù)測評分，并把預(yù)測評分最高的前N個(gè)未評分項(xiàng)目推薦給目標(biāo)用戶u。

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

圖1 本文算法流程圖

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

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

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)集與評估標(biāo)準(zhǔn)

實(shí)驗(yàn)中采用美國明尼蘇達(dá)大學(xué)GroupLens項(xiàng)目組提供的MovieLens數(shù)據(jù)集對本文算法的性能進(jìn)行測試。其中包括100 KB、1 MB、10 MB三個(gè)規(guī)模的數(shù)據(jù)集。本文采用100 KB的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中包括943個(gè)用戶對1 682部電影的10萬條評分?jǐn)?shù)據(jù)，電影類別總共有18種，評分標(biāo)準(zhǔn)為1到5之間的整數(shù)。數(shù)據(jù)集中用戶對某一電影的評分值越大說明用戶越喜歡這部電影。為了評估算法性能，將數(shù)據(jù)集的80%作為訓(xùn)練集，其余的20%作為測試集。

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

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

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

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

圖2 MAE對比圖

圖3 RMSE對比圖

5 結(jié)束語

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