基于精英集的多目標差分進化聚類算法*

張明珠，曹 杰，王 斌

(南京財經大學信息工程學院，江蘇 南京 210023)

1 引言

聚類技術是數據挖掘中的一種重要工具并被廣泛應用在諸如信息檢索、文本挖掘、圖像處理和數據分析等領域[1 - 5]。作為一種無監督的學習問題，聚類將未被標記過的數據基于相似性或差異性劃分成多個小組，使得同一小組內的對象盡可能相似，不同組間的對象盡可能相異[6]。一些聚類問題根據用戶經驗或領域知識可提前知道要劃分成多少類，但實際情況中很難獲取準確的聚類數。高估或低估聚類數都會損害聚類結果的質量，因此識別最佳聚類數是聚類分析中一個基本的問題。

對不知道聚類數的聚類問題，一種直接的思路是試錯法(Trial-and-error)。首先獲得每一種可能的聚類數的聚類結果，再按某種評價標準從眾多結果中挑選一個最合適的聚類解[7]，并且不同選擇標準獲得的最佳聚類數可能不同。為了獲得多個不同聚類數的聚類結果，很多方法重復運行某個聚類算法，每次固定一個不同的聚類數[8]。這類方法簡單易實施，但需多次運行，尤其當數據集較大或聚類數很多時，效率十分低下。如何更高效地獲得不同聚類數的聚類結果同時保證每種聚類結果的質量，考慮到在同時優化具有多個相互矛盾或沖突的目標的問題時，不同于單目標優化問題只能獲得一個最優解，基于種群的多目標進化算法可以得到一個包含多個近似最優解的解集。因此，本文嘗試用多目標進化算法來同時得到多個不同聚類數的劃分結果。

實際生活中很多問題需要同時優化具有多個相互矛盾或沖突的目標，不存在一個可行解使這些目標同時達到最優，這樣的優化問題被稱作多目標優化問題MOP(Multi-objective Optimization Problem)[9,10]。不失一般性，對于一個需要同時最小化m個目標的優化問題，其數學表達式為：

minx∈ΩF(x)=(f1(x),f2(x),…,fm(x))

(1)

其中，x=(x1,x2,…,xb)∈Rb是一個b維的決策變量，Ω是包含所有可行解的解空間。目標函數F(x)定義了m個由決策空間向目標空間映射的函數。令x,y∈Ω，如果對所有的i∈{1,2,…,m},有fi(x)≤fi(y),且至少存在一個i使得fi(x)

聚類算法多通過最大化類內的緊致性和類間的分離性來獲得高質量的聚類[12]，然而聚類數與這2個目標有一定的沖突，即聚類數大的時候類間的分離性會變差，而聚類數小的時候類內的緊致性會減弱，選擇合適的聚類數其實是在聚類數與類內緊致性和類間分離性的平衡中選擇一個滿意的折衷方案，從這一角度來說，從眾多不同聚類數的聚類中選擇一個聚類結果是一個多目標優化問題。聚類數作為一個能夠反映數據結構的重要指標，本文直接將其作為一個優化目標，同時以優化聚類結果緊致性為例將各數據點到其聚類中心的平方距離的總和SSD(Sum of Squared Distance)作為另一個優化目標，將不知道聚類數的聚類問題轉換為一個多目標優化問題來解決。以這2個指標為優化目標的多目標優化問題的PS中包含所有不同聚類數的聚類結果，且對優化類內緊致性來說，每種聚類數的聚類結果質量都達到全局最優。差分進化算法在很多文獻中已經被證明具有良好的性能[13 - 15]，因此，針對聚類數不確定的聚類問題，本文提出一個多目標差分進化EDEMC(Elitist-archive-based Differential Evolutionary algorithm to Multi-objective Clustering)算法同時優化2個聚類指標，以得到不同聚類數的聚類結果。

本文的主要貢獻在于：

(1)定義了一個新的精英集來保存每一種聚類數的歷史最優聚類結果并使之參與種群的差分進化；

(2)設計了新的重組算子，對子代進行局部搜索和修復；

(3)提出了一種補充策略提高種群的多樣性。

2 相關工作

對于一個多目標進化聚類算法，一條染色體往往代表了一個完整的聚類解。多目標進化聚類算法的一般流程是[16]：(1)選擇一個合適的編碼方式表示聚類結果，初始化種群；(2)選擇多個聚類有效性指標作為優化目標；(3)設計合適的進化操作方式，包括選擇、交叉和變異；(4)使用有效的環境選擇方式維持種群的收斂性和多樣性；(5)從Pareto最優解集中挑選一條最優染色體解碼為聚類的結果。

不同于聚類數已知的聚類問題，Handl等人[17]提出了一種自動確定聚類數并得到該聚類數的聚類結果的多目標進化聚類算法。該算法用一種Locus-based Adjacency Graph的編碼方式表示聚類結果，染色體長度等于數據點的個數n，每一個基因位上的值是[1,n]中的一個整數，如果基因位i上的值是j，則表示數據點i和數據點j有聯系，這2個數據點歸為同一類。Wikaisuksakul[18]在初始化種群時，對每條染色體從給定的聚類數的范圍中隨機選擇一個作為其有效的聚類數并依此對聚類中心編碼，即若數據點維度是d，染色體的聚類數是K*，那么該條染色體的長度為d*K*。?zyer等人[19]在初始化時對每一條染色體在給定聚類數的范圍中隨機選取一個整數K*作該染色體的聚類數，因為采用基于標簽的染色體編碼方式，所以染色體上每個基因位的值代表類標簽，基因位的取值為[1,K*]中的隨機整數，代表了該基因位對應數據點所屬的類。上述3種方式求得的Pareto解集都包含了多個不同聚類數的聚類解，但可能不包含范圍內所有聚類數的解，甚至缺少真實聚類數的聚類解，導致從種群中選擇最佳聚類數的聚類結果時產生偏差。于是，Wang等人[20]將聚類數K設為優化目標，將各個數據點到其聚類中心的平方距離的和設為另一個優化目標，但對平方距離和的目標函數進行了轉換，保證2個優化目標之間絕對沖突，使代表不同聚類數的染色體的目標向量之間互不支配，這樣在基于非支配排序和擁擠度的環境選擇中各K值均至少有一條染色體被選中并遺傳到下一代，使得Pareto解集中每一個K都有染色體存在。但是，因未考慮對無效簇的處理，即某些聚類中心沒有任何數據點附屬,染色體代表的聚類數是不真實的，因此實際的解集中可能有些聚類結果是缺失的。本文所提算法在進化過程中不僅對不合法的染色體進行修復，使每一條染色體被賦予的聚類數都是真實、有效的，還在種群缺少任意一個聚類數K對應的染色體時，生成新的優良染色體補充到種群中，提高種群的多樣性。

進化算法中精英集的提出主要是為了提高算法的收斂速度[21]，如文獻[22]提出用保存了優良染色體的外部種群(External Population)參與每一代進化，將父輩與外部集組合到一起后通過比較支配強度賦予染色體適應度，挑選支配性更強的染色體參與繁殖。精英集也被用于保持種群的多樣性。文獻[23]創建了2個檔案(Archive)分別用于維持種群的收斂性和多樣性，并且2個檔案采用不同的進化操作以更好地實現各自的功能。本文算法中的精英集針對本文待解決問題的特點，保存每一個聚類數K對應的歷史最優聚類解，利用精英集補充種群中缺失的K值的染色體，增加種群的多樣性；另外，精英集參與差分進化生成新染色體，使更多有利基因片段遺傳到下一代，促進種群快速收斂。

3 基于精英集的多目標差分進化聚類算法

本文提出的基于精英集的多目標差分進化聚類算法EDEMC的主要流程如算法1所示。

算法1基于精英集的多目標差分進化聚類算法EDEMC

輸入：數據集Data，最小聚類數Kmin，最大聚類數Kmax，種群規模N，最大迭代次數maxGen，交叉概率CR，縮放因子F。

輸出：精英集E。/*E中含有每一種聚類數的近似最優聚類結果*/

步驟1初始化種群P和精英集E，每一條染色體代表一個聚類數K的聚類解；

步驟2主循環：

(1)用二進制錦標賽的方式從P中選擇N條染色體組成交配池MatingPool；

(2)利用DEbest遺傳操作生成子代Q。具體地，對MatingPool中每一條染色體si,i=1,2,…,N:

①用式(5)的方式生成變異染色體vi;

②對vi按式(6)生成交叉染色體ui;

③利用one-step-K-means對ui進行局部搜索，并修復ui的有效聚類數，生成染色體qi。

(3)依據非支配排序和擁擠度對集合{P,Q}進行環境選擇，生成過渡種群P′；

(4)Supplement(P′,E,Data),檢查P′是否含有給定范圍內每一個聚類數的聚類解，若存在缺失，利用精英集對之進行補充；

(5)精英集E和種群P′互相更新每一個K的最優聚類結果，將更新后的P′賦值給P作為下一代的父輩；

(6)是否滿足停止條件，若未滿足，返回(1)。

算法2Supplement// 檢查并補充染色體

輸入：過渡種群P′，精英集E，數據集Data。

輸出：過渡種群P′。

步驟1檢查過渡種群P′中是否含有所有聚類數K對應的聚類結果，缺失的聚類數的值組成集合lostK；

步驟2補充種群P′中缺失的K的染色體，對每一個K∈lostK：

(1)找到精英集E中K-1對應的聚類解，解碼，拆分其中最為分散的一個簇，生成新的染色體，記為s1；

(2)找到精英集E中K+1對應的聚類解，解碼，合并最相近的2個類簇中更分散的一個簇，生成新的染色體，記為s2；

(3)比較精英集E中K對應的聚類解與染色體s1、s2的支配性，將更優的染色體添加到P′中，若三者互不支配則隨機選擇。

算法的目標是獲得所給范圍[Kmin,Kmax]內所有聚類數K對應的聚類結果，Kmax和Kmin是用戶給定的聚類數K的上下界，從而生成2個優化目標——最小化聚類數K和類內平方距離和SSD——的Pareto最優解集，2個目標函數的計算方式如式(2)和式(3)所示：

(2)

f2=K*

(3)

其中，K*是當前染色體代表的聚類解的有效聚類數。ck是類Ck的中心，類中心的計算方式見式(4)，|Ck|是類Ck包含的數據點的總數。pi∈Rd是一個屬于類Ck的d維數據點。distance(x,y)是一個計算數據點x與數據點y之間距離的函數，本文采用歐氏距離。聚類過程中將每個數據點劃歸到與之距離最近的一個簇中，數據點與類的距離按數據點到類中心的距離計算。

(4)

3.1 初始化

進化算法一般將種群表示為一個矩陣，一個N*n的矩陣表示種群含有N條染色體，每條染色體長度為n。本文采用實數編碼的方式將聚類中心編碼進染色體，具體編碼方式可參考圖1。其中，染色體長度統一為n=d*Kmax，d為數據點的維度，Kmax是最大聚類數，K*是染色體代表的聚類解的有效聚類數，ci,j表示聚類中心ci的位置坐標的第j個元素。染色體中前d個基因位上的值是第1個聚類中心的位置坐標，接下來的d個基因位上的值是第2個聚類中心的位置坐標，以此類推。每一條染色體被隨機賦予一個[Kmin,Kmax]中的整數K*作為真實的聚類數，即只有前d*K*個基因位上的值是該染色體對聚類中心真實有效的編碼。

算法首先隨機初始化一個包含多條染色體的種群，代表了對問題的多種解。隨機初始化能夠增加種群的多樣性，提高種群的搜索能力。本文初始化種群時需要使每一個聚類數K至少有一個解存在，另外為了使染色體合法，即每一個類至少有一個數據點附屬，對每一條染色體，從數據集中隨機選擇Kmax個不同的數據點作為聚類中心，然后結合染色體實際的K*值，計算染色體的目標向量。

Figure 1 Encoding scheme of chromosome圖1 染色體編碼示意圖

精英集的大小為(Kmax-Kmin+1)，用于保存目前為止所得染色體中每一種聚類數K對應的最優染色體。初始化時找到種群P中不同K對應的所有染色體，并從中挑選SSD值最小的染色體作為該K值的最優解保存到E中。

3.2 重組和擇優

利用二進制錦標賽的方式從P中挑選N條染色體組成交配池MatingPool。詳細操作可參考NSGA-II(Nondominated Sorting Genetic Algorithm-II)[24]。對MatingPool中的每一條染色體用類似DE/current to best/1[25]的方式生成后代，該操作記作DEbest。首先按式(5)生成變異染色體vi，si是待操作的父體，sbest是與si具有相同真實聚類數K*的歷史最優染色體，即E中K*對應的染色體。sr1和sr2是從P中隨機選擇的2個不相同的染色體。參數縮放因子F∈(0,2]。

vi=si+F*(sbest-si)+F*(sr1-sr2)

(5)

變異后，用式(6)生成交叉后的染色體ui=(ui,1,ui,2,…,ui,n)，n=Kmax*d。

j=1,2,…,n

(6)

其中，CR是交叉概率；rand是一個[0,1]的隨機數；jrand是一個[1,n]的隨機整數，用于保證ui和si至少有一個基因位不同。

新生成染色體的聚類數K值從其父代遺傳。生成ui后，根據其K值，即si的K*值，解碼ui得到聚類中心，依據劃分結果用one-step-K-means[19]局部搜索，更新一次聚類中心(如式(4)所示)，刪去無效中心后得到新染色體qi并計算優化目標值。對MatingPool中每一條染色體進行上述操作后生成Q={q1,q2,…,qN}。對[P,Q]用文獻[24]中的方式進行環境選擇選出N條優良染色體組成過渡種群P′。

3.3 檢查并補充K

為保證每一個聚類數K在種群中都存在聚類解，有機會參與進化和交換信息，首先檢查在過渡種群P′中是否每一個K值都有對應的解存在，若存在缺失，則利用精英集中的染色體生成新染色體補充到P′中，生成新種群P。生成新染色體時主要采用的思想是合并與拆分，有很多文獻[7,26]展示了該方式對提高聚類結果質量的促進作用。補充K后生成的種群P大小不固定，但不小于N。

首先，根據過渡種群P′中所有染色體對應的聚類解的聚類數，找出缺少的聚類數K。對每一個缺失的K值，從精英集E中找到其前后K值對應的聚類解的染色體，即代表了聚類數為K-1和K+1的聚類解的染色體，分別記為e(K-1)和e(K+1)。將e(K-1)中最分散的類拆分成2個，增加1個類；將e(K+1)中距離最近的2個類中更分散的類中的數據點合并到其它簇中，減少1個類。比較產生的新的聚類結果(染色體)是否優于(支配)精英集E中K對應的染色體e(K)，若是，則將e(K)替換成更優的染色體。最后將e(K)添加到P′中。

每個類的分散程度用該類中所有數據點到聚類中心的平方距離和的均值衡量，即：

(7)

類之間的距離用聚類中心間的歐氏距離度量，即類Ci和類Cj的距離為：

distance(Ci,Cj)=distance(ci,cj)=

(8)

拆分過程中將最分散的類拆開。挑選該類中離簇中心最遠的數據點和離簇中心最近的數據點作為新的聚類中心，刪去該簇的初始中心，將該簇中剩余的數據點依據新生成的2個中心重新劃分。劃分結果用one-step-K-means方法更新一次聚類中心后，將新的聚類中心編碼到染色體中，依此生成新染色體替換原來的染色體。合并過程中首先找到距離最近的2個類，將更分散的類中的數據點根據數據點到其它聚類中心的遠近分配至距離最近的簇中，隨后同樣用one-step-K-means方法更新一次聚類中心，將新聚類中心編碼生成染色體替換原染色體。需要注意的是，拆分與合并的方式不止這一種，本文采用此種方法一方面是因為在多次迭代過程中具體的操作方式對種群整體的表現影響不大，另一方面是可以減少對距離的計算。

3.4 更新精英集

3.5 時間復雜度

對于本文提出的EDEMC算法，其時間復雜度分析如下：在每一次迭代中，時間復雜度由2個部分組成：第1部分是環境選擇中的非支配排序和擁擠度計算，其時間復雜度為O(mN2)；第2部分是計算染色體的優化目標和劃分聚類，該過程中需要計算距離，時間復雜度為O(NNdataKmaxd)。其中m為優化的目標數，N為種群的染色體數，Ndata為數據集中數據點的個數，Kmax為最大聚類數，d是數據點的維度。因此，當算法迭代次數為maxGen時，算法總的時間復雜度為O(maxGen*(mN2+NNdataKmaxd))。

4 實驗結果與分析

本節對本文算法進行驗證和分析。實驗主要分為3個部分，第1部分用于分析算法總體的表現，以及驗證算法中一些關鍵操作對算法性能的提升作用。為了評估本文算法聚類結果的收斂性，即聚類結果的類內緊致性，第2部分將本文算法與GKA(Genetic K-means Algorithm)[27]進行比較。第3部分主要為了驗證算法是否能夠有效獲得多種不同聚類數的聚類結果，將所提算法與MOKGA(Multi-objective K-means Genetic Algorithm)[19]和EMO-KC(Evolutionary Multi-objective Optimization K Clustering)[20]算法進行對比，這里將MOKGA中同樣反映聚類結果緊致性的優化目標TWCV(Total Within-Cluster Variance)改為SSD，以便于比較。

本文采用調整的蘭特指數ARI(Adjusted Rand Index)和聚類準確性CA(Clustering Accuracy)[12]作為評價指標。ARI通過統計正確決策的樣本對數來評價算法性能，CA比較預測結果與真實結果的一致性來評價聚類準確度。2個指標取值均在[0,1]，值越大表示聚類效果越好。

4.1 實驗設置

實驗數據集包括3個模擬生成的二維數據集(https://personalpages.manchester.ac.uk/staff/Julia.Handl/generators.htm)和UCI(http://archive.ics.uci.edu/ml/index.php)中的5個真實數據集。模擬數據集均包含1 000個維度為2的數據點，且數據集中數據點可劃分為4個類簇。真實數據集的大小各不相同，最大的數據集Breast Cancer Wisconsin包含569個數據點，數據點的維度高達30。各數據集的具體信息如表1所示。在各進化聚類算法的最大迭代次數的參數設置中，對模擬數據集設置的值均為500，對真實數據集中數據維度為13及以下的數據集設置的值為1 000，而對數據集Breast Cancer Wisconsin設置的值為2 000。聚類數的取值設為[2,20]，種群大小N=100，EDEMC中交叉概率CR=0.9，縮放因子F=0.3。算法GKA、EMO-KC和MOKGA中的其它參數使用各自原文中推薦的值。各數據集的具體信息如表1所示。實驗在CPU為3.6 GHz，RAM為16 GB的Windows 10操作系統上進行。

Table 1 Features of experimental datasets表1 實驗數據集的特性

4.2 EDEMC的總體表現

為了簡要展示算法的聚類效果，從每一個數據集的一系列聚類解中選擇已知的正確聚類數對應的解為例進行說明。表2是各算法在所有數據集的真實聚類數上所得聚類結果的SSD、ARI和CA。

從表2中可以看到，在全部8個數據集上，EDEMC算法在7個數據集上得到的聚類結果的SSD不大于其它算法的，4個數據集上的ARI不小于其它算法的，6個數據集上的CA不小于其它算法的。綜合來看，EDEMC在大部分數據集上都能夠獲得良好的聚類結果。

在維持其它操作不變的情況下，將EDEMC中補充聚類數的聚類解的過程替換為直接從精英集中將聚類數K對應的個體加入到當前種群的方式，記該算法為EDEMC1；將EDEMC中DEbest操作修改為模擬二進制交叉和多項式變異，交叉概率為0.9，變異概率為1/n，n為染色體的長度，分布指數均為20，記該算法為EDEMC2。各算法的其它參數按照前文進行設置。在數據集Square4上運行EDEMC1、EDEMC2和EDEMC各10次，對所得結果取平均值，結果如圖2所示，EDEMC的Pareto前沿在EDEMC1和EDEMC2的Pareto前沿的下方，即在相同聚類數的情況下，EDEMC聚類結果的SSD小于EDEMC1和EDEMC2聚類結果的，這表明了填補策略中拆分-合并操作和DEbest操作的有效性。

Table 2 SSD,ARI and CA of clustering results of each compared algorithm on datasets under their true number of clusters表2 真實聚類數下各算法在數據集上的聚類結果的SSD，ARI和CA

Figure 2 PF of EDEMC,EDEMC1 and EDEMC2 on dataset Square4圖2 EDEMC、EDEMC1和EDEMC2 在數據集Square4上所得的PF

4.3 EDEMC與GKA的對比

因為GKA算法假設聚類數已知，需要將之作為算法的輸入參數，對每一個K∈[Kmin,Kmax]，GKA均需運行一次。為公平比較運行時間，對每一個K值，GKA的最大迭代次數為小于maxGen/(Kmax-Kmin+1)的最大整數，如此GKA獲得所有K值的聚類結果所用的迭代次數將不大于EDEMC運行一次所用的最大迭代次數。這里選取數據集Iris進行實驗。圖3是EDEMC與GKA算法的實驗結果，包括實驗所得的K與SSD的結果以及對應K的ARI值。可以觀察到，EDEMC運行一次與GKA運行多次后的結果均涵蓋了每一個K值的劃分，并且對每一個K，兩者的類內平方距離和近似，ARI互有優劣，這表明本文算法在同時優化2個目標的情況下得到的聚類效果不比全力優化其中一個目標得到的聚類效果差。表3所示是各算法總的運行時間，從中可以看到，在相同或更少的總迭代次數下，GKA的運行時間遠遠大于EDEMC的，主要是因為GKA需要多次運行才能得到各種聚類數的聚類結果，并且GKA中每次變異都需要計算各變異點到聚類中心的距離，增加了計算時間，尤其當數據點較多或數據維度較高時，距離計算非常耗時，如數據集大小為(150,4)的Iris，GKA的用時約為EDEMC的5倍，而在大小為(1 000,2)的數據集Square1上，GKA的用時增長為EDEMC的15倍左右。

Figure 3 Experimental results of EDEMC and GKA on dataset Iris圖3 EDEMC和GKA在數據集Iris上的實驗結果

Table 3 Running time of each algorithm

4.4 EDEMC與MOKGA、EMO-KC的對比

以真實數據集Iris、Glass和模擬數據集Square4上的實驗為例，圖4是EDEMC、MOKGA和EMO-KC算法的實驗結果。只考慮算法最終所得解集中分別保留了多少個不同聚類數的解時(這在本文中反映了種群的多樣性)，從圖4中可以觀察到，MOKGA算法所得聚類解集對應的PF多處有斷裂，意味著缺少很多聚類數K對應的聚類解；EMO-KC算法對應的PF分散性較好，在大部分數據集上只在線段尾端發生殘缺，說明EMO-KC在這些數據集上缺少較大聚類數的聚類解。本文所提EDEMC算法所得聚類解集的PF對應的線段連貫、完整，說明其多樣性最好。

整體而言，EMO-KC算法的多樣性優于MOKGA算法，但EMO-KC和MOKGA都可能存在缺失的聚類數，分析原因如下。雖然EMO-KC算法中設計的優化目標函數使得不同聚類數的染色體間互不支配，環境選擇過程中這些非支配解也會被保留，但因為遺傳操作的隨機性，會有聚類中心沒有任何染色體附屬，即存在空簇，去掉無效的聚類中心后染色體實際的聚類數目會少于K，便可能導致最終輸出中沒有該聚類數對應的聚類結果。本文算法會檢查是否存在無效的聚類中心，并且刪去空簇后會修正染色體的實際聚類中心和聚類數K，如果種群丟失了某些K的聚類解，則利用精英集補充種群中缺失K的聚類解，因此不同大小的K都有染色體參與進化，精英集中染色體的聚類數目都是真實有效的。MOKGA算法采用標簽編碼，不存在無效簇，但變異使得染色體的聚類數K動態變化，并傾向于越來越小，尤其當數據集的真實聚類數較大時，初始階段的進化過程中可能會將具有真實聚類數的染色體淘汰掉。MOKGA輸出的PS中可能具有多個不同K的聚類解，但不能保證每一個K值都有染色體存活到最后，也就是說同樣會存在丟失聚類數的聚類結果的情況。

EDEMC算法不僅能夠一次性給出給定范圍內所有聚類數K的聚類結果，且聚類結果的質量較高。實驗顯示，EDEMC的類內平方距離和SSD均小于或等于EMO-KC和MOKGA算法聚類結果的。在圖4中表現為，EMO-KC的PF對應的線段位于EDEMC的PF對應的線段的上方，而MOKGA解集的PF對應的線段遠在兩者的上方。總體而言，在解集的分布性和收斂性2方面本文所提EDEMC算法均為最優。

運行效率方面，因為MOKGA算法中采用基于距離的變異和one-step-K-means操作，因距離計算耗時的原因導致MOKGA在3者中用時最長；EDEMC算法中同樣用到了one-step-K-means，并且當種群中不存在某個聚類數K的聚類解時，為生成該K的聚類解需要對類簇進行拆分和合并，也需多次計算距離，因此EDEMC的運行時間略長于EMO-KC算法的。

Figure 4 Experimental results of EDEMC,EMO-KC and MOKGA on real-world datasets Iris, Glass, and synthetic dataset Square4圖4 EDEMC、EMO-KC和MOKGA在真實數據集 Iris、Glass和模擬數據集Square4上的實驗結果

5 結束語

不同于現有的通過重復運行從而獲得多個不同聚類數的聚類結果的算法，本文將聚類作為一個多目標優化問題同時最小化聚類數K和類內平方距離和SSD，通過新的多目標差分進化算法一次性獲得多種聚類數的聚類解。算法創建并維持一個保存了各個聚類數的歷史最優結果的精英集，通過新的遺傳操作和補充策略讓種群迭代優化，最后輸出各個聚類數K的近似最優聚類結果組成的Pareto解集，獲得多個不同的聚類數與類內平方距離和的平衡。實驗表明了所提算法的有效性，以及補充策略和差分進化對算法性能的提升。與GKA、MOKGA和EMO-KC算法在多個模擬數據集和真實數據集上的對比實驗表明，本文所提算法不僅能在較少的時間內獲得分布更廣的Pareto解集，并且所得的解具有良好的收斂性——這里表現為具有更小的SSD。

本文算法給出了多個K值的聚類結果的可選項，未來將研究如何充分利用Pareto解集的信息從中得到最終的聚類。另外，本文算法的優化目標是用盡可能少的聚類數使類內平方距離和最小，可以考慮引入更多能夠反映不同數據結構特性的優化目標，當優化3個以上的目標時可用類似文獻[28]中的算法對超多目標的優化問題進行優化。最后，當處理大樣本或高維數據時，面對快速增長的搜索空間，可嘗試用大規模多目標優化算法[29]實現多目標聚類。