（应用数学专业论文）fcm算法参数研究及其应用.pdf

摘要 模糊c 一均值( f c m ) 聚类算法是非监督模式识别中应用最为广泛的算法之一。 由于该算法是通过极小化目标函数而求得最优解的，而在目标函数中涉及到的两 个重要参数( 即加权指数m 和聚类数c ) 值必须事先确定才能得到与数据集结构相 符合的划分结果，因此涉及到这两个参数的优选问题。 为此，本文首先提出划分模糊度的概念，并在此基础上借助模糊决策思想提 出了加权指数m 的一种优选方法。同时，又由于f c m 算法适用于球型分布的数据 集分析，为此本文在定义球型半径之后通过对隶属度的重新定义，提出了基于划 分模糊度的聚类有效性函数，实现了聚类数c 的自适应确定。实验结果表明本文提 出的有关参数肌和参数c 的确定方法是有效的。 最后，本文利用f c m 算法对微阵列基因表达数据进行了分析，并把所得结论 与基于模型的微阵列基因表达数据分析所得结论进行了比较，结果表明该方法是 有效的，从而为f c m 算法开辟了新的应用领域。 关键词：模糊c 均值( f c m ) 算法模糊聚类划分模糊度加权指数m聚类 有效性微阵列基因表达 a b s t r a c t f u z z yc m e a n ( f c m ) c l u s t e r i n ga l g o r i t h m i so n eo ft h e w i d e l ya p p l i e d a l g o r i t h m s i n u n s u p e r v i s e d m o d e lr e c o g n i t i o nf i e l d s a sw e l lk n o w n ，t h eo p t i m a l s o l u t i o no ff c m a l g o r i t h mi so b t m n e db ym i n i m i z i n gt h eo b j e c t i v ef u n c t i o n ，i nw h i c h t w oi m p o r t a n t p a r a m e t e r s ，f u z z yw e i g h t i n ge x p o n e n t ma n dt h en u m b e ro fc l u s t e r s c ， i si n v o l v e dh o w e v e r ，ap o o rp a r t i t i o n i n gr e s u l t w i l lb eo b t a i n e df o rt h e i m p r o p e r c h o i c e sv a l u e so fb o t hma n dc t h e r e f o r et h ep r o b l e mo fo p t i m i z a t i o no fb o t hm a n dci sd e s e r v e dt os y s t e m a t i cs t u d y f o rt h i sp u r p o s e ，b a s e do n p a r t i t i o nf u z z yd e g r e ea n df u z z yd e c i s i o n ，am e t h o d o f t h eo p t i m a lc h o i c ef o rp a r a m e t e r f n i s p r e s e n t e di nt h i sp a p e r t h e nb yd e f i n i n go f r a d i u so fd a t as e tt ou p d a t et h em e m b e r s h i pd e g r e e ，ac l u s t e rv a l i d i t yf u n c t i o nb a s e do n t h e p a r t i t i o nf u z z yd e g r e e i sa l s o p r o p o s e d e x p e r i m e n t a l r e s u l t si l l u s t r a t et h e e f f e c t i v e n e s so ft h eo 州m a lc h o i c eo fma n dc a t l a s t ，f u z z y c m e a n c l u s t e r i n g m e t h o di su s e dt o a n a l y z em i c r o a r r a yg e n e e x p r e s s i o nd a t ai no r d e r t od e t e c td i f f e r e n t i a l l ye x p r e s s e dg e n e c o m p a r e d 、i mt h er e s u l t s o fm o d e l b a s e dc l u s t e r a n a l y s i s o fm i c r o a r r a y g e n e se x p r e s s i o nd a t a ，o n r r e s u l t s i n d i c a t et h a tf u z z yc l u s t e r i n gc a nb eau s e f u lt o o lt oe x p l o i td i f f e r e n t i a lg e n ee x p r e s s i o n f o rm i c r o a r r a yd a t a ， k e yw o r d s ：f u z z yc - m e a n ( f c m ) a l g o r i t h m d e g r e e w e i g h t i n ge x p o n e n t m e x p r e s s i o n f u z z yc l u s t e r i n g c l u s t e r i n gv a l i d i t y p a r t i t i o nf u z z y m i c r o a r r a yg e n e 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人己经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名趣垄日期：伊 工一彤 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文在解 密后遵守此规定) 本人签名： 导师签名 拯兰 刭三孕旦 日期： 婴! ：! ! ：绶 日觌：渺j ip 、2 一一 苎二里堑丝 ! 第一章绪论 1 1 聚类分析简介 随着现代社会科学和自然科学的相互渗透，信息科学以其强大的生命力在所 有边缘性学科中脱颖而出，而模式识别则是信息处理中的一种极为重要的手段。 模式识别诞生于2 0 世纪2 0 年代，随着4 0 年代计算机的出现，5 0 年代人工智能的 兴起，模式识别在6 0 年代初迅速发展成为一门学科。它所研究的理论和方法在很 多学科和技术领域得到了广泛的应用，从而推动了人工智能系统的发展，扩大了 计算机应用的可能性。几十年来，模式识别研究已取得了丰硕的成果，在很多领 域得到了成功的应用。但是，由于模式识别涉及到很多复杂的问题，因此，现有 的理论和方法对于解决这些问题还存在不足之处，这就要求我们进一步的研究探 讨。 模式识别包括监督模式识别和非监督模式识别。监督模式识别是指已知某些 样本的分类情况，用这些已知样本对这些分类系统进行学习( 训练) ，使得分类系 统能够对这些已知样本正确分类，然后用已学习好的分类系统对未知样本进行分 类。监督识别需要知道学习样本的先验知识。与监督识别相对应的是非监督识别， 它不需要知道样本的先验知识，也不需要获取训练样本。 聚类分析就是无监督模式识别中的一个重要分支。所谓聚类就是按照事物间 的相似性进行区分和分类的过程。聚类分析则是一种数据划分或分组处理的重要 手段和方法，其操作的目的在于将特征空间中一组没有类别标志的矢量按某种相 似性准则划分到若干个子集中，使得每个子集代表整个、某个或某些特征和性质。 从这个意义上讲，聚类又称为无监督分类。“人以群分，物以类聚”，聚类是一个 古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必 须区别不同的事物并认识事物间的相似性。 聚类分析技术大体上分为硬聚类方法、软聚类方法和可能性聚类方法。硬聚 类方法将样本对各个类的隶属度取成0 和1 两种值，取值为o 表示该样本不属于 这一类，取值为1 表示该样本属于这一类。因此这种分类的类别界限是分明的而 实际上大多数对象并没有严格的属性，它们在性态和类属方面存在着中介性，适 合进行软划分。模糊聚类方法【2 1 将样本对各个类的隶属度扩展到i o 。l ，该类方法是 基于z a d e h 在1 9 6 5 年提出的模糊集理论。模糊聚类顾及到的样本与样本之间的联 系，认为每一样本与各个聚类中心都有一个隶属关系。模糊聚类能够有效的对类 与类间有交叉的数据集进行聚类，所得的聚类结果明显优于硬聚类。与硬聚类算 法相比，模糊聚类算法的收敛速度要慢的多。 三墅至堕王至燮堂堡主! ! ：苎：堕竺童茎丛壅垄苎璧塑 随着计算机的发展和实际问题的需要，基于目标函数的聚类方法已成为聚类 分析的主流。这一方面是由于将聚类问题表述成优化问题易于与经典数学的非线 性规划领域联系起来，可用现代数学方法来求解。另一方面是由于算法的求解过 程比较容易用计算机来实现。 模糊聚类理论的发展推动了其在生产实践中的应用，反过来实际应用的需求 又促进了模糊聚类理论的不断丰富和完善随着理论的发展，模糊聚类已经在众多 的领域获得广泛的应用，并取得了令人满意的效果和可观的效益其应用范围涉及 到通讯系统中的信道均衡、矢量量化编码中的码书设计、时间序列的预测、神经 网络的训练、参数估计、医学诊断、天气预报、食品分类、水质分析等领域。此 外，在图像处理中被用于图像分割【35 2 堋+ “1 ，图像增强【4 1 ，图像压缩【5 1 等；在模式 识别中，被用于语音识别【6 ，雷达目标识别等。 1 2 基于目标函数的模糊聚类中参数的研究进展 自从z a d e h 在1 9 6 5 年提出的模糊集理论问世后，模糊集理论率先在模式识别 领域得到应用。由于模式识别中固有的模糊性，所以将模糊集引入模式识别获得 了巨大的成功。以模糊集为基础处理聚类问题是由b e l l m a n ，k a l a b a 和z a d e h 吲于 1 9 6 6 年首先提出的。第一个系统地表述和研究模糊聚类的是著名学者r u s p i n i ! 加川】。 1 9 6 9 年，r u s p i n i 定义了数据集的模糊划分概念。与此同时，z a d e h “j ，t a m u r a 等 人提出了基于相似关系和模糊关系的聚类方法，这类方法分为聚集法和分裂法， 目前已提出了许多不同技巧来应用这一思想1 5 “。从七十年代到八十年代，人们对 模糊关系矩阵及其传递闭包等问题进行大量的研究。到九十年代，尽管还有人做 这方面的研究，但研究热潮已逐渐退却。此外，人们也试图用图论的方法研究模 糊聚类，如1 9 7 4 年d u n n ”】利用图论分析t a m u m 等人提出的聚类方法；1 9 9 2 年丁 斌1 5 7 1 提出动态模糊图最大树聚类法；1 9 9 3 年，z h e n g g u w u 和r l e a h y 0 s 提出最优 图论方式的聚类方法。在将硬聚类方法推广到模糊聚类方法情形方面，人们也做 了许做工作，如将硬聚类中常用的k 一近邻法推广到模糊聚类。1 9 8 5 年t a og u 和 b u b u i s s i o n m 1 提出松弛k 一最近邻法，同年k i l l e r 等人( 1 7 i 提出了一种模糊k 一最近邻 法，1 9 9 1 年b e r e a u 和b u b u i s s i o n 6 提出了另一种形式的模糊k 一最近邻法。人们也 提出了其它一些模糊聚类方法，如1 9 8 5e s o g b u e 【1 8 】提出了动力学模糊聚类方法， 1 9 8 8 年m a n t a r a sv a l e r d e l l 9 1 基于难以辨别关系提出了几种模糊聚类方法。 上面我们叙述了一些模糊聚类方法，由于各种各样的原因，这些方法的应用 不是很广泛。实际中受到普遍欢迎的方法是基于目标函数的模糊聚类方法。基于 目标函数的模糊聚类方法首先是由r u s p i n i f l 0 1 1 1 提出的，但真正有效的方法是由 d u n n 2 0 _ 2 “2 习给出的。1 9 7 4 年d u n n 将硬聚类c 均值算法推广到模糊情形，同年 第一章绪论 b e z d e k l 2 1 将d u m a 的方法般化，建立了模糊c 一均值算法理论，1 9 8 0 年b e z d e k t 2 2 3 1 证明了模糊c - 均值聚类算法的收敛性并证明了模糊c 均值聚类算法与硬c - 均 值聚类算法的关系。从此，基于目标函数的模糊聚类算法蓬勃发展起来。目前已 形成了庞大的体系。人们从不同的角度对基于目标函数的模糊聚类算法进行了研 究，下面我们主要此类算法中参数的研究进行综述。 1 2 1 加权指数珊的研究 在模糊聚类目标函数 ，。：1 m 中，b e z d e k l 2 j i 3 i 入了加权指数m ，使d u m a 的聚类准则变成m = 2 的特例。有人认为从数学上看参数川的出现不自然也没有必 要【2 ，但是对于从硬聚类准则函数推广到目标函数，如果不给隶属度乘个权重， 这种推广则是无效的。参数m 又称为平滑因子，控制着模式在模糊类间的分享程 度f 2 】，因此要实现模糊聚类就必须选定一个合适的肌值，然而最佳m 的选取目前 尚缺乏理论指导。 b e z d e k l 2 4 给出过一个经验范围1 1 拂s5 ：后又从物理解释上得出m = 2 最有 意义；c h a n 等人【25 】从汉字识别的应用背景得出m 的最佳取值应在1 2 5 1 7 5 之间； b e z d e k 等人【2 2 从算法收敛性角度出发，得出m 的取值与样本数目n 有关，建议肺的 取值要大于n ( h 一2 ) ；p a l 等人 2 q 则从聚类有效性的实验研究中得到m 的最佳选取 区间为 1 5 ，2 5 】，在不作特殊要求的情况下可取区间中值m = 2 。 上述有关m 的取值范围，大都来自实验和经验，均为启发式的，一方面不够 系统，另一方面没有给出具体的优选算法，此外，也缺乏最优m 的检验方法。这 一系列开放问题，都值得进一步的探索，以便奠定m 优选的理论基础。 1 2 2 聚类数c 的研究 对于给定的数据集，如果己知有聚类结构，则需要用算法来确定这个结构。 而大多数聚类算法需要事先给定数据集的聚类数，如果聚类数选取的不合适，会 使划分结果与数据集的真正结构不相符，从而导致分类失败。关于数据集的最佳 聚类数确定问题属于聚类有效性研究的范畴。 关于聚类有效性问题的研究可分为以下三种研究途径， ( 1 ) 基于数据集的模糊划分 这类方法基于这样的观点，一个能较好分类的数据集应该是较“分明”的。 因此，模糊划分的模糊性越小，聚类的结果越可靠。基于这种观点的第一个聚类 有效性函数是由z a d e h l 2 7 提出的分离度，但正如b e z d e k l 2 1 指出的，分离度并不能用。 1 9 7 4 年b e z d e k 2 8 1 借助d u r r a l l 9 】提出的划分系数概念，提出了第一个实用的模糊聚 三堕j 茎皇! 型垫查堂堡主笙苎：鉴坚童墼竺塞墨茎窒望 类有效性函数并提出了与划分系数密切相关的另一个聚类有效性函数戎0 分熵。 w i n d h a m 2 9 1 利用隶属度的最大值定义了比例系数，g u n d e r s o n 3 川利用划分系数成功 地对星云域数据进行了分析，从而确立了这类方法的地位。1 9 9 8 年t r a u w a e r t 3 i i 分析指出划分系数的最大值并非总是对应最好的分类，这说明划分系数也具有很 大的局限性。范九伦”2 】等用可能性分布的观点解释划分系数，提出了一个新的有 效性函数，其性能明显地优于划分系数。 ( 2 ) 基于数据集的几何结构 这类方法建立在这样的观点之上，一个能较好分类的数据集，每一个子类应 该是紧致的并且子类与子类应尽可能分离的，以紧致性和分离性的比值作为聚类 有效性标准。对于紧致性和分离性定义的不同，产生了不同的公式。应用数据集 本身的特征，d u n n 定义了分离性指标并证明了该分离性指标大于1 时，数据集具 有唯一的聚类结构。，g u n d e r s o n 3 0 】定义了分离系数。1 9 7 9 年d a v i c s 和b o u l d i n 利 用类与类间的f i s h e r 距离定义了分离性测度。基于数据集的模糊c 均值聚类g a t h 和g e v a f 3 3 】引入了模糊超体积和模糊密度的概念，定义了与数据集结构非常密切的 聚类有效性函数。1 9 9 1 年x i e 和b e n i 利用目标函数定义了一个称之为x i e b e n i 指标的聚类有效性函数。 ( 3 ) 基于数据集的统计信息 这类方法是基于硬聚类提出的，他们建立在这样的观点上，最佳分类对应的 数据结构所提供的统计信息是最好的。基于数据集的类内统计信息和类间统计信 息，v o g e l 和w o n g 3 4 提出了p f s 聚类方法。j a i n 和m o r e a m 【3 5 】借助统计中的b o o t s t r a p 技术确定聚类有效性。基于信息论中的a i c 准则，z h a n g 和m o d e s t n o l 3 6 定义了一 个聚类有效性函数。1 9 9 2 年b e n 和l i u 3 7 1 基于最大熵原则提出了一种无偏差聚类 算法和熵形式的聚类有效性函数。1 9 9 7 年r o b e r t s 3 8 运用最大相关原则和标量空间 滤波技术提出了一个聚类有效性函数。 基于数据集模糊划分的有效性函数具有简单、运算量小的优点，但与数据集 的结构特征缺少直接联系：基于数据集的几何结构的有效性函数也数据集的结构 密切相关，但表述较复杂，运算量较大；基于统计信息的有效性函数的性能与数 据集分布密切相关，但依赖于数据分布与统计假设的一致性。 以上三种途径是聚类有效性问题研究的主流。 目前聚类有效性问题的研究范围已拓广到椭球状、线状和壳状数据p j ，还提 出了基于可能性的聚类有效性函数f 4 0 j 。此外，也提出了一些针对噪声数据有效性 函数。不过球状分布数据的模糊分类问题是最基本的，因为这类问题的研究结果 可直接推广到其它数据的分析上。 有效性问题是聚类分析的瓶颈，该问题的解决将会对聚类分析的成功应用产生十 分深远的影响。 第一章绪论 1 3 模糊聚类算法在微阵列基因表达中的应用 生物电子学【4 l j 是生命科学和信息科学相互交叉渗透和综合而成的前沿科学， 它不仅推动了生命科学和医学的发展，而且对信息科学的发展也起了重要作用。 伴随着非典型肺炎对人类生命的侵袭促使我们须对基因功能有更多，更深刻的了 解，以揭开生命的奥妙。而微阵列( m i c r o a r r a y s ) 技术则是一种新的、能够系统地、 全面地探索基因组功能的有力手段，它不仅能同时比较不同标本的基因表达( 生 物有机体的遗传信息都是以基因的形式储存在细胞的遗传物质d n a 分子上的，而 d n a 分子的基本功能之，就是把它所承载的遗传信息转变为由特定氨基酸顺序 构成的多肽或蛋白质( 包括酶) 分子，从而决定生物有机体的遗传表型。这种从 d n a 到蛋白质的过程叫做基因的表达) 水平的差异，也能够提供某一基因或某一 群基因的表达模式与其他基因的表达模式相互间关联的信息。 微阵列技术主要是指由成千上万个d n a 样品或寡核苷酸，密集排列于硅片、 玻璃片、聚丙烯或尼龙膜等圊相支持物上，再与模板在严格条件下进行杂交，最 后由激光共聚焦显微镜等设备获取图像信息，通过计算机分析处理获得信息的技 术集合，微阵列又常称为微排列或微点阵。目前新兴的d n a 芯片是微阵列中最主 要的一种。 面对d n a 微阵列产生的海量数据，需要人们进行数据挖掘以识别基因和对基 因表达进行研究。对于采集到的信息进彳亍大量处理的一个重要模块就是分类，即 把数据划分为一系列有意义的子集，这在数学上称为聚类。聚类增强了人们对客 观现实的认识，是概念描述和偏差分的先决条件。聚类技术主要包括传统的模式 识别方法和数学分类学，如决策树归纳、贝叶斯分类、神经网络技术、k 均值聚 类、基于知识的案例推理、遗传算法等。以上方法都属于硬聚类。事实上由于研 究对象的模糊性用软聚类则显得更为合适。 研究对象之所以带有模糊性是因为： ( 1 ) 基因表达水平的显著性本身所具有的模糊性，即具显著性从高到低有一 系列中间过度状态。因此用经典的明晰集合来刻画是不合适的，用模糊集合论来 刻画就显得顺理成章。经典的集合论中隐含有一个假设，即一个研究对象，或者 完全具有某种性质，或者完全不具有某种性质，即或者完全属于某个集合，或者 完全不属于某个集合。这就忽略了研究对象在量上具有这种性质的程度。 ( 2 ) 由于现阶段技术能力和手段有限，或者受环境条件及各种因素的影响， 造成了人们对研究对象的认识不充分，获取的信息不足而对事物认识产生模糊性。 建立在z a d e h 提出的模糊集理论基础之上的模糊聚类则得到了样本属于各个 类别的不确定性程度，表达了样本类属的中间性，即建立起了样本对于类别的不 硒安电子科技火学硕士论文：f c m 参数研究及其应用 确定性描述，客观地反映了现实世界，因此用模糊聚类来解决此问题有其内在的 必然性和合理性。其中模糊c - 均值聚类技术在此领域应用最为广泛。 用模糊聚类来发现基因表达的差异性及其显著性只是模糊聚类应用于模式识 别领域的一小分支。随着理论的进展、应用的发展，模糊聚类会为人类认识自然、 认识自身开创新的天地。 1 4 本文的主要研究成果及内容 尽管基于目标函数的模糊聚类理论及其应用已被许多研究人员进行了讨论， 但距问题的圆满解决还有很大的差距。其中，有关聚类目标函数中参数的优选尚 需进一步的研究，为此，本文将研究重点放在f c m 算法的参数优选上，此后又把 此算法应用于微阵列基因表达数据分析。具体研究成果归纳起来包含以下三个方 面。 1 。提出一种基于划分模糊度与模糊决策的加权指数m 的优选方法。 2 提出基于划分模糊度的聚类有效性函数。 3 基于f c m 算法的微阵列基因表达数据分析。 本文共分成四章。第一章为绪论，介绍了聚类分析；概述了基于目标函数的 模糊聚类中参数的研究进展及其意义、在微阵列基因表达数据中的应用及本文所 取得的主要成果和内容安排。第二章介绍了聚类分析、硬c - 均值聚类算法、模糊 c 一均值聚类算法( f c m ) 及此算法的参数优选研究。第三章首先提出了划分摸糊 度，进而在此基础之上提出了f c m 算法中模糊加权指数m 优选的一种新方法、结 合模糊划分信息和数据集的几何结构提出了一种新的聚类有效性函数，最后对隶 属度进行了解释。第四章把f c m 算法应用于微阵列基因表达数据分析，取得了很 好的结果。 第二章模糊c - 均值( f c m ) 算法参数研究 第二章模糊c 一均值( f c m ) 算法参数研究 2 1引言 在日常生活、生产、科研工作中，经常要对研究对象进行分类。研究和处理 给定对象的分类方法称为聚类分析( c l u s t e r i n ga n a l y s i s ) 。聚类分析是数理统计中 研究“物以类聚”的一种多元分析方法，即用数学定量地确定样品的亲属关系， 从而客观地分型划类。在普通聚类分析中，类别之间是清晰的，分类集合中任意 两个元素要么等价，要么不等价。事实上，有许多事物的类之间无明显的划分， 它们相互之间的关系更多的是模糊关系。在多数场合，一组事物是否形成一个类 群、一个事物是否属于某一个子类，都不是很明确的，而是一个聚类、隶属程度 的问题，因此，用模糊集合的理论和方法来描述和处理聚类问题更为自然、方便。 用普通关系的聚类分析方法就不宜对具有模糊关系的事物分类。 把模糊数学方法引入聚类分析，便产生模糊聚类分析。模糊聚类分析方法大 致可分为两种：一是基于模糊关系的模糊聚类法。另一种称为非系统聚类法，它 是先把样品粗略的分一下，然后按其最优原则进行分类，经过多次迭代直到分类 比较合理为止，这种方法也称为逐步聚类法。比较典型的有模糊c - 均值聚类算法。 本章的研究内容具体安排如下： 在2 , 2 中，介绍了硬c 均值聚类( h c m ) 算法。 在2 3 中，介绍了模糊c 均值聚类( f c m ) 算法，及其广为研究应用的原因。 在2 4 中，分析了加权指数m 对f c m 算法的影响，说明了对参数m 优选研究 的必要性。 在25 中，介绍了聚类有效性的含义及聚类数c 的研究方向。 在2 , 6 中，对本章内容进行了小结。 2 2 硬c 一均值聚类算法 硬c 一均值聚类( h c m ) 算法是经典的硬聚类算法之一，能够对超椭球状的数 据进行分类。 设x = k ，x ：，矗 匕r5 ，其中_ = b 。工：f ，工，r r 。是数据集，n 是数据集 中元索的个数，c 是聚类中心数( 1 0 1 i c 上述数学规划问题可通过如下的算法来求解； 起始迭代标准s 0 ，初始分类矿( 0 i ，和k = o ； 步骤1 用下述公式计算u ( 。) “班记由巍商嘛忙 步骤2 用下述公式计算矿( + 1 ) n “口 ) x ， wv ，积+ 1 ) = 艺_ 忙) 步骤3 用一个矩阵范数忙1 1l l 较v ( ) 与矿( 川) ，若 l 矿以+ 1 一矿。| | 占 则停止迭代，否则置k = t + 1 ，转向步骤1 a 上述方法也可以用初始化聚类中心u ( o ) 来作为起始。 2 3 模糊c 一均值聚类算法 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) d u r r a 依据r u s p i n i 定义的集合的模糊划分概念，将硬c 均值聚类算法推广到 模糊情形，如果不给隶属度“乘一个权重，这种推广是无效的。而最简单和最直 第二章模糊c - 均值( f c m ) 算法参数研究 接的方法是将“。变成“；，由此d u n n 给出下面的模糊c - 均值聚类( f c m ) 算法。 m i n j ： ，c ) = 妻量“；d ； i = 1 j = l 使得主“。= 11 j n “。【o ，l 】，1 j s ， 1 i c 玎 0 1 i c j ；l ( 2 8 ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) b e z d e k 将上述表达推广到更一般的情形，给出模糊聚类的一般描述。模糊聚 类问题可表示成下面的数学规划问题： 问题f c l ： m i n j 。，妙，c ) = “? d ； 使得壹“。= 11 j h 忙1 。 “【0 , 1 1 ，1 ，胛，1 s i c n 即 “驴 0 1 i ss j = l ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) 这里是权重因子( m 1 ) ，b e z d c k 给出如下算法来解上述的数学规划问题。 起始迭代标准占 0 ，初始分类矿( 0 ) ，和k = 0 ； 步骤1 用下述公式计算u ( ) 如果夥，d 口( 七) o ，则有 如果存在，r ，使得d 口 ) = o ，则令：“口g ) = 1 r s 时i ，, u 0 ) = o 步骤2 用下述公式计算y 如“) ( 2 1 6 ) 土州 钉 、= 够一 生幻 ，l 。脚 | l f 1 0 西安电子科技犬学硕士论文：f c m 参数研究及其应用 v i v 。 + 1 ) = 量“孑辑b ， ，= l “孑 ) ( 2 。1 7 ) 步骤3 用一个矩阵范数| | | 】比较矿( ) 与矿( 川) ，若 l 眇以+ 1 ) 一矿扯) s ( 2 1 8 ) “| | 则停止迭代，否则置k = 七+ 1 ，转向步骤1 。 上述方法也可以用初始化聚类中心u ( o ) 来作为起始。 该算法是收敛的+ 其解点是问题f c l 的局部最小点或鞍点。对于满足下述 条件的解集q ，上述算法可以收敛到一个局部最小点。 vuem 肛，j m p ，v ) 厶妙，v + ) v v r ”，j 。妙+ ，v ) ，。，v + ) ( 2 1 9 ) m m 表示满足条件( 2 1 3 ) ，( 2 1 4 ) ，( 2 1 5 ) 的矩阵集合。 f c m 算法是目前比较流行的一种模糊聚类算法，究其原因大致由以下几个方 面：首先模糊c - 均值泛函j 。仍是由传统的硬c 一均值泛函，l 的自然推广，我们知 道，是一个应用十分广泛的聚类准则，对其在理论上的研究已经相当完善，这 就为l 的研究提供了良好的条僻：。数学上看，j 。与r 。的希尔伯特空间结构( 正 交投影和均方逼近理论) 有密切的关系，因此l 比其它泛函有更深厚的数学基础。 最后，也是最重要的是它不仅在许多领域获得了非常成功的应用，而且以f c m 算 法为基础，人们提出基于其它原型的模糊聚类算法，形成了一大批f c m 类型的算 法：如模糊c 线( f c l ) 、模糊c 一面( f c p ) 等聚类算法，分别实现了对呈线状、 超平面状结构模式子集( 或聚类) 的检测。 2 4 加权指数m 对f c m 算法的影响 为了把硬c 一均值聚类中的目标函数扩展到模糊情形，b c z d e k 引入了加权指数 m ，给出模糊c - 均值类型聚类目标函数的普遍形式p 。妙，尸l m b ，m ) ) 。f c m 算 法通过极小化，。而获得最佳聚类结果矽+ ，v ) ，如果不考虑隶属函数和聚类原型与 第二章模糊c - 均值( f c m ) 算法参数研究 1 l 参数的嵌套隐含关系，有 掣笋= 壹i - 1j 蚍- 1 ) m - l o g ( , u 。) 坩 = 壹兰k 。，) k ，。1 0 。) 2 】 ( 2 2 f，j j k ，“p 口j 2j ( 2 从式( 2 ) 可知， 。将随i = 1i 2 的1 增l 加o g 而( 单调递减。对应不同的m 值，显然2 有0 020)20 jm 不同的最佳模糊c _ 戈0 分，因此，f c m 算法对加权指数m 存在聚类有效性问题。也 就是说需要确定m 为何值时m l n j 。对应的聚类结果是最有效最合理的。可见参数 m 对f c m 算法有重要影响。 为了研究参数m 对f c m 算法性能的影响，首先讨论对应于m 可行解两端的情 况，有如下定理： 定理21 ：对于m f i ，。) 的f c m 算法，存在以下情况： 当m 一1 + 时，f c m 算法退化为h c m ； 当m = 1 时，f c m 算法变成h c m ； 当聊寸o o 时，f c m 算法的聚类结果是最模糊的，即“f = 。 从目标函数以及划分矩阵和聚类原型的迭代公式出发，易证定理2 4 1 成立。 为了衡量模糊聚类结果的模糊程度，b e z d e k t 2 】仿照s h a n n o n 信息熵的形式定义 了划分熵的公式： 定义2 1 ：对于给定的聚类数c 和划分矩阵u ，其划分熵定义为 积c)-去妻兰2109ah l o g ( 形。j21i=l=1 ， 。p ，c ) = 圭i 彤。i ( 2 ) n ，p q ， 其中a ( 1 ，。o ) 为对数的底数，且约定心= 0 时，有心l o g 。) = 0 。对于模糊 聚类问题，我们当然不满足于数据的硬划分，还想获得样本间的相近信息。在此 前提下，样本集的划分越分明就越有利于分类，因此，对于给定的m 值，总希望 模糊聚类的划分熵越小越好。 加权指数聊影响f c m 算法的性能，因此也必然对聚类结果的划分熵产生影 响，有关影响可由定理2 4 2 来表述。 定理2 2 对于1 o 且= j ，那么对于 月= 2 ，0 2 的情况，对 于任意足够小的s 0 ，当且今当m 2 的f c m 的目标函数是否存在鞍点? 从实验的角度得出的经验法则是，给定打，选择 m h ( h 一2 ) ，这样至少可以避免由定理2 3 提供的鞍点。 综上所述，参数m 对f c m 算法有重要影响，其影响主要是：统一了h c m 算 法和f c m 算法：决定聚类的模糊程度，控制样本在类间的分享程度；抑制噪声； 影响目标函数的凹凸性及算法的收敛性等。因此，加权指数m 是f c m 算法中的 个重要参数。 2 5 模糊聚类有效性 对于给定的数据集，首先需要判断有无聚类结构，这属于聚类趋势研究的课 题，如果已经确认有聚类结构则需要用算法来确定这些结构，这属于聚类分析研 究的课题。得到聚类结构后，则需要分析聚类的结构是否合理，这属于聚类有效 性研究的课题，对聚类分析而言，有效性问题又可转化为最佳类别数c 的确定【2 】。 历史上有关聚类有效性问题的研究大都是基于硬c 均值和模糊c 均值算法。 d u b e s 4 4 j 牙口j a i n 【4 5 】曾对8 0 年前的研究做过评述。现有的聚类有效性函数按其定义 方式可分为：基于数据集集合划分的、基于数据集几何结构的和基于数据集统计 信息的。这3 类的理论基础和特点均列于下表。 比较项目基于模糊划分基于几何结构基于统计信息 好的聚类分析对应每个子类应当是紧最佳分类对应的数 理论基础数据集较“分明”的致的而且子类间是据结构提供的统计 划分尽可能分离的信息最好 优点简单、运算量小与数据集的结构密与数据集分布密切 切相关相关 与数据集的结构特表述比较复杂、运算性能依赖统计假设 缺点征缺乏直接联系量大与数据分布的一致 性 z a d e h 的分离度2 】d u n n 的划分系数【1 9 】v o g e l 等人的p f s 聚 b e z d e k 的划分熵【2 】g u n d e r s o n 的分离系类【3 4 】 代表性研究w i n d h a m 的比例系数【3 0 ij a i n 等人的子举法【3 5 1 数2 9 】x i e b e n i 指标4 6 1b e n i 的熵形式有效 性函数日7 1 1 9 9 5 年，p a l 与b e z d e k 【4 7 1 比较了划分系数、b e z d e k 的熵指标、x i e b e n i 指标、 扩展的x i e b e n i 指标及f u k u y a m a - s u g e n o 指标。认为f u k u y a m a - s u g e n o 指标对于 1 4 西安电子科技大学硕士论文：f c m 参数研究及其应用 模糊c 一均值聚类算法中的加权指数很敏感。相比较而言，x i e b e n i 指标具有较好 的效果。如前所述，样本集的分类结果与样本集本身及分类算法有很大的联系， 我们认为聚类有效性问题需要将这三个因素都结合起来才能取得比较好的结果。 这也是x i e b e n i 指标比其它有效性函数好的一个因素。因此这里要简单介绍一下 x i e b c n i 指标。 1 9 9 1 年x i e 和b e n i 利用目标函数定义了一个称之为x i e b e n i 指标的聚类有效 性函数，如( 2 1 6 ) 所示 州圯习2 蒜m 幕l ni t v 碉2 “；+ 彰 船+ i1 一v | lf l ( 詈) s e p ( v ) ( 2 2 2 ) 盯：移，y ，x ) = 主耋甜。2 ，d ； ( 2 2 3 ) s 印( 矿) = ( 呼t l v , - v , i 1 2 ) c ：出， 上式中 为样本数，垆7 妙，v ，x ) 中的上下标分别表示f c m 中的加权指数为 2 ，d ：表示样本泻身分类聚类中心的距离。x i e b e n i 指标可解释为移，v ，z ) 的总 方差盯( 见2 2 3 式) 与啪分离性指标j 印o ，) ( 见2 2 4 式) 的比值。当( u ，v ，x ) 的总方差较小时，则“。较大，而盯较小。分类效果好的时候，各类中心间的距离 应该大，即分离性指标j e p ( v ) 比较大。由此，对应最佳类数c 时，哆m 妙，v ，z ) 应 该最小。 x i e 和b e n i 认为当类数c & 2 至i n 一1 变化时，x i e b e n i 指标具有递减的趋势， 假定对于确定的样本集，只有一种最佳的分类妙：，曙) ，为了避免由于单调性带来 的最佳类数选择错误的问题，他们认为应该选择一个最大的候选数c 。，然后在 c ：2 , 3 ，c 的范围内计算每个c 时的嘭“p ，y ，x ) ，最小的嘭“p ，y ，爿) 所对 应的类数c 为最佳。 当用模糊c 均值聚类算法从c = 2 到c 。进行聚类时，如果加权指数州不是2 时，x i e 和b e n i 推荐将( 2 2 2 ) 式改为如下形式： 第二章模糊c - 均值( f c m ) 算法参数研究 1 5 y f ”u ，矿，x 2 j_=赫i=lj=l d i t l l n 2 圭量“孑- ； n4 l 1 | l v 一v 4f l 盯。( u ，v ，x ) = 壹n “i r a + d ： l = l t l 。 。 ( 2 2 5 ) ( 2 2 6 ) 式( 22 5 ) 即为x i e b e n i 指标的扩展形式。其中c = 2 l n ( n ) 。 没有万能的模糊聚类有效性函数，这也是有效性函数层出不穷的原因。既然 单一的度量方式不能解决所有可能的聚类有效性问题，那么现有的有效性函数将 长期存在。另外，现有的聚类有效性函数多是针对模糊c 均值聚类算法的，除了 d a v e 4 8 和k r i s h a p u r a m 4 9 提出过针对模糊c 壳聚类的有效性函数外，很少有人讨 论面向模糊线、面阻及其它原型聚类算法的有效性问题，此外对可能性聚类、半 模糊聚类的有效性度量也需要进一步丰富和发展，以便完善聚类有效性理论。 上述聚类有效性函数，主要被用来确定合理的聚类数，以保证算法得到更有 效的分类结果。而在实际的聚类中，即使分类数选取的合适，由于选取的算法不 合适或者算法的参数选取的不合适，也可能的不到数据的真实结构。这促使人们