基于基因表達(dá)式編程的多目標(biāo)自動(dòng)聚類算法

徐麗麗 許春秀 張 靜 齊 峰

1(山東勞動(dòng)職業(yè)技術(shù)學(xué)院信息工程系 山東 濟(jì)南 250022)2(山東師范大學(xué)商學(xué)院 山東 濟(jì)南 250014)

0 引 言

聚類是將一組未標(biāo)記的對(duì)象分配到不同簇中，使得來自同一簇內(nèi)的對(duì)象之間的相似性最大，而來自不同簇間的對(duì)象之間的相似性最小[1]。聚類算法目前已被廣泛應(yīng)用于許多領(lǐng)域，包括機(jī)器學(xué)習(xí)、模式識(shí)別、圖像分析、信息檢索、生物信息學(xué)、數(shù)據(jù)壓縮和計(jì)算機(jī)圖形學(xué)。

傳統(tǒng)的單目標(biāo)聚類算法具有簡(jiǎn)單、執(zhí)行速度快且效率高等優(yōu)點(diǎn)，但同時(shí)也存在著算法容易陷入局部最優(yōu)，需要預(yù)先指定最終的聚類數(shù)目以及算法適應(yīng)性低等局限性。與單目標(biāo)聚類算法僅采用單個(gè)聚類標(biāo)準(zhǔn)來對(duì)對(duì)象進(jìn)行劃分不同，多目標(biāo)聚類算法可通過同時(shí)優(yōu)化多個(gè)聚類評(píng)價(jià)標(biāo)準(zhǔn)來獲得聚類結(jié)果，這樣可以增加算法對(duì)大部分聚類結(jié)果的魯棒性[2-3]。其中，進(jìn)化算法可以對(duì)聚類解空間進(jìn)行全局搜索從而克服傳統(tǒng)聚類算法容易陷入局部最優(yōu)的缺點(diǎn)，因此，近年來基于進(jìn)化計(jì)算的聚類算法逐漸成為科研人員關(guān)注的焦點(diǎn)[4-6]。除此之外，傳統(tǒng)聚類算法需要預(yù)先設(shè)定聚類的數(shù)目，但是在實(shí)際應(yīng)用中對(duì)于待聚類的數(shù)據(jù)通常缺乏與類別數(shù)目有關(guān)的先驗(yàn)知識(shí)，而基于進(jìn)化計(jì)算的聚類算法借助進(jìn)化機(jī)制實(shí)現(xiàn)聚類解空間的隨機(jī)搜索，無須預(yù)先指定聚類數(shù)目。本文以基因表達(dá)式編程算法(Gene Expression Programming，GEP)為基礎(chǔ)，結(jié)合設(shè)計(jì)的廣義聚類代數(shù)算子和目標(biāo)優(yōu)化函數(shù)，提出了一種基于基因表達(dá)式編程的多目標(biāo)自動(dòng)聚類算法(MAGEP-Cluster)。MAGEP-Cluster算法不僅可以自動(dòng)確定最優(yōu)聚類的數(shù)目，還可以同時(shí)基于簇內(nèi)數(shù)據(jù)緊湊性和簇間數(shù)據(jù)連通性兩個(gè)衡量指標(biāo)實(shí)現(xiàn)數(shù)據(jù)的有效劃分。

1 相關(guān)工作

作為統(tǒng)計(jì)學(xué)、模式識(shí)別、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和生物信息學(xué)等幾個(gè)領(lǐng)域的基礎(chǔ)，聚類的目的是為了確定一組未標(biāo)記數(shù)據(jù)的固有分組，其中每個(gè)組中的對(duì)象在某些相似性標(biāo)準(zhǔn)下是不可區(qū)分的。聚類將數(shù)據(jù)集劃分為組(簇)，其中組(簇)中的數(shù)據(jù)元素彼此有很高的相似性，而組(簇)間元素彼此間的相似性很低。

自動(dòng)多目標(biāo)聚類的目的就是為了解決需要預(yù)先確定最終聚類數(shù)目或分區(qū)數(shù)目的問題。MOCK(具有自動(dòng)k-確定的多目標(biāo)聚類)[7]是一種基于PESA-II[8]的多目標(biāo)聚類算法，它被用于優(yōu)化兩個(gè)互補(bǔ)的目標(biāo)函數(shù)：總體偏差(測(cè)量簇內(nèi)數(shù)據(jù)的緊湊性)和連通性(考慮相鄰數(shù)據(jù)項(xiàng)是否放置在相同的簇中)。以往的研究表明，在各種基準(zhǔn)數(shù)據(jù)集中，MOCK的表現(xiàn)優(yōu)于傳統(tǒng)的單目標(biāo)聚類算法。該算法適用于超球形或分離的簇，并且可以提供更好的聚類結(jié)果，但是MOCK在重疊簇上的聚類結(jié)果并不能令人滿意。文獻(xiàn)[9]中提出了一種基于對(duì)稱性的多目標(biāo)聚類算法(VAMOSA)，該方法以基于模擬退火的多目標(biāo)優(yōu)化方法作為底層優(yōu)化策略，借助聚類中心字符串化的編碼規(guī)則，并在聚類中使用文獻(xiàn)[10]中新提出的點(diǎn)對(duì)稱距離來代替常規(guī)的歐幾里德距離。實(shí)驗(yàn)結(jié)果表明，VAMOSA算法整體性能優(yōu)于MOCK，但是，同樣該算法對(duì)重疊數(shù)據(jù)集的聚類沒有很好的魯棒性?；诨虮磉_(dá)式編程算法[11]，文獻(xiàn)[12-14]提出了一類名為GEP-Cluster聚類算法，該類算法都借鑒了遺傳進(jìn)化過程中的某些生物特性，例如小生境等，相關(guān)實(shí)驗(yàn)結(jié)果表明該類算法的性能要好于基于原始GEP聚類算法的表現(xiàn)。

文獻(xiàn)[15]針對(duì)層次聚類算法不足，提出了一種基于GEP計(jì)算模型的層次聚類算法(GEPHCA)，尋找適應(yīng)度最高的聚類中心。相關(guān)仿真實(shí)驗(yàn)表明，該算法不僅能夠?qū)崿F(xiàn)自動(dòng)聚類，而且具有自適應(yīng)迭代、速度較快、穩(wěn)定高效等優(yōu)點(diǎn)。文獻(xiàn)[16]通過結(jié)合基因表達(dá)式編程和已有的串行聚類DBSCAN算法提出了一種GEP-DBSCAN協(xié)作過濾聚類算法來尋找最近鄰居，改進(jìn)基于密度的協(xié)作過濾方法，實(shí)驗(yàn)表明了算法的有效性以及提高了時(shí)間效率。文獻(xiàn)[17]針對(duì)模糊C-均值聚類圖像分割方法存在的對(duì)初始值敏感及抗噪性能差的問題,提出一種結(jié)合基因表達(dá)式編程與空間模糊聚類的圖像分割方法。仿真實(shí)驗(yàn)表明，該算法在聚類劃分系數(shù)、聚類劃分熵和峰值信噪比等評(píng)價(jià)指標(biāo)上總體性能優(yōu)于其他比較算法。文獻(xiàn)[18]對(duì)傳統(tǒng)的基于基因表達(dá)式編程的聚類算法進(jìn)行改進(jìn)，提出了一種新的聚類合并準(zhǔn)則解決原算法后期過合并的問題，同時(shí)改進(jìn)算法編碼方式并在進(jìn)化過程中引入多目標(biāo)來解決聚類問題。仿真結(jié)果表明，新算法的性能優(yōu)于對(duì)比算法。文獻(xiàn)[19]提出了一種改進(jìn)的融合基因表達(dá)式編程和k均值算法的自動(dòng)聚類算法，在GIS物流選址優(yōu)化問題中實(shí)驗(yàn)結(jié)果表明，所提算法具有收斂速度快和聚類精度高的優(yōu)勢(shì)。

本文以GEP-Cluster聚類算法為研究對(duì)象，通過改進(jìn)聚類代數(shù)算子、引入新的目標(biāo)優(yōu)化函數(shù)和設(shè)計(jì)聚類中心合并規(guī)則，提出了一種新的基于基因表達(dá)式編程(GEP)自動(dòng)多目標(biāo)聚類算法，稱為MAGEP-Cluster。該算法不僅可以在沒有任何先驗(yàn)知識(shí)的情況下自動(dòng)確定聚類的數(shù)目，而且與其他聚類算法相比性能更優(yōu)。

2 MAGEP-Cluster算法

聚類可以被視為一個(gè)多目標(biāo)優(yōu)化問題。MAGEP-Cluster算法不僅可以自動(dòng)確定聚類的數(shù)目，還可以基于簇內(nèi)數(shù)據(jù)的緊湊性和簇間數(shù)據(jù)的連通性兩個(gè)標(biāo)準(zhǔn)實(shí)現(xiàn)所有數(shù)據(jù)的有效劃分。本節(jié)將對(duì)MAGEP-Cluster算法的核心部分進(jìn)行詳細(xì)闡述。

2.1 廣義聚類代數(shù)算子

聚類算子是實(shí)現(xiàn)MAGEP-Cluster算法的關(guān)鍵，同時(shí)也是GEP染色體的核心構(gòu)成元素，其設(shè)計(jì)的合理性直接決定了自動(dòng)多目標(biāo)聚類算法的效能。結(jié)合文獻(xiàn)[20-21]中關(guān)于聚類代數(shù)算子的相關(guān)研究成果，這里提出了兩種分別用于分割和聚合的廣義聚類代數(shù)算子，將其命名為∪n和∩n，如圖1所示。

圖1 廣義聚類分割算子∪n和廣義聚合算子∩n

假設(shè)Ox,Oy,Oz分別是簇Cx、Cy和Cz的d維度中心點(diǎn)，其中，Ox=(x1,x2,…,xd),Oy=(y1,y2,…,yd),Oz=(z1,z2,…,zd)。

當(dāng)n=3時(shí)，廣義聚類分割算子∪n和廣義聚合算子∩n的計(jì)算規(guī)則如下：

(1) ∪3(Ox,Oy,Oz)={Ox,Oy,Oz}

(2) ∩3(Ox,Oy,Oz)={Oxyz}

2.2 GEP染色體編碼

MAGEP-Cluster算法采用了與GEP相同的染色體編碼方式，每條染色體由頭部和尾部構(gòu)成。頭部可以包含函數(shù)節(jié)點(diǎn)或者終端節(jié)點(diǎn)，而尾部只能包含終端節(jié)點(diǎn)。MAGEP-Cluster算法中，函數(shù)節(jié)點(diǎn)集合為F={∪2,∩2,∪3,∩3,…,∪n,∩n}，終端節(jié)點(diǎn)集合T={x1,x2,…,xm},i∈[1,m]，其中xi表示數(shù)據(jù)集中第i個(gè)對(duì)象，m代表數(shù)據(jù)集中對(duì)象的個(gè)數(shù)。

根據(jù)GEP染色體編碼的特點(diǎn)，這里使用F和T的元素組成GEP染色體的頭部，使用T中的元素構(gòu)建GEP染色體的尾部。GEP染色體在初始化時(shí)，若基因位位于染色體頭部，則隨機(jī)從集合F∪T中隨機(jī)選取一個(gè)元素作為該基因位的取值；若基因位位于染色體尾部，則隨機(jī)從集合T中隨機(jī)選取一個(gè)元素作為該基因位的取值。

另外，特別需要注意的是，GEP染色體中的實(shí)數(shù)編碼信息表示某個(gè)類別的聚類中心，而不是某單個(gè)數(shù)據(jù)對(duì)象，所以在染色體進(jìn)化過程中允許有重復(fù)的終端節(jié)點(diǎn)。

假設(shè)h表示GEP染色體頭部的長(zhǎng)度，t表示GEP染色體尾部的長(zhǎng)度。由于聚類算子的最大參數(shù)量是h，那么t=h(n-1)+1。從聚類表達(dá)樹中可以看出，在最極端的情況下，一條GEP染色體最多可以表達(dá)h(n+1)個(gè)聚類中心。

圖2展示了MAGEP-Cluster中GEP染色體三種表達(dá)形式。圖2(a)展示了一條GEP染色體(h=4)的編碼串形式，圖2(b)展示了GEP染色體對(duì)應(yīng)的GEP聚類表達(dá)樹，圖2(c)展示了GEP聚類表達(dá)樹對(duì)應(yīng)的GEP聚類操作算子表達(dá)式。

(a) GEP染色體編碼串

2.3 GEP聚類表達(dá)樹解碼

由圖2可知，GEP染色體編碼串到GEP聚類表達(dá)樹的轉(zhuǎn)換是通過從左到右和從上到下的廣度優(yōu)先遍歷操作來實(shí)現(xiàn)的。而GEP聚類表達(dá)樹的解碼即獲得對(duì)應(yīng)聚類代數(shù)算子表達(dá)式是通過從左至右和從上到下的深度優(yōu)先遍歷操作來實(shí)現(xiàn)的，并且在解碼過程可根據(jù)聚類代數(shù)算子的定義對(duì)GEP聚類表達(dá)樹中包含的聚類中心進(jìn)行聚合和分割。

對(duì)GEP染色體對(duì)應(yīng)的GEP聚類表達(dá)樹解碼的目的是為了了解染色體信息中攜帶的聚類中心信息。在實(shí)際解碼時(shí)，可采取遞歸方式遍歷聚類表達(dá)樹來完成解碼過程，其中主要包含聚合、分割和集中數(shù)據(jù)等操作。

解碼過程的主要步驟如下：(a) 從聚類表達(dá)樹的根節(jié)點(diǎn)開始處理。如果聚類表達(dá)樹的根節(jié)點(diǎn)是∪n，則將以該節(jié)點(diǎn)的子節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹從左至右依次放置到n個(gè)不同的集合中，實(shí)現(xiàn)多個(gè)不同簇間的分割；如果聚類表達(dá)樹的根節(jié)點(diǎn)是∩n，則從左至右依次遍歷其所有子樹，將所有子樹中的數(shù)據(jù)放入同一簇中，計(jì)算所有子樹根節(jié)點(diǎn)的平均值，將該平均值作為聚類中心點(diǎn)。注意，真正的聚類中心是由距離聚類中心點(diǎn)最近的數(shù)據(jù)對(duì)象來替代表示的。(b) 如前所述，遞歸地解碼所有的子樹。

(a) MAGEP-Cluster在Data_3_2上的聚類結(jié)果

GEP聚類表達(dá)樹解碼算法的具體流程，如算法1所示。

算法1聚類表達(dá)樹解碼(尋找聚類中心)

輸入：聚類表達(dá)樹

輸出：聚類中心

(1) 如果聚類表達(dá)樹的根節(jié)點(diǎn)非空，則跳轉(zhuǎn)到根節(jié)點(diǎn)；

(2) 判斷根節(jié)點(diǎn)類型：

(3) 如果根節(jié)點(diǎn)為∪n，則依次將該節(jié)點(diǎn)的所有子樹放置到集合I中；

(4) 遍歷集合I中的所有子樹并依次進(jìn)行遞歸解碼；

(5) 如果根節(jié)點(diǎn)為∩n，則依次遍歷解碼其所有子樹；

(6) 聚類中心點(diǎn)←計(jì)算子樹中的所有數(shù)據(jù)點(diǎn)的平均值；

(7) 尋找距離聚類中心點(diǎn)最近的數(shù)據(jù)點(diǎn)作為聚類中心；

(8) 返回所有的聚類中心；

(9) 算法結(jié)束。

2.4 GEP染色體遺傳操作

與經(jīng)典GEP算法類似，MAGEP-Cluster采用了三種遺傳操作：選擇、交叉和變異。

(1) 選擇操作：主要根據(jù)GEP染色體適應(yīng)度值借助雙人錦標(biāo)賽方法來實(shí)現(xiàn)，同時(shí)精英選擇策略也被使用，即每代種群最優(yōu)個(gè)體自動(dòng)保留到新種群中。

(2) 交叉操作：主要采用了單點(diǎn)交叉和雙點(diǎn)交叉兩種方式。大量實(shí)驗(yàn)結(jié)果表明，交叉概率設(shè)為0.87時(shí)MAGEP-Cluster呈現(xiàn)出更好的性能。由于交叉點(diǎn)是隨機(jī)選取的，一旦產(chǎn)生的染色體后代是非法的，算法規(guī)定本次交叉操作將取消。

(3) 變異操作:是進(jìn)化過程中跳出局部極值點(diǎn)的有效方式。大量實(shí)驗(yàn)結(jié)果表明，變異概率設(shè)為0.024時(shí)MAGEP-Cluster呈現(xiàn)出更好的性能。實(shí)際操作時(shí)，隨機(jī)選擇染色基因位進(jìn)行變異，根據(jù)基因位所處位置分為兩種變異操作：如果基因位在頭部，則在集合F∪T中隨機(jī)選擇一個(gè)元素代替當(dāng)前基因位的元素；如果基因位在尾部，則在集合T中隨機(jī)選擇一個(gè)元素代替當(dāng)前基因位中的元素。如果變異后的染色體是非法，則重新隨機(jī)選擇基因位執(zhí)行變異操作，直到產(chǎn)生合法染色體后代為止。

2.5 聚類中心合并算法

大量實(shí)驗(yàn)結(jié)果表明，雖然MAGEP-Cluster在解決多目標(biāo)聚類問題方面效果很好，但有時(shí)最終獲得的聚類中心不一定是最優(yōu)的，例如會(huì)出現(xiàn)聚類中心過多的現(xiàn)象。因此，在通過MAGEP-Cluster獲得數(shù)據(jù)的聚類中心后，有必要設(shè)計(jì)一種聚類中心合并算法。

通過研究相鄰簇中數(shù)據(jù)點(diǎn)的相互關(guān)系，本文提出了一種聚類中心自動(dòng)合并算法，算法流程如算法2所示。

算法2聚類中心自動(dòng)合并算法

輸入：MAGEP-Cluster聚類中心列表L

輸出：合并后的聚類中心列表L

(1) 從L中隨機(jī)選擇一個(gè)聚類中心Ci，根據(jù)剩余聚類中心到Ci的距離對(duì)L進(jìn)行排序，得到一個(gè)新的排序聚類中心列表Ls={Ci,Cj,…}，其中Cj是距離Ci最近的簇，以次類推；

(2) 從Ci中選擇一個(gè)最接近Cj的點(diǎn)xi；

(3) 從Cj中選擇一個(gè)最接近Ci的點(diǎn)xj；

(4) 計(jì)算xi和xj間的歐氏距離Dij；

(5) 計(jì)算Ci的平均距離Di；

(6) 計(jì)算Cj的平均距離Dj；

(7) 如果Dij≤Di或者Dij≤Dj，則將Ci和Cj合并為Cij，同時(shí)替換L中的Ci和Cj；

(8) 重復(fù)上述過程，直到L中沒有聚類中心可以合并；

(9) 輸出合并后的聚類中心列表L；

(10) 算法結(jié)束。

2.6 聚類目標(biāo)函數(shù)

多目標(biāo)聚類算法性能在很大程度上取決于聚類目標(biāo)函數(shù)的選擇，這些目標(biāo)函數(shù)應(yīng)盡可能滿足簇內(nèi)緊湊，簇間稀疏的總體要求。本文考慮選取兩個(gè)互補(bǔ)的目標(biāo)函數(shù)：簇內(nèi)緊湊性函數(shù)和簇間連接性函數(shù)作為多目標(biāo)聚類算法中GEP染色體適應(yīng)度值。

簇內(nèi)緊湊性函數(shù)用來度量簇內(nèi)所有數(shù)據(jù)點(diǎn)的總對(duì)稱距離，即計(jì)算數(shù)據(jù)對(duì)象與其對(duì)應(yīng)的聚類中心之間的總對(duì)陣距離。簇內(nèi)緊湊性函數(shù)定義為：

(1)

簇間連接性函數(shù)用來評(píng)估相鄰數(shù)據(jù)點(diǎn)被放置在同一個(gè)簇中的重要程度，定義為：

(2)

聚類目標(biāo)函數(shù)包括簇內(nèi)緊湊性函數(shù)和簇間連接性函數(shù)的一個(gè)重要原因是它們能夠平衡彼此增加或減少簇總數(shù)的趨勢(shì)，從而不必預(yù)先指定聚類簇個(gè)數(shù)k。與緊湊性相關(guān)的目標(biāo)值必然隨著簇個(gè)數(shù)的增加而提高，而連通性恰好相反，兩者之間的相互作用對(duì)于保持簇個(gè)數(shù)的動(dòng)態(tài)變化至關(guān)重要。

2.7 MAGEP-Cluster算法流程

本節(jié)將對(duì)所提出的算法MAGEP-Cluster算法流程進(jìn)行詳細(xì)描述，具體的算法流程如算法3所示。MAGEP-Cluster算法采用了與經(jīng)典多目標(biāo)遺傳算法：NSGA-II[22]類似的進(jìn)化流程，其中非支配排序和擁擠度計(jì)算規(guī)則與NSGA-II完全相同。

算法3MAGEP-Cluster

輸入：數(shù)據(jù)集D，染色體頭部長(zhǎng)度h，種群大小N，最大進(jìn)化代數(shù)Gmax，最大簇個(gè)數(shù)Kmax，貢獻(xiàn)簇間連通性的鄰居個(gè)數(shù)L，變異概率Pm，選擇概率Ps，交叉概率Pc。

輸出：數(shù)據(jù)集D的聚類中心列表。

(1) 根據(jù)數(shù)據(jù)集D的特點(diǎn)及實(shí)驗(yàn)要求，設(shè)置參數(shù)h、N、Gmax、Kmax、L、Pm、Pc、Lmax的初始值。

(2) 根據(jù)GEP染色體編碼規(guī)則，創(chuàng)建初始種群Pt(t=0)，種群規(guī)模為N。

(3) 根據(jù)GEP染色體解碼規(guī)則，結(jié)合兩個(gè)聚類目標(biāo)函數(shù)和算法1，對(duì)種群Pt進(jìn)行非支配排序和擁擠度計(jì)算。

(4) 依概率Pc和Pm對(duì)種群Pt進(jìn)行單點(diǎn)交叉操作、雙點(diǎn)交叉操作和變異操作，生成一個(gè)新的規(guī)模為N的種群Qt。

(5) 構(gòu)建中間種群Rt=Pt∪Qt。

(6) 根據(jù)GEP染色體解碼規(guī)則，結(jié)合兩個(gè)聚類目標(biāo)函數(shù)和算法1，對(duì)種群R_t進(jìn)行非支配排序和擁擠度計(jì)算，借助雙人錦標(biāo)賽選擇法和精英保留策略，從中間種群R_t中選擇N個(gè)染色體生成新種群P_(t+1)，令t=t+1。

(7) 如果t≤Gmax，則返回第(4)步，否則轉(zhuǎn)向第(8)步。

(8) 取當(dāng)前種群的最優(yōu)GEP染色體執(zhí)行算法2，返回最優(yōu)聚類中心列表。如果滿足實(shí)驗(yàn)要求，則轉(zhuǎn)第(9)步，否則轉(zhuǎn)第(2)步。

(9) 算法結(jié)束。

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

3.1 數(shù)據(jù)集

為了驗(yàn)證MAGEP-Cluster算法的有效性，這里選擇了3個(gè)人工數(shù)據(jù)集和6個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集來比較MAGEP-Cluster和其他三個(gè)聚類算法的性能。

雖然人工數(shù)據(jù)集看起來很簡(jiǎn)單，但都包含一些特殊特征，例如Data_5_2中部分?jǐn)?shù)據(jù)高度重疊，Data_4_3中存在部分噪聲點(diǎn)(僅在兩個(gè)不同的簇之間)，這些特殊特征會(huì)對(duì)聚類目標(biāo)優(yōu)化函數(shù)產(chǎn)生干擾，影響聚類算法的最終效果。因此，選取人工數(shù)據(jù)集目的就是為了驗(yàn)證算法能否在處理這些具有特殊特征數(shù)據(jù)集時(shí)具有良好的魯棒性。

表1中給出了數(shù)據(jù)集的簡(jiǎn)要描述，主要涉及總樣本數(shù)據(jù)點(diǎn)數(shù)(n)，分類簇個(gè)數(shù)(k)和樣本數(shù)據(jù)屬性個(gè)數(shù)(d)三個(gè)方面。

表1 人工數(shù)據(jù)集和UCI數(shù)據(jù)集

3.2 性能評(píng)價(jià)

為了評(píng)價(jià)算法性能，除了選取聚類數(shù)目作為衡量標(biāo)準(zhǔn)外，還引入了簇精度(ClusterAccuracy,CA)作為評(píng)價(jià)4種算法性能的指標(biāo)，CA主要用來評(píng)估聚類結(jié)果中正確分類的數(shù)據(jù)點(diǎn)(由算法獲得的聚類標(biāo)簽)所占比例，其計(jì)算式為：

(3)

式中:rj,sj分別表示數(shù)據(jù)xj∈Ci所對(duì)應(yīng)的聚類標(biāo)簽和真實(shí)標(biāo)簽;|Ci|是第i個(gè)簇中的數(shù)據(jù)點(diǎn)個(gè)數(shù);δ表示指示函數(shù)，定義如下：

(4)

CA本質(zhì)上表示的是通過聚類獲得的標(biāo)簽與實(shí)際標(biāo)簽相同的數(shù)據(jù)點(diǎn)的數(shù)量。顯然，CA越大，聚類效果越好。

3.3 結(jié)果分析

為了更好驗(yàn)證MAGEP-Cluster算法的性能，這里分別選取了另外三種算法：GEP-Cluster、Mock和VAMOSA作為比較對(duì)象。由于每種算法的初始種群是隨機(jī)生成的，為了保證比較的公平性，對(duì)于每個(gè)數(shù)據(jù)集，每個(gè)算法獨(dú)立運(yùn)行200次，以使聚類結(jié)果具有可比性，然后分別計(jì)算每種算法得到的最優(yōu)簇?cái)?shù)(K)和簇精度(CA)的平均值。另外，由于MAGEP-Cluster與GEP-Cluster均使用類似的GEP染色體編碼和解碼規(guī)則，在實(shí)驗(yàn)時(shí)，規(guī)定兩個(gè)算法中GEP染色體的頭部和尾部相同，唯一區(qū)別在于兩個(gè)算法使用的函數(shù)集不同，MAGEP-Cluster采用了廣義聚類代數(shù)算子即算子的操作數(shù)大于等于2，而GEP-Cluster采用的是二元聚類代數(shù)算子即算子操作數(shù)只能為2。

表2和表3分別給出了四種算法在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上的K和CA比較結(jié)果。

表2 人工數(shù)據(jù)集最優(yōu)簇?cái)?shù)(K)和簇精度(CA)

表3 UCI數(shù)據(jù)集最優(yōu)簇?cái)?shù)(K)和簇精度(CA)

MAGEP-Cluster在三個(gè)人工數(shù)據(jù)集上的聚類結(jié)果如圖3所示。

如算法2和算法3所示，通過本文提出的MAGEP-Cluster算法獲得的聚類數(shù)的平均值最接近每個(gè)數(shù)據(jù)集中的實(shí)際聚類數(shù)，與GEP-Cluster、MOCK和VAMOSA相比，MAGEP-Cluster算法在聚類方面具明顯的優(yōu)勢(shì)。此外，從算法2和算法3中還可以看出，對(duì)于所有的數(shù)據(jù)集來說，所提出的MAGEP-Cluster算法產(chǎn)生的聚類精度(CA)的平均值高于GEP-Cluster、MOCK和VAMOSA的平均值，表明MAGEP-Cluster可以為不同的數(shù)據(jù)集找到更好的聚類分區(qū)。

4 結(jié) 語

本文通過改進(jìn)聚類代數(shù)算子、引入新的目標(biāo)優(yōu)化函數(shù)和設(shè)計(jì)聚類中心合并規(guī)則，提出了一種新的基于基因表達(dá)式編程(GEP)自動(dòng)多目標(biāo)聚類算法，稱為MAGEP-Cluster。所提出的MAGEP-Cluster可以通過優(yōu)化簇內(nèi)數(shù)據(jù)緊湊性和簇間數(shù)據(jù)連接性兩個(gè)目標(biāo)函數(shù)來自動(dòng)計(jì)算簇的最佳數(shù)量并提高了聚類算法的準(zhǔn)確性。實(shí)驗(yàn)部分分別在3個(gè)人工數(shù)據(jù)集和5個(gè)UCI數(shù)據(jù)集，比較了MAGEP-Cluster與GEP-Cluster、MOCK和VAMOSA的聚類性能。實(shí)驗(yàn)結(jié)果表明，MAGEP-Cluster算法能夠有效地計(jì)算最優(yōu)聚類數(shù)目，并在一定程度上提高了最終聚類結(jié)果的準(zhǔn)確性。MAGEP-Cluster與GEP-Cluster相比之下，除了使用的函數(shù)集不同外，其他部分相似性很高，但在使用時(shí)前者卻表現(xiàn)出了更好的魯棒性，其中一個(gè)很重要的原因在于MAGEP-Cluster采用了廣義聚類算子，但該算子對(duì)MAGEP-Cluster算法具體的影響機(jī)制尚不明確，因此，廣義聚類算子的影響機(jī)制將成為未來研究工作的重點(diǎn)。