（计算机软件与理论专业论文）基于网格的聚类算法和孤立点技术的研究.pdf

郑州大学硕士学位论文 基于网格的聚类算法和孤立点技术的研究 摘要 数据挖掘就是从大量的数据中提取有趣的非平凡的，蕴涵的，先前未知 的、而且是潜在有用的信息模式。它是根据人们的特定要求，从浩如烟海的数据 中找出所需的信息来，供人们的特定需求使用。据国外专家预测，随着数据量的 日益积累和计算机的广泛应用，在今后的5 一1 0 年内，数据挖掘将在中国形成一 个新型的产业。 聚类分析是数据挖掘中一项重要的技术。聚类的任务是把数据集中的对象组 成多个有意义的子类，在同一子类中的对象彼此相似，不同子类中的对象不相似。 从另外一个角度看待聚类分析就是孤立点的检测技术，其研究对象是数据集中偏 离绝大多数对象的很小一部分数据。在许多k d d 应用中，研究孤立点比研究聚类 更有用、更重要。因为，在某些应用领域中研究孤立点的异常行为能发现隐藏在 数据集中更有价值的知识。 聚类和孤立点检测是两个相辅相成的方面，在聚类的过程中要决定如何处理 孤立点的问题，寻找孤立点有时要使用一些聚类的方法。人们通过聚类或孤立点 的分析，识别密集的或稀疏的区域，从而发现全局的分布模式，以及数据属性之 间有趣的相互关系。目前的聚类技术和孤立点检测技术已经广泛应用在如数据挖 掘、统计学、机器学习、空间数据库技术、生物学以及入侵检测和天气预报等等 相关领域中，取得了很大的成功和实用价值。 本文在分析了基于网格的聚类算法的思想和方法的同时，针对目前网格算法 存在的一些缺陷提出了基于覆盖网格的聚类算法。并通过综合数据集上和真实数 据集上做了大量的对比实验来验证其算法的正确性。试验结果表明：基于覆盖网 格的聚类算法能够准确，有效的发现任意形状，大小的聚类。同时在执行效率和 精度上也比其它的聚类算法更加合理有效。 同时，在分析研究现有的基于密度的孤立点检测算法基础上，针对其性能和 精度上的不足，提出了一种新的度量方法局部偏差系数和基于局部偏差系数的孤 立点检测算法。实验结果表明：该算法在发现孤立点的技术上对于同一类基于密 度的孤立点检测算法在性能和质量上都具有很大的优势。 关键词：数据挖掘，聚类分析，孤立点检测，网格划分，空间覆盖，局部偏差率， 局部偏离系数 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 a b s tr a c t t h ep r o c e s so fd i s c o v e r i n gi n t e r e s t i n g , u s e f u la n dp r e v i o u s l yu n k n o w n k n o w l e d g ef r o mv e r yl a r g ed a t a b a s ei s k n o w n 勰d a t am i n i n g b a s e do ns t e a l r e q u e s tb yp e o p l e d a t am i n i n gc 蚰r e t r i e v et h ei n f o r m a t i o nt h a ti so nd e m a n df r o ma m a s so fd a t a s e tf o ru s eb yp e o p l e a sf o r e c a s t e db yf o r e c a s te x p e r t ：w i t ht h e d e v e l o p m e n ta b o u tc o m p u t e rt e c h n o l o g ya n da c c u m u l a t i o na b o u td a t a , d a t am i n i n g w i l lb e c o m ean g wi n d u s t r ya f t e rf i v eo rt e ny e a r si nc h i n a c l u s t e r i n ga n a l y s i sh a sb e c o m e a 1 1 i g h l ya c t i v et o p i ci nt h ed a t am i n i n gr e s e a r c h i t st a s ki st h ep r o c e s so f g r o u p i n gt h ed a t ai n t oc l a s s e so rc l u s t e r ss ot h a to b j e c t sw i t h - 一i nac l u s t e rh a v eh i g hs i m i l a r i t yi nc o m p a r i s o nt oo n ea n o t h e r , b u ta r ev e r yd i s s i m i l a r t oo b j e c t si no t h e rc l u s t e r s f r o mt h eo t h e rv i e w , c l u s t e r i n ga n a l y s i si sj u s ta so u t l i e r d e t e c t i o n ，t h er e s e a r c ho b j e c t sa r ev e r ys m a l ld a t at h a td e v i a t ef r o mt h eo t h e rl a r g e d a t a s e t f o ra p p l i c a l i o 鹤s u c h 勰d e t e c t i n gc r i m i n a la c t i v i t i e so fv a r i o u sk i n d s ( e gi n e l e c t r o n i cc o m m e r c e ) ，r a r ec 、嘲坞d e v i a t i o n sf r o mt h em a j o r i t y , o re x c e p t i o n a lc 邵e s m a y b em o r ei n t e r e s t i n ga n du s e f u lt h a nt h ec o m m o n c 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 r es u p p l ye a c ho t h e r , w en e e dt od e c i d eh o wt o d e a lw i t l lo u t l i e r sw h e nc l u s t e r i n g ；, a tt h es a m et i m e , d e t e c t i n go u t l i e ra l s on e e dh a sa k n o w l e d g ea b o u tc l u s t e r i n gs o m et i m e p e o p l eu s 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 n t e c h n o l o g yt oi d e n t i f yd e n s ea r e ao ri s o l a t ea r e a , a n df i n a l l yf i n dd i s t r i b u t e dp a t t e r n w h e na l lc o m e st oa l l ，t h ei n t e r e s t i n gr e l a t i o n s h i pa m o n gd a t aa t t r i b u t e s n o w a d a y s ， c 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 r ew i d e l ya p p l i e dt o t h ef i e l d ss u c h 鹊p a t t e m r e c o g n i t i o n , d a t am i n - 一i n g , m a c h i n el e a r n i n g , s p a c ed a t a b a s et e c h n o l o g y , b i o l o g y , i n - b r e a kd e t e c t i o na n dw e a t h e rf o r e c a s t ，m a k eah u g es u c c e s sa n dc r e a t eh i g hv a l u e 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 sa n di no r d e rt o r e s o l v et h ed e f e c t st h a ti th a s ，w ee d v a n c es u p p l ya na l g o r i t h mb a s e do no v e r l a p p i n g g r i da n dh a v 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 e c o r r e c t n e s so fg r i dc l u s t e r i n g , t h ee x p e r i m e n to ns y n t h e t i cd a t a s e t sa n dr e a ld a t a s e t 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 ，o g b ca l g o r i t h m sc a nb em o r en i c e l ya n d e f f i c i e n t l yi d e n t i 匆c l u s t e r 研t l la n ys h a p e so rs i z ea n dh a sm o r ee f f e c t i v e l yt h a n o t h e r sa l g o r i t h m so np e r f o r m a n c ea n d p r e c i s i o n a tt h es a m et i m e ，a n a l y s i so ft h ee x i s t i n gd e n s i t yb a s e do nt h eo u t l i e rd e t e c t i o n i l 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 a l g o r i t h m , b a s e do ni t sp e r f o r m a n c ea n dt h ea c c u r a c yo ft h es h o r t f a l l ，t h i sp a p e r p r e s e n t san e wo u t l i e rd e t e c t i o na l g o r i t h mb a s e do nl o c a ld e v i a t i o nc o e f f i c i e n tf a c t o r t h er e s u l t ss h o w e d ：t h ea l g o r i t h ma b o u to u t l i e rd e t e c t i o nf o rt h es a m et y p eo f t e c h n o l o g yb a s e d o i lt h ed e n s i t yo f t h eo u t l i e rd e t e c t i o na l g o r i t h mi np e r f o r m a n c ea n d q u a l i t yh a sb i ga d v a n t a g e k e yw 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 n , o v e r l a p p i n gg r i d , l o c a ld e v i a t i o nr a t i o ，l o c a ld e v i a t i o nc o e f f i c i e n t 1 i i 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 1 1 研究背景与意义 第1 章引言 由于计算机术和存储技术的飞速发展，使人们在短时间里就可以从各种来源 搜集和存储大量的人工难以管理的资料。虽然现代数据库技术可对这些资料进行 有效地的存储，但人类还需要一种技术以帮助人们分析、理解甚至可视化这些资 料。因此就产生了k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 技术。它是一个 从较低资料中抽取高级知识的总体过程，就是从数据库中识别有效地、新颖地、 潜在有用地并、最终可被理解的模式地一个非平凡过程。k d d 包括很多内容，其 核心部分就是数据挖掘( d a t am i n i n g ) 。近十多年来，数据挖掘逐渐成为数据库 和人工智能等研究领域的一个热点方向。 聚类是把一组个体按照相似性归成若干类别，即“物以类聚”。它的目的是 使得属于同一类别的个体之间的距离尽可能的小而不同类别上的个体间的距离 尽可能的大。聚类的结果可以得到一组数据对象的集合，我们称其为簇。簇中的 对象彼此相似，而与其它簇中的对象相异。在许多应用中，可以将一个簇中的数 据对象作为一个整体来对待。 聚类技术中对待个体的另一种角度就是孤立点检测，孤立点检测的研究对象 是数掘集中偏离绝大多数对象的很小一部分数据。在许多k d d 应用中，研究孤立 点比研究聚类更有用、更重要。因为，在某些应用领域中研究孤立点的异常行为 能发现隐藏在数据集中更有价值的知识。因此，孤立点检测是一个重要的数据挖 掘任务，称为孤立点挖掘或异常挖掘。 聚类和孤立点检测是两个相辅相成的方面，在聚类的过程中要决定如何处 理孤立点的问题，寻找孤立点的过程有时也可以使用一些聚类的方法缩小数据 集的范围。人们通过聚类或孤立点的分析，识别密集的或稀疏的区域，从而发现 全局的分布模式，以及数据属性之间有趣的相互关系。目前的聚类技术和孤立点 检测技术已经广泛应用在如数据挖掘、统计学、机器学习、空间数据库技术、生 物学以及入侵检测和天气预报等等相关领域中，取得了很大的成功和实用价值。 基于网格的聚类技术是聚类技术中一个重要的技术方向。其基本思想是首先 通过将数据空间的每一维平均分割成等长的区间段，从而将数据空间分成不相交 的网格单元，同一单元的数据点属于同一类的可能性比较大，所以落入同一网格 中的数据点可被看作一个对象进行处理，以后所有的聚类操作都是在网格单元上 郑州大学硕士学位论文 基于网格的聚类算法和孤立点技术的研究 进行。因此，基于网格的聚类过程与数据点的个数无关，只与网格的个数有关系， 聚类的效率得到很大的提高，但网格聚类算法对参数的依赖性较大，同时，网格 聚类算法对于高维数据的处理存在很大的制约性，因为其划分网格的技术而导致 的“维度灾难”问题一直是网格算法的最大“性能瓶颈”。 基于密度的孤立点算法现在是孤立点挖掘中一个十分热的方向。其基本思想 就是在局部的空间中利用k 距离邻居的概念赋予每个对象局部的孤立因子。从而 找到局部范围内的孤立点。但是现存的孤立点检测技术都存在一些性能上的问 题：1 ) ：通常在检测到少数孤立点以前，需要大量的计算数据集中每个对象的局 部可达距离和局部可达密度：2 ) 现在的孤立点挖掘算法的时间复杂度都是 o ( 1 ( n 2 ) ，而其中的k 值往往取的十分大，才能更好的发现出孤立点。这样在性能 上就显在有很大的缺陷。 所以，对于网格聚类算法和孤立点检测算法的研究一直有着广阔的发展空 问，今后将会在更多的领域中发挥作用。 1 2 研究内容与思路 针对上面的分析，本文就以下内容进行了研究： 1 在对数据挖掘理论和网格聚类算法的研究的基础上，提出了基于覆盖网格 的聚类算法。 在系统的研究了数据挖掘理论和网格聚类算法的基础上，提出更快的高效的 覆盖网格聚类算法。并在综合数据集和真实数据集上进行了测试，最后给出实验 结果，同时也分析了该算法的时间复杂度。 2 提出了基于局部偏差系数的孤立点检测算法( l d c - m i n e ) 算法和增强性算 法( e l i ) c - m i n e ) 算法。 在系统的研究了孤立点检测算法的基础上，提出了一个新的度量因子一局部 偏差系数( l d c ) 和基于局部偏差系数的孤立点检测算法和增强性算法，并在综 合数据集和真实数据集上进行了测试，最后给出试验结果，同时分析了该算法的 时间复杂度。 1 3 论文组织与结构 路。 本文分为五章，具体的组织如下： 第1 章主要阐述了课题研究的背景与意义，并概要的说明研究的内容和思 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 第2 章系统性的分析了数据挖掘，网格聚类理论和孤立点挖掘理论，在分析 网格聚类技术和孤立点挖掘技术的基础上，介绍了一些常见的基本网格的聚类算 法和孤立点挖掘算法，并分析了这些算法的优点和缺点。 第3 章在研究了传统网格聚类算法的基础上，提出了基于覆盖网格的聚类算 法，并将该算法在综合数据集和网络入侵数据集上进行测试，最后给出试验结果， 同时分析了算法的时间复杂度和空间复杂度。 第4 章在研究了孤立点检测算法的基础上，提出了一个新的度量因子一局部 偏差系数( l d c ) 和基于局部偏差系数的孤立点检测算法和增强性算法，并在综 合数据集和真实数据集上进行了测试，最后给出试验结果，同时分析了该算法的 时间复杂度和空间复杂度。 第5 章对前面的研究工作进行了总结与展望，给出了本文的主要创新点，并 提出了今后的研究方向。 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 第2 章数据挖掘和算法分析 2 1 数据挖掘概述 随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的 数据急剧增加，可是用于对这些数据进行分析处理的工具却很少。目前数据库系 统所能做到的只是对数据库中已有的数据进行存取和简单的操作，人们通过这些 数据所获得的信息量仅仅是整个数据库所包含的信息量的很少的一部分，隐藏在 这些数据之后的更重要的信息是关于这些数据的整体特征的描述及对其发展趋 势的预测，这些信息在决策生成的过程中具有重要的参考价值。这就引起了对强 有力的数据分析工具的急切需求。快速增长的海量数据收集、存放在大型和大量 数据库中，没有强有力的工具，理解它们已经远远超出了人的能力。 面对这种挑战，数据库中的知识发现( k d dk n o w l e d g ed i s c o v e r yi n d a t a b a s e s ) 技术逐渐发展起来。k d d 就是从大量、不完全、有噪声的异质模糊 数据中挖掘隐含的潜在有用知识的过程，它不但能够学习已有的知识，而且又可 以发现未知的规律。同时，k d d 也是一门新兴的交叉学科，汇聚了数据库、人工 智能、统计、可视化和并行计算等不同领域的研究人员。 一般将k d d 中进行知识学习的阶段称为数据挖掘( d a t am i n i n g ) ，它是整个 数据库中的知识发现过程中一个非常重要的处理环节，所以两者往往混用。一般 而占，在数据库、统计和数据分析等工程应用领域称为数据挖掘，而在a i 和机 器学习界等研究领域人们则称之为数据库中的知识发现。本文将不加区分地使用 两者。 2 1 1 数据挖掘概念 知识发现k d d 是指从大量数据中提取出可信的、新颖的、有效的、潜在有用 的并能被人理解的模式的非平凡处理过程【l i 。这种处理过程是一种高级的处理过 程。 在上述定义中，数据是指有关事实的集合，记录和事物有关的原始信息。模 式是一个用语言来表示的一个表达式，它可用来描述数据集的某个子集。我们所 说的知识，是对数据包涵的信息更抽象的描述。对大量数据进行分析的过程，包 括数据准备、模式搜索、知识评价，以及反复的修改求精。该过程要求是非平凡 的，意思是要有一定程度的智能性、自动性( 仅仅给出所有数据的总和不能算作 是一个发现过程) 。有效性是指发现的模式对于新的数据仍保持有一定的可信度。 4 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 新颖性要求发现的模式应该是新的。潜在有用性是指发现的知识将来有实际效 用，如用于决策支持系统里可提高经济效益。最终可理解性要求发现的模式能被 用户理解，目前它主要体现在简洁性上翻。 2 1 2 数据挖掘过程 数据挖掘过程可粗略地分为按需选择数据、数据集成、数据预处理、数据转 换、挖掘过程以及模式评估和知识表示等口, 4 , 5 , 6 1 。 图2 1 数据挖掘的过程 ( 1 ) 数据选择 从数据源中检索与分析任务相关的数据。 ( 2 ) 数据集成 建立目标数据集。根据数据挖掘目标，从原始数据中选择相关数据集，并将 不同数据源中的数据集成起来，以确定数据挖掘的操作对象，需要解决平台、操 作系统和数据类型不同产生的数据物理格式差异。 ( 3 ) 数据预处理 数据集中不可避免地存在着不完整、不一致、不精确和重复的数据，这些数 据统称为脏数据。数据抽取之后须利用领域专门知识对脏数据进行清洗。通常采 用基于规则的方法、神经网络方法和模糊匹配技术分析多数据源数据之间的联 系，然后再对它们实施相应的处理。 5 郑州大学硕士学位论文 摹于网格的聚类算法和孤立点技术的研究 ( 4 ) 数据转换 根据分析任务目标，选用关键特征表示数据，并将数据通过汇总或聚集等操 作转换为适于数据挖掘处理的形式。 ( 5 ) 挖掘算法 使用智能方法提取数据模式。这些方法包括概括、分类、回归和聚类等。 ( 6 ) 模式评估 采用有关方法对数据挖掘发现的模式进行评价，根据某种兴趣度度量，识别 表示知识的真正兴趣的模式。 ( 7 ) 知识表示 使用可视化和知识表示技术，向用户提供挖掘的知识，帮助用户理解发现的 模式。 由上述过程可知，整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘 途中发现选择的数据不太好，或使用的挖掘技术产生不了期望的结果，这时，用 户需要重复先前的过程，甚至从头重新开始。 基于这种观点，加拿大华裔科学家j i a w e ih a n 提出典型的数据挖掘系统具有 以下主要成分( 如图2 2 ) i t ： ( 1 ) 数据库、数据仓库或其它信息库这是一个或一组数据库、数据仓库、 电子表格或其它类型的信息库。可以在数据上进行数据清理和集成。 ( 2 ) 数据库或数据仓库服务器根据用户的数据挖掘请求，数据库或数据 仓库服务器负责提取相关数据。 ( 3 ) 知识库这是领域知识，用于指导搜索，或评估结果模式的兴趣度。 这种知识可能包括概念分层，用于将属性或属性值组织成不同的抽象层。用户信 念方面的知识也可以包含在内。可以使用这种知识，根据意外性评估模式的兴趣 度。领域知识的其它例子有兴趣度限制或阂值和元数据。 ( 4 ) 数据挖掘引擎这是数据挖掘系统的基本部分，由一组功能模块组成， 用于特征化、关联、分类、聚类分析以及演变和偏差分析。 ( 5 ) 模式评估模块通常，此成分使用兴趣度度量，并与数据挖掘模块交 互，以便将搜索聚焦在有趣的模式上。它可能使用兴趣度阈值过滤发现的模式。 模式评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实 现。对于有效的数据挖掘，建议尽可能深地将模式评估推进到挖掘过程之中，以 便将搜索限制在有兴趣的模式上。 ( 6 ) 图形用户界面本模块在用户和数据挖掘系统之间通信，允许用户与 系统交互，指定数据挖掘的任务，提供信息、帮助搜索聚焦，根据数据挖掘的中 6 郑州大学硕士学位论文 基于网格的聚类算法和孤立点技术的研究 问结果进行探索式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓库模 式或数据结构，评估挖掘的模式，以不同的形式对模式可视化。 图2 2 典型的数据挖掘系统结构 2 1 3 数据挖掘功能 数据挖掘的功能反映了数据挖掘算法发现的模式的种类。根据履行功能的不 同，我们将数据挖掘问题分为数据概括、联接分析、分类、聚类、依赖建模、孤 立点分析以及演变分析等几个类别。 ( 1 ) 数据概括 数据库数据是最基本的信息，不能满足不同层次的用户希望从不同的层次和 角度对数据进行处理或浏览的需求。数据概括是一种把数据库数据从低层次抽象 到高层次的过程，换言之，就是对数据进行浓缩，用紧凑形式重新对其进行表示。 ( 2 ) 关联分析 关联分析用于重新建立数据对象之间业已存在的隐含联系，这种联系有关联 规则和序列模式两种表现形式。关联规则反映的是同时频繁出现的数据对象之间 的蕴涵关系，序列模式表明的是时态数据中频繁出现的事件序列。 ( 3 ) 分类 数据分类是根据一个分类模型，在数据库中的对象集合中找到一些共同的属 性，并把它们分成不同类型的过程。其目的在于根据历史数据自动创建能预测未 来行为的分类规则。分类规则反映的是属性数据对象和类别标识之间的因果关 系。在分类问题中，待产生的类别的数目是事先知道的，而且，训练数据中同时 包含有属性数据和类别标识数据。 7 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 ( 4 ) 聚类 数据的聚类分析是根据使类内部的相似性最大，而使类问的相似性最小化的 原则将一组数据分组( 没有预先定义的类属性) 。这种将实际的或抽象的对象分 成相似对象的类的分组过程叫做聚类。聚类分析有利于在大量对象集合上建立有 意义的划分而这种划分是一种分而治之的方法，即将大规模的系统分解成较小 的组成部分以简化设计和实现。聚类也便于分类编制，将观察到的内容组织成类 分层结构，把类似的事件组织在一起。 ( 5 ) 依赖建模 依赖建模用于发现反映变量间非平凡依赖关系的模型。依赖模型逻辑上由结 构层和量化层两部分组成。结构层表明的是变量问的局部相互依赖关系，通常以 图形方式描述；而量化层则是对变量间依赖关系强弱的定量描述。利用依赖建模 可以从某一对象的信息推断另一对象的信息。 ( 6 ) 孤立点分析 数据库中可能包含一些数据对象，它们与数掘的一般行为或模型不一致。这 些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常 而丢弃。然而，在一些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那 些更有趣。孤立点数据分析称作孤立点挖掘( o u t l i e rm i n i n g ) 。 ( 7 ) 演变分析 数据演变分析( e v o l u t i o nh n a l y s i s ) 描述行为随时问变化的对象的规律或 趋势，并对其建模。尽管也包括了时态数据的分类、聚类和关联分析等，但时间 序列数据分析、序列或周期模式匹配和基于相似性的数据分析等是进化分析区别 于其它方法的特征。 2 2 聚类算法综述 聚类分析一直是数据挖掘中一项重要的技术。通常来说，聚类和孤立点检测 是两个相辅相成的方面，在聚类的过程中要决定如何处理孤立点的问题，寻找孤 立点也要使用一些聚类的方法。人们通过聚类或孤立点的分析，识别密集的或稀 疏的区域，从而发现全局的分布模式，以及数据属性之间有趣的相互关系。目前 的聚类技术和孤立点检测技术已经广泛应用在如数据挖掘、统计学、机器学习、 空间数据库技术、生物学以及入侵检测和天气预报等等相关领域中，取得了很大 的成功和实用价值。 在本节中，我们大致简介了一些目前在聚类研究和孤立点检测研究中出现的 8 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 著名的算法。聚类算法大体上可分为：基于划分的方法、基于层次的方法、基于 密度的方法、基于网格的方法、基于模型的方法。其中，基于网格的聚类算法由 于其能发现任意形状、大小的聚类，聚类效果高等优点而受到很大的关注。我们 主要以介绍基于网格的聚类算法为主，其他相关的聚类方法详情可参阅文献 7 。 而孤立点检测算法大致分为：基于统计学方法、基于距离的方法、基于偏差的方 法和基于密度的方法。而目前的研究热点是基于密度的方法，所以我们把基于密 度的孤立点挖掘算法当作重点介绍，其他的方法也可参阅文献【8 】。 2 2 1 网格聚类算法综述 基于网格的聚类方法采用了网格的数据结构，它将空间量化为有限数目的单 元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。这种方法的主 要优点是处理速度快，其处理时间独立于数据对象的数目，仅依赖于量化空间中 每一维上的单元数目。 基于网格方法包括；s t i n g ，它利用存储在网格单元中的统计信息； w a v e c l u s t c r ，它利用一种小波转换方法来聚类；c l i q u e ，它是在高维数据空间 中基于网格和密度的聚类方法；s c i 等。 ( 1 ) s t 烈g s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 9 1 是一种基于网格的多分辨率聚类技术， 它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩 形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的 单元。关于每个网格单元属性的统计信息( 例如平均值、最大值和最小值) 被预 先计算和存储。这些统计信息对于下面描述的查询处理是有用的。 高层单元的统计参数可以很容易地从低层单元的计算得到。这些统计参数包 括：属性无关的参数c o u n t ；属性相关的参数m ( 平均值) ，s ( 标准偏差) ，m i n ( 最小值) ，m a x ( 最大值) ，以及该单元中属性值遵循的分布( d i s t r i b u t i o n ) 类型，例如正态分布、一致分布、指数分布或无( 如果分布未知) 。当数据被装 载进数据库，底层单元的参数c o u n t ，m ，s ，m i n 和m f l x 直接进行计算。如果分 布的类型事先知道，d i s t r i b u t i o n 的值可以由用户指定，也可以通过假设检验 ( 如z 2 检验) 来获得。一个高层单元的分布类型可以基于它对应的低层单元多 数的分布类型，用一个阈值过虑过程来计算。如果低层单元的分布彼此不同，阈 值检验失败，高层单元的分布类型被置为n o n e 。 统计参数的使用可以按照以下自顶向下的基于网格的方法。首先，在层次结 构中选定一层作为查询处理的开始点。通常，该层包含少量的单元。对当前层次 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 的每个单元，我们计算置信度区间( 或者估算其概率范围) ，用以反映该单元与 给定查询的关联程度。不相关的单元就不再考虑。低一层的处理就只检查剩余的 相关单元。这个处理过程反复进行，直到达到底层。此时，如果查询要求被满足， 那么返回相关单元的区域。否则，检索和进一步的处理落在相关单元中的数据， 直到它们满足查询要求。 s t i n g 有几个优点：( i ) 由于存储在每个单元中的统计信息提供了单元中的数 据不依赖于查询的汇总信息，所以基于网格的计算是独立于查询的。( i i ) 网格结 构有利于并行处理和增量更新。( i i i ) 该方法的主要优点是效率很高：s t i n g 扫描 数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是o ( n ) ，其中n 是对象的数目。在层次结构建立后，查询处理时间是o ( g ) ，这里g 是最低层网 格单元的数目，通常远远小于1 1 。 由于s t i n g 采用了一个多分辨率的方法来进行聚类分析，s t i n g 聚类的质 量取决于网格结构的最低层的粒度。如果粒度比较细，处理的代价会显著增加； 但是，如果网格结构的最低层的粒度太粗，将会降低聚类分析的质量。而且， s t i n g 在构建一个父亲单元时，没有考虑孩子单元和其相邻单元的关系。因此， 结果簇的边界要么是水平的，要么是竖直的，没有对角的边界。尽管该技术有快 速的处理速度，但可能降低簇的质量和精确性。 ( 2 ) w a v e c l u s t e r w a v e c l u s t e r 1 0 1 是一种多分辨率的聚类算法，它首先通过在数据空间上强加一 个多维网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换 后的空间中找到密集区域。 在该方法中，每个网格单元汇总了一组映射到该单元中的点的信息。这种汇 总信息适合于在内存中进行多分辨率小波变换使用，以及随后的聚类分析。 小波变换是一种信号处理技术，它将一个信号分解为不同频率的予波段。通 过应用一维小波变换n 次，小波模型可以应用于n 维信号。在进行小波变换时， 数据被变换以便在不同的分辨率层次保留对象间的相对距离。这使得数据的自然 聚类变得更加容易区别。通过在新的空间中寻找高密度区域，可以确定聚类。 小波变换对聚类有如下优点： 它提供了无指导的聚类。它采用了帽形( h a t - s h a p e ) 过虑，强调点密集的区 域，而忽视在密集区域外的较弱的信息。这样，在原特征空间中的密集区域 成为了附近点的吸引点( a t t r a c t o r ) ，距离较远的点成为抑制点( i n h i b i t o r ) 。 这意味着数据的聚类自动地显示出来，并“清理”了周围的区域。这样，小 波变换的另一个优点是能够自动地排除孤立点。 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 小波变换的多分辨率特性对不同精确性层次的聚类探测是有帮助的。 基于小波变换的聚类速度很快，计算复杂度是o ( n ) ，这里n 是数据库中对象 的数目。这个算法的实现可以并行化。 ( 3 ) c l i q u e c l i q u e ( c l u s t e r i n g i nq u e s t ) 【l l 】聚类算法综合了基于密度和基于网格的聚 类方法。它对大规模数据库中的高维数据的聚类非常有效。c l i q u e 的中心思想 如下： 给定一个多维数据点的大集合，数据点在数据空间中通常不是均衡分布 的。c l i q u e 区分空间中稀疏的和“拥挤的”区域( 或单元) ，以发现数 据集合的全局分布模式。 如果一个单元中的数据点的数目超过了某个输入模型参数，则该单元是 密集的。在c l i q u e 中，簇定义为相连的密集单元的最大集合。 c l i q u e 分两步进行多维聚类： 第一步，c l i q u e 将n 维数据空间划分为互不相交的长方形单元，识别其中 的密集单元。该工作对每一维进行。代表密集单元的相交子空间形成了一个候选 搜索空问，其中可能存在更高维的密集单元。 c l i q u e 将更高维密集单元的搜索限制在子空间的密集单元的交集中。这种 方法来自于关联规则挖掘中的先验性质( a p r i o r ip r o p e r t y ) 。一般来说，该性质在 搜索空间中利用数据项的先验知识以便裁减空间。c l i q u e 所采用的性质如下： 如果一个k 维单元是密集的，那么它在k 一1 维空间上的投影也是密集的。也就 是说，给定一个k 维的候选密集单元，如果检查它的k 一1 维投影单元，只要有 一个是非密集的，那么k 维单元也不可能是密集的。因此，可以从k l 维空间 中的密集单元来推断k 维空间中潜在的( 或候选的) 密集单元。通常，最终的结 果空间比初始空间要小很多，然后检查密集单元决定聚类。 在第二步，c l i q u e 为每个簇生成最小化的描述。对每个簇，它确定覆盖相 连的密集单元的最大区域，然后确定最小的覆盖。 c l i q u e 自动地发现最高维的子空间，高密度聚类存在于这些子空间中。 c l i q u e 对元组的输入顺序不敏感，无需假设任何规范的数据分布。它随着输入 数据的大小线性地扩展，当数据的维数增加时，具有良好的可伸缩性。但是，由 于方法大大简化，聚类结果的精确性可能会降低。 ( 4 ) s c i s c i ( s u b s p a c e c l u s t e r i n g b a s e d0 1 1i n f o r m a t i o n ) 【1 2 】聚类算法综合了基于密度 和基于网格的聚类方法。网格的划分方法和c l i q u e 类似，通过对d 维数据集d 郑州大学硕士学位论文 基于网格的聚类算法和孤立点技术的研究 的每个属性上等分得到，首先对各个属性进行排序为 l j ，u j 】j = 1 , 2 ，3 ，4 d 然 后通过k - r e g u l a r 划分分成彼邻的矩形单元格。数据空间被划分为k d 个相同体积 的单元格。所以说网格是均匀划分的。 在聚类子空间中，它通过连接稠密单元格的技术获得簇的大体轮廓。落入每 个单元格中的数据点的总数就看作为该单元格的密度。把单元格分成三种类型， 稠密单元格，稀疏单元格，孤立单元格。先通过熵的定理去除某些对于聚类效果 信息少的属性，然后稠密单元格彼此相连，被稀疏单元格分离，形成簇的轮廓。 而孤立单元格也被稀疏单元格分离，就被看作孤立点集，而稀疏单元格中的点可 能是簇的边界点，也可能是噪音点，需要进一步处理。处理的方法是对待每一个 在稀疏单元格中的数据点，看它离其他单元格最近的是否是什么类型的单元格， 如果是稠密单元格，则把它归为簇中，否则就是噪音数据。最后形成簇。 聚类的基本思想是分为4 个阶段。 l 划分数据空间，单元格的边长k 是输入参数； 2 计算在每个单元格中的点数，然后标识每个单元格的类型； 3 利用熵的定理去除某些属性x j如果i n f o ( x j ) = l 0 9 2 k - i * 或 i n f o ( x j ) 1 ，可得l g q + d l g k _ l g n ，即l g k 。 l g n q ， 所以 - n q = m 一 3 3 算法描述 算法c b o g ( c l u s t e r i n gb a s e do no v e r l a p p i n gg r i d ) 形式化的描述如下； 算法c b o g ： 26 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 输入参数：k ，m _ s u p ： l ：划分：将d 维数据空间划分为边长为e p s ，的超矩形，同时计算每个网格 中的密度，相交网格的网格编号。 2 ：剪枝：删除没有邻居的孤立网格单元，标记和高密网格连接的稀疏网格， 还有孤立的高密度单元判断。 3 ：聚类；连接高密网格形成聚类。 4 ：边界处理：针对稀疏网格的处理，即聚类边界点的处理。最后输出聚类结 果。 c b o g 算法的每个步骤具体描述如下： l ：划分：根据输入的k 值，按照定义1 中的计算方法，计算超矩形每一维 度上的长度e p s i ( 1 f d ，d 为数据的维度) ，为下一步生成超矩形做准备。然后 建立数据空间的网格覆盖。开始时，网格集合为空。从数据集中读取一个数据点， 如果该点不能落入任何一个已有的网格中，按照定义1 建立一个网格，网格的密 度为l ；如果新输入的数据点属于已有的网格，相应的网格密度增加1 同时记 录网格的共享点和具有共享点的网格号。直到数据点全部处理为止。 在划分网格的过程中，先输入的点可能属于后生成的网格，为了防止共享 信息的丢失，需要进行共享点的增补过程。图3 3 就是二维动态网格的生成示意 图 图3 3 二维动态网格生成示意图 2 ：剪枝：遍历所有的网格，根据网格密度d e n ( c ) 标记各个网格的类型。 删除孤立网格，标记稀疏网格为边界处理做准备。 3 ：聚类：根据网格单元中存放的信息查找相交的高密网格单元，采用广度 优先搜索，使用贪心算法的增长模式生成聚类。 在聚类过程中，可能会出现一个高密度的网格单元没有相交的邻居。这种情 27 郑州大学硕士学位论文基于网格的聚类算法和孤立点技术的研究 况可能是在生成网格时，由于参数的设置造成的，它可能属于某个聚类或单独形 成一个小聚类。我们处理的方法是在其每一维上扩大其边长e p s ，4 ，如果它和 高密度网格相交，就把它和高密度网格归于一类。反之就单独形成聚类。 4 ：边界处理：对于每一个稀疏网格，我们找到和它相邻的高密网格，然后 在高密网格的每一维上扩大边长e p s ，4 ，然后对于稀疏网格中的数据对象，逐 一判断该对象是否属于扩大维边长后的新的高密网格。如果属于的话，就把该数 据对象归为高密网格所在的簇中；反之，就认为该数据对象为噪音数据。 该算法由于使用的是动态的网格生成技术。所以它能够克服固定网格划分技 术带来的很多缺陷。如图3 1 ( a ) 中的小聚类丢失现象。如果使用我们的动态生 成技术。那么我们以数据对象为中心点就可以把和它临近的数据对象包含在一 起，避免了该小聚类别不同的网格分开的情况。而对于边界点的处理，如果使用 动态的网格生成技术，那么就会使得边界变得很柔和。当然我们无法避免一些本 属于簇的数据对象落入稀疏网格，然而，我们使用简单的边界处理技术就能够很 好的捕捉到那些簇的边界点。 由于使用的是基于网格技术的聚类。所以输入参数的设置k 和r e _ s u p 还是十 分重要。如果k 的值过于大的话，那么在每一维上划分的区间数就很多，可能就 会出现生成很多小聚类的情况，而不能把他们聚到一起；如果k 的值过于小的情 况，有可能把本不属于一起的类划分到了一个网格中，就区分不开这两个网格， 也就区分不开这两个最终的聚类。ms u p 的设置如果过于大，就会在类中丢失一 些小网格；如果过于小，就可能把一些孤立点也归于大类中，所以说该算法对于 输入参数还是敏感的。 3 4 实验分析 我们的实验环境是i n t e l ( r ) p e n t i u m ( r ) 4c p u2 4 0 g h