基于基因表達式編程的多目標自動聚類算法

徐麗麗 許春秀 張 靜 齊 峰

1(山東勞動職業技術學院信息工程系 山東 濟南 250022)2(山東師范大學商學院 山東 濟南 250014)

0 引 言

聚類是將一組未標記的對象分配到不同簇中，使得來自同一簇內的對象之間的相似性最大，而來自不同簇間的對象之間的相似性最小[1]。聚類算法目前已被廣泛應用于許多領域，包括機器學習、模式識別、圖像分析、信息檢索、生物信息學、數據壓縮和計算機圖形學。

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

1 相關工作

作為統計學、模式識別、機器學習、數據挖掘和生物信息學等幾個領域的基礎，聚類的目的是為了確定一組未標記數據的固有分組，其中每個組中的對象在某些相似性標準下是不可區分的。聚類將數據集劃分為組(簇)，其中組(簇)中的數據元素彼此有很高的相似性，而組(簇)間元素彼此間的相似性很低。

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

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

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

2 MAGEP-Cluster算法

聚類可以被視為一個多目標優化問題。MAGEP-Cluster算法不僅可以自動確定聚類的數目，還可以基于簇內數據的緊湊性和簇間數據的連通性兩個標準實現所有數據的有效劃分。本節將對MAGEP-Cluster算法的核心部分進行詳細闡述。

2.1 廣義聚類代數算子

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

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

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

當n=3時，廣義聚類分割算子∪n和廣義聚合算子∩n的計算規則如下：

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

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

2.2 GEP染色體編碼

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

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

另外，特別需要注意的是，GEP染色體中的實數編碼信息表示某個類別的聚類中心，而不是某單個數據對象，所以在染色體進化過程中允許有重復的終端節點。

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

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

(a) GEP染色體編碼串

2.3 GEP聚類表達樹解碼

由圖2可知，GEP染色體編碼串到GEP聚類表達樹的轉換是通過從左到右和從上到下的廣度優先遍歷操作來實現的。而GEP聚類表達樹的解碼即獲得對應聚類代數算子表達式是通過從左至右和從上到下的深度優先遍歷操作來實現的，并且在解碼過程可根據聚類代數算子的定義對GEP聚類表達樹中包含的聚類中心進行聚合和分割。

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

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

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

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

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

輸入：聚類表達樹

輸出：聚類中心

(1) 如果聚類表達樹的根節點非空，則跳轉到根節點；

(2) 判斷根節點類型：

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

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

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

(6) 聚類中心點←計算子樹中的所有數據點的平均值；

(7) 尋找距離聚類中心點最近的數據點作為聚類中心；

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

(9) 算法結束。

2.4 GEP染色體遺傳操作

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

(1) 選擇操作：主要根據GEP染色體適應度值借助雙人錦標賽方法來實現，同時精英選擇策略也被使用，即每代種群最優個體自動保留到新種群中。

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

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

2.5 聚類中心合并算法

大量實驗結果表明，雖然MAGEP-Cluster在解決多目標聚類問題方面效果很好，但有時最終獲得的聚類中心不一定是最優的，例如會出現聚類中心過多的現象。因此，在通過MAGEP-Cluster獲得數據的聚類中心后，有必要設計一種聚類中心合并算法。

通過研究相鄰簇中數據點的相互關系，本文提出了一種聚類中心自動合并算法，算法流程如算法2所示。

算法2聚類中心自動合并算法

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

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

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

(2) 從Ci中選擇一個最接近Cj的點xi；

(3) 從Cj中選擇一個最接近Ci的點xj；

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

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

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

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

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

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

(10) 算法結束。

2.6 聚類目標函數

多目標聚類算法性能在很大程度上取決于聚類目標函數的選擇，這些目標函數應盡可能滿足簇內緊湊，簇間稀疏的總體要求。本文考慮選取兩個互補的目標函數：簇內緊湊性函數和簇間連接性函數作為多目標聚類算法中GEP染色體適應度值。

簇內緊湊性函數用來度量簇內所有數據點的總對稱距離，即計算數據對象與其對應的聚類中心之間的總對陣距離。簇內緊湊性函數定義為：

(1)

簇間連接性函數用來評估相鄰數據點被放置在同一個簇中的重要程度，定義為：

(2)

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

2.7 MAGEP-Cluster算法流程

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

算法3MAGEP-Cluster

輸入：數據集D，染色體頭部長度h，種群大小N，最大進化代數Gmax，最大簇個數Kmax，貢獻簇間連通性的鄰居個數L，變異概率Pm，選擇概率Ps，交叉概率Pc。

輸出：數據集D的聚類中心列表。

(1) 根據數據集D的特點及實驗要求，設置參數h、N、Gmax、Kmax、L、Pm、Pc、Lmax的初始值。

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

(3) 根據GEP染色體解碼規則，結合兩個聚類目標函數和算法1，對種群Pt進行非支配排序和擁擠度計算。

(4) 依概率Pc和Pm對種群Pt進行單點交叉操作、雙點交叉操作和變異操作，生成一個新的規模為N的種群Qt。

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

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

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

(8) 取當前種群的最優GEP染色體執行算法2，返回最優聚類中心列表。如果滿足實驗要求，則轉第(9)步，否則轉第(2)步。

(9) 算法結束。

3 實驗與結果分析

3.1 數據集

為了驗證MAGEP-Cluster算法的有效性，這里選擇了3個人工數據集和6個UCI標準數據集來比較MAGEP-Cluster和其他三個聚類算法的性能。

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

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

表1 人工數據集和UCI數據集

3.2 性能評價

為了評價算法性能，除了選取聚類數目作為衡量標準外，還引入了簇精度(ClusterAccuracy,CA)作為評價4種算法性能的指標，CA主要用來評估聚類結果中正確分類的數據點(由算法獲得的聚類標簽)所占比例，其計算式為：

(3)

式中:rj,sj分別表示數據xj∈Ci所對應的聚類標簽和真實標簽;|Ci|是第i個簇中的數據點個數;δ表示指示函數，定義如下：

(4)

CA本質上表示的是通過聚類獲得的標簽與實際標簽相同的數據點的數量。顯然，CA越大，聚類效果越好。

3.3 結果分析

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

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

表2 人工數據集最優簇數(K)和簇精度(CA)

表3 UCI數據集最優簇數(K)和簇精度(CA)

MAGEP-Cluster在三個人工數據集上的聚類結果如圖3所示。

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

4 結 語

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