（电路与系统专业论文）基于粗糙集的模糊聚类及其图像分割应用.pdf

摘要 驯ir e ii r l lirr lr i lliilj y 2 0 6 6 6 0 5 物理或抽象的集合，按照特定的规则划分成相似的对象类的过程称为聚类分 析。簇是数据对象的集合概念，这些对象与同一簇中的对象彼此相似，而与其他 簇中的对象相异。聚类分析在近几十年中已有了长足的发展，已成为数据挖掘研 究领域中一个非常活跃的研究课题，在图像分割中也有广泛的应用。为了适应众 多的应用要求，相当数量的聚类方法相继被提了出来。然而，由于不同的聚类应 用对分析方法有不同的要求，因此目前的聚类方法还存在一定的问题。本论文在 粗糙集的框架下，引入遗传算法，用进化优化目标函数的思想来解决聚类中存在 的问题，提出了基于粗糙集和遗传算法的一般化模糊聚类算法，并将其应用于图 像分割中。本论文的主要工作如下： 提出一种基于粗糙集和遗传算法的一般化模糊c 均值聚类方法。该方法通过 在粗糙集框架的基础上引入遗传算法的概念和思想，设计一种特别的染色体编码 方案，采用选择、交叉和变异的基因操作，融合了两种不同的传统聚类方法，也 就是模糊c 均值( f c m ) 和可能性c 均值( p c m ) 方法，对目标对象进行聚类， 降低了聚类方法对初始聚类中心选择的敏感性，提高了聚类结果的性能和稳定性。 针对图像处理的任务要求，将上述聚类方法应用于图像分割技术领域中，以 达到目标识别的目的。针对给定的图像，利用小波分解和灰度共生矩阵的方法， 提取图像的数学特征，再利用分水岭方法进行初分割以降低图像信息的冗余度和 数据的规模，利用该聚类方法对图像信息数据进行聚类得到图像的分割结果。实 验表明，该方法增加了图像分割的稳定性，提高了图像分割的平均准确度和分割 质量。 为解决较复杂数据的聚类问题，特别是流形数据，我们以基本的谱聚类算法 为基础，并在数据空间中采用密度敏感的距离测度方式对数据进行处理，得到其 在流形上相互之间的相似性，并通过论文提出的g a r f p c m 聚类算法对本征向量 矩阵数据进行聚类，达到对流形等较复杂数据进行分类和识别的目的。针对于流 形数据等较复杂数据，该聚类方法提高了聚类的平均准确率和鲁棒性，获得了较 好的类别划分结果。 本课题得到国家自然科学基金( n o 6 0 8 0 3 0 9 8 ) 、国家教育部博士点基金 科o 2 0 0 7 0 7 0 1 0 2 2 ) 、省自然科学基金( n o 2 0 1 0 j q 8 0 2 3 ) 、中央高校基本科研基金 州o k 5 0 5 1 0 0 2 0 0 11 ) 的资助。 关键词：粗糙集遗传算法模糊c 均值可能性c 均值图像分割 i i 基于粗糙集的模糊聚类及其图像分割应用 a b s t r a c t t h ep r o c e s st h a tap h y s i c a lo ra b s t r a c ts e to fo b j e c t si sp a r t i t i o n e di n t os e v e r a l s i m i l a ro b j e c t i v ec l u s t e r si sc a l l e dc l u s t e r i n ga n a l y s i s o b j e c t si nt h es a m es u b g r o u p a r es i m i l a rw h i l et h e ya r ed i s s i m i l a re a c ho t h e ri ft h e ya r ei nd i f f e r e n ts u b g r o u p s h e r e t h es u b g r o u pi sam a t h e m a t i c a lw o r dw h i c hi su s e da st h es e to fo b j e c t s f o rt h el a s t d o z e n so fy e a r sc l u s t e r i n ga n a l y s i sh a sb e e nd e v e l o p e dm a t u r e l y i tb e c o m e sa v e r yh o t r e s e a r c hs u b j e c ti nt h ef i e l do fd a t am i n i n g ，i n c l u d i n gi m a g es e g m e n t a t i o n ，a n ds oo n t om e e tt h er e q u i r e m e n t sf o ra p p l i c a t i o n ，al o to fc l u s t e r i n gm e t h o d sa r ep u t f o r w a r d h o w e v e r t h e r ea r ek i n d so fp r o b l e m si nv i e wo fd i f f e r e n tr e q u i r e m e n t sf o rd i f f e r e n t c l u s t e r i n ga p p l i c a t i o n s s ow i t h i nt h ef r a m e w o r ko fr o u g h - s e tt h e o r y , t h i sp a p e rc o m e s u pw i t h ag e n e r a l i z e df u z z yc l u s t e r i n gm e t h o db a s e do nr o u g h - s e ta n dg e n e t i c a l g o r i t h m ( g a ) t oc o p ew i t ht h ep r o b l e m si n c l u s t e r i n gt a s k su s i n gt h e i d e ao f o p t i m i z i n ga no b j e c t i v ef u n c t i o nv i ae v o l u t i o n i na d d i t i o n ，t h i sc l u s t e r i n gm e t h o di s a l s oe m p l o y e di nt h ef i e l do fi m a g es e g m e n t a t i o n t h em a i nc o n t r i b u t i o n sc a nb el i s t e d a sf o l l o w s ： a ni m p r o v e dg e n e r a l i z e df u z z yc - m e a n sc l u s t e r i n gm e t h o db a s e do nr o u g h 。s e t a n dg ai s p u tf o r w a r d w i t h i nt h ef r a m e w o r ko fr o u g h - s e tt h e o r y , t h i s m e t h o d i n t r o d u c e st h ei d e ao fg aa n dd e s i g n sas p e c i a lc h r o m o s o m ee n c o d i n gs c h e m et o a d o p tt h eg e n em a n i p u l a t i o n ，w i t hs e l e c t i o n ，c r o s s o v e ra n dm u t a t i o ni n c l u d e d a tt h e s a m et i m et h i s m e t h o dc o m b i n e s t w od i f f e r e n tt y p e so ft r a d i t i o n a lc l u s t e r i n g a l g o r i t h m sf c m ( f u z z yc m e a n s ) a n dp c m ( p o s s i b i l i s t i ec m e a n s ) i no r d e r t oc l u s t e r t h eo b j e c t s ，w h i c hh e l p st ol o w e rt h es e n s i t i v e n e s st oi n i t i a l l ys e l e c t e dc l u s t e rc e n t e r s a n di m p r o v et h ep e r f o r m a n c ea n ds t a b i l i t yo fc l u s t e r i n gr e s u l t s a c c o r d i n gt ot h er e q u i r e m e n t so fi m a g ep r o c e s s i n gt a s k s ，t h ec l u s t e r i n gm e t h o d m e n t i o n e da b o v ei sa p p l i e dt ot h ef i e l do fi m a g es e g m e n t a t i o n ，i no r d e rt oa c h i e v e t h e g o a lo fo b j e c ti d e n t i f i c a t i o n f o rag i v e ni m a g e ，t h em a t h e m a t i c a lf e a t u r e sa r ee x t r a c t e d w i t l lt l em e t h o d so fw a v e l e td e c o m p o s i t i o n a n dg l c m i na d d i t i o n ，a p r e s e g m e n t a t i o np r o c e s sc a l l e dw a t e r s h e da l g o r i t h mi s i n t r o d u c e dh e r et ol o w e rt h e r e d u n d a n c ya n ds c a l eo fo b j e c t s t h er e s u l to fi m a g es e g m e n t a t i o nc a nb eo b t a i n e d a f t e rac l u s t e r i n gp r o c e s sw i t ht h em e t h o dp u tf o r w a r di nt h i sp a p e r s o m ee x p e r i m e n t s p r o v et h a tt h i sm e t h o dc a ns t r e n g t h e nt h es t a b i l i t ya n di m p r o v et h ea v e r a g ea c c u r a c y - t oc o p ew i t hc o m p l i c a t e do b j e c t s ，e s p e c i a l l yf o rm a n i f o l dd a t ao b j e c t s ，b a s e do n i v基于粗糙集的模糊聚类及其图像分割应用 r o u g h s e tt h e o r yw ec a r r yo u tc l u s t e r i n gw i t had e n s i t y - s e n s i t i v em a n i f o l dd i s t a n c e m e a s u r ee m p l o y e di nt h ed a t as p a c et op r o c e s st h eo b j e c t s h e n c et h es i m i l a r i t y b e t w e e ne a c ho b j e c tp a i rc a nb eo b t a i n e d a f t e r w a r d st h ep r o p o s e dg a i 江p c m c l u s t e r i n ga l g o r i t h mi nt h i sp a p e ri s u s e dt op a r t i t i o nt h ed a t ao ft h es u b s e q u e n t e i g e n v e c t o rm a t r i x t h u sw ec a r lr e a c ht h eg o a lo fc l a s s i f y i n g a n dr e c o g n i z i n g m a n i f o l do rc o m p l i c a t e do b j e c t s t h i sc l u s t e r i n gm e t h o dm e n t i o n e da b o v ei m p r o v e s t h ea v e r a g ea c c u r a c ya n dr o b u s t n e s si nc l u s t e r i n gm a n i f o l do rc o m p l i c a t e dd a t a 1 1 1 i s p a p e r w a ss u p p o r t e d b y t h en m i o n a ln a t u r a ls c i e n c ef o u n d a t i o n ( n o 6 0 8 0 3 0 9 8 ) ，t h en a t i o n a lr e s e a r c hf o u n d a t i o nf o rt h ed o c t o r a lp r o g r a mo fh i g h e r e d u c a t i o no fc h i n a ( n o 2 0 0 7 0 7 010 2 2 ) ，t h ep r o v i n c i a ln a t u r a ls c i e n c ef o u n d a t i o no f s h a a n x io fc h i n a ( n o 2 010 j q 8 0 2 3 ) a n dt h ef u n d a m e n t a lr e s e a r c hf u n d sf o rt h e c e n t r a lu n i v e r s i t i e s ( n o k 5 0 5 1 0 0 2 0 0 11 ) k e y w o r d s ：r o u g h - s e t g e n e t i ca l g o r i t h mf c m p c mi m a g es e g m e n t a t i o n 第一章绪论 第一章绪论 1 1 聚类研究背景以及意义 聚类是按照特定的规则把相似的对象通过静态分类的方法分成不同的组别或 者更多的子集，这样让在同一个子集中的成员对象都有相似的一些属性，常见的 包括在坐标系中更加短的空间距离等。由此可见，聚类分析是可以利用数学的方 法来研究和处理所给定对象的分类问题，这个过程完全依赖于成员对象之间的特 征差别。古人云“物以类聚，人以群分，可以见得聚类是一个古老的问题，它伴 随着人类社会历史的产生和发展而不断深化和广泛化，人类要充分的认识世界的 本质就必须区别不同的事物并认识事物间的相似性和相异性【l j 。在模式识别领域 中，由于对输入空间中的样本对象没有设定期望的输出，因此聚类是非监督的一 类。 分类学是一门古老的学问，而聚类分析正是来源于分类学。随着人类文明中 科学技术的发展，对于分类的要求已经不仅限于靠人们的经验和专业知识去实现， 因为单凭这些难以确切地达到分类的结果。在这个基础上，该领域的学者逐渐把 越发成熟的一些数学工具引用到分类学中，也就是我们所说的数值分类学，在此 之后多元分析技术也被采纳到数值分类学中形成了后来的聚类分析。 传统意义上，常见的聚类分析计算方法主要如下几种类型：划分的方法 ( p a r t i t i o n i n gm e t h o d s ) ，层次的方法( h i e r a r c h i c a lm e t h o d s ) ，基于密度的方法 ( d e n s i t y b a s e dm e t h o d s ) ，基于网格的方法( g r i d b a s e dm e t h o d s ) ，基于模型的方 法( m o d e l b a s e dm e t h o d s ) 。传统的划分方法有k m e a n s 和k m e d o i d s ，传统的层 次法有b i r c h 和c u r e ，传统的密度方法有d b s c a n 和o p t i c s ，传统的网格 方法有s t i n g 和c l i q u e ，传统的模糊方法由c o b w e b 和c l a s s i t 。不论是哪 类的方法，聚类在其执行的过程中没有教师的指导，不能获得任何关于预先定义 的数据项的类属信息，因而通常被看作是一种无监督的学习方法【l 儿2 1 。 聚类是关于静态数据分析的一门技术，在许多领域受到了广泛的应用。在商 务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买 模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导植物和动物的分 类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中 相似地区的确定，汽车保险单持有者的分组，及根据房子的类型、价值和地理位 置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对w e b 上的文档进 行分类，以发现信息。 2 基于粗糙集的模糊聚类及其图像分割应用 聚类研究已经有相当长的时间了，但是聚类的应用研究一直并未停息。随着 各个领域间联系越来越多，越来越精密，聚类分析依然有提高的空间和意义。 1 2 模糊聚类概述 从划分的角度看，传统的聚类分析是一种硬划分，体现在它将每个有待辨识 的对象严格地划分到某个类中，具有非此即彼的性质，因此通过这种划分而得到 的类别相互之间有分明而严格的界限。但是实际上，大多数的对象并没有完全严 格的属性，它们之间在类属和性态方面存在着中介性，适合进行软划分【2 】。自从 学者z a d e h 3 提出模糊集理论以来，对于这种软划分便有了有力的分析工具，而 人们也逐渐用模糊处理的方法来解决聚类问题，并称之为模糊聚类分析方法。 最早提出模糊划分这一概念的是r u s p i n i 4 ，基于这个概念该领域内的学者提 出了多种多样的聚类方法，比较典型的有：基于相似性和模糊关系的方法【5 1 ，基 于模糊等价关系的传递闭包方法 6 1 ，基于模糊图论最大树的方法【7 1 ，以及基于数 据集的凸分解、动态规划和难以辨识关系等此类方法。事实上，上述所列的方法 由于其本身的局限性并不适用于大数据量的聚类任务，难以满足实时性要求高的 场合，因此很难有更加广泛的应用，故在该方面的研究也就越来越少了。 考虑到以上阐述的问题，现在受到普遍应用的是基于目标函数优化的方法。 该方法设计简单、解决问题的范围广，最终还可以转化为优化问题而借助经典数 学的非线性规划理论求解，并易于计算机实现。因此，随着计算机的应用和深入 发展，此类方法成为聚类方法研究的重点和热点。其基本思想是将聚类的准则函 数转化为函数要优化的目标函数，然后就是如何使用数学手段求解目标函数的最 值并获得最佳聚类结果的问题了。现有的实现途径主要分为基于交替优化的实现， 基于神经网络的实现，基于进化计算的实现3 类。目前，模糊聚类研究主要集中 于以下几个方向：对模糊划分矩阵的研究，对相似性准则的研究，对聚类原型的 研究，对加权指数模糊度的研究，对聚类所处理数据集类型的研究等【2 j o 基于划分的方法是我们研究模糊聚类问题时常采用的一类方法，比较经典的 聚类方法有传统的模糊c 均值算法等，这些方法共同点是都没有对目标对象的特 征进行优化，而是直接地通过他们的特征进行聚类操作。这样一来，上面提到的 这类方法得到的结果就会很大程度上取决于对象的分布情况。如果其中的某一类 中对象的分布稀疏，而另一类的中的对象分布稠密，使用这些方法得到的结果就 会比较差；如果遇到对象分布更加复杂混乱的情况，聚类的结果就会远远低于我 们对于结果的期望。 以模糊c 均值举例，事实上这个方法对于非超球体数据、被噪声污染的数据、 多模式原型混合的数据或不对称数据等多种常见的数据结构起不到好的效果。考 第一章绪论 3 虑到这个问题，相关领域的学者在后续的研究中提出一些新的模糊聚类算法来适 应不同类的数据结构模式。例如，针对不同而又复杂的聚类原型，分别提出了基 于壳原型、任意二次曲线原型的模糊聚类算法。当然这类算法也有其本身的弱点， 一方面在于需要利用对象的先验知识选择合适的聚类原型，另一方面在于不能有 效处理混合聚类原型的数据结构。 模糊聚类理论的发展丰富也推动了其在生产实践中的应用，而反过来实际应 用的需求和问题也间接促进了模糊聚类理论的不断丰富和完善。随着理论的发展， 模糊聚类已经在众多的领域获得广泛的应用，并且取得了令人满意的效果和可观 的效益。其应用范围涉及到通讯系统中的信道均衡、矢量量化编码中的码书设计、 时间序列的预测、神经网络的训练、参数估计、医学诊断、天气预报、食品分类、 水质分析、图像处理等领域 2 1 。 1 3 模糊聚类的图像分割应用 根据抽象程度和处理方法的不同，图像领域的技术可以分为三个概念性的层 次：图像处理、图像分析和图像理解，把这三个层次的有机结合称为图像工程技 术。图像处理是较低层的操作，主要在图像像素级上进行操作。有代表性的图像 处理技术包括图像降噪、图像编码和图像分割【8 j 。 其中，图像分割是图像处理中一个关键的部分，它是后续图像分析和图像理 解的基础，但是由于各方面的原因其技术一直是阻碍图像理论发展的瓶颈之一。 另一方面，图像分割在实际中也有广泛的应用，如目标识别、目标测量、变化监 测等。由于分割的准确性会很大地影响后续任务的有效性，因此具有相当重要的 研究意义。 在本质上图像分割是一个按照其像素属性( 如灰度、纹理、颜色、对比度等) 进行类别划分的过程，也就是给每个像素赋予一个标号，该标号反映像素在分割 结果中所属的类别。只要找到这些特征的标号，就能实现对像素的分类，从而得 到图像分割的结果。从这个角度看，模糊聚类技术可以很容易地应用到图像分割 中。 模糊聚类技术应用到图像分割中的基本思想是，通过颜色强度矩阵或变换等 现代数学方法提取图像像素的特征数据，以此作为模糊聚类的处理对象，并对这 些数据进行聚类操作，最终得到像素的类别标号，达到图像分割的目的。目前， 基于传统模糊c 均值算法及其变体算法的模糊聚类在图像分割上的应用已经极为 广泛，并且扩展到图像的变化检测领域中。 针对图像分割任务中有噪声的图像，可以设计加入邻域信息的模糊聚类算法， 此类算法能够利用图像中的噪声区域信息，提高分割的准确率。另外，一些实现 4 基于粗糙集的模糊聚类及其图像分割应用 自动分割的聚类算法也相继提了出来，这种算法可以不预先给定分割的目标数目 便得到分割结果。 1 4 本文研究的主要内容及论文安排 到目前为止，相关领域内的学者对模糊聚类方法及其图像分割上的应用，进 行了广泛而深入的探讨和研究。但是，由于图像应用的多样性和海量性，以及模 糊聚类本身复杂而多样的特点，要更好地构建算法并较好地实现图像上的应用是 一项很有挑战性的课题。 在已有聚类背景和图像应用前景的吸引下，本文对模糊聚类及其在图像上的 应用问题进行了比较深入的研究。具体内容安排如下： 第一章为绪论，简要介绍了本论文的研究背景及意义，包括模糊聚类的定义、 起源与发展，传统聚类方法的类型和相关算法，以及模糊聚类在图像分割技术上 的应用知识。 第二章包括以下几部分内容，首先介绍了模糊聚类的基础知识，包括概念、 实现思想和两个隶属度表示方式不同的传统模糊聚类算法；然后概述了粗糙集的 基础知识，包括基本理论、特点和相关应用，特别是在数据挖掘领域的应用；最 后详细介绍了一种粗糙集框架下的聚类算法r f p c m ，包括其思想、流程、特点 说明，以及基于粗糙集的这一类聚类算法的定量评价指标。 第三章重点叙述了一种基于粗糙集和遗传算法的模糊聚类方法g a r f p c m ， 首先简要介绍了遗传算法的基础知识，包括理论背景、应用以及简单遗传算法的 基本步骤；然后在粗糙集框架下将遗传算法思想引入到聚类算法中，提出了基于 粗糙集和遗传算法的模糊聚类算法g a r f p c m ，并对其算法思想、具体实现步骤 等进行了详细的描述；最后，给出了与该算法有关系的仿真实验和与之相关的质 量与性能分析。 第四章是与图像处理相关的，首先对图像分割的基础知识进行了简要描述， 包括图像分割的基本概念和一些传统及新型的图像分割方法；然后，将第三章介 绍的基于粗糙集和遗传算法的模糊聚类方法g a r f p c m 引入到图像分割领域中， 构建了基于粗糙集和g a 模糊聚类的图像分割算法s e gg a r ；最后，将提出的 图像分割算法进行了在人工合成图像和真实图像上的仿真实验，并从视觉观察和 统计学角度进行了详细的分析。 第五章在第三章提出的基于粗糙集和遗传算法的模糊聚类算法g a r f p c m 算法基础上，对传统的谱聚类算法进行改进，提出具有进化思想和密度敏感性的 谱聚类算法s c g a r 。首先，针对谱聚类的基础进行了阐述，包括其基本的思想、 算法的步骤及其应用；然后，描述了算法改进的过程：引入密度敏感的距离测度 第一章绪论 5 方式，以此在数据空间中对数据进行相似性计算，并通过g a r f p c m 算法对本征 向量矩阵数据进行类别划分，以达到聚类的目的；最后描述了相关的算法评价指 标，并以此对数据集进行仿真实验，并通过对比算法对本章算法的性能进行了分 析。 第六章对本文的工作进行了总结，并以先前工作为基础对于今后要做的工作 和相关领域内的前景从不同的角度进行了展望。 6 基于粗糙集的模糊聚类及其图像分割应用 第二章基于粗糙集的模糊聚类研究 7 第二章基于粗糙集的模糊聚类研究 2 1 模糊聚类理论基础 聚类( c l u s t e r i n g ) 是数据挖掘领域中一个重要的研究课题。概念上，聚类可 以看作是将物理或抽象对象的集合划分为由类似的对象组成的多个类或簇的过 程。从用划分方法进行聚类分析的角度上讲，划分类别分为硬划分和模糊划分， 其中模糊划分对应的聚类就是模糊聚类( f u z z yc l u s t e r i n g ) 。在聚类的过程中，有 些数据的属性对于提高聚类质量所起的作用很小，有时候甚至会起到干扰的负面 作用。但传统的模糊聚类是无指导分类的过程，没有考虑到这些属性的影响，忽 略了它们之间的差异性，降低了聚类结果的质量。 2 1 1 模糊聚类的基本思想 当聚类涉及到事物之间的模糊界限的时候，需运用模糊聚类的分析方法。一 般地，把要被聚类的事物称为目标或对象。从聚类过程的数学类型看，模糊聚类 有两种基本方法：系统聚类法和逐步聚类法。 系统聚类法是基于模糊等价关系的模糊聚类分析方法。在经典的聚类分析方 法中，可用经典等价关系对目标集合d 进行聚类。设尺是d 上的经典等价关系， 对于d 中的两个元素x 和y ，若x r y 或( 五y ) 足，则把工和j ，并为一类，否贝, l j x 和 y 分到不同的类中。 与之相应地，我们也可以用0 的模糊等价关系对目标集合d 进行模糊聚类。 设r 是d 上的模糊等价关系，从是尺的隶属函数。对于任何口1 0 ，1 i ，定义尺 的口截关系 & = ( 五y ) i 腾( 五y ) 口；五y e o ( 2 - 1 ) 其中，& 是d 上的经典等价关系。可以根据& 得到d 的一种聚类，这儿称之 为口水平上的聚类。即对于d 中的任意两个元素x 和y ，如果有, u s ( x ，y ) 倪，那 么元素x 和y 属于同一类；反之，x 和) ，不属于同一类。 应用这种方法，分类的结果会取决于口值的大小。口值越大，分的类数越多。 口小到某一值时，d 中的所有样本就合并为同一类。这种系统聚类法其优点在于 可按照实际需要选择口的取值大小，以便得到适合该需要的分类结果。 与系统聚类法相对应，逐步聚类法是一种基于模糊划分的模糊聚类分析方法。 它是预先给出要分类的对象要分成的类数，然后按照某种最优化的原则进行再分 8 基于粗糙集的模糊聚类及其图像分割应用 类，经过多次迭代直到得到一个比较合理的结果为止。 在分类的过程中，可认为某个对象以某一隶属度属于某一类，又以另一个隶 属度属于另外的一类。这样以来，对象就不是明确地属于或不属于某一类。若待 聚类对象个数为玎，要分为c 类，则它的模糊划分矩阵元素“有如下的3 个特性： ( 1 ) 甜f ，l o ，1 l ，其中i = l ，c ；j = 1 9 * , o 刀。 ( 2 ) k = 1 ，其中，= 1 ，”，即每一个对象属于所有类的隶属度累加和 为1 宁1 l ( 3 ) k 0 ，其中i = 1 ，f ，即每一个类的模糊子集都不能是空集。 对于逐步聚类法来说，模糊划分矩阵有无穷多个，这种模糊划分矩阵的全体 称之为模糊划分空间。传统意义上，最优分类的标准是对象与聚类中心的距离平 方和最小。这是因为一个对象是按照不同的隶属度属于各类的，具有一定的相对 性，所以应同时考虑它与每一类的聚类中心的距离。该方法需要反复迭代计算， 计算工作量大，需要在电子计算机上进行。算法得到最终的最优划分矩阵之后， 还应进行去模糊，即计算相应的常规划分以得到所需的聚类结果。 目前模糊聚类算法的发展情况表明，基于划分概念的逐步聚类法是这个领域 的主流研究方向。逐步聚类法也逐渐衍生出不同的分支，其算法越来越显得成熟 和具有多样性。但是由于其应用范围广，应用的要求也各种各样，聚类算法总是 有其一定范围内的弊端和不足。 2 1 2 模糊c 均值算法 模糊c 均值( f u z z yc m e a n s ，f c m ) 1 1 1 是最常见的一种模糊聚类算法，它 在每次迭代中根据与类中心的欧氏距离给每个对象分配一个隶属度，称为概率性 隶属度( p r o b a b i l i s t i cm e m b e r s h i p ) 。对于f c m 算法来说，它可以有效处理由类边 缘的重合引起的不确定性的问题。 我们令x = 而，x ，吒 为要被f c m 算法分成c 类的玎个对象的集合， v = v 1 ，v ，v c ) 为某次迭代过程中c 个聚类中心的集合，其中x ，9 t ”， v 孵“。则f c m 算法要通过最小化一个准则函数来得到最终的聚类结果，该准 则函数为： ，= 主窆( 心) 柏峙一v i l 2 ( 2 2 ) 3 = il = l 其中，1 惕 o o 是f c m 算法的加权指数模糊度，v 为第f 个类层对应的中心， 鳓【o ，l 】是对象t 对类层的概率性隶属度，i i | i 是距离表达式，通过拉格朗日求 解法可以得到极值情况下聚类中心和概率性隶属度的解，作为其更新公式。如下 所示： 第二章基于粗糙集的模糊聚类研究 9 ( 2 3 ) ( 2 4 ) 其中，以为对象乃到类层中心的欧氏距离，即： 刃= 忙一v 8 2 ( 2 5 ) 整个f c m 聚类的过程开始于从对象集合中随机选择c 个对象作为初始的c 个 类中心。基于欧氏距离的测度，通过式( 2 4 ) 计算对象x ，对类屈的概率性隶属度。 在所有对象的隶属度计算完成后，新的聚类中心通过式( 2 3 ) 计算而得。如此循 环迭代计算，直到聚类中心达到一定的稳定程度后迭代结束。也就是说，上一次 迭代中的中心与当前迭代的中心相同的时候。迭代结束后，根据对象对所有类隶 属度的大小分配类的标记给它，聚类过程完成。 2 1 3 可能性c 均值算法 在上面描述的f c m 算法中，一个对象的概率性隶属度与这个目标与相应类 中心的相对距离成反相关的关系。事实上，这样造成了该算法对噪声和异常值相 当敏感。因此，最终结果的概率性隶属度并不总是对应着某个对象属于某个类的 真实程度。另外，从与中心一致性的角度出发，一个对象x ，对类屈的概率性隶属 度只应该决定于该类的中心与它的远近程度，而与其他类的相似程度是无关的。 从物理世界的联系本质看，这似乎并不是一个十分合理的观点。 为解决这个问题，k r i s h n a p u r a m 和k e l l e r 【1 2 】提出了可能性c 均值( p o s s i b i l i s t i e c m e a l l s ，p c m ) 算法。与f c m 的概率性隶属度相对应，p c m 采用一种叫做可 能性隶属度( p o s s i b i l i s t i cm e m b e r s h i p ) 的衡量方式来描述某个对象属于某个类的 程度。p c m 也要通过优化一个准则函数来达到聚类的目的，这个要最小化的函数 描述为： ( 2 6 ) 其中，l _ m 2 o o 是p c m 算法的加权指数模糊度，绣表示第f 个类屈的尺度参数。 与f c m 最大的不同，在于p c m 形成的可能性隶属度矩阵n 并不算是一个划分矩 阵，因为它并不满足划分矩阵的第二个特性： 唧兰广一 ，【一，_j 。卑一 = 士婀 = 分 ，广 暑一-、 屹 一 0 。一 研 。简 + 2 i 一 r - 、 ，ji 。卢 。硝 i i ， 1 0 基于粗糙集的模糊聚类及其图像分割应用 c 屹= 1 ( 2 - 7 ) ，= l 驴研1 q 罐 有以下限制 o ，1 】，v f ，；o o ，w 。 尺度参数臻表示类屈的影响因子或大彬其计算公式为： 轳肜云 q 母) 其中， 经验上，k 一般取值为l 。在每次循环迭代中，”，的更新值只依赖于对象x ， 和类中心v 的相似程度。数据的最终划分可以理解为一种可能性的划分，而隶属 度值可理解为某个对象属于某个类的可能程度，或对象对于该类中心的一致性。 聚类中心更新的进程方式与f c m 的情况一模一样，可参照式( 2 3 ) ，只需将公 式中的从。换为k ，即可。 然而，p c m 算法的缺点是容易产生重合的类【1 3 1 。为解决这个问题，最近关于 把f c m 和p c m 的两种隶属度( 概率性隶属度与可能性隶属度) 结合起来用于模 糊聚类算法中也被提了出来【1 3 l 【1 4 】。 2 2 粗糙集与及其聚类应用 粗糙集( r o u g hs e t ) 理论【9 j 【1 0 】作为一个全新的数学概念，是近年来用于解决 不确定性，模糊性和信息不完整性的一个新范型，已经应用于模糊规则提取，不 确定性推理，模糊建模等方面。它最早是在1 9 8 2 年由波兰的著名学者p a w l a kz 教授首次提出，而经过1 0 年的系统化研究后他出版了相关的专著，在专著中全面 而系统地详述了粗糙集理论。粗糙集解决不确定性问题，主要是通过学习经验获 得知识，以分析不确定关系，进而进行不完整知识的推理，近似决策的分类决策 等。由此可见，粗糙集是在知识不确定情况下用于帮助决策的有效方法。 0 1 二l 啦i i u 一 耽 v-，、l-、 。芦。卢 = = p q 第二章基于粗糙集的模糊聚类研究 2 2 1 粗糙集的背景知识 经过近3 0 年的发展，目前粗糙集理论已经成为数据处理领域中解决不确定性 问题的热门研究方向。粗糙集理论的主要思想，在于通过按照规则合并知识库中 相似相近的知识元素以进行知识约简。 粗糙集理论具有一些其他数学理论不具有的一些独特的观念，这些观念使得 基于该理论的方法特别适合于进行不确定性数据分析f 4 0 j ： ( 1 )知识的粒度性。粗糙集理论认为知识粒度性的存在导致了使用既有的 知识不能精确地表示某些概念，所以通过引入不可区分关系作为粗糙集 理论的基础，并以此定义了上下近似等概念，能够有效地逼近这些概念。 ( 2 )新型成员关系。与模糊集合理论需要指定成员隶属度不同，粗糙集的 成员是客观计算的，其方法基础只和数据有关，从而避免了主观因素的 影响。 从知识发现的角度出发，采用粗糙集的方法具有很多的优点。由于粗糙集为 分析和处理不确定性，模糊性和信息不完整性提供了完备而有效的方法，因此具 有广泛的应用范围。目前，粗糙集理论应用的主要领域有专家系统、图像处理、 机器学习、模式识别、知识获取以及数据挖掘等。通过在数据挖掘中引入粗糙集 理论可以解决信息不完整性、不精确情况下的问题，并且基于知识约简的思想能 够减小数据挖掘系统的复杂性，提高系统的运行效率。对于数据挖掘领域来说， 粗糙集最早主要用于分类，而今有关粗糙集的研究已经扩展并深入到该领域中的 各个方面【”j 。 在数据挖掘领域中应用粗糙集理论，主要是基于粗糙集固有的一些特征，如 下所示： ( 1 )在数据挖掘中，关系型数据库是最主要的研究对象，考虑到可以把关 系表作为粗糙集方法中的信息表或者决策表，因此这种类型的数据库有 利于粗糙集的应用。 ( 2 )粗糙集理论的约简思想可以应用于高维数据的预处理技术，通过减少 冗余属性来达到数据降维的目的。 ( 3 )从客观世界的角度出发，从数据库中挖掘到的知识可能是不确定的， 粗糙集为此提供了一个较为有效的解决途径。 ( 4 )应用粗糙集理论有助于数据挖掘计算的并行执行，尤其是在大型数据 库上进行数据挖掘计算时其效率会得到很大的提高。 ( 5 )粗糙集在处理数据中的异常值方面有很强的能力。 近些年来，粗糙集理论在很多不同的领域中得到了广泛的应用，包括汽车工 业，商业预测，图像过滤和网页挖掘等。粗糙集在知识发现、决策分析、模式识 1 2 基于粗糙集的模糊聚类及其图像分割应用 别和机器学习等领域的成功应用，也逐渐引起了国际上学术界的广泛关注。 2 2 2 粗糙集理论基础 粗糙集理论源于一个概念近似空间一个关系系统( 或二元组) 。 对于一个组合对( r ) ，其中u 是一个由研究对象组成的非空有限集合( 称 之为论域) ，尺是u 上的一个等价关系。其中，r 具有自反性、对称性和传递性。 按照一定的规则，关系尺把集合u 分解成不相交的类，或者称划分为一系列不连 续的子集。即对于两个元素x 和y ，当且仅当( x ，y ) r 时，判定x 和y 属于同一 类。此处，我们用u r 表示关系r 下【，的商集，并且有u 尺= 墨，五，以 ， 其中z 是灭的一个等价类，f = 1 ，2 ，研。如果u 中的两个元素x 和y 属于相同 的等价类x u r ，那么我们可以认为石和y 是不可区分的。另外，月的等价类 和空集。是近似空间( u ，尺) 中的初等集。给定一个任意的集合x 2 u ，一般来说 它可能不能在( u ，r ) 中精确描述，这时可通过一个下近似和上近似对来描述，即： 星( x ) = u 五a n dr ( x ) = u 五 ( 2 - 1 1 ) x c 崔x 。r - 嘣# o 也就是说，下近似墨( 彳) 是作为x 子集的所有初等集的联合，而上近似尺( x ) 是与有x 交集的所有初等集的联合。我们用区间i 星( x ) ，r ( x ) i 表示近似空间 ( u ，r ) 中一个普通集合x ，或者称之为x 的粗糙集。下近似垦( x ) 可理解为那些 明确属于x 的u 中的元素集合，而上近似r ( x 1 则为那些可能属于x 的u 中的元 素集合。更进一步地，当且仅当r ( x ) = r ( x ) 时认为x 是在( u ，r ) 中可定义的( 或 精确的) 。 关于粗糙集，p a w l a kz 提出了一些基本的性质，本论文中仅仅描述几条由这 些基本性质推理出来的与后续内容相关的性质【4 9 】。 对于一个划分分类方案u r = 五，五，纸 ，因为缺少足够的知识不能 准确定义其中的五，i = 1 ，2 ，聊。然而，可以使用现有的信息定义五的下近 似区域星( 墨) 和z 的上近似区域尺( 置) ，以此来描述五。五的下近似区域星( 置) 和上近似区域尺( 置) 满足以下性质： ( 1 ) a 星( 置) s r ( 置) u 。 ( 2 ) 星( 置) 厂、星( x ，) = a ，i 歹。 ( 3 )一个元素z 不属于任何一个下近似区域x 一定属于两个或多个上 近似区域。 这三条性质不是相互独立的，本论文后续内容涉及到了以上的性质。 第二章基于粗糙集的模糊聚类研究 1 3 2 2 3 基于粗糙集的聚类算法r f p c m 粗糙集理论具有善于处理不精确数据的特性，因此将模糊聚类方法与粗糙集 理论结合，更加符合客观世界对聚类任务的要求，也逐渐成为聚类分析方法的重 要研究方向，并获得了广泛的应用。1 9 8 2 年在文献【l6 】中，l i n g r a s 和w e s t 提出一 个新的聚类算法粗糙c 均值( r o u g hc m e a n s ，r c m ) 。其中，r c m 算法通 过一个类中心和一个上近似( u p p e ra p p r o x i m a t i o n ) 和下近似( l o w e r a p p r o x i m a t i o n ) 对来描述一个类。上近似和下近似是两个不同的加权参数，用来 计算新的聚类中心。从处理不确定性的角度看，对模糊集和粗糙集理论的