（计算机应用技术专业论文）数据挖掘中模糊聚类与聚类集成研究.pdf

一一一一一一一亘立銮鋈盔兰堑三亚童兰兰耋造奎一一一一一篁! ! 豆摘要数据收集和数据存储技术的快速进步使得各组织机构积累海量数据，如何提取有用信启、已经成为巨大挑战。数据挖掘技术应运而生，并显示出强大的生命力。聚类分析是数据挖掘任务中的重要分支。所谓聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽量小，类内相似性尽量大。传统的聚类分析是一种“硬”划分，它把每个待辨识的对象严格地划分到某个类中，具有“非此即彼”的性质，所以这种划分的界限很分明。但实际上现实生活中大多数对象并没有严格的属性，它们在形态和类属性方面存在着中介性，具有“亦此亦彼”的性质，因此比较适合进行“软”划分。模糊集理论的提出为这种软划分提供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。高维数据聚类问题被公认为较难处理的一种聚类问题。本文简要介绍了模糊集合和模糊关系概念，总结了模糊聚类的原则和通用的方法，讨论了常用的模糊聚类算法，在此基础上提出了基于图论的高属性维稀疏数据的模糊聚类算法。有效地实现对不同类型高属性维稀疏数据的归并，使得聚类结果更符合实际情况，聚类质量较高。由于聚类分析的重要性和特殊性，近年来该领域的研究取得了长足的发展，涌现出了许多聚类分析的方法。聚类集成方法将不同算法或在同一算法下使用不同参数得到的结果进行集成，从而得到比单一算法更为优越的结果。但绝大多数聚类集成方法的研究都集中在硬划分上，即研究如何对硬聚类算法进行集成，在模糊聚类算法方面尚缺乏建树。针对该种情况，本文提出了一种模糊聚类集成的决策模型。该模型同时考虑“专家决策和“多数投票”机制将模糊c 均值( f u z z yc m e a n s ，f c m ) 算法设定不同参数得到的不同结果进行集成，最后通过对人工数据集、u c i 数据集及w e b 数据集等多组实验，验证了该模型的有效性。关键词：数据挖掘；模糊聚类：聚类集成；决策模型：f c m 算法a bs t r a c tw i t ht h er a p i dp r o g r e s so fd a t ac o l l e c t i o na n dd a t as t o r a g et e c h n o l 0 9 3 ，m a n 3 , 1 a 玛ed a t ai sa c c u m u l a t e da n dt h ea b i l i t yo fu s e f u li n f o r m a t i o ne x t r a c t i n gb e c o m e sac h a l l e n g e d a t am i n i n gi ss u c hat e c h n o l o g ya n ds h o ws t r o n gp o w e r a so n eo ft h em o s ti m p o r t a n tb r a n c h e 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 sd i v i d e sas e to fp h y s i c a lo ra b s t r a c to b je c t si n t os e v e r a lc l u s t e r st h a tc o n s t i t u t ef o rt h es i m i l a ro b j e c t s t h eo b j e c t si nt h es a m ec l u s t e ra r es i m i l a r , b u tt h eo n e si nd i f f e r e n tc l u s t e r sa r ed i s s i m i l i t u d ee a c ho t h e r 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 sf o c u s e so n h a r d p a r t i t i o n s ，w h o s eb o u n d a r i e sb e t w e e no b j e c t sa r ea c c u r a t ew h e nw ec l a s s i f ) 7t h e m b u ti nt h er e a lw o r d ，m o s to b je c t sa r eu s u a l l yf u z z yi nt h e i rp a t t e r na n dc l a s sf e a t u r e ，t h e yf i tf o r “s o f t p a r t i t i o n s t h i sp r o b l e mc a r lb e s o l v e db 3 rap o w e r f u la n a l y s i st o o lw h i c hi sc a l l e df u z z 3 rs e tt h e o r y f u z z ym e t h o d sb e c o m et ob ea p p l i e di n t ot h ec l u s t e r i n ga n db e e nc a l l e df u z z yc l u s t e r i n ga n a l y s i s h i g h - d i m e n s i o n a ld a t ac l u s t e r i n gi su n i v e r s a l l ya c c e p t e dt ob eah a r dp r o b l e mi nc l u s t e r i n ga n a l y s i s i nt h i st h e s i s w ep r e s e n tt h eb a s i cc o n c e p t so ff u z z y s e t sa n df u z z yr e l a t i o n s ，s u m m a r i z et h ef u z z ) , c l u s t e r i n gp r i n c i p l e sa n dm e t h o d s ，a n dd i s c u s st h em o s tf i e q u e n t l 3 7u s e da l g o r i t h m s f u r t h e r m o r e ，an o v e lm i n i m u ms p a n n i n gt r e e ( m s t ) f o rh i g h d i m e n s i o n a ls p a r s ed a t ao b j e c tf e a t u r ew e i g h t e df u z z yc l u s t e r i n gi sp r o p o s e d ，w h i c hc a r lm e r g et h eh i g h d i m e n s i o n a ls p a r s ed a t ae f f e c t i v e l y , m a k et h ec l u s t e r i n gr e s u l tc l o s et ot h er e a ld a t as t r u c t u r e ，a n dh i g h e rc l u s t e r i n gq u a l i t y c a nb eo b t a i n e d b e c a u s eo ft h ei m p o r t a n c ea n ds p e c i a l i z a t i o no fc l u s t e r i n ga n a l y s i s ，g r e t ap r o g r e s so ft h i s f i e l dh a sb e e nm a d ei nr e c e n ty e a r s ，a n dm a n 3 ，c l u s t e r i n ga l g o r i t h m sh a v ea p p e a r e d c l u s t e r i n ge n s e m b l ei sf lm e t h o df o rc o m b i n i n gd i f f e r e n tp a r t i t i o n sw h i c hp r o d u c e db yd i f f e r e n ta l g o r i t h m so rb yo n ea l g o r i t h mi nd i f f e r e n tp a r a m e t e r s i th a sb e e np r o v e da l le f f e c t i v em e t h o dw h i c hl e a d st ob e t t e rr e s u l tt h a ns i n g l ea l g o r i t h m m o s tr e s e a r c h e st h i n km o r ea b o u tc r i s pc l u s t e r i n gc o m b i n a t i o n 。b u ti n v o l v e1 i t t l ea b o u tf u z z yc l u s t e r i n ge n s e m b l e i nt h i st h e s i s ，b 3 7a n a l y z i n gf u z z ys e tt h e o b 7a n de x i s t e n tc l u s t e r i n ge n s e m b l em e t h o d s ，ad e c i s i o nm o d e lf o rf u z z yc l u s t e r i n ge n s e m b l ei sp r e s e n t e d t h eh o v e la 1 g o r i t h mf i r s t l x ro b t a i nt h eo p t i m a p a r t i t i o nw h i c h一一一一一一匿壹至运盔兰巫圭亚窒生兰焦笙奎一一一董夏c a l l e d “e x p e r t ”i 1 1t h i sp a p e rf r o m 日i n d i v i d u a lf u z z 3 ，p a r t i t i o n sg e n e r a t e db yf u z z yc - m e a n sa l g o r i t h mw i t hd i f f e r e n tp a r a m e t e r s t h e n ，w eu s ef u z z yv o t i n gs c h e m et op r o d u c et h e “m a j o r i t yj u d g e r f i n a l l y , t h et w oj u d g e r sa r ec o m b i n e db yd e c i s i o nm o d e l e x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o di na r t i f i c i a ld a t as e t s ，u c id a t as e t sa n dw e bd a t as e t s k e yw o r d s ：d a t am i n i n g ；f u z z yc l u s t e r i n g ；c l u s t e r i n ge n s e m b l e ；d e c i s i o nm o d e l ：f u z z 3 ，c - m e a n s ( f c m ) a l g o r i t h m西南交通大学硕士研究生学位论文j 上页西南交通大学四南父遗大罕学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。本学位论文属于1 保密口，在年解密后适用本授权书；2 不保密口，使用本授权书。( 请在以上方框内打叫”)学位论文作者签名： 寸聿之j 孓火指导老师签名：絮2 ：蔗日期：弘8 s l ?日期：跏乳r 7西南交通大学硕研究生学僮论受箜! i 亟西南交通大学学位论文创新性声明本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。本学位论文的主要创新点如下：1 本文在深入分析模糊聚类分析技术的基础上，对高属性维稀疏数据的稀疏特性进行了重点分析和讨论。针对先验知识缺乏条件下，采用“数据驱动”的思想，挖掘原始数据内在的结构特征，提取特征权值，构造加权差异度计算公式，并采用基于图论的模糊聚类方法为稀疏特征相似关系构造模糊图，利用图上的最小模糊支撑树进行动态聚类。该算法不依赖于初始原型的选择，也无需类属的先验知识，可以真正做到无监督自学习。实验证明该方法有效。2 针对模糊理论与聚类集成相结合方向鲜有人研究的研究现状，本文对“软”聚类集成进行深入研究，并提出了一种基于模糊集理论的模糊聚类集成决策模型。该模型首先对f c m 算法设定不同的初始化参数产生个划分结果，并从中选取一个最优划分，称为“专家决策”。然后，使用投票机制产生一个“多数判决”。最后，通过提出的决策模型将两结果集成，形成最终的聚类集成结果。在人工数据集、u c i 数据集及w e b 数据集上的多组实验，证实了该模型的有效性。西南交通大学硕兰研究兰二学位论文篁! 豆1 1 本文研究背景第1 章绪论进入2 1 世纪，通信、计算机和网络技术正改变着整个人类和社会。随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累了大量数据信息。人们希望能够了解激增的数据背后隐藏着的重要信息，以便更好地利用这些数据。而目前的数据库系统可以实现高效地数据录入、查询、统计等功能，但无法发现数据中存在的关系和规则，从而无法根据现有的数据对未来的发展趋势进行预测。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸”但“知识贫乏”的现象。面对这一挑战，数据挖掘和知识发现( d m k d ) 技术应运而生，并显示出强大的生命力。聚类分析是数据挖掘中非常重要的研究领域和应用技术之一，各种形式的聚类分析方法以及广阔的应用领域为聚类分析研究提供了宽广的舞台。在聚类分析中加入模糊理论，可以使现有的聚类分析方法更加符合复杂的实际情况，由此产生了模糊聚类分析。该分析方法顾及到样本间的联系，能够有效的对类与类间有交叉的数据集进行聚类，所得的聚类结果明显优于硬聚类。在各个领域有着很好的应用前景。由于聚类分析领域的长足发展，各种文献提出了众多聚类算法】，可分为层次方法、划分方法、基于密度的方法、基于网格的方法、基于模型的方法、增量聚类算法等。事实上，任何单一聚类算法都不可能达到普遍适用的效果。面对特定的应用问题，需集成多种聚类算法，以接近数据集本身的真实分布。聚类集成方法将不同聚类算法或在同一算法下使用不同参数得到结果进行集成，从而得到比单算法更为优越的结果。近几年的研究和实验表明，聚类集成方法可以很好地提高聚类算法的鲁棒性和稳定性。目前，已经在医学诊断、基因表达分析、非数值型数据聚类等方面有了一定应用。因此，研究聚类集成方法有着广泛的科研和实际应用价值。1 2 国内外研究现状本文涉及到数据挖掘技术、模糊理论及聚类集成等多领域知识，在这些领西南交通大学硕士研究生学位论文一箜至页域知识飞速发展、现实应用要求不断提两的情况下，各领域知识融合到一起，形成新的交叉理论。在这里，有必要简单介绍一下这些领域的研究现状。1 2 1 数据挖掘技术的发展及研究现状数据挖掘的发展历史与科学技术尤其是人工智能技术的迅猛发展以及数据库技术的发展及应用密切相关。数据挖掘其实是一个逐渐演变的过程，其思想可以追溯到2 0 世纪7 0 年代。随着数据库存储技术和计算速度提高，科学研究人员意识到，还可以利用机器学习的方式来分析数据。机器学习的过程就是将一些已知的并已被成功解决的问题作为范例输入计算机，机器通过学习这些范例总结并生成相应的规则，这些规则具有通用性，使用它们可以解决某一类的问题。随后，伴随着神经网络技术的形成和发展，人们的注意力转向知识工程。知识工程不同于机器学习那样给计算机输入范例，让它生成出规则，而是直接给计算机输入已被代码化的规则，而计算机是通过使用这些规则来解决某些问题。专家系统就是这种方法所得到的成果，但它有投资大、效果不甚理想等不口 巴08 0 年代人们又在新的神经网络理论的指导下，重新回到机器学习的方法上，并将其成果应用于处理大型商业数据库。8 0 年代末在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论会上首次出现k d d ( k n o w l e d g ed i s c o v e r vi nd a t a b a s e ) 这个术语，人们接受了这个术语，并用k d d 来描述整个数据发掘的过程。随后的k d d 国际学术大会研究重点逐渐从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透，数据挖掘和知识发现成为当前计算机科学界的一大热点。随着支持数据挖掘技术的三个基础海量数据搜集、强大的多处理器计算机、数据挖掘算法发展成熟经过数十年的发展，数据挖掘渐渐成为成熟的技术，并在实际应用中取得了良好效果。数据挖掘的研究正方兴未艾，其发展前景已经在国际上得到了确认。目前，国内外很多大学、研究机构和公司都已经在这个方面进行了实质性的研究和产品开发。预计在本世纪，数据挖掘的研究还会形成更大的高潮，研究焦点可能会集中到以下几个方面 ：( 1 ) 研究在网络环境下的数据挖掘技术，特别是在因特网上建立数据挖掘服务器，并且与数据库服务器配合；西南交通大学硕士研究生学位论文第3 页( 2 ) 加强对各种非结构化数据的开采，文本挖掘成为了一个目前研究的热点。其它的非结构化数据有图形数据、视频图像数据、声音数据乃至综合多媒体数据的开采；( 3 ) 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准化；( 4 ) 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解，也便于在知识发现的过程中进行人机交互；( 5 ) 处理的数据将会涉及到更多的数据类型，这些数据类型或者比较复杂，或者是结构比较独特。为了处理这些复杂的数据，就需要一些新的、更好的分析和建立模型的方法，同时涉及到为处理这些复杂或独特数据所做的费时和复杂数据准备的一些工具和软件；( 6 ) 交互式发现：( 7 ) 知识的维护更新。1 2 2 模糊聚类理论的发展及现状模糊聚类是将模糊集的概念应用到传统聚类分析中，让数据集的对象在分类中的隶属用隶属函数来确定，也就是说，对象在各类中的隶属度为连续区间 o ，1 之间的某个值，以不同程度隶属于多个类，而非确定性聚类中的0 或1的二值逻辑。模糊聚类的优点在于能适应那些分离性不是很好的数据，这允许了数据性质的模糊性，为数据结构的描述提供了详细的信息。由于模糊聚类得到了样本属于各个类别的不确定性程度，表达了样本类属的模糊性，即建立起样本对于类别的不确定性的描述，更能客观地反映现实世界，从而成为聚类分析研究的主流之一。1 9 6 5 年美国自动控制专家扎德( l a z a d e h ) 教授首次提出模糊集理论f 5 ) ，模糊数学应运而生。1 9 6 6 年b e l l m a n ，k a l a b a 和z a d e h 共同提出将模糊集概念引入到聚类分析中处理聚类问题。而最早系统地表述和研究模糊聚类问题的是著名学者r u s p i n i 。1 9 6 9 年，r u s p i n i 率先定义了数据集的模糊划分的概念。利用这一概念，人们相继提出了多种模糊聚类分析方法，比较典型的有i ，1 ：基于目标函数的模糊聚类方法、基于相似性关系和模糊关系的方法、基于模糊等价关系的传递闭包方法、基于模糊图论的最大树方法以及基于数据集的凸分解、动态规划和难以西南交通大学硕士研究生学位论文第4 页辨识关系等方法。随着现代技术的进步，计算呈现数据集规模大、维数高、运算复杂等特点m 。目前国内外的研究主要集中在针对现代运算特点寻找新算法上，但仍未有突破性进展。对其研究的重点主要集中在以下三个方面：( 1 ) 对经典f c m 算法的改进方面，包括对f c m 初始化方法研究，参数m的优选问题，目标函数的改进及聚类有效性函数的设计等。如张枸针对f c m 对初始化聚类中心敏感问题，提出的一种基于减法聚类与聚类有效性评判的f c m聚类算法 9 1 ，蔡卫菊、张颖超等提出的基于核方法的模糊聚类”o l ，都大大提高了算法的效率。( 2 ) f c m 算法实用性的研究，目前为止f c m 算法是理论最完备，应用最广泛的一种模糊聚类算法，许多科技人员充分利用该算法，将其运用到模式识别、特征提取、图像分割、古生物类别分析、市场研究和w e b 网上文档分类等领域，研究其实用价值。如浙江大学姚敏教授将改进的f c m 算法运用网络入侵检测方法和分析w e b 日志中去】。( 3 ) 将模拟自然领域中某种现象的计算方法应用到模糊聚类分析中，如神经网络算法，遗传算法，模拟退火算法，进化计算，克隆算法等。这些算法在模糊聚类中都取得了不错的成绩，如李洁、焦李成提出了基于自然计算的模糊聚类新算法【1 2 1 3 ，张志红提出了基于改进神经网络的f c m 算法等。但是现在这些算法还不成熟，存在许多不足之处，需要加以完善。虽然模糊聚类发展的时间较短，尚处于成长阶段，但已经显示出勃勃生机。国际和国内的学者都对模糊聚类的研究非常重视，模糊理论方面的专业学术杂志有：f u z z ys e t sa n ds y s t e m s ( 模糊集与系统，国际模糊系统协会会刊，德国承办) ，模糊系统与数学( 中国模糊系统协会会刊，国防科技大学承办) ，f u z z ym a t h ( 模糊数学杂志，美国) ，b u s e f a l ( 模糊集及其应用研究快报，法国) ，i e e et r a n s a c t i o n so nf u z z ) rs y s t e m ( i e e e 模糊系统，美国电气和电子工程师学会主办) 。而在i e e e 的汇刊中模式分析与机器智能( p a m i ，p a t t e r na n a l y s i sa n dm a c h i n ei n t e l l i g e n c e ) 、系统、人和控制( s m c ，s y s t e m s ，m a n ，a n dc y b e r n e t i c s ) 、模糊系统( f s ，f u z z ) rs y s t e m s ) 、神经网络( n n ，n e u r a ln e t w o r k s ) 、信号处理( s p ，s i g n a lp r o c e s s i n g ) 等几乎每期都有讨论聚类及模糊聚类的文章。从1 9 9 2 年开始的由i e e e 和神经网路理事会共同主办的f u z z i e e e 会议，每两年召开一次，每次至少有3 到4 个专题讨论聚类和模糊聚类分析的最新研究进西声交通大学硕士铲究生学位论文一第5 页展和发展现状。另外，我国作为模糊数学研究的大国，不仅在基石出理论研究上取得了丰硕的成果，而且在模糊聚类的应用研究上亦令世人瞩目，比如基于模糊聚类的天气预报、矿藏识别和医学诊断等等。为了积极引导模糊聚娄分析的理论和应用的研究热潮，国家自然科学基金委员会还专门对“模糊聚类的新方法研究”立了项，作为重点资助项目。1 2 3 聚类集成发展及研究现状聚类集成( c l u s t e r i n ge n s e m b l e c l u s t e r i n gc o m b i n a t i o n ) 又称聚类组合或聚类融合。该概念在2 0 0 2 年首次被as t r h l 和jg h o s h 在文献 1 5 中提出，但类似的研究在2 0 0 1 年已经进行【埔】。集成方法在分类算法和回归模型中的使用已经比较成熟，但在聚类分析领域，发展不过短短几年时间，远未达到成熟的程度。但实验表明，聚类集成方法可以很好地提高聚娄算法的鲁棒性和稳定性，有着很好的发展前景，被誉为聚类分析发展的一个里程碑。目前该领域的研究逐步升温，提出了一些算法：f r e d & j a i l l ，2 0 0 2 t 球1 ，f e m & b r o d l e y ，2 0 0 3 t 9 1 ，m o n ti e t a l ，2 0 0 3 1 ：0 1 都是首先建立实例间的相似度矩阵，然后运用凝聚层次聚类算法进行集成。s t r e h l &g h o s h t - , j 基于超图划分提出了对多个划分进行聚类集成的算法，同时也提出了可以将聚类集成问题看作是一个基于互信息的优化问题，但是它没有提出具体的求解方法。a t o c h y , i - - i 是将要集成的多个划分构成多变量的混合模型。唐伟与周志华f ：3 1 根据不同聚类间的互信息作为权值，使用选择性的加权投票进行聚类集成。f r o s s y n i o t i s f 2 4 呗0 利用b o o s t i n g 算法对聚类进行集成。x z f e m 等1 2 5 使用随机投影法将高维数据投影到低维空间，通过多次投影得到若干个数据子集，然后用e m 聚类算法对每次的投影子集聚类集成，后来他们又综合使用p c a 与随机抽样、p c a 与随机投影等方法产生聚类成员。l i k t m c h e v a 等人口7 】对聚类集成中聚类成员的差异度的影响进行了详尽的讨论，通过实验作者发现聚类成员间较大的差异度将能提高聚类融合的质量。聚类成员之间的差异度可以通过r a n di n d e x ，j a c c a r di n d e x ，a d ju s t e dr a n di n d e x ，m u t u a li n f o r m a t i o n 等来铤量。s t h a d j i t o d o r m 等f 2 x j 进一步研究发现，聚类成员间的差异度与聚类融合质量之间的关系是非单调的，当差异度过大时，聚类融台的质量反而下降。文中指出，适中的差异度将能得到较好的聚类融合结果，该文还给出了寻找适中差异度的方法。一西南交通大学硕铲究生学位论文第6 页总结说来，该领域的研充主要集中在两个方面：如何产生有效的聚类成员，不同的聚类成员之间需要有什么样的差异度；如何设计共识函数以便对聚类成员进行集成，包括对聚类成员结果标志的匹配( 在不同聚类结果中，对实质相同的类给予同样的标志) 等。图1 1 给出了目前聚类集成的主要研究方法。 聚类集舫多。类集成方连，夕，、多设多-s i n g l el i n kc o m pl i n k叫基于c 。o c i a t i 。n 除a v g l i n kl不同算法厂厨嚼 别铜叫投票方法其它未戒崩白一确誊燃，一一_c s p a孓、一叫卜一超图方法f 。重抽样h g p a一一咧麟子焦不例暂萌礁卜- 4 信息论方法m c l a投耪归罐k 、j湄厶j ：苣刑一撕脚j 。r 一f 比r - 1 x 芏随机投影图】1 聚类集成研究方法图未来聚类集成的研究方向应主要集中在以下几个方面：( 】) 若干关键参数的确定，确定聚类的个数是聚类分析研究的热点之一，在聚类集成中，如何确定每个聚类成员的聚类个数、最终聚类的个数以及它们之间的关系将是一个值得探讨的问题。另外，在聚类成员质量差别很大时，聚类集成要给不同的聚类成员赋予不同的权重才可能得到较好的集成效果，权重的设计也是一个需要解决的问题。f 2 ) 在聚类成员产生方面，需要进一步研究不同聚类算法之间的高效融合以及选择不同聚类算法的准则；而聚类成员相互不独立时的聚类集成，高维数据、海量数据的聚类集成，聚类之间存在混叠数据时的聚类集成等都对聚类集成提出了挑战。同时，差异度的量化分析仍需要更深入的研究。( 3 ) 在共识函数设计方面，需要进一步研究“软”聚类( 模糊聚类) 的聚类集西声交通大学硕士研究生学位论史筻上员成及“硬”聚类与“软”聚类的聚类集成。而聚类集成的可扩展性算法、增量式算法的研究也是急需解决的问题。( 4 ) 目前，聚类集成方法已经应用在医学诊断、基因表达分析、非数值型数据聚类等方面，研究聚类集成方法更广泛的实际应用以及现有机器学习方法在聚类集成中的应用都将有重要的意义。1 3 论文主要内容及组织结构本文主要是基于模糊理论进行聚类分析，采用模糊的方法处理高维稀疏数据聚类问题取得了较好的聚类结果。研究聚类集成中模糊算法的集成方法，提出了一种模糊聚类集成决策模型。本文研究的具体内容如下：( 1 ) 研究数据挖掘的主要技术和发展过程，介绍了数据挖掘的任务，详细总结了数据挖掘工具的发展历程及目前存在的流行数据挖掘工具及软件，方便研究人员选择使用。( 2 ) 研究聚类分析方法的基本原理及主要方法，在这个原理基础上继续研究模糊聚类分析的方法和步骤。首先介绍了模糊聚类分析中基本的理论知识模糊集合和模糊关系概念，然后介绍了经典的基于目标的模糊聚类算法f c m 算法，为下文的使用做了铺垫。( 3 ) 针对一类特殊的高属性维稀疏数据的聚类问题，分析一般数据对象之间差异度的衡量方法，根据高维稀疏数据的稀疏特点将其抽象为二态高维稀疏数据聚类问题，引入了稀疏特征的差异度计算公式。但该计算公式隐含假定待分析样本矢量的各维特征对分类的贡献均匀，不考虑各个特征分类的不同影响，为此采用加权方法处理该问题。以往的加权方法是在具有足够多先验知识的前提下简单地为每个特征赋予一定权值。本文考虑当先验知识有限或缺乏时，采用“数据驱动”思想，挖掘原始数据内在的结构特征，提取特征权值。文中利用特征选择技术为特征赋权值，得到加权稀疏特征差异度计算公式，最后采用基于图论的模糊聚类方法为稀疏特征相似关系构造模糊图，利用图上的最小模糊支撑树进行动态聚类。( 4 ) 将模糊理论与聚类集成方法相结合，研究模糊聚类集成。文中就聚类集成目前的研究现状及发展趋势做了详细阐述，并介绍了与模糊聚类集成相关的一些基本理论，在此基础上提出了一种模糊聚类集成模型。该模型首先对f c m西南交通大掌硕士研究生学位论文簋里玉算法设定不同的初始化参数产生日个划分结果，并从中选取一个最优划分，称为“专家决策”。然后，使用投票机制产生一个“多数判决”。最后，通过提出的决策模型将两个结果集成，形成最终的聚类集成结果。全文共分5 章，每章内容如下：第1 章，阐述了选题背景和研究意义，介绍了目前国内外对数据挖掘技术、模糊聚类分析及聚类集成方法各领域的研究现状。，第2 章，概述了对数据挖掘中的关键技术、任务及发展，对数据挖掘工具的发展、使用状况进行详细总结。介绍了聚类分析的概念及主要聚类算法。第3 章，模糊聚类分析的研究。介绍基本的模糊理论，重点介绍模糊集合和模糊关系概念，并给出了f c m 算法的演化和计算过程。第4 章，针对一类特殊的高属性维稀疏数据的聚类问题，提出了基于图论的高维稀疏数据模糊特征加权聚类算法。第5 章，研究聚类集成与模糊理论，提出了一种模糊聚类集成决策模型。西南交通大学硕士研究生学位论文第9 页2 1 数据挖掘概述第2 章数据挖掘综述数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。从实际应用角度上讲，数据挖掘可以定义为：按既定问题目标，对海量数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先运有效的方法。数据挖掘是一门交叉学科，它汇聚了数据库、人工智能、机器学习、统计学、模式识别、可视化、并行计算和神经网络等不同学科和领域，近年来受到各界的广泛关注。同时，数据挖掘也为这些学科的发展提供了新的机遇和挑战。2 1 1 数据挖掘中的关键技术在数据挖掘的处理过程中，数据挖掘方法是最为关键的，而目前数据挖掘的方法主要有以下几类：( 1 ) 关联规则方法：挖掘关联规则就是发现存在于大量数据集中的关联性或相关性，例如关联规则“9 0 客户在购买面包的同时也会购买牛奶”，其直观意义为顾客在购买某些商品的时候有多大倾向会购买另外一些商品。( 2 ) 分类和聚类方法：分类就是假定数据库中的每个对象( 在关系数据库中对象是元组) 属于一个预先给定的类，从而将数据库中的数据分配到给定的类中。而聚类是将实体对象集合依照某种相似性度量原则划分为若干个类似实体对象组成的多个类或簇的过程。分类和聚类都是对目标进行划分，划分的标准是类内差别最小而类间差别最大。分类和聚类的区别在于分类事先知道类别数和各类的典型特征，而聚类则事先不知道。( 3 ) 数据统计方法：使用这些方法一般首先建立一个数据模型或统计模型，然后根据这种模型提取有关的知识。例如，可由训练数据建立一个b a y e s i a n 网，然后，根据该网的一些参数及联系权重提取出相关的知识。( 4 ) 机器学习方法：大多数机器学习方法使用人类的认识模型模仿人类的学习方法从数据中提取知识j 由于机器学习经过多年的研究，已取得了些较满西南交通大学硕士研究生学位论文第10 页意的成果，因此，在数据挖掘中可以利用目前比较成熟的机器学习方法。( 5 ) 多层次数据汇总归纳：数据库中的数据和对象经常包含原始概念层上的详细信息，将一个数据集和归纳成更高概念层次信息的数据挖掘技术被称为数据汇总。概念汇总将数据库中的相关数据由低概念层抽象到高概念层，主要有数据立方体和面向对象的归纳两种方法。( 6 ) 神经网络方法：神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关注。典型的神经网络模型主要分3 大类：以感知机、b p反向传播模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以h o p f i e l d 的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络模型；以a r t 模型、k o h o l o n 模型为代表的，用于聚类的自组织映射方法。( 7 ) 决策树方法：利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信息量的字段，建立决策树的一个结点，再根据字段的不同取值建立树的分支；在每个分枝子集中，重复建立树的下层结点和分支的过程，即可建立决策树。国际上最有影响和最早的决策树方法是j r q u m l a n 提出的i d 3 方法，它对越大的数据库效果越好，在i d 3 基础上后人又发展成各种决策树方法。( 8 ) 序列模式分析方法：主要用于发现一定时间间隔内接连发生的事件。这些事件构成一个序列，发现的序列应该具有普遍意义，其依据除了统计上的概率之外，还要加上时间的约束。( 9 ) 可视化技术：数据与结果被转化和表达成可视化形式，如图形、图像等，使用户对数据的剖析更清楚。2 1 2 数据挖掘的任务数据挖掘主要包括四种任务：预测建模、异常检测、关联分析和聚类分析。f 1 ) 预测建模以说明变量函数的方式为目标变量建立模型。涉及两类建模任务：分类和回归。分类用于预测离散的目标变量：回归用于预测连续的目标变目里。( 2 ) 异常检测的任务是识别其特征显著不i 司于其他数据的观测值。这样的观测值称为异常点或离群点。异常检测算法的目标是发现真正的异常点，而避免错误地将正常的对象标注为异常点。换言之，一个好的异常检测器必须具有高西南交通大学硕士铲究生学位论文一第11 页检测率和低误报翠。异常检测的应用包括检测欺诈、网络攻击、疾病的不寻常模式、生态系统扰动等。( 3 ) 关联分析用来发现描述数据中强关联特征的模式。所发现的模式通常用蕴含规则或特征子集的形式表示。用于搜索空间是指数规模的，关联分析的目标是以有效的方式提取最有趣的模式。关联分析的应用包括找出具有相关功能的基因组、识别一起访问的w e b 页面、理解地球气候系统不同元素之间的联系笙寸o( 4 ) 聚类分析旨在发现紧密相关的观测值组群，使得与属性不同簇的观测值相比，属于同一簇的观测值相互之间尽可能类似。聚类可用来对相关的顾客分组、找出显著影响地球气候的海洋区域以及压缩数据等。2 1 3 数据挖掘工具分析。数据挖掘的发展离不开数据挖掘软件的发展，根据时间的推移以及技术的完善程度进行划分，数据挖掘软件已经经历了四代发展。第1 代数据挖掘软件只能够支持少数几个数据挖掘算法，一般只能挖掘向量数据，数据一般一次性调进内存进行处理。但如果数据太大，或频繁的变化，就需要借助数据库或数据仓库技术进行管理。显然第一代系统的功能非常的有限，不能满足客户的需求。第2 代数据挖掘软件与数据库管理系统( d b m s ) 集成，支持数据库和数据仓库，与之存在高性能的接口，具有较高的可扩展性：能够挖掘大数据集、以及更复杂的数据集；通过支持数据挖掘模式( d a t am i n i n gs c h e m a ) $ 口数据挖掘查询语言增加系统的灵活性。第3 代数据挖掘软件和预言模型系统之间能够无缝集成，使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中：由数据挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持功能；能够挖掘网络环境下( i n t e m e t e x t r a n e t ) i 均分布式和高度异质的数据，并且能够有效地和操作型系统集成；缺点在于不能支持移动环境。目前移动计算技术越来越重要，将数据挖掘和移动计算相结合是当前的一个研究领域。第4 代软件能够挖掘嵌入式系统、移动系统、和普遍存在的计算设备产生的各种类型的数据。但其数据挖掘原型或商业系统尚未见报道。西南交通大学硕士研究生学位论文一_ _ 簋_ 12 页目前币面上数据挖掘应属方面的商品工具和软件种类繁多，大部分属于第2代系统，也有部分属于第2 代系统延续下的相应的第3 代产品，现按照数据挖掘工具类型划分，可分为：( 1 ) 传统主观导向系统：这是针对专业领域应用的系统。如基于技术分析方法对金融市场进行分析。采用的方法从简单的走向分析直到基于高深数学基础的分形理论和谱分析。这种技术需要有经验模型为前提。属于这类商品有美国的m e t a s t a k ，s u p e rc h a r t s ，c a n d l e s t i c kf o r e c a s t e r 和w a l ls t r e e tm o n e y 等。( 2 ) 传统统计分析：这类技术包括相关分析、回归分析及医子分析等。一般先由用户提供假设。再由系统利用数据进行验证。缺点是需经培训后才能使用，同时在数据探索过程中，用户需要重复进行一系列操作。属于这类商品有美国的s a s ，s p s s 和s t a rg r a p h i c s 等。由于近年来更先进的数据挖掘方法的出现和使用，这些厂商在原有系统中综合一些数据挖掘部件，以获得更完善的功能。以上两种技术主要基于传统的数理统计等数学的基础上，一般早己开始用于数据分析方面。( 3 ) 神经元网络删) 技术：神经元网络技术是属于软计算( s o f tc o m p u t i n g )领域内一种重要方法，它是多年来科研人员进行人脑神经学习机能模拟的成果，已成功地应用于各工业部门。在数据挖掘的应用方面当需要复杂或不精确数据中导出概念和确定走向比较困难时，利用神经网络技术特别有效。经过训练后的n n 可以想象具有某种专门知识的“专家”，因此可以像人一样从经验中学习。n n 有多种结构，但最常用的是多层b p ( b a c kp r o p a g a t i o n ) 模型。它已广泛地应用于各种d m 工具和软件中。有些是以n n 为主导技术，例如俄罗斯的p o l y a n a l y s t ，美国的b r a i n m a k e r n e u r o s e l l 和o w l 等。n n 技术也已广泛得作为一种方法嵌入各种d m 成套软件中。其缺点是神经网络容易受过度训练带来的影响，这主要是由于神经网络太灵活，可变参数太多造成的。( 4 ) 决策树：决策树算法是目前应用最广泛的归纳推理算法之一，也是一种简单的知识表示方法，它将事例逐步分类成代表不同的类别。由于分类规则是比较直观的，因而比较易于理解。这种方法一般限于分类任务。在系统中采用这种方法的有美国的i d i s ，法国的s i p i n a 。英国的c l e m e n t m c 和澳大利亚的c 5 0 。( 5 ) 进化式程序设计( e v o l u t i o n a r yp r o g r a m m i n g ) ：这种方法的独特思路是：系统自动生成有关目标变量对其他多种变量依赖关系的多种假设，并形成以内西南交通大学硕士铲究生掌位诠窒篁! ! 夏部编程语言表示的程序。内部程序( 假设) 的产生过程是进化式的，类似于遗传算法过程。当系统找到较好地描述依赖关系的一个假设时就对这程序进行各种不同的微小修正，生成子程序组，再在其中选择能更好地改进预测精度的子程序，如此依次进行，最后获得达到所需精度的最好程序时，由系统的专有模块将所找到的依赖关系由内部语言形式转换成易于为人们理解的显式形式，如数学公式，预测表等。由于采用通用编程语言，这种方法在原则上能保证任何一种依赖关系和算法都能用这种语言来描述。( 6 ) 基于事例的推理方法( c a s eb a s e dr e a s o n i n g ，c b r ) ：这种方法的思路非常简单。当预测未来情况或进行正确决策时，系统寻找与现有情况相类似的事例，并选择最佳的相同的解决方案，这种方法能用于很多问题求解，并获得好的结果，其缺点是系统不能生成汇总过去经验的模块或规则。采用这种方法的系统有美国的p a