劉 明 術(shù)
(黃山職業(yè)技術(shù)學(xué)院,安徽 黃山 245000)
?
基于K-均值聚類的混合聚類算法
劉 明 術(shù)
(黃山職業(yè)技術(shù)學(xué)院,安徽 黃山 245000)
摘要:K-均值聚類算法是聚類算法中比較典型的算法之一,在其各類改進(jìn)算法中都受到了離群點(diǎn)、初質(zhì)心、類個(gè)數(shù)等因素的干擾。本文利用相似密度提出一種新的聚類初始質(zhì)心選取和離群點(diǎn)判別方法,對K-均值聚類算法進(jìn)行了改進(jìn)。通過實(shí)驗(yàn)證明改進(jìn)算法提高了聚類的有效性和穩(wěn)定性。
關(guān)鍵詞:K-均值聚類;聚類算法;相似密度;離群點(diǎn)
聚類算法大致可分為劃分法、密度法、層次法、網(wǎng)格和模型法等幾種常見的算法[1],在模式識別和數(shù)據(jù)挖掘等領(lǐng)域應(yīng)用廣泛。其中傳統(tǒng)K-均值算法是一種最為廣泛使用的聚類算法,其不足之處是需先確定類的數(shù)目和初始質(zhì)點(diǎn)位置。由于類的最佳個(gè)數(shù)和初始質(zhì)心的位置事先不易確定,且兩者的選擇具有任意性,一旦選擇失誤,可能無法達(dá)到滿意的聚類效果。為了彌補(bǔ)均值算法的缺點(diǎn),學(xué)者們從不同角度對算法做了大量的改進(jìn)[1-5]。本文借鑒文獻(xiàn)[2]所提方法和思路,利用對象間相似度,去除離群點(diǎn),對初質(zhì)心的選擇進(jìn)行一些改進(jìn),并用函數(shù)FSSE[3]測試改進(jìn)算法的聚類效果。
1傳統(tǒng)K-均值算法
K-均值算法[4]需事先確定類的初始中心位置, 并對對象進(jìn)行粗糙的分類, 然后計(jì)算各類數(shù)據(jù)的均值,慢慢調(diào)整類的中心。反復(fù)迭代,當(dāng)類內(nèi)相似性最大、類間相似性達(dá)到最小停止[5],具體程序[6]如下:
輸入:N個(gè)n維數(shù)據(jù){x1,x2,…,xN},其中xi={xi1,…,xin},i=1,…,N;
(1) 在數(shù)據(jù)集中任意找k個(gè)對象作為初質(zhì)心{d1,d2,…,di,…,dk},di={di1,…,din};
(2)計(jì)算每個(gè)對象到各類的距離,把對象放在最近的類中。采用歐式距離d(x,U)=min[d(x,y),y∈U]進(jìn)行度量,其中x,y為個(gè)體,U為類;
(3)計(jì)算各類中所有數(shù)據(jù)的平均值,再次將數(shù)據(jù)重新劃到相似性最大的類,并求各類的均值;
(4)不斷循環(huán)執(zhí)行第(3)步,直到類的均值固定為止。
輸出:當(dāng)各對象與簇距離平方和最小時(shí),輸出k。
傳統(tǒng)K-均值算法不足之處[7]:
(1)一開始直接人為選取初始類質(zhì)心和類的數(shù)目,嚴(yán)重影響了后面的聚類效果;
(2)孤立點(diǎn)干擾嚴(yán)重。
2基本概念
定義1本文相似度測量采用歐幾里德距離進(jìn)行度量,定義如下
其中,xi=(xi1,…,xim),xj=xj1,…,xjm。
定義2設(shè)W,U為樣本集合,二者距離定義為d(W,U)=min[d(X,Y),X∈W,Y∈U]。
定義3(1)y∈ρε(x),ρε(x)以x為球心,ε為超球體半徑;
(2)Nε(x)≥δ,Nε(x)表示在ρε(x)中X點(diǎn)的個(gè)數(shù),δ為設(shè)定參數(shù)。若數(shù)據(jù)對象y在以x為球心,ε為半徑的超球體ρε(x)(數(shù)目達(dá)到δ)內(nèi),則y為ρε(x)的群點(diǎn)。
(3)若d(xi,Am)>max[d(x,y),x,y∈Am],則xi視作離群點(diǎn),其中x,y是Am中的任意兩個(gè)數(shù)據(jù);d(xi,Am)表示xi數(shù)據(jù)到Am的距離;Am是第m個(gè)類中所有數(shù)據(jù)組成的矩陣,矩陣中每一行由一個(gè)數(shù)據(jù)的所有屬性構(gòu)成。
定義4(聚類效果判斷函數(shù)FSSE)常采用歐幾里得距離度量相似性,用距離平方和(SSE)來度量聚類效果[8],即
3改進(jìn)K-均值算法
3.1改進(jìn)初質(zhì)心的篩選法
按群點(diǎn)定義要求把數(shù)據(jù)集C中的n個(gè)數(shù)據(jù)最終分成k個(gè)類,m的開始值設(shè)為1,改進(jìn)開始質(zhì)心的方法如下:
(1)計(jì)算類C中各對象間距離d(xi,yj),
(1≤i≠j≤n),把距離最小的兩對象安排到同類Am(1 (2)在C中尋找距類Am最近的對象,根據(jù)群點(diǎn)定義規(guī)則,若對象滿足條件就歸入Am,在C中去掉該對象,否則讓它進(jìn)行后面的篩選; (4)求各類總對象的均值,得到k個(gè)初質(zhì)心。 3.2改進(jìn)算法的步驟 假設(shè)數(shù)據(jù)集C={x1,x2,…,xn}由n個(gè)數(shù)據(jù)對象xi=(x1,…,xip)(i=1,2,…,n)構(gòu)成,每個(gè)對象有p個(gè)屬性,其中xij是第i數(shù)據(jù)的第j個(gè)屬性值。數(shù)據(jù)集C={x1,x2,…,xn}的矩陣形式表示為 (i=1,2,…,n;j=1,2,…,p),矩陣中的各行表示某個(gè)數(shù)據(jù)對象屬性的一個(gè)向量,各列表示數(shù)據(jù)的一個(gè)屬性。 Step1按照上述初質(zhì)心篩選方法篩選出數(shù)據(jù)集C的k個(gè)初始質(zhì)心和m個(gè)類 Am(1 Step2計(jì)算每個(gè)對象分別到m個(gè)類Am(1 Step3計(jì)算各類中心,作為類的最新初質(zhì)心; Step4反復(fù)執(zhí)行Step2~ Step3,直到類的質(zhì)心不變?yōu)橹埂?/p> 4實(shí)驗(yàn)分析 驗(yàn)證上述改進(jìn)算法效果,實(shí)驗(yàn)采用 UCI 數(shù)據(jù)中Iris的數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù),進(jìn)行了模擬測試。Iris數(shù)據(jù)集初始質(zhì)心為 (6.588 2.974 5.552 2.026),(5.006 3.418 1.464 6.244),(5.936 2.770 4.260 1.326)。 表1 改進(jìn)前質(zhì)心與真實(shí)質(zhì)心對比 表2 改進(jìn)后質(zhì)心與真實(shí)質(zhì)心對比 表3 改進(jìn)前后聚類算法效果對比 從表1、表2和表3可以看出,改進(jìn)后的K-均值算法,準(zhǔn)確率較高,聚類的效果得到提高。下面是數(shù)據(jù)集Iris在改進(jìn)算法前后聚類效果。 圖1 改進(jìn)前聚類效果 圖2 改進(jìn)后算法聚類效果 從圖1和圖2可以看出,算法改進(jìn)后,較好地去除了一些離群點(diǎn),聚類的效果得到了改善。美中不足是計(jì)算量較大,容易受閾值影響,有待進(jìn)一步的改進(jìn)。 參考文獻(xiàn): [1]朱灝東,鐘勇,趙向輝.一種優(yōu)化初始中心點(diǎn)的K-means文本聚類算法[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版),2009,41(6): 29-32. [2]劉韜,蔡淑琴,曹豐文,等.基于距離濃度的K均值聚類算法[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,35(10): 50-52. [3]孟佳娜,鄧?yán)?,于玉海,?一種改進(jìn)的K均值聚類算法[J].大連民族學(xué)院學(xué)院(自然科學(xué)版), 2011, 13(3): 274-276. [4]賈晨科,邱保志.基于K-距離的孤立點(diǎn)和聚類算法研究[D].鄭州:鄭州大學(xué),2006. [5]劉大任,孫煥良,牛志成,等.一種新的基于密度的聚類與孤立點(diǎn)檢測算法[J].沈陽建筑大學(xué)報(bào)(自然科學(xué)版),2007,22(1):149-153. [6]劉濤,尹紅健.基于半監(jiān)督學(xué)習(xí)K-均值聚類算法研究[J].計(jì)算機(jī)應(yīng)用研究, 2010,27(3):913-916. [7]王圓妹.一種改進(jìn)的K-均值聚類算法的研究[J].長江大學(xué)學(xué)報(bào)(自然科學(xué)版),2006, 3(4):76-77. [8]徐向陽.K-均值聚類算法在關(guān)系數(shù)據(jù)庫中的應(yīng)用[J].桂林電子科技大學(xué)學(xué)報(bào), 2008, 28 (4):313-316. [9]李志圣,孫越恒,何丕廉,等.基于K-Means和半監(jiān)督機(jī)制的單類中心學(xué)習(xí)算法[J].計(jì)算機(jī)應(yīng)用, 2008, 28(10): 2513-2516. Hybrid Clustering Algorithm Based on the K-Means Clustering LIU Ming-shu (Huangshan Vocational and Technical College, Huangshan, Anhui 245000, China) Abstract:K-means is one of typical clustering algorithm, but it is easily affected by the outliers, the initial cluster center of mass, and the given cluster number and so on. In this paper, the method of similar density is used to determine the initial cluster center of mass, then to remove outliers through the outlier determine rules. Furthermore, we make an improvement on K-means clustering algorithm and improve effectiveness and stability of the clustering result by the experiment. Key words:K-means clustering, clustering algorithm, isolated point, similar density 文章編號:1007-4260(2016)01-0040-03 中圖分類號:TP301.6 文獻(xiàn)標(biāo)識碼:A DOI:10.13757/j.cnki.cn34-1150/n.2016.01.012 作者簡介:劉明術(shù),男, 安徽太湖人,碩士,黃山職業(yè)技術(shù)學(xué)院講師,研究方向?yàn)檠芯糠较驍?shù)據(jù)挖掘。E-mail: 1987982580@qq.com *收稿日期:2015-08-27 網(wǎng)絡(luò)出版時(shí)間:2016-03-15 17:05網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/34.1150.N.20160315.1705.012.html