（计算机科学与技术专业论文）聚类集成关键技术研究.pdf

浙江大学博士学位论文 摘要 摘要 集成学习( e n s e m b l el e a r n i n g ) 是指利用多个学习机解决一个问题。9 0 年代 中期开始，集成学习逐渐成为机器学习中最热门的研究领域之一。集成学习早期 的研究都集中在监督式学习中，而对非监督式学习，或者说聚类集成的研究直到 近年来才逐渐受到重视，本文针对聚类集成技术中的几个关键问题进行了研究， 取得的创新性研究成果有： ( 1 ) 对基于数学形态学的聚类集成算法进行了研究。首先提出了一种基于数 学形态学的聚类分析算法c o h m m o p ，它将用于图像处理的方法引入聚类分析， 得到了理想的效果。然后基于此研究结果之上，提出了基于数学形态学的聚类集 成算法c e o m m ，它利用不同的结构元素的探针作用，对不同的结构元素探测出 来的簇核心进行集成，在集成所得到的簇核心基础上聚类。实验结果表明 c o h m m o p 能对具有复杂形状且类间隔很小的数据集进行聚类。由于采用了不同 的结构元素进行探测，算法c e o m m 对于由不同形状的类构成的数据集，比只使 用一种结构元素进行探测更理想。 ( 2 ) 对聚类集体的差异性度量进行了研究，基于分类集成中的一些度量提出 了四种聚类集体差异性度量。实验结果表明各种差异性度量与集成准确度之间并 没有严格的单调正相关关系，影响这种相关性的因素很多，在不同的平均成员准 确度情况下，不同的集体大小情况下，不同的数据分布情况下和不同的集成方法 情况下，这种相关性都不同。但是实验结果也表明当平均聚类成员准确度高于0 6 ， 集体大小为1 5 到2 0 左右，待聚类数据集有均匀簇分布时，各种差异性度量与集 成方法性能问的相关程度很高。并且在比较不同的集成算法在同一个聚类集体上 的集成性能时，发现与差异性度量相关系数更高的集成算法，集成性能也更好。 ( 3 ) 对聚类集体的生成进行了研究，提出了基于添加人工噪声数据的构造差 异性聚类集体的方法c e a n 。在此基础上，进一步提出了增强型差异性聚类集体 构造算法i c e a n ，它首先用c e a n 产生一个比较大的集体，然后对此集体进行 浙江大学博士学位论文 摘要 聚类并从中选择出差异成员构成一个更小但差异性更大的聚类集体。实验证明 c e a n 和i c e a n 产生的聚类集体的差异性很高。 ( 4 ) 对聚类集体的集成( 也称为一致性函数) 进行了研究。提出了聚类集成 算法c m c u g a ，它首先基于信息理论构造了评价与聚类集体统一程度的准则函 数，从而将聚类集成问题转化成了优化问题，然后使用经典遗传算法来找到这个 与聚类集体最统一的聚类结果。c m c u g a 集成算法容易理解，而且它借用成熟 的遗传算法来达到集成目的，不容易陷于局部最优点。实验证明c m c u g a 集成 算法的性能比较理想。还通过把聚类集体当成一个概念型数据集，应用概念型数 据聚类算法k - m o d e s 和l i m b o 来进行聚类集成。实验结果证明用概念型聚类算 法进行集成，效果还是比较好的，特别是用l i m b o 集成的效果相当理想。 ( 5 ) 提出了基于集成技术的混合数据聚类算法c b e s t 。它利用聚类集成技术 产生混合数据的相似性矩阵，基于此相似性矩阵，应用谱聚类算法得到混合数据 聚类结果。实验证明它对混合型数据聚类的效果相当不错，对噪声的鲁棒性也较 好，并且它能有效融合进先验知识。 关键词；聚类，集成学习，聚类集成，差异性，度量，数学形态学，混合型数 据聚类，概念型数据聚类，人工数据 浙江大学博士学位论文 a b s t t a e t a b s t r a c t e n s e m b l el e a r n i n gi sc o m b i n i n gm u l t i p l el e a r n e dm o d e l st os o l v eap r o b l e m s i n c et h em i d - 1 9 9 0 s ，e n s e m b l el e a r n i n gh a sg r a d u a l l yb e c o m et h em o s tp o p u l a r r e s e a r c hd i r e c t i o ni nm a c h i n el e a r n i n g e a r l y ，e n s e m b l el e a r n i n gh a sf o c u s e do nt h e s u p e r v i s e dl e a r n i n g t i l lt h el a s tf i v ey e a r st h e r eh a sb e e na l o to f a c t i v i t yi nc l u s t e r i n g e n s e m b l er e s e a r c h t h ek e yt e c h n o l o g i e so fc l u s t e r i n ge n s e m b l e 勰i n v e s t i g a t e di n t h i sd i s s e r t a t i o n , a n dt h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r es u m m a r i z e da s f o l l o w s ： f i r s t l y ，an e wc l u s t e r i n ga p p r o a c hn a m e dc 0 m v i m o pi sp r o p o s e d ，w h i c hi s b a s e do nt h eu s eo fm a t h e m a t i c a lm o r p h o l o g yo p e r a t i o n s t h r o u g ht h ea l g o r i t h m c o h m m o p , c l u s t e r sa r ed e t e c t e da sw e l ls e p a r a t e ds u b s e t sc a l l e dc l u s t e r i n gc o r eb y m e a n so fh i e r a r c h i c a lm a t h e m a t i c a lm o r p h o l o g yp r o c e d u r e s b a s e do nc o h m m o p , a c l u s t e r i n ge n s e m b l ea l g o r i t h mn a m e dc e o m m i sp r o p o s e d , w h i c hc o m b i n em u l t i p l e c l u s t e r i n gc o r e se x p l o r e db yd i f f e r e n ts t r u c t u r ee l e m e n t st og e ta d e s i r a b l ea n dc o r r e c t c l u s t e r i n gc o r eo fd a t as e t a n dt h e nc e o m mg e tt h ec l u s t e r i n go ft h ed a t as e tb a s e d o nt h ee n s e m b l ec l u s t e r i n gc o r e e x p e r i m e n t a lr e s u l t sd e m o n s t r a t eb o t hc o h m m o p a n dc e o m ma r ea b l et oc l u s t e rd a t aw i t hc o m p l e xc l u s t e rs h a p e sb e t t e rt h a nt h e c l a s s i c a lc l u s t e r i n ga l g o r i t h m s , a n dt h e yc 雒a l s of i n da no p t i m a ln u m b e ro fc l u s t e r s m o r e o v e r , c e o m m c a l ld i s c o v e ro v e r l a p p i n gc l u s t e r s 砸t i ld i f f e r e n ta r b i t r a r ys h a p e s b e c a u s ei tu s e sd i f f e r e n ts t r u e t b r ee l e m e n t s s e c o n d l y , f o u rd i v e r s i t ym e a s u r e sf o rc l u s t e r i n ge n s e m b l e sa r ep r o p o s e d s i x e x p e r i m e n t sh a v eb e e nd e s i g n e dt oe x a m i n et h er e l a t i o n s h i p sb e t w e e nt h ea c c u r a c yo f t h ec l u s t e r i n ge n s e m b l e sa n dt h em e a s u r e so fd i v e r s i t yu n d e rc o n d i t i o n so fd i f f e r e n c e e n s e m b l em e t h o d s ，d i f f e r e n te n s e m b l es i z ea n dd i f f e r e n td a t ad i s t r i b u t i o n sr e s p e c t i v e l y e x p e r i m e n t ss h o wt h er e l a t i o n s h i p so ft h e s ed i v e r s i t y m e 鹊u r e sa n de n s e m b l e p e r f o r m a n c e a r en o tm o n o t o n o u s h o w e v e r , w h e n c o n s t r u c t i n g e n s e m b l e sw i t h m o d e r a t ee n s e m b l es i z eb ys u i t a b l ec l u s t e r i n ga l g o r i t h m sf o rag i v e nd a t as e tw i t h u n i f o r mc l u s t e rd i s t r i b u t i o n , t h ec o r r e l a t i o nc o e m c i e n t sb e t w e e nt h ed i v e r s i t y m e a s u r e r sa n de n s e m b l ep e r f o r m a n c ea r cr e l a t i v e l y h i g h f i n a l l y s o m eu s e f u l s u g g e s t i o n s a b o u tt h eu s e f u l n e s so fd i v e r s i t ym e a s u r e si n b u i l d i n gc l u s t e d n g e n s e m b l e sa r ep r o p o s e d t h i r d l y , am e t h o df o c u s e do ng e n e r a t i n gc l u s t e r i n ge n s e m b l e sw i t hh i g hd i v e r s i t y n a m e dc e a ni sp r o p o s e d b yi n t r o d u c i n gt h ea r t i f i c i a ld a m c e a nc a r lo b t a i n c l u s t e r i n ge n s e m b l e sw i t hh i g hd i v e r s i t y a n db a s e do nc e a n ，a ni m p r o v e dd i v e r s i t y 浙江大学博士学经论文 e n s e m b l ec o n s t r u c t i n gm e t h o dn a m e di c e a ni sp r o p o s e d i c e a nc h o o s g sd i v e r s e c l u s t e r i n g so fal a r g ec l u s t e r i n ge n s e m b l ep r o d u c e db yc e a nt og e tas m a l l e ra n d i v i o i ed i v e r s ee n s e m b l e n 把e x p e r i m e n t a lr e s u l t ss h o wb o t hc e a na n di c e a nc a n g e t e n s e m b l e sw i t l l h i g h e rd i v e r s i t y t h a no t h e r p o p u l a rc l u s t e r i n ge n s e m b l e c o n s t r u c t i n ga p p r o a c h e s ，e s p e c i a l l yi c e a na l w a y sg e tt h em o s td i v e r s ee n s e m b l e s s o u n d e rt h es a m ea v e r a g ee n s e m b l em e m b e ra c c u r a c y , c e a na n di c e a nc a ng e tb e t t e r c l u s t e r i n gi n t e g r a t i o ne f f e c t f o u r t h l y , ac o n s e n s u ss c h e i n en a m e dc m c u g a v i at h eg e n e t i ca l g o r i t h mb a s e d o ni n f o r m a t i o nt h e o r yi sp r o p o s e d ac o m b i n e dc l u s t e r i n gi sf o u n db ym i n i m i z i n ga l l i n f o r m a t i o n - t h e o r e t i c a lc r i t e r i o nf u n c t i o nu s i n gg e n e t i ca l g o r i t h m e x p e r i m e n t a lr e s u l t s d e m o n s t r a t et 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 d a d d i t i o n a l l yac o n s e n s u s s c h e m ev i ac a t e g o r i c a ld a t ac l u s t e r i n ga l g o r i t h mi sp m p o m d ac o m b i n e dp a r t i t i o ni s f o u n da sas o l u t i o nt ot h ec o r r e s p o n d i n gc a t e g o r i c a ld a t ac l u s t e r i n gp r o b l e mu s i n gt h e k - m o d e sa n dl i m b oa l g o r i t h m e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h e e f f e c t i v e n e s so f t h ep r o p o s e dm e t h o d f i f t h l y , ac l u s t e r i n ga l g o r i t h mb a s e do ne n s e m b l ea n ds p e c t r a lt e c h n i q u en a m e d c b e s tt h a tw o r k sw e l lf o rd a t a 、i t l im i x e dn u m e r i ca n dc a t e g o r i c a lf e a t u r e si s p r e s e n t e d as i m i l a r i t ym e a s u r eb a s e do nc l u s t e r i n ge n s e m b l ei sa d o p t e dt od e f i n et h e s i m i l a r i t yb e t w e e np a i r so fo b j e c t s ，w h i c hm a k e sn oa s s u m p t i o n so ft h eu n d e r l y i n g d i s t r i b u t i o n so ft h ef e a t u r ev a l u e s as p e c t r a lc l u s t e r i n ga l g o r i t h mi se m p l o y e do nt h e s i m i l a r i t ym a t r i xt oe x t r a c tap a r t i t i o no ft h ed a t a t h ep e r f o r m a n c eo fc b e s th a s b e e ns t u d i e do na r t i f i c i a la n dr e a ld a t as e t s r e s u l t sd e m o n s t r a t et h ee f f e c t i v e n e s so f t h i sa l g o r i t h mi nc l u s t e r i n gm i x e dd a t at a s k sa n di t sr o b u s t n e s st on o i s e c o m p a r i s o n s w i t ho t h e rr e l a t e dc l u s t e r i n gs c h e m e si l l u s t r a t et h es u p e r i o rp e r f o r m a n c eo ft h i s a p p r o a c h m o r e o v e r , c b e s t c a l li n f u s ep r i o rk n o w l e d g ee f f e c t i v e l y k e y w o r d s ：c l u s t e r i n g ，e n s e m b l el e a r n i n g ，c l u s t e r i n ge n s e m b l e , d i v e r s i t y , m e a s a r e ， m a t h e m a t i c a lm o r p h o l o g y , m i x e dd a t ac l u s t e r i n g ，c a t e g o r i c a ld a t ac l u s t e r i n g ，a r t i f i c i a l d a t a 浙汪大学博士学位论文 圈目录 图目录 图3 1离散化参数m 对检测到的簇个数的影响3 0 图3 2 结构元素对探测出来的聚类核心形状的影响3 2 图3 3 不同的数学形态运算序列对聚类结果的影响3 3 图3 4c o h m m o p 实验结果3 5 图3 5 有5 个形状各异的类的数据集3 8 圈3 6 图3 5 所示的数据源使用离散化参数肝：6 0 离散化后的效果图3 8 图3 7 利用不同的结构元素对图3 6 所示的离散化后的数据进行开运算加闭运算 后得到的不同簇核心3 9 图3 8 将图3 7 所示的十二种簇核心用绝对多数投票法得到的集成簇核心4 1 图3 9 利用图3 8 的簇核心进行聚类得到图3 5 所示数据源的聚类结果( 不同形状 的符号代表不同的簇) 4 2 图3 1 0k - m e a n s 对图3 5 所示数据源的聚类效果( 不同形状的符号代表不同的簇) z l ： 图3 1 1c e o m m 实验结果( 不同形状的符号代表不同的簇) 4 3 图4 1各种差异性度量和c s p a 集成准确度与集体大小之间的关系图5 5 图4 2 差异性度量值对c s p a 集成准确度散点图5 6 图5 1人工数据集d a t a s e t l 7 3 图5 2 人工数据集d a t a s e t 2 7 4 图s 1 3人工附加噪声数据比例对i c e a n 的影响。7 8 图5 4i c e a n 在不同大小的待聚类数据集上的效果8 0 图6 1两个人工数据集9 0 图6 2c m c u o a 集成效果v e r s u s 单个成员聚类效果9 l 图6 3k - m o d e s 和l i m b o 聚类集成效果9 8 图6 4 六个人工数据集1 0 1 图7 1不同比例噪声数据对c b e s t 算法错误率的影响1 1 0 图7 2人工数据集d a t a s e t i 的两个数值型属性分布图1 1 2 图7 3人工数据集d a t a s e t 3 的两个数值型属性分布图1 1 4 浙江大学博士学位论文 表目录 表4 1 表4 2 表4 3 表4 4 表 表 表 表 4 5 5 1 5 2 5 3 表6 1 表6 2 表6 3 表6 4 表6 5 表7 1 表7 2 表7 3 表7 4 表7 5 表7 6 表7 7 表目录 不同平均成员准确度情况下各种差异性度量与c s p a 集成准确度的相关 系数5 9 不同的集体大小情况下各种差异性度量与c s p a 集成准确度的相关系数 5 9 六个不同的数据分布6 0 不同数据分布类型上的差异性度量与c s p a 集成准确度之间的相关系数 ，6 l 各种差异性度量与不同聚类集成算法集成准确度之间的相关性6 3 数据集描述7 2 不同数据集上各种聚类集体生成方法的比较7 6 不同的集成方法在不同的集体构造算法产生的聚类集体上的集成错误率 7 7 四个数据集的相关信息9 0 c m c u g a 算法与其他五种一致性函数在i r i s 数据集上的聚类集成错误率 9 三! 使用不同发生器的c m c u g a 聚类集成错误率9 3 l i m b o 和k - m o d e s 与其他集成算法在i r i s 数据集上的集成错误率1 0 0 六个人工数据集上各种聚类集成算法的错误率一1 0 1 概念型数据集例子1 0 6 人工数据集d a t a s e t l 上的实验结果1 1 2 人工数据集d a t a s e t 2 上的实验结果1 t 3 人工数据集d a t a s e t 3 上的实验结果1 1 5 真实数据集t h eg e r m a nc r e d i td a t a s e t 上的实验结果1 1 6 真实数据集a u s t r a l i a nc r e d i ta p p r o v a l 上的实验结果“7 真实数据集t h e h e a r t - d i s e a s e c l e v e 上的实验结果1 1 8 v 浙江大学博士学位论文 第l 章绪论 1 1 聚类分析 第1 章绪论 将对象( o b j e c t ) 或模式( p a t t e r n ) 分组是一种最基本的智能模式，人类很容易就 能做到，很小的小孩在不知道猫和狗的概念的时候就能区分开它们。但是让计算 机来做自动分组的事情却是相当困难的，聚类分析就是在没有任何可供学习的样 本情况下，将对象集自动分组的一种分析方法。聚类分析在探测型数据分析领域 中是一个重要的技术，它被广泛应用在工程和科学研究领域中。聚类分析通过提 取潜在的结构将对象组织成类( c l a s s ) 或簇( c l u s t e r ) ，一个簇由聚集在一起的相似 的对象组成【1 】。e v e r i t t1 2 1 列举了以下关于簇的定义： 1 一个簇是相似的对象的集合，属于不同簇的对象不相似。 2 一个簇是在测试空间中的点的集合，它使得这个簇中的任意两点之间的 距离比任何的这个簇内的点与簇外的点之间的距离小。 3 簇可以描述成在一个多维空间中的连通区域，并且它含有相对高的点密 度，它与其他这样的连通高密度区域通过一个相对低的点密度区域隔离 开来。 假设所有待聚类的对象由特征表示，并形成d 维特征向量，则一个典型的聚 类分析任务包含以下步骤1 1 1 ： 1 模式表示：选择适当的特征来表示对象( 或称为模式) ，尽可能多的包含与 任务相关的信息但又要使信息冗余减少。特征提取和选择不但可以提高 算法的性能而且能提高速度，还可用于可视化。 2 模式间的相异性( 或相似性) 测量：相异性( 或相似性) 测量方法的选 择很重要，一般选择在特征空间中的距离度量。 3 聚类( 分组) ：选择合适的算法来揭示数据集的聚类结构。 4 数据抽象( a b s t r a c t i o n ) ( n - - i 选) ：根据聚类结果归纳出简单而紧凑的类的 描述。 塑堑叁堂堕主星鱼丝第1 章绪论 5 结果评估( 可选) 。 聚类分析的核心是聚类，也就是将对象组织成一个个的簇，以使褥同一簇内 的对象相似，而不同簇间的对象不相似。聚类的输入是已经表示成多维特征向量 的对象集或对象相似( 相异) 矩阵。聚类与分类的不同之处在于：在进行分类学习 前，必须有已经标好类标签的对象集，分类在此对象集上进行学习得到类的概念 后再对新的数据进行分类；而聚类在一个完全陌生的对象集上运行，它没有已经 分好类的对象集来供它学习。所以聚类是一种非监督式学习，而分类是监督式学 习。 虽然在低维空间中，对少量对象进行区分对人类来说相当容易，但是对于高 维海量对象集或数据集，人类就必须依赖于计算机。随着计算机在各行各业的广 泛应用和发展，面对涌现出来的越来越多的海量高维数据，没有一些总结，归纳， 分析和抽象工具来帮助人类，人类将无法轻易从中得到任何有用信息或知识。聚 类分析作为一种探测型数据分析方法，它可以揭示对象与对象之间，对象与特征 之间，特征与特征之间的关系。 聚类分析在许多领域中有着重要的作用，其中包括人工智能，生物学，客户 关系管理，数据压缩，数据挖掘，信息检索，图像处理，机器学习，营销，医药， 模式识别，心理学，推荐系统和统计【3 1 。 聚类分析的典型应用有以下四个方面 4 1 ： 1 减少数据( 数据压缩) ：先将数据聚类，然后每个簇用一个原型或一些代 表点来表示，从而达到数据压缩的目的。 2 假说生成：为了得到数据性质的一些假设或有关数据结构信息的一些猜 想。可以先对数据集进行聚类分析，以对数据有一定的了解。因此，这 里使用聚类作为建议假说的媒介，然后可以使用其他数据集验证这些假 说。 3 假设检验：使用聚类分析来验证指定假说的有效性。 4 基于分组的预测：先对现有数据集聚类分析后，形成每个簇的特征表示， 对于一个新的数据，先识别它所属的簇，然后根据这个簇的特征来对它 2 浙江大学博士学位论文第1 章绪论 迸行预测。 聚类方法有许多种，有非层次聚类方法，也就是说只得到数据的一个聚类； 也有层次方法，它得到不同层次上的聚类，形成一棵聚类树。有硬聚类方法，也 就是说每个数据属于且仅于一个簇；也有软聚类方法，它给出每个对象属于不同 簇的概率。 本章剩余内容的安排如下：1 2 小节介绍本论文中用到的术语及其表示方法； 1 3 小节阐述了本论文的研究动机；1 4 小节归纳了本论文所作的工作：1 5 小节 介绍了本论文的内容安排。 1 2 术语及其表示方法 本论文研究核心是聚类算法，所以以后对象集都称为数据集，而对象或模式 就称为数据或数据点。一个数据集是多维特征向量的集合，一个有，1 个对象的数 。 据集一般表示成：x = “，x 2 ，) 。一个有d 维特征的对象表示成一个多维矢量 x ? t ，】或= i x 。，】。对于聚类，本论文一般指硬聚类，也就是说一个 聚类是一个数据的完整划分，每个数据点都属于且仅属于一个簇。一个聚类结果 一般表示成一个多维矢量石，= 阮( 而) ，石，( x ：) ，r ( ，。) 】，其中巧( x ，) 表示聚类巧给 数据x ，置的簇标签，其中簇标签一般用整数来表示。比如，对于一个只有5 个对 象的数据集，聚类互= 【l ，l ，l ，2 ，2 】就表示将前三个数据分成一个簇“，屯，毛 ，置簇 标签1 ，后两个数据组成另一个簇瓴，砖) ，置簇标签2 。对于类和簇的区分，当 我们针对一个数据的正确分类结果时，习惯称其中的每个分组为一个类( c l a s s ) ， 当我们指聚类结果时，习惯称其中的每个分组为一个簇( c l u s t e r ) 。 1 3 研究动机( m o t i v a t i o n ) 与监督式分类相比，聚类是一种病态( 讣p o s e d ) f 日题【5 l 在没有关于潜在数据 分布的先验知识情况下，不同的聚类解答看来都是同等可接受的。聚类分析算法 一般都需要采用相似性度量和聚类准则，而这当中潜含着对数据中包含的类结构 浙江大学博士学位论文第l 章绪论 的某种假设。当这些假设与样本数据不相符时，它可能产生错误或没有意义的结 果，所以关于数据领域的先验信息对于成功聚类是关键的，但是这种信息即使从 领域专家那里也很难获得。这就使得每种聚类算法都可能在某种特定的模式分布 下比其他算法好。k l e i n b e r g 5 】提出和证明了聚类分析的不可能性定理，即任何 个聚类算法不可能同时满足尺度不变性( s c a l e i n v a r i a n c e ) ，丰富性( r i c h n e s s ) 和一致 性( c o n s i s t e n c y ) 。假设一个聚类算法( 或称为聚类函数) f 在数据集x 上得到一个 聚类( 或称为划分) 7 r ，f 采用的距离函数表示成d 。则尺度不变性( s c a l e i n v a r i a n c e ) 是指对于任意的距离函数d 和系数a 0 ，有胸= 贝哟成立。丰富性( r i c h n e s s ) 是 指由于采用不同的距离函数，厂所能得到的不同聚类个数等于数据集彳的所有可 能划分的个数。一致性( c o n s i s t e n c y ) 是指如果兵力= 1 ，并且d 是d 的万转换距离 函数，则厂( ) = 石。其中d 是d 的石转换距离函数表示如果x ，x ，在聚类霈属于 同一个簇，则d t ( 毛，工，) d ，工，) ，反之d ( ，x ，) d ( ，x j ) 【”。所以面对诸多的聚 类算法，聚类分析者不但要完全理解特定的技术，而且也要知道数据获取过程的 细节和一些领域知识以便作出明智的选择1 6 1 。这些要求对用户来说显然是不太可 能达到，聚类任务的探测本质要求有更有效的聚类方法。聚类集成技术正是在这 种缺少领域知识的聚类问题背景下发展起来的，它寻找多个聚类解答的结合来获 得更优的聚类。聚类集成能在以下几个方面超过单个聚类算法1 7 l ：在不同领域和 数据集上有更好的平均性能；能发现任何单个聚类算法无法得到的结合解答；对 于噪声，异常点，采样的变动更不敏感，还可以从聚类集体分布中估计得到簇 ( c l u s t e r ) 的不确定性；通过数据子集或特征子集的并行聚类和后续结果的结合，使 得聚类集成可以具有更好的并行性和可缩放性，而这对于现在数据挖掘领域的海 量高维数据集是非常重要的；它还能结合多个分布数据源或特征上的聚类解答， 而多个数据源或特征的聚类的融合在分布式数据挖掘中正变得越来越重要。 为什么多个聚类结果的集成在大多数情况下比集体的平均成员聚类性能更 好，甚至经常比集体中最好成员的性能更好? h a n s e n 和s a l a m o n1 $ i 假设集体由 个独立的学习机构成，每个成员学习机的误差是p ，并假设参与集成的各成员学 4 浙4 太堂博士学位论垄l 一 第1 章绪论 习机的误差是相互独立的，那么采用绝对多数投票法集成得到的误差是： 厂 ，、 e = k ki p k ( 1 一p ) h 公式( 1 1 ) k nj 2 一， 在p o 5 时，昱随的增大两单调递减。因此，当每个学习机的正确率都高 于o 5 时，并且它们的错误相互独立时，随着集体中成员学习机数目的增加集成 的准确度就越高，当趋向于无穷时，集成的错误率趋向于0 。 这就说明在集成学习中，只有当集体中的成员在一些输出上不一致时，结合 它们才能减少学习误差【8 一。这种不一致性称为集体的差异性，当集体的差异性 增加，也就是成员学习器之间的关联性越低时，集成学习的优势就越明显。 虽然集成学习技术在9 0 年代中期开始逐渐成为机器学习中最热门的研究领 域之，但集成学习早期的研究都集中在监督式学习中，而对非监督式学习，或 者说聚类集成的研究直到最近几年才开始。聚类集成算法要解决的主要问题有两 个l 1 0 1 ，一个是如何产生不同的聚类从而形成一个聚类集体，第二个问题是如何从 这个聚类集体中得到一个统一的聚类结果。目前国内外在聚类集成方面的研究都 把重点放在第二个问题上，也就是如何从聚类集体中得到一个统一的聚类结果， 所谓的一致性函数( c o n s e n s u sf u n c t i o n ) 的研究土。 如何生成一个高质量的聚类集体? 怎样来度量一个聚类集体的差异性? 怎 样的集成方法更适合于当前的聚类集体? 如何充分利用集体的差异性进行聚类 集成? 如何利用聚类集成技术? 这些问题是影响聚类集成性能的关键，是值得深 入研究的问题。本文将对聚类集成技术中的关键问题进行研究，以提高聚类集成 的效果，这对于聚类集成算法走向实际应用领域是非常重要的。 1 4 本文的工作 本论文针对聚类集成中的几个关键问题进行研究，主要做了以下几方面的工 作： 1 首先研究了基于数学形态学的聚类方法，基于此提出了利用不同的结构 元素得到簇核心集体，在其上集成得到集成簇核心后，再进行聚类的方 浙江大学博士学位论文第1 章绪论 法。实验证明此方法对于具有复杂簇形状的数据集聚类效果比较理想。 2 针对聚类集体差异性度量问题，提出了几种聚类集体差异性度量方法， 并且对各种差异性度量与不同集成方法性能间的关系进行了比较全面的 实验研究，得到了一些可取结论。 3 针对聚类集体生成问题，提出了在生成聚类集体的过程中人为加入噪声 数据以增加聚类集体的差异性的方法。并进一步提出利用人工附加数据 生成一个比较大的聚类集体后，选择差异成员组成一个更小但差异性更 大的聚类集体的算法。此算法在数据集比较小，特征少，从而用传统方 法不足于产生一个差异性聚类集体时比较有效。 4 针对聚类集成问题或者说一致性函数问题，提出了一种基于信息理论和 遗传算法的集成方法，并且提出了将集成问题转换成概念型数据聚类问 题，由概念型数据聚类算法来进行聚类集成的方法。这两种算法的思路 都是将聚类集成问题转换成其他闯题，从而剩用其他研究领域的成功算 法来实现聚类集成。实验证明这两种方法是行得通的，效果也是比较理 想的。 5 将聚类集成技术应用于混合型数据聚类，提出了一种效率和效果都比较 理想的混合型数据聚类算法。 1 5 本文的结构安排 第二章是研究背景和相关文献综述。第三章是基于数学形态学的聚类集成算 法的研究，利用数学形态学得到待聚类数据集的簇核心集，从而利用集成技术得 到一个更优的聚类结果。聚类集成首先需要生成一个差异性聚类集体，然后对此 聚类集体进行集成。由于聚类集体的差异性是聚类集成中的一个关键影响因素， 所以在第4 章对聚类集成的差异性度量进行了研究。既然聚类集成首先需要生成 一个差异性聚类集体，所以第5 章针对聚类集体的构造进行了研究。在生成一个 聚类集体后，就是如何利用这个聚类集体进行集成的问题了，所以本文在第6 章 对一致性函数进行了研究，也就是聚类集体集成的研究。由于大多数的聚类算法 6 浙江大学博士学位论文第1 章绪论 和准则函数都不适于处理混合型数据，所以在第7 章提出了一种基于集成技术的 混合数据聚类算法。最后一章是论文的总结和对未来工作的展望。第三章到第七 章，每章将以国内外研究现状分析开始，以该章工作的总结和对未来工作的展望 结束。 浙江大学博士学位论文第2 章研究背景及相关文献综述 第2 章研究背景及相关文献综述 2 1 引言 在设计分类器时，用来学习的训练样本集中的样本类别归属是被标记了 ( 1 a b e l e d ) 的。这种利用已标记样本集的学习方法称为有监督学习( s u p e r v i s e d l e a r n i n g ) 方法。而对于聚类来说，它是一种无监督学习方法( u n s u p e r v i s e dl e a r n i n g ) ， 它用来处理未被标记的样本集。从原理上讲，究竟能不能从未被标记的样本中学 到一些有用的东西，这完全取决于我们是否愿意去接受一些假设( a s s u m p t i o n ) ，毕 竟，任何理论的证明都是以一些假设为前提的【i ”。对同一组对象进行聚类，可能 会由于采用的特征、相似性度量、聚类算法准则函数和算法搜索策略不同而导致 完全不同的结果，而这些度量、准则和策略就隐含着对数据的一些假设。在用户 不能确定哪种假设更会理时，可能结合它们能获褥更好的平均性能，所冒的错误 聚类损失风险也可以低得多。2 2 小节将对聚类算法进行文献综述，在介绍各种 聚类算法时，会尽可能的介绍清楚它们所采用的相似性度量，准则函数和搜索筑 略；2 3 小节将介绍应用到聚类算法中的各种搜索技术，以及它所导致的偏差 ( b i a s ) ；2 4 小节将介绍聚类集成技术；最后是本章小结。 2 2 聚类算法 目前在文献中存在大量的聚类算法，下面将按照以下几类来分别介绍其中的 一些典型算法【1 2 】：划分方法；凝聚型层次方法；基于密度的方法；基于网格的方 法；混合密度估计方法：针对概念型和混合型数据的聚类算法：模糊聚类方法； 和聚类分析中的一些最新方法( 谱聚类方法，约柬聚类和基于聚类的特征选择) 。 这里之所以把基于聚类的特征选择放在聚类算法中，是因为基于聚类的特征选择 其实是一种聚类算法，它与特征选择融合在一起以解决高维数据的聚类问题。 浙江大学博士学位论文第2 章研究背景及相关文献综述 2 2 1 划分方法 划分方法也称为硬聚类方法，它将数据集划分成互不相交的簇。划分方法通 过优化一个局部定义( 定义于模式子集) 或全局定义( 定义于所有数据上) 的准 贝j j i 函数来得到数据的一个聚类陋1 。k - m e a