一種基于GA的聚類集成算法

何靈敏,潘益民

(中國計(jì)量學(xué)院信息工程學(xué)院,浙江杭州310018)

聚類是一種科學(xué)研究中經(jīng)常要用到的技術(shù),是認(rèn)知未知事物的重要手段,也一直是機(jī)器學(xué)習(xí)領(lǐng)域中一個(gè)活躍的研究方向.現(xiàn)有的聚類方法有不下數(shù)百個(gè),但都只適用于解決特定問題.尋找泛化性能好的聚類算法一直是研究者的一個(gè)努力目標(biāo).2000年左右,人們發(fā)現(xiàn)通過集成多個(gè)聚類結(jié)果,可構(gòu)造出一個(gè)集成的聚類結(jié)果.新構(gòu)造的聚類結(jié)果相比于原來單個(gè)聚類結(jié)果有更好的平均性能,且適用于處理多種問題.此后,聚類集成開始成為聚類研究的一個(gè)新方向.Topchy A.在他的論文[1]中將聚類集成的優(yōu)點(diǎn)概括為:魯棒性、適用性、穩(wěn)定性、并行性和可擴(kuò)展性.

聚類集成的思想主要是利用普通聚類算法生成的多個(gè)聚類結(jié)果,來構(gòu)造出一個(gè)更加優(yōu)秀的結(jié)果.每個(gè)聚類集成算法都由以下兩個(gè)部分組成:基聚類算法和一致性函數(shù)(也稱為共識(shí)函數(shù)).基聚類算法用于對(duì)同一個(gè)待聚類數(shù)據(jù)產(chǎn)生多個(gè)聚類結(jié)果.這些產(chǎn)生的聚類結(jié)果所組成的集合被稱為一個(gè)聚類集體.一致性函數(shù)是指用于從產(chǎn)生的聚類集體中得到一個(gè)最終聚類結(jié)果的算法.聚類集成算法的一般過程是先由基聚類算法產(chǎn)生一個(gè)聚類集體,然后使用一致性函數(shù)從聚類集體中計(jì)算出一個(gè)集成聚類結(jié)果.

近年來,聚類集成技術(shù)的研究取得了很多成果.按照文獻(xiàn)[2]的分類方法,現(xiàn)有的聚類集成算法大致可分為以下五類:(1)基于互聯(lián)合矩陣的方法;(2)基于互信息理論的方法;(3)基于圖形劃分問題的方法;(4)基于有限混合模型的方法;(5)基于投票的方法.這些方法從不同的角度入手,解決了如何產(chǎn)生一個(gè)集成聚類結(jié)果的問題.但是這些方法都存在著各自的局限性.

總結(jié)前人研究的經(jīng)驗(yàn)和成果,本文提出一種基于GA(genetic algorithm)的集成算法(ECUNGA).該算法本質(zhì)上屬于基于互信息理論的方法,使用平均互信息(normal mutual information,NMI)表示兩個(gè)聚類結(jié)果之間的相似度,以GA作為共識(shí)函數(shù),搜索一個(gè)與聚類集體差異度最小的聚類.我們借用了成熟的GA算法搜索集成聚類結(jié)果,使算法不易陷入局部解,并在UCI數(shù)據(jù)進(jìn)行試驗(yàn),取得了良好的效果.

1 基聚類算法

目前常用的基聚類算法有很多,按照產(chǎn)生聚類差異性方法的不同,可以分成以下幾類[3]:(1)使用不同算法生成聚類集體;(2)使用同一算法不同參數(shù)生成聚類集體;(3)使用不同數(shù)據(jù)子集生成聚類集體;(4)使用不同特征子集生成聚類集體.

我們的基聚類算法采用經(jīng)典k-means方法,即通過隨機(jī)確定k-means算法的初始點(diǎn),運(yùn)行多次算法,得到所需要的聚類集體.采用k-means算法的優(yōu)點(diǎn)是算法簡(jiǎn)單、運(yùn)行速度快.在實(shí)驗(yàn)中與k-means算法進(jìn)行比較,可以證明集成算法的有效性.

2 一致性函數(shù)

一致性函數(shù)是本算法設(shè)計(jì)的重點(diǎn),設(shè)計(jì)的核心思想是利用GA搜索一個(gè)與聚類集體最統(tǒng)一的聚類結(jié)果.統(tǒng)一度則由到聚類集體中每個(gè)聚類的NMI值之和定義.其中NMI的定義形式如下:

其中ka和kb是聚類φa和φb中類的個(gè)數(shù);nh,l是同時(shí)在φa的h類中和φb的l類中點(diǎn)的個(gè)數(shù);nh是在 φa的h類中點(diǎn)的個(gè)數(shù);nl是在φb的l類中點(diǎn)的個(gè)數(shù).NMI的值介于0到1之間.

一致性函數(shù)的算法結(jié)構(gòu)描述如下:

Begin

Step 1.firstTime=true;

Step 2.t=0;if(firstTime=true)執(zhí)行初始化種群方法1得到P(t);轉(zhuǎn)到Step 4;

Step 3.執(zhí)行做初始化種群方法2得到P(t);

Step 4.計(jì)算種群P(t)中元素的適應(yīng)度;令t=t+1;

Step 5.判斷是否滿足停止條件,如果滿足則停止并轉(zhuǎn)到step 9;

Step 6.根據(jù)計(jì)算的適應(yīng)度,從種群P(t-1)中選擇個(gè)體進(jìn)行交叉操作;

Step 7.隨機(jī)從種群P(t-1)中選擇少量個(gè)體進(jìn)行變異操作;

Step 8.用新產(chǎn)生的個(gè)體組成新種群P(t);轉(zhuǎn)到Step 2;

Step 9.記錄最好的個(gè)體和適應(yīng)度值;

Step 10.if(firstTime==true)time=false;轉(zhuǎn)到Step 1;

Step 11.比較得到的所有最好個(gè)體,選擇一個(gè)適應(yīng)度最高的個(gè)體輸出;停止.End

從算法結(jié)構(gòu)可以看出,我們的一致性函數(shù)主體是具有兩個(gè)初始種群產(chǎn)生方法的GA算法.下面從GA算法的各個(gè)部分進(jìn)行具體描述:

為了表達(dá)的方便,先對(duì)下面需要用到的符號(hào)進(jìn)行定義:D表示待聚類數(shù)據(jù)總體,m表示D中的數(shù)據(jù)點(diǎn)的個(gè)數(shù),Di表示第i個(gè)數(shù)據(jù).C表示D的一個(gè)聚類結(jié)果,k表示C中的聚類個(gè)數(shù),Cj表示C中第j個(gè)聚類.R表示基聚類算法得到的聚類集體.

1)編碼與解碼

個(gè)體編碼形式如下:

xn的取值表示該數(shù)據(jù)點(diǎn)屬于的聚類.如xi=j,就表示Di屬于Cj.

2)初始種群產(chǎn)生

算法使用的初始種群產(chǎn)生方法共有兩個(gè),分別用在兩次單個(gè)遺傳算法中.兩個(gè)方法都可以描述如下:

算法都使用已經(jīng)用其他單個(gè)算法得到的聚類結(jié)果集R作為產(chǎn)生初始種群的基礎(chǔ),采用有放回的抽樣技術(shù)從R中抽樣出n個(gè)聚類結(jié)果,其中,n是設(shè)定的初始種群的大小.然后我們?cè)賹?duì)抽樣出的聚類結(jié)構(gòu)進(jìn)行隨機(jī)化處理,即在每個(gè)聚類結(jié)果中隨機(jī)選出s%的數(shù)據(jù)進(jìn)行隨機(jī)賦值.s被稱為初始化隨機(jī)參數(shù),它的取值會(huì)影響收斂速度和搜索全局解的能力.

對(duì)于種群產(chǎn)生方法1,s的取值為0.

對(duì)于種群產(chǎn)生方法2,s的取值根據(jù)問題不同自定義,一般取20左右.

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

我們用個(gè)體到其他個(gè)體的NMI值之和作為適應(yīng)度函數(shù),形式如下:

其中,n是設(shè)定的初始種群的大小,Xi表示種群中第i個(gè)個(gè)體,Rj表示R中第j個(gè)聚類結(jié)果.

4)交叉操作

交叉操作是設(shè)計(jì)聚類集成算法的難點(diǎn),因?yàn)楦鱾€(gè)聚類結(jié)果中的相同標(biāo)簽值都有可能表示不同含義,所以不能采用普通的單點(diǎn)交叉或多點(diǎn)交叉.我們?cè)O(shè)計(jì)的交叉操作,如圖1.

5)變異操作

采用單點(diǎn)變異法,即選擇一個(gè)變異點(diǎn),隨機(jī)產(chǎn)生一個(gè)隨機(jī)聚類標(biāo)簽進(jìn)行替換.

6)GA搜索停止條件

GA搜索停止條件共有兩個(gè),滿足任意一個(gè)條件,GA搜索將停止.條件一是GA搜索超過了設(shè)定的最大允許代數(shù).條件二是GA搜索最大停滯代數(shù)達(dá)到最大允許值.

圖1 交叉操作流程圖Figure 1 Flow chart of crossover

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

為了說明ECUNGA算法的有效性,我們使用UCI數(shù)據(jù)集在MATLAB 7.0環(huán)境下進(jìn)行實(shí)驗(yàn).

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

實(shí)驗(yàn)使用選自 UCI數(shù)據(jù)集的5個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),所選的數(shù)據(jù)集都為完整的數(shù)值型數(shù)據(jù)集.詳細(xì)信息,如表1.

表1 實(shí)驗(yàn)數(shù)據(jù)集描述Table 1 Description of experimental data sets

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

實(shí)驗(yàn)采用正確率作為衡量算法的標(biāo)準(zhǔn).為了分別說明算法的有效性和對(duì)聚類集體數(shù)量對(duì)算法的影響力,實(shí)驗(yàn)分為兩部分進(jìn)行.

3.2.1 算法有效性實(shí)驗(yàn) 在本實(shí)驗(yàn)中算法ECUNGA的聚類集體的大小設(shè)置為40,種群產(chǎn)生方法2的初始化隨機(jī)參數(shù)為20,GA最大允許代數(shù)為500,最大允許停滯代數(shù)為50.使用ECUNGA算法得到的聚類結(jié)果與使用k-means算法得到的聚類結(jié)果進(jìn)行比較.以10次計(jì)算的平均正確率做比較,結(jié)果如表2.

表2 有效性實(shí)驗(yàn)結(jié)果Table 2 Experimental result

從實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn),在以上5組數(shù)據(jù)上,ECUNGA算法計(jì)算的正確率都高于簡(jiǎn)單k-means算法計(jì)算的正確率.這表明ECUNGA可以有效的集成聚類集體的有用信息,構(gòu)造出更加優(yōu)秀的聚類結(jié)果.

3.2.2 聚類集體規(guī)模對(duì)算法影響力的實(shí)驗(yàn) 在本實(shí)驗(yàn)中算法ECUNGA的聚類集體的大小分別設(shè)置為 5、10、20、40,其它參數(shù)設(shè)置同上.實(shí)驗(yàn)在Iris、Wine和Glass數(shù)據(jù)集上進(jìn)行,比較結(jié)果的10次平均正確率在不同規(guī)模聚類集體下的差異,其結(jié)果如表3.

表3 聚類集體規(guī)模對(duì)算法影響力實(shí)驗(yàn)結(jié)果Table 3 Result of collective size influence on clustering algorithm experiment

從實(shí)驗(yàn)中可以發(fā)現(xiàn)算法在數(shù)據(jù)集Iris和Wine上對(duì)聚類集體的規(guī)模不敏感,而在Glass數(shù)據(jù)集上聚類集體的規(guī)模小于20時(shí)算法不是很穩(wěn)定,最好和最壞結(jié)果相差比較大.所以算法在使用時(shí),應(yīng)產(chǎn)生規(guī)模在20以上的聚類集體,以保證算法穩(wěn)定性.

4 結(jié) 語

本文提出了一種基于GA的聚類集成算法(ECUNGA).算法使用k-means的固有隨機(jī)性,產(chǎn)生一個(gè)聚類集體.使用特別構(gòu)造的GA算法搜索一個(gè)到聚類集體平均NMI值最小的結(jié)果作為最終聚類.算法在UCI數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),取得了滿意的結(jié)果,證明了算法的有效性.

[1]TOPCHY A,JAIN A K,PUNCH W.A Mixture Model for Clustering Ensembles[C]∥Proceedings of the 4th SIAM International Conference on Data Mining.Florida:SIAM,2004:379-390.

[2]陽琳赟,王文淵.聚類融合方法綜述[J].計(jì)算機(jī)應(yīng)用研究,2005(12):8-11.

[3]羅會(huì)蘭,孔繁勝.聚類集成關(guān)鍵技術(shù)研究[D].杭州:浙江大學(xué),2007.

[4]陳秋靈,徐江峰.用遺傳算法搜索一維光子晶體帶隙[J].中國計(jì)量學(xué)院學(xué)報(bào),2007,18(1):70-74.

[5]李彬,張化祥.基于Bugging的聚類集成方法[J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31(1):164-166.

[6]GELBARD R,GO LDM AN O,SPIEG LER I.Investigating diversity of clustering methods[J].an Empirical Comparison Data&Knowledge Engineering,2007,63(1):155-166.

[7]李 科,田社平,王志斌.遺傳算法加權(quán)中值濾波器的優(yōu)化設(shè)計(jì)[J].中國計(jì)量學(xué)院學(xué)報(bào),2008,19(1):56-60.

[8]張曉菲,張火明.精英策略的改進(jìn)非支配遺傳算法[J].中國計(jì)量學(xué)院學(xué)報(bào),2010,21(1):52-58.

[9]楊 燕,靳 蕃,KAMEL M ohamed.聚類有效性評(píng)價(jià)綜述[J].計(jì)算機(jī)應(yīng)用研究,2008,25(6):1630-1638.

[10]李 凱,常圣領(lǐng),高 悅.基于聚類技術(shù)的集成學(xué)習(xí)算法研究[J].河北大學(xué)學(xué)報(bào):自然科學(xué)版,2009,29(2):209-213.