摘要
聚类算法在数据分析,数据挖掘等许多地方有广泛的应用,该文探索了基于量子行为的微粒群优化算法(QPSO)及FCM的数据聚类。
首先,在分析PSO聚类、QPSO算法聚类的基础上,使用一种新的距离度量方法进行聚类,实验证明了新的度量方法比Euclidean标准更具有健壮性,聚类的结果更精确。在此基础上使用QPSO算法进行数据聚类,实验结果证明了QPSO算法优于PSO算法。QPSO算法不仅参数个数少,随机性强,并且能覆盖所有解空间,保证算法的全局收敛。
其次,在QPSO算法中,收缩-扩张系数对于QPSO中的单个粒子的收敛来说是一个至关重要的参数,提出了一种新的聚类算法——适应性的基于量子行为的微粒群优化算法的数据聚类(AQPSO)。AQPSO在全局搜索能力和局部搜索能力上优于PSO和QPSO算法,它的适应性方法比较接近于高水平智能群体的社会有机体的学习过程,并且能保证种群不断地进化。
最后,本文针对模糊C均值(FCM)聚类算法存在的缺点,利用量子粒子群优化(QPSO)算法的全局搜索能力,提出了一种新的聚类算法——基于量子粒子群优化的FCM聚类算法(QPSO-FCM)。QPSO-FCM算法先对随机初始点利用QPSO进行优化,然后利用产生的中心点进行聚类。新算法可以降低FCM算法对初始点的敏感度,一定程度上避免了FCM算法易陷入局部极优的缺陷。几组数据实验结果表明,与FCM和PSO-FCM算法相比,本文提出的QPSO-FCM算法聚类结果更可靠。继续在QPSO中使用新的距离公式与FCM相结合,数据表明新的算法能得到更优的结果。
Clustering algorithm has a wide application in many fields, for example data analysis and data excavation .In this paper we explore data clustering and the application with Quantum-behaved Particle Swarm Optimization (QPSO) and FCM.
Firstly, advancing QPSO algorithm to cluster data based on the PSO clustering and QPSO clustering, I propose a new distance metric in clustering procedures. Experiment results show that this new metric is more robust and accuracy than common-used Euclidean norm, I use QPSO algorithm to data clustering based on the new metric .The experiment results show that QPSO is superior to PSO. Not only the parameters of QPSO are few and randomicity of QPSO is strong, but also QPSO cover with all solution space and guarantee global convergence of algorithms.
Secondly, In QPSO, Contraction-Expansion Coefficient is a vital parameter to the convergence of the individual particle in QPSO. In this paper we use adaptive mechanism, therefore we use Adaptive Quantum-behaved Particle Swarm Optimization (AQPSO) to cluster date. The AQPSO outperforms PSO and QPSO in global search ability and local search ability, because the adaptive method is more approximate to the learning process of social organism with high-level swarm intelligence and can make the population evolve persistently.
Finally, After analyzing the disadvantages of the Fuzzy C-means (FCM) clustering algorithm,this paper proposes a novel Fuzzy C-means clustering based on Quantum-behave Particle Swarm Optimization algorithm. Not only parameters of QPSO are few and randomicity of QPSO is strong, but also QPSO covers with all solution space and guarantees global convergence. And it avoids the local minimum problems of FCM.At the same time,using QPSO to optimize initial centers first, FCM is no longer a large degree dependent on the initialization values.Numerical experiments show that the proposed algorithm is more robust and accuracy than FCM and PSO-FCM..
Using new distance metric in QPSO with FCM, The new QPSO-FCM can get more robust result.
引文
1) D vander Merwe , A Engelbrecht . Data Clustering using Particle Swarm Optimization[J/OL].http://cirg.cs.up.ac.za/publications/CEC2003d.pdf
2)曾建潮,介婧,崔志华.微粒群算法[M].北京:科学出版社,2004.
3) Sun J, Xu W B.A Global Search Strategy of Quantum-behaved Particle Swarm Optimization[C].Proceedings of IEEE conference on Cybernetics and Intelligent Systems, 2004:111– 116.
4) Sun J, Feng B , Xu W B. Particle Swarm Optimization with Particles Having Quantum Behavior[C]. Proceedings of 2004 Congress on Evolutionary Computation, 2004:325-331
5) kuo-Lung Wu,Miin-Shen Yang.Alternative c-means clustering algorithms[C].Pattern Recognition 35(2002) 2267-2278.
6) G. Sherlock,“Analysis of large-scale gene expression data”Current Opinion in Immunology, vol.12, pp201-205, 2000.
7) J Quackenbush“Computational analysis of microarray data”Nat.Rev.Genetics, vol.2.pp418-427, 2001.
8) M B Eisen, P.T.Spellman, P.O.Brown D.Botstein“Cluster analysis and display of genome-wide expression patterns”in Proc.Nat.Acad.Sci.USA, vol.95, 1998, pp14863-14868.
9) Thomas Werner“Target gene identification from expression array data by promoter analysis”Biomolecular Engineering, vol.17, pp87-94, 2001.
10) Javier Herrero, Alfonso Valencia, Joaquin Dopazo“A hierarchical unsupervised growing neural network for clustering gene expression patterns.”Bioinfomatics,vol.17 no.2, pp126-136, 2001.
11) C.Fraley, E.Raftery“MCLUST: Software for model-based cluster analysis”J.Classification, vol.16, pp297-l.18, pp306, 1999.
12) D.Ghosh, A.M.Chinnaiyan“Mixture modeling of gene expression data from microarray experiments”Bioinformatics, vo 275-286, 2002.
13) K.Y.Yeung, C.Fraley, A.Murua,A.E.Raftery, W.L.Ruzzo“Model-based clustering and data transformations for gene expression data”Bioinformatics, vol.17, pp977-987, 2001.
14) L.J.Heyer,S.Kruglyak,S.Yooseph“Exploring expression data: Identification and analysis of coexpress genes”Genome Res., vol.9, pp.1106-1115, 1999.
15) F.De Smet, J.Mathys, K.Marchal, G.Thijs, B.De Moor, Y.Moreau“Adaptive quality-based clustering of gene expression profiles”Bioinformatis, vol.18, no.5, pp.735-746, 2002.
16) M.Bittner, P.Meltzer, Y.Chen, Y.Jiang et al“Molecular classification of cutaneous malignant melanoma by gene expression profiling“Nature, vol.406, pp.536-540, 2000.
17) K.Y.Yeung, D.R.Haynor,and W.L.Ruzzo,“Validating clustering for gene expression data”Bioinformatics, vol.17, pp309-318, 2001.
18) Angeline P. Using selection to improve particle swarm optimization [A]. Proceedings of IJCNNp99 [ C ] .Washington , USA , 1999. 84～89.
19) B.Bullnheimer,R.F.Hartl,andC.Strauss.A New Rank Based Version of the Ant System—A Computational Study.Central Eeuropean Journal of Operations Research, 7:25-38, 1999.
20) Clerc M. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization [A]. Proceedings of the Congress on Evolutionary Computation [C]. Piscataway , NJ : IEEE Service Center , 1999. 1951～1957.
21) J. Sun et al:Parameter Selection of Quantum-behaved Particle Optimization. ICNC 2005, LNCS 3612, pp. 543– 552, 2005.? Springer-Verlag Berlin Heidelberg 2005.
22) Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms. New York: Plenum Press, 1981.
23) Pal N R, Bezdek J C. On cluster validity for the fuzzy c-mean model. IEEE Transactions on Fuzzy Systems, 1995,3(3): 370-379.
24) Bezdek J C, Hathaway R J, Sabin M J, Tucker W. Convergence theory for fuzzy c-means:Counter-examples and repairs. IEEE Transactions on SMC, 1987,17(5): 873-877
25)刘笛,朱学峰,苏彩红.一种新型的模糊C均值聚类初始化方法[J].计算机仿真,2004.21(11):148-151.
26) Kim Dae-won, Lee Kwang H, Lee Doheon. A Novel Initialization Scheme for the Fuzzy C-Means Algorithm for Color Clustering[J].Pattem Recognition Letters,2004,25(2):227-237.
27)王洪春,彭宏.基于模糊C-均值的增量式聚类算法.微电子学与计算机,2007,24(6):156-161.
28)张雯,杨春明,罗雪春.改进的粒子群优化算法.微电子学与计算机, 2007,24(3):70-72.
29) Zu¨lal Gu¨ngo¨r, Alper U¨nler, K-harmonic means data clustering with simulated annealing heuristic, Applied Mathematics and Computation (2006),doi:10.1016/j.amc.2006.05.166.
30) T Kohonen“self-Organizing Maps”, Springer Series in Information Sciences,Vol 30,Spring-Verlag,1995.
31) J Kennedy, RC Eberhart,“Particle Sarm Optimization”[J].Proceedings of the IEEE International Joint Conference on Neural Networks,1995,4:1942-1948.
32) J Kennedy,RC Eberhat,Y Shi,“Sarm Intelligence”. Morgan Kaufmann,2002
33) Clerc,M., Kennedy, J..The Particle Sarm:Explosion,Stability and Convergence in a Multi-Dimensional Complex Space.IEEE Transcaction on Evolutionary Conputationm,6(2002)58-73.
34) Wen bo Xu and Jun Sun.Adaptive Parameter Selection of Quantun-Behaved Particle Sarm Optimization on Global Level ,ICIC 2005.2005(Part I):420-428.
35) Adams R,Bischof L. Seeded region growing[C].IEEE-PAMI,1994,16(6):641-646.
