（模式识别与智能系统专业论文）模糊聚类算法的研究与实现.pdf

南京理工大学硕士学位论文模糊聚类算法的研究与实现 摘要 聚类就是按照事物间的相似性进行区分和分类的过程，在这一过程中没有教 师指导，因此是一种无监督的分类。聚类分析则是用数学方法研究和处理所给定 对象的分类。传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分 到某个类中，具有非此即彼的性质，因此这种分类的类别界限是分明的。而实际 上大多数对象并没有严格的属性，它们在性态和类属方面存在着中介性，适合进 行软划分。z a d e h 提出的模糊集理论为这种软划分提供了有力的分析工具，人们开 始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。 模糊聚类分析算法的一般包括三个步骤：第一步：数据标准化；第二步：建 立模糊相似矩阵：第三步：聚类。本文对模糊聚类分析中的两种算法进行研究并 给出实验结果。然后分析等价传递闭包法，针对传递闭包法的不足之处，结合等 价矩阵的性质，并利用最优等价矩阵的概念，给出了一个新的模糊聚类分析算法， 即：近似最优等价矩阵法。 最后，利用v 1 3 语言实现了一个模糊聚类分析算法，并通过实际数据加以验证。 关键字：模糊集合，模糊聚类分析，模糊等价矩阵，传递闭包 南京理工大学硕士学位论_ 戈 模糊聚类算法的铲究与实现 a b s t r a c t t h i sp a p e rw i l li l l u s t r a t e “c l u s t e r i n ga n a l y s i s ”t h o r o u g h l y c l u s t e r i sap r o c e s st h a ta s s o r t st h i n g sb yt h e i rs i m i l a r i t y t h e r ei sn oa d v i s e r i nt h i sp r o c e s s 。s oi t i 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 “c l u s t e r i n g a n a l y s i s ”r e s e a r c ha n dp r o c e s sa s s o r tt h i n g sb ym a t h e m a t i c a lm e a n s t r a d i t i o n a lc l u s t e r i n ga n a l y s i sa s s o r t st h i n g ss t r i c t l y ：t h e r e f o r et h e l i m i to ft h ec l a s s i f i c a t i o ni sv e r yc l e a r l y b u ti nf a c tm o s to ft h et h i n g s h a v en oo b v i o u sa t t r i b u t eb ye a c h ：t h e i r1i m i ti sv a g u e ，a sar e s u l ts o f t c l a s s i f i c a t i o ni sab e t t e rw a yt op r o c e s st h e m p r o f e s s o rz a d e hi n t r o d u c e d t h et h e o r yo ff u z z ys e t s ，w h i c ho f f e rap o w e r f u lm e a n st os o l v et h ep r o b l e m p e o p l eb e g i nt ou s ef u z z yw a yt od e a lw i t hc l u s t e r i n gp r o b l e m ，a n dc a l l i t “f u z z yc 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 r i n ga n a l y s i s ”c o n t a i n st h r e es t e p s t h ef i r s ti sd a t a s t a n d a r d i z a t i o n ：t h es e c o n di st oe s t a b l i s hf u z z ys i m i l a rm a t r i x ：t h et h i r d i sc l u s t e r i n g t h i sp a p e rw i l lr e s e a r c ht w oa r i t h m e t i co ft h ef u z z y c l u s t e r i n g a n a l y s i sb yt e s t a n dt h e nw ew i l la n a l y z et h e “t r a n s i t i v e c l o s u r e ”a r i t h m e r i ct h r o u g ht w op r o c e d u r e s ：f i r s t ，b yc o m p r e h e n d i n g c h a r a c t e r i s t i co ft h et r a n s i t i r ec l o s u r ea r i t h m e t i ct oa n a l y z ei t sd e f e c t ： s e c o n d u s i n gt h ec o n c e p to f “o p t i m a lf u z z ye q u i v a l e n tm a t r i x ”a n dt h e n w ew i l lg i v ean e wf u z z yc l u s t e r i n ga n a l y s i sa r i t h m e t i c t h en a m ei s “a p p r o x i m a t eo p t i m a le q u i v a l e n tm a t r i x ”a r i t h m e t i c f i n a l l y ，t h ep a p e rw i l la c c o m p l i s hf u z z yc l u s t e r i n ga n a l y s i sp r o g r a m b yv b i ti ss i g n i f i c a n tt ou s ed a t at ov a l i d a t ei t k e yw o r d s ：f u z z ys e t ，f u z z yc l u s t e r i n ga n a l y s i s ，f u z z ye q u i v a l e n tm a t r i x ， t r a n s i t i v ec l o s u r e l i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：建盘2 d d 右年6 剧c 曰 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：啦 2 0 粥年8 刖扣 南京理工大学硕士学位论文模瑚聚类算法的研究与实现 1 绪论 1 1 研究背景 聚类是人类最基本的一项认识活动，人类要认识世界就必须区别不同的事物 并认识事物间的区别与联系，并且是伴随着人类的产生和发展而不断深化的一个 问题。所谓聚类，它是一种研究分类的多元分析方法，就是按照事物的某些属性， 将事物分成多个类或簇，所以又称为簇分析、群分析，它的做法是使得在同一类 中的事物相似性尽可能的大，不同类别间的事物相似性尽可能的小。聚类分析就 是用数学方法研究和处理所给定对象的分类。 经典分类学往往是从单因素或有限的几个因素出发，凭经验和专业知识对事 物分类。这种分类具有非此即彼的特性，同一事物归属且仅归属所划定类别中的 一类，因此这种分类的类别界限是分明的，所以这种分类又被称为硬分类。随着 人们认识的深入，发现这种分类越来越不适用于对具有含义模糊的事物进行分类。 如把人按身高分为“个子高的人”，“个子矮的人”，“身材中等的人”。如何判别特 定的一个人的类别便产生了经典分类学解决不了的难题。而这类问题适合进行软 分类，模糊数学的产生就为软分类提供了数学基础，由此产生了模糊聚类分析。 我们把应用普通数学方法进行分类的聚类方法称为普通聚类分析，而把应用模糊 数学方法进行分析的聚类分析称为模糊聚类分析。由于模糊聚类得到了样本属于 各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别 的不确定性的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流。 在现实生活中，人们往往会使用一些意思清楚而又不准确的语言来描述这个 世界，比如“这座山很高”，“今天天气很热”等，对于有着丰富经验和常识的人 来说，理解这些是很容易的，但让计算机去分析这些带有模糊性的信息就很困难 了，例如，我们能很容易地根据别人描述的特征找到一个东西，但让计算机去做 则很困难，因为以往的计算机技术大都是基于经典数学的，经典数学能很好地处 理精确信息，但对含义不明确的信息就显得无能为力了，而这种信息在日常生活 中被大量使用。美国控制学专家l a z a d e h 教授充分认识到了这一矛盾，提出了模 糊数学的核心思想，就是用数学的手段来模仿人的思维，建立对复杂事务进行模 糊度量、模糊识别、模糊推理、模糊控制和模糊决策的本领，由此产生了模糊数 学。 最早是由r u s p i n i 将模糊理论应用于聚类分析，于是出现了数据对象聚类归属 模糊化，即每个数据对象并非一定要绝对的归属于某个聚类，而可以按照某一归 属系数不同程度的分别属于不同的聚类。模糊聚类分析的实质就是根据研究对象 南京理工大学硕士学位论文模糊曩类算法的酽究实现 本身的属性构造模糊知阵，在此基础上根据一定的隶属度来确定其分类关系。比 较典型的有：基于相似性关系和模糊关系的方法( 包括聚合法和分裂法) ，基于模 糊等价关系的传递闭包方法，基于模糊图论的最大树方法，动态直接聚类法、人 工神经网络模糊聚类法以及基于数据集的凸分解、动态规划和难以辨识关系等方 法。 模糊聚类理论的发展推动了它在生产实践中的应用。由于模糊聚类的强大功 能，使得这种技术己经在很多的领域获得了成功的应用。而且随着模糊聚类理论 的不断发展和完善，必将发挥更大的作用。 由于模糊聚类与模式识别的有着自然联系，使得它在识别领域首先获得了最 为广泛的应用；其次，在图像处理中经常需要处理无监督的分类问题，因此理所 当然的成为重要的分析工具，图像处理是计算机视觉的重要组成部分，由于人眼 视觉的主观性使图像比较适合用模糊手段处理，同时训练样本图像的缺乏又需要 无监督分析，而模糊聚类正好满足这两方而的要求，因此成为图像处理中一个强 大的研究分析工具。 模糊聚类在图像处理中最为广泛的应用为图像分割，由于图象分割问题可以 等效为象素的无监督分类，因此早在1 9 7 9 年c o l e m a n 和a n d r e w s 就提出用聚类算 法进行图像分割，此后基于二维直方图、塔型结构、小波分析、分形分维等一系 列新技术，人们又相继提出了多种基于模糊聚类的灰度图像分割的新方法，并且 在纹理图像分割、彩色图像分割、序列图像分割、遥感图像分割等方而也获得了 很大的进展。基于模糊聚类的方法在边缘检测、图像增强、图像压缩、曲线拟合 等众多方而的研究同样一也取得了丰硕的成果。 现在数据挖掘技术是当今数据库系统研究和应用领域的热点问题，聚类分析 是数据挖掘中非常重要的研究领域和应用技术之一，由于人们有待处理的问题越 来越多，因此要求数据库处理的数据种类也越来越多，这其中就有含义不明确的 模糊数据，所以将模糊信息处理技术加入到聚类分析中，便可以有助于数据挖掘 技术的发展。 此外，在通讯系统中的信道均衡、矢量量化编码中的码书设计、时间序列的 预测，神经网络的训练、参数估计、医学诊断、气候分类、食品分类、水质分析 等领域中模糊聚类分析也发挥着重大的作用。例如，在对耕作土壤进行分类时， 红壤、黄壤和棕壤之间的界限不是很清晰，那么介于两者之间的土壤归属问题， 用模糊聚类分析来处理更加合理。 各种形式的聚类分析方法以及广阔的应用领域为聚类分析研究提供了宽广的 舞台。同时，在聚类分析中加入模糊理论，可以使现有的聚类分析方法更加符合 复杂的实际情况，模糊聚类分析方法也在各个领域有着更好的应用前景。 2 南京理丁大学耐i 士学位论文模犄| 聚类算法的研究与实现 1 2 模糊数学的研究现状及发展 1 9 6 5 年，模糊理论的创始人，美国加利福尼亚大学伯克利分校的计算机和自 动控制理论专家la z a d e h 教授发表了题为“f u z z ys e t ”的论文，这标志着模糊 信息处理的诞生，并于2 0 世纪6 0 年代在各科学会议上从模糊信息处理观点出发， 阐述了他的理论。这一理论为描述和处理事务的模糊性和系统的不确定性，以及 模拟人所特有的模糊逻辑思维功能，从定性到定量，从而创造了研究模糊性或不 t 确定性问题的理论方法，z a d e h 教授在随后的研究工作中，准确地阐述了模糊性的 含义，制定了刻画模糊性的数学方法即：模糊集合、隶属度、隶属函数等，迄今 已成为了一个较为完整的数学分支了。 目前对模糊数学的研究十分活跃，模糊集合理论进一步丰富了经典数学的理 论系统，为人们处理模糊信息提供了很多好的方法。现在，模糊数学的公理化基 础已经在建立，正接受实践的检验，并进一步得到完善。自从1 9 7 6 年模糊数学传 入我国以来，通过广大模糊数学研究工作者地努力，模糊数学在我国得到了极大 的发展，目前水平已居于世界前列。模糊数学在实际应用中几乎涉及到了国民经 济的各个领域及相关部门，模糊数学在医学、气象、环境、农业、能源、军事、 经济管理和地质勘探等方面都得到了广泛而又成功的应用。 从模糊理论诞生到今天四十年来，模糊理论和技术得到了迅速的发展，在这 个领域国内外许多学者做了大量卓有成效的研究工作，其中有很突破性的研究。 模糊理论与技术的一个突出优点就是能较好地描述和模仿人的思维方式，并能总 结和反映人的体会和经验，对复杂事务和系统可进行模糊度量、模糊识别、模糊 推理、模糊控制与模糊决策。尤其是将模糊理论与人工智能在神经网络和专家系 统等方面相互结合的研究己深入到计算机技术、多媒体技术、自动控制技术以及 信息采集与处理技术等一系列高新技术的开发、研究与利用，为推动了决策科学、 应用科学、管理科学与社会科学的进步作出了极大的贡献，这种学术理论体系不 断完善的额成果正在迅速地转变为生产力，促进了全人类社会物质文明的不断发 展。 i 3 本文的研究对象与工作 1 3 1 研究对象 本文首先研究基于模糊等价关系的聚类分析方法的基本原理，在这个原理基 础上制定聚类分析的步骤。首先是对所研究的对象的数据进行预处理，建立一个 数据矩阵，然后计算对象两两之间的相关程度，得到它们的模糊相似关系，之后 南京理工大学硕士学位论文 模糊蒙类算法的酽究j i 实现 用相应的方法对研究对象进行模糊分类。接着本文介绍了两种模糊聚类分析的两 种算法：传递闭包法和最大树法。 其次是重点分析了模糊聚类分析中基于模糊等价关系的传递闭包法，根据这 种这种方法的缺陷，利用模糊等价矩阵的一些性质和相关的命题，对原有的方法 进行改进。 1 3 2 研究工作 本文主要研究将模糊信息处理技术融入聚类分析中，就是使用模糊聚类分析的 方法来实现聚类问题。 本文通过阐述模糊集合知识，引出模糊数学中一个重要的研究领域，即模糊聚 类分析，介绍模糊聚类分析方法的原理及运算过程，并对模糊聚类分析中两种重 要的方法即传递闭包法和最大树法进行实验，运用实例得出分类结果，并通过结 果的对比进行分析给出结论。 之后进一步阐述模糊聚类分析中的等价传递闭包法的特点，指出这个方法的 不足之处，给出针对传递闭包法这个不足之处的改进算法，即近似最优等价矩阵 法，并分析这个算法特点和适用领域。 最后使用v b 语言实现一个模糊聚类分析程序。 1 4 本文的内容安排 本文的内容一共分六章。 第一章为“绪论”，介绍模糊聚类分析的背景意义、研究现状和发展情况。本 文的研究对象与工作概述及内容安排。 第二章为“模糊集合”，先介绍经典集合的概念，后引出模糊集合的概念，从 这两者的性质出发，比较它们的共同点和区别，阐述模糊集合的基本运算方法， 给出分解定理，它是联系模糊集合与经典集合的桥梁，为以后的章节作铺垫。 第三章为“模糊聚类分析及算法”，说明模糊聚类分析是如何通过模糊矩阵的 变化来实现的，以及模糊聚类分析的步骤和能实现分类的各种方法，最后对其中 的两种方法的进行试验，并分析结果。 第四章为“模糊聚类算法的研究”，基于上一章介绍的等价传递闭包法，通过 理论铺垫，说明这种方法的不足之处，并根据模糊等价矩阵的特性，对等价传递 闭包法改进为近似最优矩阵法。 第五章为“模糊聚类分析算法的实现”，说明实现的模糊聚类分析程序的结构、 运行过程，并通过实验结果加以验证。 4 墼理工大学硕士学位论文模糊聚类算法的研究与实现 本文最后的结束语是对本文所做的工作进行了简要的总结。 南京理工大学硕t 学位论文模帮聚类算法的研究实现 2 模糊集合 2 1 经典集合 2 1 1 集合的基本概念 集合是现代数学的基本概念之一正如在几何学中很难给点和直线给出确切的 定义一样，在集合论中也很难给集合下一个确切的定义，但为了明确起见，我们 还是奖集合定义如下。 我们称具有共同属性的一些事物的全体为“集合”，而“集合”中的每一个事 物称为是该“集合”的“元素”。本文为了便于区别于模糊集合，我们称之为“经 典集合”，“集合”常用a 、b 、x 、y 、z 等大写英文字母表示，“元素”则常用 a 、b 、c 、x 、y 、z 等小写英文字母表示，a 属于a ，记为a a ，a 不属于a ， 记为a g a 。 由以上定义可知，集合是由元素组成，它可以理解存在于世上的任何客观事 务，无论它们是具体的还是抽象的。事实上，集合与一个概念在人脑中的形成密 切相关。一个概念的形成大致需要包含两个方面：方面是从在条件把握各个有 关因素对这个概念所作的规定，即这个概念的内在涵义，称之为概念的“内涵”； 另外一方面就是这个概念所包含的内容，换句话说就是符合此概念的事物全体， 我们称之为概念的“外延”。“1 内涵和外延是描述概念的两个方面，它们是相辅相 成的。 简而言之，外延实际上是表现概念的一个集合。 集合的元素可以任意多，并且一些完全毫不相关的事物都可以是同一集合中 的元素，比如：s = 3 ，计算机，苹果，物理，人民 ，但是实际上这种集合对我 们处理问题一般来说是没有什么价值的，在实际应用中，我们讨论问题时总是限 制在一定的范围之内进行的，所以在讨论集合前常常需要首先给出我们研究的范 围，称之为“论域”。论域本身是一种特殊的集合，它的选取一般不是唯一的，可 以根据具体的要求来确定。 下面是几种常用的集合： 当一个集合中的元素数目为有限时，称之为。有限集合”，若一个集合中 的元素数目为无限时，称之为“无限集合”。 设s 是无限集合，若s 与自然数集合n 之间一一对应的关系，则称s 为“可 列集合”，反之则称其为“不可列集合”。 不含任何元素的集合称为“空集合”，简称为“空集”，记为中；包含论域 6 南京理工大学妒士学位论文模糊聚类算法的研究与实现 中所有元素的集合称为“全集”，记为u 。 集合的表示法主要有两种“： 枚举法 即对于元素不多的集合，可以将它的所有的元素都一一列出，比如“大于2 小于8 的质数集合”= 2 ，3 ，5 ，7 。 使用这种方法时，常常还能以某种明显的顺序规律，仅列出一部分元素，而 将集合中的其他一些元素隐含表示，从而能够表示出部分元素数目无限的集合。 描述法 描述法通过形式描述的手段表示集合，表示集合最常用的方法：设集合s 的 元素具有属性p ，则s = x i p ( x ) ) ，其中竖线左边为元素符号，而右边是集合元 素所具有的性质。 描述法适合用于那些很难一一列出集合元素的集合，并且其元素之间也不存 在任何顺序规律性。 集合的基本概念 对于任意的两个集合a 、b ，若集合a 的每一个元素都是集合b 的元素，则 称a 是b 的“子集”。记为a c b 或b d a ；若b 中存在不属于a 的元素，则称a 是 b 的“真子集”，记为a r = b 且b 3 a 。 两集合“相等”，当且仅当a b 且b 虿a 。 论域u 为包含任意集合a ，即a _ u 。 对于任意集合a ，恒有o a 。 对于一个集合a ，由其所有子集作为元素构成的集合称为a 的“幂集”，记 为： p ( a ) = f x i x c a 设x 、y 为两个集合，则x 和y 的笛卡尔积( 又称为“直积”) 定义为 x x y = ( x ，y ) x x ，y y 。 2 1 2 集合的运算及其性质 与实数运算类似，集合间也定义了一些基本运算“】。 定义2 1 ：设a 、b 为论域u 中的任意两个集合，则定义： a 与b 的“并集”：a u b = f x i x a 或x b ； a 与b 的“交集”：a n b = x l x e a 且x b ： a 与b 的“差集”：a b = f x x a 且x 薯b ； a 的“补集”：a = u a = x i x 芒e a 。 7 南京理工大学硕士学位论文 模糊聚类算法的铲究与实现 并集和交集运算可以推广至多个，乃至无穷多个集合问的运算。 在模糊集合论中，在同“与”、“或”运算符号不混淆的情况下，习惯使用符 号v 表示“取最大值”，使用符号 表示“取最小值”，即： x v y = m a x ( x ，y ) ， v i x j 2 n n x ( 。l ，x 2 xh ) ； x a y = m i n ( x ，y ) ， h 金x 1 2r a i n ( x 1 ，x2 ，x d ) 。 集合运算的基本性质“3 设a 、b 和c 为论域u 中的任意三个集合， ( 1 ) 交换律：a u b = b u a ：a n b = b n a ； ( 2 ) 幂等律：a u a = a ，a n a - - - - - a ： ( 3 ) 结合律：( a n b ) n c = a o ( b n o ) ， ( a u b ) u c = a u ( b u c ) ： ( 4 ) 分配律：a u ( b n c ) = ( a u b ) n ( a u c ) ， a n ( b u c ) = ( a n b ) u ( a n c ) ： ( 5 ) 吸收律：a u ( a n b ) - - a ， a n ( a u b ) - - - - a ： ( 6 ) 对偶律：( a u b ) - - - - a n b ， ( a n b ) = a u b ： ( 7 ) 互补律：a u a = u ：a n a - - - - - 中； ( 8 ) 还原律：( a ) = a ； ( 9 ) 同一律：a u 中= a ，a n u = a ： a 零律：a u u = u ，a n 中= o ： q d 传递律：若a b 及b c c ，则a c 。 2 1 3 二元关系 1 二元关系 关系是一个基本概念，如生活中的“师生关系”、“父子关系”等，数学上有 “大于关系”、“小于关系”等。而序对又可以表达两个对象之间的关系，于是要 引入下面的定义“1 。 定义2 2 ：设x ，y ef ( u ) ，x y 的子集r 称为从x 到y 的二元关系，特别 是，当x = y 时，称之为x 上的二元关系，以后把二元关系简称为关系。 南京理工大学硕士学位论文模糊聚类算法的研究与实现 若( x ，y ) r ，则称x 与y 有关系，记为x r y ；若( x ，y ) 薯r ，则称x 与y 没有关系，记为x i y 。 设r 是x 上的关系。 ( i ) 若对于任意的x x ，有x r x ，则称r 是自反的。 ( 2 ) 对于任意的x ，y e x ，若x r y = ： y r x ，则称r 是对称的。 ( 3 ) 对于任意的x ，y ，z x ，若x r y ，y r z ：j x r z ，则称r 是传递的。 2 关系的矩阵表示法 关系的表示方法很多，除了用直积的子集表示外，对于有限论域的情形，用 矩阵表示在运算上比较方便。 定义2 3 ：设两个有限集x = x l ，x2 ，x3 ，x 。) ，y = ( y l ，y 2 ，y3 ， r y ly 2 y h x 1r l l r 1 2r l n x 2 r 2 l r 2 2 r 2 月 x wr _ 1r m 2r m 表2 1 3 1 关系矩阵表示法 其中当x ，ry 时，则r p = 1 ； 当x 。页yj 时，则re = o 。 称为m x n 矩阵r = ( 。口) 。为r 的关系矩阵，记为 r = lr t 2 ，2 lr m r ir 2 由定义可知，关系矩阵中的元素或是0 或是1 。在数学上把各个只是0 或1 组 成的矩阵称为布尔矩阵，因此任何关系矩阵都是布尔矩阵。 3 关系的合成 若r ，为兄妹关系，r ，为母子关系，即x 与y 有兄妹关系：x r 。y ；y 与z 有母 子关系：y r2 z ，那么x 与y 有舅甥关系，这就是关系r 。与r ：的合成，记为r 。r 2 。 定义2 4 “1 ：设r 。是从x 到y 的关系，r ：是从y 到z 的关系，则称r i 。r 2 为 关系r ，与r ：的合成，表示为 r lor 2 = ( x ，z ) i3 y e y ，使( x ，y ) r l ，( y ，z ) r 2 ) 。 4 等价关系和划分 9 南京理工大学硕士学位论文模脚聚类算法的研究与实现 为了将集合的元素进行分类，下面要引进一个重要的关系，即等价关系。 定义2 5 ：设集合x 上的二元关系r 具有自反性、对称性和传递性，则称r 使 x 上的等价关系，此时x r y 又称为x 等价于y ，记为x y 。 集合x 上等价关系的重要性在于，它可以将集合x 分成适当的子集，实际上 就是将集合x 进行分类，为此引入下面的定义。 定义2 6 m ：设x 是非空集，x ，是x 的非空子集，若u x 。= x ，且x ，nx ，= 由 ( i j ) ，则称集合族 x 。 为x 的一个划分，称集x 。为这个划分的一个类， 以万表示为 万= x 。ix 。c x ，且对任意的x e x 恰好属于同一个x 。 。 划分万的每个元素称为一个块，也称为划分的一个类。 当划分的块数为有限时，划分万可以表示为 万= x ，x 2 ，x ，n 为块数。 显然，对有限集而言，它的划分块数一定也是有限的。 集合x 上的等价关系与x 的划分有着密切的联系，为了说明这种联系，要引 进等价类的概念和一个结论。 定义2 7 “3 ：设r 是集合x 上的等价关系，对于x 中的每个元素x ，称与x 等 价的元素所组成的集合为由x 生成的等价类，记为 x 。，即 x 月= yly e x ，y x 。 显然，等价类 x 。满足： ( 1 ) x = u x 。； ( 2 ) x r z rj x rn z r = 中。 定理2 1 “1 ：集合x 上的任一等价关系可以确定x 的一个划分， 来，集合x 的任一划分( 即分类) 可以确定x 上的一个等价关系。 5 相似关系 与等价关系一样，相似关系的应用也非常的广泛。 定义2 8 “1 ：设s 是集合x 上的关系，若s 是自反的、对称的， 关系。 即分类；反过 则称s 是相似 定义2 9 “1 ：设s 是集合x 上的相似关系，若c c x ，那么对于任意的x ，y e c ， 有x s y ，则称c 是由相似关系s 产生的相似类，记为i x 。，即 i x ) s = = yix ，y e c ，x s y 。 显然满足：x = t j i x s ，但是因为相似关系不具有传递性，所以当i x 。 z 。时， x s n z s o l o 南京理工大学硕士学位论文模糊聚类算法的酽究与实现 2 2 模糊集合 一模糊集合的概念 上一节曾讨论过一个经典集合的“内涵”和“外延”都必须是明确的，所以 对论域中的任何元素，或者属于某一集合，或者不属于这个集合，两者必居其一 且仅居其一。然而在现实世界中，有许多概念并没有明确的“外延”，比如说“天 气好”、“水温很低”、“个子很高”等都是模糊的概念。这样就使得经典集合论对 于这样的概念显得力不从心了，因为模糊概念很难简单地用“属于”或“不属于” 来表示，而只能通过属于的程度来描述。换句话说，就是论域中的元素符合某一 概念的程度不能仅仅用0 或l 来表示，而需要借助于介于0 到1 之间的实数来表 示。 1 定义2 1 0 。：论域x 上的“模糊集合”a 定义为： a = ( x ，a ( x ) ) lx x 或者a = ( x ，4 ( x ) ) ix x 其中a ( x ) 或者。( x ) 称为“隶属函数”，它满足： a ：x m ，这里m 称为“隶属空间”，最常见的隶属空间为区间( o ，1 ) 隶属函数a ( x ) 用于刻画元素x 对模糊集合a 的隶属程度，即“隶属变”。所 以模糊集合a 的每个元素( x ，a ( x ) ) 都能明确地表现出x 的隶属等级。a ( x ) 的值越大，x 的隶属程度就越高。比如，a ( x ) = l 时，说明x 完全属于a ；而a ( x ) = o 时，说明x 不属于a ，而a ( x ) 值介于0 和1 之间时，说明隶属于a 的 程度也介于“属于”与“不属于”之间是模糊的。与经典集合类似，在模糊集合 的表示中，对于隶属度为0 的元素可以不列出。 由定义可以看出，模糊集合a 是由隶属函数。( x ) 唯一确定的，以后可以把 模糊集合a 与隶属函数( x ) 看成是等同的，还要指出的是，隶属程度的思想是 模糊数学的基本思想。 当。( x ) 的值域变为集合 0 ，1 时，模糊集合a 就是经典集合，可见经典集 合是模糊集合的特殊情形。 x 上的所有模糊集合组成的集合称为x 的模糊幂集，记为r ( x ) 。 二模糊集合的表示法 1 序偶表示法 序偶表示法又称为向量表示法，它的形式为： a - - - ( x 1 ，a ( x 1 ) ) ，( x2 ，a ( x2 ) ) ，( x 。，a ( x 。) ) 2 z a d e h 表示法 ( 1 ) 符号法：这种表示法适合用于论域为有限集合或可列集合的模糊集合的 描述。设论域为x = x 。，x ：，x ，x 。 ，a 为x 上的一个模糊集合，则a 可以 1 t 南京理工大学硕士学位论文模糊聚类算法的酽究实现 记为； a ：争兰盟 智虬 这里的仅仅是借用类数学符号和，并不表示分式求累加和运算，而只是 描述a 中有哪些元素，以及各个元素的隶属度值。当以上假设中的n 改为无穷大 时，便可以描述一个可列论域中的模糊集合了。 ( 2 ) ，符号法：这种表示法适合用于任何种类的论域，特别是论域为无限集合 的模糊集合的描述。设论域为x = x ，x2 ，x ，x 。 ，a 为x 上的一个模糊集 合，则a 可以记为： a ：f 业 0 x x 与符号法相同，这里的积分符号，仅仅是一种表示，而并不意味着是进行积分 运算。 3 隶属函数法 当论域为实数集合中的某个区间时，有时候将模糊集合的隶属函数用解析表 达式表示比较方便。 三模糊集的运算及其性质 1 定义 现将经典集合的运算推广到模糊集。由于模糊集中没有点和集之间的绝对属 于关系，所以其运算的定义只能以隶属函数间的关系来确定。 定义2 1 1 9 3 ：设a ，b 1 - ( u ) ，则有 包含：对于任意的x u ，有a ( x ) b ( x ) a _ b ； 相等：对于任意的x u ，a ( x ) = b ( x ) a = b 。 定义2 1 2 嗍：设a ，b r ( u ) ，定义 并：对于任意的x u ，a u b 的隶属函数( x ) 为 ( a u b ) ( x ) = a ( x ) v b ( x ) ： 交：对于任意的x u ，a n b 的隶属函数u ( x ) 为 ( a n b ) ( x ) = a ( x ) 八b ( x ) ： 补：对于任意的x u ，a 的隶属函数“( x ) 为 a = l a ( x ) 。 2 模糊集运算的性质 ( 1 ) 交换律：a u b = b u a ；a o b = b a a ； ( 2 ) 幂等律：a u a = a ，a o a = a ： ( 3 ) 结合律：( a n b ) o c = a n ( b n o ， 南京理工大学硕士学位论文模糊聚类算法的磅【究j 实现 ( 4 ) 分配律： ( 5 ) 吸收律： ( 6 ) 对偶律； ( a u b ) u c = a u ( b u c ) ： a u ( b n c ) = ( a u b ) n ( a u c ) 。 a n ( b u c ) = ( a n b ) u ( a n c ) ： a u ( a n b ) = a ， a n ( a u b ) = a ： ( a u b ) = a n b ， ( a n b ) = a u b ： ( 7 ) 还原律：( a ) = a ： ( 8 ) 同一律：a uo = a ，a n u = a ； ( 9 ) 零律：a u u = u ，a n 中= o ： 值得注意的是，与经典集合交、并和补运算性质不同的是，在这垦互补律不再成 立，这一事实表明模糊集合不再具有“非此即彼”的特点，这正是模糊性带来的 特征。 2 3 模糊集的分解定理 2 3 1 一截集 分解定理是联系经典集合与模糊集合的桥梁而模糊集的截集正是构架这个桥 梁较为理想的工具，截集的思想以下面的例子来说明。 假设某医生有五个病人x i 、x2 、x 3 、x 、x 5 ，他们的体温分别是3 8 9 摄氏 度、3 7 0 摄氏度、3 7 2 摄氏度、3 9 2 摄氏度、3 8 1 摄氏度。则在统计时可以有 记录： 3 7 摄氏度以上的有五人x i 、。2 、x3 、x4 、x5 3 8 摄氏度以上的有三人x 1 、x4 、x ， 3 9 摄氏度以上的有一人x 。 若考虑到有多少发烧的病人时，医生就可以根据不同的经验而得出不同的结论。 例如，若认为3 7 摄氏度以上就是发烧，则有四人发烧；若认为3 8 摄氏度以上就 是发烧，则有两人发烧。事实上，“发烧”属于模糊概念，所以采用模糊数学来描 述更为合适。例如，若根据医生的经验可以将各个体温段认为是“发烧”的隶属 函数表示如下： 3 9 摄氏度取隶属度= l 3 8 5 3 9 摄氏度取隶属度= o 9 3 8 3 8 5 摄氏度取隶属受= 0 7 3 7 3 8 摄氏度取隶属度= 0 4 1 3 南京理工大学硕士学位论文模糊聚类算法的研究与实现 3 7 摄氏度 取隶属度= 0 则将前面的“发烧病人”表示为模糊集合 a = ( x i ，0 9 ) ，( 22 ，o ) ，( x3 ，0 4 ) ，( x4 ，1 ) ，( x5 ，0 7 ) 这样，可以对发烧的病人进行一些分类，例如，可以将隶属函数0 9 的病人分出 作为“发高烧”进行特别护理：a 。9 = x i ，x 。 ，一般地我们用a 。表示a ( x ) 的元素x 组成的集合。 定义2 1 3 ：设a 为论域u 中的模糊集合，x o ，1 ，定义a 的“ 截集” 为集合 a ，= xia ( x ) 实数凡称为“阈值”又称为“置信水平”。特别是，当集合a 。= xia ( x ) ) 称为a 的“ 强截集”。 定理2 2 ：设a ，b 为模糊集合，则下面的等式成立 ( a u b ) = a u b i ( a o b ) i = a a b i 定理2 3 ：令a 为模糊集合，a 、9 o ，1 且a 8 ，则a 。a 口。 这个定理从理论上回答了“ 值越小，a ，包含的元素越多”的问题。这种让 由大到小取值，而a ，所含的元素由少到多的过程，实际上是一种分类过程。 值取得越大，a 。包含的元素越少，分出的类就越多，分类就越细；反之，x 值取 越小，a ，包含的元素越多，分出的类就越少，分类就越粗，这是以后模糊聚类分 析的基础。 2 3 2 分解定理 模糊集合a 的凡截集是经典集合，所以我们自然会考虑能否用经典集合来表 示模糊集合，那么模糊集合的分解定理就可以解决这个问题。 为了叙述分解定理，首先要介绍一种新运算，即：数凡 0 ，1 与模糊集合a 的乘积 a 。 1 数 与模糊集合a 的乘积 定义3 1 4 “1 ：设入 0 ，1 ，a f ( u ) ，规定 a f ( u ) ，其隶属函数 为 ( a ) ( x ) = 八a ( x ) ， 并称 为数九与使糊集合a 的乘积。可见 a 是一个模糊集合。 特别地，若a 是u 的一个经典集合，则入a 表示由入和a 所确定的一个模糊集 合，其隶属函数为 1 4 南京理工大学顿十学位论文接榔聚类算法的铲究与实现 ( a ) ( x ) = a 舭( x ) = x ，当x e a 时； ( a ) ( x ) = x a z _ ( x ) = 0 ，当x 叠a 时。 这个模糊集 a 称为入与a 的“积”。由此可以看出，当x a 时，x 对于 a 的隶 属度等于九。 数 与模糊集合a 的乘积运算的性质： ( 1 ) l m r ( r 础 隧 旷 跏 性性称递对传 3仉 -。l i l rx 。仅 础 忙 根 设 r ：如即例 南京理工大学硕士学位论文模糊聚类算法豹研究与实现 又因为 n 。n = 0 ：，o i 3 。 0 1 ，墨3 = 0 ：。o i 3 = n 所以r = l0 1 3o i 3 l 是模糊等价矩阵。 模糊等价矩阵的性质： 定理3 4 m ：r 是模糊等价矩阵营任意的x 【o ，1 ，r ，是等价的布尔矩阵。 此定理的重要性在于将模糊等价矩阵转化为等价的模糊布尔矩阵有限论域 上的普通等价关系，而等价关系是可以分类的。因此，当入在 0 ，1 上变动时， 由r ，得到不同的分类。这些分类之间的联系则由下面一个定理给出。 定理3 5 ：设r | l 。是模糊等价矩阵，则对入，i l 0 ，1 。且九 蚌， r 。所决定的分类中的一个类是r 4 决定的分类中的某个类的子类。 证：因为对任意的九，“ o ，1 ， r 妒= 1 。 这就是说，如果i ，j 按r 。分在一类，则按r 。也必分在一类，即r ，所决定的 分类中的每个类是r ，决定的分类中的某个类的子类。 定理3 5 表明，当 0 ，否则，也要作适当的变换。 2 距离法 ( 1 ) 绝对值倒数法 r d 2 l ， m 。2 瓦j 1 2 j ； i j ， ( 3 3 1 - l o ) 其中m 适当选取，使得0 r 。1 。 ( 2 ) 绝对值指数法 。：。砷f - - 艺k h | 1 0 直接用距离法时，总是令 。口2 1 - - c d ( xj ，1 ，) ， 其中c 为适当选取的参数，它使得0 r 。1 。 经常采用的距离有： 海明距离 d ( x l ，xj ) = k 一l 此时相似系数r 。与绝对值减数法一致。 欧几里德距离 n 一 d ( x 。，x ) = 1 f ( 靠- - x 且) 2 切比雪夫距离 d ( x ，x ，) 2 二k 一靠i 。 3 主观评定法 主观评定法就是请专家或者是有实际经验者直接对x 。与x ，的相似程度评分， 作为r 。的值。 三聚类 1 基于模糊等价矩阵聚类方法 ( 1 ) 传递闭包法 因为模糊等价矩阵能对论域进行等价的划分，这就能满足聚类分析的需要。 然而，在通常的情况下，由标定过程构造出的模糊关系仅仅能满足自反性和对称 性，而不满足传递性，所以生成的只是一个模糊相似矩阵r ，而不是模糊等价矩阵， 南京理工大学硕七学位论文模糊聚粪算往的研究 j 实现 所以为了进行分类，还要在这个模糊相似矩阵的基础之上去生成一个模糊等价矩 阵，最自然的方法就是去求该模糊相似矩阵r 的传递闭包t ( r ) ，这样便可以得到 一个模糊等价矩阵。当生成模糊等价矩阵后，取某一实数 0 ，1 ，计算出t ( r ) ( 布尔矩阵) p 便得到论域x 的一个等价划分：当p 。= 1 时说明x 。与x ，在同 一个等价类中；否则他们两个不在同一个等价类中。如果依次将 值从l 变小至0 时，便可以得到x 的一个逐渐由细变粗的动态分类。在这个方法中，由于模糊等