基于量子行為的微粒群優(yōu)化算法的數(shù)據(jù)聚類

摘要：在PSO聚類算法的基礎(chǔ)上，提出了基于量子行為的微粒群優(yōu)化算法（QPSO）的數(shù)據(jù)聚類。QPSO算法不僅參數(shù)個數(shù)少、隨機(jī)性強(qiáng)，并且能覆蓋所有解空間，保證算法的全局收斂。PSO與QPSO算法的不同在于聚類中心的進(jìn)化上，實驗中用到四個數(shù)據(jù)集比較的結(jié)果，證明了QPSO優(yōu)于PSO聚類方法。在聚類過程中使用了一種新的度量代替Euclidean標(biāo)準(zhǔn)，實驗證明了新的度量方法比Euclidean標(biāo)準(zhǔn)更具有健壯性，聚類的結(jié)果更精確。

關(guān)鍵詞： 聚類；基于量子行為的微粒群優(yōu)化算法；新的度量

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)11-0049-03

聚類是一個將數(shù)據(jù)集劃分為若干組（class）或類（cluster）的過程，并使得同一組內(nèi)的數(shù)據(jù)對象具有較高的相似度，而不同組中的數(shù)據(jù)對象是不相似的。它是一種無監(jiān)督的模式識別問題。許多領(lǐng)域，包括數(shù)據(jù)分析、數(shù)據(jù)挖掘、圖像分割、統(tǒng)計學(xué)、機(jī)器學(xué)習(xí)都使用了聚類算法。

相似或不相似的描述是基于數(shù)據(jù)描述屬性的取值來確定的，通常就是利用（各對象間）距離來進(jìn)行表示的。傳統(tǒng)的聚類方法如C－均值聚類、模糊C－均值聚類（FCM）在聚類過程中根據(jù)Euclidean距離，但是基于這類距離的聚類方法一般只能發(fā)現(xiàn)具有類似大小和密度的圖形或球狀聚類。所以在下面的聚類過程中將使用一種新的距離度量[1]。這種新的度量比經(jīng)常使用的Euclidean標(biāo)準(zhǔn)更具有健壯性。基于新的度量標(biāo)準(zhǔn)，本文提出了一種新的聚類方法——基于量子行為的微粒群優(yōu)化算法（QPSO）的聚類方法[2，3]。這種聚類方法能保證粒子群的全局收斂，優(yōu)于PSO算法的性能，具有較強(qiáng)的健壯性，并且在實際應(yīng)用系統(tǒng)中能容忍經(jīng)常發(fā)生的情況。

首先考慮目標(biāo)函數(shù)，對四個數(shù)據(jù)集來說，QPSO目標(biāo)函數(shù)的平均值最小，其性能最好。QPSO比PSO聚類方法穩(wěn)定。

其次，考慮聚類之間的距離，其值越大越好，QPSO對iris、DATASET4，其聚類之間的偏差比較大。

最后，考慮聚類內(nèi)部的距離。它表明了一個聚類內(nèi)部的每個數(shù)據(jù)向量與聚類中心的偏離，其值越小越好。QPSO對iris、wine、breast cancer來說，保證了聚類內(nèi)部比較緊密。

5結(jié)束語

本文在一種新的距離度量上，提出了一種新的聚類方法——QPSO聚類方法。通過實驗，表明了新的度量具有較強(qiáng)的健壯性。在此基礎(chǔ)上進(jìn)行的基于QPSO算法的聚類性能優(yōu)于PSO聚類方法，并且總體來說基于QPSO算法形成的聚類之間的距離比較大，聚類內(nèi)部的距離比較小。通過QPSO聚類算法對圖像進(jìn)行的分割效果是非常令人滿意的，相似的像素聚到了同一個類中。由于獲取的RGB圖像分辨率低，它的灰度級強(qiáng)度可能會位于內(nèi)部和外部范圍的邊界上，造成相似的像素屬于不同的小立方體，但是這種概率是非常低的。

參考文獻(xiàn)：

［1］KUO L W，MIIN－SHEN Y.Alternative c－means clustering algorithms[J].Pattern Recognition，2002，35:2267-2278.

［2］SUN Jun， XU Wen－bo.A global search strategy of quantum－behaved particle swarm optimization[C]//Proc of IEEE Conference on Cybernetics and Intelligent Systems.2004:111－116.

［3］SUN Jun， FENG Bin， XU Wen－bo.Particle swarm optimization with particles having quantum behavior[C]//Proc of Congress on Evolutionary Computation.2004:325-331.

［4］曾建潮，介婧，崔志華.微粒群算法[M].北京:科學(xué)出版社，2004:200-210.

［5］RAMOS V， MUGE F.Image colour segmentation by genetic algorithms[C]//Proc of the 11th Portuguese Conference on Pattern Recog￣nition. Porto， Portugal:[s.n.]，2000.

［6］郭國棟，馬頌德.彩色圖像分割[J].中國圖象圖形學(xué)報，1998，3（11）：918-921.

［7］OHLANDER R，PRICE K，REDDY D R. Picture segmentation using a recursive region splitting method [J]. CGIP，1978，8(3):313-333.

［8］TREMEAU A，BOREL N. A region growing and merging algorithm to color segmentation[J].Pattern Recognition， 1997，30(7):1191－1203.

［9］PAL N R，PAL S K. A review on image segmentation techniques[J].Pattern Recognition，1993，26（9）:1277－1294.

［10］ADAMS R，BISCHOF L. Seeded region growing[J].IEEE－PAMI，1994，16(6):641-646.

［11］KASS M，WITKIN A，TERZOPOULOS D. Snakes:active contour models[J]. Int J Compular Vision，1987，1（4）:321-331.

［12］劉少創(chuàng)，林宗堅.彩色航空影像分割的OCTOPUS方法[J].中國圖象圖形學(xué)報，1997，2（11）：790-794.

［13］MERWE van der D W， ENGELBRECHT A P．Data clustering using particle swarm optimization[EB/OL].

(2003).[2006-09-01].http://cirg.cs.up.ac.za/publications/CEC2003d.pdf.

［14］KENNEDY J， EBERHART R C. Particle swarm optimization[C]//Proc of the IEEE International Joint Conference on Neural Networks.1995:1942－1948.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”