（计算机软件与理论专业论文）半监督学习方法及其应用研究.pdf

摘要 摘要 随着计算机技术的发展，人类收集数据、存储数据的能力得到了极大的提高，无论 是科学研究还是社会生活，各个领域中都积累了大量的数据，对这些数据进行分析以发 掘数据中蕴含的有用信息，几乎成为所有领域的共同需求。传统的机器学习方法大多只 考虑有标记数据( 1 a b e l e dd a t a ) 或者未标记数据( u n l a b e l e dd a t a ) ，但是在很多真实问题 中往往是二者并存的。半监督学习( s e m i s u p e r v i s e dl e a r n i n g ) 由此应运而生。 半监督学习是模式识别和机器学习中重要研究领域之一，一直为国际机器学习界关 注，其在分类( c l a s s i f i c a t i o n ) 和聚类( c l u s t e r i n g ) 中得到了广泛的应用，本文主要针对 半监督聚类进行研究和分析。 本文首先对于半监督聚类领域的国内外研究情况进行回顾，然后通过对无监督聚类 和监督学习理论知识的介绍，得出半监督聚类为何会得到广泛关注，同时给出半监督聚 类常用的思路和算法。最后本文详细介绍了我们在这方面研究开展的一系列工作： ( 1 ) 我们提出了改进微分进化算法的半监督模糊聚类，在结合传统f c m 和进化 算法的基础上，参考粒子群算法惯性权重思想，引入惯性加权系数。算法前期可以维持 个体的多样性，后期能够加快算法的收敛速度，有效地提高了算法的性能。遥感图像数 据等实验结果证明了算法的有效性。 ( 2 ) 我们提出了基于改进的成对约束的半监督聚类算法，首先对原先少量约束对 信息进行调整，增加约束对量。在此基础上利用监督信息对原始数据进行降维，利用闭 包中心代替闭包集，最后在基于成对约束的k 均值算法上进行聚类。该算法解决了成对 约束的违反问题，同时提高了聚类的性能。在u c i 数据集的实验中可以证明这种方法的 可行性。 关键词：半监督聚类，模糊c 均值，k 均值算法，成对约束，进化算法，闭包 a b s t r a c t a b s t r a c t w i 廿lt h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , t h ea b i l i t yo fd a t ac o l l e c t i o na n ds t o r a g e h a sb e e ni m p r o v e dg r e a t e l y n o to n l yi ns c i e n c er e s e a r c h ，b u ta l s oi nd a i l yl i f ep l e n t yo fd a t a h a sb e e ng a i n e d h o wt oa n a l y s et h e s ed a t ag o ta n dm i n et h eu s e f u li n f o r m a t i o nh i d d e ni nt h e d a t a ，w h i c hi sac r i t i c a lr e q u i r e m e n ti ne v e r yf i e l d i nt h et r a d i t i o n a lm a c h i n el e a r n i n g ，j u s tt h e u n l a b e l e dd a t ao rt h el a b e l e dd a t aw e r ec o n s i d e r e d b o t ho ft h e ma r ee x i s t i n gi nm a n y i n s t a n c e s ，h o wt ou s et h ec o m b i n e di n f o r m a t i o n s ，t h e ns e m i - s u p e r v i s e dl e a r n i n gi sp r o p o s e d s e m i s u p e r v i s e dl e a r n i n gi s o n eo ft h em o s ti m p o r t a n tr e s e a r c hf i e l d si n p a t t e r n r e c o g n i t i o na n dm a c h i n el e a r n i n g i ti sw i d e l ya p p l i e di nc l a s s i f i c a t i o na n dc l u s t e r i n g i nt h i s p a p e ro n l ys e m i - s u p e r v i s e dc l u s t e r i n gi sm e n t i o n e d i nt h i sp a p e r , f i r s t l y , t h es t u d ys t a t u so ns e m i s u p e r v i s e dc l u s t e r i n gi sr e v i e w e d s e c o n d l y , w ei n t r o d u c et h et h e o r yo ft h en o n - s u p e r v i s e dc l u s t e r i n ga n ds u p e r v i s e dc l u s t e r i n g ，a n dg e t t h er e a s o n sw h ys e m i - s u p e r v i s e dl e a r n i n gi sw i d e l ya t t e n d e d w ea l s oi n t r o d u c et h eg e n e r a l m e t h o da n da l g o r i t h mi ns e m i - s u p e r v i s e dc l u s t e r i n g l a s t l y , w ep r e s e n tw h a tw eh a v ed o n e a b o u ts e m i - s u p e r v i s e dc l u s t e r i n gw h i c hc a nb eg e n e r a l i z e dt w ot h i n g s ( 1 ) w ep r o p o s eam o d i f i e dd i f f e r e n t i a le v o l u t i o na l g o r i t h mf o rs e m i - s u p e r v i s e df u z z y c l u s t e r i n g o nt h eb a s e so ft r a d i t i o n a lf c ma l g o r i t h ma n de v o l u t i o n a r ya l g o r i t h m , w ei n t r o d u c e i n e r t i a - w e i g h t e dc o e f f i c i e n tb yc o n s i d e r i n gi n e r t i a - w e i g h t e di d e ao fp a r t i c l es w a r ma l g o r i t h m ， w h i c hk e e p sd i v e r s i t yo fi n d i v i d u a la te a r l ys t a g e sa n dq u i c k e n sc o n v e r g e n ts p e e da tl a t e r s t a g e s ，a n da tt h es a m et i m ei m p r o v e st h ep e r f o r m a n c eo ft h ea 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 f o rr e m o t es e n s i n gd a t ai n d i c a t et h ee f f i c i e n c y ( 2 ) w ep r o p o s eas e m i - s u p e r v i s e dc l u s t e r i n ga l g o r i t h mb a s e do nm o d i f i e dp a i r w i s e c o n s t r a i n t s w ea d j u s tt h eo l df e wp a i r w i s ec o n s t r a i n t st og e tm o r ei n f o r m a t i o na tf i r s t ，t h e n u t i l i z en e ws u p e r v i s i o nt oi n t e g r a t ed i m e n s i o n a lr e d u c t i o n w eu s ep a i r w i s ec o n s t r a i n t s k - m e a n sa l g o r i t h mt oc l u s t e ri nt h es u b s e ti nw h i c ht h ec l o s u r e sa r ec h a n g e db yc l o s u r e s c e n t e r t h i sn e wa l g o r i t h ms o l v e st h ep r o b l e mo fv i o l a t i n gp a i r w i s ec o n s t r a i n t s ，a l s oi m p r o v e s t h ep e r f o r m a n c eo fc l u s t e r i n g t h ef e a s i b i l i t yi sp r o v e do nu c id a t a b a s e k e y w o r d s ：s e m i - s u p e r v i s e dc l u s t e r i n g ，f u z z ycm e a n ，k - m e a n sa l g o r i t h m ，p a i r w i s e c o n s t r a i n t s ，e v o l u t i o na l g o r i t h m ，c l o s u r e i i 独创性声明 本人声明所呈交的学位论文是芬人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签 名- 殛拯兰遮 日 期：理之星：缨 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签 名：盗拯! 送导师签名：壅塑盔 日 期：7 的少孑笋 第章引言 第一章引言 1 1 半监督聚类研究现状 数据库技术的发展使保存在计算机上的数据以惊人的速度增长，面对迅速膨胀的超 级数据库时，人们却无从着手去理解数据中包含的信息，更难以获得有价值的信息。如 何从海量的数据中提取有用的和有价值的信息即知识成为信息研究的瓶颈【1 1 。数据挖掘 就是因为这些问题应运而生发展起来的数据处理技术。数据挖掘在2 0 世纪9 0 年代以美 国信息工程领域为代表的研究专家做了大量的尝试与研究，并对数据挖掘做了详细的论 述。 数据挖掘是从大量数据中提取人们感兴趣的信息和知识，这些往往是隐含的、有用 的、尚未发现的，它是一种综合应用统计分析、数据库和智能语言等来分析庞大数据资 料的智能化技术1 2 | 。这个定义包括好几层含义： ( 1 ) 数据源必须是真实的、大量的、含噪音的； ( 2 ) 发现的必须是用户感兴趣的知识； ( 3 )发现的知识要可接受、可理解、可运用，最好能用自然语言表达发现； ( 4 )并不是要求是放之四海皆准的知识，所有发现的知识都是相对的，是有特定 前提和约束条件、面向特定领域。 目前，数据挖掘已经引起了人们的广泛关注，成为国内外数据库和信息决策领域的 最前沿研究方向。 聚类分析是依据样本间关联的度量标准将其自动分成几个群组，且使同一群组内的 样本相似，而属于不同群组的样本相异的一组方法。一个聚类分析的系统输入是一组样 本和一个度量两个样本间相似度( 或相异度) 的标准。聚类分析的输出是数据集的几个 组( 类) ，这些组构成一个分区或个分区结构。聚类过程通常是没有教师指导的，是 无监督过程。 基于目标函数的聚类方法已成为聚类分析的主流【3 1 。一方面可将其转化为优化问题 易于与经典数学的非线性规划领域联系起来，用现代数学方法来求解；另方面求解过 程易于计算机实现。各种聚类方法得到了广泛的应用。如图像处理、模式识别以及模糊 推理等。 在很多实际应用中，在得到数据同时，可能得到一些先验知识。在传统的聚类分析 过程中，算法对样本进行聚类并未考虑先验知识。 半监督学习是近年来机器学习领域的一个研究热点。在实际应用中，获取大量无标 江南大学硕士学位论文 签样本是非常容易的，而获取有标签的样本需要付出大量时间和精力，代价昂贵。传统 的无监督学习只考虑无标签样本，而监督学习只利用少量的有标签样本学习。半监督学 习的优越性则体现在综合利用有标签和无标签样本进行学习【4 1 。 半监督学习一般分为两大类：半监督分类和半监督聚类。前者利用有标签数据辅佐 分类过程，以达到更好的分类效果；后者利用无标签数据使算法达到更好的分类效果。 本文针对半监督聚类进行研究。 1 9 8 5 年，p e d r y c z 5 】在研究模糊聚类算法时就已提出半监督聚类的思想，把“半监督 称为“部分监督 ( p a r t i a ls u p e r v i s i o n ) 。然而一直到最近几年，伴随着大规模实际问题的 出现，人们才重新认识到半监督聚类的价值。许多传统的聚类算法陆续被推广到相应的 “半监督 版本。 现有的半监督聚类算法大致可分为3 类。第1 类是基于约束的半监督聚类算法 ( c o n s 仃m n t b a s e ds e m i - s u p e r v i s e dc l u s t e r i n gm e t h o d ，简称c b s s c ) 。这类算法一般使用 m u s t 1 i n k 和c a n n o t - l i n k 成对约束来引导聚类过程。其中又可以分为如下几类： ( 1 ) 在原始目标函数中增加一个包含样本标记信息或者其他约束的监督项【6 】； ( 2 ) 在聚类过程中分配类标记时施加强制约束【7 】； ( 3 ) 利用有标记样本或者其他约束来生成一个初始聚类【8 】【9 1 。 第2 类是基于距离的半监督聚类算法( d i s t a n c e b a s e ds e m i s u p e r v i s e dc l u s t e r i n g m e t h o d ，简称d b s s c ) ，这类算法利用成对约束来学习距离度量，从而改变各样本之间 的距离，使其有利于聚类。其可分为如下几类： ( 1 ) 基于期望最大化方法( e m ) 的s t r i n g e d i t 度量【1 0 1 ； ( 2 ) 基于最短路径算法的欧式度量【l l 】； ( 3 ) 基于凸最优化的马氏度量【1 2 】【1 3 】。 第3 类是集成了约束与距离的半监督聚类算法( c o n s t r a i n ta n dd i s t a n c eb a s e d s e m i s u p e r v i s e dc l u s t e r i n gm e t h o d ，简称c d b s s c ) ，它将两种方法进行了统一。如文献【1 4 【1 5 】 就是典型的混合方法。 在半监督聚类中，一般利用监督信息指导聚类过程，通常监督信息有如下两种形式： 带类标签的样本数据和成对约束信息。相对来说获得成对约束信息要更容易，而且带类 标签的样本可以转换为成对约束。 半监督聚类已经被广泛的运用到网页检索和文本分类、基于生物特征的身份识别、 图像检索和视频检索，医学数据等一系列活动中。在研究人员的不断努力下，半监督聚 类在理论和实际研究应用中都获得了长足的发展。 2 第一章引言 目前半监督聚类的研究正在继续从广度和深度上不断进行扩展【1 6 l 。不断有各种传统 的或新提出的半监督聚类的改进算法出现，同时也有新的数学方法不断的引进半监督聚 类中。半监督聚类探讨的对象已经由简单的数据结构扩展到流形结构，半监督数据和图 模型的关系等。换而言之，半监督聚类已经和当前机器学习研究的热点和重点问题紧密 联系在一起了。 半监督聚类的理论在未来一段时间内仍将是机器学习研究的重点和热点。这些研究 对于我们理解机器学习的机理以及人机交互都具有重要的理论意义。 1 2 研究意义和目标 半监督聚类融合了无监督和有监督聚类的各自优点，通过较小的代价，如利用成对 约束信息指导聚类，使获得更好的聚类效果。半监督聚类势必成为聚类研究的热点，新 的理论会不断涌现出来，将科技成果转化到实际生产中，降低生产投资成本，提高经济 效益。 在半监督聚类中，一些已经提出的算法已经取得了不错的分类效果。我们的目标是 对算法进行改进，不降低分类效果，同时可以提高算法的运行速度。在改进微分进化算 法的半监督模糊聚类中，参照传统f c m 和进化算法，添加粒子群惯性权重思想。算法前 期不影响种群的多样性，而在后期加快了收敛速度。很好的达到了上述目的。在半监督 聚类中，怎样才能更好的利用监督信息，在这方面的研究人员各抒己见，出现了大量的 方法，都获得了不错的效果。我们在前人研究的成果上，首先利用约束对之间隐含的关 系，扩大约束对数量，再利用扩大的监督信息对原始样本进行投影，最后利用基于成对 约束的k m e a n s 算法去聚类，实验结果表明可以提高聚类性能。 1 3 论文章节安排 本文共分为5 章，章节安排如下： 第一章为引言部分，首先介绍了数据挖掘的概念，然后讲述了聚类分析与数据挖掘 的关系，最后提出半监督聚类，并给出了常用半监督聚类研究思路和方法。 第二章首先介绍了聚类的分类和度量方法，并相应的进行了简单的介绍。接着我们 给出了半监督聚类的一些典型算法，最后对半监督聚类算法最近的研究成果作简单的回 顾。 第三章首先介绍了模糊集的一些基本知识，并给出了模糊c 均值算法的一般步骤， 然后给出了进化算法的基本原理和实现步骤。在两者的基础之上我们提出了改进微分进 化算法的半监督模糊聚类，并对该算法进行详细的介绍，最后在遥感图像等数据集进行 实验，进行详细的分析。 第四章首先介绍一种如何通过成对约束内部之间的关系扩大成对约束量，然后利用 监督信息进行降维。在不违反成对约束的基础上提出一种改进的半监督聚类算法。在 u c i 数据集中进行验证算法的可行性。 3 江南大学硕士学位论文 第五章为全文的总结，对研究中存在的问题和不足加以说明，对本文所取得的成果 进行了分析，并对进一步的研究做了展望。 4 第二章半监督聚类算法分析 第二章半监督聚类算法分析 在数据挖掘和机器学习领域内，半监督聚类这个研究课题已经引起了研究人员的广 泛的关注，半监督聚类的目的在于利用先验知识对样本获得一个更好的分类。半监督聚 类优越性在于融合了无监督聚类和有监督分类两者的优点。所以在介绍半监督聚类之前 我们先简单回顾一下聚类知识，同时介绍几种常用聚类算法。 2 1 聚类分类以及常用度量方法 2 1 1 聚类的类别 在这里我们给出e v e r i t t 1 7 l 在1 9 7 4 年关于聚类所下的定义：一个类簇内的实体是相 似的，不同的类簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一类簇的任 意两个点间的距离小于不同类簇的任意两个点间的距离；类簇可以描述为一个包含密度 相对高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其 他区域( 类簇) 相分离。 事实上，聚类是一个无监督的分类，它没有任何先验知识可用。聚类分析的输入可 以用一组有序数对( x ，s ) 或( x ，d ) 表示，这里x 表示一组样本，s 和d 分别是度量样本 间相识度或相异度( 距离) 的标准。聚类系统的输出是一个分区a = g 1 ，g 2 ，g ，其 中，q ( 七= 1 ，) 是x 的子集，如下所示： g 1ug 2u u g r = x ( 2 1 ) qn g = ，i s ， ( 2 2 ) a 中成员g 1 ，g 2 ，g 叫做类，每一个类都是通过一些特征描述的。在基于搜索的 聚类中，聚类分析的结果是类( x 中的单独的点集) 和它的特征或描述。 在图2 1 中，我们将给出不同类型聚类算法的分类。聚类算法可分为层次方法与划 分方法两大类。所谓层次聚类是指产生一个嵌套的簇集。在层次体系中，每一层都有一 些分开的簇。在最底层，每一个元组都组成一个单独的簇。在最高层，所有的元组都属 于同一簇集。在层次聚类中，不必输入簇的数目。所谓划分聚类是指利用算法构造一个 簇集，其中簇的数目由用户指定或系统指定。传统的聚类算法为了满足内存要求，一般 都是针对数值型的小型数据库设计的。为了满足内存约束，这些针对大型数据库设计的 算法要么采取对数据进行抽样，要么利用数据机构来压缩或修剪数据库。基于是否产生 重叠或非重叠的簇，可得到不同的聚类算法。但即使只考虑非重叠的簇，也有可能将一 个元组放置到不同的簇中。非重叠聚簇类算法可分为外部的和内部的。外部算法使用元 组的标签来辅助分类过程。事实上，这些算法就是传统的有指导学习分类算法，使用这 些算法要用到特殊的输入训练集。内部算法不需要任何先验信息，而只取决于包含元组 之间距离的邻接矩阵。 江南大学硕士学位论文 图2 - 1 聚类算法的分类 f i g 2 - 1t y p e so fc l u s t e r i n ga l g o r i t h m 层次聚类算法实际上是产生嵌套的聚集，根据产生聚集的方式不同，可以分为凝聚 算法和分裂算法。 凝聚算法在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把 那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。不同的层次算法在 每一层合并簇的方式也不同。算法2 1 给出了一个典型的凝聚聚类算法。 算法2 1 输入： d = ，f 2 ，厶) ，成员集合 彳 表示成员之间距离的邻接矩阵 输出： d e i i 以有序三元组形式表示的谱系图 凝聚算法： d = 0 ： k = 刀： k = ，饥) ) ； d e = d ，k ，k ) ) ；在初始谱系图中，每一个成员均为一个单独的簇。 r e p e a t o l d k = k ； d = d + 1 ； a d = v e r t e xa d j a c e n c ym a t r i xf o rg r a p h w i t ht h r e s h o l dd i s t a n c eo fd ； ( 七，k ) = n e w c l u s t e r s ( d d ，d ) ； i fo l d k kt h e n d e = d e u ( d ，k ，k ) ；新簇集加入谱系图中 u n t i lk = 1 6 第二章半监督聚类算法分析 算法2 1 调用一个称为n e w c l u s t e r s 的过程来决定如何从前一个层次的簇合并产生 下一个层次的簇。不同类型的凝聚算法具有不同的n e w c l u s t e r s 过程。n e w c l u s t e r s 过程 可能之合并了两个簇，也可能合并了多个簇。当几个簇之间具有相等的距离是，不同的 算法会采用不同的合并策略。另外，计算簇之间距离的方式也可能发生变化。 分裂聚类在初始使所有元组都属于同一个簇，然后将上层的簇重复分裂为两个下层 簇，直到每一个元组都组成一个单独的簇为止。其主要思想是将那些成员之间不是非常 紧密的簇进行分裂。 划分聚类或非层次在一步中就产生所有的簇，而不需要几个步骤。虽然在各种算法 中，可以在算法内部产生几个不同的簇集，但划分聚类的结果只产生一个簇集。由于仅 有一个簇集作为输出，所有用户必须输入期望得到的簇的数目k 。另外还需要度量函数 或准则函数来判定所给出的解的优劣程度。在准则函数意义下，具有最优值的解作为最 终的聚类结果。常用的度量是平方误差度量，它表示簇中每一点到簇的质心的距离平方 的和： 量 如( q ，f 。，) 2 ( 2 3 ) m = l e k m 还有一些相关的度量方法我们将在后面一一讲解。 基于划分算法的聚类常用的算法有最小生成树、平方误差聚类算法、k 均值聚类、 最近邻算法、p a m 算法、结合能量算法、基于遗传算法的聚类、基于神经网络的聚类 等，限于篇幅就不一一介绍了。 前面提到的都是一些传统的聚类技术。当在动态数据库上进行聚类时，这些算法可 能并不合适。首先这些技术都假设要有足够的主存( 因为大多数算法的复杂性都是 o ( n 2 ) ) ，用于存储要聚类的数据及相应的数据结构。由于大型数据库包含了成千上万个 元组( 或更多) ，因此这些假设是不现实的，另外，在算法的多次迭代中，不断地进行 i o 操作也要付出很大的代价。但由于主存的限制，这些算法都不能扩展到大型数据库 上去。另一个问题是有些聚类技术还假设所有数据是一次提供的。对于动态数据库而言， 这个假设也不是现实的。b i r c h 算法、d b s c a n 算法以及c u r e 算法很好解决了上述 问题。这里我们将详述讨论b i r c h 算澍2 1 。 b i r c h 是一个综合的层次聚类方法。它引入两个概念：聚类特征( c f ) 和聚类特 征树( c f 树) ，它们用于概括聚类描述，这些结构辅助聚类方法在大型数据库中取得较 高的速度和伸缩性。 ( 1 ) 聚类特征c f 一个聚类特征c f 是一个三元组，给出对象子聚类信息的汇总描述。假设某个子聚 类中有个d 维的点或对象 q 。则该子聚类的聚类特征c f 定义如下： c f = ( ，l s ，s s ) ( 2 4 ) 7 江南大学硕士学位论文 其中n 是子类中点的个数，l s 是个点的线性和( 即q ) ，嬲是数据点的平方 i - i ， 和( y d 2 ) 。 一 i = l ( 2 ) c f 树 一棵c f 树存储了层层叠叠聚类的聚类特征，它是一个有两个参数的高度平衡树： 分支因子b 和阈值工，分支因子定义了每个非叶节点孩子的最大数目，而阈值参数给出 了存储在树的叶子节点中聚类的最大直径，这两个参数会直接影响结果树大小。 定义2 1 在一个有刀个节点的聚类中，这刀个节点分别为d 1 ，0 2 ，q ，则该 聚类的直径d 定义为： ih l ( q q ) 2 肚i 坐n 杀矿 il 刀一1 ) d 代表一个聚类中每一对节点之间的平均距离。 每个非叶子节点形式为：【c f , ，幽f 磁】，其中扛1 , 2 ，b ，c h i t d ，是一个指向它的第i 个子节点的指针，而c f , 是该子节点所代表的子聚类的c f 条目。因此，一个非叶子节 点代表一个由它个条目所代表的所代表子聚类组成的聚类。另外，为了限制叶子节点的 大小，设置一个阈值三，确保每个叶子节点最多含有三个条目，每一个叶子节点条目的 形式为 c f , 】，f - 1 , 2 ，l ，c f , 是它的第i 个子聚类的c f 。与此同时，为了提高查询速 度，每一个叶节点均设置两个指针，p r e v 和n e x t ，用于连接所有的叶节点。一个叶节点 也代表一个由它的各条目所代表的子聚类组成的聚类。图2 2 表示了一个c f 树的最后 两层示意描述。 c fl + c f 2 + c f 3c f 4 + c f 5 c f 3 目c f 4 邙5 e 二 c f lc f 2 图2 - 2c f 树结构 f i g 2 - 2s t r u c t u r eo fc ft r e e 最后第二层 后第一层 b i r c h 算法包括以下两个阶段： 第一阶段：扫描数据库，建立一个初始存放内存的c f 树，它可以被认为是数据的 多层压缩，试图保留数据内在的聚类结构。 8 第二章半监督聚类算法分析 第二阶段：采用某个聚类算法对c f 树的叶节点进行聚类。 在第一阶段中c f 树是根据不断插入的对象而动态建立的，因此，b i r c h 算法是一 种增式聚类方法，一个对象被插入到与它最近的叶子节点中。若一个叶节点的子聚类直 径在插入一个新对象后大于阈值工，那么该叶子节点和其他叶子节点就要进行分解，而 在插入一个新对象后，有关它的信息将向着树根传递。通过修改阈值可以改变c f 树 的大小。如果存放c f 树所需要的内存大于现有的内存，那么指定较小的阈值三并重建 c f 树，并通过重新将旧树的叶条目插入到新的c f 树中，重建更小的c f 树，在所有的 旧叶条目重新插入后，数据扫描( 插入到新树) 从中断电得到恢复。这样重建树的过程 不需要重读所有对象。这一点与构造矿树时的插入与分解过程相类似。 在b i r c h 算法的第二阶段，可利用任何聚类算法发，一般使用划分聚类方法，对 第一阶段所获得的c f 树进行聚类分析。 b i r c h 算法努力在现有资源条件下产生最好的聚类。面对有限的内存，一个重要 的忧虑就是如何使得i o 时间最小。b i r c h 算法利用多阶段处理方式? 扫描一遍数据集 获得一个基本理想的聚类，再次扫描一遍数据集以帮助改善聚类的质量。由此可见， b i r c h 算法的时间复杂度为d ( 刀) ，其中行是待聚类的对象数。 有关的实验结果表明，就数据对象的聚类的质量而言，b i r c h 算法表现出线性可 扩展性。然而由于大小的限制，c f 树中的每个节点仅能容纳有限的入口，因此一个c f 树节点并不总是能对应用户认为的一个自然聚类。此外如果聚类不是球状，则会由于 b i r c h 算法是利用直径来控制一个聚类直径，从而导致算法的性能变差。 在以下的章节里，我们还会挑选一些算法进行介绍。 2 1 2 相似性和距离度量以及异常点 在样本空间x 的聚类算法中，用一个数据向量表示一个样本x ( 或特征向量) 。大 多数待聚类的数据样本实用有限元的向量形式，没有必要区别对象或者说样本x j 以及相 应的向量。因此，我们假定每一个样本x i x ，扛l ，挖都用向量t = x i l 以2 ， 来 表示，聊的值表示样本的维数( 特征) ，刀是一个聚类过程的样本空间x 中的样本数。 相似度是定义一个聚类的基础，所以同一特征空间中的两个模式的相似度的度量标 准对大多数聚类算法都是必不可少的。因为一个聚类分析过程的质量取决于对度量标准 的选择，所以必须仔细选取度量的标准。一般地，不是计算两个样本间的相似度，而是 用特征空间中的距离作为度量标准来计算两个样本间的相异度。对于某个样本空间来 说，距离的度量标准是度量的( m e t r i c ) 或是半度量的( q u a s i m e t r i c ) ，以便用来量化样 本的相异度【l j 。 聚类中的“相异度 这个词意味着当x 和x 是两个相似样本时，s ( x ，x ) 的取值是很 大的，当x 和x 不相似时，s ( x ，x ) 的取值是很小的。而且，相似度的度量标准s 具有自 反性： s ( x ，x ) = s ( x ，x ) ，v x ，x x ( 2 5 ) 对于大多数聚类方法，相似度的度量标准可以标准化为： 9 江南大学硕士学位论文 0 s ( x ，x ) 1 ，v x ，x x ( 2 6 ) 通常，使用相异度的度量而不是相似度的度量作为标准。相异度的度量标准用 d ( x ，x ) ，v x ，x x 来表示。通常称相异度为距离。当x 和x 相似时，距离d ( x ，x ) 很小， 如果x 和x 不相似，d ( x ，x ) 就很大。不失一般性，我们规定： d ( x ，x ) o ，v x ，x 。x ( 2 7 ) 距离的度量标准也具有对称性： d ( x ，x 。) = d ( x ，x ) ，v x ，x 。x ( 2 8 ) 如果这是一个距离度量标准( m e t r i cd i s t a n c em e a s u r e ) 。那么需满足下面的三角不等 式： d ( x ，x 。) d ( x ，x 。) + d ( x ，x ”) ，v x ，x ，x 。x ( 2 9 ) 最著名的距离度量标准是m 维特征空间的欧式距离： a 2 c x , ，_ ) = ( ( 一啄) 2 ) u 2 ( 2 1 0 ) k = l 另外一种经常用的距离度量标准是厶距离或城边距离( c i t yb l o c k ) ： 盔( 而，o ) = e i x , , - x , i ( 2 1 1 ) k = l 最后，明考斯基距离是包括欧式距离和城区距离的特例 a , c x , ，巧) = ( ( 一靠) ，) ， ( 2 1 2 ) k = l 一般地，根据样本之间的一个距离度量标准，可以确定类( 样本集) 间的距离度量 标准，这些度量标准对评价一个聚类过程的质量是必不可少的。因此，它们也是聚类算 法的一个组成部分，广泛应用于类g 和c ，的距离度量标准是： ( 1 ) 珑i n ( e ，c j ) = m i np i p j i其中易g 和p q ( 2 1 3 ) ( 2 ) 见。册( q ，q ) = h m l其中m ，和研j 是c i 和q 的质心 ( 2 1 4 ) ( 3 ) ( c ，q ) = 1 ( 吩) b 一所i 其中只c f 和p q ，且吩和乃是类c f 和 c 。间的样本数 ( 2 1 5 ) ( 4 ) d i 嗽( g ，q ) = m a x l p ，一p l 其中p i e 和p ，q ( 2 1 6 ) 在聚类过程中，通常会遇到异常点问题。所谓的异常点是指数据集中与其他的点显 著不同的样本点。异常点可能说明数据中存在错误，异常点也可能是一些正确的数据值， 知不是这些数值与其他数据相比，非常不同。 当存在异常点时，许多聚类技术的效果都不理想，为了保证聚类效果，聚类算法可 以发现并剔除异常点。但在实际剔除异常点时一定要谨慎。例如数据挖掘问题是水灾预 报。与正常水位值相比，非常高的水位值很少发生，因此可视为异常点。但如果剔除异 常点，则数据挖掘算法就不能有效地预报水灾，这是因为反映水灾即将发生的数据已经 被剔除了。 1 0 第二章半监督聚类算法分析 异常点检测或异常点挖掘是指在数据集中标示出异常点的过程。发现异常点后，利 用聚类或者其他数据挖掘算法可以剔除它们或者按不同方式处理。许多异常点检测是基 于统计技术的。通常假设数据集服从一个已知分布，然后通过总所周知的不一致检测来 检测出异常点。但是由于现实世界数据集不一定服从简单的数据分布，所以这种方法对 于真实数据是不适用的。另外，大多数统计检验都假设使用单属性数值，而现实世界数 据集中的数据都是多属性的。采用基于距离测度的检测技术可能是一条可行的途径。 2 2 支持向量机简介 聚类是一种无教师的过程，即无监督的方法。在这里我们将介绍有监督的方法。我 们这里主要讨论的是支持向量机( s u p p o r tv e c t o rm a c h i n e ，即s v m ) 。 s v m 由v a p n i k 首先提出的，是一种通用的前馈神经网络，可用于解决模式分类和 非线性映射问题【1 礓1 8 】。从线性可分模式分类角度看，支持向量机的主要思想是建立一个 最优决策超平面，使得该平面两侧平面最近的两类样本之间的距离最大化，从而对分类 问题提供良好的泛化能力。对于非线性可分模式分类问题，可将复杂的模式分类问题非 线性地投射到高维特征空间可能是线性可分的，因此只要变化是非线性的且特征空间的 维数足够高，则原始模式空间能变换为一个新的高维特征空间，是的在特征空间中模式 以较高的概率为线性可分的。此时，应用支持向量机算法在特征空间建立超平面，即可 解决非线性可分的模式识别问题。支持向量机是基于统计学习理论的原理性方法。 考虑p 个线性可分样本 ( x 1 ，d 1 ) ，( 彳27 d 2 ) ，( x pd 尸) ，对于任一输入样本x p ，其 期望输出为d p = l ，分别代表两类的类别标示。用于分类的超平面方程为 w r x + b = 0 ( 2 1 7 ) 式中，x 为输入向量，矿为权值向量，b 为偏置，相当于负阈值，则有 j 形7 x p + b 0 ，当d ，= + 1， 1 渺r x p + 6 o ，当d j p = 一1 j 叫 由公式( 2 1 7 ) 定义的超平面与最近的样本点之间的间隔称为分离边缘，用p 表示。 支持向量机的目标是找到一个分离边缘最大的超平面，即最优超平面。图2 3 给出了二 维平面中最优超平面的示意图。可以看出，左右超平面能够提供两类之间最大可能的分 离，因此确定最优超平面的权值矾和偏置b 0 应是唯一的。公式( 2 1 7 ) 定义的一簇超平 面中，最优平面的方程应该为 形r + 6 0 = 0 ( 2 1 9 ) 江南大学硕士学位论文 - - 一- 一 最优超平面 l s p a c e 。f p 。沁。e ；n p 懂。x w x + 6 = 。 图2 - 3 最优分类超平面 f i g 2 - 3t h em a x i m i z eh y p e r p l a n e 由解析集合知识可得样本空间任一点到最优超平面的距离为 r ：w o r x + b o。 慨4 从而有判别函数 g ( x ) = 1 l w o l l = w d x + b o 给出从x 到最优超平面的距离的一种代数度量。 将判别函数进行归一化，使所有样本都满足 ( 2 2 0 ) ( 2 2 1 ) w w o r r x l ，p p + b o f 1 耋! ：= + 1 p ：1 ，2 ，p( 2 2 2 ) i 矽了x 尸+ b o 1 ， 当d p ：一1 一1 二，k 厶z z j 则对于离最优超平面最近的特殊样本彳满足i g ( x ) 卜l ，称为支持向量。由于支持 向量最靠近分类决策面，是最难分的数据点，因此这些向量在支持向量机的运行中起着 d p ( r v r x ，+ 6 ) 1 p = 1 ，2 ，p( 2 2 3 ) 厂2 甜= 磊1 = 一 泣 p 2 2 y 2 丽 2 2 5 ) 1 2 第二章半监督聚类算法分析 上式表明，分离边缘最大化等价于使权值向量- 一- ， ，一0 w i i 最小化。因此，满足公式 ( 2 2 5 ) 的条件且使0 矽0 最小的分类超平面就是最优超平面。 根据上面的讨论，建立最优分类面的问题可以表示成如下的约束优化问题，即对于 给定的训练样本p ( x 1 ，d 1 ) ，( x 2d 2 ) ，( z pd 尸) ) ，找到权值向量w 和阈值丁的最优值。 使其在公式( 2 2 3 ) 的约束下，最小化代价函数 ( 形) = 寺0 8 2 = 去形r w ( 2 2 6 ) 这个代价函数是矿的凸函数，且关于缈的约束条件是线性的，因此可以用l a g r a n g e 系数方法解决约束最优化问题。引入l a g r a n g e 函数如下： l ( w ，b , a ) = 去形7 w 一a p 【d p ( 形r x p + 6 ) 一1 】 ( 2 2 7 ) 式中a 。0 ，p = 1 , 2 ，p 称为l a g r a n g e 系数。式( 2 2 7 ) 中第一项为代价函数，第二项 非负，因此最小化西( 形) 就转化为求l a g r a n g e 函数的最小值。观察l a g r a n g e 函数可以看 出，欲使函数值最小化，应该第一项( 形) 较小，第二项较大。为了使第一项最小化， 将( 2 2 7 ) 对形和b 求偏导，并使结果为0 。 i 丝( 兰! 型：0 a 肜 ( 2 2 8 ) l o l ( w , b , a ) ：0 利用公式( 2 2 7 ) 和公式( 2 2 8 ) ，经过整理可导出最优化条件1 ： p w = a 。d p x p j 一， p = l 同时可以得出最优化条件2 ： p d p = o ( 2 2 9 ) ( 2 3 0 ) 为了使第二项最大化，将式( 2 2 7 ) 展开如下： 1ppp 三( 矿，6 ，口) = 去矽r w 一a p d p w7 x p 一6 a p d p + ( 2 3 1 ) j p = lp = lp = 1 根据式( 2 3 0 ) ，上式中第三项为0 ，根据式( 2 2 9 ) 可将上式最终表示为 ppp w