徐麗麗 許春秀 張 靜 齊 峰

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

0 引 言

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

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

1 相關工作

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

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

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

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

2 MAGEP-Cluster算法

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

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

聚類算子是實現(xiàn)MAGEP-Cluster算法的關鍵，同時也是GEP染色體的核心構成元素，其設計的合理性直接決定了自動多目標聚類算法的效能。結合文獻[20-21]中關于聚類代數(shù)算子的相關研究成果，這里提出了兩種分別用于分割和聚合的廣義聚類代數(shù)算子，將其命名為∪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的計算規(guī)則如下：

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

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

2.2 GEP染色體編碼

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

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

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

假設h表示GEP染色體頭部的長度，t表示GEP染色體尾部的長度。由于聚類算子的最大參數(shù)量是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聚類表達樹的轉換是通過從左到右和從上到下的廣度優(yōu)先遍歷操作來實現(xiàn)的。而GEP聚類表達樹的解碼即獲得對應聚類代數(shù)算子表達式是通過從左至右和從上到下的深度優(yōu)先遍歷操作來實現(xiàn)的，并且在解碼過程可根據(jù)聚類代數(shù)算子的定義對GEP聚類表達樹中包含的聚類中心進行聚合和分割。

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

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

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

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

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

輸入：聚類表達樹

輸出：聚類中心

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

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

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

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

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

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

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

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

(9) 算法結束。

2.4 GEP染色體遺傳操作

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

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

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

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

2.5 聚類中心合并算法

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

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

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

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

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

(1) 從L中隨機選擇一個聚類中心Ci，根據(jù)剩余聚類中心到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 聚類目標函數(shù)

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

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

(1)

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

(2)

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

2.7 MAGEP-Cluster算法流程

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

算法3MAGEP-Cluster

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

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

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

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

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

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

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

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

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

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

(9) 算法結束。

3 實驗與結果分析

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

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

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

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

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

3.2 性能評價

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

(3)

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

(4)

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

3.3 結果分析

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

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

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

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

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

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

4 結 語

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