基于用戶聚類與Slope One填充的協(xié)同推薦算法

龔 敏，鄧珍榮，黃文明

1.桂林電子科技大學(xué) 計(jì)算機(jī)科學(xué)與信息安全學(xué)院，廣西 桂林 541004

2.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

1 引言

隨著互聯(lián)網(wǎng)上各式各樣信息的爆炸式增長(zhǎng)，用戶經(jīng)常需面對(duì)海量信息數(shù)據(jù)卻無(wú)從下手，從而形成了“信息過(guò)載現(xiàn)象”。目前基于關(guān)鍵字的搜索引擎雖然能夠被動(dòng)地響應(yīng)用戶的搜索請(qǐng)求，但千篇一律的搜索結(jié)果已經(jīng)無(wú)法滿足用戶個(gè)性化的需求，個(gè)性化推薦系統(tǒng)作為解決該現(xiàn)狀的有效手段得到了深入的研究和發(fā)展，但個(gè)性化推薦的質(zhì)量會(huì)受到它所采用的推薦算法[1]的影響。推薦算法中協(xié)同過(guò)濾算法（Collaborative-Filtering）已成為目前應(yīng)用最廣泛的推薦算法之一，根據(jù)具體處理方式不同，主要分為基于模型（Model-Based）和基于內(nèi)存（Memory-Based）的協(xié)同過(guò)濾算法[2]。其中基于內(nèi)存的協(xié)同過(guò)濾算法的最大優(yōu)勢(shì)在于它基于集體智慧的思想，通過(guò)對(duì)用戶歷史行為數(shù)據(jù)的挖據(jù)，可以找到用戶或項(xiàng)目的相似用戶集或項(xiàng)目集，依靠這些有共同興趣的用戶或者喜歡這個(gè)項(xiàng)目的用戶也會(huì)喜歡跟他相似項(xiàng)目的理論對(duì)目標(biāo)用戶進(jìn)行推薦，從而能夠使得單憑內(nèi)容難以分析的項(xiàng)目也能夠推薦給用戶。根據(jù)相似對(duì)象的不同，基于內(nèi)存的協(xié)同過(guò)濾算法主要分為基于用戶（User-Based）的協(xié)同過(guò)濾[3-4]和基于項(xiàng)目（Item-Based）的協(xié)同過(guò)濾[5-6]。雖然基于內(nèi)存的協(xié)同過(guò)濾算法可解釋性強(qiáng)，同時(shí)又能取得較為可觀的推薦效果，但隨著時(shí)代發(fā)展，用戶數(shù)和項(xiàng)目數(shù)都在不斷地增加，便帶來(lái)了其他問(wèn)題和挑戰(zhàn)。其中由于用戶對(duì)整個(gè)項(xiàng)目集的評(píng)價(jià)非常少，導(dǎo)致用戶評(píng)分矩陣越來(lái)越稀疏，在此情況下，高維的稀疏數(shù)據(jù)會(huì)嚴(yán)重降低推薦的質(zhì)量。除此之外，傳統(tǒng)協(xié)同過(guò)濾算法必須掃描整個(gè)數(shù)據(jù)集，計(jì)算量大，因而導(dǎo)致可擴(kuò)展性差[7]。

基于上述問(wèn)題，許多研究人員從不同角度引入基于模型的算法到傳統(tǒng)的基于內(nèi)存協(xié)同過(guò)濾算法中，例如聚類（Clustering）分析模型[8-9]、主成分分析（Principal Component Analysis，PCA）模型[10]、奇異值分解（Singular Value Decomposition，SVD）模型[11]等引入到傳統(tǒng)的基于內(nèi)存的協(xié)同過(guò)濾推薦算法中，通過(guò)降維，可明顯縮小目標(biāo)對(duì)象搜索最近鄰居的范圍。由于維度的下降，雖然數(shù)據(jù)量沒(méi)有發(fā)生實(shí)質(zhì)性的改變，但在每個(gè)低維矩陣中數(shù)據(jù)稀疏性得到了緩解，使得推薦的效果得到明顯提升。除了上述提到的算法外，基于模型的算法還包括樸素貝葉斯模型（Navie Bayesian Model）[12]、基于概率模型的隱含主題分析（Probabilistic Latent Semantic Analysis，PLSA）[13]、圖模型[14]等。

為了使推薦系統(tǒng)既有一定的可擴(kuò)展性，又有較高的準(zhǔn)確率，本文提出了基于用戶聚類與Slope One填充的協(xié)同推薦算法。首先提取用戶特征屬性，并以此構(gòu)造用戶屬性矩陣，運(yùn)用基于最小生成樹(shù)的K-means算法對(duì)整個(gè)用戶集進(jìn)行聚類。然后在生成的各用戶類中利用Slope One算法對(duì)評(píng)分缺失項(xiàng)進(jìn)行填充，在此基礎(chǔ)上對(duì)聚類中的用戶分別進(jìn)行基于用戶和基于項(xiàng)目的協(xié)同過(guò)濾推薦，最終有效融合兩次推薦的結(jié)果。

2 基于最小生成樹(shù)的K-means聚類算法

聚類算法中K-means算法是一種基于劃分、實(shí)現(xiàn)簡(jiǎn)單、收斂速度快的分析算法[15]，正是因?yàn)樗倪@些優(yōu)點(diǎn)，使其在實(shí)際應(yīng)用中有很大的優(yōu)勢(shì)，成為當(dāng)前使用最為廣泛的聚類算法之一。但傳統(tǒng)的K-means聚類算法有一個(gè)明顯的缺點(diǎn)，選取初始聚類中心是隨機(jī)的，一旦初始聚類中心選擇不合理，并以此迭代地改變中心直至達(dá)到聚類準(zhǔn)則收斂時(shí)，易導(dǎo)致算法失去原有的特點(diǎn)，無(wú)法得出最優(yōu)的結(jié)果。為了避免選取初始聚類的隨機(jī)性帶來(lái)的不穩(wěn)定聚類結(jié)果，本文采用一種基于最小生成樹(shù)的K-means聚類算法，將用戶屬性相似度作為兩兩用戶頂點(diǎn)邊的權(quán)值，通過(guò)使用Prim最小生成樹(shù)算法得到最小生成樹(shù)，并通過(guò)最小生成樹(shù)找到合理的初始聚類中心，然后進(jìn)行K-means算法迭代，最終形成K個(gè)有效的用戶聚類。

2.1 用戶屬性相似度

用戶屬性相似度是最小生成樹(shù)模型構(gòu)造的重要依據(jù)，也是該聚類算法的第一步。用戶屬性相似度反映的是兩個(gè)用戶屬性之間的距離，值越大則兩個(gè)用戶屬性距離越遠(yuǎn)，反之則兩個(gè)用戶屬性距離越近。假設(shè)每個(gè)用戶是一個(gè)V維向量，而用戶向量的維度便代表了用戶屬性特征，則用戶屬性矩陣為 A=(aim)n×v，其中aim表示用戶i的第m個(gè)屬性特征。本算法采用的用戶相似度定義如式（1）所示，其中Us(i,j)表示用戶i與用戶 j之間的用戶屬性相似度：

計(jì)算各個(gè)用戶之間的屬性相似度，將其作為由用戶集構(gòu)成的帶權(quán)值的以用戶作為頂點(diǎn)的無(wú)向圖中的頂點(diǎn)邊的權(quán)值，依據(jù)該邊權(quán)值構(gòu)造最小生成樹(shù)模型。

2.2 最小生成樹(shù)K-means算法

由式（1）得到了用戶的屬性相似度，并以此構(gòu)造了以用戶作為頂點(diǎn)，以用戶屬性相似度作為頂點(diǎn)邊的權(quán)值的無(wú)向賦權(quán)圖。而最小生成樹(shù)K-means算法就是建立在這個(gè)無(wú)向賦權(quán)圖上，首先利用Prim算法找到最小生成樹(shù)，再刪除最小生成樹(shù)中權(quán)值最大的K-1條邊，這樣將得到K個(gè)互不連通的連通子圖，如圖1所示。

圖1 K個(gè)連通子圖生成圖

然后初始聚類中心便是這K個(gè)連通子圖中所有對(duì)象的中心值。最后K-means算法將以上述得到的初始聚類中心開(kāi)始進(jìn)行用戶聚類，而不是傳統(tǒng)的隨機(jī)選擇初始聚類中心。本文采用的聚類算法具體如下：

算法1基于最小生成樹(shù)的K-means聚類算法

輸入：用戶屬性矩陣A,目標(biāo)用戶U,聚類個(gè)數(shù)K。

輸出：目標(biāo)用戶U所在的用戶簇。

（1）根據(jù)用戶屬性矩陣A,利用Prim最小生成樹(shù)算法，求出最小生成樹(shù)，并將權(quán)值按照從小到大的順序排列。

（2）根據(jù)權(quán)值由小到大排列形成數(shù)據(jù)集P={u1,u2,…,un}，找到距離最近的兩個(gè)ui和uj，并求出它們之間的中心點(diǎn)Mij。

（3）刪除ui和uj，并將 Mij放入余下數(shù)據(jù)集中形成P={u1,u2,…,Mij,…,un},集合P中元素個(gè)數(shù)若大于K則回到步驟（2）。

（4）此時(shí)集合P中的K個(gè)元素即為初始聚類中心。計(jì)算用戶集中每個(gè)用戶距離K個(gè)質(zhì)心的距離，把用戶加入距離最近的質(zhì)心所在的簇中。

（5）每個(gè)用戶都已經(jīng)屬于其中的一個(gè)簇，然后根據(jù)每個(gè)簇中包含的數(shù)據(jù)向量集合，重新計(jì)算得到新的質(zhì)心。

（6）如果新計(jì)算的質(zhì)心和原來(lái)的質(zhì)心之間的距離達(dá)到設(shè)置的閾值，算法終止；否則迭代步驟（4）～（6）。

3 Slope One算法填充稀疏矩陣

Slope One算法最早是由丹尼爾教授于2005年提出的推薦算法，該算法以線性回歸模型作為預(yù)測(cè)模型，根據(jù)項(xiàng)目評(píng)分差值和用戶的歷史評(píng)分記錄來(lái)近似估計(jì)該用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分[16]。Slope One算法思想簡(jiǎn)單，實(shí)現(xiàn)相對(duì)容易，時(shí)間和空間復(fù)雜度都較小，一旦面對(duì)較為稀疏的用戶-項(xiàng)目評(píng)分矩陣，Slope One算法可利用的項(xiàng)目評(píng)分較少，會(huì)導(dǎo)致評(píng)分預(yù)測(cè)準(zhǔn)確率直線下降，推薦效果隨之降低。正因?yàn)榇嬖谏鲜鰡?wèn)題，本文利用Slope One算法填充2.2節(jié)中基于用戶聚類后的K個(gè)用戶-項(xiàng)目評(píng)分矩陣作為最終填充矩陣。

Slope One算法的本質(zhì)思想其實(shí)是形式簡(jiǎn)單的回歸表達(dá)式w=y+b，其中w為需要預(yù)測(cè)的用戶u對(duì)項(xiàng)目i的評(píng)分，y為用戶u對(duì)項(xiàng)目i以外的項(xiàng)目評(píng)分，b為項(xiàng)目i相對(duì)于項(xiàng)目 j評(píng)分的平均偏差，表示為Devi,j，如式（2）所示。其中Si,j(U)為對(duì)項(xiàng)目i和項(xiàng)目 j均有評(píng)分的用戶集合。

因此，通過(guò)公式Devi,j+Ru,j可計(jì)算出用戶u對(duì)itemi的預(yù)測(cè)評(píng)分，從而得到預(yù)測(cè)均值計(jì)算公式如下：

其中，Ri表示所有用戶已經(jīng)給予評(píng)分滿足條件（i≠j且Si,j非空）的item集合。

同時(shí)本文在計(jì)算評(píng)分時(shí)是在目標(biāo)用戶所在聚類中進(jìn)行的。例如，表1中假設(shè)U1、U2、U3屬于同一聚類，現(xiàn)需計(jì)算U2對(duì)I1的評(píng)分并填充。首先計(jì)算項(xiàng)目I1與項(xiàng)目I2的平均偏差((1-2)+(4-5))/2=-1,然后據(jù)此可得用戶U2對(duì)項(xiàng)目I1的評(píng)分是3-1=2；接著計(jì)算項(xiàng)目I1與項(xiàng)目I3的平均偏差(1-3)/1=-2，并由此計(jì)算出用戶U2對(duì)項(xiàng)目I1的評(píng)分是3-2=1；最后預(yù)測(cè)用戶U2對(duì)項(xiàng)目I1的評(píng)分是(2+1)/2=1.5。利用Slope One算法對(duì)初始各用戶聚類的用戶-評(píng)分矩陣進(jìn)行處理，矩陣中的大部分空缺值就會(huì)被填充，從而有效降低了矩陣的稀疏程度。

表1 項(xiàng)目評(píng)分矩陣

4 基于用戶和項(xiàng)目的混合協(xié)同過(guò)濾推薦與時(shí)間復(fù)雜度

協(xié)同過(guò)濾算法是1992年Goldberg等學(xué)者提出的，該算法是以目標(biāo)對(duì)象相似的用戶或項(xiàng)目為基礎(chǔ)進(jìn)行推薦。為了提高推薦算法的精度，本文提出一種線性混合基于用戶和基于項(xiàng)目的協(xié)同過(guò)濾推薦算法，在每個(gè)用戶類下，利用填充后的數(shù)據(jù)集進(jìn)行有效的推薦。本文的算法流程可以用圖2來(lái)表示。

圖2 本文算法流程

混合用戶和項(xiàng)目的協(xié)同過(guò)濾推薦具體方法是先用皮爾森相關(guān)系數(shù)[17]，如式（4）所示，定義用戶相似度，并通過(guò)最近鄰搜索得到目標(biāo)用戶的最近鄰居集合。其中s(u,v)表示用戶u與用戶v之間的用戶相似度，分別表示用戶u、v在所有項(xiàng)目上的評(píng)分均值。

通過(guò)計(jì)算用戶的相似度，進(jìn)行最近鄰搜索得到目標(biāo)用戶u的最近鄰居集合N(u)，則用戶u對(duì)未評(píng)分項(xiàng)目i的預(yù)測(cè)得分計(jì)算公式如式（5）所示：

再由余弦相似度如式（6）所示，定義項(xiàng)目相似度，搜索目標(biāo)項(xiàng)目最近鄰。其中s(i,j)表示項(xiàng)目i、j之間余弦相似度[11]，同時(shí)對(duì)項(xiàng)目i、j有過(guò)評(píng)分的用戶集合則由U(ij)表示。

通過(guò)計(jì)算項(xiàng)目之間的相似度，根據(jù)Top-N得到預(yù)測(cè)項(xiàng)目i的最近鄰居集合N(i)，則用戶u對(duì)未評(píng)分項(xiàng)目i的預(yù)測(cè)得分如式（7）所示分別表示項(xiàng)目i、j在所有用戶上的評(píng)分均值。

為了有效融合用戶和項(xiàng)目協(xié)同過(guò)濾推薦所得的預(yù)測(cè)評(píng)分，本文引入不確定近鄰因子的線性融合框架[18]，利用一個(gè)可調(diào)整因子λ將兩者的預(yù)測(cè)結(jié)果融合，產(chǎn)生最終的預(yù)測(cè)評(píng)分。λ的計(jì)算公式如式（8）所示，其中m′表示基于用戶的協(xié)同過(guò)濾算法中產(chǎn)生的最近鄰個(gè)數(shù)，n'表示基于項(xiàng)目的協(xié)同過(guò)濾算法中產(chǎn)生的最近鄰個(gè)數(shù)。

最終融合后的模型如式（9）所示，利用得到的預(yù)測(cè)評(píng)分，生成Top-N個(gè)推薦結(jié)果。

關(guān)于模型的時(shí)間復(fù)雜度，雖然模型需要分多步驟完成，但對(duì)于用戶聚類和對(duì)聚類結(jié)果進(jìn)行Slope One填充這兩部分，都可以進(jìn)行離線并行化計(jì)算。并且由于已經(jīng)離線并行化得到聚類且填充后的K個(gè)矩陣，人們?cè)诓檎夷繕?biāo)用戶或項(xiàng)目的鄰居時(shí)，只需在目標(biāo)元素對(duì)應(yīng)的小矩陣中計(jì)算簇中元素與目標(biāo)元素的相似度，這就避免了傳統(tǒng)協(xié)同過(guò)濾推薦算法中對(duì)全量評(píng)分矩陣進(jìn)行相似度計(jì)算而使得時(shí)間復(fù)雜度過(guò)大的問(wèn)題，節(jié)省了時(shí)間和空間，提高了推薦的實(shí)時(shí)性。

5 實(shí)驗(yàn)結(jié)果及分析

5.1 數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)采用的是美國(guó)學(xué)者公開(kāi)的MovieLens數(shù)據(jù)集，具體實(shí)驗(yàn)數(shù)據(jù)相關(guān)信息如表2所示。其中用戶特征信息，本文選取了其中三個(gè)用戶屬性作為用戶特征聚類的依據(jù)，并根據(jù)專家意見(jiàn)將每個(gè)屬性分類表示成數(shù)值形式[19]，age（1～5）、gender（0～1）、occupation（1～8）。本文隨機(jī)選取實(shí)驗(yàn)評(píng)分?jǐn)?shù)據(jù)中的80%用作訓(xùn)練集，20%用作測(cè)試集。

表2 實(shí)驗(yàn)數(shù)據(jù)相關(guān)信息

5.2 評(píng)價(jià)指標(biāo)

本文主要采用平均絕對(duì)偏差（Mean Absolute Error，MAE）、均方誤差（Root Mean Square Error，RMSE）來(lái)度量預(yù)測(cè)評(píng)分的偏差。MAE和RMSE是目前使用比較廣泛、業(yè)界認(rèn)可度較高的評(píng)估推薦系統(tǒng)質(zhì)量的評(píng)價(jià)指標(biāo)，這也正是本文選取這兩項(xiàng)來(lái)測(cè)試算法的有效性的原因。MAE和RMSE均為誤差值，誤差值越小說(shuō)明算法的預(yù)測(cè)精度越高，具體的計(jì)算方式為式（9）和式（10），其中N表示測(cè)試集的大小。

5.3 算法結(jié)果對(duì)比及分析

為了驗(yàn)證本文算法的有效性，分別對(duì)基于用戶的協(xié)同過(guò)濾（UBCF）[20]，基于項(xiàng)目的協(xié)同過(guò)濾（IBCF）[21]，混合用戶和項(xiàng)目的協(xié)同過(guò)濾（UICF）[22]，先用戶特征聚類再混合用戶和項(xiàng)目的協(xié)同過(guò)濾（CUICF）[23]，先填充稀疏矩陣再混合用戶和項(xiàng)目的協(xié)同過(guò)濾（FUICF）[24]，以及本文的先用戶特征聚類再填充稀疏矩陣最后混合用戶和項(xiàng)目的協(xié)同過(guò)濾（CFUICF）進(jìn)行實(shí)驗(yàn)。經(jīng)過(guò)多次實(shí)驗(yàn)發(fā)現(xiàn)，用戶數(shù)據(jù)集上聚成7個(gè)簇時(shí)，算法整體精度和擴(kuò)展性得到一個(gè)較好的折中，因此本文實(shí)驗(yàn)聚類簇設(shè)定為7個(gè)。這六種算法都采用五折交叉驗(yàn)證在MovieLens數(shù)據(jù)集上進(jìn)行100次實(shí)驗(yàn)，統(tǒng)計(jì)結(jié)果并取平均RMSE和MAE，結(jié)果如圖3和圖4所示。

圖3 RMSE對(duì)比圖

圖4 MAE對(duì)比圖

由圖可知，本文提出的推薦算法比其他五種推薦算法確實(shí)在RMSE和MAE上有較大的提高，說(shuō)明此推薦算法可以提高推薦系統(tǒng)的推薦質(zhì)量，驗(yàn)證了算法的有效性。

6 結(jié)束語(yǔ)

本文提出了基于用戶聚類與Slope One填充的協(xié)同過(guò)濾算法。首先基于用戶特征進(jìn)行聚類，其次填充稀疏矩陣，最后線性融合兩個(gè)基于內(nèi)存的協(xié)同過(guò)濾算法。本文算法彌補(bǔ)了聚類算法和協(xié)同過(guò)濾算法各自的不足。聚類算法的融入使得協(xié)同過(guò)濾算法在可擴(kuò)展性上得到提升，而在聚類下填充稀疏矩陣，又可以依靠聚類中用戶的隱性相似提高填充準(zhǔn)確率，同時(shí)緩解數(shù)據(jù)稀疏性，提高了用戶和項(xiàng)目的近鄰量，最終效果在推薦質(zhì)量上得以體現(xiàn)。在協(xié)同過(guò)濾算法中又結(jié)合兩種基于內(nèi)存的協(xié)同過(guò)濾方法，兩種方法發(fā)揮了各自推薦的優(yōu)勢(shì)，使得推薦質(zhì)量有了明顯的提高。針對(duì)本文算法中的不足之處，下一步的工作是對(duì)填充算法的優(yōu)化和時(shí)間因子對(duì)協(xié)同過(guò)濾推薦的影響展開(kāi)研究。