（计算机软件与理论专业论文）聚类分析的新方法研究.pdf

聚类分析的新力江埘究 摘要 数十年来，数据挖掘一直是一个热门话题。作为数掘挖掘的一个主要技术领 域，聚类分析产生了很多算法，并且演化成一个庞大家族。现有的聚类算法可以 分为5 类：分割算法，分层算法，基于密度算法，基于网格算法，以及基于建模 的算法。也有很多算法是结合了两个或两个以上类别，以获得更好的性能。 在聚类分析的处理过程中，一方面很重要的一个问题是如何对聚类结果进行 解释。用户希望聚类结果是比较容易解释和理解的，也就是如何为用户提供快捷 有效的途径来调节聚类过程得到可理解的结果。为达此目的，两个问题比较关键： 1 ) 如何在聚类结果中包含尽可能多的有用信息，比如密度信息；2 ) 如何不损失 性能的| j 提下找到用户希望的结果。 本文相应的提出了第一个算法s d p h c ：一个新的基于密度的分割和分层的 算法。该算法是一个组合算法。它引入了一个新概念密度权重，可以使得在 聚类中采用人工反馈机制变得比较容易。有了反馈机制，用户就可以根据对数据 的理解来对数据分类，而尽管这些数掘有可能在空间上分的比较散。同时，通过 对参数和聚类结果之问的分析，在参数设置方面引入一个自校技术，它可以节约 用户花在最优参数设置方面的时间。理论分析和实验结果均表明该算法在性能和 聚类质量方面要优于d b s c a n 、p h c 等算法。 另一方面，随着网络、存储、处理器等硬件方面的飞速发展，导致了极为巨 大的数据库的产生，它们记录了数量巨大的高维事务信息。为了应对这种趋势， 同益增长的信息隐私方面的发展要求逐渐为全球所关注，由于数掘挖掘的目的就 是从大规模数掘库中有效的发现不明显但是非常有价值的信息，所以比较容易被 误用【5 】。而个人用户：1 ) 可能不愿暴露自己的特定信息；2 ) 可能不介意给出 部分真实信息；3 ) 可能愿意给出的不是真实的但是经过修改的信息。所有的这 些情况将导致缺失属性的产生。 本文相应的提出了第二个算法c l i n c h ：一个有效的挖掘缺失高维数掘的聚 类算法。c l i n c h 类似于大部分基于网格的算法，包括一个三步的框架，问题的 解决主要在于识别出密集单元，通过逐维处理的方法识别出这些单元的方法。 c l i n c h 在开始的几个维，采用了有效的筛选策略，很多候选被裁剪掉，因此整 体的算法丌销降了下来：随后还采用了一个预测机制来处理缺失数掘的问题。通 复口人学坝l 论卫 5 聚类分析的新方法研究 过实验和复杂度分析，c l i n c h 比c l i q u e 算法要快而且聚类质量基本接近， 而比f i l v ( d b s c a n ) 不但快而且聚类质量要好。 关键词：聚类，缺失数掘，高维数掘，基于密度，基于分层，自校正 中图分类号：t p 3 1 1 复口人学帧f 论文 6 t 聚类分析的新方法州究 a b s t r a c t d a t am i n i n gh a sb e e nah e a t e dt o p i cf o rt h el a s td e c a d ea n ds t i l li s a sap r i m a r y t e c h n i q u ei n t h ee x t r a c t i n go fu s e f u li n f o r m a t i o na n dk n o w l e d g e ，an u m b e ro f a l g o r i t h m s i nc l u s t e ra n a l y s i sh a v eb e e np r o p o s e da n dh a v ee v o l v e di n t oal a r g e f a m i l y e x i s t i n gc l u s t e r i n ga l g o r i t h m sc a nb eg e n e r a l l yc a t e g o r i z e di n t o5c l a s s e s ： p a r t i t i o n i n g ，h i e r a r c h i c a l ，d e n s i t y - b a s e d ，g r i d b a s e d ，a n dm o d e l b a s e d t h e r ea r ea l s o m a n ya l g o r i t h m sc o m b i n i n gt w oo rm o r et e c h n i q u e si nd i f f e r e n tc a t e g o r i e st og a i n b e t t e re f f i c i e n c ya n dq u a l i t y i nt h ep r o c e s so fc l u s t e ra n a l y s i s ，o n ei m p o r t a n tp h a s ei st h ei n t e r p r e t a t i o no f c l u s t e r i n g r e s u l t s u s e r s e x p e c tc l u s t e r i n g r e s u l t st ob e i n t e r p r e t a b l e a n d c o m p r e h e n s i b l e t h e r e f o r e i ti sam a j o ri s s u et od e s c r i b et h ec l u s t e r i n gr e s u l t s p r e c i s e l ya sw e l la st op r o v i d ee a s yw a y sf o ru s e r st oa d j u s tt h ec l u s t e r i n gf o r c o m p r e h e n s i v er e s u l t s t w op r o b l e m sa r et h e r e f o r ei n v o l v e d ：1 1h o wt oi n c l u d ea s m u c ha su s e f u li n f o r m a t i o ni nt h ec l u s t e r i n gr e s u l t s ，e g t h ei n f o r m a t i o no fd e n s i t y ；2 ) h o wt of i n dt h eu s e re x p e c t i n gr e s u l t sw i t h o u tl o s so fe f f i c i e n c y i nt h i sp a p e r , t h ef i r s t a l g o r i t h mw ea c c o r d i n g l yp r o p o s e i sa ni n n o v a t i v e d e n s i t y b a s e dp a r t i t i o n i n ga n dh i e r a r c h i c a la l g o r i t h m t h ea l g o r i t h mi sa ”b l e n d ” a l g o r i t h ml i k ep h c b u ti ti sb a s e do nan e wn o t i o no fd e n s i t y - w e i g h tt h a tm a k e si t e a s y t oa d o p ts y n t h e t i cf e e d b a c km e c h a n i s mi nc l u s t e r i n g w i t ht h ef e e d b a c k c a p a b i l i t y , u s e r sa r ea b l et og r o u p d a t aa c c o r d i n gt ot h e i ru n d e r s t a n d i n go fd a t ae v e ni f t h ed a t ap o i n t sa r ef a ra p a r ti ns p a c e m e a n w h i l e ，b yi n v e s t i g a t i n gi n t ot h er e l a t i o n b e t w e e np a r a m e t e r sa n dt h ec l u s t e r i n gr e s u l t s ，w ei n t r o d u c eas e l f - t u n i n gt e c h n i q u e f o rp a r a m e t e rs e t t i n g ，w h i c hs a v e st h ec o s t l yt i m eu s e r ss p e n di nt h es e t t i n go fo p t i m a l p a r a m e t e r s e x p l o s i v ep r o g r e s si nn e t w o r k i n g ，s t o r a g e ，a n dp r o c e s s o rt e c h n o l o g i e sh a sl e dt od e a l w i t hu l t r al a r g ed a t a b a s e si nd a t am i n i n g ，w h i c hr e c o r dt r e m e n d o u s ，h i g h d i m e n s i o n a l a n dt r a n s a c t i o n a li n f o r m a t i o n i nt a n d e mw i t ht h i st r e n d c o n c e r n sa b o u ti n f o r m a t i o n a l p r i v a c yi nd a t am i n i n gh a v ee m e r g e dg l o b a l l y , f o rd a t am i n i n g ，w i t hi t sp r o m i s et o e f f i c i e n t l y d i s c o v e rv a l u a b l e ，n o n o b v i o u si n f o r m a t i o nf r o ml a r g ed a t a b a s e s ，i s p a r t i c u l a r l yv u l n e r a b l et om i s u s e s p e c i f i c a l l y , ap e r s o n ：1 1m a y n o td i v u l g ea ta ut h e 复口人学帧i 论且 7 ， 聚类分析的新方法”宄 v a l u e so fc e r t a i nf i e l d s ；2 ) m a yn o tm i n dg i v i n gt r u ev a l u e so fc e r t a i nf i e l d s ；3 ) m a y b ew i l l i n gt og i v en o tt r u ev a l u e sb u tm o d i f i e dv a l u e so fc e r t a i nf i e l d s a l lt h e s e s i t u a t i o n sw i l ll e a dt ot h ec r e a t i o no fm i s s i n ga t t r i b u t e s ，i e p r i v a c yc o n c e r n s i nt h i sp a p e r ，t h es e c o n da l g o r i t h mw ea c c o r d i n g l yp r o p o s ei sa ne f f i c i e n tm e t h o dt o c l u s t e ro ni n c o m p l e t eh i g h - d i m e n s i o n a ld a t a w ee m p l o yt h et h r e e - s t e pf r a m e w o r k ， j u s tt h es a m ea sm o s tg r i d b a s e da l g o r i t h m ，i no u rc l u s t e r i n ga l g o r i t h m t h ep r o b l e m i sm a i n l ys o l v e db yi d e n t i f y i n gt h ed e n s eu n i t s o u ra p p r o a c hi d e n t i f i e st h eu n i t sb y p r o c e s s i n gd i m e n s i o nb yd i m e n s i o n t h e r ea r et w oc o n t r i b u t i o n sf r o mt h i sm e t h o d ：d l o t so fp o i n t sa r ep r u n e da f t e rs e v e r a ld i m e n s i o n s ，t h e r e f o r et h et o t a lc o s ti sc u td o w n ； i i 、w ep r o p o s ea l li n n o v a t i v e p r e d i c t i o nm e c h a n i s m t os o l v et h ep r o b l e mo f i n c o m p l e t ed a t a f r o me x p e r i m e n t sa n dc o m p l e x i t ya n a l y s i s ，w ec a ns e et h a t o u r a p p r o a c ho u t p e r f o r m sm a n ye x i s t i n ga p p r o a c h e sw h i l em a i n t a i n i n gar e a s o n a b l e p r e c i s i o n k e y w o r d s ：c l u s t e r i n g ，i n c o m p l e t ed a t a ，h i g h d i m e n s i o n a ld a t a , d e n s i t y b a s e d ， h i e r a r c h i c a l ，s e l f - t u n i n g c l a s s i f i c a t i o nc o d e ：t p 3 l l 复口人学坝 ：论文 8 聚类分析的新方法埘兜 第1 章引言 随着计算机硬件技术的发展和各种各样数据库的丌发，更多的数据以i j i 所未 有的速度收集在计算机中，其数量和复杂程度远远超过了人的分析能力。又由于 缺乏有效的工具从中发现潜在的规则和信息，人类便陷入了“丰富的数据”和 “贫乏的知识”并存的尴尬的境地，因此，人们希望计算机能帮助我们分析数据， 理解数掘，从中发现数掘的关联和知识，帮助我们基于海量数据做出决策，预测 未来的发展趋势，于是导致了对数据挖掘的需求。 数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识的过程。这些知 识是隐含的、事先未知的、潜在有用信息，提取的知识表示为概念、规则、规律、 模式等形式。还有一些术语，具有和数掘挖掘相近似但稍有不同的含义，如数掘 库中知识挖掘、知识提取、数掘考古和数据捕捞等。数掘挖掘是一个包含多学科 的领域，从这些学科中吸取营养，这些学科包括：数据库技术，人工智能，模式 识别、统计学、可视化等等。 在数据挖掘领域中，聚类分析是一项重要的研究课题。与分类不同，聚类的 目标是在没有任何先验知识的前提下，根据数掘的相似性将数据聚合成不同的 簇，使得相同簇中的元素尽可能相似，不同簇中的元素差别尽可能大，因此又被 称为非监督分类。聚类分析作为数据挖掘系统中的一个模块，既可以作为一个单 独的工具以发现数据库中数据分伟的深层信息，也可以作为其他数据挖掘分析算 法的一个预处理步骤，因此研究如何提高聚类算法的性能具有重要的意义。目前， 人们提出了很多种聚类算法。其中，典型代表是基于距离的聚类算法和基于密度 的聚类算法。 1 1 数据挖掘体系结构 像很多名词一样，数据挖掘并没有一个非常精确的定义。一般描述为一个从 大量数据中归纳出“知识”的过程。在这罩，“数据”的特征足大量的、直观的， 具体的一个个数据是可以被人直接感知的，但数据的全体集合远远超过人脑的直 接处理能力。数据类型包括【l 】关系数据库( r e l a t i o n a ld a t a b a s e ) 、数据仓库( d a t a w a r e h o u s e ) 、事务数掘库( t r a n s a c t i o n a ld a t a b a s e ) 、各种高级数据库系统和应用 复1 3 t 人学坝f 论文 9 聚燮分析的新方往研究 ( a d v a n c e dd a t a b a s es y s t e m sa n da d v a n c e dd a t a b a s ea p p l i c a t i o n s ) 。“知识”的特征 是抽象的、小量的、需要做一定的处理( 比如比较) 后d 能得到的，并且是人可 以理解和掌握的。在数据挖掘的结果中“知识”是用所谓的“模式”( p a t t e r n ) 来实现的。 另外还有一个概念：知识发现( k n o w l e d g ed i s c o v e r yo f d a t a b a s e s ，k d d ) 。 严格的讲，数据挖掘只是知识发现中的一步。然而，人们通常都用数据挖掘来代 替知识发现，在本文中也遵循同样的习惯。 数据挖掘的步骤【l 】包括：数据清理、数据集成、数据选择、数据变型、数据 挖掘、数据挖掘、模式评估、知识表达。数据挖掘的体系结构【1 】如图1 - 1 ： 豁摇窿 1 2 数据挖掘的功能 薮据仓库一 图1 - i 镪蔽蓐 镟一一9 数据挖掘引擎所实现的功能分为六大类：概念描述、关联分析、分类和预测、 聚类分析、例外分析、趋势分析。 概念( 类) 描述：特性描述和辨别 复口| 人学硕i 论史 聚类分析的新方 上研究 数掘可以由一定的概念和类抽象表示人们对其关心的那部分性质。分别 简单明了的描述这些概念和类显然是非常有用的。一般的，关于这些概念( 类) 的描述称为概念( 类) 描述( c o n c e p t c l a s sd e s c r i p t i o n ) 。数掘特性描述是指目标 数据的类的全面特性的概括，典型的是用一个数据库查询末实现对用户指定类的 描述性数据的收集。比如：要研究在去年销售增长了1 0 的软件产品，只要执行 一个s o l 查询就可以收集到这些产品相应的数据。其他方法还有：使用在线分 析处理( o l a p ) 中基于数据立方的r o l l u p 操作( 详见【1 】1 3 2 ) ，面向属性的归 纳技术( 详见【1 】第五章) 等。所得到的结果可以用饼图、柱状图、多维数掘立 方和多维表来表达给用户。 1 2 1 关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 是在一个给定的数据集中发现经常同时 发生的多个属性值条件( 一般称为关联规则) 的过程，最常用于市场销售和事物 数掘分析。关联规则形式化的表示为：x 专y ，也就是，a 1 a a 2 a a m 一 b 1 八 b 2 b 。，其中a i ( i e 1 ，m ) ) 和b j ( j l ，n ) 足属性对。关联规则 x 专y 意为“同时满足x 和y 中条件的数据库记录集”。 1 2 2 分类和预测 分类( c l a s s i f i c a t i o n ) 指为了能够使用模型预测类标签( c l a s sl a b e l ) 还未知 的对象所属的类，而寻找可以描述和区分类或概念的模型的过程，其中类标签指 用来区分类的属性。包括两个步骤：第一步，通过分析训练数掘空间中的数掘， 运用分类算法，建立分类模型；第二步，用测试数据空间中的数据估计已建立的 模型的预测准确性，如果用户可以接受，则用该模型对未知其类别的数据进行分 类预测。分类的最终结果一般用分类规则( i f t h e n 条件句) 、决策树、数学公 式、神经网络来表达。这罩决策树和神经网络的定义参照【1 】第1 7 页。所谓的预 测( p r e d i c t i o n ) 专指对丢失或无效的数掘的值的预测，通常这些值都是数字的 ( n u m e r i c a l ) 。 分类算法包括决策树归纳法，贝叶斯( b a y e s i a n s ) 分类和贝叶斯信任网络，神 经网络等等。 复口人学帧 论立 聚娄分析的新方法研究 1 2 3 聚类分析 聚类分析( c l u s t e r i n ga n a l y s i s ) ，一个将指定数据集中的数掘进行聚类( 也 就是归类) 的过程，其遵循的原则是每个类( c l u s t e r ) 内部各对象问的相似性尽 可能最大，而不同类的对象l 日j 的相似性尽可能最小。在具体实现中，一般用计算 对象属性的距离( 欧几里德距离、曼哈顿距离等) 束体现对象问的相似度。这一 部分将足本文论述的重点。 1 2 4 例外分析 一个数掘库中的数掘可能不都遵循总的数据模型的行为，这些数据称为 例外( o u t l i e r ) 。通常数据挖掘方法把例外作为垃圾而抛弃，不过在一些场合下， 比如诈骗检测中，例外却成为了最受关心的明星。例外分析大致有统计、基于距 离、基于偏差三种方法。 1 2 5 趋势分析 数据趋势分析( e v o l u t i o na n a l y s i s ) 描述对象行为随时| 日j 变化的趋向和规律。 这个概念和特性描述、关联分析、分类、与时问相关的数据的聚类都有些类似， 然而前者更强调对时序( t i m e s e r i e s ) 数据的分析、有序和周期性模式的匹配、 基于相似度的数据分析。关于时序的概念可以参照【2 】。 1 3 结果的处理 并不是用数掘挖掘方法的得到的所有结果都是人们感兴趣的，而且很有可能 结果也是数量相当大的。因此必然要以人为中心、基于查询，有目的地对所得到 的模式进行进一步筛选。筛选可采用的标准分为客观和主观两种。客观的 ( o b j e c t i v e ) ：基于统计或模式结构，如支持度，可信度等。主观的( s u b j e c t i v e ) ： 基于用户对数据的理解和需求，如意外度( u n e x p e c t e d n e s s ) ，新颖度( n o v e l t y ) ， 可控度( a c t i o n a b i l i t y ) 等。 复c i 人学坝 论文 1 2 聚炎分析的新方垃研究 1 。4 数据挖掘的研究方向 1 4 1 技术角度 当前，数据挖掘研究方兴未艾，其研究与开发的总体水平相当于数掘库技术 在7 0 年代所处的地位，迫切需要类似于关系模式、d b m s ( d a t a b a s em a n a g e m e n t s y s t e m ) 系统和s o l ( s t r u c t u r eq u e r yl a n g u a g e ) 查询语占等理论和方法的指导， 才能使数据挖掘的应用得以普遍推广。预计在本世纪，数据挖掘的研究还会形成 更大的高潮，研究焦点可能会集中到以下几个方面：发现语言的形式化描述、 数掘挖掘过程中的可视化方法、网络环境下的数据挖掘、对各种半结构数据的丌 采、复杂数据类型的处理、 1 4 2 商业角度 目前，在很多领域，数据挖掘( d a t am i n i n g ) 都是一个很时髦的词，尤其是 在如银行、电信、保险、交通、零售( 如超级市场) 等商业领域。数据挖掘所能 解决的典型商业问题包括：数掘库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分 ( c u s t o m e rs e g m e n t a t i o n & c l a s s i f i c a t i o n ) 、背景分析( p r o f i l e a n a l y s i s ) 、交叉销 售( c r o s s 。s e l l i n g ) 等市场分析行为，以及客户流失性分析( c h u ma n a l y s i s ) 、客 户信用记分( c r e d i t s c o r i n g ) 、欺诈发现( f r a u dd e t e c t i o n ) 等等。 复臣人学坝i 论文 聚类分析的祈方 2 m 究 第2 章聚类分析概述 2 1 概述 聚类分析是人类的一个重要活动。早在孩提时期，一个人就在通过连续的下 意识的为模式归类，来学习如何区别猫和狗，人和动物，或父母与其他人。聚类 分析还被非常广泛的应用于很多领域，包括模式识别、数据分析、图像处理和市 场研究。 虽然聚类分析跨越多个学科，但是在各个学科中都有不同的研究重点。在数 掘挖掘中，强调对复杂、高维的大型数据集进行快速有效的处理；在统计学中， 强调用数学的基于距离的方法；在生物学中，注重于使用聚类分析来处理基因方 面的大量数据；在机器学习中，聚类分析是无人监督学习的一个例子。 在参考文献【l 】中，聚类分析算法的评价标准分为九个方面： 1 规模可扩展( s c a l a b i l i t y ) 2 可处理不同属性类型的能力 3 可处理以任意形状( a r b i t r a r ys h a p e ) 分卸的数据的能力 4 尽可能对输入参数的相关领域知识要求少 5 处理噪声数据的能力 6 记录的输入顺序不影响聚类结果 7 对高维数掘的处理能力 8 基于约束的聚类 9 结果的可说明性和可使用性 复q 人学坝i 论文 1 4 聚类分析的新方法研究 现有的算法基本集中在二维情况下对第1 、2 、3 、4 、5 、6 条的研究。另外各类 算法也各有自己的侧重点，比如基于密度的算法多侧重于对任意形状方面的研 究，分割算法主要考虑规模可扩展和对例外的处理。然而，为了对聚类分析的结 果进行币确的评估，测试数据的准备其实也是一个应该仔细研究的方面，尤其是 高维测试数据的设计。 2 2 数据类型 聚类分析过程涉及的数掘结构包括两种：数据矩阵( 见图2 一1 ) 和相异 ( d i s s i m i l a r i t y ，见图2 2 ) 矩阵： x 1 1 x 玎x l p x i l 石i f 工i p x n l 工n f 工n p 图2 - 1 口 d ( 2 1 l 0 d f 3 , 1 ) d ( 3 ，2 ) 0 ： d ( n ，1 ) d ( n ，2 ) 0 图2 2 其中图2 - 1 中的矩阵的行代表记录，列代表属性，x i j ( 1 i n ，1 j p ) 代表第 i 条汜录的第j 个属性值；图2 - 2 中的矩阵的行和列表示同样的n 个对象，d ( i ，j ) 表示第i 个对象和第j 个对象之间的相异( d i s s i m i l a r i t y ) 度。 具体计算d ( i ，j ) 时将会遇到如下几种数据类型： 2 2 1 距离型( i n t e r v a l s c a l e d ) 数值 这一类数掘是指基于距离型数据，其相异度( d i s s i m i l a r i t y ) 用距离来描述。 测量距离的方法有欧几罩德距离( e u c l i d e a n ) 、曼哈顿距离( m a n h a t t a n ) 、明科 斯基距离( m i n k o w s k i ) 。 在计算距离前，一般应先进行标准化，使得数据最终独立于单位。标准化的 步骤如下： s ，= 丢( 1 工l ，一m ，i + i x 2 ，一m ，i + 十i x 可一m 复日人学帧i 论文 1 5 聚类分析的新方 上研究 第一步，利用下式计算平均绝对偏差( m e a na b s o l u t ed e v i a t i o n ) 。其中f 足某种属 性， x 州1 i n 是有n 个属性值的集合，且 mf = 等( x l f + x 2f + + x 哼、 矿 第二步，计算标准化度量( s t a n d a r d i z e dm e a s u r e m e n t ，又称z s c o r e ) 。 最终是对标准化后的数值进行聚类分析。在这里，采用使用平均绝对偏差比使用 标准偏差( s t a n d a r dd e v i a t i o n ) 对o u t l i e r 要更健壮。因为前者使得o u t l i e r 的z s c o r e 不至于太小，这样就可以保证可被检测到。 在标准化后就可以使用各种距离公式束计算各对象之日j 相异度了。下面是明 科斯基距离公式： 州；扣i 阿i i 了i 瓦可 当q = 1 时，就是曼哈顿距离公式；当q = 2 时，就是欧几罩德距离公式。 2 2 2 离散数值( c a t e g o r i c a ld a t a ) 离散数值又可以分为有序和无序两大类型。有序类如：月份、年份；无序类 如：颜色、水果种类。在【1 】中，离散数值被划分为二进制值、名词性值、有序 值，相应相异度的计算e q 8 2 节。 2 3 五大类算法 聚类分析的算法分五大类f 1 】，分别是分割算法、分层算法、基于密度算法、 基于网格算法、基于模型算法。也有些人从数学角度出发，认为聚类分析只包括 前两种算法，当然这完全是因为看问题所采用的角度问题。 复q 人学倾l 论殳 1 6 聚类分析的新方法研究 2 3 1 分割算法( p a r t i t i o n i n gm e t h o d s ) 给定一个n 个对象的数掘集，以及整数k - 一形成的聚类的个数，一个分割 算法将所有的对象划分成k 部分( k n ) ，每一部分代表一个聚类( c l u s t e r ) 。分 割算法的思想是先将数据集初始化分割为k 部分，然后采用一个循环迭代的技术 通过将对象从一个组移到另一个组中去来提高分割的质量。 为了获得全局最优解，基于分割的聚类要求穷举所有可能的分割。在实际实 现中，绝大多数的应用采用属于两种最流行的启发式算法之一：k - m e a n s 4 或 k - m e d o i d s 5 。k - m e a n s 和k - m e d o i d s 的区别在于前者是用所有对象的平均值 ( m e a n ) 来代表聚类，而后者是用最接近聚类中心的对象( 称为m e d o i d ) 来代 表聚类。 2 3 。1 1k - m e a n s 算法 输入：整数k ，一个有n 个对象的数据库 输出：一个标准方差最小的k 个聚类的集合 步骤： 随机选取k 个对象作为仞始聚类的中心 d o e n d ； 将每一个对象加到距它最近的聚类中去； 重新计算每一个聚类的中心( 即聚类中所有对象的平均值) ； w h i l e ( 聚类发生了变化1 通常，聚类发生的变化用计算所有对象的标准方差的总和末描述。k - m e a n s 的优点是对于分御紧密( c o m p a c tc l o u d s ) 的数掘非常有效，处理较大的数掘集 也很有效( 因为它的计算复杂度为o ( n k t ) ，其中t 是循环次数，k n ，t n ) 。缺 复且人学硕i 论文 1 7 聚类分折的新方泣研_ 充 点是不适于处理离散属性，需要指定k 值，不适于非凸形状数掘，受噪声和例外 数据影响很大。从k - m e a n s 出发产生的扩展算法可从三方面区别：初始k 个m e a n s 的选择；相异度的计算；计算聚类m e a n s 的策略。对k - m e a n s 在离散属性处理方 面的扩展产生了k - m o d e s 算法；综合对连续数掘和离散数据的处理产生了 k - p r o t o t y p e s ：采用了模糊数学的思想而产生的e m 算法，并不明确将某一对象唯 一的归到某一聚类罩，也就是说聚类间没有明确的界限。 2 3 1 2k - m e d o i d s 算法( 以p a m 为例) 输入：整数k ，一个有n 个对象的数据库。 输出：所有对象到距他们最近的m e d o i d 距离总和最小的k 个聚类的集合。 步骤： 随机选取k 个对象作为初始聚类的中心 do e n d ； 将每一个剩余的对象加入到距它最近的聚类中去： 随机选择一个n o n m e d o i d 对象，o r a n d o m ； 计算将0 j 换为o r a n d o m 后整体的代价，s ； i f ( s 0 ) 将0 j 与o r a n d o m 交换形成新的聚类； w h i l e ( 聚类发生了变化) k - m e d o i d s 的产生源于k - m e a n s 在o u t l i e r 方面的弱点。然而k - m e d o i d s 同样 面临k 的选择问题，而且k - m e d o i d s 的代价太大。对k - m e d o i d s 的扩展产生了 c l a r a 【5 】和c l a r a n s 6 。 复! e 1 人学坝l 论史1 8 聚麦分析的新方注研究 2 3 2 分层算法( h i e r a r c h i c a lm e t h o d s ) 一个分层算法思想是把数据对象分组成为聚类树。进一步，分层算法可以根 掘建树的方向分为凝聚算法( a g g l o m e r a t i v e ，自底向上) 和分裂( d i v i s i v e ，自 顶向下) 算法。纯粹的分层算法由于对于数据只有一次聚合或分解，因此其聚类 质量非常差，有鉴于此，分层算法往往和迭代算法结合起来一起进行研究。 在实际操作中，由于对于要处理的数掘对象了解甚少，采用自底向上的凝聚 算法是一种很自然的想法，因此绝大多数分层算法都是属于此类。分层算法有 c h a m e l e o n 1 8 1 、b i r c h 9 、c u r e 7 、r o c k 【8 】等。他们的基本思想都是对 数据集进行一次初始划分，然后再根据某种算法来聚合。 c h a m e l e o n 是一个在层次聚类中采用动念模型的聚类算法。其主要思想 是：首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用 一个凝聚的层次聚类算法通过反复地合并子类末找到真正的结果簇。其优点是在 发现高质量的人以形状的聚类方面有更强的能力。其缺点是在最坏的情况下，高 维数据的处理代价可能对n 个对象需要o ( n 2 ) 的时i b j 。 b i r c h 算法是一个综合的层次聚类方法。其主要思想是：扫描数据库，建立 一个初始存放于内存中的c f 树，然后采用某个聚类算法对c f 树的叶结点进行 聚类。算法的计算复杂度为o ( n ) 。其优点是通过聚类特征可以方便地进行中心、 半径、直径及类内、类问距离的运算。算法具有对对象数目的线性伸缩性，及良 好的聚类质量。其缺点是由于受c f 数节点大小的限制，c f 数节点并不总队应 于用户认为的一个自然聚类。而且，如果簇不足球形，b i r c h 算法不能很好工 作。 c u r e 算法选择基于质心和基于代表对象方法之问的中问策略。该算法主要 思想是：首先把每个数据点看成一簇，然后再以一个特定的收缩因子向中心“收 缩”它们，即合并两个距离最近的代表点的簇。c u r e 的复杂度是0 ( n ) ，n 是对 象的数目。其优点是对孤立点的处理更加健壮，而且可以识别非球形和大小变化 较大的簇，对于大型数掘库具有良好的伸缩性。其缺点则有参数设置对聚类结果 有显著影响，c u r e 算法不处理分类属性，且忽略了关于两个不同簇中对象的聚 集互连性的信息。 复q 人学坝t 论文 1 9 聚类分析的惭方法州究 2 3 3 基于密度的算法( d e n s i t y - b a s e dm e t h o d s ) 适应于对处理任意形状的要求，基于密度的算法应运而生。典型的算法有 d b s c a n i o 、o p t i c s 1 2 、d e n c l u e 3 0 。 2 3 3 1d b s c a n 算法 d b s c a n 定义了一系列的概念，包括： 1 ) 领域：给定数据对象半径内的区域称为该对象的领域。 2 ) 核心对象：如果一个对象q 的- 领域包含的对象数日不小于最小数日 m i n p t s ，则称该对象为核心对象。 3 ) 直接密度可达：给定一个对象集合d ，如果p 在q 的- 领域内，而q 是 一个核心对象，称对象p 从对象q 出发直接密度可达。 4 ) 密度可达：如果存在一个对象链p 】，“，m ，p l = q ，m - p ，对p i d ，p j + 1 是 p i 关于和m i n p t s 直接密度可达的，则称对象p 和q 是关于和m i n p t s 密度可达的。 5 ) 密度相连：如果一个对象o ，使得对象p 和q 是从o 关于和m i n p t s 密度 可达的，那么对象p 和q 是关于和m i n p t s 密度相连的。 6 ) 数掘簇：个基于密度可达性的最大密度相连对象的集合。 7 ) 噪音点：对象集合中不属于任何簇的对象就足噪音点或者叫离群点。 根掘数据集具体情况设定全局参数和m i n p t s ，然后d b s c a n 算法以任意一 个数据对象p 开始，搜索所有其关于和m i n p t s 密度可达的对象。如果p 是一个 核心对象，则将p 和p 的密度可达对象集合聚类产生一个数据簇，然后反复搜索 p 的密度可达对象集合中每个对象的密度可达对象，并将其加入这个集合聚类到 这个数据簇，这个集合中所有的对象都遍历结束；如果p 是一个边界对象没有密 度可达的点，则算法继续访问下一个数据对象。这样反复的寻找那些核心对象直 接密度可达的对象，直到没有新的对象可以被添加到任何数据簇中，算法自动终 复口大学劬i 论文 聚类分析的新方往研究 止。 d b s c a n 算法在寻找领域最近邻域采用r + t r e e 组织数据索引结构， r t t r e e 的高度是l o g ( 1 1 ) ，1 1 为数据对象的数目，所以如果采用r * - t r e e ，算法的 时问复杂度为0 ( 1 1 t l o g ( n ) ) ；如果不采用r + - t r e e ，算法的时间复杂度为o ( n 2 ) 。 2 3 3 2o p t i c s 算法( 通过对象排序识别聚类结构) o p t i c s 算法的提出，是为了解决d b s c a n 算法所存在的缺点。它没有显式 地产生一个数据簇，它为自动和交互的聚类分析计算一个簇次序。o p t i c s 算法 创建了数据库中对象的一个次序，额外存储了每个对象的核心距离和一个适当的 可达距离。该算法优点是解决了对于参数敏感的问题，缺点是占用了额外的存储 空间。 2 3 3 3d e n c l u e 算法( 基于密度分布函数的聚类) d e n c l u e 算法是一个基于一组密度分布函数的聚类算法。其主要思想是： 通过定义一个密度函数，能够得出该函数的梯度和密度吸引点，从而形式化地定 义中心定义的簇和任意形状的簇。该算法优点是具有峰实的数学基础，概括了其 他的聚类方法。对于有大量“噪声”的数据集合，具有良好的聚类特性。对高纬 数据集合的任意形状的聚类，给出了简洁的数据描述。使用了网格单元，速度较 快。它的缺点是d e n c l u e 算法要求对密度函数参数和噪音阂值进行仔细的选 择。 2 3 4 基于网格的算法( g r i d b a s e dm e t h o d s ) 基于网格的聚类方法使用一个m u l t i r e s o l u t i o n 的网格数据结构。它把空间分 为有限个单元，这些单元组成了一个网格结构，所有的操作都在这个结构上执行。 网格算法的主要优点是速度快因为处理时问和对象数目没有关系，只与对空 | 、日j 每一维的划分数目有关。 代表性的算法有c l i q u e 1 6 、s t i n g 1 4 、w a v e c l u s t e r 1 5 a 复口人学帧i 论文 2 1 聚炎分析的新方 三研究 2 3 4 1c l i q u e 算法 c l i q u e 算法足一个高维数掘子空间自动聚类算法。它主要包括三步：1 ) 寻找密集单元；2 ) 通过将连接的密集单元分组产生聚类；3 ) 根据最小聚类描述 m d