一种基于改进差分进化的K-Means聚类算法研究

Research on K⁃Means clustering algorithm based on AGDE

为改进传统K-Means聚类算法中因随机选取初始聚类中心而导致聚类结果不稳定且效率低的缺点,提出一种基于改进差分进化的K-Means聚类算法(AGDE-KM)。首先,设计自适应操作算子来提升算法前期的全局搜索能力和后期的收敛速度;其次,设计多变异策略并引入权重系数,在算法的不同进化阶段发挥不同变异策略的优势,平衡算法的全局和局部搜索能力,加快算法的收敛速度;最后,提出一种基于当前种群最佳个体的高斯扰动交叉操作,为个体提供更优进化方向的同时保持种群在“维”上的多样性,避免算法陷入局部最优。将算法停止执行时输出的最优解作为初始聚类中心替代传统K-Means随机选取的聚类中心。将提出算法在UCI公共数据库中的Vowel、Iris、Glass数据集和合成数据集Jcdx上进行对比实验,误差平方和(SSE)相对于传统K-Means分别减小5.65%、19.59%、13.31%、6.1%,聚类时间分别减少83.03%、81.33%、77.47%、92.63%。实验结果表明,提出的改进算法具有更快的收敛速度和更好的寻优能力,显著提升了聚类的效果、效率和稳定性。

In order to improve the instability and low efficiency of clustering results caused by randomly selecting initial cluster centers in traditional K-Means clustering algorithms,a K-Means clustering algorithm based on adaptive guided differential evolution(AGDE-KM)is proposed.The adaptive operation operator is designed to improve the global search capability of the algorithm in the early stage and the convergence speed in the later stage.The multi-variation strategy is designed and the weight coefficient is introduced to play the advantages of different variation strategies in different evolutionary stages of the algorithm,balance the global and local search ability of the algorithm,and accelerate the convergence speed of the algorithm.A Gaussian perturbation crossover operation based on the best individual of the current population is proposed to provide a better evolutionary direction for the individual while maintaining the population diversity in"dimension",so as to avoid the algorithm from falling into local optimal.The optimal solution when the algorithm stops execution is used as the initial cluster center to replace the randomly selected cluster center of traditional K-Means.The comparative experiment of the proposed algorithm on the Vowel,Iris,and Glass datasets and the synthetic dataset Jcdx in the UCI public database are conducted.The results show that,in comparison with traditional K-Means,the sum of squared errors(SSE)is reduced by 5.65%,19.59%,13.31%,and 6.1%,respectively,and the clustering time is reduced by 83.03%,76.48%,77.47%,and 92.63%,respectively.The experimental results show that the proposed improved algorithm has faster convergence speed and better optimization finding ability,which can significantly improve the effectiveness,efficiency and stability of clustering.