一種改進(jìn)的小生境遺傳聚類算法

一種瞄的小生境遺傳聚類算法孫紅艷;王英博【摘要】傳統(tǒng)的遺傳算法具有早熟收斂和后期收斂速度慢的缺點(diǎn)，采用改進(jìn)的小生境技術(shù)解決這一問題，同時(shí)根據(jù)具體問題改進(jìn)了遺傳算子.并將改進(jìn)后的小生境遺傳算法應(yīng)用于聚類挖掘中.由于聚類挖掘算法中的K-means算法對初始值K的選取敏感，選取值的不同會導(dǎo)致聚類結(jié)果的不同，很容易陷入局部最優(yōu),使得聚類結(jié)果很差.因此,將改進(jìn)的小生境遺傳算法和K-means算法相結(jié)合，得出一種改進(jìn)的小生境遺傳聚類算法.驗(yàn)證表明優(yōu)該算法對提高聚類分析質(zhì)量是有效的.【期刊名稱】《計(jì)算機(jī)系統(tǒng)應(yīng)用》【年(卷)，期】2010(019)002【總頁數(shù)】4頁(P37-40)【關(guān)鍵詞】小生境技術(shù);聚類挖掘;K-means算法;小生境遺傳算法【作者】孫'紅艷;王英博【作者單位】遼寧工程技術(shù)大學(xué)，電子與信息工程學(xué)院，遼寧，葫蘆島,125105;遼寧工程技術(shù)大學(xué)，電子與信息工程學(xué)院，遼寧，葫蘆島,125105【正文語種】中文1引言傳統(tǒng)遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化搜索算法。生物的進(jìn)化過程主要是通過染色體之間的交叉和變異來完成的，與此相對應(yīng)，遺傳算法中最優(yōu)解的搜索過程也模仿生物的進(jìn)化過程，使用遺傳操作數(shù)作用于群體進(jìn)行遺傳操作，從而得到新一代群體，其本質(zhì)是一種求解問題的高效并行全局搜索算法。但是傳統(tǒng)的遺傳算法也存在一些缺陷，早熟收斂和后期收斂速度慢是影響其應(yīng)用的兩個(gè)主要問題。基因缺失被認(rèn)為是造成早熟收斂的主要原因，采用多樣度、成熟度可以標(biāo)志種群的早熟狀況，利用基因補(bǔ)償、自適應(yīng)交叉和變異率等技術(shù)可以有效防止早熟［1,2］。防止早熟的另一種有效技術(shù)是小生境技術(shù)［3-5］,這是模擬生態(tài)平衡的一種仿生技術(shù)，即有限的生存資源只能容納有限的生物數(shù)量.這種算法適用于多峰函數(shù)的優(yōu)化計(jì)算有多種實(shí)現(xiàn)方法，其中之一是利用排擠思想，即限制相似個(gè)體的數(shù)量。共享函數(shù)和罰函數(shù)方法是這一思想的具體實(shí)現(xiàn)［6］。雖然小生境技術(shù)有很大的優(yōu)點(diǎn)，但是其本身也有一定的缺點(diǎn)，小生境初始群體的生成是隨機(jī)的，這會對結(jié)果有一定的影響，本文針對這個(gè)弱點(diǎn)進(jìn)行了改進(jìn)。聚類是一種有效的數(shù)據(jù)挖掘方法，其算法有很多，比較典型的有K-means算法。K-means算法具有簡單和高效性，在聚類中占有重要地位。該算法要根據(jù)事先確定的K值，把待聚類樣本分為K類，使聚類域中所有樣本到聚類中心的距離平方和最小。由于以上優(yōu)點(diǎn)，K-means聚類算法己經(jīng)應(yīng)用到各種領(lǐng)域，包括圖像和語音數(shù)據(jù)壓縮、模式識別、數(shù)據(jù)分析等。本文將改進(jìn)的小生境遺傳算法來優(yōu)化K-means算法，以達(dá)到更好的聚類效果。2小生境技術(shù)2.1小生境技術(shù)的基本思想在自然界中，〃人以群分，物以類聚”是一種正常的自然現(xiàn)象，生物體總是趨向于與自己特征、性狀相似的生物生活在一起，進(jìn)行交配、繁殖。這種交配方式在生物遺傳進(jìn)化過程中，起到了積極的作用。在生物學(xué)上，小生境(niching)是指在特定環(huán)境中一種組織的功能，而把有共同特性的組織稱為物種。小生境技術(shù)就是將每一代遺傳個(gè)體分成若干類，每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群，再在種群中以及不同的種群間通過雜交、變異產(chǎn)生新一代個(gè)體群?；谶@種小生境的遺傳算法由于可以更好的保持解的多樣性，已在復(fù)雜的多峰值函數(shù)求解過程中得到了一定的應(yīng)用。但是小生境初始群體的產(chǎn)生是隨機(jī)的會影響算法的性能，因此本文提出一種新的簡單策略。2.2小生境技術(shù)的更新策略針對初始群體的產(chǎn)生是隨機(jī)的這一缺點(diǎn)，本文采取新的策略來改善這一缺點(diǎn)。小生境群體中的個(gè)體都具有相似性，因此我們將群體中的所有個(gè)體xi(0<i<m),根據(jù)其適應(yīng)度函數(shù)f(x)計(jì)算出每個(gè)個(gè)體xi相對應(yīng)的適應(yīng)度，按照適應(yīng)度大小降序排列，然后按照給定的小生境容量w,從前往后按順序劃分出小生境群體。這樣小生境內(nèi)的個(gè)體的適應(yīng)度大小都差不多，很相似。3K-means算法的基本思想K-means算法以k為輸入?yún)?shù)，把n個(gè)對象的集合分為k個(gè)簇，使得簇內(nèi)的相似度高，而簇間的相似度低。簇的相似度是關(guān)于簇中對象的均值度量，可以看作簇的質(zhì)心(centroid)或重心(centerofgravity)。算法首先隨機(jī)選擇k個(gè)對像，每個(gè)對像初始地代表了一個(gè)簇的平均值或中心，對剩余的每個(gè)對象根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇，然后重新計(jì)算每個(gè)簇的平均值，不斷重復(fù)該過程，直到準(zhǔn)則精心策劃收斂。準(zhǔn)則函數(shù)如下：K-means算法的描述如下：任意選擇k個(gè)記錄作為初始的聚類中心。計(jì)算每個(gè)記錄與k個(gè)聚類中心的距離，并將距離最近的聚類作為該點(diǎn)所屬的類。計(jì)算每個(gè)聚集的質(zhì)心(聚集點(diǎn)的均值)以及每個(gè)對象與這些中心對象的距離，并根據(jù)最小距離重新對相應(yīng)的對象進(jìn)行劃分。重復(fù)該步驟，直到式(1)不再明顯地發(fā)生變化。4改進(jìn)的小生境遺傳算法與K-means聚類算法相結(jié)合本文將改進(jìn)的小生境遺傳算法應(yīng)用到聚類挖掘中，把小生境遺傳算法的全局優(yōu)化能力與聚類分析的局部優(yōu)化能力相結(jié)合來優(yōu)化聚類分析算法的局部性。K-means算法對初值K的選取敏感，會影響到聚類結(jié)果的質(zhì)量，因此，在種群進(jìn)化中，引入K-means操作，同時(shí)為了避免早熟現(xiàn)象，采用小生境技術(shù)，讓種群中的個(gè)體不是聚集在一種環(huán)境中，而在不同特定的生存環(huán)境中進(jìn)化。這樣可以使算法在整個(gè)解空間中搜索，以找到更多的最優(yōu)個(gè)體，避免在進(jìn)化后期適應(yīng)度高的個(gè)體大量繁殖，充斥整個(gè)解空間，導(dǎo)致算法停止在局部最優(yōu)解上。該算法具體步驟如下。4.1染色體編碼的構(gòu)成由于聚類算法具有多維性、數(shù)量多等特點(diǎn)，聚類問題的樣本數(shù)目一般遠(yuǎn)大于其聚類數(shù)目，因此采用基于聚類中心的浮點(diǎn)數(shù)編碼，將各個(gè)類別的中心編碼為染色體。這種基于聚類中心的編碼方式縮短了染色體的長度，提高了遺傳算法的速度，對求解大量數(shù)據(jù)的復(fù)雜聚類問題效果較好。舉例：若某一個(gè)優(yōu)化問題含有5個(gè)變量xi(i=12...5),每個(gè)變量都有其對應(yīng)的上下限，則X:就表示一個(gè)體的基因型其對應(yīng)的表現(xiàn)型是：x=。4.2初始群體的獲得為了獲得全局最優(yōu)解，初始群體完全隨機(jī)生成。先將每個(gè)樣本指派為某一類作為最初的聚類劃分，并計(jì)算各類的聚類中心作為初始個(gè)體的染色體編碼串，共生成m個(gè)初始個(gè)體，由此產(chǎn)生第一代種群。4.3適度度函數(shù)的選取適應(yīng)度通常用來度量群體中各個(gè)體在優(yōu)化計(jì)處中可能達(dá)到或接近于最優(yōu)解的優(yōu)良程度。本算法采用式(1)構(gòu)適應(yīng)度函數(shù)，同于式(1)的值越小說明聚類結(jié)果越好，越大說明聚類結(jié)果越差，因此選擇如下的適應(yīng)度函數(shù)[7]:其中，b為常數(shù)，可以根據(jù)具體問題作調(diào)整。E為聚類準(zhǔn)則函數(shù)，即上面式子(1)。根據(jù)各個(gè)個(gè)體的適應(yīng)度大小對其進(jìn)行降序排列記憶前n個(gè)個(gè)體(n<m)。4.4遺傳算子的構(gòu)成及改進(jìn)傳統(tǒng)的遺傳算法存在著早熟收斂和后期收斂速度慢的弱點(diǎn)，小生境遺傳算法是一種新穎的遺傳算法。在遺傳算法的操作算子中，選擇算子起到啟發(fā)進(jìn)化方向的作用，交叉算子起到全局搜索的作用，而變異算子通常被認(rèn)為是一種背景操作或輔助操作，它能夠以大于0的概率找回丟失的優(yōu)良基因。4.4.1選擇算子的構(gòu)成本文采用兩種選擇算子。在小生境中，我們采用仙+入)選擇機(jī)制，它被認(rèn)為是進(jìn)化算法幾種流行的選擇機(jī)制中選擇壓最高的一種。當(dāng)在種群中進(jìn)行隨機(jī)配對的交叉操作時(shí)，^+入)選擇機(jī)制能產(chǎn)生最快的局部收斂速度。⑴+入)選擇策略是指在M個(gè)父代個(gè)體和由這M個(gè)個(gè)體交叉產(chǎn)生的入個(gè)子個(gè)體中選擇M個(gè)最佳個(gè)體。在整個(gè)的大群體中本文采用最優(yōu)保存策略。4.4.2交叉算子的構(gòu)成因?yàn)閭€(gè)體的染色體編碼是浮點(diǎn)數(shù)編碼方法，所以交叉操作采用算術(shù)交叉算子，即由兩個(gè)個(gè)體的線性組合而產(chǎn)生出兩個(gè)新的個(gè)體。例如：假設(shè)在兩個(gè)個(gè)體、之間進(jìn)行算術(shù)交叉，則交叉后所產(chǎn)生出的兩個(gè)新個(gè)體是：式中，a為一參數(shù)，這可以是一個(gè)常數(shù)，也可以是一個(gè)由進(jìn)化代數(shù)所決定的變量，分別稱為均勻算術(shù)交叉和非均勻算術(shù)交叉。4.4.3變異算子的改進(jìn)本文采用2種變異算子［8］。第一種是均勻變異，該變異算子運(yùn)用在算法的初期運(yùn)行階段，它使得搜索點(diǎn)可以在整個(gè)搜過空間內(nèi)自由地移動，從而可以增加群體的多樣性，使算法處理更多多的模式。例如：假設(shè)有一個(gè)體為X=x1x2...xk...xl若xk為變異點(diǎn)，其取值范圍為,在該點(diǎn)對個(gè)體X進(jìn)行均勻變異操作后，可得到一個(gè)新的個(gè)體X=x1...x2...x'k...xl，其中變異點(diǎn)的新基因值是=+「(-):式中，r為［0，1］范圍內(nèi)符合均勻概率分布的一個(gè)隨機(jī)數(shù)。第二種采用自適應(yīng)調(diào)整算隨機(jī)變異，該算子用在算法的后期運(yùn)行階段。但當(dāng)變異的個(gè)體為子種群中的最佳個(gè)體時(shí)，對該最佳個(gè)體及由其變異所得新個(gè)體進(jìn)行(1+1)選擇以保證最優(yōu)個(gè)體以概率1保留到下一代。4.5弓|入K-means操作先以變異后產(chǎn)生的新群體的編碼值為中心，把每個(gè)數(shù)據(jù)點(diǎn)分配到最近的類，形成新的聚類劃分。然后按照新的聚類劃分，計(jì)算新的聚類中心，取代原來的編碼值［7］。由于K-means算法具有較強(qiáng)的局部搜索能力，因此引入K-means操作后，遺傳算法的收斂速度可以大大提高。4.6進(jìn)化結(jié)束條件進(jìn)化代數(shù)初始化為0，每進(jìn)化一次，即循環(huán)一次，代數(shù)加1,若當(dāng)前進(jìn)化代數(shù)小于規(guī)定的代數(shù)，則繼續(xù)進(jìn)化，否則結(jié)束進(jìn)化。4.7本文算法步驟描述用改進(jìn)的小生境遺傳算法優(yōu)化后的K-means算法步驟描述如下：STEP1:設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器，隨機(jī)生成規(guī)模為m的初始種群；STEP2:計(jì)算個(gè)體適應(yīng)度值并降序排序；〃根據(jù)排序選擇相鄰若干個(gè)個(gè)體進(jìn)入一個(gè)小生境STEP3:While(不滿足結(jié)束條件)STEP4:計(jì)算大種群個(gè)體方差D，若D2。則設(shè)置子種群規(guī)模n(nvm,是關(guān)于D的一個(gè)函數(shù))，否則n=2;依據(jù)本文中的小生境新策略找出n個(gè)個(gè)體形成子種群；//自適應(yīng)策略的關(guān)鍵步驟，子種群規(guī)模的確定隨種群多樣性的變化而自適應(yīng)變化。根據(jù)種群多樣性的變化通過閾值。控制實(shí)時(shí)確定子種群規(guī)模。STEP5:子種群內(nèi)個(gè)體進(jìn)行算術(shù)交叉，并進(jìn)行仙+入)選擇；STEP6:用本文采用的兩種變異算子進(jìn)行變異，若變異個(gè)體為最優(yōu)個(gè)體則進(jìn)行(1+1)選擇；STEP7:EndWhileSTEP8:計(jì)算新一代群體的適應(yīng)度，以最大適應(yīng)度的最佳個(gè)體為中心進(jìn)行K-means聚類。STEP9:輸出結(jié)果。5實(shí)驗(yàn)結(jié)果與分析本文對原始K-means算法，傳統(tǒng)遺傳算法優(yōu)化的K-means算法以及本文的算法進(jìn)行了聚類挖掘?qū)Ρ闰?yàn)證。實(shí)驗(yàn)數(shù)據(jù)為一組合成數(shù)據(jù)和兩組實(shí)際數(shù)據(jù)。合成數(shù)據(jù)集為二維分布數(shù)據(jù)集(0,0),(0,1),(1,0),(1,1),(2,1),(1,2),(2,2),(3,2),(1,4),(1,5),(1,6),(2,4),(2,5),(6,6),(6,7),(7,6),(7,7),(7,8),(8,6),(8,7),(8,8),(8,9),(9,7),(9,8),(9,9)用Matlab仿真共分為三類。數(shù)據(jù)分布如圖1所示。圖1二維數(shù)據(jù)聚類結(jié)果實(shí)際數(shù)據(jù)來自UCImachinelearningrepository數(shù)據(jù)庫，所選的數(shù)據(jù)集是著名的Iris數(shù)據(jù)集和glass數(shù)據(jù)集，在TurboC環(huán)境下導(dǎo)入數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。根據(jù)表1的試驗(yàn)結(jié)果分析，K-means算法的初始聚類中心的選取對聚類結(jié)果影響較大，得到的聚類最優(yōu)解最差，準(zhǔn)確率也最低，而傳統(tǒng)遺傳算法優(yōu)化的K-means算法相對較好—些，但是準(zhǔn)確率也不是很高。相比之下，本文算法得到的聚類結(jié)果是最好，準(zhǔn)確率也是最高的。6結(jié)語本文針對傳統(tǒng)遺傳算法早熟收斂和收斂速度慢的缺點(diǎn)采用了改進(jìn)的小生境技術(shù)，并且概據(jù)具體問題改進(jìn)了遺傳算子，通過閾值實(shí)時(shí)控制子種群規(guī)模，并將改進(jìn)的小生境遺傳算法應(yīng)用于聚類分析中，針對K-means聚類算法對初始值K選取的敏感問題，把小生境遺傳算法和K-means聚類算法相結(jié)合。該算法采用基于聚類中心的編碼方案，減少了染色體的編碼長度，使得聚類效果更好。表1算法性能測試結(jié)果【相關(guān)文獻(xiàn)】TianFH,ZhouCG,TianLH.Preventionagainstallellackingeneticalgorithm.Mini-MicroSystems,2000,21(9)947-949.LiSQ,ZhaoLY,ShiZX,etal.Aneffectivemethodofpreventingprematurityofgeneticalgorithm.SytemsEngineering--Theory&Practice,1999,19(5):72-76.ZhouM,SunSD.Principleofgeneticalgorithmanditsapplications.Beijing:DefenseIndustryPress,1999,6.HaoX,LiRH.Multi-populationgeneticalgorithmforcomplexfunctionoptimization.ControlandDecision,1998,13(3):263-2