基于改进人工蜂群算法的k均值聚类算法

《基于改进人工蜂群算法的k均值聚类算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于改进人工蜂群算法的K均值聚类算法摘要：针对K均值聚类（KMC）算法全局搜索能力差、初始聚类中心选择敏感，以及原始人工蜂群（ABC）算法的初始化随机性、易早熟、后期收敛速度慢等问题，提出了一种改进人工蜂群算法（IABC）。该算法利用最大最小距离积方法初始化蜂群，构造出适应KMC算法的适应度函数以及一种基于全局引导的位置更新公式以提高迭代寻优过程的效率。将改进的人工蜂群算法与KMC算法结合提出IABCKmeans算法以改善聚类性能。通过Sphere、Rastrigin、Rosenbrock和Griewank四

2、个标准测试函数和UCI标准数据集上进行测试的仿真实验表明，IABC算法收敛速度快，克服了原始算法易陷入局部最优解的缺点；IABCKmeans算法则具有更好的聚类质量和综合性能。关键词：人工蜂群算法；K均值聚类算法；适应度函数；位置更新公式；聚类0引言聚类作为一种无监督学习，是数据挖掘领域的一个重要研究方向。聚类就是将数据对象分组成多个簇（类），同一簇内的对象相似度尽可能大，不同簇间的对象相似度尽可能小。K均值聚类（KMeans8Clustering，KMC）算法是一种基于划分思想的聚类算法，它具有思路简单、聚

3、类快速、局部搜索能力强的优点；但也存在对初始聚类中心选择敏感、全局搜索能力较差、聚类效率和精度低的局限性问题。对于KMC算法对初始点敏感和全局搜索能力较差问题，吸引了很多学者对该问题的研究与改进。文献[1]基于谱图理论思想，采用密度敏感的相似性度量来计算对象的密度，启发式地生成样本初始中心，可以得到较高质量的初始中心；文献[2]在每个类内都有一个数据稠密区的假设基础上，提出了一种基于最小支撑树的聚类中心初始化方法，该方法提高了KMC算法的模式识别率，但增加了时间复杂度；文献[3]提出一种改进的粒子群优化（Pa

4、rticleSwarmOptimization，PSO）和KMC混合聚类算法，算法在运行过程中通过引入小概率随机变异操作增强种群的多样性，提高了KMC算法的全局搜索能力；文献[4]通过将遗传算法（GeneticAlgorithm，GA）的编码、交叉和变异思想融入KMC，充分结合KMC的局部寻优能力和遗传算法的全局寻优能力，提出了一种基于遗传算法的优化KMC算法，有效地解决了KMC易陷入局部收敛的问题。群体智能与仿生算法以其进化过程与初始值无关、搜索速度快、对函数要求低的优点，成为进化算法的一个重要分支，并吸引

5、了各个领域学者对其研究。目前，比较常见的群体智能与仿生算法有粒子群算法（ParticleSwarmOptimization，PSO）、细菌觅食算法（BacterialForaging8Algorithm，BFA）、人工鱼群算法（ArtificialFishSwarmAlgorithm，AFSA）、遗传算法（GA）和蚁群算法（AntColonyOptimization，ACO）等[5]。近年来，在优化领域中出现了一种新的随机型搜索方法――蜂群算法。Seeley于1995年最先提出了蜂群的自组织模拟模型，在该模型

6、中，虽然各社会阶层的蜜蜂只完成了一种任务，但是蜜蜂以“摆尾舞”、气味等多种方式在群中进行信息的交流，使得整个群体可以完成诸如喂养、采蜜、筑巢等多种工作。Karaboga于2005年将蜂群算法成功应用于函数的极值优化问题，系统地提出了人工蜂群算法（ArificialBeeColony，ABC），该算法简单，全局搜索能力好，鲁棒性强；但是，人工蜂群算法也存在着后期收敛速度较慢、容易陷入局部最优的问题。文献[6]通过引入反学习的初始化方法，有效提高了求解效率和解的质量；文献[7]通过引入人工蜂群的粒子群算法，利用粒

7、子群的局部搜索能力和人工蜂群的全局搜索能力，使得算法具有较快的收敛速度和很强的跳出局部最优的能力。鉴于KMC和ABC算法各自的特性，本文首先提出了一种改进的ABC（ImprovedABC，IABC）算法，利用提出的最大最小距离积法初始化蜂群，保证初始点的选择能够尽可能代表数据集的分布特征，并在迭代过程中使用新的适应度函数和位置更新公式完成寻优进化；然后将IABC算法应用到KMC中提出了IABCKmeans算法，以改善聚类性能。82改进的人工蜂群算法针对原始人工蜂群的初始化、适应度函数和位置更新公式，本文提出的

8、IABC算法使用最大最小距离积法初始化蜂群，克服原始人工蜂群算法初始化的随机性；并利用新的适应度函数及引入全局引导因子的位置更新公式进行迭代寻优。2.1使用最大最小距离积法初始化种群初始化在进化算法中显得尤为重要，因为它影响算法的全局收敛速度和解的质量。所以本文在文献[8-9]的基础上提出最大最小距离积法并用其初始化蜂群，这里的初始化处理不仅克服了蜂群初始化的随机性，也为后面的K均值聚类降低了对初始