基于多目標進化的聚類實現

汪 宏 海

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

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

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

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

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

1 多目標聚類算法

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

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

(1)

(2)

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

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

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

(3)

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

目標函數則可定義為下式：

(4)

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

2 算法實現

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

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

2.1 數據預處理

1)特征重構

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

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

圖1 算法流程圖

2)數據歸一化

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

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

(5)

2.2 確定聚類數目

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

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

(6)

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

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

(7)

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

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

(8)

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

2.3 多目標聚類

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

1)編碼

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

2)初始種群的產生

X=

(9)

3)選擇

4)交叉

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

5)變異

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

(10)

6)聚類結果重編碼

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

7)對當代種群進行解碼

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

(11)

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

3 實驗分析

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

3.1 評價指標

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

Rand和Jaccard計算公式如下：

(12)

(13)

3.2 UCI數據集

3.2.1 聚類數目確定

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

表1 UCI數據集屬性

從表1可知，本文算法得到的最優聚類數目與實際分類數目一致.

3.2.2 聚類有效性校驗

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

表2 UCI數據集聚類有效性

從表2可知，總體來說，本文算法能有效實現UCI數據集的聚類.

3.3 人工數據集

3.3.1 聚類數目確定

選取TWOMOONS、TWO CLUSTER、THREECIRCLES、THREE CLUSTER、SPIRAL和SPIRAL_UNBALANCE數據集作為待聚類的數據集，待確定聚類數目范圍為[2,14]，對每個聚類數目進行20次實驗得到輪廓系數均值，取輪廓系數最大時所對應的聚類數目作為待聚類數目.通過實驗，得到實驗結果如表3所示.

表3 人工數據集屬性

從表3可知，本文算法得到的最優聚類數目與實際分類數目一致.

3.3.2 聚類有效性校驗

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

表4 人工數據集聚類有效性

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

4 結 語

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