基于ACO-PSO自适应的划分聚类算法
|
摘要
针对经典划分算法聚类数K先验未知及初始聚类中心随机选取,导致陷入局部最优的问题,提出一种基于ACO-PSO自适应的划分聚类算法。首先根据聚类算法类内相似度最大差异度最小和类间相似度最小差异度最大的基本原则,将个体轮廓系数作为最佳聚类数的检验函数,得到聚类算法的自适应K值;其次利用群智能搜索方法思想,有效结合了粒子群算法和蚁群算法的优点,先利用具有全局性和快速性的粒子群算法获得初始信息素分布,再利用具有正反馈性和并行性的蚁群算法得到精确解。最后在多个UCI数据集上的仿真结果表明,该算法不仅求解能力优于传统聚类算法及基于个体轮廓系数优化的初始聚类中心算法,而且聚类时间效率大大提高,应用于大数据收敛速度更加明显。
Aiming at the problem that the prior unknown clustering number K and the random selection of the initial clustering center for the classical partitioning algorithm lead to local optimum,we propose a partitioning clustering algorithm based on ACO-PSO adaptability.Firstly,according to the basic principle of the minimum difference and maximum similarity within the class and the maximum difference and minimum similarity between classes,the adaptive K value of the clustering algorithm is obtained by using the individual contour coefficient as the test function of the best clustering number.Secondly,in combination with advantages of particle swarm optimization algorithm and ant colony algorithm inspired by swarm intelligence search,the initial pheromone distribution is obtained by particle swarm optimization algorithm with wholeness and rapidity,and then the exact solution is got by ant colony algorithm with positive feedback and parallelism.Finally,the simulation on multiple UCI data sets shows that the proposed algorithm is not only superior to the traditional clustering and initial clustering center algorithm based on individual contour coefficient optimization,but also shortens clustering time greatly,which is more obvious in convergence speed when applied to big data.
Aiming at the problem that the prior unknown clustering number K and the random selection of the initial clustering center for the classical partitioning algorithm lead to local optimum,we propose a partitioning clustering algorithm based on ACO-PSO adaptability.Firstly,according to the basic principle of the minimum difference and maximum similarity within the class and the maximum difference and minimum similarity between classes,the adaptive K value of the clustering algorithm is obtained by using the individual contour coefficient as the test function of the best clustering number.Secondly,in combination with advantages of particle swarm optimization algorithm and ant colony algorithm inspired by swarm intelligence search,the initial pheromone distribution is obtained by particle swarm optimization algorithm with wholeness and rapidity,and then the exact solution is got by ant colony algorithm with positive feedback and parallelism.Finally,the simulation on multiple UCI data sets shows that the proposed algorithm is not only superior to the traditional clustering and initial clustering center algorithm based on individual contour coefficient optimization,but also shortens clustering time greatly,which is more obvious in convergence speed when applied to big data.
引文
[1]PELLEG D,MOORE A.X-means:extending K-Means with efficient estimation of the number of clusters[C]//Proceeding of the 17th international conference on machine learning.San Francisco,CA,USA:Morgan Kaufmann Publishers Inc.,2000:727-734.
[2]韩凌波.K-均值算法中聚类个数优化问题研究[J].四川理檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪工学院学报:自然科学版,2012,25(2):77-80.
[3]胡旺,Gary G.YEN,张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报,2014,25(5):1025-1050.
[4]VAN DER MERWE D W,ENGELBRECHT A P.Data clustering using particle swarm optimization[C]//Congress on evolutionary computation.Canberra,ACT,Australia:IEEE,2003:215-220.
[5]白树仁,陈龙.自适应K值的粒子群聚类算法[J].计算机工程与应用,2017,53(16):116-120.
[6]JAFAR O A M,SIVAKUMAR R.A study on fuzzy and particle swarm optimization algorithms and their applications to clustering problems[C]//IEEE international conference on advanced communication control and computing technologies.Ramanathapuram,India:IEEE,2012:462-466.
[7]潘晓英,陈雪静,李昂儒,等.基于自适应步长的萤火虫划分聚类算法[J].计算机应用研究,2017,34(12):3576-3579.
[8]朱春,李林国,郭剑.基于改进布谷鸟优化的模糊聚类图像分割[J].计算机科学,2017,44(6):278-282.
[9]梁冰,徐华.基于改进人工蜂群的核模糊聚类算法[J].计算机应用,2017,37(9):2600-2604.
[10]陈睿,赵志刚,张雁茹,等.基于改进粒子群蚁群算法的多目标双边匹配问题[J].计算机工程与设计,2017,38(1):220-225.
[11]柴宝杰,刘大为.基于粒子群优化的蚁群算法在TSP中的应用[J].计算机仿真,2009,26(8):89-91.
[12]潘鸿雁.基于蚁群算法和粒子群算法的Ad Hoc网络组播路由的研究[D].秦皇岛:燕山大学,2014.
[13]SHI Y,EBERHART R C.A modified particle swarm optimizer[C]//Proceedings of the IEEE international conference on evolutionary computation.[s.l.]:IEEE,1998:69-73.
[2]韩凌波.K-均值算法中聚类个数优化问题研究[J].四川理檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪工学院学报:自然科学版,2012,25(2):77-80.
[3]胡旺,Gary G.YEN,张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报,2014,25(5):1025-1050.
[4]VAN DER MERWE D W,ENGELBRECHT A P.Data clustering using particle swarm optimization[C]//Congress on evolutionary computation.Canberra,ACT,Australia:IEEE,2003:215-220.
[5]白树仁,陈龙.自适应K值的粒子群聚类算法[J].计算机工程与应用,2017,53(16):116-120.
[6]JAFAR O A M,SIVAKUMAR R.A study on fuzzy and particle swarm optimization algorithms and their applications to clustering problems[C]//IEEE international conference on advanced communication control and computing technologies.Ramanathapuram,India:IEEE,2012:462-466.
[7]潘晓英,陈雪静,李昂儒,等.基于自适应步长的萤火虫划分聚类算法[J].计算机应用研究,2017,34(12):3576-3579.
[8]朱春,李林国,郭剑.基于改进布谷鸟优化的模糊聚类图像分割[J].计算机科学,2017,44(6):278-282.
[9]梁冰,徐华.基于改进人工蜂群的核模糊聚类算法[J].计算机应用,2017,37(9):2600-2604.
[10]陈睿,赵志刚,张雁茹,等.基于改进粒子群蚁群算法的多目标双边匹配问题[J].计算机工程与设计,2017,38(1):220-225.
[11]柴宝杰,刘大为.基于粒子群优化的蚁群算法在TSP中的应用[J].计算机仿真,2009,26(8):89-91.
[12]潘鸿雁.基于蚁群算法和粒子群算法的Ad Hoc网络组播路由的研究[D].秦皇岛:燕山大学,2014.
[13]SHI Y,EBERHART R C.A modified particle swarm optimizer[C]//Proceedings of the IEEE international conference on evolutionary computation.[s.l.]:IEEE,1998:69-73.