基于遗传算法的聚类分析小论文

苏良碧周润景

内蒙古大学电子信息工程学院，呼和浩特，010021

摘要：遗传算法是一种模拟自然进化的优化搜索算法，它仅依靠适应度函数就可以搜索最优解。本文介绍了一种基于遗传算法的聚类分析方法，采用浮点数编码方式对聚类的中心进行编码，并用特征向量与相应聚类中心的欧氏距离的和来判断聚类划分的质量，通过选择、交叉和变异操作对聚类中心的编码进行优化，得到使聚类划分效果最好的聚类中心。实验结果显示，该方法的聚类划分能得到比较满意的效果。

关键词：遗传算法；聚类；适应度函数；GA

Cluster Analysis Which Based on Genetic Algorithm

Su Liangbi

College of Electronic Information Engineering，Inner Mongolia University，Hohhot

【Abstract】：Genetic Algorithm is a optimized search approach which simulates the natural evolution,it can search the optimal solution only by fitness function.This paper introduce a cluster analysis algorithm which base on GA,it uses floating-point encoding method to encode the center of the cluster,and use Euclidean distance between the feature vector and the corresponding cluster center to determine the quality of clustering,it optimizes the encoding of the cluster centers by selection,crossover and mutation operations,it can obtain the cluster centers which can make the best clustering.Experimental results show that clustering use this method can reach satisfied results.

1概述

遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。遗传算法使用群体搜索技术，通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易实现、应用效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理决策等领域得到了广泛的应用。遗传算法呈现出的是一种通用的算法框架，该框架不依赖于问题的种类。遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型复杂非线性系统，它更表现出了比其他传统优化方法更加独特和优越的性能。

聚类分析是一种新兴的多元统计方法，是当代分类学与多元分析的结合。聚类分析是将分类对象置于一个空间中，依据样本间关联的度量标准将其自动分成几个群组，且使同

一群组内的样本相似，而属于不同群组的样本相异的一组方法。聚类的样本是用度量指针的一个向量表示，即用空间的一个点来表示。同类中的样本比属于不同类的样本彼此具有更高的相似性。聚类分析通常是基于距离的，通过构造一个m 维空间的距离函数，利用这个距离函数来进行聚类。

2遗传聚类算法

2.1算法的基本流程

遗传算法的一个优点是不需要待解问题领域的特殊知识，因此用遗传算法求解问题的流程基本相同。

图1基于遗传算法聚类的基本流程

2.2编码方法

在遗传聚类问题中，可采用的染色体编码方式有两种：一种按照数据所属的聚类划分来生成染色体的整数编码方式；另一种是把聚类中心(聚类原型矩阵)作为染色体的浮点数编码。由于聚类问题的解是各聚类中心，因此本文采用基于聚类中心的浮点数编码。

所谓的将聚类中心作为染色体的浮点数编码，就是把一条染色体看成是由K 个聚类中心组成的一个串。具体编码方式如下：对于D 维样本数据的K 类聚类分析，基于聚类中心的染色体结构为：

}

,...,,,...,,...,,,,...,,{212222111211kd k k d d x x x x x x x x x S =即每条染色体都是一个长度为k ×d 的浮点码串。这种编码方式意义明确、直观，避免了二进制编码在运算过程中反复进行译码、解码以及染色体长度受限等问题。

2.3种群初始化

确定了编码方式之后，接下来要进行种群初始化。初始化的过程是随机产生一个初始种群的过程。首先从样本空间中随机选出K 个个体，K 值由用户自己来指定，每个个体表示一个初始聚类中心，然后根据我们所采用的编码方式将这组个体(聚类中心)编码成一条染色

体。然后重复进行Psize 次染色体初始化(Psize 为种群大小)，直到生成初始种群。

2.4适应度函数设计

根据前章的介绍可知遗传算法中的适应度函数是用来评价个体的适应度、区别群体中个体优劣的标准。个体的适应度越高，其存活的概率就越大。聚类问题实际上就是找到一种划分，该划分使待聚类数据集的目标函数c G （∑∑===−=c j n k j j j k c j c j m m x

G 112)(),...2,1(,||||是聚

类中心，k x 是样本）达到最小。遗传算法在处理过程中根据每个染色体（K 个聚类中心）进行聚类划分，根据每个聚类中的点与相应聚类中心的距离作为判别聚类划分质量好坏的准则函数c G ，c G 越小表示聚类划分的质量越好。

遗传算法的目的是搜索使目标函数c G 值最小的聚类中心，因此可借助目标函数来构造适应度函数如下式：

c

G fit 1

=由上式可以看出，目标函数值越小的聚类中心，其适应度也就越大；目标函数值越大的聚类中心，其适应度也就越低。

2.5选择操作

在生物进化的过程中，对生存环境适应能力强的物种将有更多的机会遗传到下一代；而适应能力差的物种遗传到下一代的机会就相对较少。遗传算法中的选择操作体现了这一“适者生存”的原则：适应度越高的个体，参与后代繁殖的概率越高。遗传算法中的选择操作就是用来确定如何从父代群体中按照某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。选择操作是建立在对个体的适应度进行评价的基础之上。进行选择操作的目的是为了避免基因缺失、提高全局收敛性和计算效率。

为了保证适应度最好的染色体保留到下一代群体而不被遗传操作破坏掉，根据遗传算法中目前已有的选择方法，本文采用了轮盘赌选择算子。该选择算子具体操作如下：

（1）首先在计算完当前种群的适应度后，记录下其中适应度最大的个体；

（2）再根据各个体的适应度值size i P i S f ,...,2,1),(=计算各个体的选择概率：

∑==size P j j i i S

f S f P 1)

()

(式中，size P 为种群大小,∑=size P j j S

f 1)(为所有个体适应度的总和。

(3)根据计算出的选择概率，使用轮盘赌法选出个体；

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

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

这种遗传操作既不断提高了群体的平均适应度值，又保证了最优个体不被破坏，使得迭

2.6交叉操作

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

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

2.7变异操作

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

2.8进化过程

进化过程就是对种群中的染色体进行选择，交叉和变异操作，然后计算出每个进化个体的适应度，并找出其中适应度最大的个体来代替上一次进化过程中适应度最差的个体，从而达到了优胜劣汰的效果。

2.9根据遗传算法得出的聚类中心进行聚类

经过maxgen代进化后，求出群体中适应度最大的染色体，解码出聚类中心，并根据得出的聚类中心进行聚类划分，输出最后聚类结果。

3实验结果

本文通过对酒的种类进行聚类分析来验证遗传算法的可行性，不同类型的酒是由多种成分按不同的比例构成的，兑酒时需要三种原料（X,Y,Z），现在已测出不同酒中三种原料的含量，需要判定它属与哪种类型。这组数据包括51个三维平面上的点，总共可以分为四类。采用遗传算法的初始设置如下：交叉概率pcross=0.9、遗传概率pmutation=0.01、进化代数（迭代次数）maxgen=100，种群规模sizepop=100。

图2maxgen=100，种群规模sizepop=100时的聚类结果

图2maxgen=100，种群规模sizepop=100时的适应度函数曲线此时的聚类结果明显是错误的，这是因为：种群规模太小，从而使得出现优秀个体的概率小；进化代数太小，种群没有达到优胜劣汰的效果。但是，随着种群规模和进化代数的增加，收敛速度也越来越慢。所以我们要选择一个合适的种群规模和进化代数。

表1设置不同种群规模和进化代数得到的聚类结果

种群规模进化代数运行次数准则函数平均值收敛速度平均值（秒）10010053472516.4466 500100530820.4470 1000150528354304.8456 1500200527907606.0212 2000200526745926.9998 25002505254071599.8 30003005242261966.5

图3maxgen=300，种群规模sizepop=3000时的聚类结果

图4maxgen=300，种群规模sizepop=3000时的适应度函数曲线

从以上结果可以看出，当进化代数maxgen=300，种群规模sizepop=3000时，就能得到正确的聚类结果。

4总结

本文给出了一种基于遗传算法的聚类分析方法。聚类分析是模式识别中非监督学习的一种重要方法，其基本思想是将空间中的特征向量按照它们之间的某种距离度量划分为若干个集合，使相同集合中的特征向量之间的距离较为接近。距离度量的方式有很多，对于N R 空间中的向量，最直观的距离度量是向量之间的欧氏距离||||c x d −=。遗传算法模拟生物进化的过程，具有很好的自组织、自适应和自学习能力，在求解大规模优化问题的全局最优解方面具有广泛的应用。聚类问题的解是各个集合的中心，通过对问题的解进行编码，然后对编码进行选择、交叉和变异操作，结合评价解好坏的适应度函数，就可找到按所选的评价标准来说是比较好的聚类划分。

我们可以看出，基于遗传算法的聚类对初始值的要求比较少，在聚类的过程中不用构造复杂的函数，但是缺点也是明显的，那就是聚类的结果具有很大的随机性，收敛速度也比较慢，今后需要对其改进。

参考文献

[1]傅景广,许刚,王裕国.基于遗传算法的聚类分析.计算机工程[J].2004.

[2]陆林花,王波.一种改进的遗传聚类算法.计算机工程与应用[J].2007

[3]Hall L O,Ozyurt I B,Bezdek J C.Clustering with a genetically optimized approach[J].IEEE Transactions on Evolutionary Computation,1999.

[4]孙即祥.现代模式识别（第二版）[M],北京：高等教育出版社，2008.

[5]王家耀.一个用于空间聚类分析的遗传K 均值算法[J].计算机工程.2006..

[6]张伟等，廖晓峰，吴中福．一种基于遗传算法的聚类新方法[J].计算机科学.2002.