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

张敏

（浙江工业职业技术学院，浙江 绍兴 312000）

【摘要】在k均值聚类算法设计过程中引入遗传算法，提出一种改进的k均值聚类遗传算法。在新的算法设计中对适度函数重新构造，同时在遗传算法的变异操作中引入新的变异算子，该变异操作主要利用对种群个体长度的不断改变来实现聚类数的自动增减，即使k值不断向最佳聚类值靠近。

教育期刊网 http://www.jyqkw.com
关键词 遗传优化；聚类算法；变异操作

遗传算法是利用自然选择和遗传机制的原理，模拟生命进化理论过程，在全局进行搜索和寻优的一种全局算法。由于其在解决许多复杂问题的过程中，取得比较好的效果，因而获得广泛应用。近年来，遗传算法被引入数据挖掘领域，作为搜索的一个重要研究方向，获得极大关注。

在k均值聚类算法中引入遗传算法，对算法进行改进，形成k均值遗传算法。该算法通过对种群的不断遗传迭代，不断搜索局部最优解，极大增加了取得全局最优解的概率。目前，基于遗传算法的k均值聚类算法主要致力于解决如下问题：

（1）针对聚类问题的解空间进行高效编码。

（2）构造适应度函数。通过适应度函数用来衡量个体对聚类问题的适应程度，在整个遗传过程中都起到至关重要的作用，如果某个体所代表质量好的聚类划分，则其适应度就高；相反，其适应度就低。

（3）确定遗传算子的选择及各控制参数值。不同的遗传算子将会直接关系到聚类中心点的优化及最终聚类数的确定，而各个控制参数值的设置将会影响整个算法是否能搜索到全局最优解，即是否会产生最佳聚类结果。

本文用一种新的变异操作来代替原有变异算子。这种变异操作主要是求解个体适应度函数，决定聚类数k值的变化方向，由于初始聚类数k值并非最佳值，因此将最初种群中具有最大适应度值的个体作为最佳聚类数的榜样个体，其他个体的长度(即k值)向该个体不断靠扰。

1　算法的基本流程

（1）算法迭代初始化参数值，如：初始聚类数k，种群大小m，交叉概率pc，变异概率pm，最大迭代次数t等。

（2）随机产生初始种群，选取个体中心，采用k均值算法对数据进行分类。

（3）计算种群个体的适应度值。

（4）不断反复执行选择、交叉、变异等操作，生成下一代群体。

（5）重复执行（3）、（4），直到达到最大迭代次数。

（6）通过计算种群个体的适应度值，输出最优分类个体。

2　遗传算子的设计

2.1　选择操作

选择操作一般是建立在对个体适应度评价的基础上。选择操作的主要目的是为了避免基因缺失问题，提高全局收敛性和计算效率。在文中选择操作使用的是最常用的轮盘选择方法，其主要思想是：个体被选中的概率直接取决于该个体相对应的适应度大小。

2.2　交叉操作

交叉操作是遗传算法中区别于一般进化算法的主要特征。通过交叉操作产生新的个体，并能够直接影响到整个算法的全局搜索能力。文中主要采用算术交叉方法(Arithmetical Crossover)。

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

3　实验验证分析

文了验证文中提出的改进后的遗传优化k均值聚类算法的性能，检测其有效性，我们建立了仿真试验环境。选取不同的数据集来对新算法进行深层的分析。同时，在实验过程中将改进后的k均值聚类算法与一般算法进行对比，通过采用Iirs数据集与Glass数据集的实际分析应用，从初始聚类数、最终聚类数、类内距变化及准则函数值等四个方面进行对比分析。实验的相关参数初始值设定为：

（1）种群大小为20，交叉概率为固定值0.6，变异概率为0.01,最大迭代次数为100。

（2）初始的聚类数，即初始k值又可分为三种情况：少于实际聚类数、等于实际聚类数、以及多于实际聚类数。

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

图1为改进的k均值遗传算法应用于Iris数据集迭代二十次，其最大适值的变化情况，可以看出根据最大适值的变化，k值可以识别出最佳聚类数，并且向其靠近。

教育期刊网 http://www.jyqkw.com
参考文献

［1］孙秀娟.基于遗传算法的K-means聚类算法分析研究[D].济南:山东师范大学,2009.

［2］张建辉.K-means聚类算法研究及应用[D].武汉:武汉理工大学,2007.

［3］周明孙,树栋.遗传算法原理及应用[M].北京:国防工业出版社,19.

［责任编辑：汤静］