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

歐陽浩,陳 波，黃鎮(zhèn)謹(jǐn)，王 萌,王智文

(廣西科技大學(xué) 計(jì)算機(jī)學(xué)院，廣西 柳州 545006)

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

歐陽浩,陳 波，黃鎮(zhèn)謹(jǐn)，王 萌,王智文

(廣西科技大學(xué) 計(jì)算機(jī)學(xué)院，廣西 柳州 545006)

傳統(tǒng)的K-means算法只能識(shí)別出類似球形的數(shù)據(jù)集，傳統(tǒng)的MST聚類算法雖然能識(shí)別任意形狀的數(shù)據(jù)集，但對噪聲和異常點(diǎn)十分敏感，由此提出了一種將K-means聚類與MST聚類相結(jié)合的聚類算法。此算法先使用K-means算法將數(shù)據(jù)分割成多個(gè)小的類似球形的數(shù)據(jù)集，然后對各個(gè)小的數(shù)據(jù)集的均值點(diǎn)采用MST聚類算法進(jìn)行聚類分析。實(shí)驗(yàn)證明此算法具有較好的抗干擾性，并且可以識(shí)別出任意形狀分布的數(shù)據(jù)集。為了評價(jià)聚類算法的性能，文中同時(shí)提出了一種新的聚類質(zhì)量評價(jià)函數(shù)，實(shí)驗(yàn)證明此評價(jià)函數(shù)是有效的。

聚類分析;K-means;最小生成樹;質(zhì)量評價(jià)函數(shù)

0 引言

K-means算法[1]由于簡單、快速的特點(diǎn)，在現(xiàn)實(shí)生活中得到廣泛的應(yīng)用[2-3]。但傳統(tǒng)的K-means算法也存在一些缺陷[4-5]：①要求預(yù)先給定一個(gè)確定的k值；②對初始聚類中心敏感；③只能發(fā)現(xiàn)球形或圓形的簇；④算法對“噪聲”和孤立點(diǎn)敏感。

MST[6-7]聚類算法是對所有的數(shù)據(jù)點(diǎn)建立最小生成樹，再去掉最小樹的若干個(gè)最大邊，從而得到多個(gè)簇。此方法可以發(fā)現(xiàn)任意形狀的簇[8]，但實(shí)際應(yīng)用中容易受到“噪聲”的影響[9]。

針對標(biāo)準(zhǔn)K-means算法和MST聚類算法不足，本文做了以下改進(jìn)：將K-means算法與MST聚類算法結(jié)合，可以有效地減少“噪聲”對聚類結(jié)果的影響，且能發(fā)現(xiàn)任意形狀的簇。

1 K-means聚類算法和最小生成樹聚類算法

1.1 K-means聚類算法

K-Means算法的核心思想是通過迭代把數(shù)據(jù)對象劃分到不同的簇中，以求目標(biāo)函數(shù)的最小化。其中，通常采用的目標(biāo)函數(shù)形式為平均誤差標(biāo)準(zhǔn)準(zhǔn)則函數(shù)：

1.2 最小生成樹聚類算法

最小生成樹聚類算法建立在完全圖的鄰接矩陣基礎(chǔ)上。首先需構(gòu)建賦權(quán)完全圖。在得到各點(diǎn)的距離的鄰接矩陣后，便利用Kruskal或者Prim算法找最小生成樹，再刪除掉最小生成樹中權(quán)值最大的K-1條邊。這樣將得到K個(gè)子樹，這K個(gè)子樹就是K個(gè)簇，如圖1所示。

圖1 MST聚類

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

(KmMST算法)

2.1 基本思想

在傳統(tǒng)的K-means算法中，先給定K的值，然后采用迭代的方式來完成聚類。K值一般情況下數(shù)值取得比較小，這樣帶了的問題是，使得聚類結(jié)果很容易受到噪聲的干擾，而且只有當(dāng)每個(gè)簇的大小近似，形狀類似于球形時(shí)才能得到一個(gè)好的聚類結(jié)果。如果在聚類分析時(shí)，能將K取值比較大的時(shí)候，這樣可以將數(shù)據(jù)對象分組成多個(gè)小的球形的簇。如圖2。然后以這些小的簇的均值點(diǎn)建立最小生成樹，刪除掉C-1條最大的邊，從而得到最終的分組。這樣可以降低噪聲或異常點(diǎn)對于聚類分析的影響。并且可以識(shí)別出任意形狀分布的數(shù)據(jù)對象。

圖2 KmMST中間結(jié)果(K=10)

2.2 K-means算法中K的獲取

2.3 算法描述

KmMST算法描述如下：

輸入：n個(gè)數(shù)據(jù)對象，調(diào)節(jié)系數(shù)r，C

輸出：若干個(gè)簇

方法:

(1)計(jì)算K的值，K=|nr|(r∈[0,1])，r的常用系數(shù)為0.5;

(2)使用K-means聚類算法，得到K個(gè)子類;

(3)計(jì)算各個(gè)子類均值點(diǎn)之間的距離，對子類的距離進(jìn)行遞增排序;

(4)采用Kruskal算法，生成最小生成樹;

(5)刪除掉C-1條權(quán)值最大的邊，從而生成C個(gè)連通分支，即C個(gè)類。

2.4 算法的復(fù)雜度分析

假定有n個(gè)數(shù)據(jù)對象，調(diào)節(jié)系數(shù)為r，算法第一步用K-means聚類的時(shí)間復(fù)雜度為O(Knt)=O(nrnt)=O(nr+1t)，其中r∈[0,1]，t為迭代次數(shù)。算法第二步生成最小生成樹的時(shí)間復(fù)雜度為：O((nr(nr-1)/2)log(nr(nr-1)/2))。所以總的算法的時(shí)間復(fù)雜度為O(nr+1t+(nr(nr-1)/2)log(nr(nr-1)/2))。算法的空間復(fù)雜度為O(n+nr(nr-1)/2)。

3 一種新的聚類質(zhì)量評價(jià)函數(shù)

在實(shí)際的聚類分析算法中，對于聚類結(jié)果的評價(jià)常用的評價(jià)函數(shù)是本文1.1節(jié)中的平均誤差標(biāo)準(zhǔn)準(zhǔn)則函數(shù)，此函數(shù)對于分布均勻，大小相近的數(shù)據(jù)集可以進(jìn)行很好的評價(jià)，但對于任意動(dòng)態(tài)變化或未知結(jié)構(gòu)的數(shù)據(jù)集的評價(jià)較差[10-11]。本文根據(jù)聚類的特點(diǎn)，即簇內(nèi)相似度盡可能高，而簇間相似度盡可能低，提出了一種新的質(zhì)量評價(jià)函數(shù),此評價(jià)函數(shù)可以對任意結(jié)構(gòu)的數(shù)據(jù)按照聚類分析的定義做出相應(yīng)的評價(jià)。

定義1:簇間相異度(inter-clusterdissimilarity，INTER_CD)。簇間相異度是描述聚類中，各個(gè)簇之間的相異度之和，其定義為：

其中C為簇的數(shù)目；dmin(Ti,Tj)表示簇Ti與簇Tj之間的最短距離，即：

定義2:簇內(nèi)相似度(intra-clustersimilarity，INTRA_CS)。簇內(nèi)相似度是描述聚類中，各個(gè)簇內(nèi)部數(shù)據(jù)點(diǎn)之間的相似度，其定義為：

其中wMST(Ti)表示簇Ti的最小生成樹的權(quán)值；|Ti|表示簇Ti中數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

定義3:簇內(nèi)平均誤差(intra-meandifference，INTRA_MD)。平均誤差是描述數(shù)據(jù)點(diǎn)與它們所屬簇的質(zhì)心的誤差的平均值，其定義為：

其中ci表示簇Ti的均值，即：

定義4：簇間平均誤差(inter-meandifference，INTER_MD)。平均誤差是描述數(shù)據(jù)點(diǎn)與其他非屬簇的質(zhì)心的誤差的平均值，其定義為：

定義5：聚類熵(clusteringentropy，CE)。聚類熵是描述聚類中各個(gè)簇?cái)?shù)據(jù)量的均勻分布情況，其定義為：

其中|p|為聚類中所有數(shù)據(jù)對象的個(gè)數(shù)。

定義6：聚類指數(shù)(clusteringindex，CI)。聚類指數(shù)是用于描述聚類質(zhì)量的指數(shù)，其定義為：

其中α∈[0,1]。

4 實(shí)驗(yàn)分析

實(shí)驗(yàn)中選擇了3個(gè)不同分布特征的數(shù)據(jù)集進(jìn)行計(jì)算實(shí)驗(yàn)，數(shù)據(jù)集通過計(jì)算機(jī)程序隨機(jī)產(chǎn)生,數(shù)據(jù)分布見圖3～圖5。PC機(jī)的配置為：Intel(R)Core(Tm)2DuoCPUET500 @2.93GHz2.93GHz，2.0GB內(nèi)存。軟件環(huán)境是WindowXPSP3V6.2，VC6.0。

4.1 與K-means以及MST聚類算法的比較

實(shí)驗(yàn)1：正態(tài)分布數(shù)據(jù)集的實(shí)驗(yàn)。使用的數(shù)據(jù)集用D1表示，共有250個(gè)二維的數(shù)據(jù)點(diǎn)，如圖3所示。由圖3不難看出，D1明顯包含2個(gè)類。圖6是采用K-means聚類算法,K=2；圖7是采用普通MST聚類算法，C=2。圖8是采用KmMST聚類算法,其中K=|nr|=15,(n=250,r=0.5)。

實(shí)驗(yàn)2：大小不均勻數(shù)據(jù)集的實(shí)驗(yàn)。使用的數(shù)據(jù)集用D2表示，共有340個(gè)二維的數(shù)據(jù)點(diǎn)，如圖4所示。由圖4不難看出，D2明顯包含2個(gè)類。圖9是采用K-means聚類算法，K=2。圖10是采用普通MST聚類算法。圖11是采用KmMST聚類算法的分析結(jié)果，其中K=|nr|=18,(n=340,r=0.5)。

實(shí)驗(yàn)3：嵌套數(shù)據(jù)集的實(shí)驗(yàn)。使用的數(shù)據(jù)集用D3表示，共有320個(gè)二維的數(shù)據(jù)點(diǎn)，如圖5所示。由圖5不難看出，D3明顯包含2個(gè)類。圖12是采用K-means聚類算法，K=2。圖13是采用普通MST聚類算法。圖14是采用KmMST聚類算法最后的分析結(jié)果，其中K=|nr|=17,(n=320,r=0.5)

圖3 實(shí)驗(yàn)1_原始數(shù)據(jù) 圖4 實(shí)驗(yàn)2_原始數(shù)據(jù)

圖5 實(shí)驗(yàn)3_原始數(shù)據(jù) 圖6 實(shí)驗(yàn)1_K-means運(yùn)算結(jié)果

圖7 實(shí)驗(yàn)1_MST聚類運(yùn)算結(jié)果 圖8 實(shí)驗(yàn)1_KmMST運(yùn)算結(jié)果

圖9 實(shí)驗(yàn)2_K-means運(yùn)算結(jié)果 圖10 實(shí)驗(yàn)2_MST聚類運(yùn)算結(jié)果

圖11 實(shí)驗(yàn)2_KmMST運(yùn)算結(jié)果 圖12 實(shí)驗(yàn)3_K-means運(yùn)算結(jié)果

圖13 實(shí)驗(yàn)3_MST聚類運(yùn)算結(jié)果 圖14 實(shí)驗(yàn)3_KmMST運(yùn)算結(jié)

4.2 與DBSCAN算法的比較

實(shí)驗(yàn)4 ：DBSCAN算法中使用的人工測試數(shù)據(jù)的實(shí)驗(yàn)。實(shí)驗(yàn)中的數(shù)據(jù)集來自文獻(xiàn)[10]當(dāng)中的人工測試數(shù)據(jù)集D4、D5、D6。其中，D4有280個(gè)數(shù)據(jù)點(diǎn)，D5有355個(gè)數(shù)據(jù)點(diǎn)，D6有240個(gè)數(shù)據(jù)點(diǎn)。圖15～圖17，分別給出了使用KmMST聚類算法(r=0.5)對D4-D6的實(shí)驗(yàn)結(jié)果。可以看出KmMST同樣能識(shí)別出這三個(gè)測試數(shù)據(jù)集。

圖15 KmMST對D4運(yùn)算結(jié)果 圖16 KmMST對D5運(yùn)算結(jié)果

圖17 KmMST對D6運(yùn)算結(jié)果

實(shí)驗(yàn)5：DBSCAN算法中使用的真實(shí)數(shù)據(jù)的實(shí)驗(yàn)。實(shí)驗(yàn)采用的真實(shí)數(shù)據(jù)是SEQUOIA 2000基準(zhǔn)數(shù)據(jù)庫中的數(shù)據(jù)集，也是文獻(xiàn)[2]中用來對DBSCAN算法進(jìn)行測試的數(shù)據(jù)庫。 圖18給出了KmMST(r=0.5)以及DBSCAN(ε=20，MinPts=4)兩個(gè)算法的性能比較結(jié)果。從圖中可以看出KmMST相對DBSCAN器運(yùn)行時(shí)間更少。

圖18 KmMST與DBSCAN性能對比

表1 聚類性能比較表

4.3 與其他改進(jìn)K-means算法的比較

實(shí)驗(yàn)6:UCI數(shù)據(jù)集的實(shí)驗(yàn)。為了驗(yàn)證KmMST算法的有效性，本文將此算法與文獻(xiàn)[9]中的基于密度的K-Means算法以及文獻(xiàn)[12]中的基于遺傳算法的K-Means算法進(jìn)行比較，分析數(shù)據(jù)來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(http://ftp.ics.uci.edu/pub/machine-learning-database)，數(shù)據(jù)集為：iris，glass以及wine。表2對這幾個(gè)數(shù)據(jù)集進(jìn)行了描述。

表2 數(shù)據(jù)集描述

基于密度的K-Means算法中參數(shù)ε的設(shè)置在文獻(xiàn)[13]中已驗(yàn)證ε=1.01時(shí)，正確率最高。基于遺傳算法的K-Means算法所使用的參數(shù)設(shè)置，來自提供此算法的文獻(xiàn)[12]：種群大小m=30，算法的最大迭代次數(shù)T=100，交叉概率pc1=0.9，pc2=0.6，變異概率pm1=0.1，pcm2=0.001，b=1000。表3給出了三種算法的性能比較。

表3 KmMST與其他改進(jìn)K-Means的性能比較

5 結(jié)束語

本文提出了一種將K-means聚類與MST聚類相結(jié)合的KmMST聚類算法。此算法先將數(shù)據(jù)集分割成多個(gè)小類似球形的分組，然后對各個(gè)分組采用最小樹聚類的方法來完成聚類分析。算法具有較好的抗干擾性，并且可以識(shí)別出任意形狀分布的數(shù)據(jù)集，是一種有效地聚類方法。對于聚類質(zhì)量性能的評價(jià)，本文提出了一個(gè)新的質(zhì)量評價(jià)函數(shù)。

本文只對低維的情況進(jìn)行了研究與實(shí)驗(yàn)，對于高維的情況仍缺少研究，而且此算法只適用于連續(xù)型的數(shù)據(jù)，不適于分組屬性數(shù)據(jù)。因此對于這些問題，需要在今后的工作中作進(jìn)一步的研究。

[1]MacQueenJ.Somemethodsforclassificationandanalysisofmultivariateobservations[C].Proceedingsof5thBerkeleySymposiumonMathematicalStatisticsandProbability.Berkeley:UniversityofCaliforniaPress, 1967: 281-297.

[2] 楊瑞龍,朱慶生,謝洪濤. 快速混合Web文檔聚類[J]. 計(jì)算機(jī)工程與應(yīng)用, 2010,46(22): 12-15.

[3] 向堅(jiān)持，劉相濱，資武成，等.基于密度的K-Means算法及在客戶細(xì)分中的應(yīng)用研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008,44(35): 246-248.

[4]GuhaS,RastogiR,ShimK.CURE:anefficientclusteringalgorithmfordatabase.In:HaasLM,TiwaryA,eds.ProoftheACMSIGMODInternationalConferenceonManagementofData.Seattle:ACMPress, 1998: 73-84.

[5] Jiawei Han, Micheline Kamber. Data Mining:Concept and Techniques. Beijing Higher Education Press, 2001.

[6] Anil K Jain. Richard C Dubes. Algorithms for clustering data[M]. New Jersey: Prentice-Hall. Inc, 1996: 55.

[7] Charles T Zahn. Graph-theoretical methods for detecting and describing gestalt clusters[J]. IEEE Transactions on Computers, 1971, C-20(1): 68-86.

[8] 楊國慧,周春光,黃艷新，等. 最小生成樹用于基因表示數(shù)據(jù)的聚類算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2003, 40(10): 1431-1435.

[9] 汪閩,周成虎,裴韜，等. 一種帶控制節(jié)點(diǎn)的最小生成樹聚類方法[J]. 中國圖像圖形學(xué)報(bào), 2002, 7(8): 766-770.

[10] 張惟皎,劉春煌,李芳玉.聚類質(zhì)量的評價(jià)方法[J].計(jì)算機(jī)工程, 2005,31(20):10-12.

[11] 韓習(xí)武,趙鐵軍.一種聚類質(zhì)量的評價(jià)方法及其應(yīng)用[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2009,41(11):225-227.

[12] 賴玉霞,劉建平,楊國興.基于遺傳算法的K均值聚類分析[J].計(jì)算機(jī)工程,2008,34(20):200-202.

[13] 王莉,周獻(xiàn)中,沈捷.一種改進(jìn)的粗K均值聚類算法[J].控制與決策,2012,27(11):1711-1714,1719.

(編輯 趙蓉)

MST Clustering Algorithm Based on K-means

OUYANG Hao,CHEN Bo，HUANG Zhen-jin，WANG Meng，WANG Zhi-wen

(Computer School, Guangxi University of Science and Technology, Liuzhou Guangxi 545006, China)

Classical K-means only can distinguish similar sphere-cluster, classical MST clustering algorithm can distinguish arbitrary cluster, but it’s very sensitive to noisy and abnormal data, the paper combine K-means and MST clustering algorithm. Firstly, K-means algorithm divides data to many similar mini sphere-clusters, and then MST clustering algorithm deals with mean points of these mini sphere-clusters. Results show that the new algorithm has good anti-noisy ability, and can distinguish arbitrary cluster. In order to analyze the quality of clustering, the paper provides a new quality evaluation function. Results show the function is effective.

clustering analysis; K-means; MST; quality evaluation function

1001-2265(2014)04-0041-04

10.13462/j.cnki.mmtamt.2014.04.011

2013-08-12；

2013-09-17

廣西自然科學(xué)基金項(xiàng)目(2013GXNSFAA019336);廣西自然科學(xué)基金項(xiàng)目(2013GXNSFBA019280);廣西壯族自治區(qū)教育廳項(xiàng)目(201203YB124);廣西科技大學(xué)科學(xué)基金(校科自1261128)

歐陽浩(1979—)，男，湖南平江人，廣西科技大學(xué)講師，碩士，研究方向?yàn)閿?shù)據(jù)挖掘和人工智能等，(E-mial)ouyanghao@tom.com。

TH122;TG65

A