基于進化思想的聚類算法及其類簇融合算法

史彥麗,金 歡

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

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

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

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

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

1 預備知識

1.1 K-means聚類算法

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

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

(1)

其中,si表示第i個類簇；k為類簇數(shù)目；oi表示第i個類簇的質心；z表示Si中的樣本點.最終目標是使各類簇內的點與中心點的距離平方和L(S)最小,聚類結束.

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

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

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

(2)若各類簇的體積差異大且類簇間距離近,則聚類效果不佳.K-means聚類算法僅用歐式距離作為相似度,當各類簇的樣本點數(shù)分配不均勻導致各類簇的體積差異大時,聚類效果不理想.對于Aggregation數(shù)據(jù)集,使用K-means聚類算法聚類的可視化結果如圖2所示.

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

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

2 EF-means算法

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

2.1 基于進化聚類的K-means聚類算法

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

(2)

(3)

nj=nj+1,

(4)

(5)

k=k+1,

(6)

uk=zk,

(7)

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

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

2.2 類簇融合算法

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

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

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

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

(8)

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

(9)

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

ni=ni+nj,

(10)

(11)

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

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

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

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

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

(12)

(13)

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

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

2.3 算法步驟

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

輸出：聚類結果C.

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

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

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

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

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

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

3 實驗結果與分析

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

3.1 評價指標

本實驗使用3個常用的聚類評價指標評估最終聚類結果,分別為：AMI、ARI、FMI.以上3個指標的值上界均為1,且當值為1時,聚類結果最優(yōu).

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

(14)

其中：

H(U)與H(V)為對應的香農熵；MI(U,V)為U與V的互信息；E{MI(U,V)}為MI(U,V)的期望值.

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

(15)

Fowlkes-Mallows指數(shù)為

(16)

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

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

實驗用到的合成數(shù)據(jù)集共6個,各項參數(shù)如表1所示.

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

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

3.3 算法參數(shù)選擇

3.4 合成數(shù)據(jù)集實驗結果分析

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

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

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

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

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

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

4 結 論

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