基于改進(jìn)量子遺傳算法的k均值聚類(lèi)分析

《基于改進(jìn)量子遺傳算法的k均值聚類(lèi)分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、基于改進(jìn)量子遺傳算法的K均值聚類(lèi)分析：NA：A：1671－7597（2011）0310019－01　　　　0引言　　K-means算法是聚類(lèi)分析中一種基本的聚類(lèi)方法[1]，因其簡(jiǎn)單可靠而被廣泛使用，但傳統(tǒng)的K均值算法受初始聚類(lèi)中心的影響而過(guò)早地收斂于局部最優(yōu)解。于是人們考慮將遺傳算法應(yīng)用于K-means聚類(lèi)分析來(lái)解決上述相關(guān)問(wèn)題的。隨著遺傳算法理論基礎(chǔ)和應(yīng)用技術(shù)的逐漸成熟，近年來(lái)涌現(xiàn)出了大量的基于遺傳算法進(jìn)行聚類(lèi)分析的新算法。　　量子遺傳算法（QuantumGeicAlgorithm,QGA）[3]是近期產(chǎn)生的一種概率進(jìn)化算法，它以

2、量子計(jì)算的一些概率和理論為基礎(chǔ)。相比傳統(tǒng)遺傳算法QGA具有很多優(yōu)點(diǎn)，但是也存在隨機(jī)性和繁瑣的編解碼等缺點(diǎn)。本文采用實(shí)數(shù)編碼三倍染色體表達(dá)的方法對(duì)傳統(tǒng)QGA作了改進(jìn)，并將改進(jìn)后的量子遺傳算法用于K均值聚類(lèi)，實(shí)驗(yàn)結(jié)果表明本文提出的量子遺傳算法K均值聚類(lèi)算法的收斂性能優(yōu)于傳統(tǒng)K均值聚類(lèi)算法。　　1K-means算法的基本思想　　假定用戶劃分?jǐn)?shù)為K，首先任意選取K個(gè)點(diǎn)作為中心，計(jì)算剩余點(diǎn)到各個(gè)中心的距離，以最近為原則進(jìn)行歸屬，基于給定的聚類(lèi)目標(biāo)函數(shù)，每次迭代使內(nèi)部對(duì)象相似性越來(lái)越大，類(lèi)間對(duì)象的相似性越來(lái)越小。　　K-means聚類(lèi)算法的基本

3、步驟為：　　1）任意選擇K個(gè)對(duì)象作為初始的簇中心；　　2）計(jì)算各個(gè)對(duì)象到簇中心的距離，以最近原則進(jìn)行劃歸；　　3）更新中心點(diǎn)，即計(jì)算每個(gè)簇中對(duì)象的平均值；　　4）如果簇的劃分發(fā)生改變則轉(zhuǎn)2），否則結(jié)束?！　∫宰钚』瘹W氏距離平方和為基礎(chǔ)描述的K-means聚類(lèi)問(wèn)題為：對(duì)于給定數(shù)據(jù)空間Rm中的n個(gè)數(shù)據(jù)目標(biāo)，分別將數(shù)據(jù)目標(biāo)分配到K個(gè)簇中，以使得每個(gè)目標(biāo)到其所在簇中心的歐氏距離平方和最?。骸　?改進(jìn)的量子遺傳算法　　2.1量子遺傳算法　　在QGA中，用量子比特來(lái)表達(dá)和存儲(chǔ)一個(gè)基因，該基因可以為“0”態(tài)或“1”態(tài)，或兩者之間的任一狀態(tài)，即該基

4、因所表達(dá)的不再是某一確定的信息，而是包含所有可能的信息，對(duì)該基因的任一操作也會(huì)同時(shí)作用于所有可能的信息。一個(gè)由m個(gè)量子比特構(gòu)成的量子染色體可以描述為：　　在量子遺傳算法中，采用量子旋轉(zhuǎn)門(mén)來(lái)實(shí)現(xiàn)量子狀態(tài)的更新和演化，通常設(shè)計(jì)量子旋轉(zhuǎn)門(mén)如下：　　QGA采用式3-1所表示的量子位染色體表示種群，通過(guò)測(cè)量染色體上量子位的狀態(tài)來(lái)生成所需要的二進(jìn)制解，采用量子門(mén)作用于量子位概率幅度來(lái)保持種群的多樣性。但是測(cè)量這是一個(gè)概率操作過(guò)程，具有很大的隨機(jī)性和盲目性，而且其編碼復(fù)雜，計(jì)算精度受編碼位的限制，并不適合高維多極值函數(shù)的優(yōu)化。　　2.2實(shí)數(shù)染色體

5、的表達(dá)　　3基于改進(jìn)量子遺傳算法的K-均值聚類(lèi)算法　　本文將量子遺傳算法和聚類(lèi)分析相結(jié)合，通過(guò)量子遺傳算法的全局優(yōu)化能力與聚類(lèi)分析的局部?jī)?yōu)化能力相結(jié)合來(lái)克服聚類(lèi)算法的局部性。相比于基本的量子遺傳算法，基于改進(jìn)量子遺傳算法的K-均值聚類(lèi)算法也是從隨機(jī)產(chǎn)生初始種群開(kāi)始，只是在種群進(jìn)化的過(guò)程中，完成種群進(jìn)化操作后對(duì)產(chǎn)生的新種群的個(gè)體引入K均值優(yōu)化操作，然將優(yōu)化后的結(jié)果作為下一代的種群。　　該算法流程描述如下：　　1）初始化種群，從給定數(shù)據(jù)中任意選取K個(gè)點(diǎn)作為中心點(diǎn)，并按照式（2-4）編碼，產(chǎn)生初始種群；　　2）對(duì)種群中的每個(gè)個(gè)體按照式（1

6、-1）計(jì)算個(gè)體的適應(yīng)度值；　　3）根據(jù)上一步計(jì)算出的值，對(duì)種群做互補(bǔ)雙變異操作；　　4）達(dá)到一定間隔時(shí)對(duì)適應(yīng)度值低的個(gè)體做離散交叉操作，以此產(chǎn)生新的種群；　　5）對(duì)上一步產(chǎn)生的新種群中每個(gè)個(gè)體執(zhí)行K-means操作，并將其優(yōu)化為以該個(gè)體為初始值的K均值問(wèn)題的局部最優(yōu)解，產(chǎn)生新一代的種群；　　6）判斷條件是否結(jié)束，如未結(jié)束轉(zhuǎn)向第3）步繼續(xù)操作?！　?實(shí)驗(yàn)結(jié)果與分析　　為了檢驗(yàn)算法的有效性，對(duì)K-均值算法，基于遺傳算法的K-均值聚類(lèi)算法[2]和本文提出的基于改進(jìn)量子遺傳算法的K-均值聚類(lèi)算法進(jìn)行對(duì)比試驗(yàn)。在Matlab環(huán)境下分別編寫(xiě)這三

7、種算法。實(shí)驗(yàn)數(shù)據(jù)集的屬性見(jiàn)表1所示?！　?shí)驗(yàn)結(jié)果分析：根據(jù)表2的實(shí)驗(yàn)結(jié)果，K-均值算法受初始化的影響很大，容易陷入局部最優(yōu)解，不是每次都能達(dá)到最優(yōu)解，特別是對(duì)于glass這種高維度的數(shù)據(jù)集，沒(méi)有遺傳達(dá)到全局最優(yōu)解。遺傳算法和改進(jìn)的量子免疫遺傳算法克服了K-均值的上述缺點(diǎn)；同時(shí)通過(guò)比較遺傳聚類(lèi)算法(GKA)和改進(jìn)的量子遺傳聚類(lèi)算法(IQGKA)對(duì)每組數(shù)據(jù)20次實(shí)驗(yàn)，IQGKA每次都能達(dá)到最優(yōu)解，而在平均迭代次數(shù)上，IQGKA的平均迭代步數(shù)都有比GKA要少。因此，改進(jìn)的量子遺傳聚類(lèi)算法的收斂速度也比較快?！　?結(jié)束語(yǔ)　　本文提出了一種改

8、進(jìn)的量子遺傳聚類(lèi)算法，克服傳統(tǒng)二進(jìn)制編碼量子遺傳算法繁瑣編解碼問(wèn)題和K-均值聚類(lèi)算法對(duì)初始值敏感的缺點(diǎn)。通過(guò)對(duì)相關(guān)數(shù)據(jù)集的測(cè)試，并與基于遺傳算法的K-均值聚類(lèi)算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明：本文提出的改進(jìn)的量子遺傳聚類(lèi)算法其聚類(lèi)性能要優(yōu)于