汪 宏 海

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

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

進化算法適合求解復雜、非線性的問題，多目標進化是采用進化計算的方法對多目標優(yōu)化問題進行求解.由于多目標優(yōu)化問題通常是復雜、非線性的，因此，多目標進化算法非常適合求解這類問題.

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

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

1 多目標聚類算法

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

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

(1)

(2)

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

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

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

(3)

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

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

(4)

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

2 算法實現(xiàn)

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

本文算法分為四個部分，分別為數(shù)據(jù)預處理、確定聚類數(shù)目、多目標進化聚類、聚類結果可視化.

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

1)特征重構

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

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

圖1 算法流程圖

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

在多維度的特征空間中，當各指標間的水平相差很大時，需要對原始指標數(shù)據(jù)進行標準化處理.這是因為：直接用原始指標值，將會突出某維度的特征的作用，相對削弱其他低維度特征的作用[7-8].

對特征矩陣進行歸一化處理，計算公式如下：

(5)

2.2 確定聚類數(shù)目

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

輪廓系數(shù)是一種結合類內(nèi)凝聚度和類間分離度的內(nèi)部評價指標，對于樣本點i來說，其輪廓系數(shù)的數(shù)值計算如下[9]：

(6)

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

因此，對于整個樣本集合來說，總體輪廓系數(shù)(SC)的計算公式為[10-11]：

(7)

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

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

(8)

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

2.3 多目標聚類

多目標聚類包括初始種群的產(chǎn)生、選擇、交叉、變異和個體適應度計算.

1)編碼

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

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

X=

(9)

3)選擇

4)交叉

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

5)變異

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

(10)

6)聚類結果重編碼

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

7)對當代種群進行解碼

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

(11)

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

3 實驗分析

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

3.1 評價指標

本文選取兩個外部指標對聚類效果進行評價，分別是Adjusted Rand Index (Rand) 和Jaccard[13-14].

Rand和Jaccard計算公式如下：

(12)

(13)

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

3.2.1 聚類數(shù)目確定

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

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

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

3.2.2 聚類有效性校驗

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

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

從表2可知，總體來說，本文算法能有效實現(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]，對每個聚類數(shù)目進行20次實驗得到輪廓系數(shù)均值，取輪廓系數(shù)最大時所對應的聚類數(shù)目作為待聚類數(shù)目.通過實驗，得到實驗結果如表3所示.

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

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

3.3.2 聚類有效性校驗

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

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

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

4 結 語

本文提出一種多目標進化的聚類算法，該算法以多目標進化為框架，將FCM、k-means聚類算法進行融合，設計了改進的進化算法.實驗結果表明了算法的有效性.