（计算机软件与理论专业论文）基于网格的聚类算法分析与研究.pdf

摘要 摘要 数据挖掘是近些年来发展起来的新技术，通过数据挖掘，人们可以发现数据 背后隐藏的有价值的、潜在的知识，为科学地进行各种商业决策提供强有力的支 持。随着数据挖掘技术的迅速发展，作为其重要的组成部分，网格聚类技术已经 被广泛的应用于数据分析、图象处理、市场研究等许多领域。基于网格的聚类算 法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。 本文首先介绍了数据挖掘研究的相关背景及其理论知识，对数据挖掘中的聚 类分析的相关工作做了一个简要的概述。在研究了传统聚类算法的基础上，提出 了基于网格的共享近邻聚类算法( g n n ) ，即将空间数据映射到网格中，在区域 查询时只考虑相关网格单元内的数据，提高了处理速度。该算法主要利用网格技 术去除数据集中的部分孤立点或噪声，使用密度阈值处理技术来定义网格的密度 阈值，使用中心点技术提高聚类效率；针对对象间的相似性度量方法，提出了基 于相似度的网格聚类算法( s g c a ) ，将其应用于网格聚类，根据定义的边界点 阙值函数提取类的边界点，显著地提高了网格聚类的精度，另外还引进了网格核 技术，使得s g c a 算法的时间复杂度也有了明显地改善。 本文使用v m u a lc + + 6 0 实现了基于网格的共享近邻聚类算法、基于相似度 的网格聚类算法、s n n 算法、c l i q u e 算法，并做了大量的对比实验，其中包 括g n n 算法和s g c a 算法的正确性和有效性。g n n 算法和s g c a 算法都具有 较好的可扩展性，可以发现任意形状的聚类，受噪声的影响不明显，它们不仅适 用于综合数据集，而且对高维数据集也具有较好的聚类结果。 实验结果表明，基于网格的共享近邻聚类算法采用网格密度阈值处理可以很 好的解决传统网格聚类算法对参数敏感的问题，使用网格中心点技术提高了聚类 的效率；基于相似度的网格聚类算法利用网格技术去除了数据集中的部分孤立点 或噪声，边界点阈值函数能有效的提取类的边界点，提高了聚类的精度；网格核 技术应用于s g c a 算法进一步改善了它的时间复杂度。 摘要 总之，基于网格的共享近邻聚类算法不仅能有效的识别出任意形状的聚类， 而且也能有效的识别出孤立点或噪声，对噪声数据和数据输入顺序不敏感，在与 传统的共享近邻聚类算法对比中显示出了一定的优越性；基于相似度的网格聚类 算法不仅适用于综合数据集，而且对高维数据集也具有较好的聚类结果。 关键词：数据挖掘；网格；聚类；共享近邻；密度阈值；中心点；相似度；阈 值函数；核 n a b s l r a c t a b s t r a c t d a t am i n i n gt e c h n i q u e si st h en e w t e c h n i q u et h a td e v e l o p si nr e c e n ty e a r s ，w h i c h 啪b eu s e dt of i n do u tp o t e n t i a la n du s e f u lk n o w l e d g ef r o mt h ev a s ta m o u n to fd a t a , a n di tp r o v i d e st h ep o w e r f u ls u p p o r tt oc a r r yo nv a r i o u sb u s i n e s sd e c i s i o ni ns c i e n c e g r o u n d w i t ht h er a p i dd e v e l o p m e n to ft h ed a t am i n i n gt e c h n i q u e s ，t h et e c h n i q u eo f g r i dc l u s t e r i n g , a si m p o r t a n tp a r t so fd a t am i n i n g , a l ew i d e l ya p p l i e dt ot h ef i e l d ss u c h a sp a t t e r nr e c o g n i t i o n , d a t aa n a l y s i s ，i m a g ep r o c e s s i n g , a n dm a r k e tr e s e a r c h r e s e a r c h o ng r i d c l u s t e r i n ga l g o r i t h m sh a sb e c o m ea h i g h l ya c t i v et o p i ci nt h ed a t am i n i n g r e s e a r c h 。 i nt h ef i r s tp a r t , w ei n t r o d u c et h er e l a t e db a c k g r o u n do fd a t am i n i n ga n di t s t h e o r i e sk n o w l e d g e t h e nw eb r i e f l ys u m m a r i z et h er e l a t e dw o r ko fc l u s t e r i n g a n a l y s i s b a s e do nt h ea n a l y s i so ft r a d i t i o n a l 班dc l u s t e r i n ga l g o r i t h m s ，w eb r i g h t f o r w a r dt h eg r i d - b a s e ds h a r e dn e a r e s tn e i g h b o rc l u s t e r i n ga l g o r i t h m ( g n n ) t h e b a s i cp r o c e d u r ei st h a td i v i d et h es p a t i a ld a t a b a s ei n t om a n yg r i d s ，t h e nm a pa l l d a t ai n t oe a c hg r i d w h e nq u e r y i n g , w ec a nj u s tc o n s i d e rp a r t so fd a t ai nr e l a t e d 鲥d s s oi t 锄a c c e l e r a t et h eo p e r a t i n gs p e e d t h eg n na l g o r i t h mr e m o v e ss o m e o u t l i e r so rn o i s e si nt h ed a t a s e tb yt h et e c h n i q u eo fg r i da n dd i s p o s e so fd e n s i t y t h r e s h o l do f 鲥db yt h em e t h o do fd e n s i t yt h r e s h o l d t h eg n n a l g o r i t h mc l u s t e r s b yt h em e t h o do fs h a r e dn e a r e s tn e i g h b o ra n di m p r o v e st h ee f f i c i e n c yb yt h eu s e o ft h e 鲥dc e n t e r a i ma tt h em e a s u r e m e n tm e t h o do i ls i m i l i t u d eb e t w e e no b j e c t s ， w ep u tf o r w a r das i m i l a r i t y - b a s e dg r i dc l u s t e r i n ga l g o r i t h m ( s g c a ) i ta p p l i e so n t h eg r i dc l u s t e r i n ga n dd i s p o s e so fb o r d e rp o i n t so fc l u s t e r sb yt h em e t h o do ft h e t h r e s h o l df u n c t i o no fb o r d e rp o i n t st h a te n h a n c e sr e m a r k a b l yt h ep r e c i s i o no fg r i d c l u s t e r i n g i no r d e rt oi m p r o v et h ee f f i c i e n c yo fs g c a , t h et e c h n i q u eo fg r i d c o r e s b a s e di su s e d i nt h i st h e s i s , w eh a v ed e v e l o p e dg n n ，s g c a , s n na n dc l i q u ea l g o r i t h ma n d i m p l e m e n t e dt h e mu s i n gv 塔u a lc + 6 0 w ec o n d u c t e das e r i e so fe x p e r i m e n t s 。 i n c l u d i n gt h ee x p e r i m e n to ft h ec o i t c c i l i c s so f 鲥dc l u s t e r i n ga n dt h ee f f i c i e n c yo fi t m a b s t r a c t n eg n na n ds g c aa l g o r i t h mh a v eb o t hb e t t e re x p a n s i b i l i t ya n dc a nd i s c o v e r c l u s t e r so fa r b i t r a r ys h a p e s t h e ya r cn o to n l ys u i t a b l ef o rs o m es y n t h e t i cd a t u s e t s ，b u t a l s oi th a sb e t t e rc l u s t e r i n gr e s u l t si n8 0 1 n ch i ：g hd i m e n s i o n a ld a t a s e t s a ss h o w ni nt h ee x p e r i m e n t a lr e s u l t s ，g n na l g o r i t h mc a ns o l v et h ep r o b l e m t h a tt h eg r i dc l u s t e r i n ga l g o r i t h mi ss e n s i t i v et op a r a m e t e r sb yd e n s i t yt h r e s h o l do f g r i da n dc a l li m p r o v et h ec f f i c i e n c yb yt h er i s eo ft h eg a dc e n t e r ；, s g c aa l g o r i t h m r e m o v e ss o m eo u t l i e r so rn o i s e si nt h ed a t a s e ta n dd c a l sw i t hb o r d e rp o i n t s p r o p e r l ya n di m p r o v e st h ep r e c i s i o no fc l u s t e r i n gr e s u l t i no r d e rt oi m p r o v et h e e f f i c i e n c yo fs g e a , t h et e c h n i q u eo fg a dc o r e s - b a s e di su s e di nt h i sp a p e r t os 哪u p t h eg n na l g o r i t h mc a l ln o to n l yc l u s t e rc o r r e c t l yb u ta l s of i n do u t l i e r s i nt h ed a t a s e ta n di sn o ts e n s i t i v et on o i s e sa n do r d e ro fd a t ai n p u t t h ep r e c i s i o no f g n n a l g o r i t h mi sb e t t e rt h a nt h a to fs n n 1 1 1 es g c a i sn o to n l ys u i t a b l ef o rs o m e s y n t h e t i cd a t u s e t s ，b u ta l s oi t h a sb e t t e rc l u s t e r i n gr e s u l t si ns o m eh i g hd i m e n s i o n a l d a t a s e t s k e yw o r d s ：d a t am i n i n g ；g r i d ；e l n s t e r i n g ；s h a r e dn e a r e s tn e i g h b o r ；, d e n s i t yt h r e s h o l d ； c e n t e r ；, s i m i l a r i t y ；t h r e s h o l df u n c t i o n ；c e r e s i v 第1 章引言 第1 章引言 1 1 研究背景及意义 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多如何从激增的数据背后找到有价值的信息，并从中提取出知识内容 已经成为目前数据挖掘和知识管理等研究领域的重要课题而数据挖掘技术 ( d a t am i n i n g ) 1 1 】正是解决这一课题的重要方法权威的g a r t n e r 调查报告显示， 数据挖掘将是今后几年全球范围内重点投资研究的十大新技术之一，它引起了学 术界和工业界的广泛关注，是当今数据库系统研究和应用领域内的一个热点问题 【2 】。 聚类( c l u s t e r i n g ) 是数据挖掘中的重要组成部分，所谓聚类就是将数据对 象分组成为多个类或簇( c l u s t e r ) ，在同一个簇中的对象之间具有较高的相似度， 而不同簇中的对象差别较大。相似度是根据描述对象的属性来计算的。距离是经 常采用的度量方式从机器学习的角度看，聚类属于无指导学习，和分类不同， 它依赖预先定义的类和类标号的训练实例。聚类分析具有广泛的应用价值，如市 场分割、模式识别、生物学研究、空间数据分析、w e b 文档分类。除此之外，聚 类分析还可以作为独立的数据挖掘工具，来了解数据发布，或者作为其他数据挖 掘算法的预处理步骤。 聚类已经被广泛地研究了许多年，迄今为止，研究人员已经提出了许多聚类 算法，大体上这些算法可以分为基于划分的方法、基于层次的方法、基于密度的 方法、基于网格的方法和基于模型的方法。 网格技术是一项新兴的技术，正处于不断发展和变化当中。基于网格的聚类 方法利用多维网格数据结构，将空间划分为有限数目的单元，以构成一个可以进 行网格聚类分析的网格结构。在网格单元中，同一单元中的点属于同一类的可能 性比较大，所以落入同一网格中的点可被看作一个对象进行处理，以后所有的聚 类操作都是在网格单元上进行。 网格聚类算法可以适用于比较分散、并不密集的空间多维数据的挖掘，弥补 第1 章引言 了基于密度的聚类算法【3 】的缺陷：不必事先假设类的个数，类的个数由算法自动 生成，弥补了肛平均值【4 1 和k - 代表点嘲聚类算法的缺陷；不必事先随机选取初始 点，由算法自动选取距离最远的非异点数据为初始点，从而避免了因初始点选择 不当而导致局部最优解的错误；通过网格合并而生成的区域表可以方便地给出聚 类结果的现实意义描述；可以方便而有效地发现异常点；由于网格聚类算法采用 了网格技术，所以算法的处理时间与数据对象的数目只呈一次线性关系，而主要 由网格的划分及数据的空间分布情况决定。当对挖掘对象进行网格划分时每维上 的划分区间数越少，聚类效率越高。如果数据的空间分布越集中，则实际所占的网 格数越少，则聚类效率越高。 所以，对网格聚类算法的研究将具有广阔的发展空间，今后将会在更多的领 域中发挥作用。 1 2 研究内容 本文在系统地归纳数据挖掘的一般原理、一般方法以及相关技术的基础上， 对数据挖掘中关键技术之一的聚类分析进行了探索性的研究，主要内容包括如下 几个方面： ( 1 ) 在简要总结介绍课题的研究背景及选题意义的基础上，研究了数据挖 掘的基本原理、一般方法及其在各个领域的应用；系统地介绍了聚类分析的相关 概念、聚类的主要分类及一些具有代表性的聚类算法。 ( 2 ) 提出了基于网格的共享近邻聚类算法。为了提高共享近邻聚类算法的 精度，本文首先利用网格聚类去除数据集中的部分孤立点和噪声数据；为了更好 地改善共享近邻聚类算法的效率，本文还提出了网格中心点技术。在综合数据集 和真实数据集上对基于网格的共享近邻聚类算法进行测试，并与传统的共享近邻 聚类算法进行比较，最后给出实验结果，同时分析了该算法的时间复杂度和空间 复杂度。 ( 3 ) 提出了基于相似度的网格聚类算法。把本文定义的相似性度量方法应 用于网格聚类算法，为了提取类的边界点，提出了边界点阙值函数，显著地提高 了聚类的精度；最后还提出了网格核技术，应用该技术进一步提高了聚类的效率。 第1 章引言 1 3 论文结构 本文共分五章，各章的主要内容如下： 第一章简要介绍了课题的研究背景与意义、论文的主要内容及组织结构。 第二章系统的研究了数据挖掘和聚类分析的相关理论知识，给出了聚类算法 的主要分类，介绍了一些常见的基于密度和基于网格的聚类算法，分析了这些算 法的优点和缺点；还对一些改进的网格聚类算法进行了详细的阐述。 第三章在研究了共享近邻聚类算法的基础上，为提高聚类的精度和聚类的效 率，提出了基于网格的共享近邻聚类算法，并将该算法在不同的数据集上进行测 试，且与传统的共享近邻聚类算法的实验结果进行比较，同时分析比较了它们的 时间复杂度。 、 第四章在研究了传统的相似度度量方法和传统网格聚类算法的基础上，提出 了基于相似度的网格聚类算法( s g c a ) ，并将该算法在综合数据集和真实数据 集上进行测试，与传统的网格聚类算法c l i q u e 在实验结果的精度上进行比较。 采用网格核技术进一步改进s g c a 算法，通过实验分析比较改进前后的时问复 杂度。 第五章对前面研究工作进行了总结与展望，给出了本文的主要创新点，并指 出了今后的研究工作。 3 第2 章数据挖掘和聚类分析 第2 章数据挖掘和聚类分析 2 1 数据挖掘概述 随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的 数据急剧增加，可是用于对这些数据进行分析处理的工具却很少。目前数据库系 统所能做到的只是对数据库中已有的数据进行存取和简单的操作，人们通过这些 数据所获得的信息量仅仅是整个数据库所包含的信息量的很少的一部分，隐藏在 这些数据之后的更重要的信息是关于这些数据的整体特征的描述及对其发展趋 势的预测，这些信息在决策生成的过程中具有重要的参考价值。这就引起了对强 有力的数据分析工具的急切需求。快速增长的海量数据收集、存放在大型和大量 数据库中，没有强有力的工具，理解它们已经远远超出了人的能力。 面对这种挑战，数据库中的知识发现k d d ( k n o w l e d g ed i s c o v e r y i n d a t a b a s e s ) 技术逐渐发展起来k d d 就是从大量、不完全、有噪声的异质模糊 数据中挖掘隐含的潜在有用知识的过程，它不但能够学习已有的知识，而且又可 以发现未知的规律。同时，k d d 也是- - i - j 新兴的交叉学科，汇聚了数据库、人 工智能、统计、可视化和并行计算等不同领域的研究人员。 一般将k d d 中进行知识学习的阶段称为数据挖掘( d a t am i n i n g ) ，它是整 个数据库中的知识发现过程中一个非常重要的处理环节，所以两者往往混用。一 般而言，在数据库、统计和数据分析等工程应用领域称为数据挖掘，而在人工智 能和机器学习界等研究领域人们则称之为数据库中的知识发现。本文将不加区分 地使用两者。 2 1 1 数据挖掘的定义 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的 数据量急剧 鸶大，在大量的数据背后隐藏着许多重要的信息，如果能把这些信息 从数据库中抽取出来，将创造很多潜在的利润，而这种从海量数据库中挖掘信息 的技术，就称之为数据挖掘【n ( d a t am i n i n g ) 。1 9 9 5 年以来，国外在知识发现和 4 第2 章数据挖掘和聚类分析 数据挖掘方面的论文非常多，已形成了热门研究方向。 从广义上讲，数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程。这个定义包括以下四个层次的含义： ( 1 ) 数据源必须是真实的、大量的、含噪声的； ( 2 ) 发现的是用户感兴趣的知识： ( 3 ) 发现的知识要可接受、可理解、可运用，最好能用自然语言表达发现结 果； ( 4 ) 并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科学 定理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的，是 有特定前提和约束条件、面向特定领域的。 从商业角度出发，数据挖掘可以描述为：按企业既定业务目标，对大量的企 业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将 其模型化的先进有效的方法 6 , 7 , s i 。 2 1 2 数据挖掘的组成 采用k d d 的广义观点：k d d 是从存放在数据库、数据仓库或其他信息库 中的大量数据中挖掘有趣、有意义的知识的过程。基于此观点典型的k d d 系 统主要由以下几个部分组成： 数据库、数据仓库或其他信息库：是进行数据挖掘的数据源，是一个或一 组数据库、数据仓库、电子表格或其他类型的信息库。可以在他们的数据 上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘要求，数据库或数据仓库 服务器负责提取相关的数据。 知识库；是特定的知识领域，用于指导搜索或评估结果模式的兴趣度。这 种知识可能包括概念分层，用于将属性或属性值组织成不同的抽象层，其 中用户确信方面的知识也可以包含在内，可以根据非期望性评估模式的兴 趣度使用这种知识。领域知识的其他例子有兴趣度限制或阈值和元数据( 例 如，描述来自多个异种数据源的数据) 。 5 第2 章数据挖掘和聚类分析 数据挖掘引擎：是数据挖掘的最重要的基本部分。由一组功能模块组成， 用于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常此成分使用兴趣度度量，并与数据挖掘模块交互，以 便将搜索聚集在有趣的模式上它可能使用兴趣度阈值过滤发现的模式。 模式评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方 法的实现。对于有效的数据挖掘，应尽可能深地将模式评估推进到挖掘过 程之中，以便将搜索限制在有兴趣的模式上 图形用户界面：是在用户和数据挖掘系统之间通信，允许用户与系统交互、 指定数据挖掘查询或任务、提供信息、帮助搜索聚焦、根据数据挖掘的中 间结果进行探索式数据挖掘。此外，还允许用户浏览数据库和数据仓库模 式或数据结构，评估挖掘的模式，以不同的形式对模式可视化。 典型的数据挖掘系统结构如图2 - 1 所示。图2 1 清晰地表示出了数据挖掘 系统中各个功能模块之间的相互作用和依赖关系 图2 - 1 典型的数据挖掘系统结构 2 1 3 数据挖掘的过程 数据挖掘是一个完整的过程，该过程从大型数据库或数据仓库中挖掘先前未 知的、有效的、可实用的信息，并使用这些信息做出决策或丰富知识。在实施数 6 第2 章数据挖掘和聚类分析 据挖掘之前，先决定采取什么样的步骤，每一步都做什么，达到什么样的目标是 必要的，有了好的计划才能保证数据挖掘有条不紊的实施并取得成功。一般地， 数据挖掘在任何一个问题上的应用，都可以大致分为三个阶段【9 1 川： 第一阶段，即数据准备阶段，拿到待分析的问题，以及与该问题相关的数据 库。包括： ( 1 ) 数据清理：主要试图填充空缺的值，识别孤立点、消除噪音，并纠正数 据中的不一致。 ( 2 ) 数据集成：将多个数据源中的数据集合起来存放在一个一致的数据存储 ( 如数据仓库) 中。这些数据源可能包含多个数据库，数据立方体或一般文件( 如 文本文件等) ( 3 ) 数据变换：将某一个数据进行某种转换操作，然后将转换后的值作为新 的变量存放在样本数据中，而转换的目的是为了把数据和将来要建立的模型拟和 得更好。 ( 4 ) 数据规约：如果选择用于数据分析的数据集太大，就会降低挖掘的速度 和影响挖掘的结果，于是就用数据规约得到数据集的压缩表示，它小得多，但能 产生同样的( 或几乎同样的) 分析结果。 第二阶段，即数据挖掘阶段，借助各种数据挖掘工具，从数据库中找出有可 能解决问题的知识。包括： ( 1 ) 确定挖掘的任务或目的，是属于数据总结、分类、聚类、关联规则发现 或序列模式发现中的哪一种。 ( 2 ) 选择合适的挖掘技术。在确定挖掘任务的基础上，选择适当的数据挖掘 技术。如分类模型常由有指导的神经元网络或归纳技术( 如决策树) 来实现；聚类 常用聚类分析技术；关联分析使用关联发现和序列发现技术等。 ( 3 ) 选择挖掘算法挖掘算法的选择是一个核心的步骤，一般不会存在一个 普遍适用的数据挖掘算法，一个算法在一个领域非常有效，但在另一个领域却可 能不太适合所以，在面对一个实际的领域，如何从众多的数据挖掘算法中精选 有效的算法就自然成为研究与开发任务首先要解决的一个核心问题。选择挖掘算 法主要考虑两个因素：一是不同的数据有不同的特点，因此需要用与之相关的算 法来挖掘；二是用户或实际运行系统的要求，有的用户可能希望获取描述型的、 7 第2 章数据挖掘和聚类分析 容易理解的知识，而有的用户或系统的目的是获取预测准确度尽可能高的预测型 知识。 ( 4 ) 挖掘数据。用选定的算法或算法组合在模式空间中进行反复迭代的搜索， 从数据集合中抽取出隐藏的、新颖的模式。 第三阶段，即结果表现及解释阶段，将发现的知识用于解释当前或历史现象， 预测未来可能发生的情况，使决策者参照从过去发生的事实中抽取的信息进 行决策制定。包括： ( 1 ) 模式评估：消除无关的、多余的模式，过滤出要呈现给用户的信息； ( 2 ) 知识表示：利用可视化技术将有意义的模式以图形或逻辑可视化的形式 表示，转化为用户可理解的语言。 上面三个阶段的工作，在实际运作中，一般都存在反复。也有人把上述整个 过程称为数据库知识发现( 即k d d ) ，而仅把第二阶段称为数据挖掘，认为它是 知识发现过程的一个步骤。图2 - 2 给出了数据挖掘的三个主要阶段及各阶段的 相关步骤1 。 8 第2 章数据挖掘和聚类分析 2 1 4 数据挖掘的功能 数据挖掘的功能反映了数据挖掘算法发现的模式的种类。根据履行功能的不 同，我们将数据挖掘问题分为数据概括、关联分析、分类、聚类、依赖建模、孤 立点分析以及演变分析等几个类别。 ( 1 ) 数据概括 数据库数据是最基本的信息，不能满足不同层次的用户希望从不同的层次和 角度对数据进行处理或浏览的需求。数据概括是一种把数据库数据从低层次抽象 到高层次的过程，换言之，就是对数据进行浓缩，用紧凑形式重新对其进行表示。 ( 2 ) 关联分析【1 2 ，捌 关联分析就是从大量数据中发现项集之间有趣的关联或相关联系。若两个或 多个数据项的取值重复出现且概率很高时，它就存在着某种关联，可以建立起这 些数据项的关联规则，如“在购买面包和黄油的顾客中，有9 0 的人同时也买了 牛奶”( 面包+ 黄油+ 牛奶) 关联可分为简单关联、时序关联、因果关联。关联分 析的目的是找出数据库中隐藏的关联网。在大型数据库中，这种关联规则是很多 的，一般用“支持度”和“置信度”两个阈值来淘汰那些没有用的关联规则。关 联分析广泛应用于市场营销、事务分析等应用领域。 ( 3 ) 分类【1 4 1 5 】 分类( 是这样的过程，它找出描述并区分数据类或概念的模型或函数) ，以便 能够使用模型预测类标记未知的对象类。导出模型是基于对训练数据集( 即其类 标记已知的数据对象) 的分析。导出模型可以用多种形式表示，一般利用判定树 归纳【1 6 1 、b a y e s 分类、神经网络【1 7 , 1 8 、k - - 最近邻【 、遗传算法1 1 们、粗糙集1 2 0 等技 术进行分类。 分类可以用来预测数据对象的类标记然而，在某些应用中，人们可能希望 预测某些空缺的或不知道的数据值，而不是类标记。当被预测的值是数值数据时， 通常称之为预测。尽管预测可以涉及数据值预测和类标记预测，通常预测限于值 预测，并因此不同于分类预测也包含基于可用数据的分布趋势识别。 ( 4 ) 聚类 数据的聚类分析是根据使类内部的相似性最大，而使类间的相似性最小化的 9 第2 章数据挖掘和聚类分析 原则将一组数据分组( 没有预先定义的类属性) 这种将实际的或抽象的对象分 成相似对象的类的分组过程叫做聚类。聚类分析有利于在大量对象集合上建立有 意义的划分，而这种划分是一种分而治之的方法，即将大规模的系统分解成较小 的组成部分以简化设计和实现。聚类也便于分类编制，将观察到的内容组织成类 分层结构，把类似的事件组织在一起。 ( 5 ) 依赖建模 依赖建模用于发现反映变量间非平凡依赖关系的模型。依赖模型逻辑上由结 构层和量化层两部分组成。结构层表明的是变量间的局部相互依赖关系，通常以 图形方式描述；而量化层则是对变量间依赖关系强弱的定量描述。利用依赖建模 可以从某一对象的信息推断另一对象的信息。 ( 6 ) 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这 些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常 而丢弃。然而，在一些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那 些更有趣。孤立点数据分析称作孤立点挖掘( o u t i i c rm i n i n g ) ( 7 ) 演变分析 数据演变分析( e v o l u t i o n a n a l y s i s ) 描述行为随时间变化的对象的规律或趋 势，并对其建模。尽管也包括了时态数据的分类、聚类和关联分析等，但时间序 列数据分析、序列或周期模式匹配和基于相似性的数据分析等是进化分析区别于 其它方法的特征。 2 2 聚类分析概述 聚类分析【1 l 是数据挖掘中一种非常重要的技术和方法，是数据挖掘的主要任 务之一。聚类是把一组个体按照相似性划分成若干个类别，跟平常说的“物以类 聚”相似。聚类分析就是使用聚类算法来发现有意义的类，主要依据是把相似的 样本划分为一类，而把差异大的样本区分开来，这样所生成的簇是一组数据对象 的集合，这些对象与同一簇中的对象彼此相似，而与其他簇的对象彼此相异在 应用中经常把一个簇中的数据对象当成一个整体来对待。 定义2 1 簇( c l u s t e r ) ：一个数据对象的集合。在同一簇中，对象具有相似 l o 第2 章数据挖掘和聚类分析 性，不同簇中，对象之间是相异的。 定义2 2 聚类分析( c l u s t e r i n ga n a l y s i s ) ：把一个给定的数据对象集合分成不 同的簇，即在空间z 中给定一个有限的取样点集或从数据库中取得有限个例子 的集合，协 乍1 聚类的目标是将数据聚集成类，使得类间的相似性最小，而 类内的相似性尽可能得大。 2 2 1 主要聚类方法的分类 目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的 目的和应用。大体上，主要的聚类算法可以划分为如下几类： ( 1 ) 划分的方法( p a r t i t i o n i n gm e t h o d ) 给定一个以个对象或元组的数据库，一个划分方法构建数据的k 个划分，每 个划分表示一个聚类簇，并且七席。也就是说，它将数据划分为k 个组，同时 满足如下的要求：( i ) 每个组至少包含一个对象；( 国每个对象必须属于且只属于 一个组。注意在某些模糊划分技术中，第二个要求可以放宽。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一 种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的 一般准则是：在同一个类中的对象之间尽可能“接近”或相关，而不同类中的对 象之间尽可能“远离”或不同。还有许多其他划分质量的评判标准。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上， 绝大多数应用采用了以下两个比较流行的启发式方法：( i ) 卜平均算法，在该算 法中，每个簇用该簇中对象的平均值来表示。( i i ) 卜中心点算法，在该算法中， 每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法，对在中小规模 的数据库中，发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复 杂形状的聚类，基于划分的方法需要进一步的改进。 ( 2 ) 层次的方法( h i e r a r c h i c a lm e t h o d ) 层次的方法对给定的数据对象集合进行层次的分解。根据层次的分解如何形 成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法， 一开始将每个对象作为单独的一个组，然后相继合并相近的对象或组，直到所有 的组合并为一个( 层次的最上层) ，或者达到一个终止条件。分裂的方法，也称 1 1 第2 章数据挖掘和聚类分析 为自顶向下的方法，一开始将所有的对象置于一个簇中在迭代的每一步中，一 个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终 止条件。 层次方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤销。 这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较小。 但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层 次聚类的结果：( i ) 在每层划分中，仔细分析对象间的“联接”，例如c u r e 和 c h a m e l e o n 中的做法。( 动综合层次聚类和迭代的重定位方法。首先用自底向上 的层次算法，然后用迭代的重定位来改进结果。例如在b i r c h 中的方法。 ( 3 ) 基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状 的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类 方法，其主要思想是：只要临近区域的密度( 对象或数据点的数目) 超出某个阈 值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域 中必须包含一定数目的点。这样的方法可以用来过虑“噪音”孤立点数据，发现 任意形状的簇。 d b s c a n 是一个有代表性的基于密度的方法，它根据一个密度阈值来控制 簇的增长。o p t i c s 是另一个基于密度的方法，它为自动的和交互的聚类分析提 供一个聚类顺序。 ( 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 这两种算 法既是基于网格的，又是基于密度的。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟 合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚 第2 章数据挖掘和聚类分析 类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪音”数据或孤立点， 从而产生健壮的聚类方法。 一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算法划分 为属于某类聚类方法是很困难的。此外，某些应用可能有特定的聚类标准，要求 综合多个聚类技术。现有的许多基于网格的聚类算法都综合了基于密度和基于网 格的方法。下面我们就来详细的介绍一些基于密度和基于网格的具有代表性的聚 类算法。 2 2 2 基于密度的聚类算法 基于密度的聚类方法将数据空间的高密对象区域看成是簇，这一个个簇是被 低密度区域分割开来的，这些簇所代表的区域就称为一个聚类。这类方法的代表 算法有：d b s c a n 、o p t i c s 、d e n c l u e 等。 ( 1 ) d b s c a n 算法 d b s c a n ( d e n s i t yb a s e ds p a t i a lc l u s t e r i n go fa p p l i c a t i o n sw i t hn o i s e ) 2 1 1 是一 个基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带 有“噪音”的空间数据库中发现任意形状的聚类。它定义簇为密度相连的点的最 大集合。 为了能够理解基于密度的聚类算法，必须掌握一些有关密度的相关概念，例 如：e 邻域、核心对象、密度可达、密度相连等。 给定对象半径e 内的区域称为该对象的。邻域。 如果一个对象的e 邻域至少包含有最小数目m m p t s 个对象，则称该对象 为核心对象。 给定一个对象集合d ，如果p 在鼋的e - 领域内，而目是一个核心对象， 我们说对象p 从对象日出发是直接密度可达的。 如果存在一个对象链p j ，p 2 ，西，p l - - - - q ，西= p ，对p ，三d ，( 1 = f 铆) ， p f 州是从印关于c 和m i n t 砸直接密度可达的，则对象p 是从对象口关于 e 和m i n p t s 密度可达的。 如果对象集合d 中存在一个对象o ，使得对象p 和鼋是从。关于e 和 m i n p t s 密度可达的，那么对象p 和q 是关于e 和m i n p t s 密度相连的。 1 3 第2 章 数据挖掘和聚类分析 密度可达是直接密度可达的传递闭包，这种关系是非对称的。只有核心对象 之间是相互密度可达的。然而，密度相连性是一个对称的关系。 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含 在任何簇中的对象被认为是“噪音”。 d b s c a n 通过检查数据库中每个点的e 邻域来寻找聚类。如果一个点p 的 c 邻域包含多于m n p t s 个点，则创建一个以p 作为核心对象的新簇。然后， d b s c a n 反复地寻找从这些核心对象密度可达的对象，这个过程可能涉及一些 密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。 如果采用空间索引，d b s c a n 的计算复杂度是o ( n l o g ( n ) ) ，这里的n 是数据库 中对象的数目否则，计算复杂度是d m 勺。该算法对用户定义的参数是敏感的。 ( 2 ) o p t i c s 算法 尽管d b s c a n 能根据给定输入参数e 和m i n p t s 对对象进行聚类，它仍然将 选择能产生可接受的聚类结果的参数值的责任留给了用户。事实上，这也是许多 其他聚类算法存在的问题。对于真实的高维数据集合而言，参数的设置通常是依 靠经验，难以确定。绝大多数算法对参数值是非常敏感：设置的细微不同可能导 致差别很大的聚类结果。而且，真实的高维数据集合经常分布不均，全局密度参 数不能刻画其内在的聚类结构。 为了解决这个问题，提出了o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n g s t r u c t u r e ) 聚类分析方法。o p t i c s 没有显式地产生一个数据集合簇，它为自动 和交互的聚类分析计算一个簇次序( c l u s t e r o r d e r i n g ) 。这个次序代表了数据的基 于密度的聚类结构。它包含的信息，等同于从一个宽广的参数设置范围所获得的 基于密度的聚类。 考察d b s c a n ，我们可以看到，对一个恒定的m n p t s ，高密度的( 即较小 的e 值) 聚类结果被完全包含在根据较低密度所获得的密度相连的集合中。记住 参数e 是距离，它是邻域的半径。因此，为了生成基于密度聚类的集合或次序， 我们可以扩展d b s c a n 算法来同时处理一组距离