基于遗传算法的K-means聚类算法分析研究

近年来,随着信息技术的发展,信息资源的经济和社会价值越来越重要。通过数据挖掘,从大量的数据资料中发现有价值的、人们感兴趣的信息或知识,可以达到为科学决策提供支持的目的。聚类分析是数据挖掘的一项基本任务,是一种无监督的分类方法。聚类的目标是把一个无类别标记的数据集按某种准则划分成不同的簇,使相同簇中数据的相似性尽可能小,而不同簇间数据相似性尽可能大。聚类的应用非常广泛,无论是在商务领域,还是在Web文档分类、图像处理等其它领域,都得到有效的应用。目前聚类算法大体上分为基于划分的方法、基于层次的方法、基于模型的方法、基于网格的方法、基于密度的方法等。 K-means算法是聚类分析的主要算法之一,是一种基于划分的聚类算法。该算法随机选取k个点作为初始聚类中心,通过一个迭代过程完成聚类。该算法有它固有的不足:它容易陷入局部极小值而得不到全局最优解;算法在进行聚类时要求有固定的K值,这对于没有经验的用户来说很困难;初始中心的选择对聚类结果有很大影响;一般的聚类算法对孤立点数据和噪声比较敏感。 遗传算法是一种通过模拟自然进化过程搜索最优解的算法,它通过基因组合、交叉、变异、自然选择等一系列过程达到优化的目的。在这些过程中,通过“优胜劣汰”的原则淘汰掉解较差的基因,使得解朝着好的方向发展。它从一组初始可行解出发在只需要目标函数这一信息的条件下实现对可行域的全局高效搜索并以概率1收敛到全局最优解,具有隐含并行性和对全局信息的有效利用能力的显著特点,这种良好的特性使得遗传算法成为函数优化和组合优化的有力工具。因此,将遗传算法和K-means算法有效结合,充分发挥遗传算法的全局寻优能力和K-means算法的局部搜索能力,可以更好地提高聚类质量。 针对传统遗传算法和聚类算法存在的缺陷,本文提出了一种改进的遗传k均值算法,该算法的改进之处:在遗传算法中采用自识别交叉算子和自适应变异算子,自识别交叉算子可以保证群体的优良模式遗传到下一代,加快了算法收敛速度,自适应变异算子扩大了搜索范围,增强了算法跳离局部最优解的能力;优化K-means聚类算法的初始中心,避免初始中心选择的随机性;根据适应度函数动态地确定合适的聚类数k值;使用了基于加权的K-平均的方法计算类中心,减小K-means算法对噪声和孤立点数据的敏感性。该文实验采用标准数据集来测试改进算法的有效性,设计了三套实验方案对改进算法和其它算法进行测试,并以图表和表格的形式对实验结果进行比较说明,得出了改进算法优于其它算法的结论。