DOI: 10.3724/SP.J.1146.2008.01698

Journal of Electronics & Information Technology (电子与信息学报) 2010/32:1 PP.92-97

Improved Cluster Algorithm Based on K-Means and Particle Swarm Optimization

To deal with the problem of premature convergence of the traditional K-means algorithm, a novel K-means cluster method based on the enhanced Particle Swarm Optimization(PSO) algorithm is presented. In this approach, the stochastic mutation operation is introduced into the PSO evolution, which reinforces the exploitation of global optimum of the PSO algorithm. In order to avoid the premature convergence and speed up the convergence, traditional K-means algorithm is used to explore the local search space more efficiently dynamically according to the variation of the particle swarm’s fitness variance. Comparison of the performance of the proposed approach with the cluster method based on K-means, traditional PSO algorithm and other PSO-K-means algorithm is experimented. The experimental results show the proposed method can not only effectively solve the premature convergence problem, but also significantly speed up the convergence.

Key words:K-means algorithm,Particle Swarm Optimization(PSO) algorithm,Stochastic mutation,Fitness variance

ReleaseDate:2014-07-21 15:07:00

[1] 陈金山等. 遗传+模糊C-均值混合聚类算法[J]. 电子与信息学报, 2002, 24(2): 210-215. Chen Jin-shan,et al. A hybrid clustering algorithm incorporating fuzzy c-means into canonical genetic algorithm[J]. Journal of Electronics & Information Technology, 2002, 24(2): 210-215.

[2] Li M J and Ng M K, et al. Agglomerative fuzzy K-means clustering algorithm with selection of number of clusters[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(11): 1519-1534.

[3] Krishma K and Murty M N. Genetic Kmeans algorithm[J]. IEEE Transactions on System, Man and Cybernetics, Part B, 1999, 29(3): 433-439.

[4] Maulik U and Bandyopadhay S. Genetic algorithm-based clustering technique[J]. Pattern Recognition, 2000, 33(9): 1455-1465.

[5] 孟伟, 韩学东. 蜜蜂进化型遗传算法[J]. 电子学报, 2006, 34(7): 1294-1300. Meng Wei and Han Xue-dong. Bee evolutionary genetic algorithm[J]. Acta Electronica Sinica, 2006, 34(7): 1294-1300.

[6] Kennedy J and Eberhart R. Particle swarm optimization[C]. Proceedings of IEEE international conference on neural networks, Perth, Australia, 1995: 1942-1948.

[7] 吕振肃, 侯志荣. 自适应变异的粒子群优化算法[J]. 电子学报, 2004, 32(3): 416-420. Lu Zheng-su and Hou Zhi-rong. Particle swarm optimization with adaptive mutation[J]. Acta Electronica Sinica, 2004, 32(3): 416-420.

[8] Del V Y and Venayagamoorthy G K. Particle Swarm Optimization: Basic concepts, variants and applications in power systems[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(2): 171-195.

[9] Van den Bergh F and Engelbrecht A P. A Cooperative approach to particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 225-239.

[10] 曾建潮, 崔志华. 一种保证全局收敛的PSO算法[J]. 计算机研究与发展, 2004, 41(8): 1333-1338. Zeng Jian-chao and Cui Zhi-hua. A guaranteed global convergence particle swarm optimizer[J]. Journal of Computer Research and Development, 2004, 41(8): 1333-1338.

[11] 赫然, 王永吉. 一种改进的自适应逃逸微粒群算法及实验分析[J]. 软件学报, 2005, 16(12): 2036-2044. He Ran and Wang Yong-ji. An improved particle swarm optimization based on self adaptive escape [J]. Journal of Software, 2005, 16(12): 2036-2044.

[12] 李晓晴, 焦素敏. 基于粒子群优化的带障碍约束空间聚类分析[J]. 计算机工程与设计, 2007, 28(24): 5924-5926. Li Xiao-qing and Jiao Su-min. PSO spatical clustering with obstacles constraints [J]. Computer Engineering and Design, 2007, 28(24): 5924-5926.

[13] Pei Zhenkui and Hua Xia. The clustering algorithm based on particle swarm optimization algorithm[C]. International Conference on Intelligent Computation Technology and Automation (ICICTA), Hunan, Oct. 20-22, 2008, 1: 148-151.

[14] 刘靖明, 韩丽川. 基于粒子群的K均值聚类算法[J]. 系统工程理论与实践, 2005, 6: 54-58. Liu Jing-ming and Han Li-chuan. Cluster analysis based on particle swarm optimization algorithm[J]. Systems Engineering-Theory & Practice, 2005, 6: 54-58.