基于K—means的改进人工蜂群聚类算法

本文是一篇算法论文范文,关于算法在职毕业论文开题报告,关于基于K—means的改进人工蜂群聚类算法相关毕业论文题目范文。适合算法及蜂群及计算机编程方面的的大学硕士和本科毕业论文以及算法相关开题报告范文和职称论文写作参考文献资料下载。

摘 要：针对K-means聚类算法对初始聚类中心敏感和易陷入局部最优解的缺点,提出一种基于K-means的人工蜂群（ABC）聚类算法.将改进的人工蜂群算法和K-means迭代相结合,使算法对初始聚类中心的依赖性和陷入局部最优解的可能性降低,提高了算法的稳定性.通过基于反向学习的初始化策略,增强了初始群体的多样性.利用非线性选择策略,改善了过早收敛问题,提高了搜索效率.通过对邻域搜索范围的动态调整,提高了算法收敛速度,增强了局部寻优能力.实验结果表明,该算法不仅克服了K-means算法稳定性差的缺点,而且具有良好的性能和聚类效果.

关 键 词：人工蜂群算法；聚类分析；K-means；反向学习；非线性选择

中图分类号：TP301.6文献标志码：A

0引言

聚类分析是一种重要的无监督学习技术,其目标是将数据集合分成若干类,使得同一类内的样本相似度尽可能大,而不同类间的样本相似度尽可能小,目前在机器学习、模式识别、Web挖掘以及图像量化等领域得到了广泛的应用[1].

K-means算法是一种常用的聚类算法,它具有良好的局部搜索能力,对较规则分布的数据进行聚类时能达到理想的聚类效果,由于高效和简单而被广泛应用,但同时存在对初始聚类中心敏感和易受孤立点的影响,导致聚类结果容易陷入局部最优解,鲁棒性不高.因此,许多学者研究并提出了一些基于K-means的改进聚类算法.文献[2]选择相互距离最远的k个处于高密度区域的点作为初始聚类中心,改善了K-means算法对初始聚类中心的依赖；文献[3]提出了一种采用密度指针（DensityPointer,DP）的聚类中心初始化方法,找到接近于真实聚类中心的数据点作为初始聚类中心；文献[4]引入密度和最近邻思想,提出了初始中心选择方法.这类算法的思想是通过找到恰当的初始聚类中心,进而提高K-means算法的聚类质量和稳定性,但这样改进的算法仍然是基于梯度下降的,因此不可避免地会陷入局部最优.由于智能优化算法具有较强的全局寻优能力,近年来被广泛应用于聚类分析并获得了较理想的效果.文献[5-6]提出的遗传算法与K-means结合的聚类算法有效解决了K-means算法对初始值过于依赖的缺点,但基本遗传算法自身存在的早熟现象使这些算法常常过早地收敛于局部最优解,且算法复杂使得聚类过程耗时较长.文献[7]将免疫粒子群算法与K-means算法相结合提出了一种基于免疫粒子群优化的聚类算法,虽然聚类效果和稳定性有了一定改善,但算法耗时较长.

人工蜂群（ArtificialBeeColony,ABC）算法[8]是Karaboga于2005年提出的一种模拟蜂群觅食行为的群体智能优化算法.由于其收敛速度较快、控制参数少、易于实现等优点[9],ABC算法受到众多学者的关注.函数优化测试表明,ABC算法比遗传算法、差分演化算法和粒子群优化算法具有更好的优化性能[10].同遗传算法相比,ABC算法不但具有遗传算法的全局寻优能力,同时具有较强的局部寻优能力；由于没有个体交叉、变异等操作,ABC算法的参数调整变得简单而易行,更适合计算机编程处理,在大多数情况下,比遗传算法更快地收敛于最优解,而且可以避免完全随机寻优的退化现象.本文提出了一种基于改进人工蜂群算法的聚类方法,将改进的人工蜂群算法和K-means迭代相结合,降低了初始聚类中心的依赖性和陷入局部最优解的可能性,有效提高了算法的聚类效果和稳定性,缩短了聚类时间.

综上所述,在相同的实验条件下对不同数据集的聚类结果表明,相比其他几种算法,本文将改进的人工蜂群算法和K-means相结合,既保证了聚类准确度和算法效率,而且算法表现出很好的稳定性,说明本文提出的改进人工蜂群聚类算法是一种可行的,适用于聚类问题并能获得较好聚类效果的算法.

5结语

本文在基本ABC算法基础上结合聚类问题对基本人工蜂群算法进行了改进,采用基于反向学习的群体初始化方案,使初始解尽可能均匀分布在搜索空间,增强了初始群体的多样性；利用非线性选择策略改善了基本ABC算法过早收敛的问题；通过对邻域搜索范围的动态调整增强了局部寻优能力；然后算法在聚类过程中将改进的人工蜂群算法和K-means迭代相结合,提高了算法的鲁棒性.另外,算法采用兼顾类内聚合度和类外分离度的聚类评价指标CHindex作为适应度函数,使聚类结果具有更高的可信度.在3组数据集上的实验结果表明,该算法具有良好的聚类效果和较高的稳定性.