基于最小方差的K-means用戶聚類推薦算法

楊大鑫，王榮波，黃孝喜，諶志群

(杭州電子科技大學 計算機學院，浙江 杭州 310018)

0 引 言

隨著互聯網和電子商務的飛速發展，在大量的商品信息面前，用戶或消費者往往很難發現最需要或最合適的商品。在信息爆炸的時代，如何解決信息超載的問題，受到了越來越多的關注，并提出了多種推薦算法，主要包括基于規則的推薦算法[1]、基于模型的推薦算法[2]和協同過濾推薦算法[3]等。雖然協同過濾推薦算法在現實中有很多的應用[4-8]，但是它在處理大數據時會存在稀疏性和擴展性等問題，導致推薦效果不理想。對研究人員有很大的挑戰。其中，文獻[9]提出了一種通過矩陣聚類的協作過濾算法，利用矩陣聚類算法對用戶評分數據進行聚類，然后對聚類后的子矩陣進行協作過濾，提高了算法的推薦精度。文獻[10]利用BP神經網絡來預測用戶對項目的評分，減小了數據集的稀疏性，提高了推薦系統的推薦質量。但是訓練BP神經網絡模型需要額外的時間花銷。文獻[11]利用奇異值對高維數據矩陣進行降維，使得評分矩陣變得密集，以此來減小數據矩陣的稀疏性。但是奇異值分解之后會導致數據丟失，在高維數據矩陣中，降維效果不是很理想。文獻[12]對用戶和項目兩個維度進行聯合聚類，通過對聚類信息的平滑處理和對用戶未評分項目的預測，在數據稀疏的問題上進行改進，從而提高了推薦的質量。

針對傳統的協同過濾推薦算法在處理大數據時存在的稀疏性、擴展性等問題，文中提出了一種基于最小方差的K-means用戶聚類推薦算法。首先利用Weighted Slope One算法對數據矩陣中的未評分項進行預測，減小其稀疏性；然后通過基于最小方差的K-means算法對填充后的評分數據進行聚類，減少用戶最近鄰搜索空間，提高算法的擴展性；最后在目標用戶所在的類中利用傳統的基于用戶的協同過濾進行推薦，生成最終的推薦結果。并通過與其他算法的對比驗證該算法。

1 相關背景知識

1.1 用戶相似性計算

基于用戶的協同過濾推薦算法通過用戶對項目的歷史評分來度量用戶之間的相似度。其中，計算用戶相似度的方法有如下幾種：皮爾遜(Pearson)相關系數法、余弦向量法和修正的余弦向量法等。文中采用余弦向量法來產生用戶最近鄰居，公式如下：

(1)

1.2 項目評分預測

利用式(1)的相似性計算可以得到目標用戶u的最近鄰居。設目標用戶u的最近鄰居的集合為Nu，則可以從目標用戶u對最近鄰居集合項目的評分中得到其對項目i的預測評分，公式如下：

(2)

1.3 基于Weighted Slope One算法降低數據稀疏性

初始數據矩陣中的0元素經過Weighted Slope One算法處理后可以降低其稀疏性。因為在推薦系統的應用過程中，用戶對項目的評分數通常會大于2，所以為了平衡各個評分項目對于目標項目的影響，需要用到Weighted Slope One算法[13]，它是Slope One算法[14]的一個遞進算法。

首先，定義一個數據矩陣R，Ru,i為用戶u對項目Itemi的評分；Iu為用戶u所有評分的項目；Ui為對項目Itemi進行評分的用戶集合；Uij=Ui∩Uj為對Itemi和Itemj兩個項目都評過分的用戶集合；Numij為集合中元素的數目。

項目Itemi和Itemj之間評分的偏差可以由式(3)得到：

(3)

最后，得到目標用戶user對項目Itemi的預測評分：

(4)

1.4 K-means算法

設待聚類的數據集為X={xi|xi∈RP,i=1,2,…,n}。K個聚類中心分別為M1，M2，…，Mk，于是用wj(j=1,2,…,k)表示聚類的k個類別。

定義1：兩個數據對象間的歐氏距離為：

(5)

定義2：同類別中數據對象的算術平均為：

(6)

定義3：聚類準則函數為：

(7)

在傳統K-means算法中，初始簇心的選擇是隨機的，通過相似度計算，把數據集中的數據樣本與最近的初始中心歸為一類，不斷重復這一過程，直到各個初始中心在某個精度范圍內不變。具體算法步驟如下：

(1)在包含N個樣本的X中隨機選擇k個樣本數據作為初始簇心Mi(i=1,2,…,k)；

(2)利用式(5)，計算X中各個樣本數據p到Mi的距離d(p,Mi)；

(3)找到每個樣本數據p的最小的d(p,Mi)，把p加入到與Mi相同的簇中；

(4)完成所有樣本的遍歷之后，通過式(6)重新計算Mi的值，作為新的簇心；

(5)重復步驟2～4，直到目標準則函數E取值不再變化。

2 基于最小方差優化K-means初始簇心

在眾多聚類算法中，K-means算法十分典型，雖然實現起來簡單方便，但也有一些弊端。首先，K值是根據人的經驗隨機確定的，具有一定的盲目性，如果不了解要聚類的數據，那么給出合理的K值就會非常困難；其次，對初始簇心的選擇也是隨機的，不同的簇心會導致不同的聚類效果，如果選擇了孤立點，則聚類結果會有很大的差異。

針對K-means算法存在的缺陷，許多研究者對其進行了優化[15-17]。文中則對初始聚類中心基于最小方差進行優化[18]，在不同范圍內選擇K個方差最小的樣本作為初始簇心。根據方差的定義，一個樣本的方差越小，它附近的數據分布就會越密集，使得簇心的選取就會越客觀，聚類結果越準確。具體選取步驟如下：

定義4：樣本xi到所有樣本距離的平均值為：

(8)

定義5：樣本xi的方差為：

(9)

定義6：數據集樣本的平均距離為：

(10)

(2)利用式(10)計算出X中各個樣本之間距離的平均值cmean；

(3)在以cmean為半徑的圓之外尋找另一個方差最小的樣本，把它作為第二個簇心，添加到集合C中；

(4)重復上一步，在剩余的樣本中不斷尋找，找到K個簇心之后，算法結束。

通過上述步驟選取到的中心點緊密度極高，可以較好地反映樣本的分布情況，具有一定的客觀性，聚類結果更加穩定、可靠。

3 基于最小方差的K-means用戶聚類推薦算法

該算法中每條數據主要由用戶、項目、評分3部分組成。設目標用戶為u，用戶集合為U={u1,u2,…,um}，基于最小方差優化后的K-means算法生成的用戶集合表示為U={C1,C2,…,Ck}。其中，k為生成的簇類個數，Ck表示第k個簇類。基于最小方差的K-means用戶聚類推薦算法的描述步驟如下：

輸入：用戶-項目數據矩陣Rm×n，聚類個數k；

輸出：N個推薦項目。

Step3：利用式(5)計算u與k個簇心之間的相似度，然后把u加入到與其最相似的類中；

Step4：利用式(1)計算u與同類中其他用戶的相似性，得到其最近鄰居集Nuj(j=1,2,…,m)；

Step5：得到最近鄰居集之后，可以根據它們對項目的評分，利用式(2)求得u對待推薦項目的預測分，從高到低排序之后，把前N個項目推薦給u。

4 實 驗

4.1 數據集與評測標準

采用MovieLens數據集對算法的性能進行測試。數據集中包括943個用戶對1 682部電影的10萬多條評分，評分為1～5之間的整數。評分值越大說明用戶對這部電影越喜歡，0表示用戶沒有對該電影進行評分。根據實驗需要，將其中的80%作為訓練集，其余20%作為測試集。

平均絕對偏差(Mean Absolute Error，MAE)是一種常用的推薦質量度量方法，通過計算預測評分與實際真實評分之間的偏差來度量預測的準確性。MAE越小，推薦精度越高。MAE的計算公式如下：

(11)

其中，pi表示用戶預測的評分；qi表示對應的實際評分。

4.2 實驗結果與分析

實驗首先對初始數據中的0元素進行有效消除，然后采用基于最小方差的K-means算法對處理后的數據進行聚類，最后在目標用戶所在類中用傳統的協同過濾算法輸出最終的推薦結果。通過實驗對傳統的協同過濾算法、簡單K-means用戶聚類推薦算法和文中算法進行了對比。設定用戶聚類數為14，最近鄰居的個數從5增加到50，間隔為5。實驗結果如圖1所示。

由圖1可知，三種算法的MAE值都會隨著目標用戶最近鄰個數的增加而降低，說明推薦的準確率可以隨著目標用戶的最近鄰居數的增加而得到有效提高。而文中算法在不同鄰居個數下的MAE值都是最低的，由此可見，與傳統協同推薦算法和簡單用戶聚類推薦算法相比，文中算法具有更好的推薦效果。

圖1 實驗結果對比

在進行傳統的推薦之前，文中算法由于對初始數據進行了填充，并且對用戶數據基于最小方差進行了聚類，使得用戶最近鄰搜索空間更具客觀性，選取到的最近鄰居更加準確。實驗結果表明，相比于傳統的協同過濾推薦算法，文中算法的準確度更高。

5 結束語

從數據稀疏性和算法擴展性兩方面進行改進，文中提出了一種基于最小方差的K-means用戶聚類推薦算法。一方面，利用Weighted Slope One算法對初始數據矩陣進行填充，降低其稀疏性；另一方面，采用基于最小方差的K-means算法對填充后的數據進行聚類，提高算法的擴展性。實驗結果表明，文中算法在一定程度上改善了數據稀疏性和算法擴展性，提高了算法的推薦質量。

[1] 陳華月,余 剛,朱征宇.基于加權關聯規則的用戶關注項目推薦算法[J].計算機工程,2006,32(6):86-88.

[2] 伍杰華,朱岸青,蔡雪蓮,等.基于隱樸素貝葉斯模型的社會關系推薦[J].計算機應用研究,2014,31(5):1381-1384.

[3] SCHAFER J B,DAN F,JON H,et al.Collaborative filtering recommender systems[C]//The adaptive web:methods and strategies of web personalization,lecture notes in computer science.Berlin:Springer-Verlag,2007:291-324.

[4] 游 文,葉水生.電子商務推薦系統中的協同過濾推薦[J].計算機技術與發展,2006,16(9):70-72.

[5] 曹一鳴.基于協同過濾的個性化新聞推薦系統的研究與實現[D].北京:北京郵電大學,2013.

[6] KONSTAN J,MILLER B,MALTZ D,et al.GroupLens:applying collaborative filtering to usenet news[J].Communications of the ACM,1997,40(3):77-87.

[7] PARK S T,PENNOCK D M.Applying collaborative filtering techniques to movie search for better ranking and browsing[C]//Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining.New York:ACM,2007:550-559.

[8] 孟 佩,曹 菡,師 軍.基于Softmax回歸模型的協同過濾算法研究與應用[J].計算機技術與發展,2016,26(12):153-155.

[9] 高鳳榮,邢春曉,杜小勇,等.基于矩陣聚類的協作過濾算法[J].華中科技大學學報:自然科學版,2005,33:257-260.

[10] 張 鋒,常會友.使用BP神經網絡緩解協同過濾推薦算法的稀疏性問題[J].計算機研究與發展,2006,43(4):667-672.

[11] VOZALIS M G,MARGARITIS K G.Applying SVD on item-based filtering[C]//Proceedings of 5th international conference on intelligent systems design and applications.[s.l.]:IEEE,2005:464-469.

[12] 韋素云,肖靜靜,業 寧.基于聯合聚類平滑的協同過濾算法[J].計算機研究與發展,2013,50(S):163-169.

[13] 鄭 丹,王名揚,陳廣勝.基于Weighted-slope One的用戶聚類推薦算法研究[J].計算機技術與發展,2016,26(4):51-55.

[14] LEMIRE D,MACLACHLAN A.Slope one predictors for online rating-based collaborative filtering[C]//SIAM data mining.California:SIAM,2005:21-23.

[15] ERISOGLU M,CALIS N,SAKALLIOGLU S.A new algorithm for initial cluster centers in k-means algorithm[J].Pattern Recognition Letters,2011,32(14):1701-1705.

[16] 汪 中,劉貴全,陳恩紅.一種優化初始中心點的K-means算法[J].模式識別與人工智能,2009,22(2):299-304.

[17] 楊善林,李永森,胡笑旋,等.K-means算法中的k值優化問題研究[J].系統工程理論與實踐,2006,26(2):97-101.

[18] 謝娟英,王艷娥.最小方差優化初始聚類中心的K-means算法[J].計算機工程,2014,40(8):205-211.