（计算机应用技术专业论文）基于商空间粒度的覆盖聚类算法.pdf

摘要 摘要 随着信息技术的高速发展，数据库应用的规模、范围和深度的不断扩大，导 致积累了大量的数据，而这些激增的数据后面隐藏着许多重要的信息，人们希望 能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可 以高效、方便地实现数据的录入、查询、统计等功能，但是无法发现数据中存在 的各种关系和规则，更无法根据现有的数据预测未来的发展趋势。而数据聚类分 析正是解决这一问题的有效途径，它是数据挖掘的重要组成部分，用于发现在数 据库中未知的对象类，为数据挖掘提供有力的支持，它是近年来广为研究的问题 之一。 聚类分析技术就是将数据区分为自然的群体，并给出每个群体特征描述的 一种数据挖掘方法。但是传统的聚类算法对高维大规模数据的处理效率不高， 我们研究的工作是希望对大规模，高维的数据库找到一种高效的聚类方法，张 铃教授提出的交叉覆盖算法可以有效地处理大规模数据的聚类问题，因此我们 提出基于覆盖算法的聚类。同时我们注意到可以用粒度描述聚类的粗细，因此 本文在聚类中引入粒度的概念 本文首先从基本概念出发，阐明了数据挖掘技术及其中的聚类分析技术的 主要概念和主要内容，之后对聚类分析算法的相关部分( 如聚类分析中的数据 表示、距离度量和常用算法) 进行了深入的分析和讨论。接着介绍了覆盖算法 的基本思想，给出了商空间粒度的基本原理，提出了基于商空间粒度的覆盖聚 类算法，并通过实验验证了该算法的有效性和可行性，适合处理高维大规模的 数据样本。进而，针对文本聚类中由于缺少类信息从而很难直接应用有监督的 特征选择方法这样的局限，提出了一种基于类信息的特征选择算法，此算法在密 度聚类算法的聚类结果上使用信息增益特征选择法重新选择最有分类能力的特 征，实验证明了算法的可行性。 论文所做的工作如下： ( 1 ) 提出了一种可以有效处理大规模高维数据的覆盖聚类算法，此方法在研 究传统的聚类算法基础上，扩展了在数据分类上得到良好应用的交叉覆盖算法， 基于商空间粒度的覆盖聚类算法 提出了改进的覆盖聚类算法，使其能够处理数据的自动聚类问题。 ( 2 ) 引入了粒度的概念，选择不同粒度计算时，可以直观地从不同角度理解 样本类内和类间的物理意义，对问题有实际的指导意义。 ( 3 ) 文本聚类属于无监督的学习方法，由于缺乏类信息还很难直接应用有监 督的特征选择方法，本文提出了一种基于类信息的特征选择算法，很好的利用 了无监督学习方法中的信息增益特征选择法。 本文在粒度聚类方面完成了一定的工作，但还存在一些不足，今后可以在 以下方面继续研究： ( 1 ) 算法的有效性 ( 2 ) 算法的伸缩性 ( 3 ) 算法的系统交互性 关键词：聚类分析；覆盖算法；商空间；粒度 i i a b s t r a c t a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n f o r m a t i o nt e c h n o l o g y , t h ed a t ab a s e a p p l i c a t i o nh a sb e e ne n l a r g i n gi nt e r mo fd i m e n s i o n ，a r e aa n dd e p t h ，a n dt h i sw i l l l e a dt ot h ea c c u m u l a t i o no fal a r g en u m b e ro fd a t a , b e h i n dw h i c hm u c hi m p o r t a n t i n f o r m a t i o ni sh i d d e n h i g h e rl e v e la n a l y s i sh a sb e e ne x p e c t e d , s ot h a tt h e s ed a t ac a n b eb e r e ru s e d t h ec u r r e n td a t as y s t e mc a ne f f e c t i v e l ya n dc o n v e n i e n t l yr e a l i z e m a n yf u n c t i o n ss u c ha si n p u t , q u e r y , s t a t i s t i ce r e ，b u tv a r i o u sr e l a t i o n sa n dr u l e s b e t w e e nd a t ac a nn o tb ee x p l o r e d ，l e ta l o n et h ef u t u r et r e n df o r e c a s to ft h ec u r r e n t d a t a d a t ac l u s t e r i n ga n a l y s i s ( d c a ) i so n ee f f e c t i v ew a yt os o l v et h i sp r o b l e m ，a n d i ti sa l s oo n ei m p o r t a n tp a r to fd a t am i n i n g t h ec l a s so fu n k n o w no b j e c tc a nb e d i s c o v e r e db ym e a n so f d c a , w h i c hp r o v i d e d p o w e r f u ls u p p o r tt od a t am i n i n g ，a n d i th a sb e e nw i d e l yr e s e a r c h e di nr e c e n ty e a r s i nd a t ac l u s t e r i n ga n a l y s i st e c h n o l o g y , t h ed a t ah a sb e e nd i v i d e di n t on a t u r a l c o l o n y , a n de a c hc o l o n yc h a r a c t e r i s t i cd e s c r i b e so n ed a t am i n i n gm e t h o d t h i si s t h eb a s i cw a yo fd 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 i n g , b u tt h et r a d i t i o n a l c l u s t e r i n ga l g o r i t h m sc a nn o te f f i c i e n t l yh a n d l eal a r g en u m b e ro fd a t a w ef o c u so n f i n d i n go n eh i 曲- e f f i c i e n tm e t h o dt o d e a l w i t ht h e s el a r g en u m b e ro fa n dh i g h d i m e n s i o n a ld a t ab a s e o n ec r o s s c o v e ra l g o r i t h mh a sb e e nd e v e l o p e dt oe f f e c t i v e l y c o p ew i t ht h el a r g e s c a l ed a t ac l u s t e r i n gp r o b l e m ，i nt h em e a nt i m e ，w er e a l i z e dt h a t t h et h i c k n e s so fc l u s t e r i n gc a nb ed e s c r i b e db yg r a n u l a r i t y , i nt h i st h e s i s ，t h e g r a n u l a r i t yc o n c e p ti si n t r o d u c e di n t oc l u s t e r i n gb a s e do nt h ec r o s s - c o v e ra l g o r i t h m f i r s t l y , d a t am i n i n gt e c h n o l o g yi n c l u d i n gt h ed e t a i l e d i n f o r m a t i o na b o u t c l u s t e r i n ga n a l y s i sh a db e e np r e s e n t e d ，a n dt h er e l a t i v ep a r t so fc l u s t e r i n ga n a l y s i s a l g o r i t h ms u c ha sd a t ae x p r e s s ，d i s t a n c ec a l c u l a t i o na n dc o m m o na l g o r i t h m sh a d b e e nd i s c u s s e d ；s e c o n d l y , t h eb a s i ci d e ao f c r o s s c o v e i a l g o r i t h ma n d q u o t i e n ts p a c e g r a n u l a r i t yi si n t r o d u c e da n do n ec o v e rc l u s t e r i n ga l g o r i t h mo nt h eb a s i so fq u o t i e n t s p a c eg r a n u l a r i t y i sp r e s e n t e d ，t h es i m u l a t i o nr e s u l t ss h o wt h ee f f e c t i v e n e s sa n d i i i 基于商空间粒度的覆盖聚类算法 f e a s i b i l i t yo ft h i sa l g o r i t h mi nd e a l i n gw i t hh i g h d i m e n s i o n a la n dl a r g e s c a l ed a t a s a m p l e s l a s t l y , t h es u p e r v i s e dc h a r a c t e r i s t i cs e l e c t i o nm e t h o d sc a l ln o tb ed i r e c t l y a p p l i e dt ot e x tc l u s t e r i n gb e c a u s eo ft h el a c ki nc l a s si n f o r m a t i o n , o n ec h a r a c t e r i s t i c s e l e c t i o nm e t h o db a s e do nc l a s si n f o r m a t i o ni s p r e s e n t e d , i n f o r m a t i o ng a i n c h a r a c t e r i s t i cs e l e c t i o nm e t h o di su s e di nt h er e s u l t so fd e n s i t yc l u s t e r i n ga l g o r i t h m t or e c h o o s et h e s em o r ec o m p e t i t i v ec l a s si n f o r m a t i o nc h a r a c t e r i s t i c s ，a n dt h e e x p e r i m e n t sr e s u l t sa p p r o v e dt h ef e a s i b i l i t yo f t h i sm e t h o d t h es u m m a r yo f w o r k ： ( 1 ) o n ec o v e rc l u s t e r i n ga l g o r i t h mw h i c hc a l ld e a lw i t hl a r g e - s c a l eh i g h d i m e n s i o n a ld a t aw a sp r o p o s e di nt h i st h e s i s ，i ti sb a s e do nt h et 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 ma n dt h ec r o s sc o v e ra l g o r i t h mw h i c hh a se x c e l l e n tp e r f o r m a n c eo nd a t a c l a s s i f i c a t i o nh a sb e e ne x t e n d e d , t h u st h ei m p r o v e dc o v e rc l u s t e r i n ga l g o r i t h mw a s g e n e r a t e dt oh a n d l ew i t ht h ea u t o m a t i cc l u s t e r i n gp r o b l e mo fd a t a ( 2 ) t h ec o n c e p to fg r a n u l a r i t yw a si n t r o d u c e d , w h i l et h ed i f f e r e n tg r a n u l a r i t y a r ec h o s e ni nc a l c u l a t i o n ，t h ep h y s i c a lm e a n i n go fw i t h i n c l a s sa n db e t w e e n c l a s s c a l lb ed i r e c t l ys h o w n ，t h a th a sag u i d em e a n i n gt op r a c t i c a la p p l i c a t i o n ( 3 ) t e x tc l u s t e r i n gb e l o n g st ot i n - s u p e r v i s e dl e a r n i n gm e t h o d ，d u et ol a c ko f c l a s si n f o r m a t i o n ，i ti sv e r yd i f f i c u l tt od i r e c t l ya p p l yt h es u p e r v i s e dc h a r a c t e r i s t i c s e l e c t i o nm e t h o d s ，i nt h i st h e s i sac h a r a c t e r i s t i cs e l e c t i o nm e t h o do nt h eb a s i so f c l a s si n f o r m a t i o ni sp r e s e n t e d ，i tg r e a t l ya p p l i e dt h ei n f o r m a t i o ng a i nc h a r a c t e r i s t i c s e l e c t i o nm e t h o do fu n s u p e r v i s e d l e a r n i n g ，t h es i m u l a t i o n r e s u l t s p r o v e d i t s e f f e c t i v e n e s s s o m ew o r kh a sb e e n d o n ei nt e r m so fg r a n u l a r i t yc l u s t e r i n g ，b u ts o m e s h o r t c o m i n g ss t i l le x i s tc u r r e n t l y , al o to f w o r kc a nb ed o n ei nt h ef u t u r e ，s u c ha s ：( 1 ) t h ee f f e c t i v e n e s so ft h ea l g o r i t h m ；( 2 ) t h er e t r a c t i l i t yo ft h ea l g o r i t h m ；( 3 ) t h es y s t e m a l t e r n a t i o na b i l i t yo f t h ea l g o r i t h me t c k e y w o r d s ：c l u s t e r i n ga n a l y s i s ；c o v e ra l g o r i t h m ；q u o t i e n ts p a c e ；g r a n u l a r i t y i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得安徽大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名 孑拍 签字日期：2 0 0 7 年4 月2 0 日 学位论文版权使用授权书 本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权安徽大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以呆用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：琴孰飘导师签名：锻毫寻 签字日期： 20 0 7 年4 月20 由 签字日期： 20 0 7 年4 月2 3 日 q - 位论文作者毕韭去向： 工作单位： 电话： 通讯地址： 邮编： 第一章绪论 1 1 数据挖掘概述 1 1 1 引言 第一章绪论 随着信息技术的高速发展，数据库应用的规模、范围和深度的不断扩大，导 致积累了大量的数据，而这些激增的数据后面隐藏着许多重要的信息，因此人们 希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系 统可以高效、方便地实现数据的录入、查询、统计等功能，但是无法发现数据中 存在的各种关系和规则，更无法根据现有的数据预测未来的发展趋势。在这样的 背景下，人们迫切需要新一代的计算技术和工具来开采数据库中蕴含的宝藏在 市场需求和技术基础都具备的环境下，数据挖掘技术应运而生。聚类分析更是数 据挖掘的重要组成部分，用于发现在数据库中未知的对象类，为数据挖掘提供有 力的支持，它是近年来广为研究的问题之一。聚类分析是一个极富有挑战性的研 究领域，采用基于聚类分析方法的数据挖掘在实践中已取得了较好的效果，目前 己广泛的用于金融投资，模式识别，趋势分析，卫星图象，地理信息系统，信 息检索等领域。它还被应用在气象分析、食品检验、生物种群划分、市场细分、 业绩评估等诸多方面。如在商务上，聚类分析可以帮助市场分析人员从客户基本 库当中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征，聚类分 析还可以应用在欺诈探测中，聚类中的孤立点就可能预示着欺诈行为的存在。 1 1 2 数据挖掘的定义 由于数据挖掘技术是属于多学科交叉领域的研究课题，长期以来，人们从 不同的角度和侧重点对数据挖掘技术进行了不同的定义。j h a n 和m k a m b e r s 从数据库的角度出发，认为数据挖掘就是从数据库、数据仓库或其它 ， ， 信息仓库中存储的大量数据中发现有用的知识的过程。i h w i t t e n 和 e f r a n k s 将数据挖掘定义为从数据中提取固有的，以前不知道的并且潜在有 用信息的过程，这样的观点是以机器学习为基础的。另外，d h a n d ，h m a n n i l a 基于商空间粒度的覆盖聚类算法 和p s m y t h 的数据挖掘的定义是为了找到毋庸置疑的关系而进行的对( 大量) 观测数据的分析，并按易于为用户所理解和使用的方式进行总结数据。显然， 这是从统计学出发的。在此基础上，通过综合各种不同的观点，对数据挖掘技 术渐渐形成了一个比较完整和准确的定义： 定义1 1 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的 实际应用数据中，抽取隐含在其中的、人们事先不知道的、但又是潜在有用的 信息和知识的过程。从更广义的角度来讲，数据挖掘就是在一些事实或观察数 据的集合中寻找模式的决策支持过程。 1 1 3 数据挖掘的一般过程 知识发现2 心( k d d ) 被认为是从数据中发现有用知识的整个过程。数据挖 掘( d m ) 被认为是k d d 过程中的一个特定步骤，它用专门算法从数据中抽取模 式。k d d 过程是交互的，复杂的，包括大量的由用户决策的步骤。b r a c h m a n 给 出了一个业界普遍认可的k d d 的一般过程。如图1 1 所示，为k d d 的一般过程。 ( 1 ) 准备阶段：应用与领域相关的先验知识理解设计开发过程，从用户的 观点认识k d d 的目标。 ( 2 ) 数据选择：根据用户的要求，选取一个数据集或数据子集，k d d 的工 作主要就是在这些数据上进行的； ( 3 ) 数据预处理：对选择产生的数据集进行再加工，检查数据的完整性与 一致性，除去数据中的噪声，对丢失的数据进行填补； ( 4 ) 数据简约：对经过数据预处理的数据，根据知识发现的任务目标，寻 求能表示数据的有用特征，利用属性约简或变换的方法对其操作，以减少数据 量； ( 5 ) 确定数据挖掘方法：根据用户的要求，确定k d d 要挖掘何种类型的知 一识，并根据目标的不同，选择数据挖掘方法( 如关联，分类，回归，聚类等) ， 包括确定合适的算法和参数，并使算法和整个k d d 的评判标准相一致； ( 6 ) 数据挖掘：运用( 5 ) 所选定的知识发现算法，从数据集中搜索用户所 需要的感兴趣的模式，如分类规则，关联规则，回归模型，聚类等； 2 第一章绪论 ( 7 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有兴趣的模式， 这些模式应该具有以下特点：易于被理解，在某种程度上对于新的或测试 数据是有效的，是潜在有用的，是新颖的； ( 8 ) 模式表示：将最终符合条件的模式展现给用户，表示的方法根据所选 择的方法的不同而会有所不同。 为了获得符合评估标准的模式，k d d 过程可能需要重复，这种重复可能需 要在任意几个步骤间进行，甚至需要整个过程的循环。k d d 的关键步骤是数据 挖掘，然而，其他各步骤对k d d 的成功应用具有同样的重要性。 图1 1k d d 的一般过程 f i g 1 1g e n e r a lp r o c e s so fk d d 1 2 聚类分析技术 1 2 1 什么是聚类 聚类【4 ( c l u s t e r i n g ) 就是将数据对象分组成为多个簇( c l u s t e r ) ，使得同一 个簇中的对象之间具有较高的相似性( s i m i l a r i t y ) ，而不同簇中的对象具有较 大的相异性( d i s s i m i l a r i t y ) 。一个好的聚类方法应产生具有如下特性的聚类结 果：簇内的对象高度相似( h i g hi n t r a - c l a s ss i m i l a r i t y ) ，而簇间的对象很少 3 基于商空间粒度的覆盖聚类算法 相似( 1 0 wi n t e r - c l a s ss i m i l a r i t y ) 。 定义1 2 假定一个数据对象由d 个属性( 也称为度量或变量) 描述，则若干 个具有d 个属性的数据对象就构成了d 维数据空间。在d 维空间中，数据对象 被称为d 维数据点，则d 维数据点x 可表示为工= ( x 1 ，硝) ，其中表示第i 个属性值，d 表示空间的维数( d i m e n s i o n a l i t y ) 。 定义1 3 由n 个d 维数据点组成的集合( 又称为d 维数据集) s 可表示为 s = ( 毛，5 。) 其中墨= ( ，) ，且j 。表示第i 个数据点的第j 个属性值。 定义1 4 根据数据点之间的相似性，将d 维数据集v 划分成 c l ，c 2 g ) i 的过程称为聚类分析，其中k d 非线性距离以2 10 s d 圭玉咒 角分离度 铲赫 2 3 2 二值变量的距离度量 对于二值变量，人们提出了各种不同的距离度量方法。对于由二值变量组 成的向量x 与y ，可以通过a ，b ，c 和d ，的值将相异程度表达出赉，其中： a 等于薯= 1 和乃= l 所出现的次数。 b 等于葺= 0 和乃= 1 所出现的次数。 1 4 第二章聚类分析算法 c 等于葺= l 和”= o 所出现的次数。 d 等- p x , = 0 和乃= 0 所出现的次数a 表2 2 对此作出了总结： t a b 2 2v a l u ec h o o s eo f t w ov a r i a b i 鹤 表2 2 二值变量的取值 y ；i。i a u b 0cd 习惯上，为二值变量定义相似度而不是相异度。表2 3 总结了一些对于二 值数据较常用的相似度度量方法 t a b 2 3c o m m o uu s e dt w ov a r i a b l e ss i m i l a r i t yc a l c u l a t i o nm e t h o d s 表2 3 常用的二值变量相似度度量方法 相似度度量数学形式 简单匹配系数 屯= 志 r u s s e l l 和r a o 口+ d + c + 盯 j a c c a r d d + d + c c z e k a n o w s k i 屯= 五再2 e l i 2 4 聚类分析算法分类 聚类分析的算法很多，在实践上，需要根据应用所涉及的数据类型、聚类 的目的以及具体应用要求来选择合适的聚类算法。聚类分析算法可以划分为以 下几大类l l 】： 2 4 1 划分方法( p a r t i t i o n i n gm e t h o d ) 对于一个包含n 个数据对象的数据集，构建k ( k 函 ：i ： ：! i ：i ：! i ：!：i ：分裂几法 图2 7 数据集f a ，b ，c ，d ，e 上的凝聚和分裂层次聚类 f i 9 2 7a g g l o m e r a t i o na n ds p l i th i e r a r c h yc l u s t e r i n go nd a t ab a s e a , b ，c ，d , e ) 分裂方法又称自顶向下的方法，开始时假定所有的对象属于一个组，在每一 步迭代中，根据分裂具有最大相异性的对象的原则，将组分裂为更小的组，直 到每一个组中只包含一个对象或达到终止条件。终止条件可以是簇的数目，或 者是进行分裂的闭值。属于该类方法的聚类算法有a r h p 算法、p d d p 算法、 o p t i g r i d 算法等。 层次方法的缺点是一旦一个步骤( 合并或分裂) 完成，就不能被撤消，即不 能更正错误的步骤。对此，有两种改进方法：1 ) 在每层划分中，仔细分析对象 间的“联接”，如c u r e ，c h a m e l e o n 中的做法；2 ) 综合层次凝聚和迭代的重定位 方法，即首先用自底向上的层次算法，然后用迭代的重定位来改进结果，如b i r c h 中的做法。 2 4 3 基于密度的方法( d e n s i t y b a s e dm e t h o d ) 大多数划分方法是基于对象间距离进行聚类的。这类方法仅能发现圆形或 球状的聚类而较难发现具有任何形状的聚类。基于密度概念的聚类方法实际上 就是不断增长所获得的聚类直到邻近( 数据对象或点) 密度超过一定阈值( 如： 一个聚类中的点数，或一个给定半径内必须包含至少的点数) 为止。这种方法 可以用于消除数据中的噪声( 异常数据) ，以及帮助发现任意形状的聚类。主要 1 7 基于商空间粒度的覆盖聚类算法 分为两种，一种是基于高密度连接区域的聚类，如d b s c a n 算法，o p t i c s 算法， 另一种是基于密度分布函数的聚类，典型算法是d e n c l u e 。 d b s c a n 基本思想是：对于一个类中的每一对象，在其给定半径的领域中包 含的对象数目不小于某一给定的最小数目，缺点是随着数据量的增大，需要有 很大的内存支持与i 0 开销，由于使用了全局参数因此没有考虑密度和类别距 离大小的不均匀性。o p t i c s 算法对数据不同部分采取不同的参数，将数据进行 递增排序便于迭代处理。密度函数算法将研究的重点从样本点密度转移到属性 空间的密度函数，d e n c l u e 将影响函数的和作为密度函数，是前面多个算法的 一般化形式，有较好的扩展性和抗干扰能力，可用于高维数据聚类。 2 4 4 基于网格的方法( g r i d - b a s e dm e t h o d ) 将对象空间划分为有限数目的单元以形成网格结构，所有聚类操作均是在 这一网格结构上进行的。这种方法主要优点就是处理时间由于与数据对象个数 无关而仅与划分对象空间的网格数相关，从而显得相对较快。典型方法有s t i n g ， c l i q u e ，w a v e c l u s t e r 。其共同之处是首先把数据空间划分成一定数目的单元， 以后所有的操作都是对单元进行的。但存在量化的问题，一般来说，划分太粗 糙造成不同聚类的对象被划分到同一单元的可能性增加( 量化不足) ，相反，划 分太细会得到许多小的聚类( 量化过度) 。通常的方法是采用先从小单元开始寻 找聚类，再逐渐增大单元的体积，重复这个过程直到发现满意的聚类为止。 2 4 5 基于模型的方法( m o d e l - b a s e dm e t h o d ) 事先为每个簇假定一个模型( 可以是数据点在空间中的密度分布函数或者 其他) ，然后寻找数据对给定模型的最佳拟和。该方法基于如下假定；目标数据 集是根据潜在的概率分布生成的。该方法主要有两类：统计学方法和神经网络 方法。统计学方法有c o b w e b 算法、c l a s s i 下算法、a u t o c l a s s 算法。神经网络 方法有竞争学习法和自组织特征映射法。 1 8 第二章聚类分析算法 2 4 6 高维数据聚类算法 常用的处理高维数据的聚类方法有降维和子空间聚类( s u b s p a c e c l u s t e r i n g ) 两种途径。降维途径常用方法有：用于多元变量统计的p c a ( p r i n c i p a lc o m p o n e n t sa n a l y s i s ) 和用于信息检索的s v d ( s i n g u l a rv a l u e d e c o m p o s i t i o n ) 两种方法。其中基于子空间途径的常见的算法有： c l i o u e ( c l u s t e r i n gi nq u e s t ) 算法，它是一种结合基于密度和基于栅格的算法， 适用于数值型数据，使用m d l 原则选择子空间。e n c l u s ( e n t r o p y b a s e d c l u s t e r i n g ) 算法是c l i q u e 算法的扩展，使用熵来进行子空间的选择。m a f i a ( m e r g i n go fa d a p t i v ef i n i t ei n t e r v a l s ) 算法对c l i q u e 进行了比较大的扩展， 算法采用对每维数据构造自适应栅格，然后将小的栅格进行合并。o t i g g r i d 算 法，p r o c l u s 算法使用基于递归划分的多维栅格。p r o g c l u s ( p r o j e c t e d c l u s t e r i n g ) 算法将高维数据投影到低维数据。o r c l u s 算法类似p r o g c l u s 算法， 但是采用非轴向的平行的子空间来投影。 2 4 7 海量数据聚类算法 对于解决海量数据的挖掘，可以从3 方面进行考虑： l 首先考虑的是保留现有的算法，尽量把所有数据都放到内存中去，可以 采用增加内存和对数据进行采样的方法。数据挖掘的算法一般要求兼顾准确性 和高效性，要求算法准确性，能够发现复杂的结构，计算出准确的参数，就必 须对大规模的数据集进行计算。而要求算法高效性，则只能对小数据集进行计 算，这显然存在矛盾之处。即便是允许对大规模的数据进行挖掘，现有的基于 内存算法要求把数据全部放入内存，所以很多情况下还是不能处理大规模数据 的问题，增加内存的方式只能缓解问题。在这种情况下通常采用的方法是：使 用采样技术选择数据的一个部分，使得处理的数据量大大减少，而又不影响算 法的准确度。 2 除了数据采样以外，还可以通过修改现有的算法，开发出新的可扩展的 算法或者近似算法来解决海量数据挖掘的问题。而且，即便在使用数据采样技 1 9 基于商空间粒度的覆盖聚类算注 术后，快速算法也是需要的。开发一个快速算法可以从三个方面考虑。 ( a ) 限制模型空间大小。把搜索范围放在一个更简单的空间，可以增加算 法的速度，一个小的搜索空间当然能够更快的得到结果。 ( b ) 发出更有效的启发式搜索方法。当不能减少搜索空间的时候，可以开 发出更有效的启发式搜索方法来加速搜索。 ( c ) 并行计算。由于很多数据挖掘的任务就是分解，所以可以利用并行处 理来完成挖掘。而且很多算法天生就具有并行特征( 如遗传算法) ，采用并行计 算将大大增加处理速度。 3 开发算法的方法是提高算法的可扩展性，着眼点是在“提高”( s c a l eu p ) 方面。而数据转换的途径则可以看为是一种“降低”( s c a l ed m m ) 的途径。这 种降低指的是降低数据的维数和数量。从这个角度来看，数据挤压的途径可以 看作是采样的推广。从原始数据集中产生一个近似数据集，然后让数据挖掘算 法来访问这个数据集，从而避免了处理整个数据。对海量数据的处理，可以基 于在对海量数据的概要数据中进行计算。但是得到海量数据的概要数据必须先 对数据进行挖掘，得到数据模型。数据转换的方法组合数据概要和数据采样的 方法来预处理数据。数据挤压是一种统计思想启发的数据挤压方法。这个方法 产生m 个伪数据点用来模仿原始大数据集的统计结构，即尽可能的逼进似然函 数的结构。 上述部分聚类算法同时属于多个类别，这里将它们分在主要所属的类别中。 此外的一些聚类算法将若干聚类方法的思想结合在一起，因此有时很难明确界 定一个聚类算法究竟属于哪一个聚类方法类别。其他的一些应用也需要将多个 聚类技术结合起来方可实现其应用目标。 本文对聚类各方法的比较研究基于以下5 个标准：1 ) 是否适用于大数据 量，算法的效率要满足数据集的大数据量、高复杂性、高增量的要求；2 ) 是否 能应付不同的数据类型，至少能处理数值属性和符号属性；3 ) 是否能发现不同 类型的聚类；4 ) 是否能应付脏数据或异常数据；5 ) 是否对数据的输入顺序不 敏感。 2 0 第二章聚类分析算法 2 5 常用的聚类分析方法比较 2 5 1 聚类算法的典型要求 在机器学习中，聚类分析属于一种无( 教师) 监督的学习方法。与分类学习 不同，无( 教师) 监督学习不依靠事先确定的数据类别，以及标有数据类别的学 习训练样本集合。正因为如此，聚类分析又是一种观察学习( 1 e a r n i n gb y o b s e r v a t i o n ) 方法，而不是示例学习( 1 e a r n i n gb ye x a m p l e ) 方法。在对概 念进行聚类的方法中，仅当一组对象可以由一个概念所描述时，这些对象才能 构成一个类。这与基于几何距离表示相似程度并进行聚类的传统聚类方法有所 不同。概念聚类方法主要包含两部分内容： ( 1 ) 发现适当的类； ( 2 ) 根据每个类形成相应的特征描述。无论如何最大程度地实现类中对象 相似度最大，类间对象相似度最小是聚类分析的基本指导思想。 聚类分析是一个富有挑战的研究领域，有关每一个应用都提出了一个自己 独特的要求。以下就是对数据挖掘中的聚类分析的一些典型要求： 1 可扩展性。许多聚类算法在小数据集( 少于2 0 0 个数据对象) 时可以工 作很好；一个大数据库可能会包含数以百万计的对象。利用采样方法进行聚类 分析可能得到一个有偏差的结果，这时就需要可扩展的聚类分析算法。 2 处理不同类型属性的能力。许多算法是针对基于区间的数值属性而设计 的。但是有些应用需要对其它类型数据，如：二值类型、符号类型、顺序类型， 或这些数据类型的组合。 3 发现任意形状的聚类。许多聚类算法是根据欧氏距离和m a n h a t t a n 距离 来进行聚类的。基于这类距离的聚类方法一般只能发现具有类似大小和密度的 圆形或球状聚类。而实际上一个聚类是可以具有任意形状的，因此设计出能够 发现任意形状的聚类算法是非常重要的。 一4 需要( 由用户) 决定的输入参数最少。许多聚类算法需要用户输入聚类 分析中所需要的一些参数( 如：期望所获聚类的个数) ，聚类结果通常都与输入 参数密切相关，而这些参数常常也很难决定，特别是包含高维对象的数据集。 这不仅构成了用户的负担，也使得聚类质量难以控制。 2 1 基于商空间粒度的覆盖聚类算法 5 处理噪声数据的能力。大多数现实世界的数据库均包含异常数据、不明 数据、数据丢失和噪声数据，有些聚类算法对这样的数据非常敏感并会导致获 得质量较差的数据。 6 对输入记录顺序不敏感。一些聚类算法对输入数据的顺序敏感，也就是 不同的数据输入顺序会导致获得非常不同的结果。因此设计对输入数据顺序不 敏感的聚类算法也是非常重要的。 7 高维问题。一个数据库或一个数据仓库或许包含若干维或属性。许多聚 类算法在处理低维数据时( 仅包含二到三个维) 时表现很好，然而对高维空间 中的数据对象，特别是对高维空间稀疏和怪异分布的数据对象的处理表现不理 想，能进行较好聚类分析的聚类算法已成为聚类研究中的一项挑战。 8 基于约束的聚类。现实世界中的应用可能需要在各种约束之下进行聚类 分析。假设要在城市中确定一些新加油站的位置，就需要考虑诸如城市中的河 流、高速路以及每个区域的客户需求等约束情况下居民住地的聚类分析。设计 能够发现满足特定约束条件且具有较好聚类质量的聚类算法也是一个重要研究 任务。 9 可解释性和可用。用户往往希望聚类结果是可理解的、可解释的以及可 用的。这就需要聚类分析要与特定的解释和应用联系在一起。 2 5 2 常用聚类算法的比较分析 q b i r c h 算法( 平衡迭代削减聚类法) b i r c h 是一个综合的层次聚类方法。算法的核心是用一个聚类特征三元组 c f 总结了一个簇个体的有关信息，从而使一簇点的表示可以用对应的聚类特征， 而不必用具体的一组点来表示，通过构造满足分支因子和簇直径限制的聚类特 征树来求聚类。描述如下： 对于一个具有n 个d 维数据点的类f x i ) ( i = l ，2 。，n ) ，它的聚类特征向量 定义为： _ c f = ( n ，l s ，s s ) ( 2 1 ) 第二章聚类分析算法 其中n 为类中点的个数；s 表示个点的线性和z ，反映了类的重 i l l n 心，s s 为个点的平方和置2 ，反映了类直径大小。 i e l 此外，对于聚类特征有如下定理。 定理2 1 假设叫= ( l ，三s ，踊) 与c f ：= ( 2 ，工足，鹞) 分别为两个类的 聚类特征，则两个类合并后形成的新类特征为 斗- 1 = _ 巧+ c e = i + 2 + 工s + 工足+ 5 岛 ( 2 2 ) 该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离 的运算。 b i r c h 算法通过一次扫描就可以进行较好的聚类，由此可见，该算法适合 于大型数据库。对于给定的m 兆内存空间，其空间复杂度为o ( m ) ，时间复杂度 为o ( d n b l n b ( m p ) ) ，其中d 为维数，n 为节点数，p 为内存页的大小，b 为 由p 决定的分支因子，i o 花费与数据库成线性关系。但b i r c h 算法只适用于 类的分布呈凸形及球形等情况，并且由于b i r c h 算法需提供正确的聚类个数和 簇直径限制，对不可视的高维数据是不行的。 c u r e 算法【1 9 】( 使用代表点的聚类方法) c u r e 算法采用了一种新颖的层次聚类算法，该算法首先把每个数据点看成 一类，然后再合并距离最近的类直至聚类个数为所要求的个数为止。它对传统 聚类方法中对类的表示方法进行了改进，回避了用所有点或简单地用中心