（计算机科学与技术专业论文）基于连通性的聚类有效性问题研究.pdf

：- l 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 撇 签字只期：乙和年6 月2 弓同 导师签名 签字同期：2 0 l o 年6 月矽同 中图分类i ，：t p 3 0 1 6 u d c ：6 2 0 j 匕 京交通大 硕士学位论文 学校代码：1 0 0 0 4 密级：公开 、， f 卜 j 基于连通性的聚类有效性问题研究 r e s e a r c ho nc o n n e c t i v i t y - b a s e dc l u s t e rv a l i d i t y 作者姓名：张尚超 导师姓名：于剑 学位类别：工学 学科专业：计算机应用技术 北京交通大学 2 0 10 年6 月 学号：0 8 1 2 0 5 7 9 职称：教授 学位级别：硕士 研究方向：机器学习 致谢 本论文的工作是在我尊敬的导师于剑教授悉心指导下完成的，从论文的选题， 一直到论文的最终定稿，于老师一直给予我细心的指导于剑教授严谨的治学念 度和科学的工作方法给了我极大的帮助和影响在此衷心感谢两年来于剑老师对 我的关心和指导 贾彩燕老师、景丽萍老师、周雪忠老师、尹传环老师在学习和生活上都给予 了我很大的关心和帮助，在此向老师们表示衷心的谢意 在实验室工作及撰写论文期间，赵静、何威、蔡敏、姜雅文、赵翔等同学对 我的论文研究工作给予了热情帮助，在此向他们表达我的感激之情 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业 最后，衷心地感谢在百忙之中审阅论文的各位老师和专家，恳请各位老师多 批评指正，并提出宝贵的意见 摘要 聚类分析是机器学习领域中一个非常重要的内容。聚类分析的任务是在数据 中发现有意义的数据分类。聚类分析已经成功的应用在很多领域中，如工程领域、 商业领域和社会科学领域等。但聚类分析中仍有很多关键问题需要研究，本文重 点对聚类有效性问题进行了研究。 本文对基于连通性的聚类有效性问题进行了深入的研究，在此基础上指出以 往的聚类有效性指标中存在的两个问题：第一，不能很好的评价类形状任意的聚 类结果；第二，现有的基于连通性的聚类有效性指标忽略了聚类结果中类内紧致 性差异大对有效性指标的影响，从而可能导致错误的评价结果。针对以上两个问 题，本文提出了相应的解决方法。首先利用图连通距离对形状和大小的不敏感性 对任意形状聚类的类内紧致性进行度量，解决了对任意形状聚类的评价问题。其 次，提出了定义聚类有效性指标的一种思路：对整个聚类结果的评价应该首先建 立聚类结果中单个类的有效性，之后再对整个聚类结果进行评价。按照上述思路 定义的聚类有效性指标可以克服聚类结果类内紧致性差异大对聚类结果评价造成 的不利影响。将以上两点相结合，本文定义出一种基于连通性的聚类有效性指标。 本文使用人工数据集和真实数据集进行了实验。实验的结果表明该聚类有效 性指标是有效的。 关键词：聚类分析；聚类有效性指标；连通距离 分类号：t p 3 0 1 6 a bs t r a c t i nt h ed o m a i no fm a c h i n el e a r n i n g ，o n eo ft h em o s ti m p o r t a n ti s s u e si sc l u s t e r a n a l y s i s t h ea i mo fc l u s t e ra n a l y s i si sp a r t i t i o n i n gag i v e nd a t as e ti n t om e a n i n g f u l g r o u p ss u c ht h a tt h ed a t ap o i n t si nt h es a m eg r o u pa r em o r es i m i l a rt oe a c ho t h e rt h a n p o i n t si nd i f f e r e n tg r o u p s c l u s t e ra n a l y s i sh a sb e e nw i d e l yu s e di nal o to ff i e l d s ，s u c h a se n g i n e e r i n g ，b u s i n e s sa n ds o c i a ls c i e n c e t h e r ea r es om a n y i m p o r t a n tb u tu n s o l v e d p r o b l e m sr e l a t et oc l u s t e ra n a l y s i s i n s t e a do fp a y i n ga t t e n t i o nt oa l lo ft h e m ，w ef o c u s o no n l yo n e i s u s s e ，t h ec l u s t e rv a l i d i t yp r o b l e m i nt h i sp a p e r , w ef o c u so nc l u s t e rv a l i d i t yp r o b l e mb a s e do nc o n n e c t i v i t y m a n y v a l i d i t yi n d i c e sf a c e dt w op r o b l e m s f i r s t ，m o s to ft h e s ei n d i c e sc a n td e a lw e l lw i t ht h e c l u s t e r so fa r b i t r a r y s h a p e s s e c o n d ，t h e yn e g l e c tt h e v a r i a n c eo fi n t r a c l u s t e r c o m p a c t n e s s t os o l v et h e s et w op r o b l e m s ，w ef i r s tt a k ea d v a n t a g e so fc o n n e c td i s t a n c e t os o l v et h ef i r s tp r o b l e m a f t e rt h a t ，w ep r o p o s ean e wi d e af o rd e f i n i n gc l u s t e rv a l i d i t y i n d i c e s w ea s s u m et h a tt h ev a l i d i t yi n d i c e sf o rt h ew h o l ec l u s t e r i n gr e s u l t ss h o u l db e d e f i n e du p o nt h ev a l i d i t yi n d i c e so fs i n g l ec l u s t e r s t h i si d e ac a nh e l pt h ei n d i c e sd e a l w i t ht h ec l u s t e r i n gr e s u l t sw h i c hc o n t a i nc l u s t e r so fd i f f e r e n ti n t r a - c l u s t e rc o m p a c t n e s s a f t e rt h a t ，w ep r o p o s ean e wc o n n e c t i v i t y - b a s e dc l u s t e rv a l i d i t yi n d e x t h ee x p e r i m e n tr e s u l t so ns y n t h e t i cd a t as e t sa n dr e a ld a t as e t ss h o wt h e e f f e c t i v e n e s so fo u rv a l i d i t yi n d e x k e y w o r d s ：c l u s t e ra n a l y s i s ；c l u s t e rv a l i d i t yi n d e x ；c o n n e c td i s t a n c e c l a s s n o ：t p 3 0 1 6 目录 摘要i i i a b s t r a c t i v 1引言1 1 1 课题背景1 1 2研究现状1 1 3本文完成的工作一2 1 4论文组织安排2 2聚类有效性相关理论概述4 2 1聚类分析的基本概念一4 2 1 1 聚类的定义4 2 1 2 聚类分析的基本步骤4 2 1 3 聚类算法5 2 2聚类结果的评价7 2 2 1 聚类有效性问题7 2 2 2 设计聚类有效性指标的基本原则8 2 2 3 外部指标1 0 2 2 4 内部指标1 2 2 2 5 相对指标1 2 3基于连通性的聚类有效性指标1 8 3 1一种聚类有效性指标的假设1 8 3 2基于连通性的聚类有效性指标2 1 3 - 3新的聚类有效性指标对基本公理的满足性2 4 4 实验结果分析2 6 4 1 实验2 6 4 2结果分析4 4 4 2 1 实验的结果分析4 4 4 2 2 计算复杂度分析4 5 4 2 3 适用性分析4 5 5 结论及今后的工作展望4 7 5 1本文总结4 7 5 2今后的工作4 7 参考文献4 8 作者简历5 0 独创性声明51 学位论文数据集5 2 1 1 课题背景 l 引言 从上世纪9 0 年代开始，信息产业得到了飞速发展，计算机互联网、数据库等 技术的发展和普及使得人类获得和存储的数据量急剧增大。与此同时，如何从海 量数据中提取有价值的信息成为了当务之急。数据挖掘技术在这种背景下应运而 生。作为数据挖掘技术的理论依据，机器学习也因此获得飞速发展。数据挖掘与 机器学习的目的是从海量数据( 包括文本数据、图像数据等) 中提取隐含的、事 先未知的、又潜在有用的信息。机器学习可以分为两大类：无监督的学习和有监 督的学习。无监督的学习一般是指聚类分析，而有监督的学习指的是分类和回归 问题。 聚类分析是机器学习中一类非常重要的方法，聚类问题的本质是将给定的数 据分割成几个组，每个组称为一个聚类，使得每个类内的点比类l 日j 的点更相似【l j 。 因此聚类分析的主要过程就是根据样本点的内在关系将数据划分成有意义的聚 类。聚类分析已应用于多个领域，如图像分析、模式识别领域中的图像分割和物 体识别等。 聚类有效性是聚类分析中的一个重要环节，目的是评价数据经过聚类后的结 果是否适合该数据。研究者们已经证明，找到一个适合于所有数据的聚类算法是 不可能的【2 】。所以一般而言，聚类算法依赖于一个特定的对数据结构的假设，该假 设对数据是否j 下确是事先未知的。如果假设不适用于数据，聚类结果就不能t f 确 的揭示数据所具有的结构。即使选择了正确的假设，也可能因为选择不正确的参 数而得到不好的聚类结果。这就需要对聚类的结果进行评价，这个问题就称为聚 类的有效性问题。 1 2 研究现状 聚类结果评价是聚类分析过程中的一个重点和难点问题，多年来，研究者们 针对聚类有效性的理论基础进行了深入的研究，并已经取得了一定进展。一些研 究者对聚类有效性指标应满足的基本要求进行了研究，并提出了一套聚类有效性 指标必须满足的基本公理【3 1 。这些公理是聚类有效性指标应满足的必要条件，是设 计聚类有效性指标最基本的要求。还有一些研究者给出了设计聚类有效性指标的 更强要求 4 】，但是这些要求并没有形成一个完整的公理体系，不能用米作为聚类有 效性指标的理论基础。此外，研究者们提出了众多的聚类有效性指标来评价聚类 的结果。聚类算法一般需要对类做出一定的假设，比如假设类内数据点之问的连 通性高于类间数据点间的连通性，或者假设类内数据点存在类原型且类内数据点 和类原型更相似等。基于连通性假设的聚类算法的优点是可以得到任意形状的聚 类，但一般对相切类等问题处理比较困难。而基于类原型假设的聚类算法则可以 较好的处理存在相切类的情况，但是很难处理任意形状的聚类。针对这些对聚类 算法的假设，大多数聚类有效性指标也相应的隐含了某种对数据的假设，所以这 些有效性指标大多只适用于对基于某种假设的聚类算法产生的聚类结果进行评 价。然而只针对基于某种假设的聚类算法的聚类结果进行评价也是非常困难的， 例如很多聚类有效性指标不能很好的对非球形的聚类进行评价，或者只能对等密 度、等大小的聚类进行评价，这些缺点或限制显然会使这些聚类有效性指标在一 些聚类结果上得不到j 下确的评价结果。因此基于某种聚类假设，对聚类结果的有 效性指标进行研究，从而找到更适合该聚类假设的聚类有效性指标就成为了研究 重点。本文对基于连通性的有效性指标进行了研究，针对聚类结果的类内紧致性 之间差异大会造成有效性指标失效这个问题提出了解决思路，并结合图连通距离 设计了新的基于连通性的聚类有效性指标，该指标可以很好的对类形状任意的聚 类结果进行评价。 1 3 本文完成的工作 在上述背景之下，本文主要针对聚类分析中的聚类有效性问题进行了研究， 首先对聚类分析和聚类有效性问题进行了系统的介绍，然后在此基础上提出了新 的基于连通性的聚类有效性指标。具体工作如下： 首先，介绍聚类分析及聚类有效性的基本概念及相关基础理论。 第二，介绍已有的聚类有效性指标，并进行简要分析。 第三，提出一种新的聚类结果的评价思路，并结合连通距离提出新的基于 连通性的聚类有效性指标。 最后，将新的有效性指标与已有的聚类有效性指标进行对比实验，验证其 有效性。 1 4 论文组织安排 本文的主要框架和结构如下： 2 第1 章给出了课题的出发点以及研究的问题，并介绍本文所完成的工作。 第2 章足全文的理论基础，介绍了聚类分析和聚类有效性的相关知识和研究 现状。 第3 章是本文的核心部分，介绍了本文提出的一种新的聚类有效性的度量假 设，并利用连通距离提出新的聚类有效性指标。 第4 章是实验部分，通过大量的比对试验以及对实验结果的分析，表明了本 文提出的聚类有效性指标的良好性能。 第5 章总结全文，对本文的研究做了分析和总结，并给出了本课题将来的研 究内容和方向。 2 聚类有效性相关理论概述 聚类分析是将数据对象的集合划分成由相似对象组成的多个子集的数据分析 过程。从机器学习的角度，聚类又称为无监督的学习，与有监督的分类学习不同， 聚类要求所有数据的类标是末知的。聚类有效性则是聚类分析过程中的重要一步， 用来评价聚类算法得到的聚类结果。 2 1 聚类分析的基本概念 2 1 1 聚类的定义 聚类分析是将数据划分成不同类的过程，同一个类中的数据对象有较大的相 似性，不属于同类的数据对象间有较大的相异性。对聚类的定义会导致对单一聚 类的定义，多年来提出了许多定义5 ，6 1 ，然而大多数的定义都不是精确的，运用了 “相似”、“相像”等词语。正如e v e r 所指出的叽大多数聚类的定义都是模糊 的，并有循环定义的倾向。这反映了对聚类的定义是困难的，甚至是不可能的。 本文参照文献【8 1 中的定义，给出聚类数学形式的定义，尽管这个定义不能普遍 适用，但是可以帮助理解聚类的概念。设x 是数据集，片缸l ，x 2 ，柳) ，r 是定义 在x 上的聚类，将x 分割成k 个集合( 聚类) c ，使其满足以下三个条件： ( 1 ) g ，f = l ，k k ( 2 ) u c i = x ( 3 ) c f n 勺= 妒，f 歹，i ，y = l ，k 另外，在类白中包含的向量彼此“更相似”，与其它类中的向量“不相似”。术语 “相似 的度量依赖于聚类的数据，对不同的数据应该定义不同的相似性度量。 相似性的度量已经成为聚类分析领域中的一个难点，很多文献【9 1 0 1 对这方面的研究 作出了贡献。 2 1 2 聚类分析的基本步骤 在聚类过程中，类的定义、结构都是未知的，而且没有已经标注好的数据对 象来表示待聚类数据的哪些特征是对聚类结果有效的。j 下因为如此，聚类才被称 4 为无监督的学习。 聚类分析依据不同的聚类假设将数据集划分成不同的聚类结果，假设数据是 由特征组成的一个向量，为完成一个聚类任务，一般需要遵循以下步骤，如图2 1 表示： ( 1 ) 特征选择( f e a t u r es e l e c t i o n ) 。选择合适的特征，尽可能包含任务相关的 信息，减小数据的冗余，在无监督的聚类中数据预处理是必要的步骤。 ( 2 ) 聚类算法( c l u s t e r i n ga l g o r i t h m ) 。选择合适的聚类算法对数据进行聚类， 揭示数据集的内在结构。 ( 3 ) 结果评价( e v a l u a t i o no f r e s u l t s ) 。通过运行聚类算法得到数据集的聚类结 果后，必须对该结果的正确性进行验证，这就是聚类结果的评价问题。 ( 4 ) 结果的理解( i n t e r p r e t a t i o no f r e s u l t s ) 。由于聚类分析不可避免的存在一定 的主观性，所以哪一种聚类结果是正确的还需要该领域的专家进行理解判定，最 后才能得出f 确的结论。 图2 1 聚类分析的步骤 f i g 2 1s t e p so fc l u s t e ra n a l y s i s 在很多情况下还应考虑“聚类倾向性”的问题，这一步主要是测试数据是否 真的拥有聚类结构。如果数据完全是随机分布的，不存在任何聚类结构，那么进 行聚类就没有意义了。 2 1 3 聚类算法 e 回回回 k l e i n b e r g 提出了聚类算法应该满足的三条基本公理【2 j ： ( 1 ) 尺度不变性( s c a l ei n v a r i a n c e ) ：距离度鼍的比例放缩彳i 会影响聚类结果。 ( 2 ) 丰富性( r i c h n e s s ) ：通过选取不同的距离定义，聚类算法的结果可以是 数据集的任意划分。 ( 3 ) 一致性( c o n s i s t e n c y ) ：增大类| 、日j 点之间的距离，减小类内点之川的距离， 不会改变聚类算法的结果。 k l e i n b e r g 提出了这三个看似很自然的假设，然而k l e i n b e r g 紧接着证明了任何 一个聚类算法不能同时满足这三条件。这就说明，任何一个聚类算法都是有缺陷 的，因此不存在聚类算法的统一框架，只能根据某种对数据的假设设计相应的聚 类算法。 一个聚类算法是否适用于对某个数据集进行聚类依赖于聚类算法所采用的近 邻性度量( p r o x i m i t ym e a s u r e ) 和聚类算法所依赖的聚类准则。 近邻性度量定量的表示了两个数据对象之问“相似”或“不相似”，而聚类 结果要求类内数据对象之问的相似性大于类问数据对象l 、日j 的相似性。近邻性度量 一般分为相似性度量( s i m i l a r i t ym e a s u r e ) 和不相似性度量( d i s s i m i l a r i t y m e a s u r e ) 。 近邻性度量是聚类分析过程中的重点和难点，其定义会直接影响聚类的结果。 聚类准则( c l u s t e r i n gc r i t e r i o n ) 可以用一个代价函数或是一些规则来表示， 以蕴涵在数据集中数据的结构为基础。我们应该考虑数据集具有何种形式的聚类 结构，因此需要对数据集选择一个合适的聚类准则。 聚类算法依据分类标准的不同，可以有不同的分类方法。按照聚类算法依据 的聚类准则可以分为以下几类j ： ( 1 ) 层次聚类( h i e r a r c h i c a lc l u s t e r i n ga l g o r i t h m s ) 层次聚类分为合并算法( a g g l o m e r a t i v ea l g o r i t h m s ) 和分裂算法( d i v i s i v e a l g o r i t h m s ) 。合并算法在每一步合并上一步产生的聚类，最后使聚类数为1 。与之 相反，分裂算法首先将数据集中的所有数据看成一个聚类，每一步的结果通过分 裂上一步的某几个聚类得到，最后将所有数据点当做一个单独的聚类。层次聚类 算法的结果可以表示为一个树状图( d e n d r o g r a m ) ，用来表示聚类之间的关系和聚 类结果的结构，如果在合适的高度切断树状图，就可以得到一个聚类结果。代表 算法有s i n g l e 1 i n k a g e 算法、c o m p l e t e 1 i n k a g e 算法、b i r c h 算法【1 2 】和c u r e 算法【1 】 等。 ( 2 ) 基于代价函数最优的聚类算法( c l u s t e r i n ga l g o r i t h m sb a s e do nc o s t f u n c t i o no p t i m i z a t i o n ) 这种方法用代价函数来量化聚类的可判断性，通常聚类数k 是固定的。这种算法多利用数学分析中的方法对代价函数进行优化，当代价函数 达到最优或是局部最优时，就结束算法。代表算法有著名的k - m e a n s 算法【l3 】和 6 f c m 1 4 j 等算法。 ( 3 ) 基于密度的聚类算法( d e n s i t y b a s e dc l u s t e r i n g a l g o r i t h m s ) 这种算法的本质是把聚类视为特征空问中数据较为密集的区域。优点是可以 发现任意形状的聚类，而且对噪声数据点不敏感。代表算法有d b s c a n 算法【l 5 1 和d e n c l u e 1 7 】等算法。 ( 4 ) 其它的聚类算法 还有一些特殊的聚类算法，包括：遗传聚类算法( g e n e t i cc l u s t e r i n g a l g o r i t h m s ) ，基于网格的聚类算法( g r i d b a s e dc l u s t e r i n ga l g o r i t h m s ) ，基于形态 学的聚类算法( m o r p h o l o g i c a l b a s e dc l u s t e r i n ga l g o r i t h m s ) ，子空间聚类算法 ( s u b s p a c ec l u s t e r i n ga l g o r i t h m s ) ，基于核的方法( k e r n e l b a s e dm e t h o d s ) 等。 根据聚类结果中数据对象是否必须完全属于某个聚类，可以把聚类算法分成 硬聚类( 每个数据对象必须完全属于一个类) ，以及模糊聚类( 每个数据对象不必 须完全属于一个类，而是通过定义隶属度来表示数据属于某个类的程度) 。 聚类算法还可以从不同的角度进行分类，比如根据聚类算法的结果是否依赖 于类原型( 能够代表某个聚类性质的数据元或模型，可以是单个或多个样本点， 或者是聚类中所有样本所共同满足的某种约束) 又可以将其分成基于类原型的聚 类算法，或者基于连通性的聚类算法，前者的代表是k m e a n s 算法，后者的代表 是如基于图论的聚类算法。 2 2 聚类结果的评价 2 2 1 聚类有效性问题 聚类结果的评价就是聚类有效性问题。聚类有效性问题是一个复杂的问题。 聚类分析的本质是给数据集x 强加一个结构或假设，然后按照这个结构或假设设 计聚类算法并对数据集进行聚类。对于同一数据集，采用不同的聚类算法得到的 聚类结果可能不同，而聚类结果也不一定能很好的表示x 本身的结构，这就是说 一个聚类算法不可能对所有数据都适用，不可能在所有的数据集上都取得好的效 果。此外数据集本身也不一定有明显的聚类结构。如果x 具有聚类结构( 聚类倾 向性明显) ，又遇到另一个问题，所有的聚类算法都需要预先知道一些特定参数或 者要求数据符合特殊的约束( 如致密性约束，形状约束等) 。如果对参数进行了不 合适的估计或者采取了不符合数据集的约束，都会导致不正确的聚类结果，所以 对聚类算法的结果进行评价是有必要的。 7 2 2 2 设计聚类有效性指标的基本原则 最近a c k e 咖a 1 1 和d a v “3 j 对聚类有效性指标应该满足的基本要求进行了深入的 理论研究，并提出了聚类有效性指标的几条基本要求，形成了一个较完整的公理 体系。这几条要求大都是基于k l e i n b e r g 提出的对聚类算法的三条要求，但与 k l e i n b e r g 的公理体系不同，a c k e r m a n 矛u d a v i d 提出的对聚类有效性指标的基本要求 是可以同时满足的。也就是说，应该设计出满足这个公理体系所有要求的聚类有 效性指标。下面重点介绍a c k e r m a n 和d a v i d 提出的这个公理体系。 a c k e r m a n 和d a v i d 提出的聚类有效性指标的公理体系中包含三条基本要求：同 构不变性( i s o m o r p h i s mi n v a r i a n c e ) 要求，局部一致性( l o c a lc o n s i s t e n c y ) 要求， c o f i n a lr i c h n e s s 要求。 同构不变性要求：如果两个聚类结果是同构的，那么聚类有效性指标对这两 个聚类结果的评价值应该是相同的。两个聚类结果c 和c 同构的定义为，如果c 中 属于同一类的数据点x ，y 在c 中也属于相同的类，则我们称c 和c 是同构的。同构 不变性的意思就是聚类有效性指标不依赖于聚类结果的具体类标。 局部一致性要求：这是对k l e i n b e r g 提出的一致性的弱化。a c k e r m a n 和d a v i d 首 先定义了距离的局部一致性变化( l o c a lc o n s i s t e n c yv a r i a n t ) 。如果满足下面两个 条件，则称d 在聚类结果c 上是距离d 的局部一致性变化： ( 1 ) 对于聚类结果c 中的任意聚类o ，存在0 i n d e x ( c , 们，就称聚类有效性指标i n d e x 满足局部一致性。因为欧式距 离不可能有局部一致性变化，所以对欧式距离定义弱局部一致性变化( w e a k l y l o c a l l yc o n s i s t e n tv a r i a n t ) ，而要求用欧式距离定义的聚类有效性指标满足弱局部 一致性( w e a k l yl o c a l l yc o n s i s t e n t ) 要求。如果满足下面三个条件，则称d 在聚类 结果c 上是距离d 的弱局部一致性变化： ( 1 ) 对聚类结果c 中的任意聚类e f ，存在o i ， 则这个聚类包含了致密且分离很好的聚类，但是d u m a si n d e x 并不能对聚类结果中 每个聚类的好坏进行评价，这是其缺点之一。而且d u n n si n d e x 对噪声很敏感，p a l 2 1 1 提出基于最小生成树( m i n i m a ls p a n n i n gt r e e ，m s t ) 、相对近邻图( r e l a t i v e n e i g h b o r h o o dg r a p h ，r n g ) 以及g a b r i e l 图( g a b r i e lg r a p h ，g g ) 的d u m a - l i k ei n d e x ， 使指标对噪声敏感程度得到降低。 掣7 = 舞等j 仁叻 以基于最小生成图的d u m a 1 i k ei n d e x 为例进行介绍，定义如公式2 9 ，考虑一 个类c ，和完全图g i ，g ，的顶点为c f 中的数据点，g f 中边e 的权重心等于该边的两 个端点x 与y 之间的距离w e = d ( x ，力。设e 尸7 为g f 的m s t 边集合，p 严7 为e 尸7 中 权值最大的边，c ，的直径d i a m ：4 s r 定义为p 严r 的权值，两个聚类问的距离可以刷它 们的平均向量的距离来定义。 ( 2 ) d a v i e s - b o u l d i n 指标【2 2 】( d bi n d e x ) 和d b