（应用数学专业论文）模糊聚类中若干问题的研究.pdf

n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n da s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo fs c i e n c e s t u d y o ns e v e r a lp r o b l e m si nf u z z y c l u s t e r i n g a t h e s i si n m a t h e m a t i c s b y h u x i a o q i n g a d v i s e db y p r o f m ar u n i n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro fs c i e n c e d e c e m b e r ，2 0 0 9 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描： 等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本承诺书) 作者签名：塑盘基 日 期：塑坦：圣：4 南京航空航天人学硕士学位论文 摘要 聚类分析作为无监督模式识别的一个重要分支已经成为现代数据分析的一个重要工具不 同的初始条件和聚类标准通常会导致不同的聚类算法因此，聚类算法是一个内容庞杂的算法 族到目前为止，人们提出了各种各样的聚类算法 模糊c 均值算法由于简单有效成为最受关注的模糊聚类算法之一该算法及其推广算法已 被成功应用到很多领域这些方法的共同点是通过反复迭代计算最优分类( 如聚类中心) 因此， 它们敏感于初始聚类中心及噪声点，而且这些方法只能检测预先给定个数的球状结构模式的聚 类然而，很多情况下聚类中心并非真实存在为了便于处理任意形状结构模式的聚类，本文 提出一种无需聚类中心的新的模糊聚类算法( c c f r - f c m ) 该方法通过定义样本点与各聚类间 的模糊相似性函数来确定各样本所属的类别为了确定数据集包含的聚类个数，我们建立与 c c f r - f c m 方法相适应的聚类有效性指标 层次聚类算法是另一类应用较为广泛的聚类方法它能够把样本集的多种分类结果全部展 示出来，但是从这些分类结果中获得用户最满意的分类情况就成了一个问题众所周知，层次 聚类中的每一种分类结果都对应某个模糊旯水平截集因此，选择最优分类结果的问题就转化 成最优阈值旯的选取问题本文从相似性关系出发，建立了一个能够体现聚类类内致密性和类 间分离性的有效性函数来选取层次聚类的最优阈值 在人工和实际数据集上的实验都表明了新算法及新的有效性指标函数的有效性 关键词：模糊聚类，模糊c 均值算法，层次聚类，聚类中心，阈值，聚类有效性 模糊聚类中若干问题的研究 a b s t r a c t a sa l li m p o r t a n tb r a n c ho fu n s u p e r v i s e dp a a e mr e c o g n i t i o n ，c l u s t e r i n ga n a l y s i sh a sb e c o m ea n i m p o r t a n tt o o li nm o d e m d a t aa n a l y s i s d i f f e r e n ts t a r t i n gp o i n t sa n dc r i t e r i au s u a l l yl e a dt od i f f e r e n t t a x o n o m i e so fc l u s t e r i n ga l g o r i t h m s t h e r e f o r e ，c l u s t e r i n ga l g o r i t h m si sav a s ta n dd i v e r s ea l g o r i t h m f a m i l y v a r i o u sc l u s t e r i n ga l g o r i t h m sh a v eb e e np r o p o s e du n t i ln o w f u z z yc - m e a n s ( f c m ) ，o w i n gt oi t sn a t i v es i m p l i c i t ya n de f f i c i e n c y , i so n eo ft h em o s tp o p u l a r c l u s t e r i n ga l g o r i t h m s f c m ，a sw e l la sa n u m b e ro fi t se x t e n s i o n s ，h a sb e e na p p l i e dt oaw i d er a n g eo f c l u s t e r i n gt a s k sw i t hg r e a ts u c c e s s w h a ti sc o m m o nf o ra l lt h e s es u g g e s t e dm e t h o d si st h a tt h e y r e q u i r et h ee l a b o r a t ei t e r a t i o n sf o rc o m p u t i n go p t i m a lc l u s t e rm e a n s ( i e c e n t e r s ) a sac o n s e q u e n c e ， t h e ya r en o t i c e a b l ys e n s i t i v et ot h ei n i t i a lc l u s t e rc e n t e r sa n dp o s s i b l ye x i s t e dn o i s e i na d d i t i o n , t h e y t e n dt of i n do n l yt h ep r e - s p e c i f i e dn u m b e ro fs p h e r e - s h a p e dc l u s t e r s h o w e v e r ，i nm a n ys i t u a t i o n s ， t h e r em a yb en o i r u e ”r e p r e s e n t a t i v e sf o rc l u s t e rc e n t e r s i nt h i sp a p e r , w eh e n c ep r o p o s ean o v e l c l u s t e r - c e n t e r - f r e er e f o r m u l a t i o no ff c mt h a tc a r lh a n d l ea r b i t r a r i l ys h a p e dc l u s t e r s t h i si sd o n eb y d e f i n i n gan o v e lf u z z ys i m i l a r i t yf u n c t i o nb e t w e e ne v e r yp o i n ta n ds o m ec l u s t e r t h i sf u r t h e ra l l o w s u st od e d u c ea m e a n i n g f u lc l u s t e r - v a l i d i t yi n d e xf o rd e t e r m i n i n ga na c c u r a t en u m b e ro fc l u s t e r si nt h e d a t a h i e r a r c h i c a lc l u s t e r i n gi sa n o t h e rm o s tp o p u l a rc l u s t e r i n ga l g o r i t h m i ti aa b l et od e p l a ys e v e r a l p a r t i t i o n i n gr e s u l t so ft h ed a t a s e t , h o w e v e r , i ti sap r o b l e mt h a tu s e r so b t a i nt h em o s ts a t i s f a c t o r y c l a s s i f i c a t i o nf r o mt h e s ep a r t i t i o n i n gr e s u l t s a si sk n o w nt oa l l ，e a c hc l u s t e r i n gr e s u l ti nh i e r a r c h i c a l c l u s t e r i n gc o r r e s p o n d st oaf u z z y 名- l e v e ls e t t h e r e f o r e ，s e l e c t i n gt h eo p t i m a lc l a s s i f i c a t i o nr e s u l ti s e q u i v a l e n tt ot h ep r o b l e mo ft h eb e s tt h r e s h o l dr s e l e c t i o n i nt h i sp a p e r , an e wc l u s t e r - v a l i d i t y i n d e xi se s t a b l i s h e du s i n gt h es i m i l a r i t ym a t r i xo ft h ed a t a s e t ，a c c o r d i n gt o c o m p a c t n e s sa n d s e p a r a t i o n t h en e wc l u s t e r - v a l i d i t yi n d e xi sa p p l i e dt od e t e r m i n et h eb e s tt h r e s h o l df o rh i e r a r c h i c a l c l u s t e r i n gm e t h o d t h ee x p e r i m e n t a lr e s u l t so nb o t hs y n t h e t i ca n dr e a l w o r l dd a t a s e t sh a v ed e m o n s t r a t e dt h e e f f e c t i v e n e s so ft h en e wa l g o r i t h ma n dt h en e wc l u s t e r - v a l i d i t yi n d i c e s k e y w o r d s ：f u z z yc l u s t e r i n g ，f u z z yc - m e a n s ，h i e r a r c h i c a lc l u s t e r i n g ，c l u s t e rc e n t e r s ，t h r e s h o l d ， c l u s t e r - v a l i d i t yi n d e x 目录 摘要i a b s t r a c t i i 目录m 图表清单v 注释表v i 第一章绪论。1 1 1引言1 1 2聚类分析概述2 1 3聚类分析的数学模型3 1 4相似性测度：4 1 5聚类分析概述：5 1 5 1 层次聚类算法5 1 5 2 基于划分的聚类算法6 1 5 3 硬聚类算法一6 1 5 4 模糊聚类算法6 1 6模糊聚类方法研究7 1 7本文的主要创新点1 l 1 8本文的内容安排1 2 第二章独立于聚类中心的模糊聚类算法1 3 2 1 原始f c m 算法一1 3 2 2 聚类的准则函数1 4 2 3 独立于聚类中心的模糊聚类算法1 5 2 4 数据实验及分析1 7 第三章新算法的聚类有效性分析2 0 3 1 已有的f c m 聚类有效性研究一2 0 3 2 新的有效性函数一2 2 3 3 新的有效性函数的实验测试2 2 3 4 关于参数口的讨论2 3 第四章层次聚类算法中最佳阈值的选取2 4 4 1 凝聚式层次聚类算法2 4 4 2 用f 统计量确定旯最佳值2 5 模糊聚类中若干问题的研究 4 3 基于相似性矩阵的有效性函数2 6 4 4 实验结果分析2 8 第五章总结与展望3 1 参考文献3 2 致谢3 5 在学期间的研究成果及发表的学术论文3 6 i v - 南京航空航天大学硕士学位论文 图表清单 图1 1p c m 算法对噪声的鲁棒性9 图1 2p c m 算法对任意形状数据集的聚类结果图9 图1 - 3f j p 算法聚类效果图1 0 图1 4 关于f c m 类型算法缺陷的两个简单实例说明1 1 图2 1 五个人工数据集1 7 图2 2f c m 算法对数据集n o r m r a n d 3 、c i r c l e d 2 、s e m i c i r c l e 聚类结果图1 8 图2 3k f c m 算法对数据集n o n n r a n d 3 、c i r c l e d 2 、s e m i c i r c l e 聚类结果图1 8 图2 4c c f r - f c m 算法对数据集n o r m r a n d 3 、c i r c l e d 2 、s e m i c i r c l e 聚类结果图1 9 图3 1a r c h 数据的聚类效果图2 3 图3 2 参数口的取值对聚类结果的影响示意图2 3 图3 - 3 通过数据集s e m i c i r c l e 研究参数口的取值2 3 图4 ，l 凝聚式层次聚类算法形成的系统树图( 直方图) 2 4 图4 2c i r c l e d 2 数据集及其在本文指标玩下的层次聚类结果图2 9 图4 3s e m i c i r c l e 数据集及其在本文指标巧下的层次聚类结果2 9 图4 4 n o r m r a n d 3 数据集及其在本文指标巧下的层次聚类结果3 0 图4 5i r i s 数据集及其在本文指标下的层次聚类结果图3 0 表2 1c c f r - f c m 算法与f c m 算法聚类手写数字的错误率比较1 9 表3 1 最优分类个数表2 2 v 模糊聚类中若干问题的研究 x样本集，论域 d样本空间维数 u模糊分类矩阵 层次聚类系统树图 盹( 故) 样本耳对形隶属度函数 v j 注释表 刀 样本个数 c 聚类类别个数 y 聚类结果 p ( 五)样本五的特征向量或模式向量 南京航空航天人学硕士学位论文 第一章绪论 1 1引言 如果说当今世界是一个脑力延伸的时代，确实一点也不过分随着现代科学特别是计算机 科学的发展，社会科学与自然科学之间相互渗透，形成许多新的边缘学科其中最具有生命力 的，莫如信息科学，因为它用量化公式把人的思维过程表现了出来这样，配合以现代电子计 算机的巨大信息存储能力，便可以解决许多人的才智所不能解决的复杂问题 信息科学的最新研究发展表明，建立在概率论基础上的香农( s h a n n o n ) 信息论，只是着重表 达信息的传递，难以表达信息本身的含义而信息科学不仅要研究信息“量”的问题，更重要的 还在于信息的结构，即信息的定性描述问题这就涉及到信息的提取、描述、分析、推理、判 断和决策等富有挑战性的处理工作在信息处理这一领域中，模式识别起着举足轻重的作用， 具有信息感知与理解等处理功能，是信息结构与含义的重要分析工具 模式识别( p a t t e r nr e c o g n i t i o n ) ，又常称作模式分类，是2 0 世纪6 0 年代初迅速发展起来的、 与高技术的研究开发有着密切联系的一门新兴学科它所研究的理论和方法在很多科学和技术 领域中得到了广泛地应用，推动了人工智能系统的发展，扩大了计算机应用的领域，在向人类 智能逼近这一永恒的前沿课题中占有一席之地可以说，在高度自动化的今天，模式识别几乎 已经进入人类生活的各个领域 “模式”( p a t t e m ) 这个词与保护神( p a t t r o n ) 来自同一词根，本意是指供模仿用的理想标本因 此，抽象地讲，模式识别是指从待识别的对象中分辨出哪个对象与标本相同或相似人脑就是 一个可靠的识别系统，人们在感受外界现象的时候，总要把它们进行分类，即把相似而又不完 全相同的现象分成一组这时，在同一组中不同的物体和现象之间总有某些方面是相似的人 们只要熟悉现象中为数不多的代表，就能从现象形成组的概念，正是人脑的这种能力才构成模 式的概念显然，分类( c l a s s i f i c a t i 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 ) 和无监督的分类( u n s u p e r v i s e dc l a s s i f i c a t i o n ) 两种类型所谓有监 督的分类，又称为有教师的分类或者有指导的分类在这类问题中，已知模式的类别和某些样 本的类别属性，首先用具有类别标记的样本对分类系统进行学习或训练，使该分类系统能够对 这些已知样本进行正确分类，然后用已经学习好的分类系统对未知的样本进行分类这就要求 我们对待分类的问题要有足够的先验知识，而要做到这一点，往往要付出相当人的代价在没 模糊聚类中若干问题的研究 有先验知识的情况下，分类则需要借助无监督的分类技术聚类分析 1 1 ( c l u s t e r a n a l y s i s ) 耳p 为无 监督的分类从学科的谱系图上看，聚类分析属于信息科学这棵大树上模式识别分支中的一片 树叶 虽说聚类应用于模式识别的时间不长，但它并非一个新的领域，早已被应用在其他学科中， 如医学图像处理、生物信息学、数据挖掘等领域d u b e s 和j a n 关于聚类分析的综述包括了从 7 7 份杂志和4 0 本书中摘取的2 5 0 条引文，如此巨大的文献量说明了聚类分析的重要性和交叉 学科性，也足以说明它的发展以及应用前景的广阔性 同时，国际和国内的学者都对聚类分析的研究非常重视，i e e e 的汇刊中模式分析与机器 智f 毙f p a m d 、系统、人和控制( s m c ) 、模糊系统( f s ) 、神经网络q n ) 、信号处理 ( s p ) 等杂志中几乎每一期都有讨论聚类分析问题的文章从1 9 9 2 年开始的由i e e e 和神经网络 理事会共同主办的f u z z i e e e 会议，每两年召开一次，每次至少有3 到4 个专题讨论聚类和模 糊聚类分析的研究进展和发展现状另外，我国作为模糊数学研究的大国，不仅在基础理论研 究上取得了丰硕的成果，而且在模糊聚类等的应用研究上亦令人瞩目，比如基于模糊聚类的天 气预报、矿藏识别和医学诊断等等在这样的背景下，( 模糊) 聚类分析研究的理论意义和实用 价值也就不言而喻了本文主要针对模糊聚类算法及聚类有效性进行研究，提出了改进的模糊 聚类算法和衡量有效性的新指标 1 2 聚类分析概述 聚类就是按照一定的要求和规律对事物进行区分和分类的过程，在这一过程中没有任何关 于分类的先验知识，没有教师的指导，仅靠事物间的相似性作为类别划分的准则，因此属于无 监督分类的范畴1 2 1 聚类分析则是指用数学的方法研究和处理给定对象的分类问题“物以类聚， 人以群分”，聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深化聚类是人类 最基本的一项认识活动人类要认识世界就必须区别不同的事物并认识事物问的区别与联系， 而每个概念的最初形成无不借助于事物的聚类分析因此，聚类分析的研究不仅具有重要的理 论意义，也具有重要的工程应用价值和人文价值 传统的聚类分析是一种硬划分，它把每个待识别的对象严格地划分到某类中，具有“非此即 彼”的性质，因此这中类别划分的界限是明确的尽管如此，现实世界中遇到的对象很多是模糊 的、不精确定义的类型，它们的成员没有精确定义的判别标准，例如，“好与坏”、“长与短”、 胖与瘦、“太热”、“有点冷”等等这些对象并没有严格的属性，它们在性态和类属方面存在着 中介性，具有“亦此亦彼”的性质，但是这些量在人们的头脑里的确有个“标准”，而且为人们所 接受，因此适合进行软划分利用这些“不确定量”非但不会影响人们之间的信息交流，反倒更 便于理解与记忆模糊集理论的提出为这种软划分提供了有力的分析工具1 9 6 5 年，美国自动 2 南京航空航天大学硕士学位论文 控制专家、数学家扎德( l a z a d e h ) 在信息与控制( i n f o r m a t i o na n dc o n t r 0 1 ) 杂志上发表了他 的论文模糊集( f u z z ys e t s ) ) ) 【3 】，把模糊性和数学统一在了一起，这标志着模糊数学的诞生人 类开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析由于模糊聚类得到了样本属于 各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性描 述，更能客观地反映现实世界，从而成为聚类分析研究的主流 1 3 聚类分析的数学模型 从数学角度来刻画聚类分析问题，可以得到如下的数学模型设x = 五，恐，毛 r 艄d 是待分析对象的全体( 称为论域) ，x 中的每个对象( 称为样本) & ，( 尼= 1 ，2 ，2 ) 常用有 限个参数值来刻画，每个参数值可以是定性的或者定量的、连续的或者二进制的，用来刻画五 的某个特征于是对象毛就伴随着一个向量p ( x a = ( 五，以：，) ，其中， ( j = 1 ，2 ，d ) 是吒在第个特征上的赋值，尸( ) 称为五的特征向量或模式向量聚类分析 就是分析论域x 中的n 个样本所对应的模式向量间的相似性，按照各样本间的亲疏关系把 五，x 2 ，毛划分成多个不相交的子集巧，匕，圪，并要求满足以下条件： kuku uk = x ； k n = 彩。1 i j c 样本( 1 尼刀) 对子集( 类) k ( 1 i c ) 的隶属关系可以用隶属函数表示为 地( x k ，= 1 i k - - 般嚣 其中，隶属函数必须满足条件心e ， 邑= i l ki 段 o ，1 ) ；心= 1 ，v k ；o 刀，v i 也就是说，要求每一个样本能且只能隶属于某一类，同时要求每个子集( 类) 都是非空的通 常称这样的聚类分析为硬划分( h a r dp a r t i t i o n 或c r i s pp a r t i t i o n ) 在模糊划分( f u z z y p a r t i t i o n ) 中，样本x 被划分成c 个模糊子集k ，k ，圪，而且样本的隶属函数从0 ，1 二值扩展到【o ，l 】 区间，满足条件： 易= 心i 段“o ，1 】；段= 1 ，v k ；0 心 ，有kc 巧或 巧n = 彩对所有f 都成立，i ，m ，= l ，2 ，g 从系统树图形成的方式来看，层次聚类 算法包括两种形式：凝聚式方法( a g g l o m e r a t i v em e t h o d s ) 和分裂式方法( d i v i s i v em e t h o d s ) 凝 聚式方法，是以一种“自底向上”的方式进行的首先将每个样本作为一个聚类，然后合并相似 模糊聚类中若干问题的研究 性最大的聚类为一个大的聚类，直到所有的聚类都被融合成为一个大的聚类它以甩个聚类开 始，以1 个聚类结束分裂式方法，是以一种“自顶向下”的方式进行的一开始它将整个样本 集看成一个大的聚类，然后，在算法进行的过程中考察所有可能的分裂方法把整个聚类分成若 干个小的聚类，第一步中分成两类，第二步中分成三类，这样一直进行下去直到最后一步分成刀 类在每一步中选择一个使得相异程度最小的分裂运用这种方法，可以得到一个相反结构的 系统树图，它以1 个聚类开始，以，1 个聚类结束与分裂式算法相比，由于凝聚式算法在计算 上简单、快捷，而且能够得到相近的最终结果，所以绝大多数层次聚类方法都是凝聚式的，它 们只是在聚类间相似性度量的定义上有所不同 1 5 2 基于划分的聚类算法 基于划分的聚类也叫分割聚类，和层次聚类方法相比它有一个明显的不同，那就是在给定 样本集的基础上直接得到一个事先定好类别数的聚类结果即给定一个具有忍个数据对象的数 据集x ，通过一个划分矩阵构建数据集的c ( c 刀) 个子集y = k ，y 2 ，圪 ，每个子集 就表示一个聚类，而且这c 个聚类满足如下的要求：( 1 ) 每个聚类至少包含一个样本，即k 囝， f = l ，2 ，c ；( 2 ) 每个样本必须至少属于一个聚类， 类kn 巧= a ，f ，- - 1 ，2 ，c 且f 歹 1 5 3 硬聚类算法 即譬形= x ；( 3 ) 每个样本只能属于一个聚 硬聚类把每个待辨识的对象严格地划分到某个类中，具有非此即彼的性质，因此这种类别 划分的界限是明确的样本对各个子类的隶属度取成0 和1 两种值，也就是说样本属于且只能 属于所有类别中的某一个类别传统的硬聚类方法大体上可分成两大类：启发式和划分式启 发式方法将数据进行树状分类，常常给出数据集的几种可能的分类情况：划分式则不同，它将 数据按照某种标准划分成单一的结果划分式技术包括目标函数法( 平方误差) 、密度估计法( 模 型搜寻) 、图结构法和最近邻法从总体而言，硬聚类算法具有花费时间少的优点，但其缺点也 是很明显的由于硬聚类方法中样本对各个子类的隶属度只能是0 或l 这两种值，绝对地割断 了样本与样本之间的联系，无法表达样本在性态和类属方面的中介性，极易陷入局部最优解， 使得所得到的聚类结果与实际要求偏差较大 1 5 4 模糊聚类算法 模糊聚类( 又称软聚类) 是聚类分析与z a d e h 教授提出的模糊理论相结合的产物模糊聚 类的分类结果仍然用样本对各类的隶属度来表示，只是这时样本对某个类别的隶属度从只能取 6 _i，ii 南京航空航天大学硕士学位论文 0 或l 两个数扩展到了整个【0 ，l 】区间，任何一个样本对所有类别的隶属度之和是1 模糊聚类 方法考虑到了样本与样本之间的联系，认为每一个样本与各个聚类中心都有一个隶属关系所 以模糊聚类能够有效地对那些类与类之间有交叉的数据集进行聚类与硬聚类相比，模糊聚类 提高了算法的寻优概率，所得的聚类结果明显地优于硬聚类方法由于模糊聚类得到了样本属 于各个类别的不确定性程度，表达了样本类属的模糊性，即建立起了样本对于类别的不确定性 的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流 1 6 模糊聚类方法研究 伴随着模糊集理论的形成、发展和深化，r u s p i n i 率先提出了模糊划分的概念以此为起点 和基础，模糊聚类理论和方法迅速蓬勃发展起来针对不同的应用，人们提出了很多模糊聚类 算法，比较典型的有基于相似性关系的直接聚类方法、基于模糊等价关系的传递闭包方法、基 于模糊图论的最大支撑树方法、基于数据集的凸分解和动态规划等方法然而，上述方法均不 能适用于大量数据的情况，难以满足实时性要求较高的场合，因此实际应用并不广泛，现在该 方面的研究正在逐步减少 实际中受到普遍欢迎的是基于目标函数的模糊聚类方法，也就是说，把聚类归结成一个带 约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类该方法设计简单，解决 问题的范围广，还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于在计算 机上实现因此，随着计算机的应用和发展，基于目标函数的模糊聚类算法成为新的研究热点 在基于目标函数的聚类算法中模糊c 均值( f c m ，f u z z yc m e a n s ) 类型算法的理论最为完 善、应用最为广泛模糊c 均值类型的算法最早是从硬聚类目标函数的优化中导出的为了借 助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，从此类 内平方误差和0 v g s s ，w i t h i n - g r o u p ss u mo f s q u a r e de r r o r ) 以成为聚类目标函数的普遍形式为 极小化该目标函数而采取的p i k a r d 迭代优化方案就是著名的硬c 均值( h c m ) 算法和i s o d a t a ( i t e r a t i v es e l f - o r g a n i z i n gd a t a a n a l y s i st e c h n i q u e a ) 算法模糊划分概念提出后，d u n n 首先把 w g s s 函数以扩展到以类内加权平均误差和函数，后来b e z d e k 又引入一个参数m ，把以 推j 。到一个目标函数的无限族，并给出了交替优化( a o ，a l t e r n a t i v e o p t i m i z a t i o n ) 算法，即为 人们所熟知的f c m 算法 从模糊聚类理论的研究现状米看，人们已经提出了许许多多的聚类算法，这恰恰说明了现 有算法还存在着种种不尽如人意的地方模糊c 均值( f c m ) 算法由于其操作简单、聚类结果 有效性高成为最受关注的模糊聚类算法之一该算法在模式识别【、图像处理f 1 1 川2 1 、数据挖掘 【13 】等领域中获得了广泛的应用即便如此，该算法仍不是无懈可击的，还遗留了很多问题亟待 解决 7 模糊聚类中若干问题的研究 尽管f c m 算法是一种无监督的机器自学习算法，但是，有两个参数模糊加权指数m 和聚 类的类别个数c 在进行聚类分析前必须给出合适的赋值，否则将影响f c m 算法的分析效果，直 接影响聚类分析结果的合理解释【1 4 1 此外，传统的f c m 算法默认欧氏距离为样本间相似性度 量，并且通过计算每个聚类内所有样本的平均值作为聚类中心代表每个聚类，这一绝对性的做 法使得其对某些特殊数据类型的聚类结果并不令人满意下文中将通过实验结果对此说明归 纳起来，f c m 算法存在以下弱点： ( 1 ) 模糊加权指数m 取何值才能保证f c m 算法获得合理的模糊聚类： ( 2 ) f c m 算法中聚类类别个数c 要求事先给定一方面需要有关数据集的先验知识， 从而影响了聚类算法的无监督性能，另一方面存在聚类结果有效性判决问题，包 括分类的正确性和聚类个数的合理性； ( 3 )由于目标函数是非凸的，很容易陷入局部极值解或鞍点而得不到最优解甚至满意 解，同时大数据量下算法耗时较多： ( 4 ) f c m 算法只能检测类内紧致、类间分离性较好的球形聚类子集这就使得f c m 算法不能直接检测不规则结构的模式子集，而且敏感于噪声点 这几个方面一直是人们对f c m 算法研究的热点，有些问题已经得到了较为理想的解决参 数m 的引入必然会对聚类分析和f c m 算法产生影响，最直接的影响是把数据集的硬划分扩展 为模糊划分，而且取不同的m 值就会产生不同模糊程度的数据划分因此，b e z d e k 认为参数所 控制着各个样本在c 个模糊类间的分享程度范九伦、吴成茂在【”1 中从数学角度给山了模糊加 权指数m 的新的解释，指出隶属度实际上是一个“等距加权值”这种解释有助于更好的理解模 糊聚类的目标函数和硬聚类的目标函数之间的联系和区别、以及模糊聚类中的模糊加权指数在 聚类中的作用现有文献中很少有内容涉及模糊加权指数m 的优选问题，因此，人多数用户在 调用f c m 算法时只是对m 简单赋值，有时索性固定m = 2 如何确定最优的聚类个数，这属于聚类有效性问题讨论的范畴关于聚类有效性问题的研 究也已经有了很丰硕的成果，从1 9 7 4 年研究者们提出了许多有效性函数，本文将在第三章中给 出详细介绍 鉴于f c m 算法的高效性和广泛的应用，人们在此基础上对其进行了发展和深化，提出了 许多模糊c 均值类型的算法如模糊c 线( f c l ) 、模糊c 面( f c p ) 、模糊c 壳( f c s ) 等聚类算法， 分别实现了对呈线状、超平面状和“薄壳”状结构模式子集( 或聚类) 的检测；以及可能性c 均 值算法口c m ) 1 1 6 1 、基于核方法的模糊c 均值算法( c f c m ) f m 8 等【2 喇 模糊c 均值聚类算法通过可能性约束条件使数据点在所有类中的隶属度之和为1 ，即假定 每个样本对聚类的影响力是相同的模糊c 均值聚类算法的隶属度适合解释共享的概率，但是 这个隶属度对于直观上的属于程度概念不是常常一致相符的而且，模糊c 均值聚类算法对噪 8 南京航空航天大学硕士学位论文 声或野值敏感为了克服f c m 的这个缺点，k r i s h n a p u r a m 和k b l l e f l l 6 】放弃了f c m 的可能性约 束条件，构造了一个新的目标函数，提出了可能性c 均值聚类( p o s s i h i l i t i ccm e a n s 。p c m ) p c m 能够聚类包含噪声或野值点的数据，使噪声数据具有很小的隶属度值，因而噪声对聚类的影响 可以忽略( 图1 1 ) 两位研究者在文献【1 6 】中通过将p c m 中的欧氏距离改变为马氏距离，得到 t h ep o s s i b i l i t i cg u s t a f s o n - k e s s e l 口g k ) a l g o f i t h r a ；通过借助f c s 算法应用的距离得到可能性c 球壳算法( t h ep o s s i b i l i t i cc - s p h e r i c a ls h e l l s ( p c s s ) a l g o r i t h m ) ：并通过实验证明p g k 对于检测交 错线状数据集有很好的效果( 图1 2 ( b ) ) ，而p c s s 能够成功分离两个同心圆环状的数据集( 图 1 2 ( d ) ) 但是p c m 对初始化条件很敏感，常常会导致一致性聚类结果p c m 重视了典型性思 想，从而减少了噪声对聚类的影响，但它忽略了隶属度，隶属度可以使类中心和数据紧密联系 在一起 ( b )( c ) 图1 1p c m 算法对噪声的鲁棒性 图( a ) 为原始数据，( b ) 为添加噪声后f c m 算法的聚类结果，( c ) 为添加噪声后p c m 算法的 聚类结果 ( a )c o )( c )( d ) 图1 2p c m 算法对任意形状数据集的聚类结果图 ( a ) 、( c ) 为原始数据，( b ) 、( d ) 为p c m 聚类结果 核方法与谱方法聚类都是在类与类之间产生非线性的分割超曲面核的应用相当于把数据 集通过一个非线性函数映射到一个高维空间，称为特征空间，通过在特征空间形成一个线性分 割从而在原空间形成非线性分割i i9 】核方法在f c m 中的应用主要分为两类：距离的核化与在 特征空间中进行聚类距离的核化( k f c m ) 是将原始f c m 算法中的欧氏距离通过核距离表达出 来，其实质还是在原始空间对样本进行聚类；而在特征空间中进行聚类通过一个非线性函数将 样本映射到特征空间，在特征空间上直接应用f c m 算法对原始样本的映像进行聚类后一种 方法增加了空间的维数，容易造成为数灾难，因而前一种方法的使用更为常见 9 模糊聚类中若干问题的研究 n z a h i d 和o a b o u e l a l a 等将f c m 算法与k 近邻方法联系起来【2 1 1 ，首先通过k 近邻原则 将原始数据集划分成一些子集，再把这些子集作为f c m 算法的初始划分通过迭代求得最优划 分这就使得f c m 算法摆脱了对聚类数目c 的先验要求，而且对于重叠交叉的数据集能得到比 f c m 算法更理想的聚集结果2 0 0 5 年，z h o us h u i g e n g 和z h a 0y u e 2 2 1 等提出n b c 算法 ( n e i g h b o r h o o d b a s e dc l u s t e r i n ga l g o r i t h m ) 根据数据的近邻的特点检测数据的聚类n b c 算法 的核心是n d f ( n e i g h b o r h o o d - b a s e dd e n s i t yf a c t o r ) ，用来计算局部密度n b c 算法对任意形 状、不同密度的数据聚类都有效，需要的输入参数比基于密度的方法要少 由于凝聚式层次聚类算法在计算上简单、快捷，而且能够得到相近的最终结果，所以绝大 多数层次聚类方法都是凝聚式的，对于层次聚类算法大都是在聚类间相似性度量的定义上的改 进e f e n d in n a s i b o v 和g o z d eu l u t a g a y l 2 3 j 提出了一个对于噪声更为稳定的f j p ( f u z z yj o i n t p o i n t s ) 算法该算法的基本思想是根据样本点与样本点之间的距离计算模糊关系矩阵，对于某 一口( o ，1 】建立口一截集和等价类此时，这些口一等价类决定了模糊聚类的每个口一截集并 非对每个口( o ，1 】都计算口一截集，而是只计算影响聚类个数的口对应的口一截集最终的截 集是由口的取值区间上的最大值确定的f j p 算法已被证明能成功检测团装数据集及流形状数 据集，即使添加噪声点后，f j p 算