（计算机软件与理论专业论文）基于层次的模糊聚类算法.pdf

摘要聚类是数据挖掘的重要分支之一，引入模糊理论的模糊聚娄分析为现实数据集提供了模糊处理能力，在许多领域被广泛应用。本文在对基于划分的模糊聚类算法中模糊c 均值聚类算法及其变种算法进行分析的基础上，围绕不同分布复杂度和数据量的数据集聚类及其输入参数问题进行了较深入的探讨，提出了密集簇中心二次模糊聚类算法s f c c 和基于动态模型的分层模糊聚类算法d m f c 两个基于层次的模糊聚类算法。基于f c m 算法、s f c c 及d m f c 算法，本研究工作对基于层次的模糊聚类过程进行了模块化描述。密集簇中心二次模糊聚类算法中引入聚类有效性度量，避免聚类簇数目作为输入参数，不再偏好发现球形和相似大小的簇分布；为进一步提高算法的模糊聚类能力，提出了基于动态模型的分层模糊聚类算法，该算法基于k _ 最近邻居图的构造和划分，合并过程中综合考虑簇问的整体相似度和内在结构的相似性，在分布复杂的数据集上有较强的模糊聚类能力。针对f c m 算法、s f c c 及d m f c 算法这三类算法的具体实现，对比给出不同数据量及分布复杂度的数据集模糊聚类结果，经实验结果可视化对照及时间复杂度分析，表明本研究工作提出的s f c c 算法与d m f c 算法在不显著增加时间复杂度的前提下，对分布复杂的数据集具有较高的模糊聚类能力。关键词：模糊聚类，f c m 算法，层次，多代表点，动态模型a b s t r a c tc l u s t e r i n gi so n eo ft h ei m p o r t a n tt a s k si nt h ef i d do fd a t am i n i n g + f u z z yc l u s t e r i n ga n a l y s i sw h i c hi n t r o d u c e st h et h e o r yo ff u z z ys e t s ，p r o v i d e st h ec a p a b i l i t yt h a tc a nb eu s e dt 0d e a lw i t hr e a lf u z z yd a t a s e t s a n di th a sb e e nw i d e l yu s e di nm a n yf i e l d s b a s e do nt h ea n a l y s i so ft h ec l a s s i cf u z z yc m e a n sc l u s t e r i n ga l g o r i t h ma n di t sv a r i a t i o n ，w h i c hb e l o n gt ot h ef u z z yc l u s t e r i n ga l g o r i t h m sb a s e do np a r t i t i o n s ，t h ep a p e rp r o p o s e st w of u z z yc l u s t e r i n ga l g o r i t h m sa n dam o d u l ed e s c r i p t i o nw h i c ha r eb a s e do nh i e r a r c h i e s a m o n go ft h e mt h es e c o n d l yf u z z yc l u s t e r i n ga l g o r i t h mb a s e do nt h ec e n t e r so fd e n s ec l u s t e r sw h i c hi n t r o d u c e ss o m eq u a l i t ym e a s u r e m e n ta b o u tc l u s t e r i n g , a v o i d st h en u m b e ro fc l u s t e r st ob et h ei n p u tp a r a m e t e r t oi m p r o v et h ec a p a b i l i t yo fa l g o r i t h m sd e a l i n gw i t hf u z z yd a t a s e t s ，p r o p o s et h eh i e r a r c h i c a lf u z z yc l u s t e r i n ga l g o r i t h mb a s e do nd y n a m i cm o d e l i n g o nt h eb a s eo ff c ma n do t h e rt w oa l g o r i t h m sm e n t i o n e da b o v e ，t h ep a p e rd e s c r i b e st h ep r o c e d u r eo ff u z z yc l u s t e r i n go nd a t a s e t sb a s e do nt h eh i e r a r c h i e si nm o d u l e s s f c cu s e st h em o s tp o s s i b l ec l u s t e rn u m b e ra st h ei n p u tp a r a m e t e ro t h e rt h a nt h ed i r e c tc l u s t e rn u m b e rb e c a u s eo ft h eq u a l i t ym e a s u r e m e n ta n dd o e sn o tp r e f e rt of i n dt h eg l o b a la n ds i m i l a rs i z ec l u s t e r s b a s e do nt h ek - n e a r e s tn e i g h b o rg r a p h ，d m f ca n a l y s e sa n dc l u s t e r st h eo r i g i n a lp a r t i t i o n i m p l e m e n t i n gf c m ，s f c ca n dd m f ct h e s et h r e ea l g o r i t h m sa n dr e s p e c t i v e l yv e r i f y i n gt h e mo nv a r i o u sd a t a s e t s ，t h ec l u s t e r i n gr e s u l t sa n dt h ea n a l y s i so ft i m ec o m p l i c a t i o ni n d i c a ! et h a tt h ea l g o r i t h m st h i sp a p e rp r o p o s e sa r ev a l i di nd e a l i n gw i t hf u z z yd a t a s e t s k e y w o r d s ：f u z z yc l u s t e r i n g ，t h ef c ma l g o r i t h m ，h i e r a r c h i c a lc l u s t e r i n g ，r e p r e s e n t a t i v ep o i n t s ，d y n a m i cm o d e l i n g第一章引言1 1 数据挖掘简介第一章引言数据挖掘“1 是一种在大型数据集中寻找有趣或有价值信息的过程，聚类分析是它的主要功能之一。与分类和预测不同，聚类是在无指导的情况下分析数据对象，继而产生对象所属的类标记。在聚类过程中，将对象根据最大化类内相似性、最小化类问相似性的原则进行分组，得到数据集的簇划分结构。数据挖掘的发展建立在相关学科发展的基础上。随着数据库技术的发展及应用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，简单的查询和统计已经无法满足人们的需求，需要出现一种挖掘数据背后隐藏的知识的手段。嗣瓣，计算氍绞术懿簧一赣域人工餐辘鑫1 9 5 6 年诞生之嚣取镶了重大遂篪。经瓣7博弈时期、自然语告理解、知识工程等阶段，目前的热点是机器学习。用数据库管理系统来存簇数据，臻辊器学习静方法采分据数撰，挖掘火量数攒鸳薅豹翔漩，这嚣者戆结会捉残了数据库中的知识发现的产生。数据库中的知识发现是- i 7 交叉性学科，涉及到机器学习、模式识别、绫诗学、姆能数攥藤、翔识获取、数据可视缘、赛蛙憩诗算、专象系统等多个领域。扶数据库中发现出米的知识w 以用在信息管理、过程控制、科学研究、决策支持锋许多方谢。鼗据掩籀是翔谈发瑗豹羧心部癸，英主要戏用对象楚海量数攥。数据挖揭技术缝历了鼗十年的发展，戴中包括数理统计、人工锗能、机器学习，加上高性能的关系数据库引攀以及广泛的数据集戏，诖数攥撼撼按寒在当裁的数据龟纛臻壤孛进入了实耀瓣玲段。根据最近g a r t n e r 的h p c 研究表明，“随着数据捕获、传输和存储技术的快速发展，大型系统翻户将更多建爨要袋蠲薪技米来挖獬审场鞋终的价蓬，采嗣更麓广阔瓣莽章亍娃理系统来到建新的商业增长点”。随着数据挖掘辅知谖发现d m k d ( d a t am i n i n ga n dk n o w l e d g ed e t e c t i o n ) l 盼硼：究逐步走向潦入，已经彤成了三根强大的技术支柱；数据库、人工智驻和数理统计。翻前d m k d 的主要研究漆容趣搔鏊穑理论、发现舞法、数据仓库、可褫伍技术、定性定量互捩穰爱、翔 ；i 表示方法、发现知识的维护和辩乖j 用、半结构化和非结构化数据中的知识发现以及阀上数据挖掘等。数据挖掘的目标是从数描集中发现隐含的、有意义的知识，它综合成用多个举科技术，具商较多的功能，当前的主要功能如下。注意，数据挖掘的备项功能不是独立存在的，它 f 在数据挖掘中强相关联，共同发挥作用。分类：控出攒述著区分数撂娄或撰念的蠖溅，跛便髓用模黧泉预测类糕记来知的对象类剐。i青岛大学硕士论文例如：银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据类别模型来区分新申请贷款的客户，以便采取相应的贷款方案。聚类：识剔出对象类别的内在规则，按照这些规则把对象分成若干类。例如：按申请人的风险特征可聚类形成高度风险、中度风险和低度风险申请者三个分组。关联规则和序列模式的发现：关联是某种事物发生时其他事物也会发生的一种联系。例如；每天购买啤酒的人也有可能购买香烟，其概率可以通过关联的支持度和置信度来描述。与关联不同，序列是一种纵向的联系。它加入了时间维的影响。例如：今天银行调整利率，明天股市的变化。预测：把握对象发展的规律对未来的发展趋势做出预见。例如对未来经济发展的判断。孤立点分析：对象中少数的、极端的特例的描述，揭示内在的原因。例如：在银行的1 0 0万毫交易中有5 0 0 例的欺诈行为，银行为了稳健经营，就要发现这5 0 0 例的内在因素，减小以后经营的风险。1 2 数据挖掘的方法及工具作为门处理数据的新* 技术，数据撼搁有许多新特征。首先，数据挖掘谳对的是海董数据，这也是数据挖掘产生的原因。其次，数据可能是不完全的、有噪声的、随机的，有簸杂的数据结构，维数犬。最后，数据挖獬是许多学科的交叉，运用了统诗学，计算瓿，数学等学辩的技术。以下是常见和应用最广泛的方法和模型；( 1 ) 传统统计方法：抽样技术；我们潮对的是犬量的效攒，对所有的数据进行分拼是不可缝豹也是没有必要的，就要在理论魏指导下进行合理的抽样。多戈统计分析；因予分辑，聚类分析等。统计预测方法，翔回归分析，时间序列分析薄。( 2 ) 埘程纯鼓术：翅豳褒等方式恕羧据特征童瘸她表述出采，熟壹菇强等，这其孛运建豹 每多是描述统计的方法。可视化技术砸对的一个难题是满维数据的可视化。( 3 ) 决策楗：零l 雳一系列援鹚筵| | 分，建袁褥获銎，蜀用予努类蠢颈溺。攀弼戆簿法毒c a r t 、c h a i d 、i d 3 、c 4 5 、c 5 0 簿( 4 ) 神经隧络：模藏入豹神经元动能。经过输入鼷，隐藏鼷。输甑膳等。辩数据避稃调整、计算，最后得到络果，可用于分类朔回归。( 5 ) 遗传算法：基于惑瞧进纯瑷论，楱撤基因联食、突变、选择等过程的一种优纯技术。关联援鬟g 挖箍算法：关联巍摄l l 是接述羧蕹项乏闳存在芙系豹燕簧l l ，形式秀“a l a a 2 a a n - - b l a b 2 b n ”。一般分为两个步骤：求出丈数据项榘。用犬数据项集产生关联规2第一章引言则，等。除了上述常用方法之外，还有粗糙集方法，模糊集合方法，贝叶斯信念网络k 最邻近算法1 3 聚类分析与分类分析不同，聚类分析输入的是一组无类标记的对象，f 且这些对象应分成几类事先也不知道。聚类分析通过分析数据集中的数据对象根据一定的分类规则，合理地划分对象集合，确定每个对象所属类别。它所采用的分类规则是由聚类分析工具决定的。聚类0 1 将数据点集合分成若干类或簇( c l u s t e r ) ，使得每个簇中的数据点之间最大程度地相似，而不同簇中的数据点最大程度地不同，从而发现数据集中新颖有用且可以理解的模式或数据分布。常见的聚类方法有基于划分、层次、密度、模型和f 日格等。聚类分析有着广泛的应用，包括模式识别，数据分析，图像处理，以及市场研究领域等。通过聚类，人们能够识别密集和稀疏的区域，进而发现全局的分布模式及数据属性之间有趣的相互关系。聚类分析在数据挖掘中的应用主要有以下几个方面：( 1 ) 聚类分析可以作为其他算法的预处理步骤这些算法继而基于生成簇进行处理。比如，它可以作为特征化和分类算法的预处理步骤，也可将聚类结果用于进一步关联分析。( 2 ) 可以作为一个独立的工具来获得数据的分布情况，然后观察每个簇的特点，集中对某些特定的簇进一步分析。可用在市场细分、目标顾客定位、业绩估评、生物种群划分等方面。( 3 ) 聚类分析可以完成孤立点挖掘。许多数据挖掘算法试图使孤立点影响最小化，或者排除他们，然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。1 4 模糊集基础经典集合论只能把自己的寝现力限制在那蝤有明确外延的概念和事物上，它明确地限定：每个集合都必须由明确的元素构成，梵素对集螽的隶属获系必须怒明确的，决不能模棱两可。但楚t 在客瓣世界中酱遍存在着大量的横期现象，且现代科技所搿对的系统日益复杂，模糊性总楚伴随着复杂性出现。1 9 6 5 年，美国控制论专家、数学家蠢德”发表了论文模糊懿合，标志着模糊数学这门学科的诞生，人们开始翅摸期集合理论对模糊现蒙进行研究。模糊粜的定义：设a 是论域x 到【o ，l 】的一个映射，即a ：x 一【o ，1 】，戈一爿和) ，则称a3青岛大学硕士论文是x 上的模糊集，而函数4 ( ) 称为模糊集a 的隶属函数，爿 ) 称为x 对模糊集a 的隶属度。模糊集合的序对表示法为：a - o ，a o ) ) l 工z a 若x 为有限集，则a 也可以用向量表示法来表示。模糊集“的并交等运算是分明集相应运算的自然推广，且可以推广到任意多个模糊集合中去。在模糊聚类中可能用到的是模糊集的a 截集，它可以将模糊集合转化为普通集合，定义为：设4 为x 上的任一模糊集，对任意0 a 1 ，记a a - - ( x 蚝蕊爿a ) ，称爿a 为a 的a 截集，a 称为阈值或置信水平。模糊关系。在模糊聚类分析中也经常用到。下面介绍它的定义。设x 和y 为论域，若r 是笛卡尔积x y 上的模糊集，则r 为x 到y 的模糊关系。r a 为a 截集关系。若r 满足自反性和对称性，则r 为模糊相似关系；若r 还满足传递性，则称为模糊等价关系。若一个矩阵元素取值在【0 ，1 】区间内，则称该矩阵为模糊矩阵。模糊关系通常用模糊矩阵的形式表示。模糊聚类分析和模糊模式识别都是研究对象的分类问题，但后者的弱的是要判断对象属于哪一个已知类，而前者是将对象按各自的特性进行合理的分类，事先并无标准的模式可循。所以，模糊模式识别是有模式的分类，而模糊聚类分析是无模式的分类。另外，因为数据聚类不需要利用已知类的信息。所以它是一种非监督学习的方法，解决方案是数据直接驱动的。模糊聚类结果中对象与簇之间的映射所体现的就是模糊集合，也就是要求解的模糊隶属度矩阵。1 5 模糊聚类分析现鬟数据集的数据分瘴里现黄不同的形态，对这魑数据集进行聚类时会发现，期待形成的簇之间可能存在确定性边界，也可能存在模糊边界，这种模糊燕事物或对象的差异之间存在中间过渡过程的结果，且在现实世界中大量存在着。经典集合论憝确定性的，无法描述这种模糊性；1 9 6 5 年z a d e h 提出模糊集的概念，解决了该翅题，也就是说，用模糊集可以有效描述实嚣盛髑孛具骞模期性震的数据对象。聚攒的目标魁以某种方式构造分组，以便组内对擞间最大程度相似，不同组中的对象间最大程度耪舞。簧绞翡聚类君法哥戳褰袈筵理黠象隶震彀鞠确豹羧攥集，帮婕统聚赛分褥蕊一耱硬划分，它把每个待辨识的对象严格地划分到某个类中，具有非此即彼的性质，因此这种分类的类鬟界辍，霹簇芝滔齄逑器是分臻骢。瑟实嚣鑫薅夸大多数黯象势没弩严揍鹩隶簸性，窀嚣i 在性质和熊属方面存在着模糊性照适合进行模糊聚凝处理。穰糊聚类辨怒将模糊兼静禳念瘦蠲到赞绕聚类分拼串，谴数据集瓣辩象在努缀孛鹣裳蔗强隶4第一章引言属函数来确定，也就是说，对象在各分组中的隶属度为连续区间【0 ，1 】之间的某个值，可以以不同程度隶属于多个簇，而非确定性聚类中的0 或l 的二值逻辑。模糊聚类的优点在于能适应那些分离性不是很好的数据和类，这允许了数据性质的模糊性，为数据结构的描述提供了详细的信息。由于模糊聚类得到了撵本属于各个类别的不确定性程度，表达了样本类属的模糊性，即建立起样本对于类别的不确定性的描述，更能客观地反映现实世界，从而成为聚类分析研究的主流之一。另外模糊聚类中应用的隶属函数通常是基于距离函数( 相似性度量) 定义的，以便隶属度描述对象与簇中心的近似程度。模糊聚类中应用的度量函数咀及聚类所需的维度约简等基本操作可直接继承传统聚类分析中应用的规则来确定，以便模糊聚类过程可以得到有效的、符合实际的聚类结果。数据点之间的距离在聚类中起了重要的作用，度量距离的方法应仔细选择。模糊聚类继承了传统聚类中常用的一些相似性度量方法。比如，当属性的均值和方差有较大的变化范围时，不应直接使用欧氏距离，因为大值的属性会让小值的属性失去影响，这时使用预处理的标准化过程即可，考虑属性问的相关性在模糊聚类中同样会收到良好韵效果。模糊聚类分析最直接的方法”1 是基于模糊等价关系来计算模糊聚类，在其基础上的改进主要就是最大树算法。而模糊聚类分析中实际应用较为广泛的则是基于划分的方法，该类方法设计简单、解决问题的范围广，最终还可以转化为优化问题而借助经典数学的非线性规划理论求解，且易于计算机实现。模糊聚类理论“1 的发展推动了其在生产实践中的应用，反过来实际应用的需求又促进了模糊聚类理论的不断丰富和完善。随着理论的发展，模糊聚类已经在众多的领域获得广泛的应用，并取得了令人满意的效果和可观的效益。模糊聚类是一种非监督学习的方法，在模式识别、数据挖掘、计算机视觉以及模糊控制等领域有广泛的应用，其应用范围涉及到通讯系统中的信道均衡、矢量量化编码中的码书设计、时间序列的预测、神经网络的训练、参数估计、医学诊断、天气预摄、食品分类、水质分析等。1 。6 本文的主要研究成果及内密本文针对基于划分的模糊聚类算法存在的问题，提出了两类改进的模糊聚类算法，并对模糊聚类过程避行模块他。为叙述方便，本文中冀法实理是缝理豹数据郡是数媲型，以便诗算度量时采用欧氏度量即可。下面就本文要研究的圭簧内容和结构作一个简单介绍。本文静磷究凌聚翔续起来燕要篷含；1 、日i 入聚类有效性魔量和孤立点处理方法，提出可扩展的密集簇= 次模糊聚类算法。5青岛大学硕士论文2 、基于k 最近邻居图和图划分思想，提出了基于动态模型的分层模糊聚类算法。3 、基于上述两类算法和经典f c m 算法，将基于层次的模糊聚类过程进行模块化，便于进一步的改进和优化。本文的结构安排如下：第一章简要介绍了数据挖掘的基本功能、常用方法以及聚类分析的有关内容，随后介绍了模糊集合理论的基础知识。在此基础上介绍了本文研究重点模糊聚类分析。确定了本文的研究范围和基本框架。第二章阐述了聚类分析中的数据类型、对象间相异度计算方法、聚类常用方法和有效聚类方法应满足的典型需求；随后对模糊聚类分析的等价闭包法、最大树算法和应用最为广泛的基于划分的模糊聚类算法等常用方法进行了分析。第三章基于前砸的分析研究，提出了两个基于层次的模糊聚类算法即s f c c 算法和d m f c算法。在此基础上，对模糊聚类过程进行了模块化。第四章叙述了s f c c 和d m f c 算法的具体实现，以及以它们为基础的模糊聚类分析系统f c a s 的工作流程等。第五章针对聚类系统f c a s 中各类算法，对不同数据量及分布复杂程度数据集的实验结果进行了综合分析评价。第六章对本文进行了总结概述，并对今后的工作进行了展望。6第二章聚类分析及模糊聚类方法第二章聚类分析及模糊聚类方法将物理或抽象对象的集合分组成为由类似对象组成的多个类的过程称为聚类。聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对蒙彼此相似，与其他簇中的对象之间彼此相异。在许多应用中，可以将一个簇中的数据对象作为一个整体来对待。从本质上来讲，模糊聚类分析继承了传统聚类分析的诸多特征以及基本操作方法，也就是说，它与聚类分析的相关性远胜过与模糊集理论的相关程度。本章详细介绍聚类分析中数据类型及相应预处理方法，如标准化操作、对象间相异度的常用度量方法、常用聚类技术的分类以及一个好的聚类方法应满足的典型需求等。聚类分析原本是数理统计中多元分析的一个分支，是指按照一定的要求和规律将事物进行分类的一种数学方法。由于现实的分类往往伴随着模糊性，所以用模糊数学的方法进行聚类分析会显得更自然，更符合客观实际，这就是模糊聚类分析，它已成为模糊理论应用最广泛和最富成果的领域之一。如何得到有效的聚类方法是当前研究中的热点，一般说来，模糊聚类方法根据其发展历程或难易程度，主要有等价闭包法、晟大树算法“和基于划分的模糊聚类算法等。本章将对这三类方法的基本流程和优缺点进行详细介绍。聚类有效性的度量方法作为聚类质量的评价指标，可用来启发聚类中的迭代过程。常用的聚类有效性度量方法将在本章第五部分介绍。2 1 聚类分析中的数据类型假设待聚类的数据集包含n 个数据对象，每个对象由p 个变量( 也称为度量或属性) 表示这些变量可能是下列类型的某一种或多种的组合。( 1 ) 区间标度变量区间标度变量是一个粗略线性标度的连续度量，典型的例子如重量和身高等。选用的度量单位将直接影响聚类分析的结果，一般说来，单位越小，变量可能的值域就越大对聚类结果的影响就越大。为避免对单位选择的依赖，数据应当标准化。标准化度量值试图给所有的变量相等的权重，当没有关于数据的先验知识时，这样做是十分有用的。标准化的一种方法是将原来的度量值转化为无单位的值，给定一个变量f 的度量值，可用下列方法实现变换：( i ) 计算平均绝对偏差s ，：s ，一砉( _ j i - m li + i 也! - m fl + + i 一m ，i ) ，这里的7青岛大学硕士论文_ ，白是f 的n 个度量值，m ，是f 的平均值，即m ，t 丢( ，+ x ：，+ + )( j i ) 计算标准化度量值z - s c 。r e ：z f ；鱼! 里，这里使用的平均绝对偏差s ，比标准差盯r( j i ) 计算标准化度量值z - s c o r e ：。f = 垫二! - 上，这里使用的平均绝对偏差5 ，比标准差盯r口对于孤立点具有更好的鲁棒性。实际应用中，是否和如何进行标准化的选择被留给了用户。若读者对标准化方法感必趣，可参见文献中数据预处理的规范化技术部分。区间标度变量所表示对象间的相异度是基于对象间的距离来计算的，最常用的是欧几里德距离( 也称欧氏距离) ，定义如下：d ，z j ) a | ，- - x ，。1 2 + i t ：一- 2 1 2 + + l 一b 1 2 ，这里的t 一 。，x i 2 ，一) 和x j 一0 1 ，x j 2 ，工扭) 是两个p 维的数据对象。另一个著名的度量方法是曼哈坦距离，其定义如下：d ( 而，x j ) 叫玉l z ，1 l + l 鼍2 一算j 2 l + - 。+ i 一x 加i 。明考斯基距离是上述两种距离的概化。它的定义如下d “，x ) 。( i 玉l - - x j l p + i 五2 - - x j 2 i q + + i 一z pr ) ”。，这里的q 是一个正整数。当q = 1时，它表示曼哈坦距离，当q - - 2 时表示欧氏距离。如果每个变量根据其重要性赋予一个权重，则可得加权的距离度量，如加权欧氏距离定义为：d ( x i ，z j ) - w l i x , l - x j l f + 心i 2 一j j 2 r + 。- 。+ _ i 一x 扭f 。( 2 ) 二元变量二元交耋廷有0 和1 蘸个状态，0 表示该交羹为空，1 表示 轰交量存在。秀讳舞二元变囊对象而和x 的相异度，已知其中任一个= 元变擞，在对壤中表现的度量值和b 熙有四种组合状态，计藏簿种缍合状态斡燕董数爵，以表格形式列为t8第二章聚类分析及模糊聚类方法表2 1 二元变量的组合状态表l0求 【l1qrq + r0ts + 1求和q + sr + tp ( 对象的总维数)在表2 1 中，q 是对象薯和_ 值均为1 豹变量数目，其余各项的意义类似。二元变量分为对称和不对称两类，它们的相异度计算方法不同。其中，当变量的两个状态有相同权重时是对称二元变量基于该类的相异度称为恒定的相异度，最著名的评价系数是简单匹配系数，定义为：d ( 玉, x j ) ：2 l ，计算过程中分母始终为p o 如果变量的两个状口+ r + s + t态不是同样重要，则该变量为不对称；基于不对称二元变量的相异度称为 恒定相异度，最著名的是j a c c a r d 系数，在它的计算中，负匹配的数目t 被认为是不重要的，因此被忽略：d 岛，其中 - 1 ，f ) 为某1 3青岛大学硕士论文( 3 ) 在相关程度为a ，的对象间连接一条边，并在相应的边上注明a ，( 不出现相交线) ，若在连接某两对象时出现回路，则不连此边( 4 ) 依次对如，如( j ) 重复步骤( 3 ) 直至全部对象连通为止( 不一定到f 步) 从而得到晟大树( 此树不唯一)( 5 ) 取口【o ，1 】，去掉线段上值小于口的连线，剩下互相连接的对象则在水平口下归于一类最大树方法是基于图论的模糊聚类方法，它通过求解加权图的最大生成树，实现了数据集的模糊聚类。该方法基于图论中的基本性质，使得聚类过程和聚类结果具有直观且易于理解等优点；但是用最大树方法聚类虽然可以省去对模糊相似关系求解传递闭包的过程，性能较有改善，却也要为相似矩阵表示的加权图计算最大树，仍需要大量的计算和存储空间，所以最大树方法和等价闭包法都不适合对中大型数据集进行模糊聚类分析。另外，上述两种方法对数据集的模糊聚类结果相同，具体证明过程参见文献【4 】。2 6 基于划分的模糊聚类方法前面介绍的模糊聚类基本思想是：给定数据集x 一 葺，z 2 ， ，确定置信水平口，考虑在口一水平上的模糊聚类。其模糊不确定性通过口体现d 确定后的聚类结果是确定的。而现实数据集中的对象在各簇中的隶属常有不确定的现象，这就要求聚类分析的过程和结果都具有模糊性。合理的聚类准则保证得到合理的聚类结果，在基于划分的聚类中使用的准则是最小平方误差和。具体说来，定义适当的目标函数来表示对象与聚类中心的相异度，聚类准则为寻求最佳的模糊聚类结果，使得目标函数取最小值。通常使用交替优化的方法来解决这类多元非线性规划问题，求取全局最优解的近似结果。基于划分的模糊聚类方法可以实现聚类结果的模糊性，在介绍具体的算法之前先引入模糊划分的概念：设数据集盖- 墨，工2 ，) ，毛r 。且而一“1 ，五2 ，而) ，i - 1 ，2 ，- ，h 设p , n为正整数且p 瑚，d - ) w 是模糊矩阵，且满足条件“n ，薹如1 1 q 1 慨，善氐 o 。称d 为x ( p ，n ) 的模糊划分矩阵，矩阵的任意元素d * 表示对象薯在第k 个划分中的隶属程度自1 9 6 9 年r u s p i n i 首先提出第1 个解析的模糊聚类算法以来，已经有很多人提出了新的模糊聚1 4第二章聚类分析及模糊聚类方法类算法。基于模糊划分的模糊聚类算法，其主要思想是将经典划分的定义模糊化，文献中主要有两种比较成功的思路来实现这种模糊化，一是在c 一均值算法的目标函数中引入隶属度函数的权重指数。“，二是在c 一均值算法目标函数中引入信息熵。2 6 1 引入隶属度函数的权重指数( 一) 经典模糊c 一均值聚类( f c m ) 算法由d u n n 提出并由b e z d e k 加以推广的模糊c 均值( f c m ) 算法。1 ，是目前应用最广泛的模糊聚类算法，主要应用领域有数据挖掘、模式识别和图像分割处理等。f c m 算法是一种基于划分的模糊聚类算法，这类算法实际上是将聚类问题转化为经典数学中的多元非线性规划来求解也就是说，在隶属度约束条件和非线性多元目标函数确定的基础上，得到目标函数最优时变量的状态值，从而获得最优的模糊划分。该方法设计简单、解决问题的范围广，并易于计算机实现。下面详细介绍f c m 算法：算法输入：待聚类的数据集d 和簇数目c 。目标函数：，2 善荟“弘2 )其中，n 为数据集中的对象数目，“目表示对象薯在簇。中的隶属度，d ，工) 为对象一与x ：之间欧氏距离的度量。m 为隶属度的权重指数，它控制聚类划分的模糊程度。m 取l 时，对应于传统的确定性聚类；i l l 越大，对象在各簇中的隶属度过渡就越光滑；m 趋向于无穷时，对象在每个簇中的隶属度几乎相同。实际应用中，m 的典型值区间为【1 2 5 ，2 。约束条件：( 1 )( 2 )( 3 )约束( 1 ) 保证任一个对象在所有簇中的隶属度之和均为1 ：约束( 2 ) 保证隶属度为非负，这两项都类似于事件发生的概率需满足的条件；约束( 3 ) 保证簇为非空。1 5h坨心222ill_篁zj，l0盘，绷。y白。r智童曼查兰堡主堡塞隶属度和簇中心的更新方程是通过最小化约束条件下的目标函数j 扶得的。对于非线性多元函数的优化问题，一般采用交替优化( o ) 的方式来求解最优状态时变量的状态值。具体方法是，利用拉格朗日乘数法构成新的方程h ，固定簇中心变量，求h 对于隶属度的偏微分为0时隶属度的表达式；固定隶属度，求解簇中心的表达式。根据以上方法可得，隶属度更新方程c ，为：“乒= ( 砉( 筹) 击 ，若对象而与簇中心重叠，则“f - 1 ，且v s _ ，h 。o 。黼崾新方鲫z 溉垆一( 妻c n ，嘉c ，“) ，这里变量的上标表示迭代数目。算法相关符号：u h h 是一4 n x c 的隶属度矩阵，忙 v 1 ，v ，v 。 是一+ p x c 的簇中心矩阵，其中d 为数据的维数，c 个列向量分另n 表示c 个簇中心。f 伽算法具体流程：( 1 )随机确定c 个初始簇中心构成矿( 1 ) ，选代计数k 初始为1 ，同时确定终止条件使用的闺值s( 2 )用隶属度更新方程( i ) 计算u f i j( 3 )用簇中心更新方程( i f ) 计算p i “1 ( 4 )若0 y 雌一矿( + n 肛即相郐两次迭代簇中心集合的变化小于阈值时则停止遣代过程；否则，k = k + l ，并转到( 2 ) 继续迭代过程。( 5 )算法迭代终止时的矿( 1 和【，n ) 即为模糊聚类得到的簇中心矩阵和隶属度矩阵，用户可根据需求对隶属度炬阵求解相应的口一截集，并转化为所需的聚类划分。p 。l 算法 辛苒蔼单蛊遣算速寝快， 壁冀适台于发鞲球状凝鹜和相儆夫，j 、静壤，且辩曦声鼓舞敏瞎针对f 删算法的种种缺陷，许多人挺出了它的改进算法，主要育以下几种改进方式：改变度羞方式，如在歌式莲离基砬上i l a 踌方差矩阵，壤用海朔鹾离度薰势樊类型鼬数据等等l 改1 6第二章聚类分析及模糊聚类方法变隶属度约束条件，原来的归一化约束假定每个数据点的影响力相同，与实际并不一致，可放松这一要求产生新的算法，使隶属度具有更好的可解释性。下面就介绍一些以f c m 算法为基础的改进的模糊聚类算法。( 二) 模糊g u s t a f s o n k e s s e l ( g k ) 算法g u s t a f s o n k e s s e l ( g k ) 算法1 是f c m 算法的扩展，模糊c 均值算法偏好发现球形簇，簇分布和大小的不同导致f c m 得到次优结果。为了适应数据的不同结构，g k 利用协方差矩阵来捕捉椭圆形簇的特性。令每个簇用簇中心和协方差矩阵共同描述，其中协方差矩阵f ( 的表示如下：m 目) ”o ，一k ) ，一k ) f 1 一互l i 一，将f 的特征值按降序排列，令九和垂n 分别表示其第k。善“个特征值和第k 个单位特征向量。特征值序列表示为4 。4 ：苫九，相应的特征向量9 。到中j ( ) 跨越第i 个簇的线性子空间，第n 个特征向量就是这个线性予空间的标准化。g u s t a f s o n - k e s s e l 算法利用上述协方差矩阵，为每个簇求出其标准导出矩阵a 一( if j ) ”1 1 ( f ) ，在此基础上对象与簇中心的度量定义为砖沪彤o 一石j ) r a “彤蚂一x j ) 。g k 算法通过改进算法应用的度量方式，即引入簇的协方差矩阵，实现了簇发现能力的扩展。g k 算法中目标函数保持不变，隶属度和簇中心的更新方程也是以类似的方法得到的。算法的参数准备：给定簇数目c ( 2 c y 2f 一0 ，1 ，刚停止该划分的局部聚类；否则重复第( i i ) 步，直至满足终止条件。经过多次实验发现，终止2 6青岛大学硕士论文条件中的阈值y 2 设置为初始所有最近对象间距离的均值，即初始数组d i s t 中第二维距离值的均值，这样即可得到较好的初始密集簇集合。( 3 ) 数据集s 局部聚类形成大量初始密集簇，簇中心通过簇中对象的均值计算获得。对象的扔始隶属度分配等价于确定- 陛划分，即对象在所属密集簇中的隶属度为i ，在其他簇中的隶属度均为0 。模糊聚类是为了对那些隶属不明确的对象进行合理的聚类分析，但初始局部聚类所得都是密集簇，对象可以完全属于簇中；在下面进行的二次聚类中将对密集簇聚类，会出现大量隶属不明确的现象，那时候分配给对象的隶属度将不断更新，具有模糊性，以适合实际的数据分布情况。( 4 ) 分析初始密集簇集合，令s 为予簇大小( 即子簇中对象数目) 的平均值，将当前d i s t 数组第二维中距离均值标记为y t 。如果子簇q 的大小墨 y t ，则将子簇c i 标记为临时孤立点簇。注意，标记为临时孤立点簇的子簇集合不参加下一步的二次聚类过程，这样既不会影响到聚类的最终结果，又能减少可能的孤立点对下一步模糊聚类过程的影响。( 5 ) 将初始密集子簇的簇中心( 除临时孤立点簇的中心之外) 构成新的数据集t ，进行二次模糊聚类。为避免f c m 算法中聚类簇数目必须已知等缺点，在二次模糊聚类中引入x i e - - b e n i聚类有效性度量：皿，y 乒) 善善“护22 “，v j ) n 郾n i n ( d 2 形，k ) ) )j _ r ，该度量在第：章中已经介绍，这里不再赘述。二次模糊聚类过程的最终目标为：在晟小化x i e b e n i 聚类有效性度量的情况下，最优化设定的目标函数。s f c c 算法中的二次模糊聚类利用x b 聚类有效性度量来帮助确定数据集中自然的簇数目，该聚类过程描述为：a ) 确定簇数目k 的可能取值范围，k 为区间 2 ，c 的整数，初始化k = 2 。b ) 从数据集t 中随机选择k 个对象构成初始簇中心集合v 。c ) 利用隶属度更新方程计算对象的隶属度向量ud ) 根据u 和簇中心更新方程，计算新的簇中心集合v e )迭代隶属度和簇中心的计算过程，直至目标函数收敛第三章基于层次的模糊聚类算法的研究f ) 计算聚类有效性度量x b ( u ，v ，k ) ，如果k = 2 ，则k = k + l ；否则，令e = x b ( k - 1 ) 一x b ( k ) ，如果e 0 且k c ，则k = k + l ，转到b ) ，否则当前k 的值就是最优簇数e l ；如果k = c ，则前面计算的x b 值取晟小值肘的k 即为最优簇数目。对应蜃优簇数目k 求得的隶属度和簇中心矩阵就是二次模糊聚类所期望的满意解。二次模糊聚类中目标函数以及所需的隶属度约束条件与f c m 算法中相同，所以计算隶属度和簇中心的更新方程同于f c m 算法中的更新方程( 1 ) 和( i d ，这里不再赘述。( 6 ) 得到自然的簇数目和满意的最终划分之后，确定原始对象在最终各簇中的隶属度。对于数据集s 中的对象墨( 1 陶时孤立点簇中的对象除外) ，如果局部聚类后属于密集簇c ，则u ，= u ，即原始对象的隶属度直接继承它所属密集簇的中心在二次聚类中的隶属度向量-i 临时孤立点簇中的原始对象仍保持初始确定划分的隶属度，即这些对象在所属簇中的隶属度为1 ，在其他簇中的隶属度均为0 ：参加二次模糊聚类的密集簇中的所有对象在临时孤立点簇中的隶属度均为0 。医为临时孤立点簇与其他所有簇都具有较大的分离性，不存在隶属不明确的现象，所以上述的隶属度赋值足以表示原始对象的分布情况。( 7 ) 计算最终隶属度矩阵u 的a 一截集，求解满足不同隶属需求的最终簇划分结果。注；第( 7 ) 步是作为可选步骤给出，用户在应用时可通过该步骤处理模糊划分矩阵，得到不同置信水平下的确定性划分。模糊聚类算法s f c c 既完整有效地发现了数据集中所有对象的分布情况，又尽量减少了可能孤立点对模糊聚类过程的影响，所以由此得到的模糊聚类结果比较自然的反映了数据集的原始分布状态。3 2 2s f o g 算法在大型数据集上的延伸为了有效处理大型数据集，使用随机采样的方法来减少模糊聚类算法的输入数据集大小。这样就可以显著改善算法的处理时间，而且，随机采样可以过滤掉大量可能的孤立点，可在一定程度上改进模糊聚类的质量。文献中有许多关于随机采样的有效算法，如交换采样、散列表采样、顺序采样、过度采样以及蓄水池采样等。感兴趣的读者，可参见文献【1 7 1 8 。通过选取适当大小的随机样本，对样本数据集进行聚类处理就可以获得非常自然的原始簇分布，这里不再详细讨论随机采样和确定样本大小的方法。假定我们的模糊聚类算法中采用一种著名的算法来生成合适大小的随机样本。经验表明，产生样本的代价相对于聚类样本的代价来说非常小。青岛大学硕士论文s f c c 算法扩展到大型数据集d 上的聚类处理过程如下所述。将源数据集d 的随机样本作为前面介绍的基于内存的s f c c 算法的输入数据集s 。算法对s 进行模糊聚类，在第( 6 ) 步为s 中的对象分配隶属度完成后，需要为数据集合d - s 中的对象计算隶属度分量，然后再进行第( 7 ) 步的选择性处理。对s 的二次模糊聚类完成后，实际存在两类簇；临时的孤立点簇和密集簇中心集合形成的划分簇。用c l 标记临时孤立点簇的集合，c 2 标记划分簇的集合。d - s 中对象隶属度的计算方法为：从集合c 2 的每个簇中随机抽取n m i n 个簇中心对象( 若某簇的对象数目小于n m i n ，则该簇中对象全部选择即可) 构成集合r ，计算c 2 的各簇中这n m i n个对象间的平均距离，将最小和最大平均距离之和标记为y m 。对于薯e d - s ，计算该对象与r 中数据的距离，用对象与各簇中数据的最近距离来标记对象与该簇的距离，如果置与各簇最近距离的最小值m i n l y m ，即该对象远离c 2 中的所有簇，则必须考虑c 1 中的簇。计算对象五与c 1 中各簇中心的距离，如果所得的最近距离m i n 2 m i n l ，则将该对象作为孤立点簇n a nc i 集合中，否则就将五指定到c l 中最靠近的簇中，这类对象都是以确定性方法赋予隶属度值的。所有对象的隶属度向量都计算完成后，可以选择性的进行s f c c 算法第( 7 ) 步求解不同置信水平下的确定簇划分。注意；c 1 中的簇不参加该过程，因为它们是已经明确聚类的簇。3 3 基于动态模型的模糊聚类算法d m f gs f c c 算法利用多代表点思想，改进了f c m 类型算法的聚类能力，扩展了可应用的数据嶷范围。但是数据集中的对象分布可能非常复杂，即聚类的簇形状和对象的密度可能是任意的，为了对复杂数据分布的数据集进行模糊聚类，发现数据集中自然的簇结构，提出下列基于动态模型的模糊聚类算法d m f c 。d m f c 算法的基本思想为：用k 一最近邻居图捕捉对象的动态邻域，继而用图划分算法形成初始密集簇，分析密集簇在最终模期簇中的可能位置，最终对密集簇进行分层合并，在合并的过程中综合考虑簇的整体相似程度和内在结构的相似性。分层合并的思想源于簇中不同位置的对象有着不同的模糊隶属度，即簇边界的对象在各簇中的模糊程度较大，而簇内部的对象则较强的隶属于当前簇，模糊程度较小。2 9第三章基于层次的模糊聚类算法的研究d m f c 算法中应用了更多的层次聚类策略，基于图划分得到初始密集簇的过程采用分裂式的聚类思想，随后的分层合并过程应用了凝聚式的聚类方法。由此实现了基于动态模型的分层模糊聚类方法，能高质量的实现复杂分布数据集的模糊聚类。令s 表示算法处理的数据集合，共有n 个p 维数据对象。d m f c 算法的基本流程如下：( 1 ) 为数据集s 构造k 一最近邻居图，得到对象相似关系的初步描述( 2 ) 用图划分算法处理k 一最近邻居图，形成初始密集子簇( 3 ) 分析并确定密集子簇的类型( 4 ) 对各类密集子簇实现分层合并的模糊聚类下面详细介绍d m f c 算法的各个步骤。3 3 1 构造k 一最近邻居图用欧氏距离函数，为s 中的对象构造h x n 阶的相似度矩阵a ，v f ，( 1 s i ，n ，i - d ，元素嘞一表示对象i 和j 之间的相异程度即对象间的歇氏距离值，矩阵对角线上的元素值均为仉发现对象气的k 个最近邻居最直接的方法是：从相异度矩阵的第i 行中找到最小的k + 1 个相异度，除i 本身外其余的k 个对象即为鼍的k 个最近邻居。但是，对于较大的n 和p ，该方法并不实用，此时可以为数据集构建适当的数据结构，如k 叉树、分支定界的r 树“1 等