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

1、<p>　　K均值聚類（k-means）優(yōu)化</p><p><b>　　——基于遺傳算法</b></p><p>　　一、 K均值聚類的算法和遺傳算法的概述</p><p>　　1、K均值聚類（k-means）就是將對(duì)物理或抽象對(duì)象的集合分組成為由類似的對(duì)象組成的多個(gè)簇的過程。聚類分析是指事先不知樣本的類別，而利用樣本的先驗(yàn)知識(shí)來構(gòu)

2、造分類器（無監(jiān)督學(xué)習(xí)），可以用兩個(gè)準(zhǔn)則來做(1)聚類準(zhǔn)則函數(shù)，(2)誤差平方和準(zhǔn)則（最常用的）。</p><p>　　2、遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化搜索算法。生物的進(jìn)化過程主要是通過染色體之間的交叉和變異來完成的，與此相對(duì)應(yīng)，遺傳算法中最優(yōu)解的搜索過程也模仿了生物的進(jìn)化過程，使用遺傳操作數(shù)作用于群體進(jìn)行遺傳操作，從而得到新一代群體，其本質(zhì)是一種求解問題的高效并行全局搜

3、索算法。它能在搜索過程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過程，從而得到最優(yōu)解或準(zhǔn)最優(yōu)解。算法以適應(yīng)度函數(shù)為依據(jù)，通過對(duì)群體個(gè)體施加遺傳操作實(shí)現(xiàn)群體內(nèi)個(gè)體結(jié)構(gòu)重組的迭代處理。在這一過程中，群體個(gè)體一代代地優(yōu)化并逐漸逼近最優(yōu)解。鑒于遺傳算法的全局優(yōu)化性，本文給出了一種基于遺傳算法的K均值聚類算法來克服K均值算法的局部性。</p><p>　　二、K均值算法的基本思想</p><

4、p>　　K均值算法是一種使用最廣泛的聚類算法。算法以K為參數(shù)，把n個(gè)對(duì)象分為K個(gè)簇，使簇內(nèi)具有較高的相似度，而簇間相似度較低。算法首先隨機(jī)選擇K個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的平均值或中心，對(duì)剩余的每個(gè)對(duì)象根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇，然后重新計(jì)算每個(gè)簇的平均值，不斷重復(fù)該過程，直到準(zhǔn)則函數(shù)收斂。準(zhǔn)則函數(shù)如下： </p><p>　　其中，ix為簇C的平均值。i</p>&l

5、t;p>　　K均值算法的描述如下： </p><p>　　(1)任意選擇K個(gè)記錄作為初始的聚類中心。</p><p>　　(2)計(jì)算每個(gè)記錄與K個(gè)聚類中心的距離，并將距離最近的聚類作為該點(diǎn)所屬的類。</p><p>　　(3)計(jì)算每個(gè)聚集的質(zhì)心(聚集點(diǎn)的均值)以及每個(gè)對(duì)象與這些中心對(duì)象的距離，并根據(jù)最小距離重新對(duì)相應(yīng)的對(duì)象進(jìn)行劃分。重復(fù)該步驟，直到式(1)不再

6、明顯地發(fā)生變化。</p><p>　　三、基于遺傳算法的K均值聚類算法</p><p>　　本文將遺傳算法應(yīng)用到聚類分析中，把遺傳算法的全局優(yōu)化能力與聚類分析的局部?jī)?yōu)化能力相結(jié)合來克服聚類算法的局部性，在種群進(jìn)化過程中，引入K均值操作，同時(shí)，為了避免早熟現(xiàn)象，在種群中采用自適應(yīng)方法動(dòng)態(tài)調(diào)節(jié)交叉概率和變異概率，使其能夠隨適應(yīng)度自動(dòng)改變。算法具體步驟如下。</p><p&g

7、t;<b>　　1 染色體編碼</b></p><p>　　染色體編碼有很多種，在聚類分析中較常用的是基于聚類中心的浮點(diǎn)數(shù)編碼和基于聚類劃分的整數(shù)編碼。由于聚類算法具有多維性、數(shù)量大等特點(diǎn)，聚類問題的樣本數(shù)目一般遠(yuǎn)大于其聚類數(shù)目，因此采用基于聚類中心的浮點(diǎn)數(shù)編碼，將各個(gè)類別的中心編碼為染色體。例如對(duì)于一個(gè)類別為3的聚類問題，假設(shè)數(shù)據(jù)集為2維。初始的3個(gè)聚類中心點(diǎn)為(1, 2), (5, 4)

8、, (8, 7)，則染色體編碼為(1, 2, 5, 4, 8, 7)。這種基于聚類中心的編碼方式縮短了染色體的長(zhǎng)度，提高了遺傳算法的速度，對(duì)于求解大量數(shù)據(jù)的復(fù)雜聚類問題效果較好。</p><p><b>　　2 初始群體的產(chǎn)生</b></p><p>　　為了獲得全局最優(yōu)解，初始群體完全隨機(jī)生成。先將每個(gè)樣本隨機(jī)指派為某一類作為最初的聚類劃分，并計(jì)算各類的聚類中心作為

9、初始個(gè)體的染色體編碼串，共生成m個(gè)初始個(gè)體，由此產(chǎn)生第一代種群。</p><p>　　3 適應(yīng)度函數(shù)的選取</p><p>　　適應(yīng)度通常用來度量群體中各個(gè)體在優(yōu)化計(jì)算中可能達(dá)到或接近于最優(yōu)解的優(yōu)良程度。本文采用式(1)構(gòu)造適應(yīng)度函數(shù)，由于式(1)的值越小說明聚類結(jié)果越好，越大說明聚類結(jié)果越差，因此選擇如下的適應(yīng)度函數(shù)： </p><p>　　其中，b為常數(shù)，可以根

10、據(jù)具體問題作調(diào)整。</p><p><b>　　4 遺傳算子</b></p><p><b>　　4.1 選擇算子</b></p><p>　　采用適應(yīng)度比例法與最優(yōu)保存策略相結(jié)合的混合選擇算子。首先在每一代開始時(shí)，將群體中的最優(yōu)個(gè)體記錄下來，然后根據(jù)各個(gè)體的適應(yīng)度計(jì)算個(gè)體被選中的概率，用輪盤賭方法進(jìn)行個(gè)體的選擇，最后在每

11、次遺傳操作后形成新群體時(shí)用當(dāng)前所記錄的最優(yōu)個(gè)體替換新群體中的最差個(gè)體，以防止遺傳操作破壞當(dāng)前群體中適應(yīng)度最好的個(gè)體。</p><p><b>　　4.2 交叉操作</b></p><p>　　交叉操作是指對(duì)2個(gè)相互配對(duì)的染色體按某種方式相互交換部分基因，從而形成2個(gè)新的個(gè)體，提高遺傳算法的搜索能力。由于本文染色體采用浮點(diǎn)數(shù)編碼，因此采用適合浮點(diǎn)數(shù)編碼的算術(shù)交叉算子，即

12、</p><p>　　其中，a是一個(gè)(0, 1)范圍內(nèi)的隨機(jī)數(shù)。</p><p><b>　　4.3 變異操作</b></p><p>　　變異是一種局部隨機(jī)搜索，與選擇、交叉重組算子相結(jié)合可以保證遺傳算法的有效性，使其具有局部隨機(jī)搜索能力，同時(shí)保持種群的多樣性，防止非成熟收斂。本文采用均勻變異算子，其具體操作過程是：對(duì)于每個(gè)變異點(diǎn)，從對(duì)應(yīng)基因

13、位的取值范圍內(nèi)取一隨機(jī)數(shù)代替原有基因值。即</p><p>　　其中，r為(0, 1)范圍內(nèi)的隨機(jī)數(shù)；,分別是該基因位的數(shù)值上下限。maxU，minU</p><p>　　4.4 交叉率和變異率的自適應(yīng)調(diào)整</p><p>　　標(biāo)準(zhǔn)的遺傳算法已經(jīng)被證明無法收斂到問題的全局最優(yōu)解，尤其是在種群分布不均勻時(shí)易出現(xiàn)未成熟收斂，即“早熟現(xiàn)象”，在進(jìn)化中后期由于個(gè)體競(jìng)爭(zhēng)減弱而

14、引起的隨機(jī)搜索趨勢(shì)還會(huì)導(dǎo)致算法收斂速度緩慢，其原因是進(jìn)化算子在整個(gè)進(jìn)化過程中都采用了固定的概率值。為了避免以上問題，本文采用了自適應(yīng)遺傳算子。自適應(yīng)遺傳參數(shù)的選擇如下：</p><p>　　其中，avgf表示每代群體的平均適應(yīng)度值；maxf表示群體中的最大適應(yīng)度值；'f表示要交叉的2個(gè)個(gè)體中較大的適應(yīng)度值；f表示群體中要變異個(gè)體的適應(yīng)度值。對(duì)于適應(yīng)度大的個(gè)體，賦予其相應(yīng)的交叉和變異概率，而對(duì)于適應(yīng)度小的個(gè)

15、體，其交叉概率和變異概率較大，自適應(yīng)的交叉和變異概率能夠提供相對(duì)某個(gè)解最佳的cp和mp，使自適應(yīng)遺傳算法在保持群體多樣性的同時(shí)，保證算法收斂。</p><p><b>　　5 K均值操作</b></p><p>　　先以變異后產(chǎn)生的新群體的編碼值為中心，把每個(gè)數(shù)據(jù)點(diǎn)分配到最近的類，形成新的聚類劃分。然后按照新的聚類劃分，計(jì)算新的聚類中心，取代原來的編碼值。</p

16、><p>　　由于K均值具有較強(qiáng)的局部搜索能力，因此引入K均值操作后，遺傳算法的收斂速度可以大大提高。</p><p><b>　　6 循環(huán)終止條件</b></p><p>　　循環(huán)代數(shù)開始為0，每循環(huán)一次，代數(shù)加1，若當(dāng)前循環(huán)代數(shù)小于預(yù)先規(guī)定的最大循環(huán)代數(shù)，則繼續(xù)循環(huán)；否則結(jié)束循環(huán)。</p><p><b>　　

17、7 算法的設(shè)計(jì)</b></p><p>　　(1)設(shè)置遺傳參數(shù)：聚類個(gè)數(shù)c，種群大小m，交叉概率cp，變異概率mp，最大迭代代數(shù)T，適應(yīng)度倍數(shù)參數(shù)b。</p><p>　　(2)隨機(jī)生成初始群體。</p><p>　　(3)計(jì)算群體各個(gè)體的適應(yīng)度。</p><p>　　(4)進(jìn)行選擇、交叉、變異、K均值操作，產(chǎn)生新一代群體。<

18、;/p><p>　　(5)重復(fù)第(3)、第(4)步，直到達(dá)到最大迭代代數(shù)T。</p><p>　　(6)計(jì)算新一代群體的適應(yīng)度，以最大適應(yīng)度的最佳個(gè)體為中心進(jìn)行K均值聚類。</p><p>　　(7)輸出聚類結(jié)果。</p><p>　　四、 實(shí)驗(yàn)結(jié)果與分析</p><p>　　為了檢驗(yàn)算法的有效性，對(duì)原始算法和改進(jìn)算法進(jìn)行

19、了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)來自給data的arff格式的文件數(shù)據(jù)，數(shù)據(jù)集分別是iris，glass。優(yōu)化后算法的參數(shù)設(shè)置如下：種群大小m=30，算法的最大迭代次數(shù)T=100，交叉概率1cp=0.9,2cp=0.6，變異概率1mp=0.1,2mp=0.001, b=1 000，所有算法運(yùn)行20次，運(yùn)行情況如表1所示。根據(jù)表1的實(shí)驗(yàn)結(jié)果，K均值算法初始聚類中心的選取敏感性很大，容易陷入局部最小值，并不是每次都能得到最優(yōu)解，特別是對(duì)于glass這種

20、較高維度的數(shù)據(jù)集，沒有一次達(dá)到全局最優(yōu)解。而改進(jìn)的算法對(duì)每組數(shù)據(jù)集的20次實(shí)驗(yàn)均能收斂到最優(yōu)解，聚類效果較好。除數(shù)據(jù)集iris外，K均值算法每組數(shù)據(jù)收斂到最優(yōu)解的平均迭代次數(shù)都比本文算法多，所以，本文算法的收斂速度也比較快。</p><p>　　表1 K均值算法和優(yōu)化后算法的比較</p><p><b>　　五、部分代碼</b></p><p>

21、;　　在代碼中主要添加和修改幾個(gè)部分</p><p><b>　　1、算中心距離</b></p><p>　　private double EuclidDistance(int x,int y,int z)</p><p><b>　　{</b></p><p><b>　　int i;&

22、lt;/b></p><p>　　double distance = 0;</p><p>　　for(i=0; i<NA; i++)</p><p><b>　　{</b></p><p>　　distance += pow( (instance[x].p[i] - pop[z].clustercenter

23、[y].p[i]),2 );</p><p><b>　　}</b></p><p>　　distance = sqrt(distance);</p><p>　　return distance;</p><p><b>　　}</b></p><p>　　private v

24、oid CalcuateDistance(int p)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p><b>　　int j;</b></p><p>　　for(i=0; i<NI; i++)</p>

25、;<p><b>　　{</b></p><p>　　for(j=0; j<K; j++)</p><p><b>　　{</b></p><p>　　instance[i].distance[j] = EuclidDistance(i,j,p);</p><p><b&g

26、t;　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　簇函數(shù)</b></p><p>　　private void Cluster(int p)</p><p><

27、;b>　　{</b></p><p><b>　　int i;</b></p><p><b>　　int j;</b></p><p>　　int index;</p><p>　　double min;</p><p>　　for(i = 0; i &l

28、t; K; i++)</p><p><b>　　{</b></p><p>　　cluster[i].clear();</p><p><b>　　}</b></p><p>　　for(i = 0; i < NI; i++)</p><p><b>　　{

29、</b></p><p>　　index = 0;</p><p>　　min = instance[i].distance[0];</p><p>　　for(j = 1; j < K; j++)</p><p><b>　　{</b></p><p>　　if(instanc

30、e[i].distance[j] < min)</p><p><b>　　{</b></p><p>　　min = instance[i].distance[j];</p><p>　　index = j;</p><p><b>　　}</b></p><p>&

31、lt;b>　　}</b></p><p>　　cluster[index].push_back(i);</p><p><b>　　}</b></p><p>　　/****計(jì)算種群中個(gè)體適應(yīng)值****/</p><p>　　pop[p].fitness = 0;</p><p>

32、;　　for(i = 0; i<K; i++)</p><p><b>　　{</b></p><p>　　for(j=0; j<cluster[i].size(); j++)</p><p><b>　　{</b></p><p>　　pop[p].fitness += pow(ins

33、tance[cluster[i][j]].distance[i],2);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　交叉函數(shù)private void CrossOver()。（略）

34、</p><p>　　迭代函數(shù)private void NextGeneration()。（略）</p><p><b>　　六、結(jié)束語</b></p><p>　　本文對(duì)K均值算法獲得最優(yōu)解的問題進(jìn)行了研究，發(fā)現(xiàn)隨機(jī)初始化會(huì)對(duì)該算法性能產(chǎn)生影響，不同的初始化中心會(huì)產(chǎn)生不穩(wěn)定的聚類結(jié)果。本文提出的基于遺傳算法的K均值聚類算法克服了上述缺陷。大量