精英遺傳K-medoids聚類算法

宋飛豹，賈瑞玉

安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

1 引言

聚類分析一直是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識(shí)別等領(lǐng)域的重要研究內(nèi)容之一[1]。K-medoids算法作為應(yīng)用廣泛的聚類算法，近年來，關(guān)于K-medoids算法的研究越來越多。文獻(xiàn)[2]根據(jù)最大最小法則選出k個(gè)稠密區(qū)域，由此得到k個(gè)初始中心點(diǎn)，從而提升了K-medoids的聚類質(zhì)量；文獻(xiàn)[3]通過差分隱私保護(hù)技術(shù)使K-medoids能夠處理增量數(shù)據(jù)的動(dòng)態(tài)聚類問題；文獻(xiàn)[4]通過引入距離加速理論提高了K-medoids聚類的效率。雖然K-medoids聚類算法對(duì)離群點(diǎn)的處理效果較好，但K-medoids算法依然存在著初始中心點(diǎn)敏感和聚類結(jié)果不穩(wěn)定等問題。為了解決這些問題，常見的方法是將遺傳算法與聚類算法相結(jié)合。文獻(xiàn)[5]按照最大屬性值范圍劃分法選擇聚類中心初值，同時(shí)運(yùn)用兩階段動(dòng)態(tài)選擇和變異方法，從而提升了算法的聚類效果。文獻(xiàn)[6]提出了在MapReduce架構(gòu)下的遺傳K-medoids算法，該算法使用遺傳算法解決K-medoids算法聚類不穩(wěn)定的問題，使用MapReduce框架解決大數(shù)據(jù)聚類的問題。雖然遺傳算法能夠在一定程度上解決K-medoids算法求解結(jié)果不穩(wěn)定的問題，但遺傳算法本身也存在著早熟、后期收斂速度慢等問題[7]。文獻(xiàn)[8-14]為遺傳算法引入了精英策略，提出了基于精英策略改進(jìn)遺傳算法的方法。

雖然精英策略在一定程度上提高了遺傳算法的全局收斂性，但是由于聚類算法的特殊性，使精英策略不能直接運(yùn)用到聚類分析中。在此基礎(chǔ)上本文提出了一種精英遺傳K-medoids聚類算法（Elite Genetic K-medoids Clustering Algorithm，EG K CA）。該算法使用K-medoids聚類的評(píng)價(jià)標(biāo)準(zhǔn)作為遺傳算法的適應(yīng)度函數(shù)。通過精英個(gè)體來保證算法的全局收斂性。同時(shí)每次進(jìn)化的進(jìn)化團(tuán)隊(duì)均通過種群的平均適應(yīng)度來引入若干隨機(jī)個(gè)體，以提高種群多樣性。通過組合交叉和父子競爭的操作提高進(jìn)化效率。最終通過測(cè)試8個(gè)具有一定代表性的數(shù)據(jù)集證明了EGKCA算法的聚類準(zhǔn)確率高，求解結(jié)果穩(wěn)定。

2 精英遺傳K-medoids聚類算法

2.1 編碼方式

傳統(tǒng)的二進(jìn)制編碼方式會(huì)出現(xiàn)編碼長度過長、數(shù)據(jù)信息讀取困難等問題，為了解決這一問題，本文采用一種簡單自然的編碼方式[6]。設(shè)數(shù)據(jù)樣本共有L個(gè)數(shù)據(jù)，中心點(diǎn)個(gè)數(shù)為k，種群數(shù)目為N，則從{ }1,2,…,L 中選擇k個(gè)值作為進(jìn)化個(gè)體Xi(1≤i≤N)，進(jìn)化個(gè)體Xi中每個(gè)等位基因代表每個(gè)中心點(diǎn)的位置，基因長度代表中心點(diǎn)的個(gè)數(shù)。

2.2 精英個(gè)體

精英個(gè)體best最初是由初始種群s中適應(yīng)度最高的個(gè)體組成的。隨著遺傳操作的進(jìn)行，將精英個(gè)體best與每次進(jìn)行遺傳操作后產(chǎn)生適應(yīng)度最高的個(gè)體tempmax進(jìn)行對(duì)比，若tempmax的適應(yīng)度大于best，則更新精英個(gè)體，將個(gè)體tempmax替換掉原先best的個(gè)體。

2.3 適應(yīng)度函數(shù)

其中，ci為劃分的中心點(diǎn)(1≤i≤k)；Ci為根據(jù)中心點(diǎn)ci劃分出來的簇；o是屬于簇Ci里面的數(shù)據(jù)元素；dist為歐式距離。E代表這所有數(shù)據(jù)元素在中心點(diǎn)集合C={c1,c2,…,ck}下聚類所產(chǎn)生的聚類代價(jià)，其值越小，代表簇內(nèi)距離越小，簇間越緊湊獨(dú)立，聚類效果越好。

為了體現(xiàn)聚類代價(jià)E的作用，本文采用的適應(yīng)度函數(shù)如下：

其中，Xi(1≤i≤N)為種群的一個(gè)進(jìn)化個(gè)體，其基因信息代表一個(gè)中心點(diǎn)集合；EXi代表數(shù)據(jù)集A在進(jìn)化個(gè)體Xi下的聚類代價(jià)。 f(Xi)的值越大，表示聚類代價(jià)越小，聚類的效果越好。 f(Xi)的最大值，即為本文需要求得的最優(yōu)聚類方案。

2.4 進(jìn)化團(tuán)隊(duì)的產(chǎn)生

傳統(tǒng)的遺傳算法在求解最優(yōu)值問題時(shí)，面臨的最大問題就是早熟現(xiàn)象。遺傳算法出現(xiàn)早熟現(xiàn)象的根本原因在于種群在進(jìn)化過程中由于不斷優(yōu)勝劣汰，使得種群多樣性喪失，個(gè)體逐漸歸于單一。為了解決遺傳算法的早熟現(xiàn)象，提高進(jìn)化效率，本文通過引入rnum個(gè)隨機(jī)個(gè)體來替換掉每次遺傳操作后形成的進(jìn)化種群中適應(yīng)度最差的rnum個(gè)個(gè)體[8，13]，從而保證了種群的多樣性。

為了更好地發(fā)揮隨機(jī)個(gè)體的調(diào)節(jié)作用，本文使得每次產(chǎn)生隨機(jī)個(gè)體的數(shù)目與本次進(jìn)化種群的整體優(yōu)秀程度有關(guān)。種群整體越優(yōu)秀，所需要的隨機(jī)個(gè)體數(shù)目越小，反之，種群整體越差，就需要更多的隨機(jī)個(gè)體為種群產(chǎn)生更多的變化。種群整體評(píng)價(jià)程度PA可由以下公式求得：

其中，fbest代表種群所經(jīng)歷過的最大適應(yīng)度；favg為當(dāng)前種群的平均適應(yīng)度；fmin代表當(dāng)前種群的最差適應(yīng)度。PA越大表示種群整體適應(yīng)度越小，也就是說種群整體處于一個(gè)較差的水平，此時(shí)就需要更多的隨機(jī)個(gè)體來為種群增加更多的變化。

隨機(jī)個(gè)體數(shù)目的計(jì)算公式如下：

其中，τ0、τ1為rnum的調(diào)節(jié)參數(shù)；N為種群個(gè)體數(shù)目。式（3）、（4）保證了 rnum 的取值范圍在 [τ1×N,(τ0+τ1)×N]之間。進(jìn)化團(tuán)隊(duì)的產(chǎn)生模型如圖1所示。

圖1 進(jìn)化團(tuán)隊(duì)產(chǎn)生模型

2.5 組合交叉

傳統(tǒng)遺傳算法的交叉方式在處理聚類問題時(shí)，由于交叉?zhèn)€體的相似性，容易出現(xiàn)交叉重復(fù)、交叉效率低下等問題。為了解決這些問題，文獻(xiàn)[13]提出了一種協(xié)作交叉操作，通過兩個(gè)交叉?zhèn)€體差異度來為交叉?zhèn)€體選擇合適的交叉方式，從而避免了個(gè)體間的無效交叉。但是在聚類分析中進(jìn)化個(gè)體存在著基因數(shù)目少，單個(gè)基因影響大等問題，使得協(xié)作交叉無法直接用在聚類算法中。為此本文通過設(shè)計(jì)一種適合聚類算法避免無效交叉的交叉算子來對(duì)協(xié)作交叉進(jìn)行改進(jìn)，提出了組合交叉的操作。

定義1（無效交叉點(diǎn)）當(dāng)參與交叉的兩個(gè)個(gè)體存在相同的中心點(diǎn)時(shí)，該中心點(diǎn)和與之對(duì)應(yīng)的交叉點(diǎn)為避免重復(fù)均不能參與交叉，此時(shí)稱該中心點(diǎn)和與之對(duì)應(yīng)的交叉點(diǎn)為無效交叉點(diǎn)。

由定義1可知，無效交叉點(diǎn)的存在嚴(yán)重影響著交叉的質(zhì)量，為了有效減少無效交叉點(diǎn)的影響，首先需要一個(gè)對(duì)無效交叉點(diǎn)影響程度的評(píng)價(jià)標(biāo)準(zhǔn)，本文使用相似度的概念來對(duì)兩個(gè)交叉?zhèn)€體進(jìn)行評(píng)價(jià)。

其中，snum表示無效交叉點(diǎn)的個(gè)數(shù)；k為中心點(diǎn)的個(gè)數(shù)；u表示兩個(gè)交叉?zhèn)€體的相似程度，其值越大，無效交叉點(diǎn)所占比重也越大，個(gè)體越相似。

定義2（整合交叉）當(dāng)兩個(gè)交叉?zhèn)€體存在若干個(gè)相同的中心點(diǎn)時(shí)，首先將這些相同的中心點(diǎn)從交叉?zhèn)€體中剔除，然后對(duì)這兩個(gè)個(gè)體進(jìn)行普通的單點(diǎn)交叉，最后把單點(diǎn)交叉后得到的兩個(gè)個(gè)體分別加入已剔除的中心點(diǎn)，得到兩個(gè)新的個(gè)體。這就是整合交叉。

為了減輕無效交叉點(diǎn)的影響，本文所提出的組合交叉操作，是根據(jù)交叉?zhèn)€體的相似度不斷調(diào)整交叉方式。當(dāng)兩個(gè)交叉?zhèn)€體的相似度u≤u0時(shí)，使用普通的單點(diǎn)交叉，此時(shí)，單點(diǎn)交叉只需要避免重復(fù)即可；當(dāng)兩個(gè)交叉?zhèn)€體的相似度u＞u0時(shí)，使用整合交叉。

2.6 變異

由于聚類算法的特殊性，使得算法在進(jìn)行遺傳操作過程中必須保持中心點(diǎn)數(shù)目不變，也就是k值的不可變性，同時(shí)也必須保證每個(gè)進(jìn)化個(gè)體不存在相同的中心點(diǎn)。也就是說每個(gè)進(jìn)化個(gè)體必須存儲(chǔ)含k個(gè)不同中心點(diǎn)的信息，這也是為什么在交叉過程中必須要避免重復(fù)的原因。

在變異過程中為了避免重復(fù)，首先從進(jìn)化個(gè)體Xi中選擇一個(gè)變異點(diǎn)sm(1≤sm≤k)，然后從與Xi相對(duì)應(yīng)的非中心點(diǎn)集合中，隨機(jī)找到一個(gè)非中心點(diǎn)的位置替換掉sm中的內(nèi)容。這樣既實(shí)現(xiàn)了變異的需求，又可以保證中心點(diǎn)不重復(fù)。

2.7 父子競爭

在傳統(tǒng)的遺傳算法中，經(jīng)常出現(xiàn)“子不如父”的現(xiàn)象，即遺傳操作后的子代種群整體適應(yīng)度不如父代種群的現(xiàn)象。出現(xiàn)這一現(xiàn)象的一個(gè)主要原因是交叉變異的不可控性。個(gè)體進(jìn)行交叉變異時(shí)，交叉變異的結(jié)果具有一定的隨機(jī)性，個(gè)體的適應(yīng)度有可能變得更好，也有可能變得更差。為了盡量控制個(gè)體的交叉變異向著一個(gè)比較正確的方向進(jìn)行，本文提出了一種父子競爭的操作。

定義3（父子競爭）將交叉變異后得到的子代個(gè)體與父代個(gè)體進(jìn)行對(duì)比，若父代個(gè)體的適應(yīng)度大于子代個(gè)體，則保留父代個(gè)體作為新種群的成員，同時(shí)該父代個(gè)體不再參與交叉變異；反之，則保留子代個(gè)體，該父代個(gè)體依然可以參與交叉變異。

2.8 EG K CA算法描述

輸入：數(shù)據(jù)集A，中心點(diǎn)個(gè)數(shù)k。

輸出：聚類中心點(diǎn)集合。

步驟1初始化種群s、精英個(gè)體best。

步驟2根據(jù)K-medoids算法計(jì)算每個(gè)個(gè)體的適應(yīng)度，并根據(jù)式（4）生成rnum個(gè)隨機(jī)個(gè)體，替換掉適應(yīng)度最差的rnum個(gè)個(gè)體，形成進(jìn)化團(tuán)隊(duì)t。

步驟3更新精英個(gè)體best，將精英個(gè)體best替換掉進(jìn)化團(tuán)隊(duì)t中適應(yīng)度最差的個(gè)體，然后將精英個(gè)體best與進(jìn)化團(tuán)隊(duì)t中適應(yīng)度最高的個(gè)體temp進(jìn)行對(duì)比，若temp的適應(yīng)度大于best，則用temp替換掉精英個(gè)體best。

步驟4遺傳操作形成新種群：

（1）使用輪盤賭選擇法選擇兩個(gè)進(jìn)化個(gè)體；

（2）組合交叉，求兩個(gè)進(jìn)化個(gè)體的相似度u，若u≤u0時(shí)，使用單點(diǎn)交叉，若u＞u0時(shí)，使用整合交叉；

（3）變異，首先從進(jìn)化個(gè)體中選出一個(gè)變異點(diǎn)，然后從非中心點(diǎn)集合中選取一個(gè)替換掉變異點(diǎn)的內(nèi)容；

（4）父子競爭。

步驟5判斷是否滿足終止條件，若是，則結(jié)束，否則轉(zhuǎn)步驟2。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證EG K CA聚類的有效性，實(shí)驗(yàn)將其與K-medoids算法和標(biāo)準(zhǔn)遺傳K-medoids聚類算法（Standard Genetic K-medoids Clustering Algorithm，SG K CA）進(jìn)行對(duì)比。其中SG K CA算法除了編碼方式與EG K CA相同，交叉變異需要避免重復(fù)之外，其他操作與標(biāo)準(zhǔn)遺傳算法相同。本文分別選擇4個(gè)人工數(shù)據(jù)集和4個(gè)從UCI挑選的真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

3.1 真實(shí)的數(shù)據(jù)集

本文從UCI中分別選取了兩個(gè)數(shù)據(jù)型數(shù)據(jù)集和兩個(gè)分類屬性數(shù)據(jù)集[1]。兩個(gè)數(shù)據(jù)型數(shù)據(jù)集分別為Iris和Wine；兩個(gè)分類屬性數(shù)據(jù)集為Zoo和Soybean。4個(gè)數(shù)據(jù)集的大體內(nèi)容如表1所示。

表1 真實(shí)數(shù)據(jù)集的描述

本文為EG K CA和SG K CA設(shè)置的迭代次數(shù)為200代，將3個(gè)算法分別運(yùn)行20次得到的聚類代價(jià)結(jié)果如表2所示。由表2可知，相對(duì)于K-medoids和SG K CA，EG K CA對(duì)4個(gè)數(shù)據(jù)集求得聚類總代價(jià)的最大值、最小值和平均值均最小。對(duì)比K-medoids和SG K CA，除了Wine數(shù)據(jù)集中SG K CA求得的平均值優(yōu)于K-medoids外，其他均不如K-medoids。這也是一般遺傳算法容易陷入早熟現(xiàn)象的又一體現(xiàn)。而K-medoids算法本身為各個(gè)數(shù)據(jù)集求得的聚類代價(jià)的最大值和最小值也有一定的差距，這說明了K-medoids也具有一定的不穩(wěn)定性。

表2 3個(gè)算法在4個(gè)真實(shí)數(shù)據(jù)集中求得的聚類代價(jià)

對(duì)于聚類準(zhǔn)確性的判斷，本文使用Sun等人[15]提出的準(zhǔn)確率判定方法，具體判定方法如下：

其中，ai是出現(xiàn)在第i個(gè)類簇（執(zhí)行算法得到的）及其對(duì)應(yīng)類（初始類）中的樣本數(shù)；k為聚類簇的個(gè)數(shù)；L是樣品總數(shù)。3個(gè)算法求解真實(shí)數(shù)據(jù)集的平均準(zhǔn)確率見圖2。由圖2可知，對(duì)比K-medoids和SG K CA，在Wine和Zoo中兩者的平均準(zhǔn)確率有少許差別，而在Iris和Soybean中兩者的平均準(zhǔn)確率一致。在這4個(gè)數(shù)據(jù)集中，EG K CA求得的平均準(zhǔn)確率均高于K-medoids和SG K CA。從而說明了EG K CA聚類更加準(zhǔn)確。

圖2 真實(shí)數(shù)據(jù)集求解的平均準(zhǔn)確率分布圖

3個(gè)算法對(duì)4個(gè)真實(shí)數(shù)據(jù)集求解10次得到的最優(yōu)聚類代價(jià)如圖3～圖6所示。對(duì)于這4個(gè)真實(shí)數(shù)據(jù)集，EG K CA求得的聚類代價(jià)最優(yōu)、最為穩(wěn)定。K-medoids和SG K CA求得的聚類代價(jià)均大于EG K CA，且均有一定的不穩(wěn)定性。

圖3 Iris中求解10次的聚類代價(jià)分布圖

圖4 Wine中求解10次的聚類代價(jià)分布圖

圖5 Soybean中求解10次的聚類代價(jià)分布圖

圖6 Zoo中求解10次的聚類代價(jià)分布圖

3.2 人工數(shù)據(jù)集

為了驗(yàn)證聚類算法在不同數(shù)據(jù)分布下的聚類效果，本文設(shè)計(jì)了4個(gè)人工數(shù)據(jù)集[5]：人工數(shù)據(jù)集1（AD1）是測(cè)試類簇間距離較大時(shí)的聚類；人工數(shù)據(jù)集2（AD2）是測(cè)試類簇間距離較小且存在邊界重合時(shí)的聚類；人工數(shù)據(jù)集3（AD3）是測(cè)試大類中包含小類時(shí)的聚類；人工數(shù)據(jù)集4（AD4）是測(cè)試存在多個(gè)類時(shí)的聚類。4個(gè)數(shù)據(jù)集的分布情況如圖7，大致狀況如表3所示。

圖7 人工數(shù)據(jù)集的分布圖

表3 人工數(shù)據(jù)集的描述

表4 各算法對(duì)人工數(shù)據(jù)集聚類情況

3個(gè)算法對(duì)4個(gè)人工數(shù)據(jù)集求解10次得到的最優(yōu)聚類代價(jià)如圖8～圖11所示。對(duì)于這4個(gè)人工數(shù)據(jù)集，EG K CA求得的聚類代價(jià)最優(yōu)、最為穩(wěn)定。K-medoids和SG K CA求得的聚類代價(jià)均大于EG K CA，且均有一定的不穩(wěn)定性。

圖8 AD1中求解10次的聚類代價(jià)分布圖

圖9 AD2中求解10次的聚類代價(jià)分布圖

圖10 AD3中求解10次的聚類代價(jià)分布圖

圖11 AD4中求解10次的聚類代價(jià)分布圖

4 總結(jié)

本文針對(duì)傳統(tǒng)K-medoids算法尋優(yōu)能力差，求解結(jié)果不穩(wěn)定等問題，提出了精英遺傳K-medoids聚類算法。該算法通過精英策略增加種群全局收斂性；通過引入以種群適應(yīng)度為基礎(chǔ)生成的若干隨機(jī)個(gè)體減少了早熟現(xiàn)象的影響；通過組合交叉的方式提高了進(jìn)化效率；通過父子競爭一定程度上控制了遺傳算法自身隨機(jī)性帶來的消極影響。8個(gè)不同的數(shù)據(jù)集的測(cè)試結(jié)果證明了該算法對(duì)不同分布情況的數(shù)據(jù)集均有較好的聚類效果，結(jié)果也比較穩(wěn)定。

目前不存在普遍適用的聚類算法，因此，未來的研究方向還應(yīng)放在如何處理含有多個(gè)離群點(diǎn)或分布規(guī)律不明顯的數(shù)據(jù)集的聚類上。