第２４卷第２期 电脑开发与应用 文章编号：１００３—５８５０（２０１１）０２—０００７—０３ 基于遗传算法的聚类分析 Ｃｌｕｓｔｅｒ Ａｎａｌｙｓｉｓ ｂａｓｅｄ ｏｎ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ 苏良昱 苏良碧。 （ 许昌学院电气信息工程学院 河南许昌４６１０Ｏ０）（。内蒙古大学电子信息工程学院 呼和浩特０１００２１） 【摘 要】遗传算法是一种模拟自然进化的优化搜索算法，它仅依靠适应度函数就可以搜索最优解。介绍了一种 基于遗传算法的聚类分析方法，采用浮点数编码方式对聚类的中心进行编码，并用特征向量与相应聚类中心的 欧氏距离的和来判断聚类划分的质量，通过选择、交叉和变异操作对聚类中心的编码进行优化，得到使聚类划 分效果最好的聚类中心。实验结果显示，该方法的聚类划分能得到比较满意的效果。 【关键词】遗传算法，聚类，适应度函数，ＧＡ 中图分类号：ＴＰ３０１．６ 文献标识码：Ａ ＡＢＳＴＲＡＣＴ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｏｐｔｉｍｉｚｅｄ ｓｅａｒｃｈ ａｐｐｒｏａｃｈ ｗｈｉｃｈ ｓｉｍｕｌａｔｅｓ ｔｈｅ ｎａｔｕｒａｌ ｅｖｏｌｕｔｉｏｎ，ｉｔ ｃａｎ ｓｅａｒｃｈ ｔｈｅ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｏｎｌｙ ｂｙ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ．Ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅ ａ ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈ ｂａｓｅ ｏｎ ＧＡ，ｉｔ ｕｓｅｓ ｆｌｏａｔｉｎｇ—ｐｏｉｎｔ ｅｎｃｏｄｉｎｇ ｍｅｔｈｏｄ ｔｏ ｅｎｃｏｄｅ ｔｈｅ ｃｅｎｔｅｒ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒ，ａｎｄ ｕｓｅ Ｅｕｃｌｉｄｅａｎ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｔｈｅ ｆｅａｔｕｒｅ ｖｅｃｔｏｒ ａｎｄ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒ ｔＯ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｃｌｕｓｔｅｒｉｎｇ，ｉｔ ｏｐｔｉｍｉｚｅｓ ｔｈｅ ｅｎｃｏｄｉｎｇ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｂｙ ｓｅｌｅｃｔｉｏｎ，ｃｒｏｓｓｏｖｅｒ ａｎｄ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｉｏｎｓ，ｉｔ ｃａｎ ｏｂｔａｉｎ ｔｈｅ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｗｈｉｃｈ ｃａｎ ｍａｋｅ ｔｈｅ ｂｅｓｔ ｃｌｕｓｔｅｒｉｎｇ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｃｌｕｓｔｅｒｉｎｇ ｕｓｅ ｔｈｉｓ ｍｅｔｈｏｄ ｃａｎ ｒｅａｃｈ ｓａｔｉｓｆｉｅｄ ｒｅｓｕｌｔｓ． ＫＥＹＷＯＲＤＳ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ｃｌｕｓｔｅｒ，ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ，ＧＡ 遗传算法是借鉴生物的自然选择和遗传进化机制 殊知识，因此用遗传算法求解问题的流程基本相同。 而开发出的一种全局优化自适应概率搜索算法。遗传 算法使用群体搜索技术，通过对当前群体施加选择、交 叉、变异等一系列遗传操作，从而产生出新一代的群 体，并逐步使群体进化到包含或接近最优解的状态。由 于其具有思想简单、易实现、应用效果明显等优点而被 众多应用领域所接受，并在自适应控制、组合优化、模 式识别、管理决策等领域得到了广泛的应用。遗传算法 呈现出的是一种通用的算法框架，该框架不依赖于问 １、输入最大迭代次数ｉｎａｘ￣ｎ ２、种群大ｄ￣ｐｏｐｓｉｚｅ ３、输入交叉概率ｐｃｒｏｓｓ ４、输入变异概率ｐｍｕｔａｔｉｏｎ １、随机生成一个种群 ２、计算每个个体的适应度 ３、找出最好的个体，记录最好适应度和平均适应度 题的种类。遗传算法是一类具有较强鲁棒性的优化算 法，特别是对于一些大型复杂非线性系统，它更表现出 了比其他传统优化方法更加独特和优越的性能。 １、进行选择、交叉和变异操作 ２、计算每个个体的适应度 ３、找出适应度最大的个体 ４、代替上一次适应度最大的个体 一一一迭代次数是否小于ｍｘ———～是否小毫 一 Ｉ——一 ｇｅｎ＝＝＞二一ＩＩ 裳 。上Ｎ 聚类分析是一种新兴的多元统计方法，是当代分 类学与多元分析的结合。聚类分析是将分类对象置于 一输出适应度最大的个 体（最佳聚类中心） 个多维空间中，依据样本问关联的度量标准将其自 动分成几个群组，且使同一群组内的样本相似，而属于 不同群组的样本相异的一组方法。聚类的样本是用度 量指针的一个向量表示，即用多维空间的一个点来表 示。同类中的样本比属于不同类的样本彼此具有更高 的相似性。聚类分析通常是基于距离的，通过构造一个 ｍ维空间的距离函数，利用这个距离函数来进行聚类。 图１基于遗传算法聚类的基本流程 １．２编码方法 １遗传聚类算法 １．１算法的基本流程（如图１所示） 在遗传聚类问题中，可采用的染色体编码方式有 两种：一种按照数据所属的聚类划分来生成染色体的 整数编码方式；另一种是把聚类中心（聚类原型矩阵） 作为染色体的浮点数编码。由于聚类问题的解是各聚 遗传算法的一个优点是不需要待解问题领域的特 ＊ ２０１０—１Ｉ－２１收到，２０１０—１２—２９改回 ＊＊ 苏良昱，男，１９７９年生，硕士，研究方向：人工神经网络的应用研究。 基于遗传算法的聚类分析 类中心，因此本文采用基于聚类中心的浮点数编码。 所谓的将聚类中 ｆｌ，作为染色体的浮点数编码，就 是把一条染色体看成是由Ｋ个聚类中心组成的一个 串。具体编码方式如下：对于Ｄ维样本数据的Ｋ类聚 类分析，基于聚类中心的染色体结构为： Ｓ＝｛ １１， １２，…， １ｄ，ｚ２ｌ，ｚ２２，…，ｏＺ＂２ ，…，ｚ １，Ｉｚ ２，…， ｚ ） 即每条染色体都是一个长度为ｋ×ｄ的浮点码 串。这种编码方式意义明确、直观，避免了二进制编码 在运算过程中反复进行译码、解码以及染色体长度受 限等问题。 １．３种群初始化 确定了编码方式之后，接下来要进行种群初始化。 初始化的过程是随机产生一个初始种群的过程。首先 从样本空问中随机选出Ｋ个个体，Ｋ值由用户自己来 指定，每个个体表示一个初始聚类中心，然后根据我们 所采用的编码方式将这组个体（聚类中心）编码成一条 染色体。然后重复进行Ｐｓｉｚｅ次染色体初始化（Ｐｓｉｚｅ 为种群大小），直到生成初始种群。 １．４适应度函数设计 根据前章的介绍可知遗传算法中的适应度函数是 用来评价个体的适应度、区别群体中个体优劣的标准。 个体的适应度越高，其存活的概率就越大。聚类问题实 际上就是找到一种划分，该划分使待聚类数据集的目 标函数Ｇ（ 一 ｌｊ ’一 。，ｍ （ 一１，２，…， ｃ）是聚类中心，．２７ 是样本）达到最小。遗传算法在处理 过程中根据每个染色体（Ｋ个聚类中心）进行聚类划 分，根据每个聚类中的点与相应聚类中心的距离作为 判别聚类划分质量好坏的准则函数 ，Ｇｆ越小表示聚 类划分的质量越好。 遗传算法的目的是搜索使目标函数 值最小的 聚类中心，因此可借助目标函数来构造适应度函数如 下式： 一 由上式可以看出，目标函数值越小的聚类中心，其 适应度也就越大；目标函数值越大的聚类中心，其适应 度也就越低。 １．５选择操作 在生物进化的过程中，对生存环境适应能力强的 物种将有更多的机会遗传到下一代；而适应能力差的 物种遗传到下一代的机会就相对较少。遗传算法中的 选择操作体现了这一“适者生存”的原则：适应度越高 的个体，参与后代繁殖的概率越高。遗传算法中的选择 操作就是用来确定如何从父代群体中按照某种方法选 取哪些个体遗传到下一代群体中的一种遗传运算。选 择操作是建立在对个体的适应度进行评价的基础之 上。进行选择操作的目的是为了避免基因缺失、提高全 局收敛性和计算效率。 为了保证适应度最好的染色体保留到下一代群体 而不被遗传操作破坏掉，根据遗传算法中目前已有的 选择方法，本文采用了轮盘赌选择算子。该选择算子具 体操作如下： ①首先在计算完当前种群的适应度后，记录下其 中适应度最大的个体； ②再根据各个体的适应度值ｆ（ｓ ）， 一１，２，…， Ｐ毗 计算各个体的选择概率： Ｐｉ＝ ∑ｆ（Ｓ ） ＝１ Ｐ ｓ｛ 式中，Ｐ 为种群大小， ｆ（Ｓ ）为所有个体适应 度的总和。 ⑧根据计算出的选择概率，使用轮盘赌法选出个体； ④被选出的个体参加交叉、变异操作产生新的群体； ⑤计算出新群体中的各条染色体的适应度值，用 上一代中所记录的最优个体替换掉新种群中的最差个 体，这样产生了下一代群体。 这种遗传操作既不断提高了群体的平均适应度 值，又保证了最优个体不被破坏，使得迭代过程向最优 方向发展。 １．６交叉操作 交叉操作是把两个父个体的部分结构加以替换重 组而产生新个体的操作，也称为基因重组。交叉的目的 是为了能够在下一代产生新的个体，因此交叉操作是 遗传算法的关键部分，交叉算子的还坏，在很大程度上 决定了算法性能的好坏。 由于染色体以聚类中心矩阵为基因，造成了基因 串的无序性，两条染色体的等位基因之间的信息不一 定相关，如果采用传统的交叉算子进行交叉，致使染色 体在进行交叉时，不能很好地将基因配对起来，使生成 的下一代个体的适应值普遍较差，影响了算法的效率。 为了改善这种情况，又由于本文所使用的是浮点数编 码方式，本文采用了一种以随机交叉为基础的随机交 叉算子。 １．７变异操作 在生物自然进化的过程中，其细胞分裂的过程可 能会出现某些差错，导致基因变异情况的发生。变异操 作就是模仿这种情况产生的。所谓变异操作，是指将个 体染色体编码串中的某些基因座上的基因值用该基因 座的其他等位来替换，从而形成一个新的个体。变异的 目的有二：一是增强算法的局部搜索能力；二是增加种 第２４卷第２期 电脑开发与应用 群的多样性，改善算法的性能，避免早熟收敛。变异操 作既可以产生种群中没有的新基因又可以恢复迭代过 模和进化代数的增加，收敛速度也越来越慢。所以我们 要选择一个合适的种群规模和进化代数。 程中被破坏的基因。针对本文所使用的是浮点数编码 方式，这里采用随机变异算子来完成变异操作。 １．８进化过程 进化过程就是对种群中的染色体进行选择，交叉 和变异操作，然后计算出每个进化个体的适应度，并找 出其中适应度最大的个体来代替上一次进化过程中适 应度最差的个体，从而达到了优胜劣汰的效果。 １．９根据遗传算法得出的聚类中心进行聚类 经过ｍａｘｇｅｎ代进化后，求出群体中适应度最大 的染色体，解码出聚类中心，并根据得出的聚类中心进 行聚类划分，输出最后聚类结果。 ２实验结果 本文通过对酒的种类进行聚类分析来验证遗传算 法的可行性，不同类型的酒是由多种成分按不同的比 例构成的，兑酒时需要三种原料（Ｘ，ｙ，Ｚ），现在已测 出不同酒中三种原料的含量，需要判定它属与哪种类 型。这组数据包括５１个三维平面上的点，总共可以分 为四类。采用遗传算法的初始设置如下：交叉概率 ｐｃｒｏｓｓ一０．９、遗传概率ｐｍｕｔａｔｉｏｎ一０．Ｏ１、进化代数 （迭代次数）ｍａｘｇｅｎ一１ＯＯ，种群规模ｓｉｚｅｐｏｐ＝１ＯＯ。 ２．８ ２．６ ２．４ ２．２ ２ １．８ １．６ １．４ １．２ 图２ ｍａｘｇｅｎ一１００，种群规 图３ ｍａｘｇｅｎ一１００，种群规 模ｓｉｚｅｐｏｐ＝１００时的 模ｓｉｚｅｐｏｐ：１００时的 聚类结果 适应度函数曲线 此时的聚类结果明显是错误的，这是因为：种群规 模太小，从而使得出现优秀个体的概率小；进化代数太 小，种群没有达到优胜劣汰的效果。但是，随着种群规 表１设置不同种群规模和进化代数得到的聚类结果 种群规模 进化代数 运行次数 准则函数 收敛速度 平均值 平均值（ ） ｌＯ０ １００ ５ ３４ ７２５ １６．４４６ ６ ５００ １００ ５ ３０ ８２８ ９０．４４７ ０ １ ０００ ｌ５０ ５ ２８ ３５４ ３０４．８４５ ６ ｌ ５ＯＯ ２Ｏ０ ５ ２７ ９０７ ６０６．Ｏ２１ ２ ２ ０００ ２Ｏ０ ５ ２６ ７４５ ９２６．９９９ ８ ２ ５Ｏ０ ２５Ｏ ５ ２５ ４０７ １ ５９９．８ ３ ０００ ３ＯＯ ５ ２４ ２２６ １ ９６６．５ 图４ ｍａｘｇｅｎ一３００，种群规 图５ ｍａｘｇｅｎ一３００，种群规 模ｓｉｚｅｐｏｐ＝３ ０００时的 模ｓｉｚｅｐｏｐ￣－３ ０００时的 聚类结果 适应度函数曲线 从以上结果可看出，当进化代数ｍａｘｇｅｎ＝３００，种 群规模ｓｉｚｅｐｏｐ一３ Ｏ００时，就能得到正确的聚类结果。 ３ 总 结 给出了一种基于遗传算法的聚类分析方法。聚类 分析是模式识别中非监督学习的一种重要方法，其基 本思想是将多维空间中的特征向量按照它们之间的某 种距离度量划分为若干个集合，使相同集合中的特征 向量之间的距离较为接近。距离度量的方式有很多，对 于Ｒ 空间中的向量，最直观的距离度量是向量之间 的欧氏距离 —ＩＩ ｘ—ｃ Ｉｌ。遗传算法模拟生物进化的 过程，具有很好的自组织、自适应和自学习能力，在求 解大规模优化问题的全局最优解方面具有广泛的应 用。聚类问题的解是各个集合的中心，通过对问题的解 进行编码，然后对编码进行选择、交叉和变异操作，结 合评价解好坏的适应度函数，就可找到按所选的评价 标准来说是比较好的聚类划分。 可以看出，基于遗传算法的聚类对初始值的要求 比较少，在聚类的过程中不用构造复杂的函数，但是缺 点也是明显的，那就是聚类的结果具有很大的随机性， 收敛速度也比较慢，今后需要对其改进。 参考文献 ［１］ 傅景广，许 刚，王裕国．基于遗传算法的聚类分析 ［Ｊ］．计算机工程，２００４（４）：１１－１３． Ｅ２］ 陆林花，王波．一种改进的遗传聚类算法［Ｊ］．计算机 工程与应用，２００７（２）：２２—２４． ［３］ Ｈａｌｌ Ｌ ０，Ｏｚｙｕｒｔ Ｉ Ｂ，Ｂｅｚｄｅｋ Ｊ Ｃ．Ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ ａ Ｇｅｎｅｔｉｃａｌｌｙ Ｏｐｔｉｍｉｚｅｄ Ａｐｐｒｏａｃｈ ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，１９９９（３）： １５—１８． ［４］ 孙即祥．现代模式识别［Ｍ］．北京：高等教育出版社， ２００８． ［５］ 王家耀．一个用于空间聚类分析的遗传Ｋ均值算法 ［Ｊ］．计算机工程，２００６（７）：４４—４５． ［６］ 张 伟，廖晓峰，吴中福．一种基于遗传算法的聚类新 方法［Ｊ］．计算机科学，２００２（２）：７７—７９．
