（计算机应用技术专业论文）聚类与孤立点检测算法的研究和实现.pdf

摘要 数据挖掘是在海量的数据中提取隐含的、未知的、潜在有用的知识或信息模 式的决策支持方法。聚类与孤立点检测是其中的重要组成部分。算法的两个重要 评价标准是算法的可伸缩性及算法的精度。 本文的研究内容来源于科技部的资助项目数据挖掘系统s c o p e m i n e r ，该系统 集成了数据挖掘算法研究的最新成果，开发自主产权的数据挖掘工具。聚类与孤 立点检测子系统是挖掘系统s c o p e m i n e r 中的一部分，它集成了两类高效、高精度 的聚类与孤立点检测算法。本文设计与实现了基于网格的聚类算法和基于密度的 聚类与孤立点检测算法。在此基础上，实现了聚类与孤立点检测子系统。 基于网格的聚类算法是一种有效处理低维海量数据的算法，对高维数据集效 率较低。本文分析了现有的基于网格的聚类方法的特点及适用范围，提出了基于 c d t r e e 的聚类分析算法c d t ，设计了两种剪枝优化策略以提高算法的效率。通 过在真实与人工数据集一卜的测试，验证了c d t 算法的有效性。 提出一种新的基于密度的聚类算法，具有两个方面的优势：第一，算法利用 线性回归分析方法发现密度区域变化的边界，对同一个密度区域中的点利用 d b s c a n 算法进行聚类，从而获得了多密度级别的类；第二，算法结合了d b s c a n 算法和孤立点检测算法l o f 可以同时进行聚类和检测孤立点。利用真实数据集与 人工数据集对算法进行了测试，验证了算法的有效性。 集成以上聚类与孤立点检测算法，设计与实现了聚类与孤立点检测子系统。 介绍了子系统主要的数据结构、算法实现流程，利用真实数据集展示了子系统的 使用方法。 【关键字】数据挖掘聚类分析孤立点检测 c d t r e e 聚类与孤立点检测算法的研究和实现 a b s t r a c t s t u d ya n di m p l e m e n t a t i o no fc l u s t e r i n ga n do u t l i e rd e t e c t i o na l g o r i t h m s l i uj u n l i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o ry ud o n g w a n gd a l i n g d a t am i n i n gi sad e c i s i o n s u p p o r ta p p r o a c ht h a t e x t r a c t s h i d d e n ，u n k n o w n ， p o t e n t i a l l yu s e f u lk n o w l e d g ea n dp a t t e r nf r o mh u g ev o l u m eo fd a t a c l u s t e r i n ga n d o u t l i e rd e t e c t i o na lei m p o r t a n ta r e a si nd a t am i n i n g t om e e tt h e r e q u i r e m e n to f d i s c o v e r i n gk n o w l e d g ei nv e r ym a s s i v ed a t a s e te f f i c i e n t l y ，t h ea l g o r i t h m so fd a t a m i n i n ga r er e q u i r e dt oh a v ee x c e l l e n ts c a l a b i l i t ya n dh i g hc l u s t e r i n ga c c u r a c y t h e 鲥d - b a s e da p p r o a c h c a r ld e a lw i t hm a s s i v el o w - d i m e n s i o n a ld a t a s e t s e f f i c i e n t l y ，w h i c he f f i c i e n c yi sl o wf o rh i g h d i m e n s i o n a ld a t a s e t s t h i st h e s i ss t u d i e s p r e v i o u sc l u s t e r i n ga p p r o a c h e sb a s e do ng r i d ，a n a l y z e st h e i rc h a r a c t e r i s t i ca n df i t n e s s ， a n dt h e np r o p o s e sac l u s t e r i n ga l g o r i t h mb a s e do nc d t r e e ，c a l l e dc d t t w op r t m i n g s t r a t e g i e s a r e d e v e l o p e d t o i m p r o v et h ee f f i c i e n c yo fc d tf u r t h e r e x t e n s i v e e x p e r i m e n t so nr e a la n ds y n t h e t i cd a t a s e t sa l s ot e s t i f yt h a tc d ti sb e t t e rt h a to t h e r c l u s t e r i n ga l g o r i t h m sb a s e do ng r i d an e wd e n s i t y b a s e da l g o r i t h mi sp r o p o s e d i tc a l lf i n dt h eb o u n d a r yo fd e n s i t y c h a n g eu s ；n gb yli n e a rr e g r e s s i o n , a n dg e tm u l t i 1 e v e lc l u s t e r sb yd b s c a nt oc l u s t e r t h ed a t ao b j e c t si ns a m ed e n s i t ya r e a sf u r t h e r m o r e ，t h ea l g o r i t h mc a p g e to u t l i e r se e h e n c l u s t e r i n gb yi n t e g r a t i n gd b s c a na n do u t l i e rd e t e c t i o na l g o r i t h m ( l o f ) e x p e r i m e n t s o nr e a la n ds y n t h e t i cd a t a s e t sa l s os h o wt h ev a l i d i t yo f a l g o r i t h m s t h ec l u s t e r i n ga n do u t l i e rd e t e c t i o na l g o r i t h m sa r ei n t e g r a t e di n t ot h ed a t am i n i n g s y s t e m s c o p e m i n e r t h et h e s i si n t r o d u c e sd a t as t r u c t u r e su s e di nt h es y s t e ma n df l o w c h a r t so fa l g o r i t h m ss h o wt h eu s a g em e t h o do ft h es y s t e mb ys y n t h e t i cd a t a s e t s k e y w o r d s d a t am i n i n g c l u s t e r i n ga n a l y s i s o u t l i e rd e t e c t i o nc d t r e e 引言 引言 数据挖掘( d a t am i n i n g ) 是近几年来随着数据库和人工智能发展起来的- - 1 7 新 兴的数据库技术。它是从大量的、不完全的、有噪声的、模糊的、随机的数据中 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程【i 】。 随着海量数据搜集的可能、计算机处理技术的增强和先进数据挖掘算法的提出， 数据挖掘技术不仅能对过去的数据进行查询和遍历，而且能够找出过去数据之间 潜在有价值的联系，并以一定的形式表现出来，从而极大的满足了人们对知识的 迫切需求，也为企业、商家的决策者提供了有效的决策支持。 聚类分析是一种“物以类聚的方法，是按照属性值把一组对象划分成一系 列有意义的子集的描述性任务。聚类的目的就是要将一组数据分组，而这种分组 要基于以下原理：即满足最大的组内相似性和最小的组间相似性，使得不同聚类 中的数据尽可能地不同，而同一聚类中的数据尽可能地相似。 f 前，聚类分析是数据挖掘领域的主要课题之一。作为一种基本的数据挖掘方 法，聚类分析广泛地应用于相似搜索、顾客群划分、模式识别、趋势分析等领域 中。聚类算法在金融投资、地理信息系统、卫星图像和信息检索等领域有着广泛 的应用。例如：在交易数据库中，顾客一次购买的商品( 数据项) 构成了一条交易， 将经常同时购买的数据项聚类到一起有利于改善商品的布置，提高销售利润。类 似地，电予商务在每天的日常、世务中，都会产生大量数据。这螳信息被w e b 服务 器自动收集并存储在访问同志中，经过处理转换为交易数据库。分析这些信息能 帮助销售商确定相对同定的顾客群，制定商品的销售方案，评价各种促销活动的 有效性。在天文学方面，研究人员利用聚类分析宇宙仿真系统得到的数据，更好 地理解黑洞形成和进化的物理过程。可见，聚类分析的用途徙常广泛。 与聚类分析不同，孤立点检测是发现“小的模式 ，发现与大多数对象不同 的对象【2 l 。它也是数据挖掘中一个重要组成部分，在很多应用里，例外事件常常比 普通的事件更有意义。孤立点检测大多用于电信和信用卡诈骗检测、贷款审批、 医药研究、天气预报、电子贸易中的犯罪活动检测等方面。些聚类算法j 叮以排 除孤立点，但不能用聚类算法来检测孤：迂点。孤立点检测有螳特定的要求，如 孤立点的孤立程度不同，则意义不同，所以需要单独的孤立点检测算法对3 进行 处理。 本文的研究背景是科技部的资助项目数据挖掘系统- s c o p e m i n e r 。该项目力图 集成数据挖掘最新的研究成果，开发一套自主知识产权的数据挖掘工具。本文所 研究的聚类与孤立点检测算法是系统的一个模块。通过对各类聚类与孤立点检测 聚类与孤立点检测算法的研究和实现 算法的研究，对算法的选择采用了两个基本原则：( a ) 算法要有较好的聚类质量； ( b ) 算法要有较高的执行效率。依据以上原则本文设计了两种聚类算法：一是优化 的基于网格的高效聚类算法；另一个是聚类质量较好的基于密度的聚类算法。所 设计的基于密度的聚类算法中可以同时发现孤立点检测。 在众多的数据挖掘方法中，基于网格的方法是一种相对高效的处理海量数据 的数据挖掘方法。这种方法主要应用于聚类分析算法与孤立点检测算法中。然而， 现有的基于网格的方法存在两个方面的问题：第一，该方法适用的数据维数相对 较低；第二，在一些基于网格的数据挖掘方法中，如基于单元的聚类算法，划分 的粒度越细聚类的精度越高，而粒度越细生成的单元数越多，算法的效率也会下 降。 在基于网格的聚类算法方面，分析现有的基于网格的聚类方法的特点及适用 范围，提出了基于c d t r e e 的聚类分析算法c d t ，设计了两种剪枝优化策略以提 高c d t 算法的效率：基于分支结点数据点总数的剪枝策略和基于分支结点数据对 象个数最大值剪枝策略。通过分析这两种优化方法的适用条件，本文认为当数据 维数相对较高时，这两种优化算法有优势。通过在真实与人工数据集上的测试， 也验证了c d t 算法优于其它同类方法。 基于密度的聚类可以发现任意形状的类，其聚类精度相对较高。提出一种基 于密度的聚类新算法，解决两个方面问题：第一，算法对数据对象的k 一邻居距离 进行排序，利用线性回归分析方法发现密度区域变化的边界，对同一个密度区域 中的点利用d b s c a n 算法进行聚类，从而获得了多密度级别的类；第二，算法结 合基于密度的算法d b s c a n 和孤j 立点检测赞法l o f 可以在实现聚类的同时检测 孤立点。利用真实数据集与人工数据集对算法进行了测试，验证了算法的有效性。 论文后续部分的组织结构如下： 第一章，相关技术。在本章中，概述了数据挖掘中聚类与孤立点检测相关方 法；分析与评估了现有的聚类算法。 第二章，一种优化的基于网格的聚类算法。在本章中，采用基于空间网格索 引结构，设计了优化的基于网格的聚类算法。 第三章，一种可发现多密度层次的聚类与孤立点检测算法。在本章中，提出 了一种新的基于密度的聚类算法，该算法可以实现多密度层次的聚类，同时可以 检测出孤立点。 第四章，聚类与孤立点检测子系统的设计与实现。在本章中，介绍了聚类与 孤立点检测子系统的设计与实现，同时针对一个具体应用介绍了聚类算法的使用 方法。 第五章，结论。总结全文。 2 第一章相关技术 第一章相关技术 本论文研究的是数据挖掘中的聚类及相关技术，重点为聚类分析与孤立点检 测算法的研究。本章将就后面各章中所涉及的一些内容，在相关概念与技术方面 进行讨论，包括聚类算法概述和孤立点检测算法概述。 1 1 数据挖掘概述 数据库和数据库技术在这信息爆炸中扮演着一个关键角色。传统上，数据库 系统仅仅是用来辅助商业数据处理的，许多的d b m s 研究工作也是集中于这个方 向。但是，最近出现了许多新的应用，知识发现，数据挖掘，数据仓库( d a t a w a r e h o u s e ) 就是其中一部分。 人们很早就认识到应从海量的数据中归纳发现知识。7 0 年代就提出了知识发 现，我们在1 9 8 9 年提出了机器向历史学习，近年来研究者用了更形象更现实的概 念，即“数据挖掘”。 知识发现是一个众多学科诸如人工智能、机器学习、模式识别、统计学、数 据库和知识库、数据可视化等相互交叉、融合所形成的一个新兴的且具有广阔前 景的领域。 数据挖掘的诞生是人们对数据库技术进行长期研究和开发的结果，而数据挖 掘技术发展的同时又反过来促使数据库技术进入了一个更高级的阶段。传统的数 据环境基本上是数据操作型的，传统的信息系统只负责数据的增加、删除及修改 操作，而在数据库的基础上百i 实现彤! 工作就是联机事务处理( o n l i n et r a n s a c t i o n p r o c e s s i n g ，o l i p ) 。现在由于数据积累的不断增多，人们需要分析型的数据环境， 于是就出现了由数据库导出的数掘仓库，以此为罐础则可以实现联机分析处理 ( o n l i n ea n a l y t i c a lp r o c e s s i n g ，o l a p ) 。随着海量数据搜集的可能、计算机处理技 术的增强和先进数据挖掘算法的提出，数据挖掘技术不仅能对过去的数据进行查 询和遍历，而且能够找出过去数据之间潜在有价值的联系，并以一定的形式表现 出来，从而极大的满足了人们对知识的迫切需求，也为企n k 、商家的决策者提供 了有效的决策支持。 1 1 1 数据挖掘方法分类 数据挖掘主要是利用各种知识发现算法从数据库数据中发现有关的知识，根 据发现的知识的不l 问种类，可以将数据挖掘的目标分为以下几类： 1 特征( c h a r a c t e r i z a t i o n ) 。从与学习任务相关的一组数据中提取出关于这些数 聚类与孤立点检测算法的研究和实现 据的特征式，这些特征式表达了该数据集的总体特征。 2 区分( d i s c r i m i n a t i o n ) 。通过对学习数据和对比数据的处理，提取出关于学习 数据的主要特征，这些特征可以将学习数据与对比数据分开来。例如：通过对某 种疾病与其他疾病的症状的比较，可以提取出该疾病相对于其他疾病的区分规则， 利用这些规则就可以区分出这种疾病。 3 分类( c l a s s i f i c a t i o n ) 。根据数据的不同特征，将其划归为不同的类，这些类 是事先利用训练数据建立起来的。例如：利用当前的病例数据可以建立各种疾病 的分类规则。对于新的病人，根据其症状及分类规则，可以知道疾病的种类。 4 关联规贝a ( a s s o c i a t i o nr u l e ) 。是发现数据对象间的相互依赖关系，一个关联 规则的形式为：彳l 八彳2 八彳一b l 八硬八毋。如果b l 、伤日出现，那么么卜 a 2 彳，一定出现，这表明数据彳l 、么2 彳，和数据鼠、历马有着某种联系。 例如：在对疾病状的研究过程中，人们也许会发现，某些症状的出现一定会伴随 其他一些症状的出现，通过对这种现象的深入研究，也许会找到攻克疾病的方法。 5 聚类( c l u s t e r i n g ) 。根据所处理的数据的一业属性，对这批数掘进行分类，这 种分类是基于当前所处理的数据。经过分类以后的数据，在各类之问其相似程度 很小，而在某一类内部，其数据的相似度则很大。分类结束后，每类中的数据由 唯一的标志进行标识，类中数据的共同特征也被提取出来用于对该类的特征描述。 例如：可以通过对一组新型疾病的聚类，形成每类疾病的特征描述，这样可以对 这些疾病进行识别。 6 预测( p r e d i c t i o n ) 。通过刘数据的分析处理，估计数据库中某些丢失数据的可 能值或一个数据集中某种属性值的分布情况。一般是利用数学统计的方浊，找出 与所要预测的属性相关的属性并根据相似数据的分析估算属性值的分布情况。例 如：根据同一单盥内其他职工的二l 二资，可以预测某一职工的可能工资。 上面我们介绍了数据挖掘的主要目标，下面我们介绍数据挖掘所使用的主要 方法： 1 数学统计方法。使用这种方法一般是首先建立一个数学模型或统计学模型， 然后根据这种槿型提取出有关的知识。例如：可由训练数据建立一个b a y e s i a n 网， 然后，根据该网的一些参数及联系权值提取出相关的知识。 2 机器学习疗法。大多数机器学习方法是利用人类的认知模型模仿人类的学 习方法从数据中提取知识，由于机器学习经过多年的研究，已取得了一些较满意 的成果，因此在k d d 中可以利用目前已经比较成熟的机器学习方法。 3 面向数据库方法。随着数据库技术的发展，其中的一些数据处理方法不断 完善并趋于成熟。在k d d 中，利用现有的一些启发式方法，可以提取出数据库中 的一些特征知识。 4 第一章相关技术 4 混合方法。上述各种方法各有其优缺点，为提高k d d 的效率，可将各种方 法有机地结合在一起，取长补短，以发现更有价值的知识。 5 其他方法。除了上述方法以外，还有其他一些方法，如数据可视化技术， 知识表示技术等等。 1 1 2 数据挖掘的主要研究问题 数据挖掘的主要研究问题从以下几个方面考虑：挖掘方法和用户交互，性能 问题及各种数据类型的多样性问题1 1 1 。 1 挖掘方法和用户交互问题方面 在数据库中挖掘不同类型的知识； 多个抽象层的交互知识挖掘； 结合背景知识； 数据挖掘查询语言和特定的数据挖掘； 数据挖掘结果的表示和显示； 处理噪声和不完全数据； 兴趣度问题。 2 性能方面 数据挖掘算法的有效性和可伸缩性： 并行、分布式和增量挖掘算法。 3 关于数据库类型的多样性问题 关系f 内和复杂的数据类型的处理； 由异种数据库和全球信息系统挖掘信息。 1 2 聚类分析算法概述 聚类分析方法是数据挖掘的重要手段之一，广泛应用到各个领域中。聚类的 定义是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。聚 类问题可以这样描述：给定一组数据兄把它划分成一组聚类( c l u s t e r ) ： * ，x 2 ，。 尥 ，x 兄使得不同聚类中的数据尽可能地不相似而同一聚类中的数据尽可能地 棚似。如果七= l 或j j = 凶，则称为平凡聚类。聚类方法一般分为：划分方法1 3 刮，层 次方法【7 12 1 ，基于密度的方法1 1 4 - 1 引，基网格的方法f 1 9 2 3 1 和基于模型的方法等。 聚类分析的结果主要是经验性的，使用不同的聚类分析法可以有极不相同的 结果，对所做出的结果重复性也差，特别是从统计理论上难以判断某个聚类结果 是否正确。 给定”个有限的数据对象集x ( 或从数掘库q 1 取得有限例子的集合) ，聚类的 聚类与孤立点检测算法的研究和实现 目标是将数据聚集成类，使得类问的相似性尽量小，而类内的相似性尽量大。分 类问题和聚类问题根本的不同是：分类问题中，我们知道训练例的分类属性值， 而在聚类问题中，就需要我们从训练例中找到这个分类属性值。 把数据库中的对象集合分割成一组聚类是数据挖掘的基本操作，可以用于分 类，数据缩减，预测。在数据挖掘领域中，由于要处理非常大而复杂的数据集， 所以对传统的聚类方法提出一个最基本要求：算法的效率要满足大数据集的大数 量、高复杂度、增量的要求。 1 2 1 数据挖掘对聚类典型要求 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各种特殊的要求， 我们列出了数据挖掘对聚类的典型要求【l 】。 1 可伸缩性 聚类要处理的数据量通常是十分巨大的，可能达到数十亿( g i g a b y t e s ) 、万亿 ( t e r a b y t e s ) 、甚至千万亿( p e t a b y t e s ) 字节。超大规模的数据库要求有效的、快速的 聚类算法，其运行时间必须可预测且可接受的，时间复杂度为指数或多项式的算 法不具有实用价值。 2 处理不同数据类型的能力 许多方法被设计用来聚类数值类型的数据。但是，应用可能要求聚类其它类 型的数据，如二元型、序数型、分类标称类型。 3 能发现任意形状的聚类 r l j 于聚类的具体特征在分析前一般是未知的，聚类l 】丁能是球形的、狱k 形的、 凹形的、嵌套的、中空的等任意复杂的形状和结构，这就要求聚类算法能发现任 意形状的聚类。 4 对于输入纪录的顺序不敏感 某些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合，当以 不同的顺序提交给同一个算法时，可能产生差别很大的聚类结果。开发对数据输 入顺序不敏感的算法具有重要意义。 5 基于约束的聚类 现实世晃的应用可能需要在各种约束条件下进行聚类。 6 最少的参数和确定参数值的领域知识 几乎所有的聚类算法都包含或多或少的参数，例如聚类的密度和个数等，这 些预先给定的参数值在很大程度上决定了聚类的结果。如果参数值不符合数据的 分布特征，算法就不能获得好的结果。而在实际应用中，合适的参数值很难确定。 因此，用户希望算法能依据某种原则或领域知识估订参数的最佳取值。 6 第一章相关技术 7 有效地识别噪声数据 噪声在大规模的和高维的数据库中尤其普遍。许多领域要求聚类算法具有识 别噪声的能力。在某些特殊应用中，噪声的识别甚至比聚类的发现更有实际意义， 例如在电子商务中发现非友善的恶意行为可以有效地减少损失。 8 可理解的结果 数据挖掘的结果要求用户能够理解所发现的知识，有效地评价这些知识，区 分哪些是有用的，那些是常识的或孤立的情况。聚类结果的描述一直是个困难的 问题，特别是对于高维数据来说。可视化技术把高维数据映射到低维空间，通过 直观的图形方式将模式呈现给用户，使用户可以交互地分析数据。但是多数可视 化技术不适合维数过高的数据空间。另一类方法是用简单抽象的形式描述聚类， 例如d n f ( 范式) 。该方法的优点是不受维数的限制，缺点可能是把形状不规则的聚 类分割成若干区域，使得表达式过于复杂。另外，还可以利用决策树得到聚类的 规则及相关的统计信息，但对形状不规则的聚类同样很难得到简单的规则。 9 处理高维数据 高维空间中对象之间的关系变得更加复杂，该问题一直是聚类领域的研究难 点。足否可以有效处理高维数据是衡量一个聚类算法优劣的标准之一。 l o 动态性 组合爆炸导致搜索空删指数级地增长，因此高维数据的应用钡域的数据火都 是动态的，随时间不断变化的，先前发现的知识可能过时，如果不进行更新，就 会导致决策错误。目前大多数聚类算法只能处理静态数据，当数据更新后，算法 需要从大开始执行得到新的模式：要处理动态数据，特别是动态系统中周期性变 化的数据，就必须形f 究增量聚类算法，当数据改变时，算法可以对发现的模式加 以修正。 1 1 联机支持 目前的聚类算法一般都遵循这样的步骤：给定算法和参数值，处理数据库， 得到聚类。如果等聚类完成之后，才发现结果不理恕，修改参数值，重新开始聚 类，就无疑造成了极大的资源浪费。在联机方式下，系统随时地反馈聚类过程中 每一个步骤的中间结果，用户监督聚类的进行情况，随时调整参数值，并能按照 意愿随时终止。 1 2 并行和分布的聚类算法 由于聚类算法通常具有很高的时间复杂度，而现实的数据库容量巨大，因此 聚类过程需要相当长的等待时间。随着网络的普及，信息的分布性增强，聚类的 并行算法和分布算法越来越多地受到重视。 1 3 空间数掘的聚类 聚类与孤立点检测算法的研究和实现 大多数聚类算法以点为处理对象，但空间中的对象通常是由若干个点、线、 面构成的区域。传统的方法是把它们转变成点，但这会失去某些空间关系。空间 对象之间相交、覆盖等关系使计算对象间的距离更加困难。 1 2 2 典型聚类算法 本节按照聚类的原理和方法对众多的聚类算法进行分类。层次聚类和划分聚 类是两类最常用的聚类方法，基于密度的聚类和网格聚类在效率上有了显著提高， 还有其它的方法，如基于模型的聚类、因素分析和基于图的聚类等。 在聚类分析中，目前已出现了许多适用于各种数据类型和不同应用的算法， 这些算法一般可以分为如下几类i l 】： 1 层次方法( h i e r a r c h i c a lm e t h o d ) 。对给定的数据对象集合进行层次分解。具体 可采取凝聚的方法，即将每个对象视为一个簇，相继合并相近的簇构成更大的新 簇，直至达到一个终止条件。也可采取分裂的方法，即将所有的对象视为一个簇， 然后相继分裂不相近的簇为若干个更小的新簇，直至满足终止条件。 2 划分方法( p a r t i t i o n i n gm e t h o d ) 。给定一个m 个对象的数掘集，在其上构建胛 个划分，每个划分表示一个簇，且月脚。同时满足：首先，每个簇至少包含一个 对象：其次，每个对象属于且只属于个簇。 3 基于密度的方法( d e n s i t y b a s e dm e t h o d ) 。这类方法根据每个簇的密度阈值、 而不是簇的数目闽值控制聚类的过程，即只要临近簇的密度超过某个闽值，就继 续聚类，聚类终止的条件是满足密度要求。 4 基j 二网格的方法( g d ：，a s e dm e t h o d ) 。这类方法将对象：己间量化为有限数目 的单几。形成一个网格结构，所有的聚类操作均红此h 格结构| 二进行。 5 基于模型的方、法( m o d e l b a s e dm e t h o d ) 。为每个簇假定一个模型，寻找数据 对给定模型的最佳拟合。 事实上，在实际应用中，根据具体应用领域的聚类要求，聚类方法常常要综 合多种聚类技术。 1 2 2 1 层次聚类方法 层次聚类方法递归地对对象进行合并或者分裂，直到满足某一终止条件。层 次聚类的结果可以用一个谱系图( 或二分树) 表示( 如图1 1 ) ，树中的每个节点都是 一个聚类，下层的聚类是上层聚类的嵌套，每一层节点构成一组划分。根据谱系 图生成的顺序，我们可以把层次聚类方法分为合并型层次聚类和分解型层次聚类 两种。合并型层次聚类从单成员聚类开始，把它们逐渐合并成更大的聚类，在每 一层中，相距最近的两个聚类被合并。相反，分解型层次聚类从包含所有对象的 2 第一章相关技术 一个聚类开始，把它逐渐分解成更小的聚类1 6 1 。 0s t e p 1s t e p2 s t e p 3s t e p4s t e p 合并 分解 4s t e p3s t e p2s t e pls t e p0s t e p 图1 1 层次聚类法 给定刀个对象的数捌集合咒合并型层次聚类得到x 的一系列划分：咒，1 ， x 。蜀有刀个单成员聚类，只有1 个聚类，它包含所有的对象。合并型层次聚 类及产生谱系图的基本步骤有【7 】 1 计算刀个对象两两之间的距离； 2 构造刀个单成员聚类蜀，恐，每一类的高度都为0 ； 3 找到两个最近的聚类x ，五，合并石和，聚类的个数减少l ，以被合并的 两个类的间距作为上层的高度； 4 计算新类与本层中其它类的间距，如果满足终止条件( 聚类的个数或最小间 距) ，算法结束，否则转步骤2 。 各种合并型层次聚类算法的基本步骤相同，它们的差别在于聚类间的距离的 定义不同。两个聚类间距离的计算方法主要有：最小距离、最大聚类间距离、类 平均距离、中心距离等等。 层次方法要求用户给定一个合并或分解的终止条件，例如聚类的个数或者两 个聚类间的最小距离。层次聚类的优点在于算法能得到不同粒度上的多层次聚类 结构，缺点在于时间复杂度比较高。另外，上述每种聚类间距都有其缺陷，或旨 用于形状规则、大小近似的聚类( 如中心距离) ，或者容易受噪声的影响( 如最小距 离) 。 c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ) 】采用了抽样和分区的技术。首先刘 数据随机抽样，把样本划分成若干个分区，在每个分区内部进行局部聚类，得到 9 聚类与孤立点检测算法的研究和实现 固定数目的局部聚类。然后，对所有的局部聚类进行全局聚类。为了克服各种距 离的缺陷，c u b e 用一定数目的代表表示一个聚类。先从一个聚类中选取均匀分布 的一些点，再按照一定的比例把它们向聚类中心收缩，以保证这些代表点既能反 映聚类的形状又避免噪声的干扰。由于不同分区的数据分布不同，难以对所有的 分区确定一个公共的恰当的阈值。如果一个分区中的数据来自多个聚类，那么应 该给该分区赋一个较大的阈值，相反，如果一个分区中的数据来自少数几个聚类， 那么应该给该分区赋一个较小的阈值。因此每个分区中的聚类的个数应该足够大， 使得只有属于同一个聚类的对象才会被合并。c u r e 只存储了每个聚类的代表作为 全局聚类的输入，使全局聚类能在内存中执行。 在以往的算法中，两个对象之间的距离或相似性只与这两个对象本身有关， 而与其它对象无关，所以又称为局部距离。r o c k ( r o b u s tc l u s t e r i n gu s i n gl i n k s ) 1 1 0 j 将这一局部运算扩展成一种全局运算，在计算两个对象的距离或相似性时，不仅 考虑两个对象本身，还考虑周围邻居的影响，增强了算法的抗噪声能力。如果两 个对象都与某些对象相邻，这些公共邻居称为连接。连接的个数越大，对象间的 相似性越火，属于同一个聚类的可能性也越大。为了能够处埋大规模的数据，算 法采用了随机抽样的力法。s b a c 1 2 l 算法把生物学的分类方法引入聚类问题中，在 计算对象间的相似性时，对某些特殊的特征值赋予较高的权值。 1 2 2 2 划分聚类方法 给定聚类数目k 不j 目标函数f ，划分聚类算法把x 划分成k 个类，使得目标函 数存此划分下达到最优。划分算法把聚类问题转，七成一个组合优化问题，从一个 初始划分或者一个初始中心集合开始，利用迭代控制策略优化目标函数。最常j h 月 的f i 标函数是m i r , d ( x ，m ，) ，其q 俄7 是墨的中心俅m e a n s 剪 ，：) 3 1 ，或者暑 = ij = j 。 中离中心最近的一个对象( 七m e d o i d s ) 。典型的划分方法有p a m ( p a r t i t i o n i n g a r o u n d m e d o i d s ) t 4 1 、c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o n sb a s e do nr a n d o m i z e d s e a r c h ) t 5 】等。图1 2 描述了划分算法的基本框图，其中前三个步骤有各种方法，通 过组合可以得到不同的划分算法。 划分算法一般要求所有的数据都装入内存，限制了它们在大规模数据上的应 用。它们还要求用户预先指定聚类的个数，但在大多数实际应用中，最终的聚类 个数是未知的。另外，划分算法只使用某一固定的原则来决定聚类，这就使得：当 聚类的形状不规则或者大小差别很大时，聚类的结果不能令人满意。 1 0 第一章相关技术 选择中心 l i 7 初始划分 i 修改划分 上 j 划分是否 丫 最终划分 图1 2 划分聚类算法的框图 k - m e a i l s 算法是最流行的聚类算法之一。它首先随机地选取k 个初始聚类中心， 并把每个对象分配给离它最近的中心，从而得到一个初始聚类。然后，计算廿j l 当 前每个聚类的重心作为新的聚类中心。如果新的聚类的质量优于原先的聚类，则 用新聚类代替原先的聚类。循环执行这一过程直至聚类质量不再提高为止。之后， 许多变形的算法在基本的肛m e a n s 算法的基础上，在以下方面作厂改进，例如：如 何选择初始聚类中心、如何计算下次循环的聚类中心以及用可能性密度代替距离 公。弋等。缸m e a n s 算沼i 的中心足虚拟的，并不是数据库中确实存在的) ( 、! 象。 肛m e d o i d s 算法用中心对象( m e d o i d ) 代替中，l = ( m e a i l s ) 。它首先随机地选择k 个 对象作为中心对象，把每个对象分配给离它最近的中心对象。聚类的迭代过程就 是中心对象和非中心对缘反复替换过程直到目标函数值不再有改进为止。 l e a d e 一侈j 聚类要求预先确定控制聚类大小的阈值6 。算法为每个聚类确定一个 l e a d e r ，保证任意对象与所属的聚类l e a d e r 的距离不超过l 一6 。算法顺序读入对 象，计算它与每个聚类l e a d e r 的距离，如果最近距离不超过1 6 ，则把它赋给距 离最近的聚类。否则以该对象为l e a d e r 创建一个新的聚类。该法的优点在于简单 易行，只扫描一次数据库，占用的内存空间小。但是，读入数据的顺序影向聚类 的结果，而对象赋值原理使第一个聚类总是有优先权。聚类的数目山6 决定，6 取 值越小，得到的聚类的个数就越大。l e a d e r 聚类算法用于分析w w w 上的文档， 发现用户的访问模式。 c l a r a n s 算法是第_ 个用于空间数据库的聚类算法。c l a r a n s 融合了p a m 和c l a r a 的优点，只j ! ；7 索局部数据，但不局限于固定的搜索空间。它可以看作是 l l 聚类与孤立点检测算法的研究和实现 图的搜索算法，图中每个节点代表一个解，即危个中心对象( m e d o i d s ) 。如果两个 节点包含肛1 个相同的中心对象，则称它们是相邻的，互为邻居。给定访问邻居的 最大个数以及重复迭代的最大次数，算法随机地选取k 个对象作为当前的中心对 象集，每次迭代随机地把一个中心对象替换为非中心对象得到一个相邻的中心对 象集，如果新的聚类的质量优于原先的聚类，则用新的中心对象集代替原中心对 象集，否则进行下一次替换。如果已经搜索了最大个数的邻居，聚类质量都没有 提高，则算法得到了一个局部最优解。重新开始这一过程，得到一组局部最优解， 取其中聚类质量最高的解作为最终解。c l a r a n s 仍然具有和其他划分算法同样的 缺点，如要求数据装入内存、得到的只是局部最优解、结果受初始值的影响等。 1 2 2 3 基于密度的聚类方法 以空间中的一点为中心，单位体积内点的个数称为该点的密度，从直观来看， 聚类内部点的密度较大，而聚类之间点的密度较小。基于密度的聚类根据空间密 度的差别，把具有相似密度的点作为聚类。由于密度是一个局部概念，这类算法 又称为局部聚类( l o c a lc l u s t e r i n g ) 。基于密度的聚类通常只扫描一次数据库，所以 又称为单次扫描聚类( s i n g l es c a nc l u s t e r i n g ) 。 对于空间中的一个对象，如果它在给定半径e p s 的邻域中的对象个数大于某 个给定的数值m i n p t s ，则该对缘被称为核心对象( c o r ep o i n t ) ，否则称为边界对象。 由一个核心对象密度可达的所有对象构成一个聚类。 d b s c a n t 3 1 从任一刘象p 开始，根抓参数e p s 和m i n p t s 提取所有从p 密度可 达的对象。如果p 是核心对象，则从p 可达的所有对象被标志，、j 当前类，并从它 们进一步扩展。如果p 是一个边界对象，那么p 被标记为噪声，算法提取卜一个 对象进行处理。算法依次进行下去，直至找到一个完整的聚类。然后再选择一个 新的起始刘象开始扩展，得到下一个聚类，直到所有的对象都玻标志为止。在进 行聚类之前，d b s c a n 首先为对象建立r 宰树，提取邻域对象是通过对r 树进行 区域查询得到的，! 习此d b s c a n 的平均时间复杂度为o ( n l o g n ) 。 d b s c a n 的显著特点是聚类速度快，能处理噪声以及发现任意形状的空间聚 类。但该算法存在以下缺点：( 1 ) 为了确定参数e p s 和m i n p t s ，必须计算每个对象 与它的第k 个邻居之间的距离，将结果按距离排序，绘制k - d i s t 图。图中的点伍， 少) 代表上述距离为工的对象个数为y 。这个过程非常耗费时问，尤其对大规模数据 库而言。用户必须反复实验，选择合适的参数值以达到较好的聚类效果。( 2 ) d b s c a n 用固定的参数识别聚类，当聚类的稀疏程度不同时，如果用相同的判定 标准就可能破坏聚类的自然结构。若根据较密的聚类选取较小的e p s ，对于相对稀 的聚类的对象，他们邻域中的数据对象可能小于m i n p t s ，即这些对象不是核心对 1 2 第一章相关技术 象，不会进一步扩展，结果是较稀的聚类被划分成多个聚类；相反，若根据较稀 的聚类选取较大的e p s ，那些离得较近且密度较大的聚类将被合并成同一个聚类。 ( 3 ) d b s c a n 的聚类定义以两种关系为基础：密度连通和密度可达，前者是对称非 传递的，后者是传递非对称的，定义中存在的极大性和连通性的矛盾可能会把一 个连通的聚类分割成两个聚类。 另外，许多其他算法也对d b s c a n 作了改进：如g d b s c a n ( g e n e r a l i z e d d b s c a n ) 1 1 4 1 、 d b c l a s d ( d i s t r i b u t i o n b a s e d c l u s t e r i n g o f l a r g es p a t i a l d a m b a l s e ) t 1 5 1 、o p t i c s l i 6 1 等等。 空间索引结构把空间中距离近的点存储在磁盘上同一个数据页或者相邻的数 据页中。这些索引结构或者为聚类算法提供效率上的支持( d b s c a n ) 或者作为聚类 过程的预处理( f o c u s e dc l a r a n s ) 。许多聚类算法用到邻居或最近邻居的查询操 作，它的时间复杂度决定了聚类算法的复杂度。例如，d b s c a n 的效率由区域查 询的效率决定：如果区域查询的时间复杂度为o ( 1 ) ( 数据采用低维光栅结构或网格 文件存储) ，那么整个聚类算法的时间复杂度仅为o ( 刀) 。如果区域查询的平均时间 复杂度为o ( 1 0 9 n ) ( 如低维空间中的r 宰一t r e e ) ，那么整个聚类算法的时间复杂度为 o ( n l o g n ) 。如果区域查询的时间复杂度为o ( ，) ( 如高维数据空间中r 幸t r e e 的效率下 降) ，那么整个聚类算法的时间复杂度为o ( n 2 ) 。 1 2 2 4 基于网格的聚类方法 网格文件( g r i df i l e ) 2 4 l 把l 维空间的哈希方法( l a s h i n g ) 扩展到k 维空间，用来 组织和管理多维守问的数据。它将数据空间划分为若：f 单元，每一维上分割点的 位置信息存储在数组中，分割线贯穿整个空间。s c h i k u t a 提出了一个基于网格的层 次聚类算法【1 9 1 ，根据数据存储在网格文件中的位置进行聚类。该过程包括5 个步 骤：( 1 ) 创建网格结构；( 2 ) 计算网格单) 己密度；( 3 ) 网格数据页( b l o c k s ) 排序；( 4 ) 识别聚类中心；( 5 ) 相邻页的搜索和合并。 w a v e c l u s t e r 2 l 】首次把小波变换的原理引入聚类研究中，使聚类的边界变得清 晰，聚类更容易识别。它的基本步骤是首先把数据映射到一个多维网格中，再对 网格单元进行小波变换，通过搜索连通分支得到聚类。w a v e c l u s t e r 处理大规模数 据的效率高，不受数据输入顺序的影响，具有处理噪声的能力，而且能发现复杂 结构，例如凹形或嵌套结构，或形状1 i 规则的聚类，还可