（计算机软件与理论专业论文）模糊c均值算法的研究.pdf

辽j 叫币范人学硕十学位论文 摘要 随着数据库技术的不断发展及数据库管理系统的广泛应用使得各组织机构积累了 海量数据，为了从中提取有用信息，更好地利用这些数据资源，人们提出了数据挖掘技 术。数据挖掘技术将传统的数据分析方法与处理大量数据的复杂算法相结合，是目前信 息领域和数据库技术的前沿研究课题。 聚类分析技术是数据挖掘的主要方法，它将数据划分成有意义或有用的组( 簇) ， 在众多的聚类分析算法中，模糊聚类算法是当前研究的热点。本文对其中最经典的模糊 伊均值( f c m ) 算法进行了深入研究，并对它加以改进和优化，实验验证了方法的叮行 性和有效性。 本文系统分析了f c m 算法和马氏距离的基本原理，从而利用马氏距离的优点来弥补 f c m 算法中存在的缺陷，其次利用优化的k p c a 进行特征提取，本文从三个方面对f c m 算法进行了改进。 首先，经典的模糊r 均值( f c m ) 算法是基于欧氏距离的，它只适用于球型结构的 聚类，且在处理属性高相关的数据集时，分错率增加。针对这个问题，提出了一种新的 聚类算法( f c m - m ) ，它将马氏距离替代模糊矿均值中的欧氏距离，并在目标函数r f l 引 进一4 个协方差矩阵的调节因子，利用马氏距离的优点，有效地解决了f c m 算法中的缺陷， 并利用特征值，特征矢量及伪逆运算来解决马氏距离中遇到的奇异问题。 其次，经典的模糊r 均值算法认为样本矢量各特征对聚类结果贡献均匀，没有考虑 不同的属性特征对模式分类的不同影响，且在处理属性高相关的数据集时，该算法分错 率增加。针对这些问题，提出了一种基于马氏距离特征加权的模糊聚类算法，利用自适 应马氏距离的优点对特征加权处理，从而对高属性相关的数据集进行更有效的分类。 最后，利用核函数主元分析( k p c a ) 方法对大样本，高维数据进行特征提取预处理， 并结合文化算法( c a ) 选择最优或接近最优的核函数，将其用于模糊c 嘲值( f c m ) 聚 类中，不但有效地提取了样本的非线性信息，而且使样本维数得剑约简。 利用m a t l a b 语言实现上述方法，并进行了u c i 数据集聚类和图像分割两组实验， 从实验结果看，均达到预期效果。 关键词：模糊理论；模糊产均值；马氏距离；文化算法 g1 v习i j，0jj 模糊伊均值算法的研究 t h er e s e a r c ho nf u z z yc m e a n sa l g o r i t h m a b s t r a c t w i t ht h ed e v e l o p m e n to fd a t a b a s et e c h n o l o g ya n dd a t a b a s em a n a g e m e n ts y s t e mu s e d w i d e l y ，m a n yh u g ed a t a i sa c c u m u l a t e di n o r g a n i z a t i o n s i no r d e r t oe x t r a c tu s e f u l i n f o r m a t i o na n dm a k eb e t t e ru s eo ft h e s er e s o u r c e s ，d a t am i n i n gt e c h n o l o g yi sp r o p o s e d d a t a m i n i n gc o m b i n e st h em e t h o do ft r a d i t i o n a ld a t aa n a l y s i sw i t h t h ec o m p l e xa l g o r i t h mt o p r o c e s sm a s sd a t a ，a n di sas u p e r i o ra r e ai nt h ei n f o r m a t i o na n dd a t a b a s et e c h n o l o g y a so n eo ft h em a i nm e t h o d so fd a t am i n i n g ，c l u s t e r i n ga n a l y s i sp a r t i t i o n sd a t as e ti n t o t h em e a n i n g f u lg r o u p so rc l u s t e r s i nm a n yo ft h ec l u s t e ra n a l y s i sa l g o r i t h m ，f u z z yc l u s t e r i n g a l g o r i t h mi st h ec u r r e n tr e s e a r c hh o t s p o t t h i sp a p e rr e s e a r c h e so nt h em o s tc l a s s i c a lf u z z y c - m e a n sa l g o r i t h m ( f c m ) ，a n dp r o p o s e sa ni m p r o v e da l g o r i t h mb a s e do nt h ed i s a d v a n t a g eo f f c m e x p e r i m e n t a lr e s u l ti l l u s t r a t e si t se f f e c t i v e n e s sa n df e a s i b i l i t y t h i sp a p e rs y s t e m a t i c a l l ya n a l y z e df c ma l g o r i t h ma n db a s i cp r i n c i p l eo fm a h a l a n o b i s d i s t a n c e ，u s i n gt h ea d v a n t a g e so fm a h a l a n o b i sd i s t a n c et or e m e d yt h ed e f e c t si nt h ef c m a l g o r i t h m ，a n du s i n go p t i m i z e dk p c a t oe x t r a c tf e a t u r e s w ei m p r o v e df c ma l g o r i t h mf r o m t h et h i r da s p e c t s f i r s t ，f c mi sb a s e do ne u c l i d e a nd i s t a n c ef u n c t i o n ，w h i c hc a no n l yb eu s e dt od e t e c t s p h e r i c a ls t r u c t u r a lc l u s t e r s 。w h e nf c mp r o c e s s e ss o m ed a t a s e to fh i g hc o r r e l a t i o n ，e r r o r p r o b a b i l i t yw i l lb ei n c r e a s e d f o c u s i n go na b o v et w op r o b l e m s ，t h i sp a p e rp r o p o s e sa n i m p r o v e dn e wa l g o r i t h mc a l l e df u z z yc - m e a n sb a s e do nm a h a l a n o b i sd i s t a n c ef u n c t i o n ( f c m - m ) ，a n da d dar e g u l a t i n gf a c t o ro fc o v a r i a n c em a t r i xt oe a c hc l a s si no b je c t i v ef u n c t i o n u s i n gm a h a l a n o b i sd i s t a n c e ，f c m ma l g o r i t h me f f e c t i v e l ys o l v e st h es h o r t c o m i n go ff c m a l g o r i t h m t h e r ea r ee f f i c i e n tm e t h o d st os o l v es i n g u l a rv a l u e sp r o b l e mf o rf i n d i n ge i g e n _ v a l u ea n de i g e n v e c t o r so fas y m m e t r i cm a t r i xo rc o m p u t i n gp s e u d o i n v e i r t i o ni n v o l v e di n f i n d i n gt h em a h a l a n o b i sd i s t a n c e s e c o n d ，f c mr e g a r d st h es a m p l ef e a t u r e sh a v et h es a m ec o n t r i b u t et ot h ec l u s t e rr e s u l t ； n ot h i n k i n go v e rt h ed i f f e r e n tf e a t u r e sm a yh a v et h ed i f f e r e n ti m p a c tt ot h ec l u s t e rr e s u l t w h e nf c mp r o c e s s e ss o m ed a t a s e to fh i g hc o r r e l a t i o n ，e r r o rp r o b a b i l i t yw i l lb ei n c r e a s e d f o c u s i n go na b o v et w op r o b l e m s ，t h i sp a p e rp r o p o s e sa ni m p r o v e dn e wf u z z yc l u s t e r i n g a l g o r i t h m b a s e do nf e a t u r ew e i g h t e dm a h a l a n o b i sd i s t a n c e f u n c t i o n u s i n ga d a p t i v e m a h a l a n o b i sd i s t a n c et ow e i g h tt h ef e a t u r e ，t h en e wa l g o r i t h mc a ne f f e c t i v e l yc l u s t e rt ot h e d a t a s e t so fh i g hc o r r e l a t i o n ih：，口澎 辽j 叫币范大学硕十学位论文 f i n a l l y ，k e r n e lp c am e t h o de x t r a c t sf e a t u r ef r o ml a r g es a m p l e sa n dh i g hd i m e n s i o nd a t a s e t s ，c o m b i n i n gc u l t u r a la l g o r i t h m s ( c a ) t os e l e c to p t i m i z e dk e m e lf u n c t i o no rn e a r o p t i m i z e dk e r n e lf u n c t i o n f c mb a s e do nt h em e t h o dn o to n l ye f f e c t i v e l ye x t r a c t st h e n o n l i n e a ri n f o r m a t i o nf r o mt h es a m p l e sb u ta l s or e d u c e sd i m e n s i o n t h ep a p e rw i l la c c o m p l i s ht h ea b o v e m e n t i o n e da l g o r i t h m sb ym a t l a b e x p e r i m e n t a l r e s u l t so fd a t ac l u s t e r i n go fu c ia n di m a g es e g m e n t a t i o ni l l u s t r a t et h ee x p e c t e de f f e c t k e yw o r d s ：f u z z yt h e o r y ；f u z z yc - m e a n s ；m a h a l a n o b i sd i s t a n c e s ；c u l t u r a la 1 9 0 r i t h m s 模糊r 均值算法的研究 目录 摘要g i a b s t r a c t ii 第一章绪论1 1 1 本文研究的背景。1 1 2 国内外研究现状及成果1 1 2 1 数据挖掘技术的发展l 1 2 2 模糊聚类理论的发展2 1 2 3 马氏距离研究热点2 1 3 论文主要内容及组织结构3 第二章模糊r 均值算法及分析4 2 1 模糊理论基础4 2 1 1 模糊理论的主要概念4 2 1 2 模糊关系5 2 2 聚类分析理论6 2 2 1 聚类分析的基本概念7 2 2 2 聚类分析算法8 2 3 模糊矿- 均值算法9 2 3 1 模糊旷均值算法分析9 2 3 2 模糊旷均值聚类算法的研究现状1 1 2 3 3 模糊c 一均值算法存在的问题l1 2 4 本章小结15 第三章马氏距离基本原理和处理方法1 6 3 1 马氏距离方法基本原理- 16 3 2 马氏距离中奇异问题的解决方法1 7 3 3 马氏距离的应用1 8 3 3 1 马氏距离在模式识别中的应用18 3 3 2 马氏距离在其他领域的应用1 8 3 4 本章小结1 9 第四章马氏距离在模糊聚类中的应用2 0 4 1 基于马氏距离的f c m 算法( f c m - m ) 2 0 4 1 1 新算法提出2 0 辽。了叫币范人学硕十学位论文 4 1 2 实验结果及分析2 1 4 2 基于马氏距离特征加权的模糊距离新算法( m f - f c m ) 2 6 4 2 1 马氏距离特征加权新方法2 7 4 2 2 实验结果及分析2 8 4 3 本章小结2 9 第五章基于优化k p c a 特征提取的f c m 算法3 0 5 1k p c a 原理及其优化3 0 5 1 1k p c a 原理3 0 5 1 2 文化算法原理3 2 5 2 基于优化k p c a 的学习算法( c a k p c a ) 3 2 5 3 基于c a - k p c a 的f c m 算法3 3 5 。3 1 算法的提出：3 r 3 5 3 2 仿真实验：粥 5 3 3 实验分析：3 4 5 4 本章小结3 4 结论3 5 参考文献3 7 攻读硕士学位期间发表的学术论文情况4 0 翌i 【谢4l v 模糊r 均值算法的研究 第一章绪论 1 1 本文研究的背景 数据收集和数据存储技术的快速进步使得各组织机构积累了海量数据，因此提取有 用的信息已经成为现代科技发展的巨大挑战。通常，由于数据量太大，无法使用传统的 数据分析工具和技术处理它们，有时，即使数据集相对较小，由于数据本身的非传统特 点，也不能使用传统的方法进行处理。在这种情况下，人们迫切需要一种智能并且高效 地将待处理数据转化为有用的信息和知识的方法，从而达到为决策服务的目的。数据挖 掘就是为顺应这种需要而产生并发展起来的数据处理技术。 、 数据挖掘( d a t am i n i n g ) 是在大型数据存储库中，自动地发觉有用信息的过程。 数据挖掘技术用来探查大型数据库，发现先前未知的有用模式。此外，数据挖掘还具有 预测未来观测结果的能力 1 。数据挖掘综合了如统计学、人工智能、模式识别和机器 学习、数据库技术等各领域的思想，属于深层次的数据分析方法。 聚类技术是搜索一个有限的种类集合或簇集合并且进行识别，进而描述数据的。种 数据挖掘技术。作为数据挖掘的一个重要功能，聚类分析可以获得数据的分布情况，从 而观察每个类的特点，集中对某些特定的类做进一步的分析。此外，聚类分析也可以作 为其它算法( 如关联分析和分类) 的预处理步骤，这些算法再在生成的类上进行处腮，这 样可以大大提高这些算法的执行效率，因此聚类分析已经成为数据挖掘领域中一个非常 活跃的研究课题，目前已经开发了许多有效的聚类算法，新的算法还住不断地 j 现 2 ，3 ，4 。 基于目标函数的聚类方法是聚类算法中最受欢迎的，并得到了广泛的戍用。1 9 7 4 年， d u n n 和b e z d e k 等人在模糊集合论的理论基础上，对传统的炉均值算法加以改进，提出 了基于目标函数的划分型模糊聚类方法，其代表算法是模糊伊均值算法( f u z z y c - m e a n sa l g o r i t h m ，f c m ) 5 ，6 ，也就是把聚类归结成一个带约束的非线性规则问题， 通过优化求解获得数据集的模糊划分和聚类。本文对f c m 进行了深入地研究，并针对其 算法存在的不足提出了改进，实验结果证明了方法的有效性。 1 2 国内外研究现状及成果 1 2 1 数据挖掘技术的发展 数据挖掘的诞生可以追溯到2 0 世纪8 0 年代，到目前为止，由美国人工智能协会主 办的k d d 国际研讨会已经召开了8 次，其规模已经由最初的专题讨论会演变成闻际学术 大会，其研究的重点也逐渐从发现方法过渡到系统应用，注重多种发现策略和技术的集 辽宁师范大学硕十学位论文 成，以及多种学科之间的相互渗透。国际有影响力的很多会议都是针对数据挖掘领域进 行研讨的。目前，国外数据挖掘研究的发展趋势主要有对知识发现方法的进一步研究， 如b a y e s 方法的深入研究以及b o o s t i n g 方法的研究和提高：k d d 中统计学回归法的应用： 支持向量机的研究等。 与国外研究相比，国内对数据挖掘的研究起步比较晚，在1 9 9 3 年国家自然科学基 金才首次支持对该领域的研究项目，从那以后，数据挖掘的研究工作在我国迅速发展起 来。目前，国内的许多科研单位和高等院校都开展了数据挖掘的研究工作，绝大多数集 中在对数据挖掘算法进行研究以及有关数据挖掘理论方面的研究。 1 2 2 模糊聚类理论的发展 1 9 6 5 年，学者l o t f iz a d e h 引进模糊集合论( f u z z ys e tt h e o r y ) 和模糊逻辑( f u z z y l o g i c ) 两个概念，从而创立了一种处理不精确和不确定性的方法。简要地说，模糊集 合论允许对象以o 和1 之间的某个隶属度属于一个集合，而模糊逻辑允许一个陈述以0 和1 之问的确定度为真。模糊聚类分析相对于传统的聚类方法是一种软聚类，由j 模糊 聚类方法能表示样本隶属于各个类的不确定程度，因此能表示了数据类属的中介性，且| j 建立起了样本对于类别的不确定性描述，可以更客观地反映现实世界。因此，模糊聚类 分析目前已经成为聚类分析研究的主流方向。 1 ，7 ，8 聚类分析技术的发展及应用前景十分_ “阔，学者d u b e s 和j a i n 就曾做了关于聚类 分析的综述，报告中包括了从7 7 份杂志和4 0 本书中摘取出来的2 5 0 条引文 9 。州时， 国际和国内学者都对聚类分析的研究非常重视，在i e e e 汇刊的许多杂志中几乎每期都 有讨论聚类分析问题的文章。我国在模糊数学研究方面处于世界领先地位，不仅在基础 理论研究上取得了丰硕的成果，而且在模糊聚类等的应用研究上亦令世人瞩目，比如将 模糊聚类应用于天气预报、矿藏识别和医学诊断等方面。为了积极引导模糊聚类分析的 理沦和应用的研究热潮，国家自然科学基会会还专门对“模糊聚类的新方法研究”和“尤 监督新闻视频语义分割和自动标注算法研究”立了项。在这样的背景下，越来越多的机 构和院校加入到研究模糊聚类分析的队伍中来。 7 1 2 3 马氏距离研究热点 1 9 3 6 年，印度统计学家马哈拉诺比斯( p c m a h a l a n o b i s ) 提出一种用米表示数据协 方差距离的计算方法，被称为马氏距离。它是多元统计分析中最著名的距离概念，被，“ 泛应用于各个研究领域。 马氏距离最初被应用到模式识别的许多领域，利用样本之间的马氏距离表示其| 【l j 的 差异，根据样本到各类距离的远近判断样本所属的类别，如基于k e r n e l 的马氏距离判 2 模糊r 均值算法的研究 别法 1 0 。近几年，马氏距离被应用在许多其它领域，如管理学中的马n 1 系统( m t s ) 1 1 ，它是一种新的判别预测方法，采用马氏距离作为特性指标，并结合了田口方法在 稳健性设计中的思想、技术，具有较高的准确性。在国外，马田系统被应用于医疗诊断、 产品的自动检验等许多领域，并且取得很好的效果。此外，马氏距离在地球化学领域也 得到了广泛应用 1 2 ，1 3 。 近年来，在模式识别和聚类分析领域，马氏距离也被学者广泛研究，被应用于人脸 识别、图像分割、语言识别、数据聚类、支持向量机等不同方面，都取得了很好的效果。 1 4 ，1 5 ，1 6 ，1 7 1 3 论文主要内容及组织结构 论文详细研究和分析了f c m 算法的过程，并介绍了马氏距离的基本原理，在模糊r 均值聚类算法中融入马氏距离的思想，提出了两种新算法，其一是基于马氏距离的f c m 算法，其二是基于马氏距离的特征加权在模糊聚类中应用，并分别埘每种算法给出具体 实验步骤及结果。此外，在处理高维大样本数据集时，本文提出了基二fk p c a 特征提取 的f c m 算法，并给出了算法的实验步骤及结果。本文具体内容如下： 1 ) 绪论，简要介绍了论文的选题背景和研究意义，介绍了目前聚类分析的研究现状以 及马氏距离的特点，并给出了论文的内容和结构安排。 一 2 ) 介绍模糊聚类分析的基础知识、并讨论了模糊聚类分析中的主要算法的优缺点。详 细介绍了模糊r 均值聚类算法原理并进行分析，并对f c m 聚类算法的各个步骤进行了详 细的研究，指出算法各个步骤中存在的主要问题，并分析了针对这些问题的一些研究成 果，以便于做进一步的工作。 3 ) 马氏距离的基本原理及在使用过程中出现的奇异值问题的解决方法，并介绍r l 前 马氏距离的应用现状。 4 ) 新算法的提出和实验结果，本章根据前面的介绍和分析，将马氏距离的思想引入模 糊r 均值算法中，提出了两种使用马氏距离的方法。最后对实验结果进行了分析，扶得 了较好的结果。 5 ) 基于k p c a 特征提取的f c m 算法的提出，并对实验结果进行分析比较。 6 ) 总结与展望，对论文的工作进行总结并提出以后进一步的研究方向。 辽! j7 师范人学硕十学位论文 第二章模糊伊均值算法及分析 2 1 模糊理论基础 模糊理论( f u z z yt h e o r y ) 是建立在模糊集合基础之上的，是描述和处理人类语言 中所特有的模糊信息的理论。它的主要概念包括模糊集合( f u z z ys e t s ) 、隶属度函数 ( m e m b e r s h i pf u n c t i o n ) 、模糊算子( f u z z yo p e r a t o r ) 、模糊关系( f u z z yr e l a t i o n ) 等。 2 1 1 模糊理论的主要概念 模糊集合的概念是由经典集合发展而来的，所以我们先介绍普通集合，然后再介绍 模糊集合的理论。 ( 1 ) 普通集合及其关系与运算 定义2 卜l 给定论域彳和某一性质或属性只爿中满足性质尸的所有元素所组成的 全体叫做集合( s e t ) ，简称集。 集合的基本描述方法有表达式描述法和列举法两种，集合的关系有包含、子集、集 合相等，一个集合中的元素具有下列特征： 确定性：任何一个元素要么是这个集合的元素，要么不是这个集合的元素。两 者必居其一。 互异性：集合中的元素是不能重复出现的。 无序性：集合中的元素相互交换次序之后，所得的集合与原来的集合是相同的。 常用的集合表示方法有如下三种形式： 1 列举法( 枚举法) ：对于有限集，可以将所有的元素一一列出，并用大括号括 起来表示。 2 描述法( 定义法) ：对于无限集，由于元素数目无限，可通过元素的定义来拙述 集合。 3 特征函数法：特征函数法是指用解析形式描述元素属于集合的程度。 ( 2 ) 模糊集合的概念与模糊关系的性质 在经典集合论中，论域中的某一元素x ，要么x 完全属于某个集合彳，即( x ) = 1 ： 要么完全不属于刀，即u ( x ) = 0 ，二者必居其一，元素间的分类具有截然分明的分界。从 这个意义上说，普通集合又称为“硬集”( c r i s ps e t s ) ，该函数称为集合a 的特征函数。 将特征函数推广到模糊集，是从在普通集合中只取o 和1 两值推广为 0 ，1 区间。 4 模糊r 均值算法的研究 定义2 卜2 模糊集：设j 为论域，若a 为彳上取值 0 ，1 的一个函数，则称彳为模 糊集。 假设教室晕有5 个学生，分别以s hs ：，s 。，s 。和s s 来表示，其中s ，s ：，s ：，为男7 扣， s ，s ；为女生。如果我们用九表示男学生的集合，以a ，表示女学生的集合，利用特征函 数表示法，可以将a 哪和a ，表示为： a m = 1 s l + l 5 2 + l s 3 + o s 4 + o s 5 a f = o s l + o s l + q | s j 七、| s4 + 、| s s 显然，凡和a ，的分解是截然分明的。 但是，当我们试图在这5 个同学中构成表示“高个子学生”和“矮个子学生”的集 合时，会感到传统的集合概念难以应用。学生的身高虽然有高低之分，但是，对于“高 个子学生”和“矮个子学生”这样的集合，我们不能指明哪些学生一定属于“高个子”， 哪止匕同学一定属于“矮个子”。实际上，人们在处理这样的问题时，不需要完全确定谁 是或者谁不是这些集合的成员，只需要对每一个元素确定一个数值，用这个数值表j 该 元素对所言集合的隶属程度。若学生s 。对于“高个子学，卜”集合的隶属发高_ 丁学生s 。， 我们就说学生s 。比学生s ：相对地更属于“高个子学生”这个集合，而学生s 相对地更 属于“矮个子学生”这个集合 1 8 。 币是考虑到现实世界中很多事物的分类边界是不分明的，而这种不分明的划分在人 们的 叭t l 别、判断和认知过程中起着重要的作用，为了用数学的方法来处理这种问题，扎 德( l a z a d e h ) 于1 9 6 5 年提出了模糊集合的概念。他用隶属度函数来刻i 田j 处于巾介过 渡的事物对差异双方所具有的倾向性。可以认为隶属度函数是普通集合中特征函数的推 广。当我们将特征函数的值域由 o ，1 ) 二值扩展到 o ，1 区间时，就描述了一个模糊集 合。 定义2 卜3 模糊集合：设j 为论域，若a 为j 上取值 o ，】 的一个函数，则称a 为模糊集。 值得注意的是，我们在讨论模糊集合的概念时，论域彳所包含的元素是分明的，并 不是模糊的，而只有彳上的模糊集合4 才是模糊的。从这个意义1 - 说，模糊集合应该称 为模糊子集合( f u z z ys u b s e t ) 2 1 2 模糊关系 集合论中的“关系”抽象地刻画了事物的“精确性”的联系，而“模糊关系”则从 更深刻的意义上表现了事物问更广泛的联系。从某种意义上讲，模糊关系的抽象形式更 接近于人的思维。在经济生活与经济科学中存在大量的模糊关系，而分类也是经济分析 与经营管理中常常使用的方法。模糊关系理论是许多应用原理和方法的基础。 辽。j 。师范人学硕十学位论文 定义2 卜4 模糊关系：y xy 中的二元模糊关系尺是彳y 中的模糊集合，它的隶描 函数用，( x ，y ) 表示。 h 若y - - - , 则称尺是中的模糊关系。a ( x ，y ) 在实轴闭区间 0 ，1 取值，它的大小反 ，( 映了( 墨j ，) 具有关系尺的程度。 7 由于模糊关系也是模糊集合，因此模糊集合的相等、包含、交、并、补等概念埘模 糊关系同样具有意义。 ( 1 ) 模糊关系的性质 定义2 卜5 自反性：设尺是中的模糊关系，若对v x x ，都柯( x ，x ) = 1 ，则称 尺为自反关系。 。7 定义2 1 6 转置：设尺是脓y 中的模糊关系，记尺的转置为尺，它足y x , l 中的关 系且具有隶属度函数( y ，x ) = ( x ，y ) 。 r 7 r 定义2 卜7 对称性：设尺是论域x 中模糊关系，当且仅当对v x ，y x ，有 ( x ，y ) = ( y ，x ) ，则称尺是对称关系。 片月 定义2 卜8 传递性：设尺是论域x 中模糊关系，若有尺。尺尺成立，则称月具有 传递性。 定义2 1 - 9 模糊相似关系：设尺是论域x 中模糊关系，若尺同时具有自反性和对称 性，则称尺为模糊相似关系。 定义2 卜1 0 模糊等价关系：设尺是论域x 中模糊关系，若尺同时具有自反性、对 称性和传递性，则称r 为模糊相等价关系。 7 ，1 8 2 2 聚类分析理论 聚类分析源于许多研究领域，包括数据挖掘、统计学、机器学习、模式识别等。它 是数据挖掘中的一个重要功能，但也能作为一个独立的工具来获得数据分布的情况，概 括出每个簇的特点，或者集中注意力对特定的某些簇作进一步的分析。此外，聚类分析 模糊r 均值算法的研究 也可以作为其他分析算法( 如关联规则、分类等) 的预处理步骤，这些算法在生成的簇 上进行处理。 1 9 2 2 1 聚类分析的基本概念 ( 1 ) 聚类概念 定义2 2 一l 聚类分析的输入可以用一组有序对( x ，s ) 或( x ，d ) 表示，这罩彳表示一 组样本，s 和d 分别是度量样本间相似度或相异度( 距离) 的标准。聚类系统的输出时 对数据的区分结果，即c = c l ，g9o *o 9 c k ，其中g ( 江1 , 2 ，k ) 是的子集，且满足如 下条件： c ，uc ：u uc t = x ： c inc 2 = ，f 。 f 中的成员c l ，c ：，c 。称为类或者簇。每一个类可以通过一监特征来描述。通常有如下 几种表示方式： 通过类的中心或类的边界点表示一个类。 使用聚类树中的结点图形化地表示一个类。 使用样本属性的逻辑表达式表示类。 。 用类的中心表示一个类是最常见的方式，当类足紧密的或各向分布同性时用这种 方法非常好，然而，当类是伸长的或各向分布异性时，这种方式就不能正确地表示它 们了。 1 9 褂 ( 2 ) 聚类分析方法 聚类分析是指用数学的方法研究和处理给定对象的分类，依据对象间关联的度量标 准将给定对象自动分成几个类，且使同一类中的对缘相似，而属于不同类的对象相异的 一组方法。一个聚类分析系统的输入是一组对象和一个度量两个对象i 自j 相似度( 或相异 度) 的标准，聚类分析的输出是数据集的几个类( 簇) ，这些类构成一个分区或分区结构。 聚类分析的一个附加结果是对每个类的综合描述，这种结果对于史进一步深入分析数据 集的特征是尤其莺要的。 ( 3 ) 距离与相异性的度量 一个聚类分析过程的质量取决于对度量标准的选择，冈此必须仔细选择度黾标准。 在通常情况下，聚类算法不是计算两个样本问的相似度，而是用特征空间中的距离作为 度量标准来计算两个样本间的相异度。对于某个样本空间来说，距离的度最标准可以是 度量的或半度量的，以便用来量化样本的相异度。相异度的度量用d ( x ，力来表示，通常 辽j 。师范人学硕十学位论文 称相异度为距离。当x 和y 相似时，距离j ( 五力的取值很小；当工和j ，不相似时，d ( 以力 就很大。最常用的距离度量方法有明可夫斯基距离、马式距离和余弦距离等。 明可夫斯基距离( m i n k o w s k i ) 假定，爿，y 是相应的特征，1 7 是特征的维数。x 和j ，的明可夫斯基距离度量的形式如 + f ： n r ， d ( x ，y ) = ( k y ，1 ) 彤，尸 o ( 2 1 ) 膏= i 当，取不同的值时，上述距离度量公式演化为一些特殊的距离测度。 当f 1 时，明可夫斯基距离即为绝对值距离； d ( x ，y ) = i x ，一y ，i ( 2 2 ) 七= l 当1 - - = 2 时，明可夫斯皋距离即为欧氏距离。 r 一 d ( x ，j ，) = 1 ( 坼一y ) 2 ( 2 3 ) v = i 马氏距离( m a h a l a n o b i s ) 设彳是从均值为，协方差为；的母体g 中抽取的样本总体，样本x ，到样本总体j 的马氏距离为： d e ( x i ，x ) = ( x i 一) t i 1 ( x i 一) ( 2 4 ) 余弦距离( c o s i l 3 e ) 在聚类分析中，每个对象可以看作7 维空间中的向量，第j 个对象可表示为 ，= ( ，l ，脚，x ，。) r ，它们的相似系数【叮用两个向量问的央角余弦来表示，于是第j 个与第个对象的相似系数表示为 q ，= c o s ( o , , ) = p x 腑b k = l ( 2 5 ) 2 2 2 聚类分析算法 聚类分析是一个活跃的研究领域，涌现了大量的、经典的流行算法。常用的聚类分 析算法有基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格 的聚类算法以及基于模型的聚类算法等。 模糊r 均值算法的研究 基于划分的聚类算法是目前最重要的聚类分析算法，主要有k - m e a n s 和k - m e d o i d s 两种算法，它们在复杂度上具有一定的优势，并且基于划分的聚类算法实现简单，但在 处理“噪声”和孤立点数据时效果不理想，而且都需要用户预先指定划分类的数目，具 有扩展性差的缺点。基于层次的聚类算法是第二类重要的聚类方法，目前常用的是改进 的层次聚类方法如b i r t h 和c u r e 算法。其中b i r c h 算法具有数据的线性伸缩能力，但 是它所形成的簇是球形的：c u r e 算法对独立点的处理更加健壮，而且能识别非球形和大 小变化比较大的簇，但是不能自适应的确定参数，参数设置对聚类结果也有显著影响。 基于密度的聚类算法的主要思想是只要一个区域中点的密度大于某个域值，就把它加剑 与之相近的类别中去。这类方法需要扫描整个数据库，每个数据对象都町能引起一次查 询，因此当数据量大时会造成频繁的i o 操作。代表算法有：d b s c a n 、o p t i c s 、d e n c l u e 算法等。基于网格的聚类算法中代表算法有s t i n g 算法和c l i q u e 算法，但它们只在低 维空间中处理数据十分有效。基于模型的聚类方法试图优化给定的数据和某些数据模世 之间的适应性，其中最常用的是s o m 神经网络算法。s o m 算法的最大局限性足，当学习 模式较少时，网络的聚类效果取决于输入模式的先后顺序，且网络连接权向量的初始状 态对网络的收敛性能有很大影响。 2 3 模糊伊均值算法 随着计算机技术的应用和模糊理论的发展，基于目标函数的模糊聚类算法成为目前 国内外学者的研究热点，模糊旷均值算法( f c m ) 是最受欢迎的是基于目标i ；i i 数的模糊 聚类方法，该算法于1 9 8 1 年由b e z d e k 1 9 提出。f c m 算法基于模糊集合理论，并把聚 类归结成一个带约束的非线性规划问题，通过迭代优化求解获得数据集的模糊划分和聚 类结果。模糊旷均值聚类算法是最早的目标函数聚类算法，也是目标函数聚类算法巾研 究得比较充分的算法，己经广泛应用于数据挖掘、模式识别、图像处理和计算机视觉、 公路检测等不同领域。 2 3 1 模糊产均值算法分析 设x = x ，x ：，x 。) 为门元数据集合，x ，r 5 。f c m 聚类方法就是把彳划分为c 个子 集s l ，s 2 ，s 。，若用a = 位l ，口2 ，口。) 表示这c 个子集的聚类中心，“。表示元素x ，对s ， 的隶属度，则f c m 算法的优化目标函数为： ( u ，a ，x ) = “了d ；= “驰，一口，i i ( 2 6 ) ，；l i = 1 t = li = 1 u ，满足约束条件： 9 辽j 。师范人学硕+ 学位论文 u u = 1 ，l j n ， ( 2 7 ) u i 0 ，1 i c ，1 j 1 1 这咀u = u 。 为c n 矩阵，a = 口l ，口2 ，口。) 为s xc 矩阵，d 。为x j 与口，的距离，经典的 f c m 算法罩使用欧氏距离。m 为大于l 的模糊指数，控制分类矩阵u 的模糊程度，m 越 大，分类的模糊程度越高，在实际应用中朋最佳范围为( 1 5 ，2 5 ) ，推荐使用m = 2 。f c m 算法是使目标函数最小化的迭代收敛过程。在迭代求解j 嚣m 的最小值时，甜，是按 l a g r a n g e 乘数法得到的： ( “，x ， f l ，= 导_ 一， ( 2 8 ) ，2 。一， k z 石， ( ”，) ” 圹磊1 i k 。i a b 可以看出，f c m 算法就是反复修改聚类中心矩阵和隶属度矩阵的分类过程，冈此常称 这种力- 法为动态聚类或者逐步聚类法。f c m 算法计算简单而且运算速度快，具有较直观 的儿何含义，但是与卜均值聚类算法一样，只能用类中心来表示类，这样只适于发现球 状类型等非凸面形状的簇，并且在很多情况下算法对噪声数据敏感。几经修补，该算法 的收敛性已经得以证明 2 0 ，2 1 ：f c m 算法能从任意给定初始点开始沿一个迭代子序列收 敛到其目标函数。( u ，p ) 的局部极小点或鞍点。 f c m 算法足目前比较流行的一种模糊聚类算法，究其原凶大致有以下几个方面：首 先，模糊r 均值泛函。乃是传统的硬r 均值泛函，的自然推广，我们知道，。是一个 应用十分广泛的聚类准则，对