结合膜计算与人工蜂群算法的K均值算法
|
摘要
针对人工蜂群(ABC)优化的K均值(K-means)算法较易陷入局部最优、对初始聚类中心位置敏感等问题,结合具有广泛应用前景的膜计算(MC/P system)模型,提出一种改进的聚类算法。该算法利用最大最小距离积法对蜂群食物源进行初始化,提高初始值的适应度,加快收敛。ABC与K-means算法相结合,提高ABC算法的收敛速度;将ABC的蜜源进行K-means聚类,克服K-means对初始聚类中心的依赖及K-means算法易陷入局部最优的缺点。MC具有分布式、极大并行性和非确定性的特点,可以帮助提高蜂群的多样性,并平衡蜂群的勘探能力与开发能力。在提出的算法中,MC的结构以及其进化、溶解和通讯规则被整合到ABC算法中以增强蜂群的优化能力。实验结果表明,所提出的算法具有较好的聚类效果和稳定性。
In order to overcome the artificial bee colony(ABC) optimization K-means which be fallen into local optimum easily and sensitive to the initial cluster center position, proposes an improved clustering algorithm combined the membrane computing(MC/P system) model with broad application prospects. The algorithm adopts the max-min distance product method to initialize the food source to improve the fitness of the initial value and to accelerate the convergence. K-means algorithm to improve the convergence speed of ABC algorithm. To overcome K-means' dependence on initial clustering center and easily falling into local optimum, K-means clustered food sources of ABC algorithm. The MC has the characteristics of distributed, extremely parallel and non-deterministic, which can improve the diversity of bee colonies and balance the exploration and development capabilities of bee colonies. The structure of MC and its rules are integrated into the ABC algorithm to enhance the optimization ability. The experimental results show that the proposed algorithm has better clustering quality and stability.
In order to overcome the artificial bee colony(ABC) optimization K-means which be fallen into local optimum easily and sensitive to the initial cluster center position, proposes an improved clustering algorithm combined the membrane computing(MC/P system) model with broad application prospects. The algorithm adopts the max-min distance product method to initialize the food source to improve the fitness of the initial value and to accelerate the convergence. K-means algorithm to improve the convergence speed of ABC algorithm. To overcome K-means' dependence on initial clustering center and easily falling into local optimum, K-means clustered food sources of ABC algorithm. The MC has the characteristics of distributed, extremely parallel and non-deterministic, which can improve the diversity of bee colonies and balance the exploration and development capabilities of bee colonies. The structure of MC and its rules are integrated into the ABC algorithm to enhance the optimization ability. The experimental results show that the proposed algorithm has better clustering quality and stability.
引文
[1]秦全德,程适,李丽,等.人工蜂群算法研究综述[J].智能系统学报,2014,9(2):127-135.
[2]宋潇潇,王军,等.改进膜蜂群算法求解0-1背包问题[J].计算机应用,2015,35(7):2088-2092.
[3]喻金平,郑杰,梅宏标.基于改进人工蜂群算法的K均值聚类算法[J].计算机应用,2014,34(4):1065-1069.
[4]T.Y.Nishida.An Application of P-System:a New Algorithm for NP-Complete Optimization Problems[C].Proceedings of the 8th World Multi-Conference on Systems,Cybermetics and Informatics.0rlando:Interactional Institute of Informations and Systemics,2004:109-112.
[5]Zhang C,Zhou F,Huang X.A Novel Membrane Algorithm Based on Particle Swarm Optimization for Optimization for Solving Broadcasting Problems[J].Journal of Universal Computer Science,2012,18(13):1821-1841.
[6]Tu M,Wang J,Song X,et al.An Artificial Fish Swarm Algorithm Based on P Systems[J].ICIC Express Letters,Part B:Applications,2013,4(3):747-753.
[7]Zhao Y,Liu X,Qu J.The K-medoids Clustering Algorithm by a Class of P System.Journal of Information and Computational Science,2012,9(18):5777-5790.
[8]HU Juan,CHEN Guang-chun,PENG Hong,WANG Jun,HUANG Xiang-nian,LUO Xiao-hui.A k NN Classifier Optimized by P Systems,2017,432-437.
[9]PENG Hong,WANG Jun,Perez-Jimenez Mario.Optimal Multi-Level Thresholding with Membrane Computing.Digital Signal Processing,2014,37(1).
[10]Yahya Rafaa,Shamsuddin Siti Mariyam,Yahya Salah,Hasan Shafaatunnur,Alsalibi Bisan.Automatic 2D Image Segmentation Using Tissue-Like P System.International Journal of Advances in Soft Computing and its Applications,2018,19(1).
[11]Yahya Rafaa,Shamsuddin Siti Mariyam,Yahya Salah,Hasan Shafaatunnur,Alsalibi Bisan,Al-Khafaji Ghada.Image Segmentation Using Membrane Computing:A Literature Survey,2016,314-335.
[12]Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization[R].Technical Report,Kayseri:Erciyes University,2005.
[13]Karaboga D,Basturk B.A Powerful and Efficient Algorithm for Numerical Function Optimization:Artificial Bee Colony(ABC)Algorithm[J].Journal of Global Optimization,2007,39(3):459-471.
[14]Zhao J,Xie B,ZHANG L,et al.A Web Services Composition Method Supporting Domain Feature[J].Chinese Journal of Computers,2005,28(4):731-738.
[15]赵文昌,李忠木.融合改进人工蜂群和K均值聚类的图像分割[J].液晶与显示,2017,32(9):726-735.
[16]Isanam,Salamahsa,Ngahuk.Adaptive Fuzzy Moving K-means Clustering Algorithm for Image Segmentation[J].IEEE Transactions on Consumer Electronics,2009,55(4):2145-2153.
[17]李海洋,何红洲.改进人工蜂群优化的K均值图像分割算法[J].智能计算机与应用,2018(3).
[18]曹永春,蔡正琦,邵亚斌.基于K-means的改进人工蜂群聚类算法[J].计算机应用,2014,34(1):204-207.
[19]Janani Balakumar,Dr.S.Vijayarani.Text Document Clustering Using Artificial Bee Colony with Bisecting K-means Algorithm.International Journal of Advanced Research in Computer Science[S.l.].2018,9(1):619-623,feb.2018.ISSN 0976-5697.
[20]Alam Gowthul,S.Baulkani.A Hybrid Approach for Web Document Clustering Using K-means and Artificial Bee Colony Algorithm.International Journal of Intelligent Engineering and Systems,2016,9(4):11-20.
[21]Cong Tran,Wu Zhijian,Wang Zelin,Deng Changshou.A Novel Hybrid Data Clustering Algorithm Based on Artificial Bee Colony Algorithm and K-Means.Chinese Journal of Electronics,2015,24(4):694-701.
[22]Giuliano Armano,Mohammad Reza Farmani.Clustering Analysis with Combination of Artificial Bee Colony Algorithm and K-means Technique.International Journal of Computer Theory and Engineering,2014,6:141-145.
[23]Bonab M.B.,Hashim S.Z.M.,Alsaedi A.K.Z.,Hashim U.R.Modified K-means Combined with Artificial Bee Colony Algorithm and Differential Evolution for Color Image Segmentation.Computational Intelligence in Information Systems.Advances in Intelligent Systems and Computing,vol 331.Springer,Cham.2015.
[24]Paun G.Computing with Membranes[J].Journal of Computer and System Sciences,2000,61(1):108-143.
[25]Zou W,Sui X,Chen H,et al.A Clustering Approach Using Cooperative Artificial Bee Colony Algorithm[J].Discrete Dynamics in Nature and Society,2010,(2010-10-18),2010(2):1038-1045.
[2]宋潇潇,王军,等.改进膜蜂群算法求解0-1背包问题[J].计算机应用,2015,35(7):2088-2092.
[3]喻金平,郑杰,梅宏标.基于改进人工蜂群算法的K均值聚类算法[J].计算机应用,2014,34(4):1065-1069.
[4]T.Y.Nishida.An Application of P-System:a New Algorithm for NP-Complete Optimization Problems[C].Proceedings of the 8th World Multi-Conference on Systems,Cybermetics and Informatics.0rlando:Interactional Institute of Informations and Systemics,2004:109-112.
[5]Zhang C,Zhou F,Huang X.A Novel Membrane Algorithm Based on Particle Swarm Optimization for Optimization for Solving Broadcasting Problems[J].Journal of Universal Computer Science,2012,18(13):1821-1841.
[6]Tu M,Wang J,Song X,et al.An Artificial Fish Swarm Algorithm Based on P Systems[J].ICIC Express Letters,Part B:Applications,2013,4(3):747-753.
[7]Zhao Y,Liu X,Qu J.The K-medoids Clustering Algorithm by a Class of P System.Journal of Information and Computational Science,2012,9(18):5777-5790.
[8]HU Juan,CHEN Guang-chun,PENG Hong,WANG Jun,HUANG Xiang-nian,LUO Xiao-hui.A k NN Classifier Optimized by P Systems,2017,432-437.
[9]PENG Hong,WANG Jun,Perez-Jimenez Mario.Optimal Multi-Level Thresholding with Membrane Computing.Digital Signal Processing,2014,37(1).
[10]Yahya Rafaa,Shamsuddin Siti Mariyam,Yahya Salah,Hasan Shafaatunnur,Alsalibi Bisan.Automatic 2D Image Segmentation Using Tissue-Like P System.International Journal of Advances in Soft Computing and its Applications,2018,19(1).
[11]Yahya Rafaa,Shamsuddin Siti Mariyam,Yahya Salah,Hasan Shafaatunnur,Alsalibi Bisan,Al-Khafaji Ghada.Image Segmentation Using Membrane Computing:A Literature Survey,2016,314-335.
[12]Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization[R].Technical Report,Kayseri:Erciyes University,2005.
[13]Karaboga D,Basturk B.A Powerful and Efficient Algorithm for Numerical Function Optimization:Artificial Bee Colony(ABC)Algorithm[J].Journal of Global Optimization,2007,39(3):459-471.
[14]Zhao J,Xie B,ZHANG L,et al.A Web Services Composition Method Supporting Domain Feature[J].Chinese Journal of Computers,2005,28(4):731-738.
[15]赵文昌,李忠木.融合改进人工蜂群和K均值聚类的图像分割[J].液晶与显示,2017,32(9):726-735.
[16]Isanam,Salamahsa,Ngahuk.Adaptive Fuzzy Moving K-means Clustering Algorithm for Image Segmentation[J].IEEE Transactions on Consumer Electronics,2009,55(4):2145-2153.
[17]李海洋,何红洲.改进人工蜂群优化的K均值图像分割算法[J].智能计算机与应用,2018(3).
[18]曹永春,蔡正琦,邵亚斌.基于K-means的改进人工蜂群聚类算法[J].计算机应用,2014,34(1):204-207.
[19]Janani Balakumar,Dr.S.Vijayarani.Text Document Clustering Using Artificial Bee Colony with Bisecting K-means Algorithm.International Journal of Advanced Research in Computer Science[S.l.].2018,9(1):619-623,feb.2018.ISSN 0976-5697.
[20]Alam Gowthul,S.Baulkani.A Hybrid Approach for Web Document Clustering Using K-means and Artificial Bee Colony Algorithm.International Journal of Intelligent Engineering and Systems,2016,9(4):11-20.
[21]Cong Tran,Wu Zhijian,Wang Zelin,Deng Changshou.A Novel Hybrid Data Clustering Algorithm Based on Artificial Bee Colony Algorithm and K-Means.Chinese Journal of Electronics,2015,24(4):694-701.
[22]Giuliano Armano,Mohammad Reza Farmani.Clustering Analysis with Combination of Artificial Bee Colony Algorithm and K-means Technique.International Journal of Computer Theory and Engineering,2014,6:141-145.
[23]Bonab M.B.,Hashim S.Z.M.,Alsaedi A.K.Z.,Hashim U.R.Modified K-means Combined with Artificial Bee Colony Algorithm and Differential Evolution for Color Image Segmentation.Computational Intelligence in Information Systems.Advances in Intelligent Systems and Computing,vol 331.Springer,Cham.2015.
[24]Paun G.Computing with Membranes[J].Journal of Computer and System Sciences,2000,61(1):108-143.
[25]Zou W,Sui X,Chen H,et al.A Clustering Approach Using Cooperative Artificial Bee Colony Algorithm[J].Discrete Dynamics in Nature and Society,2010,(2010-10-18),2010(2):1038-1045.