内容发布更新时间 : 2024/11/18 20:19:16星期一 下面是文章的全部内容请认真阅读。

基于遗传算法的k-means聚类挖掘方法研究

(4) 被选出的个体参加交叉、变异操作产生新的群体；

(5) 计算出新群体中的各条染色体的适应度值，用上一代中所记录的最优个体替换掉新种群中的最差个体，这样产生了下一代群体。

这种遗传操作既不断提高了群体的平均适应度值，又保证了最优个体不被破坏，使得迭代过程向最优方向发展。 4.5.7交叉操作

交叉操作是把两个父个体的部分结构加以替换重组而产生新个体的操作，也称为基因重组。交叉的目的是为了能够在下一代产生新的个体，因此交叉操作是遗传算法的关键部分，交叉算子的还坏，在很大程度上决定了算法性能的好坏。

由于染色体以聚类中心矩阵为基因，造成了基因串的无序性，两条染色体的等位基因之间的信息不一定相关，如果采用传统的交叉算子进行交叉，致使染色体在进行交叉时，不能很好的将基因配对起来，使生成的下一代个体的适应值普遍较差，影响了算法的效率。为了改善这种情况，又因为本文所使用的是浮点数编码方式，本文采用了一种以算术交叉为基础的混合交叉算子，即基于最短距离基因匹配的算术交叉算子[58]。

算术交叉是指由两个个体的线性组合而产生出两个新的个体。假设在两个个体X1和X2之间进行算术交叉，则交叉后产生的新个体为：

???X1??X2?(1??)X1 ?? (4-9)

??X2??X1?(1??)X2其中，?为一个参数，当?为常数时，则交叉运算为均匀交叉，否则，为非均匀交叉。

假设待交叉的两条染色体为S1?x1(1)x2(1)?xk(1)和S2?x1(2)x2(2)?xk(2)(其中

xi(i?1,2?k)为一个聚类中心)，则该混合交叉算子具体操作如下：

(1) 首先比较染色体S1?x1(1)x2(1)?xk(1)的第一个基因x1(1)与S2?x1(2)x2(2)?xk(2)上的每个基因的距离；

(2) 将S2上与x1(1)距离最近的基因xi(2)选出，并放在一条与S2等长的空染色

?上； 体S2(3) 按照上面方法依次比较S1上其他基因与S2上剩余基因的距离，并把每次

40

青岛科技大学研究生学位论文

?上，生成了一条与S1相配对的染色体选出的基因按顺序放在S2??x1S2(2)?x2(2)??xk(2)?

?进行算术交叉得到下(4) 根据交叉概率随机选取一个交叉位置j，对S1和S2一代个体S1*和S2*。

最近邻基因匹配的算术算子能够尽量保证产生有意义的新个体，以提高遗传算法的收敛速度。 4.5.8变异操作

在生物的自然进化的过程中，其细胞分裂的过程可能会出现某些差错，导致变异情况的发生。变异操作就是模仿这种情况产生的。所谓变异操作，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位来替换，从而形成一个新的个体。变异的目的有二：一是增强算法的局部搜索能力；二是增加种群的多样性，改善算法的性能，避免早熟收敛。变异操作既可以产生种群中没有的新基因又可以恢复迭代过程中被破坏的基因。

常用的变异算子有基本位变异、均匀变异、边界变异、非均匀变异和高斯近似变异。均匀变异是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码操作中各个基因座上的原有基因值。而对于浮点数编码的个体，若某一变异点处的基因的取值范围为[Umin,Umax]，变异操作就是用该范围内的一个随机数去替换原基因值。针对本文所使用的是浮点数编码方式，这里采用均匀变异算子来完成变异操作。

假设一条染色体为S?x1x2?xi?xk，则均匀变异的具体操作过程如下： (1) 依次指定个体编码串中的每个基因座为变异点，并确定每个基因点的取值范围[Umin,Umax]；

(2) 对每一个变异点，以变异概率Pm从对应基因的取值范围内取一个随机数来代替原有值。其中变异点的新基因值为：

xi?Umin?r(Umax?Umin) (4-10) 式中，r为[0,1]范围内符合均匀概率分布的一个随机数。

? 41

基于遗传算法的k-means聚类挖掘方法研究

4.5.9 k-means优化操作(KMO)

由于k-means是一种局部搜索能力强的算法，本算法在每一代执行完遗传操作后引入了k-means算法中的一个操作步骤k-means操作，对新生种群中的每个个体进行k-means优化，优化后的群体作为下一代种群进入演化。这样不仅可以提高混合算法的局部搜索能力，同时又有利于提高其收敛速度。具体的优化操作如下：

(1) 根据遗传操作产生的新种群中每条染色体的聚类中心编码值，按照等式(4-3)对样本进行划分，计算出各自的分类矩阵U；

(2) 根据分类矩阵U，按照式(4-4)计算新的聚类中心并进行编码；

(3) 对新的聚类中心重新计算适应度值，找出当前种群中的最差个体，用选择操作所记录的上一代的最优个体替换掉它。

经k-means优化操作后产生新一代种群开始下一轮遗传操作。 4.5.10算法终止条件

算法终止条件如下：

(1) 算法迭代次数超过设定的最大迭代次数T；

(2) 运行过程中得到相同最优个体的适应度值次数连续出现超过某一阈值。 只要满足以上两个条件中的任何一个条件则算法结束。在每次进行选择、交叉、变异、优化操作之后，记录当前子代中适应度最高的个体，算法运行结束后，适应度最高的个体为聚类问题的最优解。

4.6本章小结

本章首先对k-means算法思想进行了详细的描述，分析了k-means算法的优点和缺点。然后，针对算法的特点进行了讨论，并给出了一些现有的改进方法。最后，将k-means算法和遗传算法相结合并加以改进，提出了改进型遗传k-means算法，并给出了改进算法策略以及算法流程。

42

青岛科技大学研究生学位论文

第五章 实验结果与比较分析

5.1实验平台

为了检测本文提出的改进型遗传k-means聚类算法的有效性，我们在一定的环境下对算法进行了仿真实验。实验硬件环境是Intel(R) Pentium(R) D CPU 2.8G，512M内存，160G硬盘；软件环境是Windows XP操作系统，Matlab7.0。

5. 2 实验结果和分析

下面通过三组实验对k-means算法、改进的遗传k-means算法的算法性能进行测试和比较。每组实验都给出了最终的聚类结果图，聚类正确率，目标函数最小值。 5.2.1实验一

在本实验中，用给定的一组包含两类的数据集作为测试样本。该数据集共包含20个数据点，具体数据如下表所示。对于该数据集，聚类数k的取值为2。

表5-1测试数据1 Table.5-1 Test data1

数据标号 1 2 3 4 5 6 7 8 9 10 x 1.0 1.5 1.5 2.0 1.5 2.0 1.0 2.0 1.0 8.0 y 2.0 0.5 1.0 1.5 2.0 0.5 1.0 2.5 2.5 7.0 数据标号 11 12 13 14 15 16 17 18 19 20 x 7.0 8.0 9.0 9.0 7.0 8.0 9.5 9.0 9.5 8.0 y 8.0 8.0 8.0 6.0 7.0 9.0 7.0 7.0 8.0 6.0 本次实验中，改进算法的有关参数设置如下：初始种群Psize=20，交叉概率

43

基于遗传算法的k-means聚类挖掘方法研究

Pc=0.9，变异概率Pm=0.01，最大迭代次数为T=100，聚类个数K=2。k-means算法的迭代次数T=100。图5-1为原始数据集1，图5-2为k-means算法聚类的结果，图5-3为IGKA算法的聚类结果。

图5-1 原始数据分布图 Fig.5-1 Initial data scattergram

图5-2 k-means算法聚类结果

Fig.5-2 The clustering result of k-means methods

44