一种基于遗传优化的k均值聚类算法研究

《一种基于遗传优化的k均值聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一种基于遗传优化的k均值聚类算法研究张敏（浙江工业职业技术学院，浙江绍兴312000）【摘要】在k均值聚类算法设计过程中引入遗传算法，提出一种改进的k均值聚类遗传算法。在新的算法设计中对适度函数重新构造，同时在遗传算法的变异操作中引入新的变异算子，该变异操作主要利用对种群个体长度的不断改变来实现聚类数的自动增减，即使k值不断向最佳聚类值靠近。.jyqk，交叉概率pc，变异概率pm，最大迭代次数t等。（2）随机产生初始种群，选取个体中心，采用k均值算法对数据进行分类。（3）计算种群个体的适应度值。（4）不断反复执行选择、交叉、变异等操作，生成下一代群

2、体。（5）重复执行（3）、（4），直到达到最大迭代次数。（6）通过计算种群个体的适应度值，输出最优分类个体。2　遗传算子的设计2.1　选择操作选择操作一般是建立在对个体适应度评价的基础上。选择操作的主要目的是为了避免基因缺失问题，提高全局收敛性和计算效率。在文中选择操作使用的是最常用的轮盘选择方法，其主要思想是：个体被选中的概率直接取决于该个体相对应的适应度大小。2.2　交叉操作交叉操作是遗传算法中区别于一般进化算法的主要特征。通过交叉操作产生新的个体，并能够直接影响到整个算法的全局搜索能力。文中主要采用算术交叉方法(ArithmeticalCro

3、ssover)。变异操作通过不断对种群中个体基因的增减，实现最终聚类数的确定。变异概率能够决定变异操作的实施频率，其大小亦能够影响种群的多样性及算法收敛性能。为了简化起见，对变异概率采取固定值，考虑到算法执行的实际情况，初始的k值选择具有不确定性，存在较大变数，开始时可将变异概率值选取大些，随着k值不断接近最优值，其变异概率将不断减少。在整个算法执行过程中，变异概率对最终的聚类结果起到直接的影响作用，因此，对于变异概率的设置，可以引入自适应变异操作。3　实验验证分析文了验证文中提出的改进后的遗传优化k均值聚类算法的性能，检测其有效性，我们建立了仿真

4、试验环境。选取不同的数据集来对新算法进行深层的分析。同时，在实验过程中将改进后的k均值聚类算法与一般算法进行对比，通过采用Iirs数据集与Glass数据集的实际分析应用，从初始聚类数、最终聚类数、类内距变化及准则函数值等四个方面进行对比分析。实验的相关参数初始值设定为：（1）种群大小为20，交叉概率为固定值0.6，变异概率为0.01,最大迭代次数为100。（2）初始的聚类数，即初始k值又可分为三种情况：少于实际聚类数、等于实际聚类数、以及多于实际聚类数。表1为改进后算法运行结果，其中C(x)与E值均为平均值。程序中算法根据适值得变化来识别最终的最佳

5、聚类数，并不断向最优值聚拢。随着算法迭代次数的增加，平均类间距在不断缩小，各类间更加紧凑。从表中的准则函数E不难看出，改进算法虽然使k值向最佳聚数靠近，甚至可以达到最佳聚类，但最终的聚类结果却并非是最优聚类划分，如针对表中最后一行显示，当最终聚类数为6时，改进方法的最终聚类结果大于最佳k值的次数明显占很大比例，即最终聚类数偏大，这与在算法过程中聚类中心点的选取是有关的。图1为改进的k均值遗传算法应用于Iris数据集迭代二十次，其最大适值的变化情况，可以看出根据最大适值的变化，k值可以识别出最佳聚类数，并且向其靠近。.jyqkeans聚类算法分析研究

6、[D].济南:山东师范大学,2009.［2］张建辉.K-means聚类算法研究及应用[D].武汉:武汉理工大学,2007.［3］周明孙,树栋.遗传算法原理及应用[M].北京:国防工业出版社,19.［责任编辑：汤静］