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

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

0 引 言

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

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

1 相關(guān)背景知識

1.1 用戶相似性計算

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

(1)

1.2 項目評分預(yù)測

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

(2)

1.3 基于Weighted Slope One算法降低數(shù)據(jù)稀疏性

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

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

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

(3)

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

(4)

1.4 K-means算法

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

定義1：兩個數(shù)據(jù)對象間的歐氏距離為：

(5)

定義2：同類別中數(shù)據(jù)對象的算術(shù)平均為：

(6)

定義3：聚類準則函數(shù)為：

(7)

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

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

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

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

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

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

2 基于最小方差優(yōu)化K-means初始簇心

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

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

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

(8)

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

(9)

定義6：數(shù)據(jù)集樣本的平均距離為：

(10)

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

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

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

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

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

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

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

輸出：N個推薦項目。

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

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

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

4 實 驗

4.1 數(shù)據(jù)集與評測標準

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

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

(11)

其中，pi表示用戶預(yù)測的評分；qi表示對應(yīng)的實際評分。

4.2 實驗結(jié)果與分析

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

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

圖1 實驗結(jié)果對比

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

5 結(jié)束語

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

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

[2] 伍杰華,朱岸青,蔡雪蓮,等.基于隱樸素貝葉斯模型的社會關(guān)系推薦[J].計算機應(yīng)用研究,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] 游 文,葉水生.電子商務(wù)推薦系統(tǒng)中的協(xié)同過濾推薦[J].計算機技術(shù)與發(fā)展,2006,16(9):70-72.

[5] 曹一鳴.基于協(xié)同過濾的個性化新聞推薦系統(tǒng)的研究與實現(xiàn)[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回歸模型的協(xié)同過濾算法研究與應(yīng)用[J].計算機技術(shù)與發(fā)展,2016,26(12):153-155.

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

[10] 張 鋒,常會友.使用BP神經(jīng)網(wǎng)絡(luò)緩解協(xié)同過濾推薦算法的稀疏性問題[J].計算機研究與發(fā)展,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] 韋素云,肖靜靜,業(yè) 寧.基于聯(lián)合聚類平滑的協(xié)同過濾算法[J].計算機研究與發(fā)展,2013,50(S):163-169.

[13] 鄭 丹,王名揚,陳廣勝.基于Weighted-slope One的用戶聚類推薦算法研究[J].計算機技術(shù)與發(fā)展,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] 汪 中,劉貴全,陳恩紅.一種優(yōu)化初始中心點的K-means算法[J].模式識別與人工智能,2009,22(2):299-304.

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

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