張明珠，曹 杰，王 斌

(南京財(cái)經(jīng)大學(xué)信息工程學(xué)院，江蘇 南京 210023)

1 引言

聚類技術(shù)是數(shù)據(jù)挖掘中的一種重要工具并被廣泛應(yīng)用在諸如信息檢索、文本挖掘、圖像處理和數(shù)據(jù)分析等領(lǐng)域[1 - 5]。作為一種無監(jiān)督的學(xué)習(xí)問題，聚類將未被標(biāo)記過的數(shù)據(jù)基于相似性或差異性劃分成多個(gè)小組，使得同一小組內(nèi)的對(duì)象盡可能相似，不同組間的對(duì)象盡可能相異[6]。一些聚類問題根據(jù)用戶經(jīng)驗(yàn)或領(lǐng)域知識(shí)可提前知道要?jiǎng)澐殖啥嗌兕?，但?shí)際情況中很難獲取準(zhǔn)確的聚類數(shù)。高估或低估聚類數(shù)都會(huì)損害聚類結(jié)果的質(zhì)量，因此識(shí)別最佳聚類數(shù)是聚類分析中一個(gè)基本的問題。

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

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

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

(1)

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

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

本文的主要貢獻(xiàn)在于：

(1)定義了一個(gè)新的精英集來保存每一種聚類數(shù)的歷史最優(yōu)聚類結(jié)果并使之參與種群的差分進(jìn)化；

(2)設(shè)計(jì)了新的重組算子，對(duì)子代進(jìn)行局部搜索和修復(fù)；

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

2 相關(guān)工作

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

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

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

3 基于精英集的多目標(biāo)差分進(jìn)化聚類算法

本文提出的基于精英集的多目標(biāo)差分進(jìn)化聚類算法EDEMC的主要流程如算法1所示。

算法1基于精英集的多目標(biāo)差分進(jìn)化聚類算法EDEMC

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

輸出：精英集E。/*E中含有每一種聚類數(shù)的近似最優(yōu)聚類結(jié)果*/

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

步驟2主循環(huán)：

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

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

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

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

③利用one-step-K-means對(duì)ui進(jìn)行局部搜索，并修復(fù)ui的有效聚類數(shù)，生成染色體qi。

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

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

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

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

算法2Supplement// 檢查并補(bǔ)充染色體

輸入：過渡種群P′，精英集E，數(shù)據(jù)集Data。

輸出：過渡種群P′。

步驟1檢查過渡種群P′中是否含有所有聚類數(shù)K對(duì)應(yīng)的聚類結(jié)果，缺失的聚類數(shù)的值組成集合lostK；

步驟2補(bǔ)充種群P′中缺失的K的染色體，對(duì)每一個(gè)K∈lostK：

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

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

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

算法的目標(biāo)是獲得所給范圍[Kmin,Kmax]內(nèi)所有聚類數(shù)K對(duì)應(yīng)的聚類結(jié)果，Kmax和Kmin是用戶給定的聚類數(shù)K的上下界，從而生成2個(gè)優(yōu)化目標(biāo)——最小化聚類數(shù)K和類內(nèi)平方距離和SSD——的Pareto最優(yōu)解集，2個(gè)目標(biāo)函數(shù)的計(jì)算方式如式(2)和式(3)所示：

(2)

f2=K*

(3)

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

(4)

3.1 初始化

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

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

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

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

3.2 重組和擇優(yōu)

利用二進(jìn)制錦標(biāo)賽的方式從P中挑選N條染色體組成交配池MatingPool。詳細(xì)操作可參考NSGA-II(Nondominated Sorting Genetic Algorithm-II)[24]。對(duì)MatingPool中的每一條染色體用類似DE/current to best/1[25]的方式生成后代，該操作記作DEbest。首先按式(5)生成變異染色體vi，si是待操作的父體，sbest是與si具有相同真實(shí)聚類數(shù)K*的歷史最優(yōu)染色體，即E中K*對(duì)應(yīng)的染色體。sr1和sr2是從P中隨機(jī)選擇的2個(gè)不相同的染色體。參數(shù)縮放因子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是一個(gè)[0,1]的隨機(jī)數(shù)；jrand是一個(gè)[1,n]的隨機(jī)整數(shù)，用于保證ui和si至少有一個(gè)基因位不同。

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

3.3 檢查并補(bǔ)充K

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

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

每個(gè)類的分散程度用該類中所有數(shù)據(jù)點(diǎn)到聚類中心的平方距離和的均值衡量，即：

(7)

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

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

(8)

拆分過程中將最分散的類拆開。挑選該類中離簇中心最遠(yuǎn)的數(shù)據(jù)點(diǎn)和離簇中心最近的數(shù)據(jù)點(diǎn)作為新的聚類中心，刪去該簇的初始中心，將該簇中剩余的數(shù)據(jù)點(diǎn)依據(jù)新生成的2個(gè)中心重新劃分。劃分結(jié)果用one-step-K-means方法更新一次聚類中心后，將新的聚類中心編碼到染色體中，依此生成新染色體替換原來的染色體。合并過程中首先找到距離最近的2個(gè)類，將更分散的類中的數(shù)據(jù)點(diǎn)根據(jù)數(shù)據(jù)點(diǎn)到其它聚類中心的遠(yuǎn)近分配至距離最近的簇中，隨后同樣用one-step-K-means方法更新一次聚類中心，將新聚類中心編碼生成染色體替換原染色體。需要注意的是，拆分與合并的方式不止這一種，本文采用此種方法一方面是因?yàn)樵诙啻蔚^程中具體的操作方式對(duì)種群整體的表現(xiàn)影響不大，另一方面是可以減少對(duì)距離的計(jì)算。

3.4 更新精英集

3.5 時(shí)間復(fù)雜度

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

4 實(shí)驗(yàn)結(jié)果與分析

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

本文采用調(diào)整的蘭特指數(shù)ARI(Adjusted Rand Index)和聚類準(zhǔn)確性CA(Clustering Accuracy)[12]作為評(píng)價(jià)指標(biāo)。ARI通過統(tǒng)計(jì)正確決策的樣本對(duì)數(shù)來評(píng)價(jià)算法性能，CA比較預(yù)測(cè)結(jié)果與真實(shí)結(jié)果的一致性來評(píng)價(jià)聚類準(zhǔn)確度。2個(gè)指標(biāo)取值均在[0,1]，值越大表示聚類效果越好。

4.1 實(shí)驗(yàn)設(shè)置

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

Table 1 Features of experimental datasets表1 實(shí)驗(yàn)數(shù)據(jù)集的特性

4.2 EDEMC的總體表現(xiàn)

為了簡(jiǎn)要展示算法的聚類效果，從每一個(gè)數(shù)據(jù)集的一系列聚類解中選擇已知的正確聚類數(shù)對(duì)應(yīng)的解為例進(jìn)行說明。表2是各算法在所有數(shù)據(jù)集的真實(shí)聚類數(shù)上所得聚類結(jié)果的SSD、ARI和CA。

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

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

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

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

4.3 EDEMC與GKA的對(duì)比

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

Figure 3 Experimental results of EDEMC and GKA on dataset Iris圖3 EDEMC和GKA在數(shù)據(jù)集Iris上的實(shí)驗(yàn)結(jié)果

Table 3 Running time of each algorithm

4.4 EDEMC與MOKGA、EMO-KC的對(duì)比

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

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

EDEMC算法不僅能夠一次性給出給定范圍內(nèi)所有聚類數(shù)K的聚類結(jié)果，且聚類結(jié)果的質(zhì)量較高。實(shí)驗(yàn)顯示，EDEMC的類內(nèi)平方距離和SSD均小于或等于EMO-KC和MOKGA算法聚類結(jié)果的。在圖4中表現(xiàn)為，EMO-KC的PF對(duì)應(yīng)的線段位于EDEMC的PF對(duì)應(yīng)的線段的上方，而MOKGA解集的PF對(duì)應(yīng)的線段遠(yuǎn)在兩者的上方。總體而言，在解集的分布性和收斂性2方面本文所提EDEMC算法均為最優(yōu)。

運(yùn)行效率方面，因?yàn)镸OKGA算法中采用基于距離的變異和one-step-K-means操作，因距離計(jì)算耗時(shí)的原因?qū)е翸OKGA在3者中用時(shí)最長(zhǎng)；EDEMC算法中同樣用到了one-step-K-means，并且當(dāng)種群中不存在某個(gè)聚類數(shù)K的聚類解時(shí)，為生成該K的聚類解需要對(duì)類簇進(jìn)行拆分和合并，也需多次計(jì)算距離，因此EDEMC的運(yùn)行時(shí)間略長(zhǎng)于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在真實(shí)數(shù)據(jù)集 Iris、Glass和模擬數(shù)據(jù)集Square4上的實(shí)驗(yàn)結(jié)果

5 結(jié)束語(yǔ)

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

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