基于近邻传播的改进组搜索优化聚类算法

系统仿真学报 ›› 2015, Vol. 27 ›› Issue (9): 2066-2074.

基于近邻传播的改进组搜索优化聚类算法

张康, 顾幸生

华东理工大学教育部化工过程控制与优化重点实验室,上海 200237

收稿日期:2015-05-15 修回日期:2015-08-03 出版日期:2015-09-08 发布日期:2020-08-07
作者简介:张康(1984-),男,山东,博士生,研究方向为人工智能与模式识别;顾幸生,男,教授。
基金资助:
国家自然科学基金(61174040, 61104178, 61205017)

Affinity Propagation Based Improved Group Search Optimizer Clustering Algorithm

Zhang Kang, Gu Xingsheng

Key Laboratory of Advanced Control and Optimization for Chemical Process, Ministry of Education East China University of Science and Technology, Shanghai 200237, China

Received:2015-05-15 Revised:2015-08-03 Online:2015-09-08 Published:2020-08-07

摘要/Abstract

摘要： 聚类问题本质上作为一个最优化问题,理论上是可以使用近年来流行的群智能优化算法来求解的。针对组搜索优化(GSO)算法在全局和局部搜索能力上的不足,提出了一种新型的——快速全局组搜索优化算法(FGGSO),采用了竞选策略、破坏——重建策略、加速与跳跃策略。基于该改进的组搜索算法,提出了一种基于近邻传播(AP)算法的改进组搜索优化聚类算法。针对AP算法不能设定输出类数的不足,通过将其与FGGSO算法结合,先使用AP算法得到候选类中心点,再利用FGGSO优化聚类结果,得到确定类数的聚类。实验结果表明所提算法能够获得预期的聚类效果。

关键词: 聚类分析, 近邻传播, 组搜索算法, 优化

Abstract: The essence of clustering is an optimization problem. It can be solved by swarm intelligent algorithms which are the popular research area in recent years. A novel Group Search Optimizer (GSO) algorithm named Fast Global Group Search Optimizer (FGGSO) was proposed. FGGSO improved the individuals' updating strategies of GSO, adopting the campaign strategy, destruction-construction strategy and accelerating-jumping strategy. By this means, the proposed algorithm improved the global and local search capability of the original GSO. Furthermore, based on this FGGSO algorithm, a novel improved AP algorithm was proposed. On account of deficiency of AP clustering unable to deal with a user given cluster number, FGGSO and AP were combined. Firstly, AP algorithm was used to obtain any candidate exemplars, and then the clustering result was optimized using FGGSO algorithm, so that a certain cluster number can be obtained. Experimental results show the effectiveness of the proposed algorithm.

Key words: clustering analysis, affinity propagation, group search optimizer, optimization

中图分类号:

TP18

张康, 顾幸生. 基于近邻传播的改进组搜索优化聚类算法[J]. 系统仿真学报, 2015, 27(9): 2066-2074.

Zhang Kang, Gu Xingsheng. Affinity Propagation Based Improved Group Search Optimizer Clustering Algorithm[J]. Journal of System Simulation, 2015, 27(9): 2066-2074.

参考文献

[1] Eberhart R C, Kennedy J.A new optimizer using particle swarm theory[C]// Proceedings of the Sixth International Symposium on Micro Machine and Human Science. 1995, 1: 39-43.
[2] Dorigo M, Maniezzo V, Colorni A.Ant system: optimization by a colony of cooperating agents[J]. Systems, Man, and Cybernetics, Part B, IEEE Transactions on (S1083-4419), 1996, 26(1): 1-13.
[3] Li R, Shi S, Nian Q, et al. Research on Pattern Recognition of Gas Explosion Disaster Risk in Coal Mines Based on PSO-SVM[J]. China Safety Science Journal (S1003-3033), 2013, 23(5): 38-43.
[4] Das S, Suganthan P N.Differential evolution: a survey of the state-of-the-art[J]. Evolutionary Computation, IEEE Transactions on(S1089-778X), 2011, 15(1): 4-31.
[5] Banks A, Vincent J, Anyakoha C.A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications[J]. Natural Computing (S1567-7818), 2008, 7(1): 109-124.
[6] Van der Merwe D W, Engelbrecht A P. Data clustering using particle swarm optimization[C]// The 2003 Congress on Evolutionary Computation, IEEE. USA: IEEE: 2003, 1: 215-220.
[7] Horng M H.Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation[J]. Expert Systems with Applications (S0957-4174), 2011, 38(11): 13785-13791.
[8] He S, Wu Q H, Saunders J R.Group search optimizer: an optimization algorithm inspired by animal searching behavior[J]. Evolutionary Computation, IEEE Transactions on (S1089-778X), 2009, 13(5): 973-990.
[9] Barnard C J, Sibly R M.Producers and scroungers: a general model and its application to captive flocks of house sparrows[J]. Animal Behaviour (S0003-3472), 1981, 29(2): 543-550.
[10] Yan X, Yang W, Ma H, et al. Soft Sensor for Ammonia Concentration at the Ammonia Converter Outlet Based on an Improved Group Search Optimization and BP Neural Network[J]. Chinese Journal of Chemical Engineering (S1004-9541), 2012, 20(6): 1184-1190.
[11] Li L, Xu X T, Liu F, et al. The group search optimizer and its application to truss structure design[J]. Advances in Structural Engineering (S1369-4332), 2010, 13(1): 43-52.
[12] Cui Z, Gu X.A discrete group search optimizer for hybrid flowshop scheduling problem with random breakdown[J]. Mathematical Problems in Engineering (S1024-123X), 2014.
[13] Frey B J, Dueck D.Clustering by passing messages between data points[J]. Science (S0036-8075), 2007, 315(5814): 972-976.
[14] Zhang K, Gu X S.A Fast Global Group Search Optimizer algorithm[C]// Proceeding of the IEEE International Conference on Information and Automation. USA: IEEE, 2014: 59-64.
[15] Lichman, M. UCI Machine Learning Repository. [DB/OL]. (2015-07-29) [2015-5-15] http://archive.ics.uci.edu/ml.
[16] Zhang J, Tuo X, Yuan Z, et al. Analysis of FMRI data using an integrated principal component analysis and supervised affinity propagation clustering approach[J]. Biomedical Engineering, IEEE Transactions on (S0018-9294), 2011, 58(11): 3184-3196.