基于改进遗传算法K―means聚类方法

1、基于改进遗传算法的Kmeans聚类方法大纲：K-means算法是聚类解析划分方法中的一种常用方法，也是目前在数据解析方法中最有应用远景的方法之一。但K-mean算法对初始聚类中心十分敏感，这对办理学生成绩等数据而言，会以致聚类结果极为不牢固。为此，提出基于改进遗传算法的K-means聚类算法。该算法利用遗传算法解决初始聚类中心，提高聚类结果的牢固性，但存在前期过早收敛和后期收敛过慢的缺点。将改进遗传K-means聚类算法应用于高职高专的学生考试成绩解析中，能够很好地解决传统遗传聚类算法对聚类结果的不牢固性问题，并经过聚类结果对学生考试成绩进行分类议论，利用所获得的数据聚类结果指导授课，进而提高

2、授课质量。要点词：聚类；K-means算法；遗传算法序言K-means算法是一种应用特别广泛的聚类解析方法，具有简洁、高效、可伸缩性强等优点，一般用簇内数据对象的均值表示K-means算法每个簇的中心1。但传统K-means算法存在诸多不足之处。比方，传统K-means算法对初始聚类中心敏感、算法需要指定参数K的值、输入的不同样K值随目标准则函数进行不同样次数的迭代、聚类结果颠簸大、简单陷入局部最优2。遗传算法拥有很强的鲁棒性和适应性，在解决大空间、多峰值、非线性、全局寻优能力等问题上拥有优势，但也存在着先期过早收敛和后期收敛过慢的缺点。基于改进遗传算法的K-means算法能够有效解决算法对初

3、始值K的依赖性，自动生成类K；同时严格采用初始中心点，加大各中心点之间的距离，防备初始聚类中心会选到一个类上，必然程度上战胜了算法坠入局部最优状态3-6。本文基于改进遗传算法进行学生成绩的K-means聚类解析，将学生的考试成绩依照不同样科目分成不同样的类簇，利用改进遗传算法解决初始聚类中心问题，进而在整体上归纳解析该门课程所拥有的特点属性，以及每门课程之间的联系性和差异性，以提高算法效率和正确性。而且，经过选择运算、交织运算和变异运算来加快算法的收敛性。1.1传统K-means聚类算法传统K-means算法随机选择聚类中心，其核心思想为：给出n个数据点，找出k个聚类中心，利用欧氏距离式计算每

4、个数据点与近来聚类中心的距离平方和最小值，依照近来原则把各数据点分到各个簇，利用式（1）计算每簇中数据对象的均值，采用目标准则函数（2）进行迭代运算，直到簇心的搬动距离小于某个给定的值。传统K-means算法描述以下：输入：n个数据集D，数据聚类个数k。输出：平方误差准则最小的k个簇的会集。详尽步骤以下：从数据集D中，输入聚类个数k和包含n个数据对象的数据库；随机选择k个对象作为初始聚类中心；依照簇中它们与聚类中心的相似度，将每个对象划分到相似的簇；重复-；更新簇的平均值，依照每个簇中对象的平均值，重新划分相应的对象；计算目标准则函数；直到每个目标准则函数不再发生变化，即方差议论函数开始收敛为

5、止。传统K-means算法划分方法是依照初始聚类中心来确定数据的初始化7。但是k个初始聚类中心的确定对聚类结果影响很大，由于步骤是随机选择k个对象作为初始聚类中心的。每次迭代使簇中节余的对象依照与簇中心的相似度重新划分到相似的簇。每次完成迭代运算，就会算出新的聚类中心，以及误差平方和准则函数（2）的值。若再进行一次迭代后，误差平方和准则函数的值不发生改变，说明算法已经收敛。在迭代过程中，函数（2）逐渐减少，直到为最少值为止。图1显示了K-means算法的迭代过程。传统K-means算法对初始聚类中心很敏感，采用不同样的初始聚类中心，会获得不同样聚类的结果，而且平时得不到全局最优解。因此，如何找

6、到一组较优的初始中心点，进而获得较好的聚类结果并除掉聚类结果的颠簸性值得研究8。传统K-means算法存在的主要问题以下：（1）不行估计聚类个数K，一般需起初指定。起初不能够确定给定的数据集最适合分为几个种类。有的算法依照类的自动合并和分裂获得较为合理的K值；有的依照方差解析理论，混杂统计量来确定最正确K值，并应用模糊划分来考据最佳分类数的正确性；有的则结合全协方差矩阵RPCL算法，逐渐删除只包括少量训练数据的类。但是从前的这些改进基本没有详尽应用到学生考试成绩系统中。（2）算法过多依赖于初始值并经常坠入局部极小解。不同样的初始值可能造成算法聚类结果的不牢固。K-means算法常采用误差平方和

7、准则函数作为聚类准则函数。聚类准则函数经常存在好多个局部极小值，但只有一个是全局最小。由于每次确定的初始聚类中心都会偏离非凸函数曲面的全局最优解的找寻范围，使用迭代运算，聚类准则函数只能达到局部最小，而不能够获得全局最小。因此，好多算法利用遗传算法进行初始化，以内部目标函数作为议论指标，但基于遗传的K-means算法（GA-K均值算法）存在先期过早收敛此后期收敛过慢的缺点。1.3基于改进遗传算法的K-means聚类算法思想本文提出了一种基于改进遗传算法的K-means算法，该算法结合K-means算法的高效性和局部找寻能力，以及改进遗传算法的全局优化能力，能够达到较好的聚类结果。染色体编码选择由于聚本数量大、数高，本文采用将各聚的中心坐d染色体，其在聚中心的数量K，其度K*d，m1，m2，mk，其中Xi=mj1，mj2，m