宋飛豹，賈瑞玉

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

1 引言

聚類分析一直是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識別等領(lǐng)域的重要研究內(nèi)容之一[1]。K-medoids算法作為應(yīng)用廣泛的聚類算法，近年來，關(guān)于K-medoids算法的研究越來越多。文獻(xiàn)[2]根據(jù)最大最小法則選出k個稠密區(qū)域，由此得到k個初始中心點(diǎn)，從而提升了K-medoids的聚類質(zhì)量；文獻(xiàn)[3]通過差分隱私保護(hù)技術(shù)使K-medoids能夠處理增量數(shù)據(jù)的動態(tài)聚類問題；文獻(xiàn)[4]通過引入距離加速理論提高了K-medoids聚類的效率。雖然K-medoids聚類算法對離群點(diǎn)的處理效果較好，但K-medoids算法依然存在著初始中心點(diǎn)敏感和聚類結(jié)果不穩(wěn)定等問題。為了解決這些問題，常見的方法是將遺傳算法與聚類算法相結(jié)合。文獻(xiàn)[5]按照最大屬性值范圍劃分法選擇聚類中心初值，同時運(yùn)用兩階段動態(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聚類的評價標(biāo)準(zhǔn)作為遺傳算法的適應(yīng)度函數(shù)。通過精英個體來保證算法的全局收斂性。同時每次進(jìn)化的進(jìn)化團(tuán)隊(duì)均通過種群的平均適應(yīng)度來引入若干隨機(jī)個體，以提高種群多樣性。通過組合交叉和父子競爭的操作提高進(jìn)化效率。最終通過測試8個具有一定代表性的數(shù)據(jù)集證明了EGKCA算法的聚類準(zhǔn)確率高，求解結(jié)果穩(wěn)定。

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

2.1 編碼方式

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

2.2 精英個體

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

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)生的聚類代價，其值越小，代表簇內(nèi)距離越小，簇間越緊湊獨(dú)立，聚類效果越好。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.6 變異

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

在變異過程中為了避免重復(fù)，首先從進(jìn)化個體Xi中選擇一個變異點(diǎn)sm(1≤sm≤k)，然后從與Xi相對應(yīng)的非中心點(diǎn)集合中，隨機(jī)找到一個非中心點(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)象的一個主要原因是交叉變異的不可控性。個體進(jìn)行交叉變異時，交叉變異的結(jié)果具有一定的隨機(jī)性，個體的適應(yīng)度有可能變得更好，也有可能變得更差。為了盡量控制個體的交叉變異向著一個比較正確的方向進(jìn)行，本文提出了一種父子競爭的操作。

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

2.8 EG K CA算法描述

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

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

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

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

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

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

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

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

（3）變異，首先從進(jìn)化個體中選出一個變異點(diǎn)，然后從非中心點(diǎn)集合中選取一個替換掉變異點(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)行對比。其中SG K CA算法除了編碼方式與EG K CA相同，交叉變異需要避免重復(fù)之外，其他操作與標(biāo)準(zhǔn)遺傳算法相同。本文分別選擇4個人工數(shù)據(jù)集和4個從UCI挑選的真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

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

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

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

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

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

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

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

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

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

圖3 Iris中求解10次的聚類代價分布圖

圖4 Wine中求解10次的聚類代價分布圖

圖5 Soybean中求解10次的聚類代價分布圖

圖6 Zoo中求解10次的聚類代價分布圖

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

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

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

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

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

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

圖8 AD1中求解10次的聚類代價分布圖

圖9 AD2中求解10次的聚類代價分布圖

圖10 AD3中求解10次的聚類代價分布圖

圖11 AD4中求解10次的聚類代價分布圖

4 總結(jié)

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

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