基于改進量子遺傳算法的k均值聚類分析

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

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

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

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

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

5、的表達　　3基于改進量子遺傳算法的K-均值聚類算法　　本文將量子遺傳算法和聚類分析相結(jié)合，通過量子遺傳算法的全局優(yōu)化能力與聚類分析的局部優(yōu)化能力相結(jié)合來克服聚類算法的局部性。相比于基本的量子遺傳算法，基于改進量子遺傳算法的K-均值聚類算法也是從隨機產(chǎn)生初始種群開始，只是在種群進化的過程中，完成種群進化操作后對產(chǎn)生的新種群的個體引入K均值優(yōu)化操作，然將優(yōu)化后的結(jié)果作為下一代的種群?！　≡撍惴鞒堂枋鋈缦拢骸　?）初始化種群，從給定數(shù)據(jù)中任意選取K個點作為中心點，并按照式（2-4）編碼，產(chǎn)生初始種群；　　2）對種群中的每個個體按照式（1

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

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

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