一種改進的小生境遺傳聚類算法

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