基于遺傳算法的聚類方法研究.pdf

1、近年來(lái)數(shù)據(jù)挖掘引起了信息產(chǎn)業(yè)界的廣泛關(guān)注，其主要原因是存在大量的可用數(shù)據(jù)，并且迫切需要將這些數(shù)據(jù)轉(zhuǎn)換成有用的信息和知識(shí)。通過(guò)數(shù)據(jù)挖掘，可以將知識(shí)發(fā)現(xiàn)的研究成果應(yīng)用于實(shí)際數(shù)據(jù)處理中，為科學(xué)決策提供支持。聚類分析是數(shù)據(jù)挖掘的一項(xiàng)基本任務(wù)，是一個(gè)無(wú)監(jiān)督的學(xué)習(xí)過(guò)程，聚類的目標(biāo)是在沒(méi)有任何先驗(yàn)知識(shí)的前提下，將數(shù)據(jù)聚集成不同的簇，使得相同簇中的元素盡可能相似，不同簇中的元素差別盡可能大。通過(guò)聚類，人們能夠識(shí)別密集的和稀疏的區(qū)域，因而發(fā)現(xiàn)全局的分布模

2、式，以及數(shù)據(jù)屬性之間有趣的相互關(guān)系。 在聚類分析中，K-means算法可以說(shuō)是應(yīng)用較為廣泛的一種算法，但它的一個(gè)致命弱點(diǎn)是對(duì)初始化非常敏感而容易陷入局部極小值，而遺傳算法是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，其顯著特點(diǎn)是隱含并行性和對(duì)全局信息的有效利用能力，因此，借鑒K-means算法，用遺傳算法來(lái)解決聚類問(wèn)題，既能發(fā)揮遺傳算法的全局尋優(yōu)能力，又能兼顧K-means算法的局部搜索能力，從而更好地解決聚類問(wèn)題。本文就是提出了

3、新的混合遺傳算法，并以此來(lái)解決聚類問(wèn)題。 本文對(duì)遺傳算法和經(jīng)典的聚類算法做了深刻地分析、研究，提出了一種改進(jìn)的基于模擬退火機(jī)制的多種群并行遺傳算法，利用該混合遺傳算法解決聚類問(wèn)題，并通過(guò)實(shí)驗(yàn)驗(yàn)證算法的有效性。主要工作包括： 1.介紹分析了聚類算法以及遺傳算法。 介紹了數(shù)據(jù)挖掘的相關(guān)概念、任務(wù)、方法，然后介紹了聚類分析的概念、常見算法以及遺傳算法的基本概念、研究現(xiàn)狀等，并進(jìn)行了相應(yīng)的分析。 2.提出了一種改

4、進(jìn)的基于模擬退火機(jī)制的多種群并行遺傳算法。 提出的混合遺傳算法利用模擬退火遺傳算法，并對(duì)其進(jìn)行了改進(jìn)(采用動(dòng)態(tài)調(diào)節(jié)近鄰子集大小的方式)，再結(jié)合多種群并行遺傳算法的思想，同時(shí)加入小生境技術(shù)，從而有效地克服基本遺傳算法的早熟收斂等缺陷。 3.將改進(jìn)的基于模擬退火機(jī)制的多種群并行遺傳算法用于聚類分析。 借鑒了K-means算法，并采用基于聚類中心的浮點(diǎn)編碼方式，同時(shí)考慮到聚類數(shù)目k的值通常在事前不能很好地確定，往往根據(jù)

5、經(jīng)驗(yàn)來(lái)定，所以本文分別提出了固定聚類數(shù)目k值的聚類算法以及可以動(dòng)態(tài)確定恰當(dāng)?shù)木垲悢?shù)目k值的相應(yīng)算法，使得聚類算法具有更普遍的意義。 4.測(cè)試本文提出算法的有效性。 為了測(cè)試本文提出的聚類算法的性能，本文采用兩組實(shí)驗(yàn)數(shù)據(jù)，分別針對(duì)固定聚類數(shù)目k的聚類算法以及動(dòng)態(tài)確定聚類數(shù)目k的聚類算法進(jìn)行實(shí)驗(yàn)，并與其它的聚類算法，即K-means算法以及基于遺傳算法的聚類算法進(jìn)行效果比較，實(shí)驗(yàn)結(jié)果顯示本文算法有效地解決了聚類問(wèn)題。

6、 由于人們面對(duì)的數(shù)據(jù)是海量的，所以要求聚類算法能夠快速準(zhǔn)確地解決實(shí)際問(wèn)題。本文提出的算法利用多種群并行遺傳算法的思想，可以將較大的任務(wù)劃分成若干較小的任務(wù)，由不同的計(jì)算機(jī)來(lái)并行處理，這樣就提高了算法執(zhí)行的效率。并且，在每個(gè)種群中加入模擬退火操作以及小生境技術(shù)，借助模擬退火算法具有較強(qiáng)的局部搜索能力，并能使搜索過(guò)程避免陷入局部最優(yōu)解，而小生境技術(shù)通過(guò)維護(hù)群體中小規(guī)模低適應(yīng)度物種的生存，保持了物種多樣性，避免進(jìn)化過(guò)程中出現(xiàn)過(guò)早收斂和陷入局部