基于遺傳算法的K-MEANS聚類改進研究.pdf

1、聚類分析是數(shù)據(jù)挖掘中的一個重要研究領(lǐng)域,是一種數(shù)據(jù)劃分或分組處理的重要手段和方法。聚類的應(yīng)用是非常廣泛的,無論是在商務(wù)領(lǐng)域,還是在生物學(xué)、Web文檔分類、圖像處理等其它領(lǐng)域,都得到了有效的應(yīng)用。目前聚類算法大體上分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法以及模糊聚類。k-means算法是聚類算法中主要算法之一。它是一種基于劃分的聚類算法。該算法隨機選取k(k為聚類數(shù))個點作為初始聚類中心,通過一個

2、迭代過程完成聚類。該算法有它固有的不足:算法本身是迭代的,且不能確保它收斂于最優(yōu)解,它常常達到局部最優(yōu)而得不到全局最優(yōu)解;算法在進行聚類以前要求知道K值,這對于沒有經(jīng)驗的用戶來說很困難;初始聚類中心的選擇對于最后的聚類結(jié)果有很大的影響。遺傳算法是基于生物進化的概念設(shè)計了一系列過程來達到優(yōu)化的目的。這些過程包括:基因組合、交叉、變異、自然選擇。在這些過程中,通過“優(yōu)勝劣汰”的原則來淘汰掉解較差的基因,使得解朝著好的方向發(fā)展。遺傳算法從一組

3、初始可行解出發(fā)在只需要目標(biāo)函數(shù)這一信息的條件下實現(xiàn)對可行域的全局高效搜索并以概率1收斂到全局最優(yōu)解,這種良好的特性使得遺傳算法成為組合優(yōu)化和函數(shù)優(yōu)化的有力工具,并成為計算智能領(lǐng)域的研究熱點。本文首先對聚類分析的遺傳算法進行了研究,討論了聚類問題的編碼方式和適應(yīng)度函數(shù)的構(gòu)造方案與計算方法,分析了不同遺傳操作對聚類算法的性能和聚類效果的影響意義。然后對k-means算法中初值的選取方法進行了分析和研究,提出了一種基于遺傳算法的k-means

4、聚類改進(混合聚類算法),在基于均勻采樣的小樣本集上用k值學(xué)習(xí)遺傳算法確定聚類數(shù)k,用遺傳聚類算法的聚類結(jié)果作為k-means聚類的初始聚類中心,最后在已知初始聚類數(shù)和初始聚類中心的情況下用k-means算法對完整數(shù)據(jù)集進行聚類。由于遺傳算法是一種通過模擬自然進化過程搜索最優(yōu)解的方法,其顯著特點是隱含并行性和對全局信息的有效利用的能力,所以新的改進算法具有較強的穩(wěn)健性,可避免陷入局部最優(yōu),大大提高聚類效果。實驗采用標(biāo)準(zhǔn)數(shù)據(jù)集來測試該算法