k均值課程設(shè)計---K均值聚類k-means優(yōu)化

1、K均值聚類（k-means）優(yōu)化基于遺傳算法一、K均值聚類的算法和遺傳算法的概述1 、K均值聚類（k-means）就是將對物理或抽象對象的集合分組成為由類似的對象組 成的多個簇的過程。聚類分析是指事先不知樣本的類別，而利用樣本的先驗知識來構(gòu)造分類器（無監(jiān)督學(xué)習(xí)），可以用兩個準(zhǔn)則來做（1）聚類準(zhǔn)則函數(shù)，（2）誤差平方和準(zhǔn)則（最常用的）c 2、遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化搜索算法。生物的進(jìn)化過程主要是通過染色體之間的交叉和變異來完成的，與此相對應(yīng)，遺傳算法中最優(yōu)解的搜索過程也模仿了生物的進(jìn)化過程，使用遺傳操作數(shù)作用于群體進(jìn)行遺傳操作，從而得到新一代群體，

2、其本質(zhì)是一種求解問題的高效并行全局搜索算法。它能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程， 從而得到最優(yōu)解或準(zhǔn)最優(yōu)解。算法以適應(yīng)度函數(shù)為依據(jù)，通過對群體個體施加遺傳操作實現(xiàn)群體內(nèi)個體結(jié)構(gòu)重組 的迭代處理。在這一過程中，群體個體一代代地優(yōu)化并逐漸逼近最優(yōu)解。鑒于遺傳算法的全局優(yōu)化性，本文給出了一種基于遺傳算法的K均值聚類算法來克服 K均值算法的局部性。二、K均值算法的基本思想K 均值算法是一種使用最廣泛的聚類算法。算法以 K為參數(shù)，把n個對象分為K個簇， 使簇內(nèi)具有較高的相似度， 而簇間相似度較低。 算法首先隨機選擇 K個對象，每個對象初始 地代表了一個簇的平均值或中

3、心， 對剩余的每個對象根據(jù)其與各個簇中心的距離， 將它賦給 最近的簇，然后重新計算每個簇的平均值，不斷重復(fù)該過程， 直到準(zhǔn)則函數(shù)收斂。準(zhǔn)則函數(shù) 如下：匯'fr=liC1其中，ix為簇C的平均值。i K均值算法的描述如下：（1）任意選擇K個記錄作為初始的聚類中心。（2）計算每個記錄與K個聚類中心的距離，并將距離最近的聚類作為該點所屬的類。（3）計算每個聚集的質(zhì)心（聚集點的均值）以及每個對象與這些中心對象的距離，并根據(jù)最小 距離重新對相應(yīng)的對象進(jìn)行劃分。重復(fù)該步驟，直到式（1）不再明顯地發(fā)生變化。三、基于遺傳算法的K均值聚類算法本文將遺傳算法應(yīng)用到聚類分析中， 把遺傳算法的全局優(yōu)化能力與聚

4、類分析的局部優(yōu)化 能力相結(jié)合來克服聚類算法的局部性，在種群進(jìn)化過程中，引入K均值操作，同時，為了避免早熟現(xiàn)象，在種群中采用自適應(yīng)方法動態(tài)調(diào)節(jié)交叉概率和變異概率，使其能夠隨適應(yīng)度自動改變。算法具體步驟如下。1染色體編碼染色體編碼有很多種，在聚類分析中較常用的是基于聚類中心的浮點數(shù)編碼和基于聚類劃分的整數(shù)編碼。由于聚類算法具有多維性、數(shù)量大等特點，聚類問題的樣本數(shù)目一般遠(yuǎn)大于其聚類數(shù)目，因此采用基于聚類中心的浮點數(shù)編碼，將各個類別的中心編碼為染色體。例如對于一個類別為 3的聚類問題，假設(shè)數(shù)據(jù)集為2維。初始的3個聚類中心點為(1, 2), (5, 4), (8, 7),則染色體編碼為(1,2, 5,

5、 4, 8, 7)。這種基于聚類中心的編碼方式縮短了染色體的長度，提高了遺傳算法的速度，對于求解大量數(shù)據(jù)的復(fù)雜聚類問題效果較好。2初始群體的產(chǎn)生為了獲得全局最優(yōu)解，初始群體完全隨機生成。先將每個樣本隨機指派為某一類作為最初的聚類劃分，并計算各類的聚類中心作為初始個體的染色體編碼串，共生成m個初始個體，由此產(chǎn)生第一代種群。3適應(yīng)度函數(shù)的選取適應(yīng)度通常用來度量群體中各個體在優(yōu)化計算中可能達(dá)到或接近于最優(yōu)解的優(yōu)良程度。本文采用式(1)構(gòu)造適應(yīng)度函數(shù)，由于式(1)的值越小說明聚類結(jié)果越好，越大說明聚類結(jié)果越差，因此選擇如下的適應(yīng)度函數(shù)：/ = &/(! + £)其中，b為常數(shù)，可以根

6、據(jù)具體問題作調(diào)整。4遺傳算子4.1 選擇算子采用適應(yīng)度比例法與最優(yōu)保存策略相結(jié)合的混合選擇算子。首先在每一代開始時，將群體中的最優(yōu)個體記錄下來，然后根據(jù)各個體的適應(yīng)度計算個體被選中的概率，用輪盤賭方法進(jìn)行個體的選擇，最后在每次遺傳操作后形成新群體時用當(dāng)前所記錄的最優(yōu)個體替換新群體 中的最差個體，以防止遺傳操作破壞當(dāng)前群體中適應(yīng)度最好的個體。4.2 交叉操作交叉操作是指對2個相互配對的染色體按某種方式相互交換部分基因，從而形成2個新的個體，提高遺傳算法的搜索能力。由于本文染色體采用浮點數(shù)編碼，因此采用適合浮點數(shù)編碼的算術(shù)交叉算子，即其中，a是一個(0,1)范圍內(nèi)的隨機數(shù)。4.3 變異操作變異是一

7、種局部隨機搜索，與選擇、交叉重組算子相結(jié)合可以保證遺傳算法的有效性，使其具有局部隨機搜索能力，同時保持種群的多樣性，防止非成熟收斂。 本文采用均勻變異算子，其具體操作過程是：對于每個變異點，從對應(yīng)基因位的取值范圍內(nèi)取一隨機數(shù)代替原 有基因值。即其中，r為(0, 1)范圍內(nèi)的隨機數(shù)；，分別是該基因位的數(shù)值上下限。maxU minU4.4 交叉率和變異率的自適應(yīng)調(diào)整標(biāo)準(zhǔn)的遺傳算法已經(jīng)被證明無法收斂到問題的全局最優(yōu)解，尤其是在種群分布不均勻時易出現(xiàn)未成熟收斂， 即“早熟現(xiàn)象”，在進(jìn)化中后期由于個體競爭減弱而引起的隨機搜索趨 勢還會導(dǎo)致算法收斂速度緩慢，其原因是進(jìn)化算子在整個進(jìn)化過程中都采用了固定的概

8、率 值。為了避免以上問題，本文采用了自適應(yīng)遺傳算子。自適應(yīng)遺傳參數(shù)的選擇如下：f w k f>f其中，avgf表示每代群體的平均適應(yīng)度值；maxf表示群體中的最大適應(yīng)度值；'f表示要交叉的2個個體中較大的適應(yīng)度值；f表示群體中要變異個體的適應(yīng)度值。對于適應(yīng)度大的個 體，賦予其相應(yīng)的交叉和變異概率，而對于適應(yīng)度小的個體，其交叉概率和變異概率較大，自適應(yīng)的交叉和變異概率能夠提供相對某個解最佳的cp和mp使自適應(yīng)遺傳算法在保持群體多樣性的同時，保證算法收斂。5 K均值操作先以變異后產(chǎn)生的新群體的編碼值為中心，把每個數(shù)據(jù)點分配到最近的類，形成新的聚類劃分。然后按照新的聚類劃分，計算新的聚

9、類中心，取代原來的編碼值。由于K均值具有較強的局部搜索能力，因此引入K均值操作后，遺傳算法的收斂速度可以大大提高。6循環(huán)終止條件循環(huán)代數(shù)開始為0,每循環(huán)一次，代數(shù)加 1,若當(dāng)前循環(huán)代數(shù)小于預(yù)先規(guī)定的最大循環(huán) 代數(shù)，則繼續(xù)循環(huán)；否則結(jié)束循環(huán)。7算法的設(shè)計(1)設(shè)置遺傳參數(shù)：聚類個數(shù)c,種群大小m,交叉概率cp,變異概率mp最大迭代代數(shù) T,適應(yīng)度倍數(shù)參數(shù)bo(2)隨機生成初始群體。(3)計算群體各個體的適應(yīng)度。(4)進(jìn)行選擇、交叉、變異、K均值操作，產(chǎn)生新一代群體。(5)重復(fù)第(3)、第(4)步，直到達(dá)到最大迭代代數(shù) To(6)計算新一代群體的適應(yīng)度，以最大適應(yīng)度的最佳個體為中心進(jìn)行K均值聚類。

10、輸出聚類結(jié)果。四、實驗結(jié)果與分析為了檢驗算法的有效性，對原始算法和改進(jìn)算法進(jìn)行了對比實驗。實驗數(shù)據(jù)來自給data的arff格式的文件數(shù)據(jù)，數(shù)據(jù)集分別是 iris , glass。優(yōu)化后算法的參數(shù)設(shè)置如下：種群大小m=3Q算法的最大迭代次數(shù) T=100,交叉概率1cp=0.9,2cp=0.6 ,變異概率 1mp=0.1,2mp=0.001, b=1 000 ,所有算法運行 20次，運行情況如表 1所示。根據(jù)表1的實 驗結(jié)果，K均值算法初始聚類中心的選取敏感性很大，容易陷入局部最小值，并不是每次都能得到最優(yōu)解，特別是對于glass這種較高維度的數(shù)據(jù)集，沒有一次達(dá)到全局最優(yōu)解。而改 進(jìn)的算法對每組數(shù)

11、據(jù)集的20次實驗均能收斂到最優(yōu)解，聚類效果較好。除數(shù)據(jù)集iris外,K均值算法每組數(shù)據(jù)收斂到最優(yōu)解的平均迭代次數(shù)都比本文算法多，所以，本文算法的收斂 速度也比較快。表1 K均值算法和優(yōu)化后算法的比較聚類算法數(shù) 逑 集Earn達(dá)到 最優(yōu) 解次數(shù)達(dá)到最 優(yōu)解的 平均送 代次數(shù)E的最優(yōu)解K均值Dacal13333 345.333 339M1 325Z05.333 33iris7S.945 07S.540 5278.942 31124 278 940 52必轉(zhuǎn)576.767 51336 290 S8395.045 980.336 063 50本文Daul5333 335.333 335.333 332

12、01.75333 33ms78.940 5278ao 5278.940 5220S37S.940 52shss336.063 50336 063 50336 063 502022.0336.063 50五、部分代碼在代碼中主要添加和修改幾個部分1、算中心距離private double EuclidDistance(int x,int y,int z)int i;double distance = 0;for(i=0; i<NA; i+)distance += pow( (instancex.pi - popz.clustercentery.pi),2 );distance = sqrt

13、(distance);return distance;private void CalcuateDistance(int p)int i;int j;for(i=0; i<NI; i+)(for(j=0; j<K; j+)(instancei.distancej = EuclidDistance(i,j,p);)2、簇函數(shù)private void Cluster(int p)(int i;int j;int index;double min;for(i = 0; i < K; i+)(clusteri.clear();)for(i = 0; i < NI; i+)(in

14、dex = 0;min = instancei.distance0;for(j = 1; j < K; j+)(if(instancei.distancej < min)(min = instancei.distancej; index = j;)clusterindex.push_back(i);)./*計算種群中個體適應(yīng)值*/popp.fitness = 0;for(i = 0; i<K; i+)(for(j=0; j<clusteri.size(); j+)(popp.fitness += pow(instanceclusterij.distancei,2);)3、交叉函數(shù)