史彥麗,金 歡

(1.吉林化工學(xué)院 理學(xué)院,吉林 吉林 132022；2.吉林化工學(xué)院 信息與控制工程學(xué)院,吉林 吉林 132022)

聚類屬于無監(jiān)督學(xué)習(xí)算法,依據(jù)某個(gè)或者多個(gè)相似度準(zhǔn)則,使處于同一類的數(shù)據(jù)具有更高相似性,處于不同類的數(shù)據(jù)具有更大的差異性.聚類算法在大數(shù)據(jù)[1]、數(shù)據(jù)挖掘[2]、社交網(wǎng)絡(luò)[3]、離群值檢測(cè)[4]、計(jì)算機(jī)視覺[5]、模式識(shí)別[6]、圖像處理[7-8]以及生物信息學(xué)[9]等領(lǐng)域應(yīng)用廣泛.近年來，學(xué)者們提出了大量聚類算法.均值漂移[10](Meanshift)算法作為一種爬山算法,算法核心為順著密度增加的方向找到聚簇點(diǎn).DBSCAN[11]算法是一種基于密度的聚類算法,善于處理多種形狀分布的數(shù)據(jù)集.AP[12]聚類算法的核心思想是將所有的目標(biāo)數(shù)據(jù)作為潛在聚類中心,通過計(jì)算所有數(shù)據(jù)點(diǎn)之間的相似度關(guān)系來構(gòu)建矩陣,進(jìn)而獲得各樣本的聚類中心.

K-means聚類算法是一種基于劃分的聚類算法,通過設(shè)置初始中心點(diǎn)和類簇個(gè)數(shù)k,反復(fù)迭代尋優(yōu),直到迭代結(jié)果不發(fā)生改變,確定最終聚類中心點(diǎn),算法結(jié)束.但算法未能考慮數(shù)據(jù)點(diǎn)的密度分布,對(duì)非凸形分布的數(shù)據(jù)集聚類效果差.另外,K-means聚類算法的k值選取需先驗(yàn)知識(shí),如何選取最優(yōu)k值成為K-means聚類算法的重難點(diǎn).與K-means聚類算法不同,進(jìn)化聚類算法[13]不僅可以反映當(dāng)前時(shí)刻各數(shù)據(jù)特征之間的關(guān)系,還能為后期即將輸入的新數(shù)據(jù)做好聚類準(zhǔn)備.當(dāng)輸入新數(shù)據(jù)時(shí),該點(diǎn)將分配給距離相似度最大的類或以該點(diǎn)為中心自建新類,可以觀察每個(gè)數(shù)據(jù)對(duì)最終聚類結(jié)果所產(chǎn)生的影響,通過反復(fù)迭代更新,中心點(diǎn)和類簇?cái)?shù)目將自適應(yīng)選取.

基于上述分析,本文提出基于進(jìn)化思想的類簇融合聚類算法及其類簇融合算法(Clustering lgorithm based on evolutionary thought and its cluster fusion algorithm,EF-means).針對(duì)K-means聚類算法k值選取需要先驗(yàn)知識(shí)的問題,EF-means聚類算法將K-means聚類算法與進(jìn)化聚類算法進(jìn)行合并,通過設(shè)定距離倍參α,逐漸將數(shù)據(jù)劃分,在此過程中自動(dòng)確定類簇?cái)?shù)目k.

針對(duì)K-means聚類算法處理非凸形分布的數(shù)據(jù)集時(shí)聚類效果差,提出基于最近距離的中間圓密度簇融合算法與基于代表類的中間圓密度簇融合算法兩種類簇融合算法,可大幅降低聚類算法在k值選取上的復(fù)雜度及時(shí)間成本,通過度量類簇體間的密度相似度及類簇間部分點(diǎn)集的密度相似度,將相似度大的類簇進(jìn)行融合,可處理凹形分布的數(shù)據(jù)集,并使k值逐漸減小,直到類簇融合過程結(jié)束,達(dá)到合理的聚類結(jié)果.

1 預(yù)備知識(shí)

1.1 K-means聚類算法

K-means算法對(duì)數(shù)據(jù)集聚類前,需先設(shè)定類簇?cái)?shù)目k及對(duì)應(yīng)的初始聚類中心點(diǎn),接著以歐式距離為相似度準(zhǔn)則,將剩余數(shù)據(jù)點(diǎn)劃分到相似度大的中心點(diǎn)所代表的類簇中,形成k個(gè)類簇.然后,更新各類簇中心坐標(biāo),并重新將數(shù)據(jù)劃分給新的聚類中心點(diǎn).最后,迭代以上過程,當(dāng)連續(xù)兩次的聚類結(jié)果不發(fā)生改變,則所有數(shù)據(jù)完成劃分,聚類完成.

對(duì)于給定數(shù)據(jù)集ZN×M=[z1,z2,…,zN]T,其中zi=[zi1,zi2,…,ziM],N為樣本數(shù),M為樣本維數(shù),K-means聚類算法將數(shù)據(jù)集ZN×M劃分為k個(gè)類簇S=[s1,s2,…,sk],對(duì)應(yīng)的類簇中心點(diǎn)為O=[o1,o2,…,ok].計(jì)算各類簇內(nèi)的點(diǎn)與中心點(diǎn)的距離平方和為

(1)

其中,si表示第i個(gè)類簇；k為類簇?cái)?shù)目；oi表示第i個(gè)類簇的質(zhì)心；z表示Si中的樣本點(diǎn).最終目標(biāo)是使各類簇內(nèi)的點(diǎn)與中心點(diǎn)的距離平方和L(S)最小,聚類結(jié)束.

1.2 K-means聚類算法缺陷分析

K-means聚類算法也存在缺陷,綜合多方面分析,表現(xiàn)為以下3方面：

(1)k值及初始聚類中心點(diǎn)的選取需憑借先驗(yàn)知識(shí).聚類前,K-means聚類算法需設(shè)定參數(shù)k，對(duì)擁有龐大數(shù)據(jù)量或維度高的數(shù)據(jù)集需要反復(fù)嘗試調(diào)整參數(shù)k,時(shí)間成本高,且聚類結(jié)果不理想.對(duì)于同一數(shù)據(jù)集,K-means聚類算法選取不同的k值所對(duì)應(yīng)聚類結(jié)果的可視化，如圖1所示.

(2)若各類簇的體積差異大且類簇間距離近,則聚類效果不佳.K-means聚類算法僅用歐式距離作為相似度,當(dāng)各類簇的樣本點(diǎn)數(shù)分配不均勻?qū)е赂黝惔氐捏w積差異大時(shí),聚類效果不理想.對(duì)于Aggregation數(shù)據(jù)集,使用K-means聚類算法聚類的可視化結(jié)果如圖2所示.

(3)對(duì)非凸形分布的數(shù)據(jù)集聚類效果差.K-means聚類算法處理非凸形分布的數(shù)據(jù)集時(shí),沒有考慮到各數(shù)據(jù)之間的密度相似度和余弦相似度等相似性,各數(shù)據(jù)的相似性和差異性無法合理度量,使聚類結(jié)果不理想.使用K-means聚類算法對(duì)Twomoon數(shù)據(jù)集聚類的可視化結(jié)果如圖3所示.

為解決上述問題,近些年學(xué)者們對(duì)K-means聚類算法進(jìn)行了改進(jìn).Arthur[14]提出了K-means++聚類算法,在K-means聚類算法的基礎(chǔ)上使初始中心點(diǎn)的距離盡可能的遠(yuǎn),聚類中心點(diǎn)將更準(zhǔn)確,但k值選取仍需人為確定.Memarsadeghi[15]提出了ISODATA聚類算法,對(duì)于聚類結(jié)果中的每一個(gè)類簇,當(dāng)類簇內(nèi)的樣本數(shù)過少或者兩類簇間的距離相似度大時(shí)進(jìn)行合并,當(dāng)類簇內(nèi)的數(shù)據(jù)點(diǎn)過于離散時(shí),則將該類簇分裂為多個(gè)類簇,通過反復(fù)迭代,k值逐步被確定,但算法需要調(diào)整的參數(shù)多,參數(shù)選取難度大,且各參數(shù)相互影響.Fahim[16]提出了NOK-means聚類算法,NOK-means聚類算法將DBSCAN聚類算法與K-means聚類算法合并,利用DBSCAN聚類算法確定類簇的數(shù)目并計(jì)算各類簇的中心點(diǎn),從而確定K-means聚類算法的參數(shù),使得類簇?cái)?shù)k以及聚類中心點(diǎn)自適應(yīng)選取,但NOK-means聚類算法無法對(duì)非凸形分布的數(shù)據(jù)集正確聚類.Sinaga[17]等人提出了U-K-means聚類算法,相比于K-means聚類算法,U-K-means聚類算法不需要任何初始化和參數(shù)選擇仍可自動(dòng)確定最優(yōu)類簇的數(shù)量,但算法仍無法精準(zhǔn)處理非凸形分布的數(shù)據(jù)集.

2 EF-means算法

針對(duì)K-means聚類算法的k值選取需要靠先驗(yàn)知識(shí),以及K-means聚類算法處理非凸形分布的數(shù)據(jù)集時(shí)聚類效果較差,本文提出基于進(jìn)化思想的聚類算法及其類簇融合算法.EF-means算法將K-means聚類算法與進(jìn)化聚類框架進(jìn)行合并,可將數(shù)據(jù)劃分為多個(gè)體積小的凸形分布的類簇,此時(shí)類簇?cái)?shù)k自適應(yīng)選取,但實(shí)際類簇?cái)?shù)目大于真實(shí)類簇?cái)?shù)目.提出基于最近距離的中間圓密度簇融合算法,算法尋求距離相似度最大的類簇,將凸形分布、體積小且密度相似度大的類簇融合為一個(gè)類簇.k值逐漸接近真實(shí)值,但該類簇融合算法無法融合相似度大且形狀為非凸形分布的類簇.為解決此問題,本文提出基于代表類的中間圓密度簇融合算法,算法將各個(gè)類簇內(nèi)的一部分?jǐn)?shù)據(jù)作為代表類,用各自代表類代替原始類簇判斷類簇之間融合,可將非凸形分布的且密度相似度大的類簇融合,k值將逐漸減小,直到類簇融合過程結(jié)束,聚類完成.

2.1 基于進(jìn)化聚類的K-means聚類算法

將K-means聚類算法與進(jìn)化聚類框架合并,類簇?cái)?shù)目k將自適應(yīng)確定,可大幅降低聚類算法在k值選取上的復(fù)雜度及時(shí)間成本.對(duì)于數(shù)據(jù)集ZN×M=[z1,z2,…,zN]T,其中zi=[zi1,zi2,…,ziM],N為樣本數(shù),M為樣本維數(shù).首先,將ZN×M中任意兩個(gè)數(shù)據(jù)點(diǎn)z1與z2設(shè)為初始聚類中心點(diǎn).當(dāng)新數(shù)據(jù)點(diǎn)zi輸入時(shí),計(jì)算zi與聚類中心點(diǎn)的歐氏距離,并求得所有聚類中心點(diǎn)之間距離的均值,公式如下：

(2)

(3)

nj=nj+1,

(4)

(5)

k=k+1,

(6)

uk=zk,

(7)

其中,α為待調(diào)參數(shù)(距離倍數(shù)參數(shù)),nj代表第j個(gè)類的數(shù)據(jù)點(diǎn)的個(gè)數(shù),ej=zt-ui.

如圖4所示,因算法采用歐氏距離來度量各數(shù)據(jù)點(diǎn)及類簇之間的相似度,聚類結(jié)果均為凸形分布的類簇,實(shí)際類簇?cái)?shù)大于真實(shí)類簇?cái)?shù),各類簇間存在重疊冗余特征.

2.2 類簇融合算法

在使用基于進(jìn)化聚類的K-means聚類算法進(jìn)行聚類過程中,各類簇之間存在間隙,隨著數(shù)據(jù)樣本點(diǎn)的逐步加入,各類簇之間的間隙將被逐漸填充,使原本空間上不相交的兩個(gè)類簇緊密相交,增加了各類簇間的相似性,為此，本文提出兩種類簇融合算法.類簇的融合算法可以很好地解決各類簇之間關(guān)系,設(shè)定對(duì)應(yīng)相似度來量化類簇間關(guān)系,將相似度大的類簇進(jìn)行融合,可以消除類簇間重疊和冗余的信息,使實(shí)際類簇?cái)?shù)目逐漸趨近真實(shí)值,得到更加精準(zhǔn)的聚類結(jié)果.

2.2.1 基于最近距離的中間圓密度簇融合算法

使用基于進(jìn)化思想的K-means聚類算法進(jìn)行聚類后,實(shí)際類簇?cái)?shù)大于真實(shí)類簇?cái)?shù).為解決此問題,提出基于最近距離的中間圓密度簇融合算法,算法具體流程如下.

上述聚類中心點(diǎn)為OK×M=[o1,o2,…,oK]T,其中oi=[oi1,oi2,…,oiM],K為類簇?cái)?shù),M為樣本維度.首先,計(jì)算所有簇與簇之間中心點(diǎn)的歐氏距離x(oi，oj),找到中心點(diǎn)相距最近的兩個(gè)類的中心點(diǎn)oi和oj,計(jì)算公式如下：

(8)

然后,設(shè)上述中心點(diǎn)oi與oj為圓A與圓B的圓心,兩圓半徑分別用rA與rB表示,oi與oj連線中點(diǎn)為中間圓圓心,r表示中間圓半徑,且滿足下式：

(9)

最后,比較中間圓中A類點(diǎn)和B類點(diǎn)的總數(shù)m(A,B)、圓A中點(diǎn)的數(shù)量mA與圓B中點(diǎn)的數(shù)量mB三者的大小,若m(A,B)>mA或m(A,B)>mB,則將A類與B類融合,并更新相應(yīng)參數(shù),公式如下：

ni=ni+nj,

(10)

(11)

否則不融合.不難看出m(A,B)可反映類簇A和類簇B的密度相似度,通過與類簇A、類簇B的點(diǎn)密度對(duì)比來判斷融合,可將密度相似度大的類簇合理合并,消除類簇間重疊和冗余信息,達(dá)到準(zhǔn)確聚類目的.

如圖5所示,在K-means聚類算法基礎(chǔ)上使用基于最近距離的中間圓密度簇融合算法的可視化結(jié)果,最終得到的結(jié)果為多個(gè)凹形分布的類簇,此時(shí)各類簇中心點(diǎn)之間的中點(diǎn)均分布于凹形類簇外,此時(shí)中間圓內(nèi)無數(shù)據(jù)點(diǎn)分布,中間圓的點(diǎn)密度無法正確量化兩個(gè)凹形類簇的相似性.

2.2.2 基于代表類的中間圓密度簇融合算法

凹形類簇之間的中間圓內(nèi)無數(shù)據(jù)點(diǎn)分布,因此中間圓的點(diǎn)密度無法正確量化兩個(gè)凹形類簇的相似性.為此,本文提出基于代表類的中間圓密度簇融合算法,該算法將各類簇之間相似度最大的l組點(diǎn)作為代表類,并將代表類代替原始類簇進(jìn)行類簇融合分析.具體過程如下：

對(duì)于聚類中心點(diǎn)集合OK×M,首先計(jì)算簇與簇之間所有點(diǎn)之間的相互距離,選取最近的2l個(gè)點(diǎn)作為代表點(diǎn),這些點(diǎn)組成的類稱為代表類,以2個(gè)代表類的中心點(diǎn)，及其連線中點(diǎn)o(k1,k2),這3點(diǎn)分別為圓心,調(diào)整半徑參數(shù),計(jì)算3個(gè)圓內(nèi)點(diǎn)的密度.計(jì)算如下：

(12)

(13)

其中vi是第i個(gè)代表點(diǎn)；o(k1,k2)k為代表類的中心點(diǎn)；ρki代表第i個(gè)圓的點(diǎn)密度；nki表示該類數(shù)據(jù)點(diǎn)在該圓內(nèi)的個(gè)數(shù).比較ρk1、ρk2與ρk3的大小.如果ρk3>ρk1或ρk3>ρk2,則合并聚類,更新相應(yīng)參數(shù)；否則不合并.重復(fù)以上,直到結(jié)果不發(fā)生改變,算法結(jié)束.

如圖6所示,在基于最近距離中間圓密度簇融合算法的基礎(chǔ)上使用基于代表類的中間圓密度簇融合算法的可視化結(jié)果.相似度大的非球形類簇發(fā)生了融合,得到類簇?cái)?shù)為真實(shí)值,聚類完成.

2.3 算法步驟

輸入：數(shù)據(jù)集data,距離倍參α,密度倍參ρk.

輸出：聚類結(jié)果C.

step 1：將數(shù)據(jù)集中任意兩個(gè)數(shù)據(jù)點(diǎn)作為初始中心點(diǎn).

step 2：當(dāng)有新數(shù)據(jù)點(diǎn)zi加入時(shí),根據(jù)式(2)計(jì)算與其最近的聚類中心點(diǎn)的距離rt.

step 4：重復(fù)step 2和step 3,直到無新的數(shù)據(jù)點(diǎn)加入時(shí),執(zhí)行step 5.

step 5：根據(jù)公式(8)找出相距最近的兩個(gè)類簇,根據(jù)公式(9)設(shè)定各圓的半徑,比較3個(gè)圓內(nèi)點(diǎn)的個(gè)數(shù)m(A，B),mA,mB,若m(A，B)>mA或m(A，B)>mB,則將兩類融合,并根據(jù)公式(10)、(11)更新相應(yīng)參數(shù).

step 6：重復(fù)step 5,直到m(A，B)

step 7：若ρk3>ρk1或ρk3>ρk2,則合并相應(yīng)的兩個(gè)類簇,并根據(jù)公式(10)、(11)更新相應(yīng)參數(shù),并重復(fù)上述步驟,直到ρk3<ρk1且ρk3<ρk2時(shí),聚類算法結(jié)束.

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)使用合成數(shù)據(jù)集對(duì)EF-Means算法進(jìn)行測(cè)試與評(píng)估.將EF-means聚類算法與DBSCAN[11]、OPTICS[18]、AP[19]與K-mean等聚類算法進(jìn)行比較.其中K-means、DBSCAN、OPTICS和AP均參照文獻(xiàn)[20]的實(shí)驗(yàn)結(jié)果.

3.1 評(píng)價(jià)指標(biāo)

本實(shí)驗(yàn)使用3個(gè)常用的聚類評(píng)價(jià)指標(biāo)評(píng)估最終聚類結(jié)果,分別為：AMI、ARI、FMI.以上3個(gè)指標(biāo)的值上界均為1,且當(dāng)值為1時(shí),聚類結(jié)果最優(yōu).

對(duì)于數(shù)據(jù)集,假設(shè)有U和V兩種不同的標(biāo)簽,其中U和V分別代表數(shù)據(jù)集的真實(shí)類別和聚類結(jié)果,則調(diào)整互信息AMI(U,V)的值為

(14)

其中：

H(U)與H(V)為對(duì)應(yīng)的香農(nóng)熵；MI(U,V)為U與V的互信息；E{MI(U,V)}為MI(U,V)的期望值.

調(diào)整蘭德系數(shù)ARI定義為

(15)

Fowlkes-Mallows指數(shù)為

(16)

其中：TP表示數(shù)據(jù)樣本對(duì)的真實(shí)類別和聚類結(jié)果一致；TN表示數(shù)據(jù)樣本對(duì)的真實(shí)類別和聚類結(jié)果均不一致；FP表示數(shù)據(jù)樣本對(duì)的聚類結(jié)果一致,但真實(shí)類別不一致；FN表示數(shù)據(jù)樣本對(duì)的真實(shí)類別一致,但是聚類結(jié)果不一致.

3.2 數(shù)據(jù)集

實(shí)驗(yàn)用到的合成數(shù)據(jù)集共6個(gè),各項(xiàng)參數(shù)如表1所示.

表1 合成數(shù)據(jù)集

為保證算法有效性驗(yàn)證的客觀性,選取不同類型數(shù)據(jù)集進(jìn)行測(cè)試說明.其中Aggregation數(shù)據(jù)集由7個(gè)樣本點(diǎn)數(shù)分配不均勻的類簇組成,且各類簇的體積差異較大；Flame數(shù)據(jù)集由1個(gè)球形分布的類簇和1個(gè)非球形分布的類簇組成,且兩個(gè)類簇相距較近；Jain數(shù)據(jù)集由2個(gè)非凸形分布的類簇組成,且各類簇內(nèi)的樣本點(diǎn)分布不均勻；Pathbased數(shù)據(jù)集由1個(gè)環(huán)形類簇和2個(gè)球形類簇組成,且球形類簇被環(huán)形類簇包圍；Spiral數(shù)據(jù)集由兩個(gè)相互環(huán)繞的環(huán)形類簇組成；D31數(shù)據(jù)集由31個(gè)球形類簇構(gòu)成，數(shù)據(jù)集的類簇?cái)?shù)目多，且各類簇間的距離較近.

3.3 算法參數(shù)選擇

3.4 合成數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

表2為5種聚類算法在6個(gè)數(shù)據(jù)集上的聚類結(jié)果及其對(duì)應(yīng)的參數(shù)值.圖7～9分別展示了EF-means聚類算法、DBSCAN聚類算法與K-means聚類算法對(duì)Jain、Flame和Pathbased數(shù)據(jù)集的聚類結(jié)果,“紅星”代表EF-means聚類算法與K-means聚類算法的類簇中心點(diǎn),DBSCAN算法的可視化圖中的黑色點(diǎn)代表算法識(shí)別出的噪聲點(diǎn).

表2的實(shí)驗(yàn)結(jié)果表明,本文所提出EF-means聚類算法整體性能優(yōu)于其他算法.處理表1的數(shù)據(jù)集時(shí),EF-means聚類算法顯著優(yōu)于其他4種聚類算法.處理Spiral與Jain數(shù)據(jù)集時(shí),EF-means聚類算法可以達(dá)到100%準(zhǔn)確的水平.處理D31數(shù)據(jù)集時(shí),EF-means聚類算法優(yōu)于除K-means算法之外的其他算法.

表2 5種聚類算法在6個(gè)合成數(shù)據(jù)集上的聚類性能

圖7的可視化結(jié)果可看出,Jain數(shù)據(jù)集由2個(gè)非球形分布的類簇組成,且各類簇內(nèi)的樣本點(diǎn)分布不均勻,稀疏度差異較大.EF-means聚類算法可正確發(fā)現(xiàn)數(shù)據(jù)集的形狀及類簇?cái)?shù).由于數(shù)據(jù)點(diǎn)的密集程度相差較大,DBSCAN聚類算法將其中一個(gè)類簇的多個(gè)點(diǎn)劃分為了噪聲點(diǎn),導(dǎo)致最終的聚類結(jié)果差.由于數(shù)據(jù)集由2個(gè)非球形分布的類簇組成,K-means聚類算法無法進(jìn)行準(zhǔn)確聚類.

圖8的可視化結(jié)果可看出,Flame數(shù)據(jù)集主要由一個(gè)凸形分布的類簇和一個(gè)非凸形分布的類簇組成,兩類簇緊密相接,且左上角有兩個(gè)噪音點(diǎn).對(duì)于含有凸形分布和非凸形分布類簇的數(shù)據(jù)集,EF-means聚類算法都能進(jìn)行準(zhǔn)確聚類.由于Flame數(shù)據(jù)集兩類簇邊緣緊密相接,且DBSCAN聚類算法易將均勻分布且相距較近的數(shù)據(jù)點(diǎn)聚為一類,導(dǎo)致DBSCAN聚類算法將Flame數(shù)據(jù)集兩類簇邊緣的數(shù)據(jù)點(diǎn)錯(cuò)誤地聚為一類.因數(shù)據(jù)集中含有非凸形分布的類簇,且K-means聚類算法無法排除噪聲點(diǎn),使得聚類結(jié)果差.

圖9的可視化結(jié)果可看出,Pathbased數(shù)據(jù)集由1個(gè)環(huán)形類簇和2個(gè)球形類簇組成,且球形類簇被環(huán)形類簇包圍.從圖9可以看出,EF-means聚類算法不僅能成功發(fā)現(xiàn)類簇?cái)?shù),還能進(jìn)行精準(zhǔn)聚類.由于數(shù)據(jù)集內(nèi)的球形類簇的點(diǎn)分布密集,環(huán)形類簇的點(diǎn)分布稀疏,DBSCAN聚類算法成功識(shí)別出中間的兩個(gè)類簇,并將環(huán)形類簇識(shí)別為噪聲點(diǎn).因數(shù)據(jù)集中包含2個(gè)球形類簇和1個(gè)非球形類簇,所以K-means聚類算法僅正確識(shí)別中間的2個(gè)類簇,而環(huán)形類簇被錯(cuò)誤地劃分為3個(gè)類,使得K-means聚類算法最終的準(zhǔn)確度很低.

4 結(jié) 論

針對(duì)K-means聚類算法的不足,本文提出了EF-means聚類算法.將K-means聚類算法與進(jìn)化聚類算法合并,數(shù)據(jù)點(diǎn)將分為多個(gè)凸形分布的類簇,再使用基于最近距離的中間圓密度簇融合算法和基于代表類的中間圓密度簇融合算法對(duì)凸形分布的類簇進(jìn)行融合,得到最終的聚類結(jié)果.K-means聚類算法對(duì)k值的選取十分敏感,而且在處理數(shù)據(jù)量大和類簇類別多的數(shù)據(jù)集時(shí),k值的選取及初始聚類中心點(diǎn)的選擇難度將大幅度增加,且無法處理非凸形分布的數(shù)據(jù)集,而EF-means聚類算法的距離倍數(shù)參數(shù)α和密度閾值參數(shù)ρk的取范圍較為固定,選取難度和時(shí)間成本低,有效地解決了K-means聚類算法的難題,使得k值被自適應(yīng)選取,不再需要初始聚類中心點(diǎn),并且可以識(shí)別任意形狀的類簇.通過對(duì)多個(gè)合成數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析及可視化觀察可知,使用EF-means聚類算法可正確發(fā)現(xiàn)數(shù)據(jù)集的形狀及類簇?cái)?shù),并且處理非凸形分布的數(shù)據(jù)集有較好的聚類效果,提高了算法的可行性與實(shí)用性.