基于遺傳算法的K-means聚類算法分析研究.pdf

1、近年來(lái)，隨著信息技術(shù)的發(fā)展，信息資源的經(jīng)濟(jì)和社會(huì)價(jià)值越來(lái)越重要。通過(guò)數(shù)據(jù)挖掘，從大量的數(shù)據(jù)資料中發(fā)現(xiàn)有價(jià)值的、人們感興趣的信息或知識(shí)，可以達(dá)到為科學(xué)決策提供支持的目的。聚類分析是數(shù)據(jù)挖掘的一項(xiàng)基本任務(wù)，是一種無(wú)監(jiān)督的分類方法。聚類的目標(biāo)是把一個(gè)無(wú)類別標(biāo)記的數(shù)據(jù)集按某種準(zhǔn)則劃分成不同的簇，使相同簇中數(shù)據(jù)的相似性盡可能小，而不同簇間數(shù)據(jù)相似性盡可能大。聚類的應(yīng)用非常廣泛，無(wú)論是在商務(wù)領(lǐng)域，還是在Web文檔分類、圖像處理等其它領(lǐng)域，都得到有效

2、的應(yīng)用。目前聚類算法大體上分為基于劃分的方法、基于層次的方法、基于模型的方法、基于網(wǎng)格的方法、基于密度的方法等。 K-means算法是聚類分析的主要算法之一，是一種基于劃分的聚類算法。該算法隨機(jī)選取k個(gè)點(diǎn)作為初始聚類中心，通過(guò)一個(gè)迭代過(guò)程完成聚類。該算法有它固有的不足：它容易陷入局部極小值而得不到全局最優(yōu)解；算法在進(jìn)行聚類時(shí)要求有固定的K值，這對(duì)于沒(méi)有經(jīng)驗(yàn)的用戶來(lái)說(shuō)很困難；初始中心的選擇對(duì)聚類結(jié)果有很大影響；一般的聚類算法對(duì)孤立

3、點(diǎn)數(shù)據(jù)和噪聲比較敏感。 遺傳算法是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的算法，它通過(guò)基因組合、交叉、變異、自然選擇等一系列過(guò)程達(dá)到優(yōu)化的目的。在這些過(guò)程中，通過(guò)“優(yōu)勝劣汰”的原則淘汰掉解較差的基因，使得解朝著好的方向發(fā)展。它從一組初始可行解出發(fā)在只需要目標(biāo)函數(shù)這一信息的條件下實(shí)現(xiàn)對(duì)可行域的全局高效搜索并以概率1收斂到全局最優(yōu)解，具有隱含并行性和對(duì)全局信息的有效利用能力的顯著特點(diǎn)，這種良好的特性使得遺傳算法成為函數(shù)優(yōu)化和組合優(yōu)化的有

4、力工具。因此，將遺傳算法和K-means算法有效結(jié)合，充分發(fā)揮遺傳算法的全局尋優(yōu)能力和K-means算法的局部搜索能力，可以更好地提高聚類質(zhì)量。 針對(duì)傳統(tǒng)遺傳算法和聚類算法存在的缺陷，本文提出了一種改進(jìn)的遺傳k均值算法，該算法的改進(jìn)之處：在遺傳算法中采用自識(shí)別交叉算子和自適應(yīng)變異算子，自識(shí)別交叉算子可以保證群體的優(yōu)良模式遺傳到下一代，加快了算法收斂速度，自適應(yīng)變異算子擴(kuò)大了搜索范圍，增強(qiáng)了算法跳離局部最優(yōu)解的能力；優(yōu)化K-mea