（应用数学专业论文）遗传模糊混合聚类算法的研究与应用.pdf

东北大学硕士学位论文摘要 遗传模糊混合聚类算法的研究与应用 摘要 聚类分析是多元统计分析的一种 也是非监督模式识别的一个重要分支 它已经被 广泛地应用于模式识别 数据挖掘 决策分析和预测等许多领域 引入模糊理论的模糊 聚类分析为现实数据提供了模糊处理能力 更能客观地反映现实世界 从而成为聚类分 析研究的主流 本文对模糊聚类分析进行了研究 主要做了以下工作 1 对模糊c 均值 f u z z yc m e a n s f c m 与遗传算法相结合的混合聚类算法进行 了研究 用遗传算法求解 其关键的问题是染色体编码 个体适应度评价 遗传算子的 设计以及遗传参数的设置 本文给出了关于这些问题的一种新的设计方法 在文献 2 6 的基础上提出了一个改进的遗传模糊混合聚类算法 h g f a 并用m a t l a b 进行仿真 实验 结果表明 这种改进后的算法能够有效的提高收敛速度 改善聚类效果 在收敛 速度和对初值的敏感性方面h g f a 算法明显优于f c m 在聚类质量及收敛速度上优于原 有算法 2 对改进的遗传模糊混合聚类算法 h g f a 的应用进行了研究 本文将h g f a 算法分别应用在了超市会员聚类和灰度图像二值化中 用h g f a 算法对超市会员进行聚 类 能够得到与实际完全相符的聚类结果 用h g f a 算法对灰度图像进行二值化处理 不需要设定阈值 可以较好的分离出目标图像 另外这也说明了h g f a 算法在处理大数 据集时的有效性 关键词 聚类分析 模糊聚类分析 模糊c 均值聚类算法 遗传算法 应用 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho nh y b r i d c l u s t e r i n ga l g o r i t h m c o m b i n i n gf c m w i t hg aa n di t sa p p l i c a t i o n a b s t r a c t c l u s t e r i n ga n a l y s i si sak i n do fs t a t i s t i c a lm u l t i a n a l y s i s i sa l s oa ni m p o r t a n tb r a n c ho f t h eu n s u p e r v i s e dp a t t e r nr e c o g n i t i o nm e t h o d i ti sw i d e l yu s e di nm a n yf i e l d si n c l u d i n g p a t t e r nr e c o g n i t i o n d a t am i n i n g d e c i s i o n a n a l y z i n ga n dp r e d i c t i o n f u z z yc l u s t e r i n ga n a l y s i s w h i c hi n t r o d u c e st h et h e o r yo ff u z z ys e t sp r o v i d e st h ec a p a b i l i t yt h a tc a nb eu s e dt od e a lw i t h r e a lf u z z yd a t u s e t s c a nr e f l e c tr e a lw o r l dm o r eo b j e c t i v e l y s oi th a sb e e no n eo fm o s th e a t e d r e s e a r c ht o p i co f t h ec l u s t e r i n ga n a l y s i s t h i sp a p e ri se n g a g e di nf u z z yc l u s t e ra n a l y s i s h a sd o n et h ef o l l o ww o r k 1 t h eh y b r i dc l u s t e r i n ga l g o r i t h mi n c o r p o r a t i n gf c mi n t og e n e t i ca l g o r i t h mi s r e s e a r c h e d u s i n gg e n e t i ca l g o r i t h mt os o l v et h ep r o b l e m k e yi s s u e sb l ec h r o m o s o m ec o d i n 舀 p o p u l a t i o ni n i t i a l i z a t i o n f i t n e s sf u n c t i o n g e n e t i co p e m t o ma n dg e n e t i cp a r a m e t e r s t h i s p a p e rg i v e san e wd e s i g n i n gm e t h o da b o u tt h e m a n dp r e s e n t sa ni m p r o v e dh y b r i dc l u s t e r i n g a l g o r i t h m h g f a o nt h eb a s i so fr e f e r e n c e 2 6 w ea l s od i de x p e r i m e n t su s i n gm a t l a b w i t l lt h i sa l g o r i t h m r e s u l t so fe x p e r i m e n t si l l u s t r a t e st h a tt h ei m p r o v e dh y b r i dc l u s t e r i n g a l g o r i t h mn o to n l yc a ni m p r o v et h ec o n v e r g e n c es p c c d b u ta l s oc a ni m p r o v et h ec l u s t e r i n g r e s u l t so b v i o u s l y i ti ss u p e r i o rt of c mi nc o n v e r g e n c es p e e da n ds e n s i t i v i t yt oi n i t i a lv a l u e i t i sa l s ob e t t e rt h a ni n i t i a la l g o r i t h mi nc l u s t e rq u a l i t ya n dc o n v e r g e n c es p c e d 2 a p p l i c a t i o no f t h ei m p r o v e dh y b r i dc l u s t e r i n ga l g o r i t h mc h g f a i ss t u d i e d w ea p p l y h g f aa l g o r i t h mt oc l u s t e r i n go fs u p e r m a r k e tm e m b e r sa n dt u r n i n gt h eg r e yi n l a g ei n t o t w o v a l u e di m a g er e s p e c t i v e l y c l u s t e r i n gr e s u l t so fs u p e r m a r k e tm e m b e r sw i t hh g f ai s c o n s i s t e n tw i t hf a c t t u r n i n gt h eg r e yi m a g ei n t ot w o v a l u e di m a g ew i t hh g f ad o n tn e e dt o f i n dt h et h r e s h o l da n dc a nc l a s s i f yt a r g e ti m a g e t h i sa l s os h o w sv a l i d i t yo fh g f aa l g o r i t h m t 0d c a lw i t hl a r g ed a t a s e t s k e yw o r d s c l u s t e ra n a l y s i s f u z z yc l u s t e ra n a l y s i s g e n e t i ca l g o r i t h m f u z z yc m e a n s c l u s t e r i n ga l g o r i t h mf f c m a p p l i c a t i o n i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的 论文中取得的研究成果除加 以标注和致谢的地方外 不包含其他人己经发表或撰写过的研究成果 也不包括本人为 获得其他学位而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均己在论 文中作了明确的说明并表示谢意 学位论文作者签名 蓟终 日 期 2 舻7 扩 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留 使用学位论文的规定 即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘 允许论文被查阅和借 阅 本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索 交 流 学位论文作者签名 日 玛睽 z q q 2 l 另外 如作者和导师不同意网上交流 请在下方签名 否则视为同意 学位论文作者签名 导师签名 签字日期 多酲p 签字日期 东北大学硕士学位论文第一章绪论 1 1 论文研究背景 第一章绪论 物以类聚 人以群分 聚类是人类一项最基本的认识活动 它把一个没有 类别标记的样本集按某种准则划分成若干个子集 类 使相似的样本尽可能归为一 类 而不相似的样本尽量划分到不同的类中 人类要认识世界就必须区别不同的事 物并认识事物间的相似性 而每个概念的最初形成无不借助于事物的聚类分析 通过适当聚类 事物才能便于研究 事物的内部规律才可能为人类所了解掌握 聚 类分析是多元统计分析的一种 也是非监督模式识别的一个重要分支 因此 聚类 分析的研究不仅具有重要的理论意义 也具有重要的工程应用价值和人文价值 它 己经被广泛地应用于模式识别 数据挖掘 计算机视觉和模糊控制等许多领域 但是传统的聚类分析属于硬划分的范畴 它把每个待识别的对象严格的划分到 某类中 也就是说对于数据空问中的任何元素 或者属于某一类 或者不属于该类 两者必居且仅居其一 具有 非此即彼 的性质 因此这种类别划分的界限是分明 的 然而在现实世界中 许多实际问题并没有严格的属性 它们在性态和类属方面存 在着中介性 具有 亦此亦彼 的性质 因此随着模糊集理论的提出 人们开始用 模糊的方法来处理聚类问题 并称之为模糊聚类分析1 2 5 由于模糊聚类得到了样本 属于各个类别的不确定性程度 表达了样本类属的中介性 即建立起了样本对于类 别的不确定性描述 更能客观地反映现实世界 从而成为聚类分析研究的主流 1 2 模糊聚类分析的发展概况 模糊划分的概念最早是由r u s p i n i 在1 9 6 9 年提出1 6 利用这一概念 人们提出 了多种聚类方法 从二十世纪七十年代到八十年代 人们对模糊矩阵和传递闭包进 行了大量的研究 到九十年代 人们用图论的方法研究模糊聚类 比较典型的有 t a m u r a 提出相似性关系和模糊关系的方法 包括聚合法和分裂法 7 1 z k i m 提出基于 模糊等价关系的传递闭包法 8 z h e n g g uw u 提出模糊图论最大树方法1 9 1 以及其他 学者提出的基于数据集的凸分解 动态规划和难以辨识关系等方法 然而由于上述方法不太适用于大规模数据情况 难以满足实时性要求高的场合 因此其实际的应用不够广泛 故在该方面的研究也就逐步减少了 实际中受到普遍 欢迎的是基于且标函数的模糊聚类方法 该方法设计简单 解决问题的范围广 最 1 东北大学硕士学位论文 第一幸绪论 终还可以转化为优化问题而借助经典数学的非线性规划理论求解 并易于计算机实 现 因此 随着计算机的应用和发展 该类方法成为聚类研究的热点 基于目标函数的模糊聚类方法首先是由r u s p i n i 提出的1 6 1 0 1 但真正有效的方法 是由d u n n 给出的 1 1 1 2 1 9 7 4 年d u n n 将硬c 均值聚类算法推广到模糊情形 同年 b e z d e k 将d u n n 的方法一般化 建立了模糊c 均值 f u z z yc m e a n s f c m 聚类 理论1 1 3 1 4 1 9 8 0 年b e z d e k 证明了模糊c 均值聚类算法的收敛性并讨论了模糊c 均 值聚类算法与硬c 均值聚类算法的关系 1 5 l 从此 基于目标函数的模糊聚类方法蓬 勃发展起来 目前己形成了庞大的体系 人们从不同的角度对基于目标函数的模糊 聚类方法进行研究 归纳起来主要集中在以下四个方面1 1 6 l 模糊聚类新方法的研究 实现途径的研究 聚类有效性的研究和模糊聚类的应用研究 模糊聚类新方法的研究主要集中在 对模糊c 均值聚类算法的收敛性和停止准 则的研究 提高模糊c 均值聚类算法的收敛速度 修改目标函数 修改模糊划分空 间 给模糊聚类算法溶入先验知识 修改模糊c 均值聚类算法中的距离 噪声数据 的模糊聚类和混合型数据的聚类 模糊聚类算法的实现途径研究 基于目标函数的模糊聚类方法 实际上是一个 非线性规划问题 因此也必然存在对初值敏感 容易陷入局部极值点 求解过程缓 慢等局限 为此 人们在算法实现途径方面进行着不懈的努力 借助各种技术寻求 快速最优聚类的新方法 模糊聚类算法的聚类有效性研究 聚类有效性问题的研究是一旦数据集被分类 如何判断聚类数c 的合理性 为了求得最佳的分类数 人们主要从以下几个方面进 行研究 基于数据集的模糊划分的聚类有效性函数和基于数据集的几何划分的聚类 有效性函数等 有效性问题是聚类分析的瓶颈 该问题的解决将会对聚类分析的成 功应用产生十分深远的影响 模糊聚类算法应用方面的研究 该方法己经有效地应用在大规模数据分析 数 据挖掘 模式识别 图像处理 决策支持等领域 具有重要的理论与实际应用价值 随着模糊聚类理论的不断发展和完善 这几个方面的研究还将继续深入 必将 成为未来模糊聚类理论发展的主要研究方向 1 3 遗传模糊聚类算法 1 3 1 模糊聚类算法中引入遗传算法的意义 传统的基于目标函数法的f c m 算法通过采用梯度下降法对目标函数进行优化 一2 东北大学硕士擘住论文第一章绪论 寻找所研究问题的最优解 是一种局部搜索算法 因此存在着两个致命的弱点 一 是在处理大数据集时花费的时间相当多 二是对初值非常敏感 所以很容易陷入局 部极小值 由于存在这样的缺点 使f c m 算法在实际应用中受到很大的限制 针对 f c m 算法存在的缺点 人们也曾提出过很多改进措施 如s e l i m 和a s u l t a n 等人提出 的模拟退火 模糊聚类算法1 1 7 t 8 j 但由于模拟退火算法只有当温度下降地足够慢时才 能收敛到全局最优点 大量的运算时间限制了其适用性 人们也曾经用神经网络技 术来聚类 而神经网络虽然以其并行处理节省了时间 仍然没有解决对初值敏感的 问题 也就很难获得全局最优解 遗传算法是一种应用非常广泛的全局优化方法 它通过对群体进行遗传操作 优胜劣汰 经过若干代的进化寻得最优解 隐含并行性和全局搜索特性是它的两大 显著特点 而且具有较强的稳健性 可避免陷入局部最优 遗传算法的这些特点恰 好能够克服f c m 对初值敏感的缺点 所以人们开始将遗传算法与f c m 相结合来解决 聚类问题 1 3 2 遗传模糊聚类算法的研究现状 由于遗传算法与f c m 相结合 既可以发挥遗传算法的全局寻优能力 又可以兼 顾f c m 的局部寻优能力 从而较好地解决聚类问题 基于这种思想 有越来越多的 学者们致力于这方面的研究 使得遗传模糊聚类算法得到了一定的发展 1 9 9 2 年刘健庄等人提出了基于遗传算法的k 均值算法和模糊c 均值算法1 1 9 2 0 l 同时b e z d e k 也提出了用遗传算法指导聚类的算法 2 此后致力于这方面研究的学 者越来越多 1 9 9 3 年f a l k 提出了所谓的分组遗传算法 g r o u p i n gg e n e t i ca l g o r i t h m g g a 2 2 l 他致力于设计适当的染色体表达来获取问题的编码 并应用于各种分组 分割以及聚类问题 1 9 9 4 年a l s u l t a n 提出用t a b u 搜索算法求解k 均值聚类问题1 2 3 1 他通过对划分矩阵u 的随机搜索以获得全局最优解 随着研究的深入 人们发现若直接运用基本遗传算法来解决聚类问题 算法的 性能较差 要构造有效的基于遗传算法的聚类算法 必须尽可能地应用特定问题领 域的知识 如 1 9 9 9 年k r i s h m a 以k 均值算子代替交叉算子 设计了一种混合遗传算 法 2 4 1 并根据g u n t e r 弓l 入的有限状态齐次马尔可夫链方法证明了该算法以概率1 收敛 到全局最优点 2 0 0 0 年m a u l i k 采取对聚类中心的浮点数编码方式1 2 5 1 设计了浮点数 交叉 变异操作 从而提高了遗传算法的搜索效率 2 0 0 4 年 董云影等设计了基于 遗传算法的模糊聚类算法1 2 6 1 并提出了改进的算法f 2 7 l 取得了比较好的效果 但这两 种聚类算法并不完善 有待迸一步的改进与提高 3 东北大学硕士学位论文 第一幸绪论 1 4 本文主要工作与内容安排 本文首先对遗传算法与f c m 算法相结合的混合聚类算法进行了研究 为了将遗 传算法与f c m 算法更好地结合起来 充分发挥遗传算法的全局搜索能力和f c m 算法 强大的局部搜索能力 对原有算法进行了改进 提出了改进的遗传模糊混合聚类算 法 h g f a h g f a 算法通过对问题解空间交替进行全局和局部搜索 较好的解决 了遗传算法在达到全局最优解前收敛慢和f c m 算法容易陷入局部极小值的问题 为 了证明该算法的有效性 用m a t l a b 进行了仿真实验 实验结果表明 这种改进后 的算法能够有效的提高收敛速度 改善聚类效果 其次 对改进的遗传模糊混合聚类算法 h g f a 的应用进行了研究 h g f a 算 法具有较好的通用性和有效性 在本文给出的两个具体的应用实例中都得到了良好 的应用 本文内容安排如下 第一章介绍了课题的背景 模糊聚类的发展概况 遗传模糊聚类算法的研究意 义及研究现状 第二章系统的介绍了聚类分析 模糊聚类分析的有关知识 并详细地讨论了 f c m 算法 还对与本文研究相关的遗传算法的原理 特点以及基本遗传算法进行了 介绍 第三章对遗传算法与f c m 算法相结合的聚类算法进行了改进 提出了改进的 遗传模糊混合聚类算法 h g f a 并对该算法用m a t l a b 进行了仿真实验 结果 证明了该算法的优越性 这是本文的重点 第四章对改进的遗传模糊混合聚类算法 h g f a 的应用进行了研究 给出了 两个具体的应用实例 第五章总结本文的主要工作并做出对未来研究的展望 4 东北大学硕士学位论文 第二章预备知识 2 1 聚类分析概述 第二章预备知识 1 帚一早 耿亩刘以 2 1 1 聚类的概念及描述 聚类是一个古老的问题 它伴随着人类社会的产生和发展而不断深化 人类要 认识世界就必须区别不同的事物并认识事物间的相似性 1 0 j 所谓聚类 就是把给定 对象集合分组成为由类似对象组成的多个类的过程 使类内相似性尽可能大 类间 相似性尽可能小 在聚类过程中没有任何关于分类的先验知识 没有教师指导 仅靠事物间的相 似性作为类属划分的准则 因此属于无监督分类的范畴 聚类分析则是指用数学的 方法研究和处理给定对象的分类 聚类分析是一种数据划分或分组处理的重要手段 和方法 其操作的目的在于将特征空间中一组没有类别标记的矢量按某种相似性准 则划分到若干个子集中 使得每个子集代表整个样本集的某个或者某些特征和性质 聚类分析已经被广泛地应用于模式识别 数据挖掘 计算机视觉和模糊控制等许多 领域 是当前研究的热点问题之一 2 8 2 9 j 2 1 2 常用的聚类算法 目前常用的聚类算法有如下八种 1 不完全或启发式聚类分析方法 主要是几何方法 描述和投影方法 例如主 要成份分析是通过降维来分析高维数据 目的是要得到一个二维或三维的图形描述 然后可以通过基于数据可视化的启发式方法来划分聚类 2 确切的硬聚类分析方法 即每个数据确切地分配给一个类 形成一个常规的 聚类划分 3 交错的硬聚类分析方法 即每个数据至少被分配到一个类中 它也可以同时 被分配给几个类 4 概率聚类分析方法 对每一个数据来说 决定聚类的概率分布指明了这个数 据被分配到一个类的概率 如果这种概率被解释为隶属度 那么这种方法也可以称 为模糊聚类算法 5 可能性聚类分析方法 这样的方法是纯模糊聚类算法 隶属度或可能性表示 一个数据属于各个类的程度 可能性聚类分析放松了每个数据对所有类的隶属度总 5 一 东北大学硕士学位论文 第二章预备知识 和必为1 的概率约束 6 层次的聚类分析方法 它是对给定的数据对象集合进行层次的分解 根据层 次的分解如何形成 层次的方法可以分为凝聚式方法和分裂式方法 凝聚式方法也 称为自底向上的方法 一开始把每个数据对象单独的作为一个类 然后相继的合并 相近的对象或类 直到所有的类被合并为一个类 层次的最上层 或者达到一个 终止条件 相反地操作即为分裂式方法 7 基于目标函数的聚类分析方法 这种方法的基础就是目标或评价函数 它给 每个可能的聚类划分分配一个待优化的度量值或误差值 最好的聚类一定要获得最 好的评价 从这个意义上来讲 把目标函数用于聚类分析 从而使聚类分析转化成 了一个优化问题 8 聚类判别方法 这种方法采用交互式的优化算法 但运用启发式方程来建立 划分并评估聚类参数 由于已用的聚类产生规则是实探性地被选择的 所以这种方 法在聚类模型变得难于最小化或目标函数缺乏可辨性时显得非常有效 2 2 模糊聚类分析 2 2 1 模糊聚类分析介绍 聚类分析技术大体上分为硬聚类方法 软聚类方法 传统的聚类分析属于硬聚 类的范畴 它把每个待识别的对象严格的划分到某类中 也就是说对于数据空间中 的任何元素 或者属于某一类 或者不属于该类 两者必居且仅居其一 具有 非此 即彼 的性质 因此这种类别划分的界限是分明的 然而在现实世界中 许多实际问 题并没有严格的属性 它们在性态和类属方面存在着中介性 具有 亦此亦彼 的性 质 那么用这种传统的方法将无法解释这类问题 如在区分 年轻人 和 老年人 时 就不存在那么明显的年龄界限 为了解决类似这样的问题 需要引进模糊的思想 基于模糊集理论 r u s p i n i 于1 9 6 9 年率先提出了模糊划分的概念 以此为起点和基 础 人们开始用模糊集的方法来处理类似于上述的聚类问题 并称之为模糊聚类 下面我们来介绍一下有关模糊集的概念 对于一个普通集合m 空间中任一元素x 要么x 膨 要么x 硭肘 二者必居 其一 这一特征可用一个函数表示为 品茹 m 即为集合m 的特征函数 将特征函数推广到模糊集 从在普通集合中只 东北大学硕士学位论文第二章预备知识 取0 和1 这两个值 推广到模糊集中为f 0 1 1 区间 定义 模糊集 设x 为论域 x 上的一个模糊集合衍由x 上的一个映射来 表示如下 工一 o 1 对f x g x 麝0 称为x 对于肠的隶属度 坳称为庸的 隶属函数 由定义可知 模糊集合詹是一个抽象的东西 而函数p 则是具体的 所以 我们只能通过坳来认识和掌握露 坳 力在实轴的闭区间 叫上取值 的值 反映了x 中的元素z 对于厨的隶属程度 0 的值越是靠近1 表示隶属度程越 高 g 越是靠近0 则表示隶属程度越低 如果定义 o 一l 一石 m 和 o 0 一x 正肘 麝便演化成一个普通集合m 由此可见 模糊集合是普通集合 概念的推广 在模糊聚类中 每个样本不再仅属于某一类 而是以一定的隶属度分别属于每 一类 由于模糊聚类得到了样本属于各个类别的不确定性程度 表达了样本类属的 中介性 即建立起了样本对于类别的不确定性的描述 能更客观地反映现实世界 从而成为聚类分析研究的主流 j 人们提出过很多种模糊聚类方法 但是实际中受到普遍欢迎的是基于目标函数 的模糊聚类方法 该方法设计简单 解决问题的范围广 最终还可以转化为优化问 题而借助经典数学的非线性规划理论求解 并易于计算机实现 因此 随着计算机 的应用和发展 该类方法成为聚类研究的热点 最经典的基于目标函数的模糊聚类 方法是模糊c 均值聚类方法 目前该算法应用非常广泛 2 2 2 模糊c 均值算法 f u z z yc m e a n s f c m 2 2 2 1f c m 算法描述 f c m 算法是基于对目标函数优化基础上的一种模糊聚类方法 聚类结果是每一 个数据点对聚类中心的隶属度 该隶属度用一个数值来表示 作为一种无监督的模 糊聚类方法 f c m 算法在实现过程中不需要人为干扰 数据样本集合x 一 工 c r 的模糊c 一划分可用模糊矩阵u t 帆l 表 示 矩阵 的元素 表示第k 驻 1 2 n 个样本点属于第f f 1 2 c 类的隶属 度 满足如下条件 v i k o 1 v k 善 m 1 荟 o f c m 算法的目标函数为每个样本点到相应的聚类中心的加权距离平方和 7 东北大学硕士学位论文第二章预备知识 l 矿 善薹 4 叱2 瓴 u 2 1 其中 丸2 h 屹 一 毛一u 厂彳 五一u a g s s 阶的对称正定矩阵 以是一种距离 范数 表示样本点黾与第f 个聚类中心u 之间的距离 用 表示单位矩阵 当a 一 时 如表示欧氏距离 e u c l i d 当a 7 对 d n 表示马氏距离 m a h a l a n o b i s 一般 情况下 采用欧氏距离 在目标函数表达式中 肌 阻 m 1 是模糊加权指数 又称平滑参数 其控制模 糊聚类的模糊程度 n l 越大 模糊程度越大 m 越小 模糊程度越小 一般情况下 取m t 2 f c m 算法是一个使目标函数最小化的迭代收敛过程 2 2 2 2f c m 算法的分析求解过程 f c m 算法在极值的约束条件 一1 下 通过逐步迭代使目标函数厶 u y 达到极小值m i n l 厂 矿 m n 仉 吖 叫薹砉 h 引2 l 荟叫著 r 丸 2 可以用拉格朗日方法求解 其求解过程如下 令拉格朗日函数为 其中a 是一参数 由婴 o 得到 a a 由罢 o 得到 u a f 砉 艉 叱 2 a 砉 一 筹 壹 1 o 以身4 善 九九州一 8 东北大学硕士学位论文第二章预备知识 岛n 硝斋厂 罗 一1 白 扣艄击捌而 行黼击 呤厂 齑 l k t 1 渊忑 下面再求解使得目标函数 y 达到极小值m i n u y 时的聚类中心 与 上面的方法相同 由监型 堕 0 得到 9 东北大学硕士学位论文 第 章预备知识 t a c u v 扣 迎掣 荟 圳瓴一峙 一2 爿 i 一2 爿 叫 所以可以得到模糊聚类的聚类中心 h 鲨 荟以广 从上面的表达式可以看出 由隶属度就可以求出聚类中心 2 2 2 3f c m 算法的实现步骤 f c m 算法步骤如下 1 初始化 取模糊加权指数m 一2 聚类的类别数c 2 s c n 数据样本点的 个数 l 迭代停止闽值s 初始的聚类中心值矿 以及迭代次数 0 2 计算由隶属度所组成的划分矩阵 0 对于任意的f k 如果以o o 则 似一 砉阱d 4 舞i 口wj 如果如 0 则 n 铆 1 且对碲一f 使甜m 0 3 更新聚类中心值 塾坠 荟 厂 4 终止判断 若妙o o y 似9 tf 则算法停止 否则转到步骤2 在上述算法中 首先初始化聚类中心点值 也可以先初始化由隶属度所组成的 1 0 瞻4 也 善 瓴 v 广 厂 醇 嶂 似 x角 v自 东北大学硕士学位论文 第二幸预备知识 划分矩阵u 再求聚类中心值 再更新划分矩阵u 最后判别条件为 妒 一u i t 由以上算法可以看出 f c m 算法的过程就是不断地修正聚类中心y 和由隶属度 所组成的划分矩阵u 的过程 因此是动态聚类过程 2 3 遗传算法简介 2 3 1 遗传算法的基本原理 遗传算法 3 0 4 2 1 g e n e t i c a l g o r i t h m 简称g a 是模拟生物在自然环境中的遗传 和进化过程而形成的一种自适应全局优化概率搜索算法 遗传算法中包含两个必须 的数据转换操作 即编码和解码 把一个问题的可行解从其解空间转换到遗传算法 所能处理的搜索空间的转换方法称为编码 相反过程就是解码 所以编码的实质就 是在问题的解空间与算法的搜索空间之间建立一个映射 算法在确定了实际问题的 参数集后 把搜索空间 欲求解问题的解空间 映射为遗传空间 即把每一个可能 的解编码为一个向量称为一个染色体 向量的每一个元素称为基因 一般情况下 染色体的长度撑是固定的 但对于一些问题疗也可以是变化的 根据不同的情况 这 里的等位基因可以是一组整数 也可以是某一范围内的实数值 或者是纯粹的一个 符号 最简单的等位基因是由0 和1 这两个整数所组成的 相应的染色体就可表示为 一个二进制符号串 这种编码所形成的排列形式x 是个体的基因型 与它对应的x 值是个体的表现型 所有个体组成群体 对于群体中的每个个体 按预定的目标函 数 或某种评价指标 对每个个体进行评价 根据其结果给出一个适应度的值 个 体越接近于目标函数的最优点 其适应度就越大 反之 其适应度就越小 与生物 一代一代的自然进化过程相类似 遗传算法的运算过程也是一个反复叠代的过程 第r 代群体记作p 0 经过一代遗传操作 选择 交叉 变异等 后 得到第t l 代 群体 它也是由多个体所组成的集合 记做p f 1 这个群体不断地进行遗传和进 化操作 并且每次都按照优胜劣汰的规则将适应度高的个体更多的遗传到下一代 最终在群体中将会得到一个优良的个体 它所对应的表现型z 将达到或接近问题的 最优解 在应用遗传算法求解问题时 主要步骤如图2 1 3 3 所示 遗传算法中包含了如下5 个基本要素 1 问题编码 2 初始群体的设定 3 适应值函数的设计 4 遗传操作设计 5 控制参数设定 主要是指群体大小和使 用遗传操作的概率等 这5 个要素构成了遗传算法的核心内容 东北大学硕士擘位论文 第二章预备知识 i 向量解码得参数 2 计算目标函数值 3 目标函数值向适 应度映射 4 适应度调整 i 选择 2 交叉 3 变异 或其他遗传算子 确定实际问题的参数 对参数集进行编码 初始化群体p t 评价群体 满足条件 一 二二 一结束 遗传操作 群体p t f 群体p t 1 图2 1 遗传算法的漉程图 f i g2 ip r o c e s sf i g u r eo f g e n e t i ca l g o r i t h m 2 3 2 遗传算法的特点 遗传算法与传统的优化算法相比有如下不同的特点 1 遗传算法处理的对象是编码后形成的个体 而不是参变量自身 2 遗传算法不是从一个点开始搜索 而是对多个个体进行群体搜索 3 遗传算法不需要导数或其它辅助信息 只需要适应度 用它来评价个体 引 导搜索过程朝着搜索空间更优解的方向移动 4 遗传算法是一种高效有方向随机搜索方法 5 遗传算法具有隐含并行性 它虽然在每一代只是对有限个个体进行操作 但 处理的信息量为种群规模的高次方 6 遗传算法在形式上简单明了 不仅便于与其它方法相结合 而且非常适合于 大规模并行计算机运算 1 2 东北大学硕士学位论文 第二幸预备知识 7 遗传算法具有很强的鲁棒性 即在存在噪声的情况下 用遗传算法对同一问 题的多次求解中所得到的结果是相似的 2 3 3 基本遗传算法 随着遗传算法的发展 为了解决不同的问题 致力于这方面的专家及学者已经 设计了许多不同的编码方法及遗传算子 由这些不同的的编码方法和遗传算子就构 成了各种不同的遗传算法 但这些遗传算法都是通过对生物遗传和进化过程中选择 交叉 变异机理的模仿 来完成对问题最优解的自适应搜索过程 因此g o l d b e r g 总 结了这些遗传算法的共同点 给出了一种统一的最基本的遗传算法 一基本遗传算 法 s i m p l eg e n e t i ca l g o r i t h m 简称s g a 1 3 4 基本遗传算法只使用选择算子 交叉 算子和变异算子这三种基本算子完成对群体的遗传操作 由于其操作过程简单易行 从而不但使其自身具有一定的应用价值 也给其它各种遗传算法提供了一个基本框 架 基本遗传算法的结构如下 1 编码方法 使用固定长度的二进制符号串对问题参数进行编码 每个个体都 是由 o 1 组成的符号串 2 初始化 初始群体中各个个体的基因值可用均匀分布的随机数来生成 3 个体适应度 基本遗传算法按与个体适应度成正比例的概率来决定当前群体 中每个个体遗传到下一代群体中的机会多少 这里要求所有个体的适应度必须为正 数或零 这样 根据不同种类的问题 必须预先确定好由目标函数到个体适应度之 间的转换规则 特别是要处理好当目标函数值是负数时的处理方法 4 遗传操作 选择运算使用比例选择算子 交叉运算使用单点交叉算子 变异 运算使用基本位变异算子或均匀变异算子 5 参数设置 基本遗传算法有4 个运行参数 分别为种群规模 p o p s i z e 最 大遗传进化代数 m a x g e n 交叉概率 和变异概率 己 这4 个参数的取值对遗传 算法的求解结果和求解效率都有一定的影响 但目前尚无合理的选择它们的理论依 据 所以要根据实际问题进行合理设置 这里只是给出一些经验值 p o p s i z e 一般 取为2 0 1 0 0 m a x g e n 一般取为1 0 0 5 0 0 一般取为0 4 0 9 9 变异概率已一般 取为0 0 0 0 1 0 1 1 3 东北大学硕士学位论文 第三章改进的遗传模糊混合聚类算法 第三章改进的遗传模糊混合聚类算法 模糊聚类分析在很多领域得到广泛应用 在众多的模糊聚类算法中 基于目标函数 的f c m 算法可以说是最受欢迎 应用最为广泛的一种算法 然而f c m 算法实质上是初始 聚类中心到聚类结果的映射 当初值确定后 聚类的结果就被唯一确定 所以算法对初 值非常敏感 易收敛到局部极小值 这在聚类数比较大的情况下尤其突出 由于存在这 样的缺点 使f c m 算法在实际应用中受到很大的限制 针对f c m 算法存在的缺点 人们 也曾提出过很多改进措施 但并没有取得很理想的效果 遗传算法是一种应用非常广泛的全局优化方法 隐含并行性和全局搜索特性是它的 两大显著特点 遗传算法的这些特点恰好能够克服f c m 对初值的敏感 但是遗传算法的 局部搜索能力不如f c m 所以人们开始把遗传算法与f c m 结合起来 这样既可以发挥遗 传算法的全局搜索能力 又可以兼顾f c m 的局部寻优能力 从而更好地解决聚类问题 基于这样的思想 本文对这种混合聚类算法进行了研究 用遗传算法求解 其关键的问题是染色体编码 个体适应度评价 遗传算子的设计 以及遗传参数的设置 本文给出了关于这些问题的一种设计方法 在文献 2 6 1 的基础上 提出了一个改进的遗传模糊混合聚类算法 本文把改进后的算法记为h g f a h y b r i d c l u s t e r i n ga l g o r i t h mc o m b i n i n gg a w i t hf c m 下面将给出h g f a 算法的具体设计方法 3 1 编码 初始化及适应度的设计 3 1 1 编码 e o d i n g 当把遗传算法应用于具体问题时 编码是设计遗传算法的一个关键步骤 编码方法 除了决定个体的染色体排列形式及个体从搜索空间的基因型变换到解空间的表现型时 的解码方法 编码方法也影响到交叉算子 变异算子等遗传算子的运算方法 所以编码 方法在很大程度上决定了如何进行群体的遗传进化操作以及遗传进化运算的效率 编码 方法大体上可以分为三类 二进制编码方法 实数编码方法 符号编码方法 常用的编 码方式有两种 二进制编码和实数编码 所谓实数编码方法 是指个体的每个基因值用某一范围内的一个浮点数来表示 个 体的编码长度等于其参变量的个数 因为这种编码方法使用的是参变量的真实值 所以 实数编码方法又叫做真值编码方法 它相对于二进制编码方法有如下优点d 5 s 6 1 1 适合在遗传算法中表示范围较大的数 5 东北欠学硕士学位论文第三章改进的遗传模糊混合聚类算法 2 适合精度要求较高的遗传算法 3 便于大空间的遗传搜索 4 改善了遗传算法的计算复杂性 提高了运算效率 5 便于遗传算法与经典的优化算法的混合使用 6 便于设计针对具体问题的遗传算子 7 便于处理复杂的参变量约束条件 由于实数编码方法的上述优点 所以本文采用了实数编码方法 h g f a 算法对聚类 中心 v hi q r s f 1 2 c 进行编码 由于每条染色体由e 个聚类中心组成 而每个聚类中心h 1 2 e 有s 个特征 即b b b 吆 因此每条染色体是c x s 维的实向量 例如 c h r q l m 2 m v 2 i 屹2 v 2 屹i 匕2 k 一 一 一 弋 3 1 2 初始化 i n i t i a l i z a t i o n l 遗传算法是群体性操作 算法开始前要随机地产生p o p s z e 种群规模 个个体 组成初始群体 该群体代表一些可能解的集合 遗传算法的任务是从这个群体出发 模 拟进化过程进行择优汰劣 最后得出优秀的群体和个体 满足优化的要求 由于h g f a 算法采用了对聚类中心进行实数编码方法 与之相应 本文用样本空间 x 的每个特征取值范围内均匀分布的随机数来产生初始种群 具体如下 初始化 b e g i n 确定样本空间x 的j 个特征的取值范围 并记第i 个特征的取值范围为 玩0 u 7 f o r j 1t o p o p s i z e d o f o rj lt 0cd o f o rf 1t ojd o 产生 u 1 范围内的随机数 e n d f o r f 将这样产生的 个随机数组成一个聚类中心 e n d f o r 1 1 1 1 6 东北大学硕士学位论文第三章改进的遗传模糊混合聚类算法 将这c 个聚类中心组成一个个体 e n d f o r 后 由这p o p s i z e 个个体组成群体p o p o e n d 这样就产生了初始种群p o p o 由于产生的随机数服从均匀分布 因此初始种群 p 印 o 遍历整个解空间 能够充分反映问题解的性态 3 7 l 3 1 3 适应度 f i m e s s 在遗传算法运行中 为了执行适者生存的原则 必须对个体进行适应性评价 适应 度函数 f i t n e s sf u n c t i o n 构成了个体的生存环境 遗传算法基本上不需要外部信息 只 需根据适应度函数来控制种群的更新 根据适应度函数对群体中的每个个体计算其适应 度 以此来衡量各个个体在优化计算中有可能达到或接近于最优解的优劣程度 为群体 进化的选择提供依据 使适应度较高的个体遗传到下一代的概率较大 而适应度较低的 个体遗传到下一代的概率相对小一些 甚至被淘汰 设计适应度函数的主要方法是把问题的目标函数转换成合适的适应度函数 这里将 用遗传算法进行模糊聚类 模糊聚类的目标函数为由式2 1 定义的厶 算法追求以的最 小化 每个个体所对应的目标函数厶越小 聚类效果就越好 个体的适应度也就越高 所以很容易想到可以将目标函数厶作如下的转换 1 厶作为适应度函数 但对某些 聚类问题 目标函数值以可能会很小 这样经上式转化的适应度就会过大 不便于处 理 所以为了避免这种情况发生 h g f a 算法中的适应度函数取为厂 1 1 l 3 2 遗传算子设计 3 2 1 选择 s e l e c t i o n 遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体 遗传到下一代群体中的一种遗传运算 选择操作是建立在对个体的适应度进行评价的基 础之上的 在基本遗传算法中 使用比例选择算子1 3 8 l 对群体进行选择操作 它也是最基本的选 择算子 其基本思想是 每个个体被选择的概率与个体的适应度大小成正比 但对于各 种不同的问题 比例选择算子并不是最适合的一种选择算子 因为它存在以下不足 在 开始阶段 如果一个规模不太大的种群内有少数适应值很高的个体 按比例的选择方法 这些个体会被大量繁殖 在种群中占有很大的比重 这样就会使种群的多样性迅速降低 1 7 东北大学硕士学位论文 第三章改进的遗传模糊混合聚类算法 导致过早收敛 从而可能丢失一些有意义的搜索点或最优点 而陷入局部最优 在结束 阶段 即使种群保持了多样性 但若所有或大多数个体都有很高的适应度 从而使种群 平均适应度和最大适应度相差无几 那么平均适应度附近的个体和具有最高适应度的个 体被选中的机会几乎相同 这样就使选择操作成了一个近似随机的步骤 适应度的作用 就会消失 从而搜索性能得不到明显改进 所以在进行选择操作的时候 h g f a 算法采取随机联赛选择d 3 l 和最优保存策略 3 s l 相结合的方法 随机联赛选择的基本思想是 从当前群体中随机选择一定数量的个体 将其中适应 度最大的个体保存到下一代 被选择的个体返回到父代群体中 继续参加下一次的选择 反复执行该过程 直到被选择出的个体数量达到预定的群体规模 联赛规模用口表示 也称q 一联赛选择 q t o u r n a m e n ts e l e c t i o n 联赛选择与个体的适应度大小有间接关系 注重适应度大小的比较 在联赛选择中 选择力度的大小取决于q 的大小 q 值越大 每次选出的优胜者的 适应度就越高 反之 q 值越小 优胜者的适应度或高或低 随机性较强 为了尽量保 证群体的多样性 h g f a 算法中取g 2 但是如果仅使用这种方法 选择出的个体随机 性很强 适应度较高甚至最高的个体都可能选择不上 另外随着群体的进化过程虽然会 产生出越来越多的优