（模式识别与智能系统专业论文）基于模糊矩阵的聚类融合.pdf

硕士论文基于模糊矩阵的聚类融合 摘要 聚类分析是在探索性数据分析领域尤其在数据挖掘和知识发现的一种重要方法，并 且被成功应用于工程，生物学，心理学，药学，市场，等其他学科中。聚类通过抽象出 数据中基本结构作为个体分组或者个体分层来组织数据。 本文的主要工作是不仅在理论上并且通过m a t l a b 对比实验的方法详细分析研究了 聚类融合算法，更重要的是提出了一种新的非常有效的聚类算法，这种聚类方法基于聚 类融合。聚类融合是一个非常强大的工具，可以大大提高非监督分类方法的健壮性以及 稳定性。聚类融合的目的是弥补单个聚类算法的缺陷，因为所有单个聚类对原数据都有 不同程度的依赖以及不同输入参数和初始化对算法都会产生影响。聚类融合算法的基本 思想是通过运行多次聚类算法，这些算法可以是相同算法不同参数，初始值或者不同数 据取样，也可以是不同算法，然后得到多次聚类的结果，一般是带有聚类标签的数据结 构，聚类融合的任务是由这个数据结构产生最终的聚类分割，这一过程称为共识函 数”。聚类融合和普通聚类算法的最大不同之处在于普通聚类的对象是数据集，考虑问 题的要素是数据集的性质，而聚类融合的对象是普通聚类算法产生的结果，考虑的问题 摆脱了数据的分布而是如何最大化共享这些结构信息。聚类融合可以看作是对聚类算法 进行的”聚类”。然而找到一个合适的共识函数是聚类融合中最大的难题，目前常用的 共识函数有基于相似度矩阵，基于超图分割，相互信息，还有基于统计的方法。 这些方法大部分都是利用聚类标签作为共识函数的输入，然而标签向量是硬划分聚 类算法的结果，本文依据概率统计的基本原理，采用模糊聚类作为生成算法以及产生的 模糊矩阵作为共识函数的输入。通过运行多次模糊聚类算法或者类似的软划分算法得到 模糊矩阵，然后由数据点隶属度独立性假设，推导出数据对象的先验概念密度，建立有 限混合模型，并且利用e m 算法估计出数据对象属于每一个模式的数学期望。 本文提出的算法具有非常优良的聚类效果。本文做了大量的计算机实验旨在证明算 法在不同数据分布上的有效性。实验采用了标准u c i 机器学习数据集，结果表明了算法 比别的融合算法聚类正确率更高。 关键词：聚类，聚类融合，混合模型，e m 算法，模糊聚类 a b s t r a c t c l u s t e ra n a l y s i si sa ni m p o r t a n tm e t h o di ne x p l o r a t o r yd a t aa n a l y s i se s p e c i a l l yi nt h ef i e l d s u c ha sd a t am i n i n ga n dk n o w l e d g ed i s c o v e r y , a n di sb e i n ga p p l i e di nav a r i e t yo fe n g i n e e r i n g a n ds c i e n t i f i cd i s c i p l i n e ss u c ha sb i o l o g y , p s y c h o l o g y , m e d i c i n e ，m a r k e t i n g c l u s t e r i n g a n a l y s i so r g a n i z e sd a t ab ya b s t r a c t i n gu n d e r l y i n gs t r u c t u r ee i t h e ra sag r o u p i n go f i n d i v i d u a l s o ra sah i e r a r c h yo fg r o u p s t h em a i nt a s ko ft h i sp a p e ri st od e l v ei n t ot h ec l u s t e r i n ge n s e m b l ea l g o r i t h mi nd e t a i l s n o to n l ys t a y i n go nt h et h e o r yb u ta l s od o i n gm a n ym a t t a be x p e r i m e n t s ，a n dm o s t l y i m p o r t a n t l yc o m eu pw i t hav e r ye f f e c t i v ea n d n o v e lm e t h o dw h i c hi sb a s e do nt h ec l u s t e r i n g e n s e m b l e 。 c l u s t e r i n ge n s e m b l ei sv e r yp o w e r f u lt o o l ，g r e a t l yi m p r o v i n g t h es t a b i l i t ya n dr o b u s t n e s s o ft h eu n s u p e r v i s e dc l a s s i f i c a t i o n c l u s t e r i n ge n s e m b l e i sa i ma ta m e l i o r a t i n gs i n g l e c l u s t e r i n ga l g o r i t h md e f e c t ，b e c a u s ea l ls i n g l ec l u s t e r i n ga l g o r i t h ma s s u m e st h a tt h ed a t aa r e i nd i f f e r e n td i s t r i b u t i o na n dt h eo u t c o m eo fa l g o r i t h mi ss e n s i t i v et o t h ed i f f e r e n ti n p u t a r g u m e n t sa n dd i f f e r e n ti n i t i a l i z a t i o n s ot h eb a s i ci d e ao fc l u s t e r i n g e n s e m b l ei st ov a n e l u s t e r i n ga l g o r i t h mm a n yt i m ew h i c hc a nb es o m ea l g o r i t h mw i t h d i f f e r e n tp a r a m e t e r , d i f f e r e n ti n i t i a l i z a t i o no rd i f f e r e n td a t as a m p l i n g ，a sw e l la si n c l u d i n gd i f f e r e n tc l u s t e r i n g a l g o r i t h m 。a n dt h e nt h ec l u s t e r sr e s u l th a sb e e np r o d u c e d ，w h i c hf o rn o r m a ls i t u a t i o n ，i st h e d a t as 仃u c t i 】r ew i t hc l u s t e rl a b e l s t h et a s ko fc l u s t e r i n ge n s e m b l ec o m b i n e st h ed a t as t r u c t u r e o fm u l t i p l ep a r t i t i o n si n t ot h ef i n a lc l u s t e r i n gl a b e l ，w h i c hu s u a l l yi sc o n s i d e r e da sc o n s e n s u s f u n c t i o n t h eb i g g e s td i s t i n c t i o nb e t w e e nt h ec l u s t e r i n ge n s e m b l ea n dt r a d i t i o n a lc l u s t e r i n g a l g o r i t h ml i e si nt h a tt h et a r g e to ft r a d i t i o n a la l g o r i t h mi s t h ed a t as e tw h i c hs h o u l db e c o n s i d e r e dw h a ti st h ed i s t r i b u t i o na n du n d e r l y i n gs t r u c t u r e w h e r e a st h ec l u s t e r i n ge n s e m b l e c o n c e m sw i t ht h eo u t c o m eo ft h et r a d i t i o n a lc l u s t e r i n g ，i ns t e a do ff o c u s i n go nt h e d i s t r i b u t i o no ft h ed a t as e t ，w h i c hs h o u l db et h et a s ko ft r a d i t i o n a lc l u s t e r i n g ，t h ec l u s t e r i n g e n s e m b l eo m vc a r e sa b o u th o wt om a x i m i z et h es h a r e di n f o r m a t i o ng e n e r a t i n gb yt h eo r i g i n a l o n e c l u s t e r i n ge n s e m b l ec a l lb es e e na st h ec l u s t e r i n gf o rt h ec l u s t e rp a r t i t i o n 。h o w e v e r , f i n d i n gap r o p e rc o n s e n s u sf u n c t i o n ish a r dp r o b l e mi nt h ec l u s t e r i n ge n s e m b l e i nt h ec u r r e n t r e s e a r c h t h ec o n s e n s u sf u n c t i o ni n c l u d e s t h e s i m i l a r i t y m a t r i xb a s e dm e t h o d ， h y p e r g r a p h b a s e dm e t h o d ，m u t u a li n f o r m a t i o n ，a n ds t a t i s t i c a l - b a s e dm e t h o d a l lo fs u c hm e t h o d si su s i n gt h ec l u s t e r i n gp a r t i t i o nl a b e l sa st h ei n p u to fc o n s e n s u s f u n c t i o n ，h o w e v e r , t h el a b e lv e c t o ri st h eo u t c o m eo fh a r dp a r t i t i o nc l u s t e r i n ga l g o r i t h m ，t h i s p a p e rb a s e so nt h ep r i n c i p l eo fs t a t i s t i c sa n dp r o b a b i l i t yt h e o r y , t a k i n gt h ef u z z yc l u s t e r i n g a l g o r i t h m 嬲g e n e r a t i v ea p p r o a c ha n df u z z ym a t r i xa st h ei n p u to fc o n s e n s u sf u n c t i o n t h r o u g hm u l t i p l er u n n i n go ff u z z yo rs o f tp a r t i t i o nc l u s t e r i n ga l g o r i t h m ，t h ea l g o r i t h mt h e n a s s u n l e st h a te a c hd a t ap o i n ti si n d e p e n d e n tw i t hd i f f e r e n tc l a s sb e l o n g i n gv a l u e ，a n dd e r i v e s t h ef o r m u l ao fp r i o rp r o b a b i l i t yo fd a t ap o i n t s w eb u i l dt h ef i n i t em i x t u r em o d e la n du s ee m a l g o r i t h mt oe s t i m a t et h ep a r a m e t e ro f t h ed a t a se x p e c t a t i o no f b e l o n g i n gt oe a c hm o d e l t h ea l g o r i t h mo ft h i sp a p e ri ss u p e r i o ro n m a n yd a t as e t s a n dt h i sp a p e rd o e sm u c hw o r k o i le x p e r i m e n t sd nc o m p a r i n gw i t hd i f f e r e n ta l g o r i t h ma n dd a t as e t s a n dt h e e x p e r i m e n t t a k e st h eu c im a c h i n ee a r n i n gd a t as e t s a n dt h er e s u l ts h o w st h a ts u c hm e t h o di sb e t t e rt h a n t h eo t h e re n s e m b l ea l g o r i t h mo nt h es t a b i l i t ya n dh i g h e ra v e r a g e c l u s t e r i n gp e r f o r m a n c e k e yw o r d ：c 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 ，f i n i t em i x t u r em o d e l ，e ma l g o r i t h m ，f u z z y c l u s t e r i n g i i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 己在论文中作了明确的说明。 研究生签名： 牺 汐拇石月叩 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 硕士论文基于模糊矩阵的聚类融合 1 绪论 1 1 研究背景及其意义 近十几年来，随着计算机科学与技术的发展，计算机被应用到各行各业，人们利用 信息技术生产和搜集数据的能力大幅度提高，不计其数的数据库被用于商业管理、政府 办公、科学研究和工程开发等领域，这一势头仍将持续发展下去。但是，现代化的数据 库技术虽然能够经济、高效地储存、检索与管理这些信息数据流，但却缺乏必要的技术 来帮助我们分析、理解甚至是将这些数据可视化地表达出来。在如此大量的数据背后隐 藏了很多具有决策意义的信息，怎样才能得到这些“知识”呢? 于是，一个新的挑战摆 在我们面前：在这信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能 不被信息的汪洋大海所淹没，而是从中及时发现有用的知识，提高信息利用率呢? 要想 使科学实验数据真正地为科研服务，只有充分对其进行分析、挖掘，帮助科研工作者发 现以前不能发现的问题，找出以前不能找出的规律。要想使数据真正成为一个公司的资 源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数据反而 可能成为包袱，甚至成为垃圾。因此，面对“人们被数据淹没，却饥饿于知识”的挑战， 数据挖掘和知识发现技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘( d a t am i n i n g ) 就是从大型数据库或数据仓库那些大量的、不完全的、有噪 声的、模糊的数据中，提取人们感兴趣的知识，这些知识隐含在数据中，或者人们事先 不知道的、但非常有用的信息和知识【l 引。 数据挖掘是一个多学科交叉领域，涉及机器学习、模式识别、知识获取、统计技术 与智能数据库，专家系统技术等多种技术【3 】。它汇聚了不同领域的研究者，尤其是可视 化、并行计算等方面的学者和工程技术人员。数据挖掘是目前国际上数据库和信息决策 领域的最前沿研究方向之一。数据挖掘技术作为一种重要的商业决策技术已经越来越受 到国际上的重视，并成为企业界研究的一个热点。数据挖掘的成果可以用在信息管理、 过程控制、科学研究、决策支持等许多方面。 在传统的决策支持系统中，知识库中的知识和规则是由专家或程序人员建立的，是 由外部输入的。对于那些决策者明确了解的信息，可以用查询、联机分析处理 ( o n l i n e a n a l y t i c a lp r o c e s s i n g ，简写为o l a p ) 或其它工具直接获取；而另外一些隐藏在 大量数据中的关系、趋势，即使是管理这些数据的专家也是没有能力发现的，这些信息 对于决策可能又是至关重要的，这类问题就可以用数据挖掘来解决。 在科学研究方面，特别是计算科学研究，涉及大量的实验或观测数据分析。在天文 学上，数据挖掘能帮助天文学家发现遥远的类星体：在分子生物学特别是基因工程的研 究上，通过使用计算生物分子有关的分析方法，帮助人们在基因研究上作出了很多重大 1 1 绪论硕士论文 发现。 在商业方面，数据挖掘技术在企业市场营销中得到了比较普遍的应用，它所能解决 的典型商业问题包括：数据库营销、客户群体划分、背景分析、交叉销售等市场分析行 为，以及客户流失性分析、客户信用记分、欺诈发现等等【4 j 。如：在市场营销方面，通 过收集、加工和处理涉及消费者消费行为的大量信息，确定特定消费群体或个体的兴趣、 消费习惯、消费倾向和消费需求，进而推断出相应消费群体或个体下一步的消费行为， 然后以此为基础，对所识别出来的消费群体进行特定内容的定向营销，这与传统的不区 分消费者对象特征的大规模营销手段相比，大大节省了营销成本，提高了营销效果，从 而为企业带来更多的利润；在金融市场，数据挖掘已经应用于股票价格预测、购买权交 易、债券等级评定、资产组合管理、商品价格预测、合并和买进以及金融危机预测等方 面；数据挖掘用于诈骗检测，主要是通过分析正常行为和欺诈行为之问的关系，得到欺 诈行为的特征，当某项业务符合这些特征时，可以向有关人员告警。 在电信业方面，电信业己经迅速的从单纯的提供市话和长话服务演变为提供综合电 信服务，如语音、传真、寻呼、移动电话、图像、电子邮件、计算机，以及其他数据通 信服务。随着越来越多的国家对电信业的开放和新兴计算与通信技术的发展，电信市场 正在迅速扩张并越发竞争激烈。因此，利用数据挖掘技术来帮助理解商业行为、确定电 信模式、捕捉盗用行为、更好的利用资源和提高服务质量是很有必要的。 从技术层面上看数据挖掘的一个非常重要的方面是建立分类与预测模型，分类和预 测是两种数据分析形式，它们可用于抽取能够描述重要数据集和预测未来数据趋势的模 型。分类方法用于预测数据对象的离散类别，预测方法用于预测数据对象的连续取值。 研究人员已经提出了许多具体的分类预测方法。数据分类过程主要包含两个步骤，第一 步是建立一个描述己知数据集类别的模型，该模型通过对数据库中各数据对象内容的分 析获得。它是在已知训练样本类别的情况下，通过学习建立相应的模型。通常分类学习 所获得的模型可以表示为分类规则形式、决策树形式和数学公式形式。第二步是利用所 获得的模型进行分类操作。经过评估，如果模型的分类准确率是可以接受的，那么就可 以使用这一模型对未来的数据对象进行分类。与分类学习方法相比，预测方法可以认为 是对未知类别数据对象的类别取值，利用学习所获得的模型进行预测。目前分类与预测 方法己被广泛应用于各行各业，如信用评估、医疗诊断、性能预测和市场营销等应用领 域。 聚类分析作为数据挖掘分类与预测技术中的一个分支，是数据挖掘一种重要的挖掘 任务和挖掘方法，它研究数据间逻辑上或物理上的相互关系，通过一定的规则将数据集 划分为在性质上相似的数据点构成的若干个类。它从数据库中寻找数据问的相似性，并 依此对数据进行分类，使得不同类中的数据尽可能相异，而同一类中的数据尽可能相似， 即“物以类聚”，从而优化大规模数据库的查询和发现数据中隐含的有用信息或知识，数 硕士论文基于模糊矩阵的聚类融合 据聚类在很多领域中有着广泛的应用，如：模式识别、图象处理、数据压缩、空间数据 分析、市场研究、w w w 上( w w w 上的文本分类：对w e b 的日志数据聚类以后发现 相似的访问模式) 等等。迄今为止人们提出了很多聚类算法，例如分割的方法、层次的 方法、基于密度的方法、基于网格的方法和基于模型的方法。其中有代表性的算法包括 k m e a n s 、d b s c a n 、c u r e 、c l i q u e t m 】不同的算法有着不同的应用背景，有的适 用于大数据集，可以发现任意形状的聚类；有的算法思想简单，适用于小数据集。所有 这些算法都试图通过不同的途径实现对大规模数据库的有效聚类。但总的来说，都没有 取得理想的效果，问题在如下几个方面： 第一是算法的效率问题，由于现在数据库的数量和单个数据库的规模都大大增加 了，如何对以惊人速度增长的数据量进行聚类，如何提高算法的执行效率是许多算法需 要解决的问题。第二是初值的选择，初值的选择对聚类算法的最终结果有很大的影响。 第三是样本的输入顺序，许多算法对数据的输入顺序非常敏感。第四是最优解问题，聚 类问题本质是一个优化问题，这就是通过一种迭代运算使得系统的目标函数达到一个极 小值，但是这个目标函数在状态空间中有很多极小值，其中只有一个是全局最小值，而 其它都是局部最小值。优化的目标是达到全局最优而非局部最优，为了求得最优解往往 需要耗费大量的时间。在数据挖掘领域中，大数据集使得最优解问题变得不太可能，所 以一般情况下，采用初值选择来求得一个近似最优解。 从以上提出的问题可以看出，对大规模、高维数据库的高效聚类分析仍然是一个有 待研究的开放问题。 1 2 内容以及组织结构 在之前的所有的聚类算法侧重于对于数据具体的一个模型进行优化，提高其算法性 能以及运行效率，最近一种新的思路是结合已经研究出的聚类算法的优点，通过多次运 行聚类算法再进行融合的途径来实现具有高效，健壮性的聚类过程。这种方法被称为聚 类融合( c l u s t e r i n ge n s e m b l e ) ，本文主要研究了聚类融合，系统得介绍了聚类融合的基 本方法与技术，在此基础之上提出了一种新的聚类融合方法。 一、引言部分。主要概述了论文的研究目的、课题的研究背景、论文的主要研究工 作和文章的结构安排。 二、聚类分析技术部分。介绍聚类分析的定义、要求、数据类型及应用方面，并详 细介绍和分析了聚类算法的分类，以及不同算法的思想以及特点，最后讨论了聚类的评 价准则。 三、聚类融合技术部分。给出了聚类融合的定义，基本思想方法，以及最主要的技 术，尤其讨论几个常见的聚类融合算法和它们之间的比较。 l 绪论硕j ：论文 四、基于模糊矩阵的聚类融合算法。提出了一个新的聚类融合算法，改进了共识函 数，创造性地改变了原先一直以标签数据结构作为共识函数输入。提高了算法的稳定性 和平均性能。 五、结论部分。总结研究成果和展望下一步需要完成的工作。 4 硕士论文 基于模糊矩阵的聚类融合 2 聚类算法综述 聚类分析在许多学科上都有着非常多的应用，用于发现在数据库中未知的对象的 类。这种类别划分的依据是“物以类聚”，也就是考察个体或数据对象间的相似性，将 满足相似性条件的个体或数据对象划分在一组里，不满足相似性条件的个体或数据对象 划分在不同的组里。通过聚类过程形成的每一个组称为一个簇( c l u s t e r ) 。 聚类分析提供了由个别数据对象到数据对象所指派到的簇的抽象。此外，一些聚类 技术使用聚类原型来刻画簇的特征。这些原型提供了数据分析与数据处理的基础。这些 方面包括如数据汇总，数据压缩，以及有效的发现最近邻。 聚类分析的结果不仅可以揭示数据间的内在联系与区别，同时也为进一步的数据分 析与知识发现提供了重要的依据，如数据间的关联规则，分类模式以及数据的变化趋势 等。作为统计学的重要研究内容之一，聚类分析具有坚实的理论基础并形成了系统的方 法学体系。然而，基于统计学的聚类分析方法大多局限于理论上的分析并依赖于对数据 分布特征的概率假设，较少考虑具体应用中的实际数据特征与差异。由于数据挖掘技术 的迅速崛起，聚类分析得以在数据库技术领域获得长足的发展。在下面的章节将提供这 些聚类分析的最主要的部分。 2 1 聚类算法原理 2 1 1 数据表示及类型 数据表示( d a t ar e p r e s e n t a t i o n ) 是实现聚类技术的一个非常重要的先决条件和步骤， 不同的数据表示方法可能对算法的效能产生影响，不同的数据也适用于不同的聚类算 法。就数据的表示方法而言可以分为模式矩阵( p a t t e mm a t r i x ) 表示方法和邻近度矩阵 ( p r o x i m i t ym a t r i x ) 表示方法。就数据类型而言，大体上可以分为离散( d i s c r e t e ) ，二 值( b i n a r y ) ，连续( c o n t i n u o u s ) 。就数据尺度而言大体可以分为定量( q u a n t i t a t i v e ) 与 定性( q u a l i t a t i v e ) 两种表示方法。定量的属性包括比值型( r a t i o ) 和区间型( i n t e r v a l ) 。定 性的属性又可称作标称( n o m i n a l ) 或范畴( c a t e g o r i c a l ) 属性和序数类型( o r d i n a l ) 。这 个数据表示的结构图如下所示： 2 聚类算法综述 硕士论文 n o m t n o l o r d i n a li n t e r v a lr o t t o o r c l t n a l i n t e r v a l r a t t o i t y 图2 1 1 1 数据类型示意图 ( 一) 模式矩阵( p a t t e r nm a t r i x ，或称为对象与变量结构) ：它是一个多维变量的一 个矩阵表示，其中每一行表示一个对象，每一个对象是一个维数为d 的向量。 定义：x = “，x 2 ，_ ) ，其中薯r d ，誓= ( 誓l ，t 2 ，) ，f = 1 ，2 ，n 表示为x = i五d x 1吒d ( 二) 相似度矩阵( s i m i l a r i t y m a t r i x ) 或者相异度矩阵( d i s s i m i l a r i t y m a t r i x ) 这个矩阵是一个n 维方阵，并且是一个对称矩阵，矩阵中的每一个元素是数据点的 近似度或者相异度衡量表示如下： 6 d = o d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) d ( n ，1 ) d ( n ，2 ) o 0 ； 硕士论文基于模糊矩阵的聚类融合 其性质如下： 1 相似度矩阵：d ( i ，f ) = 0 ，扛1 ，2 ，n 相异度矩阵：d ( i ，i ) m a x d ( i ，k ) ，f ，k = 1 ，2 ，n 2 d ( i ，后) = d ( k ，f ) ，f ，k = 1 ，2 ，n 3 d ( i ，七) 0 ，f ，k = l ，2 ，n ( 三) 区间标度变量 区间标度变量是一个粗略线性标度的连续变量。其相似度函数可以用欧式距离和曼 哈顿距离度量，在下面给出具体的介绍。 ( 四) 二值变量 每一个模式的特征取值只有两个可能：0 或l 。例如一个病人生病情况，0 表示生病， 1 表示不生病。那么任意两个模式，模式i 和模式k 之间可以组成如下列联表： 1 耘 0 & lo 园all a l o 图2 1 1 2 列联表示意图 其中表示模式i , k 中都取0 的特征个数，a 。表示模式i 取0 特征个数，模式k 取 1 的特征个数，a 。表示模式i 取1 模式k 取0 的特征个数，口1 l 表示模式i , k 都取1 的特 征个数。这样可以定义任意两个模式的相似度函数： 1 简单相似度函数：d ( i ，尼) ：兰吐兰丑一：鱼d 粤 ( 2 1 1 1 ) 口o o + q l + 口o l + q o d 2 j a c c a r d 相似度函数：d ( i ，k ) = a l l + a o i + 口l od a o o ( 五) 标称变量 标称变量是二元变量的推广，它可以具有多于两个的取值。假设一个标称变量取值 的个数为n ，所有取值可以用一组整数或者字母表示以示区别，令两个模式i , k 的取值 相同的特征个数为n ( n n ) ，其相异度计算如下： ， d ( i ，k ) = ( 2 1 1 3 ) 7 2 聚类算法综述 硕十论文 其中d 表示模式特征维数 ( 六) 序数变量 序数型变量可以是离散的，也可以是连续的。在连续型的序数变量中，值的相对顺 序是必要的，而其实际的大小则不重要。例如，在某个比赛中的相对排名( 例如金牌、 银牌和铜牌) 经常比事实的度量值更为必需。在相异度的计算中，需要把每个变量的值 域映射到某个区间上，以便每个变量都有相同的权重。然后可以采用距离的计算方法进 行相异度的计算。设k 是用于描述n 个对象的一组序数型变量之一，其相异度计算如下： = j n 丽i k - - 1 ( 2 1 1 4 ) ( 七) 比例变量 主要的相似性度量一般有如下几个： 1 m i n k o w s k i 距离函数： 椰，护f ，壹i 嘞一h 7 ，纠 ( 2 m ) 3 曼哈顿距离函数： 4 m a h a l a n o b i s 距离函数： d ( f ，尼) = ( 一魂) 7 1 _ 1 ( 誓一) 5 余弦函数： 州朋= 赢 v7 一 一 i a k ( 2 1 1 6 ) ( 2 1 1 7 ) ( 2 1 1 8 ) ( 2 1 1 9 ) 2 2 2 聚类的步骤 大多数聚类方法都具有特征选择或特征抽取、聚类算法设计或选择、聚类确认三个 刀故 一 ，l 、，毪 一 葺k i | 、， ：!i 一 而 d闰 ，l = 驴， ： o 数 d 函离l 上巳足 式 欧 ，、| b 一 d 卢 = 、 尼 o d 硕士论文基于模糊矩阵的聚类融合 基本步骤。其中聚类算法设计包括数据表示，相似度表示，以及分组。基本流程如下图 所示： 数撂一 图2 2 2 1 聚炎啼 特征选择是指在所有的数据属性的集合中选择一个子集来代表数据。特征抽取则是 对原始数据集作一些变换来生成新的有用的特征，由现有的数据属性产生新的属性的过 程。特征选择或特征抽取这是两个处理方式不同而目的相同的从原始数据集中得到特征 的方法。这两种方式对高效的聚类应用都是至关重要的，一方面降低算法的计算复杂度， 另一方面它们都具有降维的作用，对处理高维数据带来的“维灾”问题具有不可替代的 作用。选择或生成好的特征能大大的减少聚类算法的工作量并简化聚类算法的设计。 聚类算法设计或选择选择比较”好”的数据表示，以及一个相应的相似性度量函数。 相似性度量直接地影响了聚类的形式和内容，几乎所有的聚类算法都明显或者含蓄地与 某一相似性度量有所关联，一些算法甚至直接工作于相异度矩阵之上。一旦相似性度量 被选择使用，构建聚类准则函数就成了拥有很好的数学定义的“簇 划分的优化问题。 聚类确认也称为聚类有效性验证( c l u s t e rv a l i d a t i o n ) 。给定一个数据集，聚类算法 总是能够生成一个分类而不管它是否存在非随机结构。对给定数据集采用不同的算法总 是会生成不一样的聚类结果，甚至采用同一种聚类算法也可能会因为其输入参数的选择 及模式实例的输入顺序的不一样而导致完全不同的结果。因此，给用户提供一个关于聚 类算法结果可信度的有效性评估标准和准则是十分重要的。这些内容将在2 8 节给予具 体的讨论。 2 2 3 聚类算法分类及特性 ( 一) 聚类算法分类 聚类算法是一个内容庞杂的算法族，在近5 0 年的研究中研究者们提出了许多的算 法，通用聚类算法可以分为参数的方法和非参数的方法。参数的方法试图去最小化一个 代价函数或优化标准。非参数的方法即是基于数据相识度或者距离的方法。特殊聚类算 法包括一些特殊数据情况和特殊要求下的聚类算法。虽然这些算法各不相同，但是大致 按照如下图归类： 9 2 聚类算法综述 硕十论文 图2 2 3 1 聚类算法层次图 ( 二) 聚类算法特性 ( 1 ) 可伸缩性： 许多聚类算法在只有几百个数据对象的小数据集合上工作得很好；但是，一个大规 模数据库可能包含成千上万甚至是几百万的数据对象，在这样的大数据集合样本上进行 聚类可能会导致有偏差的结果。我们需要具有高度可伸缩性的聚类算法。 ( 2 ) 分布适应性： 许多聚类算法假设某一数据具有特定的分布。更具体的说，他们常常假定可以用混 合分布对数据建模，例如，k m e a n 算法假定数据是超球分布，一个簇可能是任意分布的。 提出能发现任意分布的算法是很重要的。 ( 3 ) 参数依赖性： 许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生的簇的数目。 聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据 集来说更是如此。要求用户输入参数不仅加重了用户的负担，也使得聚类的质量难以控 制。 ( 4 ) 抗噪声性： 绝大多数现实世界中的数据库都包含了孤立点，空缺，未知数据或者错误的数据。 一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。 ( 5 ) 次序依赖性： 一些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合，当以不同的 顺序提交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入不敏感的算 1 0 倾1 论文 基f 模糊矩阵的聚娄触台 法具有很重要的意义。 ( 6 ) 数据高维性： 一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的 数据可能只涉及两到三维。人类虽多在三维的情况下能够很好的判断聚类的质量。在 高维空间中聚类数据对象是非常有挑战性的，特别是考虑到这样的数据可能非常稀疏， 而且高度偏斜。 ( 7 ) 能完成约束条件下的聚类操作：现实世界的应用可能需要在各种约束条件下 进行聚类。假设你的工作在一个城市为给定数目的自动提款机选择安放位置。为了作出 决定，你可以对住宅区进行聚类，同时考虑如城市的河流和公路网，每个地区的客户要 求等情况。要找既满足特定的约束，又具有良好聚类特性的数据分组是一项具有挑战性 的任务。 在本章余下的篇幅将关注聚类分析的重要算法，并且研究以及开发的处理它们的概 念以及技术。 2 2 基于划分的聚类算法 划分聚类( p a r t i t i o n a lc l u s t e r i n g ) 是。种参数的方法，简单地将数据对象集合划分成 不重叠的子集( c l u s t e r ) ，使得每一个数据对蒙恰好在个子集中。在下图中，所有的点被 分为三炎。 图22 个别的看，每个簇集都是一个划分的聚类。算法般采用贪心启发式算法，最小 糍罐 2 聚类算法综述硕1 ：论文 化某个优化函数，通过迭代最终获取符合要求的划分。最常见的优化函数是平方误差和 ( s s e ) 。s s e 也称作为散布，其定义如下： 跚= d ( 碱) = y y , l x ：k k 一气0 ( 2 2 1 ) m k = lj ck = li = 1 其中距离函数d 一般代表欧几罩得距离，g 表示第k 个类的中心。聚类问题转化为优化 最小化s s e 。 基于划分的算法分为两种类别，第一种是“硬”划分，也就是说每一个数据对象要 么属于某一类，要么就不属于。另一种是”软”划分，每一个数据对象，数据每一个类别 是以一个0 到1 之间的数来表示其隶属度。而这些方法都是通过最小化目标函数实现的。 2 2 1 硬划分算法 最著名的硬划分算法的代表是k m e a n s 算法，它是一种基于原型的聚类算法，使用 的准则函数便是s s e ，通过迭代使得s s e 达到最小，是一种局部最优的结果，而并非全 局最优，算法流程如下： 1 ) 初始化k 个聚类中心点 c l ，c 2 ，c 1 ) ，以及初始化s s e 。 2 ) 重复如下步骤： 3 ) 把每一个数据对象指派到最近的一个聚类中心，完成一次聚类过程。 4 ) 求出每一个类的”质心”即为新的聚类中心，并且计算出新的s s e 。 5 ) 如果s s e 没有变化就转到( 6 ) 否则转到( 2 ) 6 ) 结束 算法的时间复杂度为o ( s x k m x n ) ，i ，m ，n 分别为迭代次数，对象个数，特 征维数。该算法优点在于简单，迭代速度快。问题在于如下方面： ( 1 ) 如何初始化聚类中心 对于不好的初始化参数，算法往往收敛到局部最优离全局最优差别比较大，解 决的方法一般是多运行几次。 ( 2 ) 如何选择聚类类别个数参数k 一般人为给定类别个数。 ( 3 ) 如何处理空簇的情况 如果所有点在指派步骤都没有分配到某一个簇，那么就会得到空簇。如果发生这 种情况，需要某种策略来选择一个替补质心，不然平方误差将会偏大。 ( 4 ) 如何避免噪声点的影响 使用平方误差标准时，噪声点( 离群点) 可能过度的影响所发现的簇，当存在噪 声点时，质心可能不如没有噪声点时那样具有代表性。 1 2 硕士论文基于模糊矩阵的聚类融合 有许多旨在提高算法性能的新方法被提出来，例如g l o b a lk m e a n s 算法，利用k d t r e e 数据结构的快速k m e a n s 算法等等，这些方法从不同程度上解决了上述的问题。 2 2 2 软划分算法 一般认为这种划分方法是模糊化的划分算法。如果数据对象分布在明显的簇中，那 么把对象分类为不相交的簇是可以接受的。传统的划分聚类算法中，每个数据通过计算 最终都将属于一个且唯一一个聚类。然而客观世界中大量存在着界限并不分明的聚类问 题。模糊聚类扩展了传统聚类的思想。考虑一个靠近两个簇边界的对象，它离其中的一 个稍微近一些，如果对每一个对象和每一个簇赋予一个权值，指明该对象属于该簇的程 度( 被称为隶属度) ，通过使用隶属，使得可以把每一个数据分配给所有的聚类，不同 于传统的聚类方法，模糊聚类的结果使得每个数据最终可能属于多个聚类，每个数据对 每个聚类分配一个隶属度。聚类的结果可以表示为一个模糊矩阵。最常见的模糊聚类是 f c m 算法。模糊聚类技术基于模糊集合论，并且并不等同于传统的概率方法，其中隶 属权值具有自然的解释。 ( 1 ) 模糊集合论 1 9 6 5 年，l o t f iz a d e h 引进模糊集合论( f u z z ys e tt h e o r y ) 和模糊逻辑( f u z z yl o g i c ) 作为一种处理不精确和不确定的方法。在现实世界中，有许多概念并没有明确的“外延”， 比如说“天气好”、“水温很低”、“个子很高”等都是模糊的概念。这样就使得经典集合 论对于这样的概念显得力不从心了，因为模糊概念很难简单地用“属于或“不属于” 来表示，而只能通过属于的程度来描述。换句话说，就是域中的元素符合某一概念的程 度不能仅仅用0 或1 来表示，而需要借助于介于0 到1 之间的实数来表示。模糊集合论 允许对象以0 或者1 之间的某一个隶属度属于某一个集合，而模糊逻辑允许一个以0 或 者1 之间的数表示确定度为真。模糊概念已经用于许多不同的领域包括控制系统，模式 识别和数据分析。 ( 2 ) 模糊聚类 利用模糊集合论的概念人们提出了多种聚类方法，比较典型的有：基于相似性关系和 模糊关系的方法( 包括聚合法和分裂法) ，基于模糊等价关系的传递闭包方法、基于模糊