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

龔 敏，鄧珍榮，黃文明

1.桂林電子科技大學 計算機科學與信息安全學院，廣西 桂林 541004

2.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林 541004

1 引言

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

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

為了使推薦系統既有一定的可擴展性，又有較高的準確率，本文提出了基于用戶聚類與Slope One填充的協同推薦算法。首先提取用戶特征屬性，并以此構造用戶屬性矩陣，運用基于最小生成樹的K-means算法對整個用戶集進行聚類。然后在生成的各用戶類中利用Slope One算法對評分缺失項進行填充，在此基礎上對聚類中的用戶分別進行基于用戶和基于項目的協同過濾推薦，最終有效融合兩次推薦的結果。

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

聚類算法中K-means算法是一種基于劃分、實現簡單、收斂速度快的分析算法[15]，正是因為它的這些優點，使其在實際應用中有很大的優勢，成為當前使用最為廣泛的聚類算法之一。但傳統的K-means聚類算法有一個明顯的缺點，選取初始聚類中心是隨機的，一旦初始聚類中心選擇不合理，并以此迭代地改變中心直至達到聚類準則收斂時，易導致算法失去原有的特點，無法得出最優的結果。為了避免選取初始聚類的隨機性帶來的不穩定聚類結果，本文采用一種基于最小生成樹的K-means聚類算法，將用戶屬性相似度作為兩兩用戶頂點邊的權值，通過使用Prim最小生成樹算法得到最小生成樹，并通過最小生成樹找到合理的初始聚類中心，然后進行K-means算法迭代，最終形成K個有效的用戶聚類。

2.1 用戶屬性相似度

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

計算各個用戶之間的屬性相似度，將其作為由用戶集構成的帶權值的以用戶作為頂點的無向圖中的頂點邊的權值，依據該邊權值構造最小生成樹模型。

2.2 最小生成樹K-means算法

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

圖1 K個連通子圖生成圖

然后初始聚類中心便是這K個連通子圖中所有對象的中心值。最后K-means算法將以上述得到的初始聚類中心開始進行用戶聚類，而不是傳統的隨機選擇初始聚類中心。本文采用的聚類算法具體如下：

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

輸入：用戶屬性矩陣A,目標用戶U,聚類個數K。

輸出：目標用戶U所在的用戶簇。

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

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

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

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

（5）每個用戶都已經屬于其中的一個簇，然后根據每個簇中包含的數據向量集合，重新計算得到新的質心。

（6）如果新計算的質心和原來的質心之間的距離達到設置的閾值，算法終止；否則迭代步驟（4）～（6）。

3 Slope One算法填充稀疏矩陣

Slope One算法最早是由丹尼爾教授于2005年提出的推薦算法，該算法以線性回歸模型作為預測模型，根據項目評分差值和用戶的歷史評分記錄來近似估計該用戶對目標項目的評分[16]。Slope One算法思想簡單，實現相對容易，時間和空間復雜度都較小，一旦面對較為稀疏的用戶-項目評分矩陣，Slope One算法可利用的項目評分較少，會導致評分預測準確率直線下降，推薦效果隨之降低。正因為存在上述問題，本文利用Slope One算法填充2.2節中基于用戶聚類后的K個用戶-項目評分矩陣作為最終填充矩陣。

Slope One算法的本質思想其實是形式簡單的回歸表達式w=y+b，其中w為需要預測的用戶u對項目i的評分，y為用戶u對項目i以外的項目評分，b為項目i相對于項目 j評分的平均偏差，表示為Devi,j，如式（2）所示。其中Si,j(U)為對項目i和項目 j均有評分的用戶集合。

因此，通過公式Devi,j+Ru,j可計算出用戶u對itemi的預測評分，從而得到預測均值計算公式如下：

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

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

表1 項目評分矩陣

4 基于用戶和項目的混合協同過濾推薦與時間復雜度

協同過濾算法是1992年Goldberg等學者提出的，該算法是以目標對象相似的用戶或項目為基礎進行推薦。為了提高推薦算法的精度，本文提出一種線性混合基于用戶和基于項目的協同過濾推薦算法，在每個用戶類下，利用填充后的數據集進行有效的推薦。本文的算法流程可以用圖2來表示。

圖2 本文算法流程

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

通過計算用戶的相似度，進行最近鄰搜索得到目標用戶u的最近鄰居集合N(u)，則用戶u對未評分項目i的預測得分計算公式如式（5）所示：

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

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

為了有效融合用戶和項目協同過濾推薦所得的預測評分，本文引入不確定近鄰因子的線性融合框架[18]，利用一個可調整因子λ將兩者的預測結果融合，產生最終的預測評分。λ的計算公式如式（8）所示，其中m′表示基于用戶的協同過濾算法中產生的最近鄰個數，n'表示基于項目的協同過濾算法中產生的最近鄰個數。

最終融合后的模型如式（9）所示，利用得到的預測評分，生成Top-N個推薦結果。

關于模型的時間復雜度，雖然模型需要分多步驟完成，但對于用戶聚類和對聚類結果進行Slope One填充這兩部分，都可以進行離線并行化計算。并且由于已經離線并行化得到聚類且填充后的K個矩陣，人們在查找目標用戶或項目的鄰居時，只需在目標元素對應的小矩陣中計算簇中元素與目標元素的相似度，這就避免了傳統協同過濾推薦算法中對全量評分矩陣進行相似度計算而使得時間復雜度過大的問題，節省了時間和空間，提高了推薦的實時性。

5 實驗結果及分析

5.1 數據集

實驗數據采用的是美國學者公開的MovieLens數據集，具體實驗數據相關信息如表2所示。其中用戶特征信息，本文選取了其中三個用戶屬性作為用戶特征聚類的依據，并根據專家意見將每個屬性分類表示成數值形式[19]，age（1～5）、gender（0～1）、occupation（1～8）。本文隨機選取實驗評分數據中的80%用作訓練集，20%用作測試集。

表2 實驗數據相關信息

5.2 評價指標

本文主要采用平均絕對偏差（Mean Absolute Error，MAE）、均方誤差（Root Mean Square Error，RMSE）來度量預測評分的偏差。MAE和RMSE是目前使用比較廣泛、業界認可度較高的評估推薦系統質量的評價指標，這也正是本文選取這兩項來測試算法的有效性的原因。MAE和RMSE均為誤差值，誤差值越小說明算法的預測精度越高，具體的計算方式為式（9）和式（10），其中N表示測試集的大小。

5.3 算法結果對比及分析

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

圖3 RMSE對比圖

圖4 MAE對比圖

由圖可知，本文提出的推薦算法比其他五種推薦算法確實在RMSE和MAE上有較大的提高，說明此推薦算法可以提高推薦系統的推薦質量，驗證了算法的有效性。

6 結束語

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