基于多目標(biāo)進(jìn)化的聚類實(shí)現(xiàn)

汪 宏 海

(浙江旅游職業(yè)學(xué)院，杭州 311231)

聚類分析本質(zhì)上可以看作是一個(gè)優(yōu)化問(wèn)題，采用不同的優(yōu)化指標(biāo)，聚類問(wèn)題就不同.已有的聚類算法存在的主要問(wèn)題是：只分析一種指標(biāo)，因而無(wú)法適用于不同特征類型的數(shù)據(jù).多目標(biāo)優(yōu)化算法能實(shí)現(xiàn)對(duì)多個(gè)不同目標(biāo)的同時(shí)優(yōu)化，受此啟發(fā)，可以將聚類問(wèn)題轉(zhuǎn)化為對(duì)多個(gè)聚類指標(biāo)的優(yōu)化問(wèn)題，從而獲得更好的聚類性能[1].

進(jìn)化算法適合求解復(fù)雜、非線性的問(wèn)題，多目標(biāo)進(jìn)化是采用進(jìn)化計(jì)算的方法對(duì)多目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解.由于多目標(biāo)優(yōu)化問(wèn)題通常是復(fù)雜、非線性的，因此，多目標(biāo)進(jìn)化算法非常適合求解這類問(wèn)題.

基于多目標(biāo)進(jìn)化的聚類優(yōu)化是目前的一個(gè)研究熱點(diǎn)，涌現(xiàn)出很多代表性工作.文獻(xiàn)[1]在多目標(biāo)螢火蟲(chóng)算法中引入一種動(dòng)態(tài)調(diào)整的變異機(jī)制以獲得更加均勻分布的非劣解，其中以動(dòng)態(tài)減小的概率選擇個(gè)體，并采用類似于差分進(jìn)化算法中變異算子的策略對(duì)其進(jìn)行變異，通過(guò)自適應(yīng)調(diào)整收縮因子以提高變異效率.文獻(xiàn)[2]提出一種基于局部集成和克隆選擇的多目標(biāo)聚類算法.在聚類過(guò)程中，周期性的將聚類解集劃分為若干鄰域，對(duì)每個(gè)鄰域進(jìn)行局部集成操作，剔除各個(gè)類數(shù)下的不合理劃分；利用克隆選擇算法的思想構(gòu)建3種變異算子，推動(dòng)種群的進(jìn)化，分別具有增大或減小當(dāng)前解的聚類類數(shù)、調(diào)整當(dāng)前解樣本劃分情況的功能.文獻(xiàn)[3]提出一種基于密度估計(jì)的多目標(biāo)免疫克隆聚類方法.該算法根據(jù)密度聚類的思想，通過(guò)引入核密度估計(jì)，解決了克隆算法中克隆規(guī)模的問(wèn)題.文獻(xiàn)[4]提出了一種基于分解的進(jìn)化多標(biāo)進(jìn)化聚類算法，無(wú)需提前設(shè)定權(quán)重，提高了聚類效果.文獻(xiàn)[5]提出了一種改進(jìn)的離散多目標(biāo)量子微粒群聚類算法，提出適合整數(shù)編碼的離散量子微粒更新公式，對(duì)算法的性能提升起到了很大作用.

以上算法都是基于多目標(biāo)的框架對(duì)某種單一聚類算法進(jìn)行優(yōu)化，由于各種聚類算法各具特色，如k-means(K均值)聚類算法適用于各類別樣本量比較均衡的場(chǎng)合，若各類別樣本分布不均，則不適用，此時(shí)，F(xiàn)CM(模糊C均值)可獲得較好效果.因此，結(jié)合FCM和k-means的優(yōu)點(diǎn)，本文提出一種改進(jìn)的多目標(biāo)進(jìn)化聚類算法，該算法以多目標(biāo)進(jìn)化為框架，將FCM以及k-means聚類算法進(jìn)行融合，以初始聚類中心作為迭代自變量，在計(jì)算個(gè)體適應(yīng)度部分加入對(duì)FCM、k-means聚類結(jié)果的重排序操作和排序結(jié)果融合操作，保證聚類結(jié)果的多樣性以及各類別之間的均勻性，并利用當(dāng)代最優(yōu)個(gè)體以及歷史最優(yōu)個(gè)體二次交叉，降低算法運(yùn)行時(shí)間.實(shí)驗(yàn)結(jié)果表明了算法的有效性.

1 多目標(biāo)聚類算法

聚類的效果一般使用如下兩個(gè)指標(biāo)：類內(nèi)距離(Mean Index Adequacy：MIA)、類間距離(Mean of Distance between Curves：MDC).

類內(nèi)距離MIA表示每個(gè)聚類中心和它對(duì)應(yīng)的聚類中的所有樣本特征的距離平均值，MIA數(shù)值越小說(shuō)明類內(nèi)樣本的緊密度越強(qiáng)，聚類效果越好；反之，類內(nèi)樣本的緊密度越低，聚類效果越差，公式如下：

(1)

(2)

其中:c為聚類數(shù)目，Ck表示第c類樣本中包含的特征集合個(gè)數(shù)；ntk表示該集合中的所有特征個(gè)數(shù)；nk表示第k類樣本集中包含的單位數(shù)目；CTk表示第k類樣本集的聚類中心，其中k=1,2,3,…,c.

類間距離MDC表示不同類的聚類中心樣本集之間距離的平均值，MDC數(shù)值越大說(shuō)明類間樣本稀疏性越強(qiáng)，聚類效果越好；反之，類間樣本稀疏性越低，聚類效果越差，計(jì)算如下：

MDC(c)=mean(d(CTk1,CTk2))

(3)

其中：k1和k2分別代表不同的類別，CTk1代表第k1類樣本集的聚類中心，CTk2代表第k2類樣本集的聚類中心，d(Ck1,Ck2)表示第k1類與第k2類樣本集聚類中心的歐氏距離.

目標(biāo)函數(shù)則可定義為下式：

(4)

對(duì)于一個(gè)好的聚類效果，必然滿足MIA(類內(nèi)離散度)足夠小且MDC(類間離散度)足夠大的原則，因此，聚類是一個(gè)多目標(biāo)優(yōu)化問(wèn)題.

2 算法實(shí)現(xiàn)

算法的總體流程圖如圖1所示.

本文算法分為四個(gè)部分，分別為數(shù)據(jù)預(yù)處理、確定聚類數(shù)目、多目標(biāo)進(jìn)化聚類、聚類結(jié)果可視化.

2.1 數(shù)據(jù)預(yù)處理

1)特征重構(gòu)

在特征重構(gòu)部分應(yīng)用譜聚類的特征處理方法，譜聚類是一種基于圖論的聚類方法，通過(guò)對(duì)樣本數(shù)據(jù)的拉普拉斯矩陣特征向量進(jìn)行聚類，達(dá)到對(duì)樣本數(shù)據(jù)聚類的目的.譜聚類可以理解為將高維空間的數(shù)據(jù)映射到低維，然后在低維空間用其他聚類算法(如k-means)進(jìn)行聚類.

算法主要包括相似度矩陣W的計(jì)算、度矩陣D的計(jì)算、拉普拉斯矩陣L的計(jì)算和特征向量的計(jì)算[6].

圖1 算法流程圖

2)數(shù)據(jù)歸一化

在多維度的特征空間中，當(dāng)各指標(biāo)間的水平相差很大時(shí)，需要對(duì)原始指標(biāo)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理.這是因?yàn)椋褐苯佑迷贾笜?biāo)值，將會(huì)突出某維度的特征的作用，相對(duì)削弱其他低維度特征的作用[7-8].

對(duì)特征矩陣進(jìn)行歸一化處理，計(jì)算公式如下：

(5)

2.2 確定聚類數(shù)目

由于傳統(tǒng)的FCM和k-means算法都需要通過(guò)預(yù)設(shè)聚類數(shù)目即聚類中心的個(gè)數(shù)，才能進(jìn)行聚類中心的迭代，所以，在數(shù)據(jù)進(jìn)行預(yù)處理之后，需要確定聚類數(shù)目.本文引入輪廓系數(shù)(SC)作為聚類數(shù)目確定的評(píng)價(jià)指標(biāo).

輪廓系數(shù)是一種結(jié)合類內(nèi)凝聚度和類間分離度的內(nèi)部評(píng)價(jià)指標(biāo)，對(duì)于樣本點(diǎn)i來(lái)說(shuō)，其輪廓系數(shù)的數(shù)值計(jì)算如下[9]：

(6)

其中：a(i)是樣本點(diǎn)i與類內(nèi)所有樣本的歐幾里得距離的平均值；b(i)是樣本點(diǎn)i與最近其他類內(nèi)樣本點(diǎn)歐幾里得距離的最小值，該最小值取值范圍為[-1,1].

因此，對(duì)于整個(gè)樣本集合來(lái)說(shuō)，總體輪廓系數(shù)(SC)的計(jì)算公式為[10-11]：

(7)

其中：n為樣本點(diǎn)總數(shù)，SC數(shù)值越大，則類內(nèi)凝聚度越高，類間分離度越高，反之兩個(gè)指標(biāo)均越低.

通過(guò)預(yù)設(shè)聚類數(shù)目的范圍為[Cmin,Cmax]，分別采用FCM和k-means算法對(duì)[Cmin,Cmax]進(jìn)行聚類求取輪廓系數(shù)的數(shù)值；進(jìn)而確定最優(yōu)的聚類數(shù)目Cbest，計(jì)算公式如下[12]：

(8)

其中：Cmax,FCM、Cmax,k-means分別為FCM和k-means算法在[Cmin,Cmax]內(nèi)求得輪廓系數(shù)最大數(shù)值時(shí)的聚類數(shù)目，round是四舍五入取整符號(hào).

2.3 多目標(biāo)聚類

多目標(biāo)聚類包括初始種群的產(chǎn)生、選擇、交叉、變異和個(gè)體適應(yīng)度計(jì)算.

1)編碼

編碼采用實(shí)數(shù)編碼方式，其中每一個(gè)體都包含m×m個(gè)十進(jìn)制染色體，也即每m個(gè)染色體代表一個(gè)聚類中心歸一化后的數(shù)值，可以是1-m之間的隨機(jī)整數(shù).

2)初始種群的產(chǎn)生

X=

(9)

3)選擇

4)交叉

交叉具體過(guò)程為：利用當(dāng)代的最優(yōu)個(gè)體以及歷史最優(yōu)個(gè)體分別與當(dāng)代其他個(gè)體進(jìn)行二次交叉，形成下一代的新個(gè)體.該部分與傳統(tǒng)交叉不同的是能降低算法搜索次數(shù)，快速找到全局最優(yōu)解.

5)變異

對(duì)某一節(jié)點(diǎn)所屬分類以概率pm隨機(jī)改變，也即：對(duì)于第i個(gè)種群的第j個(gè)個(gè)體的第k個(gè)染色體是否進(jìn)行變異，公式如下：

(10)

6)聚類結(jié)果重編碼

由于傳統(tǒng)聚類算法對(duì)聚類結(jié)果分類標(biāo)簽都是隨機(jī)定值的，如對(duì)6個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)進(jìn)行分類的結(jié)果可能有[1,1,2,2,3,3]或者[2,2,3,3,1,1]，其實(shí)是相同的分類效果，即節(jié)點(diǎn)1、2為一類，節(jié)點(diǎn)3、4為一類、節(jié)點(diǎn)5、6為一類，因此需要提出一種聚類結(jié)果重編碼，對(duì)聚類結(jié)果進(jìn)行規(guī)范化，從節(jié)點(diǎn)1開(kāi)始將其分類標(biāo)簽修正為1，并將其原來(lái)為同一分類標(biāo)簽的節(jié)點(diǎn)變?yōu)?；進(jìn)而隨著節(jié)點(diǎn)號(hào)的增長(zhǎng)將分類標(biāo)簽進(jìn)行步長(zhǎng)為1的修正.如對(duì)于一個(gè)6節(jié)點(diǎn)網(wǎng)絡(luò)，原分類標(biāo)簽為[2,2,3,3,1,1]；則修正后標(biāo)簽為[1,1,2,2,3,3].

7)對(duì)當(dāng)代種群進(jìn)行解碼

首先，將個(gè)體的聚類中心分別輸入FCM和k-means聚類算法進(jìn)行迭代，求得分類結(jié)果并進(jìn)行重編碼.假設(shè)兩個(gè)聚類算法求得分類分別為RCFCM，RCk-means二者皆為1×D的矩陣，D為節(jié)點(diǎn)的數(shù)目，對(duì)于節(jié)點(diǎn)d的類別號(hào)，通過(guò)聚類結(jié)果的融合可以得到融合后的節(jié)點(diǎn)分類類別為：

(11)

然后，用各分類的類內(nèi)樣本計(jì)算聚類中心.進(jìn)而，計(jì)算當(dāng)代各個(gè)體所對(duì)應(yīng)的兩個(gè)目標(biāo)函數(shù)，MIA以及MDC數(shù)值；對(duì)Pareto解進(jìn)行優(yōu)秀個(gè)體的選取.

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

本文實(shí)驗(yàn)機(jī)器CPU為i5-4200H@2.80GHz，內(nèi)存為12GB，分別用UCI數(shù)據(jù)集和人工數(shù)據(jù)集對(duì)算法的聚類有效性進(jìn)行檢驗(yàn).

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

本文選取兩個(gè)外部指標(biāo)對(duì)聚類效果進(jìn)行評(píng)價(jià)，分別是Adjusted Rand Index (Rand) 和Jaccard[13-14].

Rand和Jaccard計(jì)算公式如下：

(12)

(13)

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

3.2.1 聚類數(shù)目確定

選取WINE、X8D5K、HEART、IRIS和VOTE數(shù)據(jù)集作為待聚類的數(shù)據(jù)集[15]，待確定聚類數(shù)目范圍為[2,14]，對(duì)每個(gè)聚類數(shù)目進(jìn)行20次實(shí)驗(yàn)得到輪廓系數(shù)均值，取輪廓系數(shù)最大時(shí)所對(duì)應(yīng)的聚類數(shù)目作為待聚類數(shù)目.通過(guò)實(shí)驗(yàn)，得到的實(shí)驗(yàn)結(jié)果如表1所示.

表1 UCI數(shù)據(jù)集屬性

從表1可知，本文算法得到的最優(yōu)聚類數(shù)目與實(shí)際分類數(shù)目一致.

3.2.2 聚類有效性校驗(yàn)

對(duì)于改進(jìn)的多目標(biāo)進(jìn)化算法，設(shè)置尋優(yōu)的自變量的上下限分別為0、1，算法的種群規(guī)模為100、迭代次數(shù)為200，對(duì)最后一代的Rand和Jaccard進(jìn)行求均值，作為該數(shù)據(jù)的聚類的外部評(píng)價(jià)指標(biāo).

表2 UCI數(shù)據(jù)集聚類有效性

從表2可知，總體來(lái)說(shuō)，本文算法能有效實(shí)現(xiàn)UCI數(shù)據(jù)集的聚類.

3.3 人工數(shù)據(jù)集

3.3.1 聚類數(shù)目確定

選取TWOMOONS、TWO CLUSTER、THREECIRCLES、THREE CLUSTER、SPIRAL和SPIRAL_UNBALANCE數(shù)據(jù)集作為待聚類的數(shù)據(jù)集，待確定聚類數(shù)目范圍為[2,14]，對(duì)每個(gè)聚類數(shù)目進(jìn)行20次實(shí)驗(yàn)得到輪廓系數(shù)均值，取輪廓系數(shù)最大時(shí)所對(duì)應(yīng)的聚類數(shù)目作為待聚類數(shù)目.通過(guò)實(shí)驗(yàn)，得到實(shí)驗(yàn)結(jié)果如表3所示.

表3 人工數(shù)據(jù)集屬性

從表3可知，本文算法得到的最優(yōu)聚類數(shù)目與實(shí)際分類數(shù)目一致.

3.3.2 聚類有效性校驗(yàn)

對(duì)于改進(jìn)的多目標(biāo)進(jìn)化算法，設(shè)置尋優(yōu)的自變量上下限分別為0、1，算法種群規(guī)模為800、迭代次數(shù)為200，對(duì)最后一代的Rand和Jaccard進(jìn)行求均值，作為該數(shù)據(jù)的聚類的外部評(píng)價(jià)指標(biāo).

表4 人工數(shù)據(jù)集聚類有效性

從表4可知，總體來(lái)說(shuō)，本文算法能有效實(shí)現(xiàn)人工數(shù)據(jù)集的聚類，但對(duì)于流行圖形的聚類效果還不夠理想.

4 結(jié) 語(yǔ)

本文提出一種多目標(biāo)進(jìn)化的聚類算法，該算法以多目標(biāo)進(jìn)化為框架，將FCM、k-means聚類算法進(jìn)行融合，設(shè)計(jì)了改進(jìn)的進(jìn)化算法.實(shí)驗(yàn)結(jié)果表明了算法的有效性.