基于Weighted-slope One的用戶聚類推薦算法研究

鄭 丹，王名揚，陳廣勝

(東北林業大學 信息與計算機工程學院，黑龍江 哈爾濱 150040)

基于Weighted-slope One的用戶聚類推薦算法研究

鄭 丹，王名揚，陳廣勝

(東北林業大學 信息與計算機工程學院，黑龍江 哈爾濱 150040)

針對傳統協同過濾推薦算法存在的數據稀疏性以及實時性差的問題，提出一種基于Weighted-slope One的用戶聚類推薦算法。該算法首先利用Weighted-slope One算法的思想對初始的用戶-評分矩陣進行有效填充，降低數據的稀疏性；然后，結合初始聚類中心優化改進的K-means方法對用戶進行聚類，生成相似用戶集合，以縮小目標用戶搜索最近鄰的范圍；最后，結合目標用戶所屬的聚類，利用基于用戶的協同過濾算法搜索最近鄰居，為目標用戶推薦對應的產品。仿真實驗結果表明，改進算法可以顯著降低數據的稀疏度，同時提升推薦的準確性和實時性。

協同過濾；高維稀疏矩陣；Weighted-slopeOne；K-means；聚類中心

1 概 述

隨著信息網絡的不斷發展，令人眼花繚亂的商品、繁雜且真假難辨的信息都在急劇增長。對于用戶來說，想要在這些信息中快速發現、收集和維護自己所需的信息記錄需要花費大量的時間和精力，這就是“信息超載”現象。在電子商務領域，通過合理地整合信息對用戶實現個性化推薦是解決信息超載問題的一種有效方案。個性化推薦作為一種依靠用戶購買記錄、用戶偏好等為基礎來實現推薦目標產品推薦的算法，在電子商務領域有著廣泛的應用。在目前的電子商務推薦系統中，協同過濾是使用最廣泛、最成功的推薦算法。它通過構建用戶-項目的評分矩陣，搜索與目標用戶具有相似偏好的鄰居用戶，根據鄰居用戶對某項目的評分值來預測目標用戶對項目的評分值，從而產生推薦結果[1]。

盡管協同過濾算法在商品的個性化推薦當中取得了巨大的成功，但是，近年來隨著電子商務平臺上用戶以及產品數量的不斷增長，數據稀疏性成為限制傳統協同過濾算法應用的瓶頸，并由此帶來了推薦精度低、實時性差和冷啟動等問題[2]。由于用戶評分的項目相對于所有項目來說只占到很小的一部分，所以當用戶的評分項目之間沒有交集的時候，很難判斷兩個用戶之間是否具有相似偏好，從而導致推薦精度的下降。同時，用戶、產品數量的激增是用戶-項目評分矩陣過大，使搜索目標用戶的最近鄰居范圍變大，推薦實時性受到嚴重影響。冷啟動問題是針對“小白”用戶來說的。“小白”用戶指的是剛進入電子商務平臺的用戶，沒有任何的評價和購買記錄，無法去度量他與其他用戶的相似度。冷啟動問題實際上是數據稀疏性的一個極端表現[3]。究其本質，形成這兩個問題的主要原因還是數據稀疏性問題，因此，有必要對數據稀疏性進行深入研究。

近年來，針對數據稀疏性帶來的問題，為了提升推薦效果，學者們將主成分分析、聚類分析、奇異值分解等算法引入到傳統的協同過濾推薦算法中，通過降維，縮小目標用戶搜索最近鄰居的范圍，使得推薦的精度和實時性有了明顯提升。文獻[4]提出使用主成分分析對維數進行約減，然后使用傳統的K-means聚類技術對用戶進行聚類，生成用戶簇類，以縮小目標用戶搜索最近鄰居的范圍，有效緩解了數據稀疏性，提升了推薦質量。文獻[5]提出使用奇異值分解算法對用戶-項目的評分矩陣進行處理，然后使用協同過濾算法對目標用戶產生推薦，有效緩解了數據稀疏性的問題，同時推薦精度也得到了提升。文獻[6]提出了一種基于項目聚類的協同過濾算法，通過對各項目進行聚類，在與目標項目最相似的若干個類中搜索最近鄰居產生推薦列表。但是，直接使用主成分分析、SVD奇異值分解、聚類分析等來對原始的用戶-評分矩陣進行處理的能力是有限的。因為，當用戶-評分矩陣數據的稀疏程度很大時，這些方法在第一步進行處理時的效果就不太理想。

基于以上啟發，文中提出一種基于Weighted-slopeOne的用戶聚類推薦算法。首先借鑒Weighted-slopeOne算法的思想對初始的用戶-項目評分矩陣進行填充，使初始的用戶-評分矩陣的稀疏性大大降低。其次，對于已經填充的用戶-評分矩陣使用一種初始聚類中心優化改進的K-means算法對用戶進行聚類，生成相似用戶集合。最后，使用協同過濾算法實現對目標用戶的推薦。具體推薦過程為：首先判斷目標用戶所屬的簇類，在目標用戶所屬的相似用戶集合內實現推薦。實驗仿真結果表明，文中所提出的方法不但有效降低了數據的稀疏性，同時由于是在目標用戶所屬簇類內為其實現系統過濾推薦，因此可以有效地降低協同過濾搜索目標用戶最近鄰居的范圍；并且由于都是目標用戶的相似用戶，因此文中提出的算法在降低計算復雜度的同時，還能有效提升推薦系統的實時響應速度。

2 基于Weighted-slope One算法降低用戶-評分矩陣的稀疏性

Slope One算法是于2005年由Daniel Lemire教授提出的一個基于項目的推薦算法[7]。算法以f(x)=x+b作為預測器，使用線性回歸預測用戶對未評分項目的打分，參數b為用戶對兩個項目評分的平均偏差[8]。Weighted-slopeOne是SlopeOne的一個遞進算法，它均衡了每個評分項目對于目標項目的影響。由于Weighted-slopeOne在預測用戶對項目的打分值時充分考慮了用戶共同評分的差異度以及不同項目被用戶同時評論的次數，因此，所得預測的評分與真實的用戶評分是比較相近的。但是，文獻[9]研究表明SlopeOne在用戶-項目評分矩陣比較密集的時候推薦的效果較好，當數據比較稀疏時，其推薦的效果并不好。鑒于此，文中并不直接使用Weighted-slopeOne算法進行推薦，而是借鑒Weighted-slopeOne算法的這種對目標用戶打分思想來對初始高維的用戶-評分矩陣進行填充，對填充后的矩陣使用初始聚類中心優化的K-means算法進行聚類，生成相似用戶集合。當對目標用戶進行推薦時，首先確定目標用戶所屬的簇類，然后在該簇類內搜索目標用戶的最近鄰居，產生推薦。

使用Weighted-slopeOne對用戶u的未評分項目進行填充降低用戶-評分矩陣的稀疏性的過程為：首先，尋找用戶u和用戶v評分過的項目集合Iuv=Iu∩Iv，利用式(1)計算用戶u的未評分項目j對于項目i的偏移量devji，根據式(2)得到目標用戶對于項目j的評分值。

這是經典的SlopeOne算法計算目標用戶對項目評分的方法，但是對項目進行評分的用戶數量在最終的預測評分時顯然也有影響。因此，使用Weighted-slopeOne算法修正最終目標用戶u對于項目的預測評分，即根據式(3)得出目標用戶對項目j的最終評分。

(1)

(2)

(3)

其中：ui，uj分別表示用戶u對項目i和項目j的評分值；card(i∩j)表示項目i和項目j同時被評分過的用戶數目；R(u)表示目標用戶u已經評價過的項目的集合；D(j)表示與目標項目j計算得到的平均偏移量devji的集合。

通過使用Weighted-slopeOne算法對初始的用戶-評分矩陣進行處理，矩陣中的大部分零元素就會被填充，從而有效降低了整個矩陣的稀疏程度。

3 初始聚類中心優化的K-means算法

K-means算法是一種基于劃分的聚類分析方法，由于其理理論可靠、算法實現簡單、收斂速度快，并且又容易實現對大規模數據的處理，因此是應用最廣泛的聚類算法之一。但是由于傳統的聚類算法對聚類中心敏感，隨機地選取任意k個點作為初始聚類中心，并迭代地改變中心使聚類準則收斂，經常會導致算法陷入局部最優，產生完全不同的聚類結果。為了避免這種初始聚類中心隨機選取帶來的聚類結果不穩定性，學者們將數據分布的稠密程度作為指標引入到初始聚類中心的選取上，希望所選取的初始聚類中心能夠在一定程度上代表數據本身的分布情況。

文獻[10]通過劃分高、低密度區域選擇高密度區域中具有代表性的數據對象作為初始的聚類中心。文獻[11]通過建立數據對象分布的密度集合，計算最近兩點的垂直中點方法來確定初始聚類中心，迭代形成最終簇類。通過考察密度特性，這些算法都有效地改善了K-means的穩定性。但算法中還存在著參數選擇較為主觀的現象，比如對于密度參數θ選得過大，可導致本不屬于同一類的樣本點被劃分到同一類的情況；如果過小，會導致相反的情形，導致噪聲數據也被列入候選聚類中心的情況，由此導致聚類性能的下降。

基于此，文中提出一種基于距離-期望密度參數的聚類中心選擇方法。該方法結合每個聚類簇大致期望的樣本平均個數來確定密度θ的大小。同時，在滿足期望密度的前提下，計算每個密度區域的半徑，作為期望密度參數，結合數據樣本間的距離，尋找初始的聚類中心。由于對用戶聚類依靠的是用戶對產品的評分相似性，與密度類似，偏好同一類產品的用戶一般會具有相同的喜好，所以將改進的K-means聚類算法直接應用于用戶聚類產生相似用戶是十分有意義的。

(1)相關定義。

定義1：密度參數。

取空間中的任一數據樣本xi，以其為中心，尋找距離xi最近的θ個數據樣本，把xi與個樣本之間的最大距離稱之為樣本xi的密度參數，用ε表示。

定義2：期望密度。

Eθ=a*n/k

(4)

其中：n為數據集的樣本總數；k為設定的聚類個數；a為期望密度比例系數。

a可以根據經驗選取，文中取a=0.6。即，如果某個數據樣本被選作聚類中心，則離該對象最近的θ個樣本應該占到以該對象為中心所形成的聚類簇覆蓋樣本的60%。

定義3：平均相異度。

數據樣本之間的平均相異度定義為：

(5)

其中：xi、xj為數據集中兩個數據樣本；t為數據對象xj的個數；d(xi,xj)為數據樣本xi與xj間的距離，文中用歐幾里得距離公式進行計算：

(6)

(2)改進算法的思想。

聚類中心優化的K-means算法中，選取具有較低期望密度參數且彼此相距最遠的k個對象作為初始的聚類中心，這些中心點能夠很好地反映數據對象的空間分布特性，同時能保證選出的聚類中心所覆蓋的區域樣本密度較高。這些都使得算法具有較高的穩定性，同時使得算法能夠獲得全局最優的聚類效果。

4 基于用戶的協同過濾推薦

協同過濾算法是于1992年由Goldberg等學者提出的，該算法是以項目屬性或者用戶評分相似性作為個性化推薦的基礎。協同過濾算法可以分為基于用戶的協同過濾和基于項目的協同過濾[12]。基于用戶的協同過濾算法實現推薦時基于如下事實：如果用戶對一些項目的評分比較相似，就認為他們在其他項目的評分上具有相似關系[13]。

算法的執行流程為：首先，計算目標用戶與推薦系統中所有用戶的相似性，找到與目標用戶最相似的鄰居用戶集合；其次，根據最近鄰居集合中用戶對項目的評分去預測目標用戶對未評分項目的打分；最后，根據預測的打分情況為目標用戶推薦打分值最高的topM個項目[14-15]。

算法執行過程中先明確的幾個計算單元如下：

(1)用戶相似度計算。

用戶之間的相似度是通過用戶對項目的歷史評分來進行度量的[16]。文中使用余弦相似性來產生用戶最近鄰居，其公式如下：

(7)

(2)項目評分預測

在預測項目評分時，經常選取前N個與目標用戶相似性最大的用戶作為目標用戶的最近鄰居，根據這些鄰居用戶對目標用戶未評分項目的評分情況來預測產生目標用戶對其的評分值。假設Nu表示鄰居用戶的集合，根據式(8)可以計算目標用戶對于某項目的預測評分。

(8)

針對預測評分的值給出目標用戶的推薦列表。

5 基于Weighted-slope One的用戶聚類推薦算法

設用戶集合為U={u1,u2,…,um}，使用改進的K-means算法生成的用戶集合表示為U'={C1,C2,…,Ck}。其中，k表示生成簇類的個數，Ck表示第k個簇類。基于Weighted-slopeOne的用戶聚類推薦算法的具體執行步驟如下：

輸入：用戶-評分矩陣D，聚類個數k，最近鄰居及大小N，推薦列表的個數M；

輸出：目標用戶的推薦列表以及對應的評分。

Step1：根據Weighted-slopeOne算法利用式(3)對初始的用戶-評分矩陣D中的0元素進行填充，生成填充矩陣Dζ；

Step2：利用改進的K-means算法基本思想對Dζ進行處理，生成k個聚類輸出，各聚類的中心為ci,i=1,2,…,k；

Step3：通過式(6)計算目標用戶與聚類中心ci的距離，將目標用戶分配到距離最小的聚類Ci(i=1,2,…,k)中；

Step4：在目標用戶所屬的簇類中，根據式(7)計算目標用戶與其他用戶的相似性，搜索出相似性最大的前N個用戶作為目標用戶的最近鄰居集合，記為Nu；

Step5：利用式(8)計算各個項目的預測評分，列出topM個預測得分最大的項目推薦給目標用戶。

6 仿真實驗與結果分析

6.1 數據集

仿真實驗中，選取了MovieLens站點的電影數據集作為實驗數據。數據集中包含了943個用戶1 682部電影共10 000條評價得分，其中每個用戶至少對20部電影進行了評分，評分值為1～5之間的整數。評分值越大說明用戶對該項目的偏好性越強，0值表示用戶未對該電影進行評分。

6.2 評測指標

在推薦算法中經常使用平均絕對誤差(MAE)來衡量推薦結果的好壞。MAE是通過計算預測的用戶評分與實際的用戶評分之間的偏差來度量預測的準確性[12]。假設目標用戶對項目的實際評分為{pi|i=1,2,…,n},其中n表示項目的總個數，使用推薦算法預測得到的目標用戶對項目的評分為 {qi|i=1,2,…,n},那么MAE的計算公式為：

(9)

從式(9)可以看出，MAE值越小說明推薦結果的準確性越高。

6.3 仿真結果分析

為保證所選取的相似用戶集合最為合理，首先針對用戶簇類個數進行系統過濾算法的實現，計算其對應的MAE值，以選擇最合理的用戶簇類個數來對目標用戶產生最終的推薦結果。

圖1就是在不同的聚類個數下MAE的變化情況。

圖1 不同聚類數目下的MAE值

由圖1可以看出，隨著聚類個數的增加，MAE的值先降后升，這說明在用戶數固定的情況下，需要找到一個最優的聚類數目能夠使推薦的MAE值達到最小。從圖1中觀察可知，當聚類個數為11時，MAE的值最低，顯然對于文中所選取的數據集而言，令k=11是最合理的聚類個數。

在確定了最優的聚類個數后，將文中所提出的基于Weighted-slopeOne算法與傳統的協同過濾算法、基于K-means用戶聚類的協同過濾算法進行了比較。最近鄰居的個數從5增至50，間隔為5。實驗對比結果如圖2所示。

圖2 推薦結果的MAE值比較

根據圖2，隨著目標用戶最近鄰居個數的不斷增加，三種算法的MAE值呈明顯的下降趨勢。這說明隨著最近鄰居個數的不斷增加，可以有效提升推薦結果的準確率。但從MAE下降的速率來看，當最近鄰居的個數上升到某個個數之后，MAE下降的速率越來越慢，最后趨近于平滑。這說明最近鄰居的個數并不是越多越好，而是隨著最近鄰居數目的增多，其為MAE減小所做的貢獻越來越小。在實際應用中，當考慮推薦系統實時性、存儲、計算的復雜度時，合理選擇最近鄰居的個數對于推薦精度和維護成本都至關重要。

除此之外，在不同的最近鄰居數目下對比三種算法可得，文中提出的算法較其他算法均有最小的MAE值，傳統的協同過濾算法的推薦效果最不理想，添加了用戶聚類的推薦效果次之。但是由于數據稀疏性和初始聚類中心隨機選取可能帶來的不穩定聚類結果，基于K-means的協同過濾推薦的精度也不高。而文中提出的算法無論是對數據稀疏性還是聚類結果都進行了對應的處理，可以確保在數據稀疏性降低的同時有穩定的聚類結果。顯然，通過文中填充高維稀疏矩陣，實現用戶聚類，為目標用戶在聚類內給出推薦結果的方法不但有效降低了數據的稀疏性，同時在聚類內搜索目標用戶的最近鄰居縮小了搜索范圍，加快了推薦算法的響應速度，推薦MAE值得到了提升。

7 結束語

文中分析陳述了協同過濾推薦算法所存在的問題以及學者為提升推薦準確率所做的研究工作。在此基礎上提出了一種基于Weighted-slopeOne的用戶聚類推薦算法。通過借鑒Weighted-slopeOne進行評分預測的思想對初始的用戶-項目矩陣中的0元素進行填充，降低數據稀疏性，使用改進的K-means聚類算法對用戶進行聚類，在簇類內查找目標用戶的最近鄰居最終給出預測評分以及推薦結果。仿真實驗證明，文中提出的算法可以有效地提升推薦的準確性，同時由于其縮小了搜索最近鄰居的空間，推薦算法的實時性也得到了提升。

[1] 王桂芬.電子商務個性化推薦系統中協同過濾算法的研究與應用[D].南昌:南昌大學,2012.

[2] 李 華,張 宇,孫俊華.基于用戶模糊聚類的協同過濾推薦研究[J].計算機科學,2012,39(12):83-86.

[3] 孫小華.協同過濾系統的稀疏性與冷啟動問題的研究[D].杭州:浙江大學,2005.

[4] 郁 雪,李敏強.一種結合有效降維和K-means聚類的協同過濾推薦模型[J].計算機應用研究,2009,26(10):3718-3720.

[5]VozalisMG,MargaritisKG.ApplyingSVDonitem-basedfiltering[C]//Procof5thinternationalconferenceonintelligentsystemsdesignandapplications.[s.l.]:IEEE,2005:464-469.

[6] 鄧愛林,左子葉,朱揚勇.基于項目聚類的協同過濾推薦算法[J].小型微型計算機系統,2004,25(9):1665-1670.

[7] 李朝陽.基于SlopeOne算法的協作過濾個性化推薦系統設計與實現[D].武漢:華中科技大學,2010.

[8] 王 毅.基于Hadoop的SlopeOne及其改進算法實現[D].成都:西南交通大學,2011.

[9] 董 麗,邢春曉,王克宏.基于不同數據集的協作過濾算法評測[J].清華大學學報：自然科學版,2009,49(4):590-594.

[10] 袁 方,周志勇,宋 鑫.初始聚類中心優化的k-means算法[J].計算機工程,2007,33(3):65-66.

[11] 周煒奔,石躍祥.基于密度的K-means聚類中心選取的優化算法[J].計算機應用研究,2012,29(5):1726-1728.

[12] 馬宏偉,張光衛,李 鵬.協同過濾推薦算法綜述[J].小型微型計算機系統,2009,30(7):1282-1288.

[13] 李 濤,王建東,葉飛躍,等.一種基于用戶聚類的協同過濾推薦算法[J].系統工程與電子技術,2007,29(7):1178-1182.

[14] 李曉艷,張子剛,張逸石.集成k-means聚類和有監督特征選擇的混合式協同過濾推薦[J].管理學報,2013,10(9):1362-1367.

[15] 張海燕,丁 峰,姜麗紅.基于模糊聚類的協同過濾推薦方法[J].計算機仿真,2005,22(8):144-147.

[16] 賀銀慧,陳端兵,陳 勇,等.一種結合共同鄰居和用戶評分信息的相似度算法[J].計算機科學,2010,37(9):184-186.

Research on User Clustering Recommendation Algorithm Based on Weighted-slope One

ZHENG Dan,WANG Ming-yang,CHEN Guang-sheng

(College of Information and Computer Engineering,Northeast Forestry University,Harbin 150040,China)

Aiming at the problems of data sparseness and the poor real-time performance of traditional collaborative filtering recommendation algorithm,a new user clustering recommendation algorithm based on Weighted-slope One algorithm is proposed.Firstly,the zero items in user-item matrix are filled by Weighted-slope One algorithm.This operation can effectively reduce the data sparseness.Secondly,the users are clustered by the optimizedK-meansalgorithm.Thisoperationcaneffectivelyfindthenearestneighborofthetargetuser.Finally,thecorrespondingproductsarerecommendedtothetargetusersaccordingtotheirnearestneighborswhicharefoundbytheusers’collaborativefilteringrecommendationalgorithm.Experimentalresultsshowthattheimprovedalgorithmcansignificantlyreducethedatasparseness,andimprovetherealtimeperformanceandtheaccuracyofrecommendation.

collaborative filtering;high-dimensional sparse matrix;Weighted-slope One；K-means;clusteringcenter

2015-07-14

2015-10-20

時間：2016-03-22

中央高校基本科研業務費專項資金項目(2572014DB05)；中國博士后科學基金面上基金(2012M520711)；國家自然科學基金資助項目(71473034)

鄭 丹(1991-)，女，碩士，研究方向為數據挖掘；王名揚，博士，副教授，研究方向為數據挖掘、社交網絡挖掘；陳廣勝，教授，研究方向為生物質材料材質預測、新型復合材料智能化檢測、技術創新方法推廣應用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1521.068.html

TP

A

1673-629X(2016)04-0051-05

10.3969/j.issn.1673-629X.2016.04.011