基于改进量子粒子群的K-means聚类算法及其应用

K-means clustering algorithm based on improved quantum particle swarm optimization and its application

针对传统K-means聚类算法受初始类中心影响导致聚类准确度较低的问题,利用量子粒子群优化算法全局搜索能力强、收敛速度快的优势,提出一种基于改进量子粒子群的K-means聚类算法.为防止量子粒子群优化算法陷入局部极值,采用具有高斯扰动的局部吸引子以提高种群跳出局部最优的能力;为提高算法的收敛速度,采用加权更新种群平均最优位置以充分发挥精英粒子的优势;通过对收缩-扩张因子和随机变量参数进行交叉实验,选出最佳参数组合策略.在标准测试函数上的仿真结果表明:改进的量子粒子群优化算法在寻优精度、收敛速度以及稳定性上都有显著提高;通过对比7种聚类算法在UCI数据集上的聚类结果可知,所提出的聚类算法具有更好的聚类性能,可以有效降低K-means对初始聚类中心的依赖.最后,将该方法应用于我国鲜食葡萄市场客户分类中,以验证该方法的有效性和实用性.通过实证分析可知,基于改进量子粒子群的K-means聚类算法结构简单、精度高,具有一定的推广性.

The original K-means clustering algorithm is seriously affected by initial centroids of clustering and easy to fall into local optima.To overcome these shortages,this paper uses the quantum particle swarm optimization(QPSO)which has power ability of global search and quick convergence rate to optimize the initial clustering centers of the original K-means algorithm.As the QPSO algorithm can easily fall into the local optimum,the local attractor with Gauss disturbance is used to make the population jump out of the local extremum.To improve the convergence speed of the algorithm,the weighted average best position is used to take advantage of the elite particles.The contraction-expansion factors and random variables are combined in order to select the best parameter strategy.The simulation results on various benchmark problems show that the optimization accuracy,convergence speed and stability of the improved optimization algorithm are significantly improved.Experimental results on the typical UCI datasets show that the proposed method is superior to compared algorithms.Finally,this method is applied to the customer classification of table grapes,which shows the effectiveness and practicability of the proposed clustering algorithm.Through the empirical analysis,it is also proved that this model can be promoted and applied.