杨爽爽, 石鸿雁. 基于改进果蝇优化的密度峰值聚类算法[J]. 微电子学与计算机, 2022, 39(9): 26-34. DOI: 10.19304/J.ISSN1000-7180.2021.1307
引用本文: 杨爽爽, 石鸿雁. 基于改进果蝇优化的密度峰值聚类算法[J]. 微电子学与计算机, 2022, 39(9): 26-34. DOI: 10.19304/J.ISSN1000-7180.2021.1307
YANG Shuangshuang, SHI Hongyan. Density peak clustering algorithm based on improved fruit fly optimization algorithm[J]. Microelectronics & Computer, 2022, 39(9): 26-34. DOI: 10.19304/J.ISSN1000-7180.2021.1307
Citation: YANG Shuangshuang, SHI Hongyan. Density peak clustering algorithm based on improved fruit fly optimization algorithm[J]. Microelectronics & Computer, 2022, 39(9): 26-34. DOI: 10.19304/J.ISSN1000-7180.2021.1307

基于改进果蝇优化的密度峰值聚类算法

Density peak clustering algorithm based on improved fruit fly optimization algorithm

  • 摘要: 密度峰值聚类算法(Clustering by fast search and find of density peaks,DPC)的截断距离参数需人工干预,且参数选取对聚类结果产生较大的影响.为解决这一问题,提出了一种基于改进果蝇优化的密度峰值聚类算法.通过Tent混沌映射初始化果蝇种群,利用Tent混沌序列随机性、遍历性和规律性的特点来提高初始种群的多样性,增强算法的全局探索能力;并引入动态步长因子与柯西变异策略对基本果蝇优化算法(Fruit Fly Optimization Algorithm, FOA)的更新机制进行改进,加强局部勘探能力,帮助算法跳出局部最优;利用随机算法收敛准则从理论上对改进FOA算法的收敛性进行分析;在6个基准测试函数上进行实验仿真,结果表明改进的FOA算法具有更快的收敛速度及更高的求解精度;将改进FOA算法与DPC算法融合成新算法,利用改进FOA算法较强的寻优能力找到最佳截断距离并实现最终的聚类.实验结果表明,新算法在UCI数据集及人工数据集上的聚类性能均有改善,相较于DPC算法、FOA-DPC算法、FADPC算法及ACS-FSDP算法具有更优的性能指标,有效抑制了手动选取截断距离参数带来的影响问题.

     

    Abstract: The cutoff distance of clustering by fast search and find of density peaks (DPC) requires manual intervention, and the selection of the parameters has great influence on the results of the algorithm. To overcome this problem, a density peak clustering method based on improved fruit fly optimization algorithm is proposed. The population of fruit fly is initialized by the Tent chaotic mapping, and using the characteristics of randomness, ergodicity and regularity of Tent chaotic sequence, the diversity of the initial population and the global exploration ability of the algorithm are enhanced. And the basic fruit fly optimization algorithm is improved by introducing dynamic step factor and Cauchy mutation strategy to enhance its local exploration ability and help the algorithm jump out of the local optimization. The convergence of the improved FOA algorithm is analyzed theoretically by using the convergence criterion of random algorithm. The experimental results of six test functions show that the improved FOA algorithm has faster convergence speed and higher solution accuracy. The improved FOA and DPC algorithm are fused into a new DPC algorithm, using the effective optimization ability of the improved FOA to find the best cutoff distance and realize the final clustering. Experimental results show that the clustering performance of new algorithm under UCI data set and artificial data set are improved, the new algorithm outperforms DPC, FOA-DPC, FADPC, ACS-FSDP with the better performance indexes, and the effect of manually selecting truncation distance parameter is effectively suppressed.

     

/

返回文章
返回