（计算机软件与理论专业论文）一种基于粗集的模糊聚类算法及应用的研究.pdf

颂士学位论交 埘鸲嚣t 圈妒嚣t h e s i s 中文摘要 数据挖掘技术是近几年国内外迅速发展起来的一门交叉学科，是利用数据 库、统计学、人工智能与机器学习等学科的技术对大量数据进行处理，提取隐含其 中的、人们事先不知道的潜在有用信息和知识的过程。已经广泛被应用于农业生产、 金融保险、国防等领域。 聚类用于从数据集中找出相似的数据并组成不同的组，聚类分析是数据挖掘的 项重要内容。有很多方法可以使数据分类，公认的方法包括基于划分的算法、基 于分层的算法及基于网格和密度的算法。模糊聚类方法将模糊数学的理论应用于聚 类分析，能有效处理边界模糊的数据分类，模糊聚类算法的出现与之前的硬聚类方 法相比，更有现实意义。 然而，由于数据库结构多样性的特点，到目前为止，没有任何一种聚类算法普 遍适应于所有数据库。在应用中，大量的聚类分析任务都需要特定算法来完成。传 统的模糊聚类算法虽然能处理大量边界模糊聚类问题，但仍存在不少问题。 本文针对模糊聚类中存在的问题，通过对模糊聚类新算法的对比研究，作了如 下工作： 首先，介绍数据挖掘和聚类分析的理论基础，并重点对模糊聚类方法f c m ， n f w f c a 进行分析对比。 其次，详细的分析了聚类分析中的问题：指标冗余，指标权重以及敏感性问题 等。这些问题导致聚类正确率下降，运行效率下降。 再次，为了更加有效的解决这些问题，本文引入粗集理论。利用粗集理论中的 属性约简方法对f c m 算法进行改进，经过比较，看到改进后算法可以有效的提高 其分类正确率，并对指标权重和敏感性问题也有所改善。 最后，将改进的算法应用到信息检索系统，对信息检索系统检索结果进行重聚 类，为高效信息检索系统构建提供理论依据和科学方法。 关键词：数据挖掘；粗集；模糊聚类分析；q f c m 算法； a b s t r a c t 1 1 坨t e c h n o l o g yo fd a t am i n i n gi sac r o s ss l l _ b j e c td e v e l o p i n gr 印i d l yd o m e s t i c a l l y 纽do v e r s e 勰，ni sap r o c e s st l l a tt 0d e a l 、i t ha n d 懿仃tm l 】【n o 、釉【i n f o 加谢o n 锄d 1 m o w l e d g e 丘0 ml 鹕e 蛐笛e sb y 璐i i l gt l l em e a n so f 出她i b a ，s t a 虹s t i c s ，a n i f i c i a l 血e 1 1 i g e n c e ，a n dm a c b i n el e a l l l i n g nh 勰b e a p p l i e de x t e n s i v e l yi nt 1 1 e 丘e l d so f 删c u l t l l r e ，丘n 锄c e ，i i l s u 啪c e ，n a t i o n a ld e f e n c ea n d s 00 n c l u s t e 血gi su s e dt of i n do u tt 1 1 eo b j e c t s l a ta r cr e 溯n b l e 蚀c ho t h e r 锄dc o m p o s e d 词；e r e n tg r o u p s ，c l u s t 盯a n a l y s i si sa ni i i l 】p o r t a n tj o bi n 讹m i i l i n g 廿l e a m a n yw a ) ，s t 0c l 硒s i 鸟t i 圮d a t 硒吒t h cp a n i t i o n i n gm e m o d s h i 删c a lm e m o d sa n d 鲥d b 觞e d m e m 0 ( 1 sh a v eg r e a tr e c o 嘶h o m 如z z yc h 峪t e rm e 1 0 d sa p p l i e dt h e 也e 0 巧o ff i l z z y m a t h e m a d c si nc l 吣t e r 撇l y s i s ，c a nd 0 、丽也t h ed a t ac 1 弱s i 丘c a ：妇也a 土h 弱af u z z ye d g e ni sm o r cm e 锄岫吕f i l lt h 跹p r i 丽。岫h a r dc l 勰s i 丘c a t i 吡 h o w e v e f ，b e c a u s et 1 1 ev 碰啊o f m cd 乏叱山撇s 协l c t u r e ，胁n o 、o 玛t 1 1 e f ei sn oo n e a 1 9 0 r i t h ma p p l i e da uc l u s t 盯觚a l y s i s i nm ea p p l i c a 矗。璐，al o to fc l u s t 盯龃a l y s i st 弱k s n e e dac 钉_ t a i l la l g o r i t l 】m t l l o u g ht t l e 仃a d i t i o n a l 如z z yc l u s t 盯a 1 鲥t h m sc a nh a n m e m 趾yp r o b l 伽衄t h a th a v ef i l z z ye d g 懿，m e r ea r em a n yd i s 缸i v 锄t a g 骼a l b yc o m p a r i s 0 咀觚dr 髓e a r c h e so nm ef u z z yc l u s t e ra l g o r i l m s ，t h i sa n i c l ea i 【n i i l ga ：t m e 呦c l 璐t e 血gc 础u t e d i ns u c ha s p c c t s ： 丘r s t l x 锄胁d u c e 也e 廿l e o r yb a s i so fd a _ t al i l j m n g 孤dc l u s t e 血g 姐a l y s i s ，e m p h a s 讫e 0 n l em z z ) rc l u s t e ra 1 9 0 r i t l l l n s 孤a l y s i s 锄dc o m p a i i s 0 n e s p e c i a j l y 也ec o m p 撕s o no f f c m a l g o r i l ma n dn f w f c aa 1 9 0 r i t h m c o n d l y ，a 舳1 ) ，z et l l ep r o b l e i 璐i nm ec l u s t e 血ga n a l y s i s ，a 缸b u t 懿幽d 觚喵t 1 1 e i i i s p r o p 硎o no fa t t r i b u t e s w e i 皿临a n di s 0 l a t e dp o i n t s s e 衄i d v 时趾d t 1 1 e s e p r o b l 锄sl e a dt 0m ed e c r e 笛eo fc o r r t e d 阳t i o 锄d 删n ge f f i c i 即l c y t h i r d l y ，矗) rr e s 0 1 i n gt 1 1 e s ep r o b l e i 璐e 伍c i e n t l y ，仕l i sa n i c l eb 血g st h e 砌l 曲s e t t 1 1 e 0 巧i i l t 0f u z z yc l u s t e r b y 岫g t l l em e m o d so f 砌b u t 鹤咖豫c t e di nm er o u g hs c t i l l e 0 d rt oi m p m v e 也ef c ma 1 9 0 r i t h m ，t h ei m p r 0 v e da 1 9 0 r i t l 姐h a db c p r 0 v c dah i g h p r e c i s e 训o 丘n a l l y a p p l i e d 廿坞i m p r o v e da 1 9 0 r i 血mi n t om c 妣撕搬 e a r c l l 叫锄，b y r e c l u s t 谢n gt ：h es e a r c hr e s u l t s ，i t1 e a dt 0ah i g l le 伍c i e n c yi i l f 0 肌a 矗0 nr e s e a r c hs y s t 锄 k e yw o r d s ：d a t am i n i n g ；r o u 曲s e t ；f i u 冯，c l u s t e r 趾a l y s i s ；q f c ma l g o r i 也m ； 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名： 日期：年月 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程纾中的 规定享受相关权益。回塞途塞握銮卮溢卮；旦坐生；旦二生；旦三生筮查! 作者签名： 日期：年月 日 导师签名：飞搀辛导师签名：秒万中吖 日期：矿缛乡月p 日 第一章绪论 1 1 选题背景和意义 随着数据库技术的飞速发展，人们拥有的数据急剧增加。历史的数据是一笔宝 贵的财富，对数据库中已有数据进行存取和简单的操作，从数据库中获得的信息量 仅仅是整个数据库所包含的信息量中很少的一部分，隐藏在这些数据库之后的更重 要的信息是关于这些数据的整体特征，使用一定技术对其综合分析，可以有效对某 些发展趋势进行预测。希望让计算机自动智能的分析数据库中的大量数据以获取一 些一直存在但还没有发现的规律和信息，推动了挖掘型工具的产生并成为其发展的 强大动力。怎样才能有效利用数据，怎样才能发现潜在知识，在这样的需求驱动下 数据挖掘技术产生并且迅速发展起来。 数据挖掘【1 】( d m ，d a ：t am 砒培) 就是从大量的、不完全的、有噪声的、模糊 的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用信 息和知识的过程。提取的知识可以被用于信息管理、查询优化、决策支持、过程控 制等。它又可以被称为“数据库中的知识发现一i a ) d ( k n o w l e d g ed is c l o v e 巧i n d a t a b a ) 、“智能数据分析一( i n t e l l i g e n td a l a 山m l y s i s ) 、“信息发现 ( - 0 皿a t i d i s c o v e 口) 、“数据考古 ( da _ t a 觚h e 0 1 0 9 y ) 等。是一门广义的交叉学科，它会聚 了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等 发面的学者和工程技术人员。数据挖掘涉及的学科领域很多，分类方法很多，常用 的分类方法是基于挖掘任务的，可以分为：( 1 ) 分类分析：( 2 ) 聚类分析；( 3 ) 关 联分析；( 4 ) 序列分析及时间序列；( 5 ) 孤立点分析 聚类分析是一种基于统计的挖掘方法，主要是把数据集聚合成不同的组，使组 内数据具有极高的相似性，不同组的数据是不相似的。聚类分析在市场营销、生物、 考古、地质、地理学等方面的研究都产生了深远的影响【”】。 聚类分析有很长的研究历史，是数据挖掘和模式识别等研究方向的重要研究内 容，在语音识别、字符识别、图像分割、机器视觉、信息检索等应用中发挥了很重 要的作用。由于数据库呈现的多样性，没有任何一种聚类技术可以普遍揭示它们所 呈现的结构特征【4 1 ，根据数据在聚类中的积聚规则，聚类算法大致可以分为层次化 聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法【5 】。划分 式聚类研究最早应用也最为广泛，它是一种需要预先指定聚类数目或聚类中型，经 过反复迭代运算，逐步降低目标函数的误差值，直到目标函数收敛的时候得到最终 聚类效果的一类聚类算法。它具有以下优点【5 l ：( 1 ) 能对大型数据集进行高效分类， 时间复杂性比较低。( 2 ) 适合常见的聚类结果为凸型的数据集。在此类算法长期的 发展中，一些经典算法比如l e a 璐算法得到不断的改进，具有了更高的性能以及 更广的适用性。由于应用的需要也产生了很多新的算法，比如把模糊理论引入聚类 分析的模糊聚类算法f c m ( f 吣s ) rc - m e a 璐) 以解决图像硬分割问题。现实世界的聚 类分析更多是边界模糊的，所以，模糊聚类算法的应用前景相当乐观。因此，本文 选择模糊聚类算法作为研究课题。 基于划分的聚类方法中，一般有以下基本数据和操作： ( 1 ) 一个有n 个样本的样本空间。每个样本选择p 个变量作为观测值； 通常n 个样本所有p 个变量的观测值可排成如下矩阵： x = 五。五： 五。如 五。五： 该矩阵被称为样本数据矩阵。其中第i 个样品p 个变量的观测值可以记为向量： 而= ，而：，) r ( 2 ) 一个作为分类统计量的测量距离。对于有p 个变量的样品来说，n 个样本 可以看成p 维空间中的n 个点，通常使用以表示第i 个样品与第j 个样品的距离。 ( 3 ) 类原型的定义，这是基于划分的聚类模型设计的关键。它可以定义为样 本空间中的点，抑或是函数关系式等。 ( 4 ) 目标函数的建立。关于样本和类原型聚类的目标函数是聚类结束的标准， 通过对目标函数的求解就能够对数据实现划分聚类。 而模糊聚类方法则是在一般聚类方法的基础上引入隶属度的概念。普通聚类方 法对于数据的划分是硬性的，而模糊聚类方法则是一种柔性的模糊划分。在样本的 分类中，当不能确切的说一个样本一定属于或者不属于某一类别时，利用模糊聚类 引入隶属度这个概念，则能很好的体现这一事实。 由于类原型或目标函数的定义方法不同，会对聚类结果产生明显的结果，因此， 充分了解各算法长处和短处，了解其特定的适用环境，便于研究者的选择使用和改 进应用。 1 2 国内外研究现状 第一个系统的研究模糊聚类的是r u s p i n i 【6 1 ，1 9 6 9 年他定义了数据集模糊划分 2 ， ， p 如砌；办 一； 一 的概念。同时，z a d e h 【7 1 ，t a 叫r a 【8 1 等也提出基于相似关系和模糊关系的聚类方法， 但由于该类方法不适合大数据集，这方面的研究后来开展较少。后来，为解决模糊 聚类问题人们利用图论、动态规划等各种技术作出尝试，均因种种原因不能奏效， 直到基于目标函数的聚类方法出现，模糊聚类才真正的普遍受到欢迎和得到应用。 它设计简单，解决问题广泛，并且可以转化成人们熟悉的优化问题，这种种优点使 此方法成为模糊聚类分析的主要手段。 基于目标函数的模糊聚类方法首先由r u s p i n i 网提出，但真正有效的算法一模糊 c 一均值算法却是由d u n n l 9 1 在1 9 7 3 年提出，1 9 8 1 年由b e z d e k 扩展，逐步建立起模 糊聚集理论，目前已形成庞大体系。f c m ( 模糊c 一均值) 是依据最小二乘原理，采 用迭代法优化目标函数来得到数据划分的，其中目标函数为： 厶= ) 。慨一m 1 1 2 扭li = d x ：数据集合x = “，而，) ，而f 形：具有s 个特征的聚类中心 ”* ：表示样本k 属于类i 的隶属度 刀：待聚类数样本总数 c ：聚类中心数 肌：聊 1 ，用来调节模糊类之间分得隶属度的程度，增大m 将增加函数的模 糊性使数据的隶属度降低 在目前庞大的模糊聚类算法研究当中，有以下几个重要发展方向【l ”： ( 1 ) 收敛性和停止准则的研究：1 9 8 7 年t u c k e r 认为f c m 算法有可能收敛到鞍 点【1 2 l ，并举例说明鞍点存在以此指出b e z d e k 算法有误，b e z d e k 等人经过重新研究， 对收敛性作出正确表述1 3 】。后来s e l i m 等【1 对模糊聚类算法的收敛性和停止准则 做了细致研究，针对数据集的概率分布，s a b i n 【1 5 1 和y a n g 【1 6 】从更一般的意义上对模 糊聚类算法的收敛性进行分析，这些研究结果极大的推动了模糊聚类理论的发展。 ( 2 ) 模糊聚类目标函数的构造研究：基于目标函数聚类方法的灵活之处在于， 可以针对不同应用构造面向问题的最佳目标函数，并取得好的聚类效果。w i n d h 锄【1 7 】 将f c m 的目标函数从基于类内最小均方误差函数扩充，提出几何模糊聚类算法。 l e s c z y n s k i 【1 8 】等将模糊集引入聚类分析，提出了新的聚类方法。t r a u w a e t 【1 9 】将最 大相关准则推广到模糊情形，提出基于模糊最大似然的聚类算法。这些都是对基于 目标函数比较成功的研究。 硕士学位论文 m a 鄹礤p sn 瑾g i s ( 3 ) 模糊划分空间的修正研究：现实世界的样本类属存在随机性，1 9 8 4 年s e l i m 和i s m a i l 【1 9 】将硬聚类和模糊聚类思想结合，提出三种软聚类方法。1 9 9 8 年k a 嘴1 和s e l i m 例对其评述，提出阈值型软聚类算法。l 【r i s h n a p u r 锄和k i l l e r 【2 1 】放松对 f c m 隶属度的限制条件，提出了可能性聚类，从而提高样本典型性。p e z d r c y 【笠l 在 1 9 9 6 年提出条件f c m 算法。以上算法从不同需要出发，对模糊划分空间的研究作出 贡献。 ( 4 ) 模糊聚类中聚类测度的研究：f c m 中距离是采用欧氏距离，在噪音环境下， 采用欧氏距离的许多聚类方法有时不够稳定，而且对于算法的初值、类的形状、大 小都过于敏感，改变度量方式可以使这些问题部分得到控制。多年来，出现了很多 通过改变度量方式对聚类算法进行改进的算法。g u s a t a f s o n 和k e s s e l 引入模糊协 方差矩阵，提出基于协方差矩阵加权的聚类度量。1 9 8 9 年g a t h 和g e v a 【2 3 l 引入最大 相关原则来计算距离，提出另一种距离度量方式，1 9 8 1 年b e z d e k 【m 1 采用样本点到 族原型的距离度量样本与原型的相似形，将模糊聚类的适用范围拓广到椭球形、线 状、平面状、超平面状的数据结构。借助不同的距离度量方式可构造不同的目标函 数，形成不同的分类标准，但度量方式的改变也会使迭代中聚类中心、隶属度有所 调整。目前针对如何选取合适度量标准解决特定问题还缺乏理论研究。 ( 5 ) 混合型数据的模糊聚类算法研究：实际问题中，数据集常常包含多种分 布，g u s t a f s o n 和k e s s e l 在1 9 7 8 年提出的协方差模糊聚类算法可对含有椭球状和 线状分布的数据进行聚类。1 9 9 5 年j 删a h a r 【笛1 在对同时含有几种数据类型的数据结 构提出了一些新的算法。 另外，随着新技术的不断出现，它们正不断的被用于模糊聚类分析中，例如： 基于神经网络的优化算法通过并行处理、分布式存储对大数据量聚类问题作出重要 贡献。而随着具有全局优化特点的遗传算法的兴起，它开始被应用于模糊聚类以解 决f c m 初始化敏感问题。 1 3 模糊聚类算法的研究发展方向 从模糊聚类算法长期的发展历史中可以发现，未来的模糊聚类算法研究有以 下发展方向： ( 1 ) 提高算法的性能。为了改进算法适应新环境的数据集聚类，可以看到， 改进算法大都通过引入参量或者改变距离测度的方法，这在一定程度上会直接影响 算法的性能。关于参数选择和性能的平衡制约直接关系着算法的现实实用性，是一 个很重要的研究方向。 4 摩士单位论交 m a 耵b r st h e g i s ( 2 ) 度量方法标准化。现实世界数据集分布多样化以及划分空间的随机性使 得聚类分析本身存在一个标准难以统一的问题。如何根据实际情况选取合适的算 法? 目前尚缺乏理论支持，多半是评经验和比较得出，因此度量方法的标准化是聚 类分析发展中必然会遇到的难题。 ( 3 ) 提高聚类有效性。基于目标函数的聚类划分方法以其简单、运算量小得 到推广，由于与数据集的结构特征缺少直接联系，是导致局部敏感性的根本原因， 虽然，诸多改进算法通过一些处理技术对此问题有所改善，但同时却降低了聚类运 算的效率，聚类有效性问题始终是聚类分析发展的瓶颈。 ( 4 ) 提高先验知识的应用。在实际问题中，蕴涵很多先验知识，许多情况下与 其结合能获得更好的聚类效果，如何运用它们将是聚类应用研究中的一个重要方向。 1 4 本文的研究内容及其组织结构 1 4 1 本文的研究内容 本文主要针对k - e a n s 聚类算法、f c m 算法以及将r e l i e f f 【2 6 】算法引入f c m 的基于特征加权的模糊聚类算法( n f w f c a 算法) 进行研究。介绍了模糊聚类算法的 基本思想、工作原理和适用范围。讨论了f 例算法对k - m e a n s 算法的重要改进以及 n 嗍算法对f c m 算法的重要改进，对比分析之后可以发现：( 1 ) 为了使k _ m e a n s 解决边界模糊的聚类问题，在k m e a n s 算法基础上引入模糊集的概念出现了f c m 算 法，为了解决各特征的权重分配，引入特征加权的概念出现了m f w f c a 算法。这是 聚类分析不断适应实际问题的演化；( 2 ) 传统k _ 舱a n s 算法虽然高效，但有初始化 敏感问题，并且仅适用于聚类结果为凸形的数据集；f c m 算法扩展了硬化分的实际 应用，但又引入了孤立点敏感问题；n f w f c a 算法对属性特征加权，不仅使得聚类结 果更准确更高效，而且也有利于对特征的选择和提取，对模糊聚类算法的发展作出 重要发展。但是n f w f c a 也不是普遍适用于任何数据集的，研究表明，聚类算法的 选取跟数据集的特征以及类簇特点有很大关系。粗集的属性简约方法不仅可以删除 信息系统中的冗余特征，还可以根据各个属性的重要性赋予权重，从另一个角度改 进了特征选择和提取。基于粗集的模糊聚类的研究还比较少，本文就此方面做出研 究总结。最后本文提出一种新的基于粗集的模糊聚类算法q f c m ，并将之试用于信息 检索系统，提高检索效果。 1 4 2 本文的组织结构 本文共分为六章，第一章介绍选题的背景和意义、基于模糊聚类的国内外研 5 究现状以及其发展方向；第二章对一些经典的基于划分的聚类算法进行深入的分 析，并且对粗集理论进行介绍，为后面的章节奠定了理论基础。第三章分析模糊聚 类算法、基于加权的模糊聚类算法的适用范围和特点，并且提出一种新的基于粗集 的模糊聚类算法。第四章给出该新算法的实用例证，并对其聚类有效性进行验证， 验证表明，该新算法适用于所提供的数据集。最后一章概括本文的主要研究成果， 分析存在的缺点，指出进一步需要解决的问题。 6 第二章模糊算法研究和粗集理论基础 数据的分析可以导出很多计算机应用，分析的结果要么用在设计阶段，要么 用在日常的事务处理过程中。例如：在客户数据中，可以根据属性选择提取有效的 分类指标，而这些指标可以反映客户的某些特征，采用适当的分类方法，就能达到 企业为客户进行分类的目的。可以根据客户购买的频度和购买的平均价值的分类， 反映出客户的忠诚度及对企业利润的贡献，从而制定不同目的的营销策略。聚类分 析是数据挖掘、模式识别、机器学习等领域中的重要研究，很多研究者已经提出许 多具体的聚类方法，当前数据挖掘聚类方法集中与基于划分的方法、基于层次的方 法、基于密度的方法、以及基于网格的方法等。 “聚类一顾名思义，就是将相近相似的对象聚成一类。从统计学角度出发，聚 类分析中把对象成为样品、样本或者个体，把它们的属性称为变量、指标或者特征， 从模式识别的角度看，对象就是数据点。以下研究中，将统一采用样本作为对象的 定义，指标作为它们属性的定义。 聚类分析的过程一般包括以下步骤【2 7 哂】： ( 1 ) 数据准备：包括特征标准化和降维。由于聚类问题中各样本的所取属性 变量往往采取不同的度量单位，其观测值可能相差十分悬殊。这样，绝对值大的变 量的影响可能会主导控制绝对值小的变量，使绝对值小的变量应有的作用得不到发 挥。为了确保各变量在分析中地位相同，往往对数据进行中心化与标准化的变换。 ( 2 ) 特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中。 根据分类目的，对数据各属性进行初步选择，选取对分类结果有影响的特征。这是 为消除噪声和提高聚类速度所做的最初的准备。特征选择有很多评判标准以及搜索 算法。 ( 3 ) 特征提取：通过对所选择的特征进行转换形成新的突出特征。与特征选 择最大的不同在于特征提取是对原有特征进行一个函数变换，该变换使得新声称的 特征互不相关。而特征的相关性主要通过协方差矩阵来表达，但协方差矩阵的非对 角线元素全不为零，说明特征是互不相关的。 ( 4 ) 聚类( 或则分组) ：首先选择合适特征类型的某种距离函数( 或则构造新 的距离函数) 进行接近程度的度量；而后执行聚类或者分组。测量距离是为了度量 样品间的接近程度。根据选取的某距离函数计算每两个样品间的距离，再另外对类 内距离和类间距离作出限定，选用合适方法实现分组。 ( 5 ) 聚类结果评估：是指对聚类结果进行评估。评估主要有3 种：外部有效 7 性评估、内部有效性评估和相关性评估。 下面将给出一个实例，进一步对此过程阐释： 为了解人体内元素与肺癌患者之间的关系，我们采用聚类分析的方法研究。初 步的特征选择中发现，患者头发中的微量元素的含量和正常人相比有所变化，如果 以c ，q ，4 含量的一个函数作为变量毛：， = 厂( c ，g ，4 ) 以& ，乙含量的另一个函数作为变量屯，则 恐= 厂( 莲，z - ) 以五为横坐标，焉为纵坐标的平面，每个检查者按这些微量元素的含量在该平 面上占据一点，其分布情况如图卜1 所示。 图卜1 肺癌患者与微量元素 从图卜l 中可以直观的看到，按分布的聚散情况可以将这些点划分为三部分： 健康人、肺癌初期患者和肺癌末期患者。这样划分对疾病的诊断，病因的分析都有 意义。 2 1 常见的几种划分式聚类算法 划分式聚类算法需要预先指定聚类数目或则聚类中心，通过反复迭代运算， 逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。标准就是 使同一分组中的记录越近越好，而不同分组中的记录越远越好。使用这个基本思想 的算法有：k m e a n s 算法，k _ m o d e s 算法、f c m 算法、n f w f c a 算法。其中，k _ m e a n s 算法和k - m o d e s 算法都是基于硬划分的：即样本分类具有“非此即彼 的特点，而 f c m 算法和n f w f c a 算法是基于软划分的，样品的分类界限是模糊的。k - 胍a n s 算法 是划分式聚类算法中的经典算法，划分式聚类算法多由它加以改进而来，比如， k m o d e s 算法。k _ m o d e s 算法是硬划分中影响比较大的算法，它对k m e a n s 算法进 8 硕士学位论文 m 脚日r 譬t h e 譬i 窭 行扩展：引入了处理分类对象的新的相异性度量方法，并在聚类过程中使用基于频 度的方法修正，以使聚类代价函数值最小化。事实上，这些改进能使k - m e a n s 算法 更快收敛。而f 叫算法是在k - m e a n s 算法的基础上引入模糊理论中的隶属度的概念， 使k - 姬a n s 从只能处理硬划分扩展到处理边界模糊的聚类，后来，为了使聚类效果 更好，解决划分式聚类算法的缺点：权重分配问题、局部最小值等问题，李洁等人 用r e h e 伍的特征选取方法改进f c m 算法，得到基于特征加权的模糊聚类算法 n f w f c a ，使得聚类效果更准确和高效。因为本文主要研究模糊聚类算法，所以只选 取对分析有影响的k _ 肛a n s 算法，f c m 算法、n f w f c a 算法作为研究对象。 2 1 1k m 哐a n s 算法 k 姬a n s 算法在许多实践中取得了很好的效果，是划分式聚类算法中最早和最 经典的算法。下面给出其直接的算法描述： 输入：聚类个数k ，以及包含n 个样本的数据库 输出：满足方差最小标准的k 个聚类 算法流程： ( 1 ) 初始化k 个原形m ，) ，其中m = 】i ， 1 ，2 ，妨， l ，2 ，刀) ( 2 ) 使每一个聚类c ，与原形w ，相对应 ( 3 ) d o ( 4 ) f o r 每一个输入向量，其中， 1 ，2 ，万) d 0 ( 5 ) 将分配给最近的原形w ，所属的聚类c ，即 i f ，一w ，i q 一i ，歹 1 ，2 ，七) ( 6 ) f o r 每一个聚类c ，其中j 1 ，2 ，七 d 0 ( 7 ) 将原形更新为当前的c ：，中所有样本的质心点，即吩= 的l ql i ( 8 ) 计算目标函数：e = i 一一1 2 产l e q ( 9 ) u n t i le 不再明显地改变或者聚类成员不再变化 k 一胍a n s 算法的工作过程可以看出，首先是从n 个数据任选k 个对象作为初始 聚类中心的，而剩下的对象，则根据它们与这些聚类中心的相似度，分别将它们分 配给最相似的聚类；每次分配完后都从每个聚类中对象的均值处获得一个“中心对 象作为新一轮聚类的k 个中心，对对象重新进行分配，一直到目标函数开始收敛 为止。一般都采用均方差作为测度函数。k 个聚类具有以下特点：各聚类本身尽可 能紧凑，各聚类之间尽可能分开。 设每个对象的维数( 属性个数) 为d ，计算复杂性分为三个部分： ( 1 ) 第一个f o r 循环所需时间复杂性d ( 豫船) 。 ( 2 ) 计算质心点( 第二个f o r 循环) 的时间复杂性是d ( 刀d ) ( 3 ) 计算目标函数的时间复杂性是d 0 d ) 。 l 厄a n s 设计简单，计算量小，主要体现在三个方面： ( 1 ) 利用上一次循环结果来减少距离计算的数量，如果n 个样本p 个向量每 两两之间计算距离，需要n p 时间，一般样本数量n 是一个很大的数，而k _ m e a n s 利用上一次的循环结果，只相对的移动聚类的质心点，几次循环之后，聚类质心点 一般移动较少。 ( 2 ) 它将原形向量组织在了一个恰当的数据结构中，结果已知一个原形的条 件下发现最近的原形变的更有效率。这种方法是根据划分式聚类已知原形数量的特 点设计的，对许多应用，向量的数量及原形向量的数量都是固定的，对于一个给定 的输入测试模式，构造优化的数据结构可以发现最近的向量。 ( 3 ) 引入目标函数的概念，使实际问题可以转化成极值问题，这在很多改善 算法中都有所体现。 2 1 2f c m 算法 f c m 算法也是一种基于划分的聚类算法。它的思想同k _ m e a n s 一样，就是使 被划分到同一类中的对象间相似度最大，而不同类间的相似度最小。f c m 算法将模 糊集的隶属度概念应用到传统硬划分式算法，实现了数据划分的柔性边界，它是 用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1 9 7 3 年b e z d e k 提 出该算法，是作为早期硬h c m 算法的改进算法提出来的。 引入隶属度概念的数据变化说明： 在硬划分方法中，如果把n 个数据归属为k 个组表示成一个归属矩阵，矩阵 中的数值应该只能取0 和1 。在f c m 算法中归属矩阵则变成一个七厅的隶属矩阵， 设归属矩阵为u = 伽群) 棚，f = 1 ，2 ，七；歹= 1 ，2 ，以 f c m 把n 个向量而，f 1 ，2 ，刀) 分成k 个模糊组，并求每组的聚类中心，使得 非相似性指标的目标函数达到最小。它与硬划分的主要区别在于f c m 用模糊划分， 使得每个给定的对象用值在0 ，1 之间的隶属度来确定其属于各个组的程度，与引 入模糊划分相适应，隶属矩阵u 允许有取值在o ，1 间的元素，但是有一归一化规 定：一个数据集的隶属度的和总等于l ： l o 硕士学位论吏 h o l 戤b 袋st h e 譬i g = l ，w = l ，刀 ( 2 1 ) 扣l 那么f 伽算法的目标函数就变成了 上o ，( u ，q ，q ) = j i = ”孑露 ( 2 2 ) j i l扛l l 这里于o ，l 间；q 为模糊组珀勺聚类中心，略爿l q 一乃i i 为第f 个聚类中心与第j 个数据点间的欧几里德距离；且m 【1 ，) 是一个加权指数。 构造新的目标函数，可以求得使2 1 式达最小值的表要条件： - ( u ，c l ，c c ， ， ) = ，c l ，c 。) + ：乃( “i ，一1 ) 扫1 ( 2 3 ) = 甜罗d ；+ 乃( ”扩一1 ) j l l 卢l 扛l 这里允，j f = 1 ，2 ，厅，是2 1 式的n 个约束式的拉格朗日乘子。对所有输入参量求导， 使2 2 式达到最小的必要条件为： ”孑_ ，l l q2 二。一 “芗 和 铲才 ( 2 4 ) ( 2 5 ) 根据上面2 4 式和2 5 式两个必备条件，f c m 算法是一个简单的迭代过程，在批处 理运行方式中，f c m 用下列步骤确定聚类中心q 和初始隶属矩阵u 1 ： 1 ：用值在o ，1 间的随机数初始化隶属矩阵u ，使其满足式2 1 中的约束条件 2 ：用式2 4 计算k 个聚类中心q ，f = l ，2 ，。j 3 ：根据式2 - 2 计算价值函数。如果它小于某个确定的阀值，或它相对上次价值 函数值的改变量小于某个阀值，则算法停止。 4 ：用2 5 计算新的u 矩阵。返回步骤2 。 上述算法也可以先初始化聚类中心，然后执行迭代过程，由于不能确保f c m 收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的快 速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行 f c m 。 通过上面的讨论，不难看出f 删算法需要两个参数，一个是聚类数目k ，另一 个是参数m 。一般来讲k 要远远小于聚类样本的总个数，同时要保证k l 。对于m ， 它是一个控制算法的柔性的参数，如果m 过大，则聚类效果会很次，而如果m 过小 则算法会接近h c m 聚类算法。 算法的输出是k 个聚类中心点向量和k 的一个模糊划分矩阵，这个矩阵表 示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大 隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均特 征，可以认为是这个类的代表点。从算法的推导过程中我们不难看出，算法对于满 足正态分布的数据聚类效果会很好，另外，算法对孤立点是敏感的。 2 1 3n f w f c a 算法 f c m 算法应用于数据挖掘中还存在一定问题。首先，它在进行聚类分析时认为 每维特征的贡献是均匀的，并不进行特征分析。实际应用中，很多聚类结构是存在 于特征空间的子空间中的，不进行特征分析，容易发生特征冗余的现象。为提高聚 类效率，进行特征选择是必须的。 n f w f c a 算法的目标函数加入了权重指数w ，形式如下所示： t。， ( 2 6 ) m i n l 缈，p ) = ( 以) 用一d ( ，岛) f = 1 ，- l _ ，= 1 s 1 u m f c 计算同类间样本间的差异为： 胄 ( 2 7 ) 研一砌= 面甓拓 异类样本间的差异为： 。 彤一肌加k 磊：、高善茹禹 8 ) l c f 正 ( 工| lj 2 i 基于r e l i f f 算法计算特征权值的方法为： 破矿一栅。够一肌洳 肛扩千+ 专一 修正后的目标函数为： ( 2 9 ) ，( 形，p ) = m 一 脚，峙2 膈叱，l 矗一以1 2 + 扣k 一嵋，卅虬，巧盯( ，p 品) 】 ( 2 1 0 ) 1 2 摩士学位论文 m 璃匹鄹睡s t h 麟堤 当，( 矿，p ) 最小，聚类结果最优。通过实验数据的测试，该算法的聚类结果较之传 统的方法更准确、高效。之前的算法对特征选择和特征提取缺少研究，而此算法则 对此作出了贡献，在模糊聚类的发展中有重要影响。 2 2 粗集理论基础 粗糙集( r o u g hs e t ) 理论是由z p a w l a k 【3 1 】于1 9 8 2 年提出的，这一理论为处 理不精确或不完全信息的分类问题提供了新的工具。它的主要思想是，在保持信息 系统分类能力不变的前提下，通过知识约简，导出问题的决策和分类。粗糙集理论 一出现就广泛应用于机器学习、数据挖掘、过程控制等各个领域，并取得了巨大成 功。 为了进一步把粗糙集应用到信息系统，苗夺谦等【3 2 1 通过建立知识与信息熵的关 系把粗糙集理论中的概念与运算进行了信息表示，并由给出的证明可以看出，对知 识越简而言，信息表示与原来的代数表示完全等价，这就给人们提供了信息系统高 效约简的理论基础。 同时，粗糙集和模糊理论的结合推动了模糊粗糙集理论的研究，两个理论的比 较和融合一直都是研究者比较感兴趣的方向，从d u b o i s 和p r a d e 【3 3 】提出模糊粗糙集 理论，到后来的各种广义模糊粗糙集理论、公理化模糊粗糙集理论等的提出，形成 了论域框架下该理论的相对完善状态。其中，粗糙集到模糊粗糙集的最大区别在于 等价关系到模糊等价关系的转变，本小节将对这些基本概念作出介绍。 2 2 1 基础概念 在粗集中，知识系统可用一个4 元组来描述：s = 缈，4 ，y ，) ，其中u 表示数据 集中的所有对象；a 表示数据集中的全部属性，彳= c u d ，c 为条件属性集合( 也 称特征属性集合) ，d 为决策属性集合( 也称分类属性集合) ；v 是属性值组成的集 合；厂：【，彳哼y 是信息函数，指定了u 中每个对象的属性值。 定义1 【卅设，矿是论域，称映射r k 力：u 矿叫o ，l 】确定矿上的一个模糊 子集厅为到矿的一个模糊关系隶属函数r ( 工，力表示( z ，y ) 关于模糊关系厅的相 关程度 定义2 【卅设r = ( 曙) 期是刀阶模糊方阵，若刀满足? 自反性? = 1 对称性? 吩= ，= i 】f 传递性：m a x ( 勺) 1 1 七刀) 勺则斤为模糊等价矩阵 定义3 3 5 】 设r = ( ) 帅是刀阶模糊方阵，若曰满足? 自反性? = 1 对称 两士学位论交 m 脚b 薹r st h e g i 墓 性：吩= 白则刀为模糊相似矩阵 定理1 【3 们 设詹是力阶模糊相似矩阵，则存在一个最小的自然数七( 七万) ，使得矿 为模糊等价矩阵，且对一切大于七的自然数1 ，恒有足1 = 科。 2 2 2 知识约简 为了说明知识约简的概念，先介绍粗糙集里一些符号定义【3 2 1 。如表2 1 所示。 表2 1 粗糙集里的符号定义表 u论域 r u 上的一个等价关系 u r r 在u 上导出的所有等价类 【吐 包含元素x 的r 的等价类，z u k = ( u ，p )一个知识库( 一个关系系统) 其中p 是u 上的一个等价关系族 i n d ( q )q 的所有等价关系的交，q 包含于p 且不为空 等价：有k - ( u ，p ) ，k 1 = ( u ，q ) 如果i n d ( p ) = i n d ( q ) 则k 兰k 1 c o r e ( p ) 关系族p 的核，p 中所有必要关系组成的集合 下面是一些重要基础概念： 必要关系与不必要关系：设u 为一个论域，p 为定义在u 上的一个等价关系族， 尺p ，如果d d ( p r ) ) 锄( p ) ，则关系r 在p 中是不必要的，否则，称r 在p 中是必要的。不必要关系在知识库中是多余的，如果将它从知识库中去掉，不 会改变知识库的分类能力。相反，如果从知识库中去掉一个必要关系，则一定改变 知识库的分类能力。 独立和相依关系族：设u 是一个论域，p 为定义u 上的一个等价关系族，r p ， 如果每个关系r p 在p 中都是必要的，则称关系族p 是独立的，否则称p 是相依 的。相依关系族中，包含有多余关系，可以对其进行约简，而对于独立的关系族， 去掉任何一个关系都将破坏知识库的分类能力。 在此基础上给出知识约简的概念： 设u 为一个论域，p ，q 为u 上的两个等价关系族，且q p 如果：( 1 ) d d ( q ) 锄( p ) ； ( 2 ) q 是独立的； 则：称q 是p 的一个约简。 1 4 2 2 4 信息熵和信息表示 粗糙集从新的视角对