（概率论与数理统计专业论文）模糊c均值算法的研究.pdf

摘要 聚类分析是数据预处理的一种重要t 具作为一种无监督分类方法。它已经被广泛地应用于模 式识别、数据挖掘、计算机视觉和模糊控制等许多领域模糊聚类由于能够描述样本类属的中介 性，能够客观地反映现实世界，己逐渐成为聚类分析的主流方法之一在众多的模糊聚类算法中，模 糊c 均值算法( f c m ) 可以说是应用最为广泛、最为灵敏的一种算法模糊c 均值算法是模糊聚类 分析中一种基本的划分方法，通常该方法采用误差平方和准则函数作为聚类有效准则模糊c 均值 算法表现出很多优点：算法简单、解决问题的范围广、快速而且能有效地处理大型数据库和高维 度数据，还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于计算机实现因此， 随着计算机的应用和发展，基于目标函数的模糊聚类算法成为新的研究热点 本文通过对f c m 聚类算法的运行机理进行系统的分析，在模糊c 均值算法中目标函数是基于 欧氏距离的基础上，针对这个问题，从以下方面对f c m 聚类算法进行了改进主要：j ：作包括： 第一，首先，本文概括介绍了聚类分析和模糊聚类分析的基本原理聚类分析就是无监督模式 识别中的一个重要分支聚类分析的基本思想是根据物以类聚的原理，对样本进行分类其次，介 绍了聚类分析的数据类型和已有的模糊聚类有效性函数以及模糊c 均值算法并指出了模糊c 均值 算法存在的问题 第二，将传统的的模糊c 均值算法中目标函数是基于欧氏距离( 即l 2 ) 改为用一种新的距离来 刻画目标函数，在此基础上，通过实验说明了基于新距离的目标函数的模糊c 均值算法的可行性与 有效性 关键词：聚类分析，模糊聚类分析，模糊c - 均值，目标函数 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 sa ni m p o r t a n tt o o lf o rd a t ap r e p r o c e s s i n g a san o n s u p e r v i s e dc l a s s i f i c a t i o n ，i t w a sw i d e l yu s e di np 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 ，c o m p u t e rv i s i o n ，f u z z yc o n t r o la n dm a n yo t h e rf i e l d s f u z z yc l u s t e r i n gc a nb ed e s c r i b e da sa ni n t e r m e d i a r yo ft h es a m p l ec l a s sw h i c hc a no b j e c t i v e l yr e f l e c tt h e r e a lw o r l d f u z z yc l u s t e ra n a l y s i sg r a d u a l l yb e c a m eo n eo ft h ew a y st h em a i n s t r e a mo fc l u s t e ra n a l y s i s f u z z yc - m e a n sa l g o r i t h mi st h em o s tw i d e s p r e a da n ds e n s i t i v ei nm a n yf u z z yc l u s t e r i n ga l g o r i t h m s f u z z yc - m e a n sa l g o r i t h mw h i c hi sab a s i co f t h ep a r t i t i o nm e t h o d s q u a r e de r r o rc r i t e r i o nf u n c t i o no f t e n u s e da sc l u s t e r i n ge f f e c t i v ec r i t e r i o n f u z z yc - m e a n sa l g o r i t h mi sd e m o n s t r a t e dm a n ya d v a n t a g e s ：s i m p l e ， aw i d er a n g eo fp r o b l e m s o l v i n g ，f a s t ，c a nd e a le f f e c t i v e l yw i t hl a r g ed a t as e t sa n dh i g h d i m e n s i o n a ld a t a i tc a na l s ob ec o n v e r t e dt ot h eo p t i m i z a t i o np r o b l e mw h i c hc a nu s en o n l i n e a rp r o g r a m m i n go fc l a s s i c a l m a t h e m a t i c a lt h e o r yt os o l v e a sf a ra st h ec o m p u t e ri sc o n c e r n e d 。i ti se a s yt oi m p l e m e n t t h u s ，w i t h t h ea p p l i c a t i o na n dd e v e l o p m e n to ft h ec o m p u t e r , t h eo b j e c t i v ef u n c t i o nb a s e df u z z yc l u s t e r i n ga l g o r i t h m i n t oan e wr e s e a r c hf o c u s n e o b j e c t i v ef u n c t i o no f t h ef u z z yc - m e a n sa l g o r i t h mi sb a s e do nt h ee u c l i d e a nd i s t a n c e a c c o r d i n g t ot h i sp r o b l e m ，t h ef o l l o w i n ga s p e c t so ft h ef c m c l u s t e r i n ga l g o r i t h mt or e c o n s t r u c ti nt h i sp a p e r m a i n t a s k si n c l u d e ： f i r s t l y , o nt h eo n eh a n d ，t h i sp a p e ro v e r v i e w e dt h eb a s i cp r i n c i p l eo ft h ec l u s t e r i n ga n a l y s i sa n d f u z z yc l u s t e r i n ga n a l y s i s c l u s t e ra n a l y s i si sa ni m p o r t a n tb r a n c ho fp a a e mr e c o g n i t i o n t h eb a s i ci d e ao f c l u s t e r i n ga n a l y s i si sb a s e do nt h ep r i n c i p l eo ff e a t h e rf l o c kt o g e t h e r , t oc l a s s i f yt h es a m p l e o nt h eo t h e r h a n d ，i n t r o d u c e dt h ed a t at y p e so fc l u s t e ra n a l y s i sa n dt h ee x i s t i n go ff u z z yc l u s t e r i n gv a l i d i t yf u n c t i o n ， f u z z yc - m e a n sa l g o r i t h ma n dp o i n t e do u tf u z z ycm e a n sa l g o r i t h mt h a th a se x i s t e dp r o b l e m s s e c o n d l y , i nt h i sp a p e r , t h eo b j e c t i v ef u n c t i o no ff u z z yc - m e a n sa l g o r i t h mi sb a s e do nt h ee u c f i d e a n d i s t a n c e ，i nt h i sa s p e c t ss u g g e s ti m p r o v e m e n t s t h eo r i g i n a le u c l i d e a nd i s t a n c e ( t h a ti sl 2 ) c h a n g e dw i t h an e wd i s t a n c et oc h a r a c t e r i z et h eo b j e c t i v ef u n c t i o n n ee x p e r i m e n t ss h o wt h a to u ra p p r o a c hi sf e a s i b l e a n de 饰c i e n t k e yw o r d s ：c l u s t e r i n ga 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 ，f u z z yc - m e a n s ，o b j e c t i v ef u n c t i o n 独创性! 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 研究生签名： 友知楫 时间：动年r 月如日 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交 论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位 论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名：袭毛_ 棚 导师签名：囊也乏矽 时间：砂勿年上月扣日 时间： “r ，年j _ 月3 1 ) 日 第一章引言 随着计算机技术的迅猛发展以及网络技术的普及，人们有更多机会通过网络与外界进行信息 交流然而，随着数据大量的涌入，增加了我们获取有用信息的难度如何从大量的类型各异数据中 获取有价值的信息，采用传统的数据库技术已显得无能为力数据的迅速增加与数据的分析处理 方法滞后的矛盾越来越大，人们希望能够在对已有的大量数据分析的基础上进行科学研究、商业 决策或企业管理，数据挖掘正是在这一背景下诞生的，数据挖掘( d a t am i n i n g ) ，又称为数据库中的 知识发现( 简称k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) ，是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含的、未知的，有满在应用价值的信息或模式的过程它是一门新兴的交 义学科，汇集了来自数据库技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据 可视化、信息检索、图像与信号处理和空间数据分析等各领域的研究成果聚类是数据挖掘中的 一种重要技术，是分析数据并从中发现有用信息的一种有效手段基于“物以类聚”的朴素思想， 它将数据对象分组成为若干个类或簇，并且使得组与组之间的相似度尽可能的小，而组内数据之间 具有较高的相似度将一群( s e o 物理的或抽象的对象，根据它们之间的相似程度，分为若干组，其 中相似的对象构成一组，这一过程就称为聚类过程( c l u s t e r i n g ) ，一个聚类( c l u s t e r i n g ，又称为簇) 就 是由彼此相似的一组对象所构成的集合，不同聚类中对象通常是不相似的通过聚类，人们能够识 别密集和稀疏的区域，发现全局的分布模式以及数据属性之间有趣的相互关系聚类分析在客户分 类、基因识别、w w w 文本分类、空间数据处理、卫星照片分析、医疗图象自动检测等领域有 着广泛的应用，而其本身的研究也是一个蓬勃发展的领域，数据挖掘、统计学、机器学习、空间数 据库技术、生物学和市场学的发展推动着聚类分析研究的进展，使它己成为数据挖掘研究中的一 个热点与其他数据挖掘方法不同，在进行聚类分析前用户一般并不知道数据集的特征因此，从 某种角度看，聚类分析是按照一定的要求和规律对事物进行区分和分类的过程，在这一过程中没有 任何关于类分的先验知识，没有教师指导，仅靠事物间的相似性作为类属划分的准则，因此是一种 无监督的学习过程，是基于观察的学习而不是基于实例的学习 “人以群分，物以类聚”，聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深 化，人类要认识世界必须区别不同的事物并认识事物间的相似性由聚类生成的类是一组数据对 象的集合，使得在同一个类中的对象之间具有较高的相似度【4 2 】，而不同类中的对象差别很人聚 类分析的研究不仅具有重要的理论意义，也具有重要的工程应用价值和人文价值聚类分析是数据 预处理的一种重要工具，是分析数据并从中发现有用信息的一种有效手段它在许多领域中均受 到相当的重视作为一种无监督分类方法，它已经被广泛地应用于模式识别、数据挖掘、计算机视 觉和模糊控制等许多领域 聚类分析是多元统计分析的一种，也是非监督模式识别的一个重要分支它把一个没有类别标 记的样本集按某种准则划分成若干个子集( 类) ，使相似的样本尽可能归为一类，而不相似的样本 尽量划分到不同的类中传统的聚类分析【5 】是一种硬划分，它把每个待处理的数据对象严格地归 属于某个类，具有非此即彼的性质在这类方法中，隶属度不是l 就是0 ，因此这种类别划分的界限 是分明的然而在现实世界中的许多实际问题并没有严格的属性，它们在性态和类属方面存在着 中介性，往往伴有模糊性。具有“亦此亦彼”的性质，例如：环境污染分类，春天连阴雨预报，临床症 状资料分类，岩石分类等等对这些伴有模糊性的聚类问题，传统的聚类方法在处理这种数据时往 第+ 争，j i； 往捉襟见肘，为此， j 模糊数学语言来表达更为自然，即通过模糊聚类得到的样本属于各个类别的 不确定性程度，也就是建立起了样本对于类别的不确定性的描述，这样就更能准确地反映现实世 界因此，人们就提出了要对待处理的对象进行软划分，z e d e h 提出的模糊集理论为软划分【3 l 】提 供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析目前，它己 发展成为聚类分析中的一个重要分支，并在众多领域得到了成功的应用而在实际中应用最广泛 的则是基于目标函数的模糊扣均值( f c m ) 聚类算法f c m 算法是通过迭代的爬山算法来寻找所 研究问题的最优解的，由于它是一种局部搜索算法，因此存在着对初始化非常敏感，很容易陷入局 部极小值的致命弱点同时，当我们使用这一聚类算法时，必须事先确定数据集的聚类数，然而聚 类数c _ 般是很难预先知道的 模糊聚类是将模糊集的概念应用到传统聚类分析中，让数据集的对象在分类中的隶属媚隶属 函数来确定，也就是说，对象在各类中的隶属度为连续区间【0 ，l 】之间的某个值，以不同程度隶属于 多个类，而非确定性聚类中的0 或l 的二值逻辑模糊聚类的优点在于能适应那些分离性不是很好 的数据，这允许了数据性质的模糊性，为数据结构的描述提供了详细的信息由于模糊聚类得到了 样本属于各个类别的不确定性程度，表达了样本类属的模糊性，即建立起样本对于类别的不确定性 的描述，更能客观地反映现实世界，从而成为聚类分析研究i s 】的主流之一 基于目标函数的模糊聚类方法首先由r u s p i n i 提出，但真正有效的f c m 算法却是由d u n n 给 出的1 9 7 3 年，d u n n 对b a l l 和h a l l 的硬c 均值( h c m ) 聚类算法加以推广，提出了模糊c 均值 ( f c m ) 聚类算法b e z d e k 将d u n n 的工作进一步推广到一个模糊目标函数聚类的无限簇，并证明了 该算法的收敛性 1 8 - - 2 1 】。从此，该类模糊聚类就蓬勃发展起来了，目前f c m 算法在各个学科领域 中得到了广泛和有效的应用，例如金融、经济、生物科技【2 7 】、地质天文、教育心理、商业、管 理、图像分割、医疗诊断、模式识别【1 0 】、自动控制等 在模糊聚类分析的众多算法中，模糊c 均值算法( f c m ) 可以说是应用最为广泛、最为灵敏的 一种算法它不仅被模糊工程的研究者所接受，而且也被推广到其它一些科学的分支，如医学诊断， 计算机可视化、通讯及过程感测f c m 算法是通过迭代的爬山算法来寻找所研究问题的最优解 的，由于它是一种局部搜索算法，因此存在着对初始化非常敏感和容易陷入局部极小值的致命弱 点为了解决这一问题，许多学者进行了大量的研究：例如引入遗传算法【2 3 】、模拟退火算法等优 化技术来克服陷入局部极值【1 6 l 的问题；通过对不同的初值多次执行f c m 算法然后从中选出最好 的结果，来克服初值敏感性的问题等同时，当我们使用这一聚类算法时，必须事先确定数据集的 聚类数，然而聚类数c 一般是很难预先知道的因此b e z d e k 提出了“聚类有效性问题”，即确定数 据集的聚类数问题，目前人们针对f c m 算法构造了许多的有效性函数【卜4 】：b e z d e k 提出的准贝q 函数v p c 和v p e ，d a v e 的p c ，f u k u y a m a 和s u g e n o 的v f c ，x i e 和b e n i 的坛b ，k w o n 的坛， g a t h 和g e v a 的v f x v 等等 尽管如此，f c m 算法的进一步推广，却受到了算法速度的限制在大数据集的情况下，f c m 算 法需要消耗大量的c p u 时间c a n n o n 等人在1 9 8 6 年提出了一个近似的模糊c 均值( a f c m ) 聚类 算法，在保持聚类精度相同的情况下，a f c m 算法所用的c p u 时间只为f c m 算法的六分之一，速 度明显加快虽然a f c m 算法的运算速度取得了明显的提高，但对大的数据量，例如9 个光谱的 2 5 6x2 5 6 大小的图像，用a f c m 算法在i b m 3 0 8 1 机上进行聚类仍需用几个小时的时间因此，进 一步提高f c m 算法的速度是很有必要的 2 筇辛，j 1 1 模糊聚类理论研究现状及分析 伴随着模糊集理论的形成、发展和深化，r u s p i n i 率先提出了模糊划分的概念以此为起点和 基础，模糊聚类理论和方法迅速蓬勃发展起来并成为聚类分析的主流方法之一针对不同的应用， 涌现出了许多模糊聚类算法，形成了庞大的理论体系比较典型的有基于相似性关系和模糊关系的 方法、基于模糊等价关系的传递闭包方法、基丁模糊图论的最大支撑树方法，以及基于数据集的 凸分解、动态规划和难以辨识关系等方法然而，上述方法均不能适用于人数据量的情况，难以满 足实时性要求较高的场合，因此实际应用并不广泛，现在该方面的研究正在逐步减少在众多的算 法中，基于目标函数的模糊c 均值( f c m ) 类型的算法最为引人注目，因为f c m 算法不仅有深厚的 数学基础，也就是说，把聚类归结成一个带约束的非线性规划问题，通过优化求解获得数据集的模 糊划分和聚类，该方法设计简单，解决问题的范围广，还可以转化为优化问题而借助经典数学的1 f 线性规划理论求解，并易于在计算机上实现，而且在许多领域中已经获得了成功的应用，是目前最 实用也是最受欢迎的算法之一因此，随着计算机的应用和发展，基于目标函数的模糊聚类算法 成为新的研究热点。正是基于此，f c m 类型的算法在学术界引起了广泛的研究兴趣d u b e s 和j a i n 关于聚类分析的综述包括了从7 7 份杂志和4 0 本书中摘取出来的2 5 0 条引文，如此巨大的文献量 说明了聚类分析的重要性和交叉学科性，也足以说明它的发展及应用前景的广阔性同时，国际 和国内的学者都对聚类分析的研究非常重视，i e e e 的汇刊中模式分析与机器智能( p a m i ) 、 系统、人和控制( s m c ) 、模糊系统( f s ) 、神经网络( m 哪、 信号处理( s p ) 等杂 志中几乎每期都有讨论聚类分析问题的文章从1 9 9 2 年开始的由i e e e 和神经网络理事会共同主 办的f u z z - i e e e 会议，每两年召开一次，每次至少有3 到4 个专题讨论聚类和模糊聚类分析的研 究进展和发展现状另外，我国作为模糊数学研究大国，不仅在基础理论研究上取得了丰硕的成果， 而且在模糊聚类等的应用研究上亦令世人瞩目，比如基于模糊聚类的天气预报、矿藏识别和医学 诊断等等为了积极引导模糊聚类分析的理论和应用的研究热潮，国家自然科学基金委员会还专 门对“模糊聚类的新方法研究”和“无监督新闻视频语义分割和自动标注算法研究”立了项，重 点资助模糊聚类的研究模糊聚类分析研究的理论意义和实用价值是不言而喻的 不过，f c m 类型的算法毕竟才经历了2 0 多年的发展，尽管迄今为止对其研究从未间断过，也 取得了颇为丰硕的成果，但算法仍存在诸多不完善的地方，甚至还有严重的不足之处因此，对 f c m 类型聚类算法的进一步优化研究就显得尤为迫切和必要这不仅有利丁算法理论的完善，更 有助于算法的推广和应用 在近几年中，模糊聚类分析【2 4 l 的发展方向主要有两个方面：改进现有的聚类算法【6 - 7 1 和发 明新的聚类算法 1 1 - - 1 5 3 2 - - 4 1 1 现在已经有一些改进的算法用来处理大型数据库 2 9 - - 3 0 】和高维度 数据例如小波变换使用多分辨率算法，网格从粗糙到密集从而提高聚类的质量对于数据量大、 维度高并且包含许多噪声的集合，要找到一个全能的聚类算法是非常困难的某些算法只能解决 其中的一到两个问题，同时能解决三个问题的算法还没有现在最大的困难是高维度数据的处理 模糊c 均值属于聚类分析中一种基本的划分方法，常采用误差平方和准则函数作为聚类准则 主要优点是算法简单、快速而且能有效地处理大数据集然而这种算法依赖丁二初始值的选择以及 数据的输入顺序基于模糊c 均值算法所采用的误差平方和准则函数这个思想【9 l ，提出一种改进的 模糊c 均值算法并与现有的算法进行比较 3 1 2 本文工作要点及结构安排 本文针对现实生活中存在的数据的情况，提出了基于新距离的目标函数的模糊c 均值算法通 过实验说明，这种方法是有效可行的，可视为模糊c 均值算法的一种改进，且为其提供了一定的依 据具体安排如下： 本文第二章主要介绍了聚类分析、聚类分析的数据类型和模糊聚类分析的基本理论为第三 章、第四章做准备本文第三章主要介绍了硬均值算法和模糊c 均值算法，以及模糊c 均值算法存 在的问题本文第四章运用原有的模糊c 均值算法对现实中的数据进行聚类本文第五章首先对现 有的模糊c 均值算法进行改造，然后用改造后的算法来对第四章的数据进行聚类，最后对两种聚类 算法进行比较，从而证明了改造后的算法的可行性和有效性并展望了模糊c 均值算法的可能发展 趋势 4 j ：受人：孚埘! i 7 - f 1 - ，沦文编昂帧枷策炎分析 ：j 介 2 1 聚类分析 第二章模糊聚类分析简介 随着现代社会科学和自然科学的相互渗透，信息科学以其强大的生命力在所有边缘性学科中 脱颖而出，而模式识别则是信息处理中的一种极为重要的手段模式识别诞生于2 0 世纪2 0 年代， 随着4 0 年代计算机的出现，5 0 年代人工智能的兴起，模式识别在6 0 年代初迅速发展成为一门学 科，它所研究的理论和方法在很多学科和技术领域得到了广泛的应用，从而推动了人工智能系统的 发展，扩大了计算机应朋的可能性几十年来，模式识别研究己经取得了丰硕的成果，在很多领域 得到了成功的应用但是，由丁模式识别涉及到很多复杂的问题，冈此，现有的理论和方法对于解 决这些问题还存在不足之处，这就要求我们进一步的研究探讨 模式识别包括监督模式识别和非监督模式识别监督模式识别是指已知模式的类别和某些样 本的类别属性，首先用具有类别标记的样本对分类系统进行学习或训练，使该分类系统能够对这些 已知样本进行正确分类，然后用学习好的分类系统对朱知的样本进行分类监督识别需要知道学 习样本的先验知识与监督识别相对应的是非监督识别，它不需要知道样本的先验知识，也不需要 获取训练样本聚类分析就是无监督模式识别中的一个重要分支系统中聚类分析的基本思想是 根据物以类聚的原理，对样本进行分类聚类是无监督的方式，因为和分类学习相比，分类学习的 例子或数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确定，即把 所有样本作为未知样本进行聚类因此分类问题和聚类问题根本的不同点为：在分类问题中，知道 训练样例的分类属性值，而在聚类问题中，需要在训练样例中找到这个分类属性值采用聚类分析 技术，可以把无标识数据对象自动划分为不同的类，并且可以不受人们的先验知识的约束和干扰， 从而获取属于数据集合中原本存在的信息聚类分析的作用是将特征空间中的样本集合按照各个 样本点( 也称模型) 之间、样本点与样本点子集合之间以及样本点子集合之间的相似性测度( 距 离或相似度) 进行聚类，得到的样本点和子集合之间的关系体系采用这种方法可以定性与定量的 确定研究对象之间的“亲疏关系”，从而达到对其进行正确与合理分类的目的在聚类分析中，一 个很重要的问题就是确定聚类时所遵循的聚类准则，按照不同的聚类准则会得到不同的聚类结果 聚类问题实质上是在一定的聚类准则下的优化问题，只是不同的聚类算法所定义的准则有所不同 “物以类聚，人以群分”，聚类问题是经常遇到的问题，人类要认识和改造世界就必须区分不同的 事物，认识事物之间的相似性与差异性，从而认识事物的本质 所谓聚类( c l u s t e r i n g ) 就是把数据分成不同的组( c l a s s ) 或类( c l u s t e r ) ，并且使得组与组之间的 相似度尽可能的小，而组内数据之间具有较高的相似度将一群物理的或抽象的对象，根据它们之 间的相似程度，分为若干组，其中相似的对象构成一组，这一过程就称为聚类过程( c l u s t e r i n g ) ，一个 聚类( c l u s t e r i n g ，又称为簇) 就是由彼此相似的一组对象所构成的集合，不同聚类中对象通常是不 相似的聚类分析就是从给定的数据集中搜索数据对象之间所存在的有价值联系与分类不同，在 开始聚类之前用户并不知道要把数据分成儿组，也不知道分组的具体标准，聚类分析时数据集合的 特征是未知的聚类根据一定的聚类规则，将具有某种相同特征的数据聚在一起，也称之为无监督 学习而分类，用户则知道数据可分为儿类，将要处理的数据按照分类标准分入不同的类别，也称为 有监督学习 5 j j 眨人学帧i “学f 一沦史第一二- 模壮月聚炎分析翰介 聚类分析的典型应用主要有：在商业方面，聚类分析可以帮助市场人员发现客户群中所存在的 不同特征的组群在生物学方面，聚类分析可以用来获取动物或植物的层次结构，可根据基因功能 对其进行分类以获得对人群中所固有的结构更深入的了解聚类还可以从地球观测数据库中帮助 识别具有相似的十地使用情况的区域此外，还可以帮助分类识别互联网上的文档以便进行信息发 现作为数据挖掘的一项功能，聚类分析还可以作为一个单独的工具来使用，它可以帮助分析数据 的分布、了解各数据类的特征、确定所感兴趣的数据类以便作进一步分析聚类分析还可以作为 其他算法( 如：分类和定性归纳) 的预处理步骤 作为统计学的一个分支，聚类分析已经被广泛地研究了许多年，主要集中在基于距离的聚类分 析基于k m e a n s ( k 平均值) 和其他一些方法的聚类分析- t 具己经被加入到许多统计分析软件 包或系统中，如s p s s 以及s a s 在机器学习领域，聚类是无监督学习( u n s u p e r v i s e dl e a n i n g ) 的一个 例子聚类和无监督学习不依赖预先定义的类和训练样本由于这个原因，聚类是通过观察学习， 而不是通过例子学习在概念聚类( c o n c e p t u a lc l u s t e r i n g ) 中，一组对象只有当它们可以被一个概念 描述时才形成一个类这不同于基于几何距离来度量相似度的传统聚类概念聚类由两个部分组 成：( 1 ) 发现合适的类；( 2 ) 形成对每个类的描述在这里，追求较高类内相似度和较低类间相似度的 指导原则仍然适用 从实现方法上分，租略说来，聚类分析方法可大致分为四种类型：谱系聚类法、基于等价关系 的聚类方法、图论聚类法和基于目标函数的聚类方法等对于前三种方法由于不能适用于大数据 量的情况，难以满足实时性要求较高的场合，因此在实际中应用并不广泛，现在这些方面的研究已 经逐步减少了实际中受到普遍欢迎的是第四种方法一基于目标函数的聚类方法，该方法把聚类 分析归结成一个带约束的非线性规划问题，通过优化求解获得数据集的最优划分和聚类 2 2 聚类分析的数据类型 聚类分析是数据预处理的一种重要手段和工具要研究某个事物，就必须首先进行数据采集， 获取食物的部分特征信息这样，不同测量的传感器就构成了研究对象的量测空间，各个传感器的 一次观测则形成了量测空间中的一个点，称为样本矢量，经过大量的观测即可获得一组描述事物的 样本集聚类分析作为一种有效的工具，经常被用来学习所得到的样本集，以提供数据中蕴含的结 构信息，帮助研究者形成假设、发现规律、建立概念并做出决策因此，是聚类分析和数据集的共 同作用揭示了研究对象的性质，要研究有效的聚类分析方法，就必须首先分析数据集的特点 通常情况下。我们总把样本看作特征空间中的点，认为模式的特征由数值来刻画，因此，主要的 研究兴趣放在分析数据集中蕴含的信息和揭示点集的内在自然结构上，很少关心数据集的来源、 表现形式及其他性质实际上，在数据分析中我们会遇到各种类型的模式： ( 1 ) 表现在数量上有大小样本集之分，这样就必须考虑小样本的统计信息不足和大样本的运算 复杂度增加的问题，目前研究的热点主要集中在人样本一卜聚类分析的快速实现上 ( 2 ) 表现在分布状态上有不同的描述模型，比如g a u s s 混合模型、m i s e s 混合模型以及b u l l e t g r a v i t y 模型和s e e d w i n d 模型等等以往聚类分析的基础多建立在g a u s s 分布为空间点放置模型 之上的，假定同种模式的样本应聚集在一起，在空间中形成椭球形的分布状态，著名的f c m 聚类 算法正是基于此而提出的随着实际应用的需要，人们发现g a u s s 模型不能描述所有可能的聚类结 构，于是着手研究其他模型刻画的数据集的模糊聚类方法，比如在误差理论中，针对m i s e s 模型提 6 j ：缒人。学f 映卜学f t 论文第：章横糊聚炎分析6 介 山的方向数据( d i r e c t i o n a ld a t a ) 的模糊聚类算法，心米处理散射在球上的数据；基丁b u l l e t g r a v i t y 和s e e d w i n d 模型，b a n e i j e e 提出的基于模型的聚类分析方法均为这方面的代表 ( 3 ) 表现在数据集的组成上有不同的样本类型，比如噪声污染的数据、部分有类别标记的 数据以及事先有类( 或簇) 存在的数据等在噪声污染的数据集中，由于存在虚假样本和噪声点， 因此研究的重点集中在克服噪声干扰、获得良好聚类上，目前已提出许多鲁棒的算法，d a v e 和 k r i s h n a p u r a m 对此也作出了详细的评述；p e z d r c y 则认为实际应用中蕴含着大量的信息，表现在部 分样本事先有明显的类属关系，为此提出了部分监督的模糊聚类算法，以后充分利用先验知识获得 更好的分类；除了对样本点的聚类分析外，还有一种分析前已存在类簇的样本集，冈此要聚类分析 的不是单个的样本点而是点簇，比如，在汉字识别的模版预分类中，来自同一字符的不同模版早已 聚为一类形成一个模式，因此在划分中必须把每个簇中的样本划分到同一类中，使得聚类分析的难 度加大 ( 4 ) 表现在模式特征的刻画上有精确型和非精确型之分，目前的聚类分析绝人多数是围绕精确 数据矢量集的，非精确数据集的研究则少而又少 在数据采集的过程中，我们可以获得两种类型的信息：一是来自测量仪器的数值信息，二是来 自人类专家的语言( 不精确) 信息即便是测量信息，由于仪器的测量误差和噪声的污染等使得测 量值也并不可靠，像约为1 0 ( 模糊数) 或者在l o 到1 5 之间( 区间数) 这样的测量结果均为不精确的 数据针对这种不精确信息样本集，有人定义了符号对象( s y m b o l i co b j e c t s ) 作为传统数据形式的 一种扩展，在符号数据中，每个样本可能用不同特征刻画，每个特征的取值也可能不止一个，甚至为 区间数、包含关系、描述语言等等但这类数据太复杂，除了在概念聚类( c o n c e p tc l u s t e r i n g ) 中有 所涉及外，很少有直接针对它们的研究 尽管在许多情况下，信息多为不精确的，而且样本的特征值大都不能表示为一个实矢量，但传 统的分类方法绝大多数都是为实矢量设计的，为了研究这种不精确数据集的模式分类问题，人们首 先从最基本数据形式一区间值数据开始着手，如i s h i b u c h i 基于线性感知器的区间值数据的神经 网络分类方法；m a n d a i 提出了可以处理区间数的基于i f - t h e n 规则的分类器；在无监督分类方面， 李文华利片j 区间值模糊推理提出了基予模糊逻辑神经元的聚类网络：范九伦从c 均值算法角度提 出了两种区间值数据的f c m 算法 基于以上分析，聚类分析中的数据类型主要有两种结构假设对一个数据集进行聚类分析，该 数据集包含佗个对象，这些对象可以是人、树木、文件等等基于内存的聚类算法通常采用以下 两种数据结构： ( 1 ) 数据矩阵 数据矩阵是一个对象一属性结构，它其实是一张关系表，每列代表对象的一个属性，每行表示 一个数据对象具有m 个属性的礼个对象( 例如：树木对象可以利用仇个属性来描述，属性如：高 度、种类等) 可以表示为一个礼m 矩阵来表示： ( 2 ) 差异矩阵 0 1 1 o , l m 口n l 口n 竹l 7 。j ：疆人础贝i ：学位论殳第翠模糊聚炎分析确介 巨量i 。 通常情况下，d ( i ，歹) 是一个非负数，当对象i 和对象j 彼此“接近”时，该数据就越接近o 值； 该数据值越大，就表示对象i 和对象歹越不相似由于有d ( i ，歹) = d u ，i ) ，且d ( i ，i ) = 0 ，冈此，此矩 阵可表示成下三角行列式的形式 通常，数据矩阵又可称为双模式( t w o m o d e ) 矩阵，差异矩阵则又可称为单模式( o n e m o d e ) 矩 阵因为数据矩阵的行和列分别表示不同的实体，而差异矩阵的行和列则表示的是同一实体许多 聚类算法都是基于差异矩阵进行聚类分析的，如果数据是以数据矩阵的形式给出的，就要先将其转 换为差异矩阵，才能利用聚类算法对其进行处理 2 3 模糊聚类分析 最初的分类是从“非此即彼”的思想出发，同一事物属于且仅属于所划定类别中的一类，这种 分类的类别界限是“清晰的、明确的、不含糊的”，是属于普通集合理论的范畴随着人类认识程 度的不断提高与实际应用的需要，发现这种分类方法在实际应用中，用普通集合理论往往不能完全 解决具有模糊性的分类问题，例如：( 1 ) 将人按身高分为：高个子、中等个子、矮个子；( 2 ) 某一生态 条件对某种害虫或某种作物的存活或适应性可以评价为：有利、比较有利、不那么有利、不利、 很不利；( 3 ) 灾害性霜冻气候对农业产量的影响程度为：很严重、严重、较重、不严重等类似这种 问题的分类没有一个明确的界限 模糊聚类是将模糊集的概念应用到传统聚类分析中。让数据集的对象在分类中的隶属崩隶属 函数来确定，也就是说，对象在各类中的隶属度为连续区间【0 ，l 】之间的某个值，以不同程度隶属于 多个类，而非确定性聚类中的0 或1 的二值逻辑模糊聚类的优点在于能适应那些分离性不是很好 的数据，这允许了数据性质的模糊性，为数据结构的描述提供了详细的信息由于模糊聚类得到了 样本属于各个类别的不确定性程度，表达了样本类属的模糊性，即建立起样本对于类别的不确定性 的描述，更能客观地反映现实世界，从而成为聚类分析研究的主流之一 正是考虑到现实世界中很多事物的分类边界是不分明的，而这种不分明的划分在人们的识 别、判断和认知过程中起着重要的作用，为了用数学的方法来处理这种问题，扎德( l a z a d e h ) 于 1 9 6 5 年提出了模糊集合的概念他用隶属度函数( m e m b e r s h i pf u n c t i o n ) 来刻画处于中介过度的事 物对差异双方所具有的倾向性以此为起点和基础，人们开始用模糊集的方法来处理上述这种聚 类问题，并称之为模糊聚类分析下面我们先来介绍一下模糊集的概念： 定义( 模糊集) 1 8 1 集合x 的模糊集是一个映射：p ：x 【0 ，l 】；x 的所有模糊集定义为： f ( x ) = u l u ：x - - 4 【0 ，1 1 论域x 上的模糊集肪由隶属函数卢府( z ) 来表征，其中弘庸 ) 在实轴的闭区间 0 ，1 】上取值， 8 筇幸橙糊聚炎分析陶介 p 府( z ) 的值反映了x 中的元素z 对丁肘的隶属程度若p 府( z ) 的值靠近1 表示隶属度很高，若 p 府( z ) 靠近0 则表示隶属度很低如果定义p 府( z ) = 1 兮z 府和g i n ( z ) 一0 z 府，砑便演 化成一个普通集合m 所以我们可以认为模糊集合是普通集合的一般化 对于任给z x ，都有惟一确定的隶属函数g m c x ) 【0 ，1 】与之对应我们可以将廊表示为 g m ( z ) ：x _ 0 ，1 】， 即是p 庸 ) 从x 到 o ，1 】的一个映射，它惟一确定了模糊集合府 值得注意的是，我们在讨论模糊集合的概念时，论域x 所包含的元素是分明的，并不是模糊的， 而只有x 上的模糊集合m 才是模糊的从这个意义上说，模糊集合应该称为模糊子集合( f u z z y s u b s e t ) 对于模糊集合而言，其隶属函数的确定方法各种各样，常常带有主观性对同一论域上的模糊 集，不同的人或者用不同的判断标准，所得出的各元素的隶属度也不尽相同而不同的隶属度结构 又导致了该模糊集旱现出不同的模糊性为了建立能够合理地测度模糊集模糊性的函数，首先必 须规定若干条模糊性测度函数的性质 如果模糊集府中某一元素瓤的隶属度t t m ( z ) = 1 ，则说明霸完全隶属于m ，此时没有丝毫 的模糊性所以，对于g 府( z i ) = 1 的情况，模糊性测度应该为o 类似地，若p 庸( 锄) = 0 ，则说明黾 完全不隶属于府，也没有丝毫的模糊性对于p 庸( z t ) = 0 的情况，模糊性测度应该为0 因此，模 糊性测度( 以d w ) 表示) 的第一条性质应该是 ( 1 ) d ( p ) = 0 ，当且仅当p = 1 或p = 0 t t 厨( z i ) 越靠近l 或者0 ，模糊性就越小；t t 庸( z 1 ) 越远离l 或者0 ，模糊性就越大因此，一个合 理的推理就是，最大模糊性应发生在p 庸( 毛) = o 5 处，此处p 府( 规) 离l 和0 同样远y , i i i i ，模糊性 测度的第二条性质是 ( 2 )当且仅当p = 0 5 ，d ( p ) 获得惟一的最人值 性质( 2 ) 说明肛0 5 时的模糊性必小于肛= 0 5 时的模糊性我们可以直观地看到，p 的值离 0 5 越远，模糊性越小，由此得到第三条性质是 c 3 ， 雪：三主：筹：萋：妻：裂兰：；主兰 ：；： 我们知道，砑的补集府c 定义为 弘府。( z i ) = 1 一p 府( z ) ， 如果p 庸( z ) 0 5 ，p 府( 铂) 离1 和p 庸。( 戤) 离0 同样远根据这一对称性，我们归纳出模糊性测度的第四条性质是 ( 4 ) d 府) = d ( # g t 。) 9 丫丛入卜# 1 t 沦艾第学授糊聚炎，f j r 阳介 性质( 4 ) 说明，府和府c 具有同等的模糊性 对于有限集的情况，能够满足上述四条基本性质的数学形式是 d c p ，= f 砉1q 五c p 庸c z t ， ， c 2 t ， d ( p ) = i q 五( p 庸( z ) ) l ， ( 2 1 ) l t =j