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

摘要 摘要 数据挖掘技术可以从大量数据中发现潜在的、有价值的知识，它给人们在信息时代所 积累的海量数据赋予了新的意义。随着数据挖掘技术的迅速发展，作为其重要的组成部分， 网格聚类技术已经被广泛的应用于数据分析、图像处理、市场研究等许多领域。网格聚类算 法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。 本文介绍了数据挖掘理论，对网格聚类算法进行了深入地分析研究。在研究了传统网 格聚类算法的基础上，提出了网格边界处理聚类算法，该算法使用边界处理技术提高了网格 聚类的精度；针对网格聚类算法对参数敏感的问题，提出了一种基于网格的参数自动化聚类 算法，该算法使用参数自动化技术解决了算法对参数敏感的问题；在分析了传统的多密度聚 类算法的基础上，提出了基于网格的多密度聚类算法( g r i d _ b a s e dc l u s t e r i n g 舢g o r i t h mf o r m u l t i d e n s i t y ) ，该算法主要采用密度闽值递减的多阶段聚类技术提取不同密度的聚类，使用 边界点处理技术提高聚类的精度，同时对聚类结果进行了人工干预。 本文使用叭a lc + + 6 0 实现了网格的边界处理聚类算法、参数自动化的网格聚类算法、 基于网格的多密度聚类算法、s n n 算法，做了大量的对比实验，其中包括基下网格聚类的 正确性实验，在综合数据集上的实验，在网络入侵真实数据集的实验以及对均匀密度的数据 集实验等。 实验结果表明，网格边界处理聚类算法可以很好的对边界点进行处理，从而提高了聚 类结果的精度；基于网格的参数自动化技术可以很好的处理传统网格聚类算法对参数敏感的 问题；基丁- 网格的多密度聚类算法不仅能够对数据集进行正确的聚类，同时还能有效的进行 孤立点检测，有效的解决了传统多密度聚类算法中不能有效识别孤立点和噪声的缺陷。基丁 网格的多密度聚类算法比传统的共享近邻s n n 算法精度高，适合于均匀密度数据集、人部分 多密度数据集，并且可以发现任意形状的聚类，对噪声数据和数据输入顺序不敏感，但对小 部分多密度数据集的聚类结果不理想。 摘要 总之，网格边界处理聚类算法提高了聚类的精度，参数自动化技术在一定程度上解决 了网格聚类算法对参数敏感的问题，而基于网格的多密度聚类算法不仅适合于均匀分布的数 据集，而且对多密度数据集基本上也适合。该算法不仅能有效的识别出各种形状的聚类，而 且也能有效的识别出孤立点或噪声，在和传统的共享近邻s n n 算法对比中显示出了一定的优 越性。 关键词：网格聚类；密度阈值递减；多阶段聚类；边界点提取；参数自动化 珏 a b s t 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 sc a nb 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 t a m o u n to fd a t a ，a n di t p l a y san e ws i g n i f i c a n tr o l et ot h es t o r e dd a t ai nt l l ei n f o t i m e s w i t ht h e r 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 fg f i dc l u s t e r i n g ，a si m p o n a n t p a n so fd a t am i n i n g ，a r ew i d e l ya p p l i e dt ot h ef i e l d ss u c ha sp a t t e mr 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 f c ho ng r i dc 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 gr e s e a r c h i n t h i s t h e s i s ，t h ea u t h o rp r e s e n t st h et h e o 巧o fd a t am j n i n g ，a n dd e e p l ya n a l y z e st h e a l g o r i t h m so fg r i dc l u s t e r i n g 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 lg r i dc l u s t e r i n ga l g o f i t h m s ，w e a d v a n c eg r i d - b a s e db o r d e rp o i n t se x t m c t i o na l g o r i t h m ( g b d ) t h a tc a ne n h a n c et h ep f e c i s i o no f 伊i dc l u s t e r i n gb yt h et e c h n i q u eo fb o r d e rp o i n t se x t r a c t i o n ；b a s e do nt h a tt h eg r i d c l u s t e r i n g a 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 s ，w ea d v 柚c ea 鲥d - b a s e dc l u s t e r i n ga l g o r i t b mw j t ht h e p a r a m e t e ra u t o m a t i z a t i o n ( f ! f 崛) t h a tc a ns o l v et h ep r o b l e mt l l a tt h eg r i dc l u s t e r i n ga l g o r i t h mi s s e n s i t i v et op a r a m e t e r 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 a l g o r i t h m sf o rm u l t i d e n s i t y ，w e a d v a n c eag r i d - b a s e dc l u s t e 血ga l g o r i t h mf o rm u l t i d e n s i t y ( g d d ) 1 m eg d d i sak i n do ft h e m u l t i 。s t a g ec l u s t e r i n gt h a ti n t e g f a t e sg f i d - b a s e dc l u s t e r i n g ，t h et e c h n i q u eo fd e n s i t yt h r e s h o l d d e s c e n d i n ga n db o r d e rp o i n t se x t r a c t i o n 1 nt h i st h e s i s ，w eh a v ed e v e l o p e dg b d ，p a gg d da n ds n n a l g o r i t h ma n di m p l e m e n t e di t u s j n g s u a lc + + 6 o w bc o n d u c l e das e r i e so fe x p e f i m e n t s ，i n d 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 f i dc l u s t e r i n g ，t h ee x p e r i m e n to ns ) r l l t h e t i cd a t a s e t s ，t h ee x p e “m e n to nt h er e a l d a t a s e ta n dt h ee x p e f i m e n to nt h ed a t a s e tw i t he v e nd e n s i l y a ss h o w ni ni h ee x p e r i m e n t a lr e s u l t s ，g b da l g o r i t h mc a nd e a lw i t hb o r d e rp o i n t sp r o p e r l y a n di m p r o v et h ep r e c i s i o no fc l u s t e f i n gf e s u l t ；p i a ga 垮o r i t h mc a ns o l v et h ep r o b l e mt h a tt h eg r j d c 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 s ；g d da l g o r i t h mc a nn o to n l yc l u s t e r sc o r r e c t l yb u i f i n do u t l i e r si nt h ed a t a s e t ，a n di t e f f e c t i v e l ys o l v e st h ep r o b l e mt h a tt r a d i t i o n a lg r i da l g o r i t h m s c a nd u s e ro n l yo rf i n do u 1 i e r so n ly t h ep r e c i s j o no fg d d a l g o r i t h mi sb e t t e rt h a nt h a to fs n n t h eg d d a l g o r i i h mw o r k sw e l lf o re v e nd e n s i t yd a t a s e ta n dl o t so fm u l t i d e n s i t yd a t a s e t s ；i tc a n i l l a b s t r a c t d i s c o v e rc l u s t e f so fa r b i t r a r ys h a p e s ；i ti s n ts e n s i t i v et ot h ei n p u to r d e fo f n o i s e sa n do u t l i e r sd a t a ； b u ti ti si m p e e c tt oc l u s t e ro ns o m em u l t i d e n s i t yd a t a s e t s t bs u mu p ，t h eg b da l g o r i t h m i m p r o v e st h ep r e c i s i o no ft r a d i t i o n a lg r i d c l u s t e r i n g a l g o r i t h m s ；t h ei a ga l g o r i t l l i l ls o l v e st h ep r o b l e mt 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 o p a r a m e t e r s ；t h eg d da l g o r i t h mc a nn o to n l yc l u s t e r sc o n e c t l yb u ta l s of i n do u t l i e r si nt h ed a t a s e t t h ep r e c i s i o no fg d d a l g o r i t h mi sb e t t e rt h a nt l l a to fs n n 1 沁yw o r d s ：g r i dc l u s t e r i n g ；d e n s i t yt h r e s h o l dd e s c e n d i i l g ；m u l t i - s t a g ec l u s t e r i n g ；b o f d e rp o i n t s e x t f a c t i o n ；p a r a m e t e ra u t o m a t i z a t i o n l v 郑重声明 y9 7 5 2 本人的论文是我在导师指导下独立撰写并完成的，学位论文没有 剽窃、抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意 承担由此产生的一切法律责任和法律后果，特此郑重声明。 学位论文作者( 签名) ：狮窆 勺吲厂年6 月；日 第1 章引言 第1 章引言 1 1 研究背景与意义 由于计算技术和存储技术的飞速发展，使人们在短时间里就可以从各种来源搜集和存储 大量的人j f ：难以管理的资料。虽然现代数据库技术可对这些资料进行经济的存储，但人类还 需要一种技术以帮助人们分析、理解甚至可视化这些资料。因此就产生了k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 技术。它是一个从较低级资料中抽取高级知识的总体过程，就是从数 据库中识别有效的，新颖的，潜在有用的并最终可被理解的模式的一个非平凡过程。k d d 包括很多内容，其核心部分就是数据挖掘p a t am i n i l l g ) 1 1 。近十多年来，数据挖掘逐渐成为 数据库和人工智能等研究领域的一个热点。 聚类( c l u s t e r i n g ) 是数据挖掘中重要组成部分，所谓聚类就是将数据对象分组成多个 类或簇( c l u s t e r ) ，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。 聚类源于许多研究领域，包括数据挖掘，统计学，机器学习，空间数据库，生物学和市场营 销等。目前它已经被广泛应用于模式识别、数据分析、图像处理和市场分析等。 聚类已经被广泛地研究了许多年，迄今为止，研究人员已经提出了许多聚类算法，大 体上这些算法可以分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方 法、基于模型的方法。 基丁网格的聚类技术首先通过将数据空间的每一维平均分割成等k 的区间段，从而将 数据空间分成不相交的网格单元，同一单元中的点属于同一类的可能性比较人，所以落入同 一网格中的点可被看作一个对象进行处理，以后所有的聚类操作都是在网格单元上进行。冈 此，基丁网格的聚类过程与数据集中数据点的个数无关，只与网格的个数有关系，聚类的效 率得到很人的提高，但网格聚类算法对参数的依赖性较人。 聚类分析所使用的数据集中，各个类的密黛程度往往不尽相同，甚至差别很人。人多 数现有的聚类算法都是致力于如何发现任意形状和大小的类，但很难有效的处理密度差别较 人的数据集。多密度聚类是数据挖掘中的一项重要技术，其目标是发现多密度数据集中的不 同密度的数据对象，将其分离出米进行数据的处理和分析。冈此，多密度聚类算法的研究为 将复杂的海量数据转换为需要的信息提供了强有力的分析手段。 第1 章引言 能够处理多密度数据集的聚类算法有c h a m e l e o n 【1 1 、共享近邻s n n 算法【2 】、多阶段等密 度线算法【3 】等。c h a m e l e o n 算法可以用来处理多密度的数据集，但当数据集较大时其算法的 时间复杂度太高。s n n 算法的优点是可以对不同密度和形状的数据集进行聚类，缺点是在 多密度聚类和处理孤立点或噪声方面精度都不高。多阶段等密度线算法采用多阶段的方式， 利用等密度线的思想对数据集进行聚类，它的缺点是不能有效地分离出多个类。 所以，对网格聚类算法和多密度聚类算法的研究将具有广阔的发展空间，今后将会在 更多的领域中发挥作用。 1 2 研究内容与思路 针对上面的分析，本文就以下内容进行了研究： 1 在对数据挖掘理论和网格聚类算法研究的基础上，提出了网格边界处理改进算法 在系统的研究了数据挖掘理论和网格聚类算法的基础上，为提高网格聚类的精度，提出 了基于网格的边界处理算法，并在综合数据集和真实数据集上进行测试，最后给出实验结果， 同时分析了该算法的时间复杂度和空间复杂度。 2 提出基于网格的参数自动化聚类算法 由于传统的网格聚类算法需要人工的输入参数，这就使得聚类结果很大程度上依赖于参 数的选择，聚类算法对参数的依赖性很大。针对这个问题，提出了基于网格的参数自动化聚 类算法，_ 并在综合数据集和真实数据集上进行测试，最后给出实验结果，同时分析了该算法 的时间复杂度和空间复杂度。 3 提出基于网格的多密度聚类算法 由于人多数网格聚类算法都只适合均匀密度的数据集，对多密度的数据集聚类效果不 好。针对这个问题，提出了基于网格的多密度聚类算法，并在综合数据集和网络入侵真实数 据集上进行了测试，最后给出实验结果，同时分析了该算法的时间复杂度剐空间复杂度。 1 3 论文组织结构 本文共分六章，具体的组织如卜： 第一章主要阐述了课题研究的背景与意义，并概要的说明研究的内容利思路。 第二：章系统的分析了数据挖掘、密度聚类和网格聚类算法理论，给出了一些常她的基 2 第1 章引言 于密度和网格的聚类算法，并分析了这些算法的优点和缺点。 第三章在研究了传统网格聚类算法的基础上，为提高网格聚类的精度，提出了基于网 格的边界处理算法，并将该算法在综合数据集和网络入侵真实数据集上进行测试，最后给出 实验结果，同时分析了算法的时间复杂度和空间复杂度。 第四章在研究了传统网格聚类算法对参数依赖性的基础上，提出基于网格的参数自动 化的聚类算法，并将该算法在综合数据集和网络入侵真实数据集上进行测试，最后给出实验 结果，同时分析了算法的时间复杂度和空间复杂度。 第五章在研究了多密度聚类算法的基础上，提出了基于网格的多密度聚类算法，并将 该算法在综合数据集和网络入侵真实数据集上进行测试，最后给出实验结果，同时分析了算 法的时间复杂度和空间复杂度。 第六章对前面研究工作进行了总结与展望，给出了本文的主要创新点，并提出了今后 的研究方向。 3 第2 章数据挖掘和聚类算法分析 第2 章数据挖掘和聚类算法分析 2 1 数据挖掘概述 随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的数据急剧增 加，可是用于对这些数据进行分析处理的工具却很少。目前数据库系统所能做到的只是对数 据库中已有的数据进行存取和简单的操作，人们通过这些数据所获得的信息量仅仅是整个数 据库所包含的信息量的很少的一部分，隐藏在这些数据之后的更重要的信息是关于这些数据 的整体特征的描述及对其发展趋势的预测，这些信息在决策生成的过程中具有重要的参考价 值。这就引起了对强有力的数据分析工具的急切需求。快速增长的海量数据收集、存放在大 型和大量数据库中，没有强有力的工具，理解它们已经远远超出了人的能力。 面对这种挑战，数据库中的知识发现( k d dk n o w l e d g ed i s c o v e r yi nd 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 ) ，它是整个数据库中的 知识发现过程中一个非常重要的处理环节，所以两者往往混用。一般而言，在数据库、统计 和数据分析等! i ：程应用领域称为数据挖掘，而在a i 和机器学习界等研究领域人们则称之为 数据库中的知识发现。本文将不加区分地使用两者。 2 1 1 数据挖掘概念 知识发现k d d 是指从大鼙数据中提取出可信的、新颖的、有效的、满在有川的并能被人 理解的模式的非平凡处理过程。这种处理过程是一种高级的处理过程。 在上述定义中，数据是指有关事实的集合，记录和事物有关的原始信息。模式是一个川 语言米表示的一个表达式，它可用来描述数据集的某个子集。我们所说的知识，是对数据包 涵的信息更抽象的描述。对人量数据进行分析的过程，包括数据准备、模式搜索、知识评价， 4 第2 章数据挖掘和聚类算法分析 以及反复的修改求精。该过程要求是非平凡的，意思是要有一定程度的智能性、自动性( 仅 仅给出所有数据的总和不能算作是一个发现过程) 。有效性是指发现的模式对于新的数据仍 保持有定的可信度。新颖性要求发现的模式应该是新的。潜在有用性是指发现的知识将来 有实际效用，如用于决策支持系统里可提高经济效益。最终可理解性要求发现的模式能被用 户理解，目前它主要体现在简洁性上乜1 。 2 1 2 数据挖掘过程 数据挖掘过程可粗略地分为按需选择数据、数据集成、数据预处理、数据转换、挖掘 过程以及模式评估和知识表示等【3 ，4 ，5 ，6 1 。 图2 1 数据挖掘的过程 ( 1 ) 数据选择 从数据源中检索与分析任务相关的数据。 ( 2 ) 数据集成 建立目标数据集。根据数据挖掘目标，从原始数据中选择相关数据集，并将不同数据源 中的数据集成起米，以确定数据挖掘的操作对象，需要解决平台、操作系统和数据类型不同 产生的数据物理格式差异。 5 第2 章数据挖掘和聚类算法分析 ( 3 ) 数据预处理 数据集中不可避免地存在着不完整、不一致、不精确和重复的数据，这些数据统称为脏 数据。数据抽取之后需利用领域专门知识对脏数据进行清洗。通常采用基于规则的方法、神 经网络方法和模糊匹配技术分析多数据源数据之间的联系，然后再对它们实施相应的处理。 ( 4 ) 数据转换 根据分析任务目标，选用关键特征表示数据，并将数据通过汇总或聚集等操作转换为适 于数据挖掘处理的形式。 ( 5 ) 挖掘算法 使用智能方法提取数据模式。这些方法包括概括、分类、回归和聚类等。 ( 6 ) 模式评估 采用有关方法对数据挖掘发现的模式进行评价，根据某种兴趣度度量，识别表示知识的 真正兴趣的模式。 ( 7 ) 知识表示 使用可视化和知识表示技术，向用户提供挖掘的知识，帮助用户理解发现的模式。 由上述过程可知，整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途中发现 选择的数据不太好，或使用的挖掘技术产生不了期望的结果，这时，用户需要重复先前的过 程，甚至从头重新开始。 基于这种观点，加拿大华裔科学家j i a w e ih a n 提出典型的数据挖掘系统具有以- 卜主要 成分( 如图2 2 ) 【1 】： ( 1 ) 数据库、数据仓库或其它信息库这是一个或一组数据库、数据仓库、电子表格 或其它类型的信息库。可以在数据上进行数据清理和集成。 ( 2 ) 数据库或数据仓库服务器根据用户的数据挖掘请求，数据库或数据仓库服务器 负责提取相关数据。 ( 3 ) 知识库这是领域知识，川丁二指导搜索，或评估结果模式的兴趣度。这种知识可 能包括概念分层，用于将属性或属性值组织成不同的抽象层。刚户信念方面的知识也可以包 含在内。可以使用这种知识，根据意外性评估模式的兴趣度。领域知识的其它例子有兴趣度 限制或闽值和元数据。 ( 4 ) 数据挖掘引擎这是数据挖掘系统的基本部分，由一组功能模块组成，删。r 特征 化、关联、分类、聚类分析以及演变和偏差分析。 6 第2 章数据挖掘和聚类算法分析 ( 5 ) 模式评估模块通常，此成分使用兴趣度度量，并与数据挖掘模块交互，以便将 搜索聚焦在有趣的模式上。它可能使用兴趣度阈值过滤发现的模式。模式评估模块也可以与 挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。对于有效的数据挖掘，建议尽 可能深地将模式评估推进到挖掘过程之中，以便将搜索限制在有兴趣的模式上。 ( 6 ) 图形用户界面本模块在用户和数据挖掘系统之间通信，允许用户与系统交互， 指定数据挖掘的任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结果进行探索式数据 挖掘。此外，此成分还允许用户浏览数据库和数据仓库模式或数据结构，评估挖掘的模式， 以不同的形式对模式可视化。 数据清 图2 2 典型的数据挖掘系统结构 2 1 3 数据挖掘的功能 数据挖掘的功能反映了数据挖掘算法发现的模式的种类。根据履行功能的不同，我们将 数据挖掘问题分为数据概括、联接分析、分类、聚类、依赖建模、孤立点分析以及演变分析 等儿个类别。 ( 1 ) 数据概括 数据库数据是最基本的信息，不能满足不同层次的刚户希望从不同的层次利角度对数据 进行处理或浏览的需求。数据概括是一种把数据库数据从低层次抽象到高层次的过程，换言 7 第2 章数据挖掘和聚类算法分析 之，就是对数据进行浓缩，用紧凑形式重新对其进行表示。 ( 2 ) 联接分析 联接分析用于重新建立数据对象之间业已存在的隐含联系，这种联系有关联规则和序列 模式两种表现形式。关联规则反映的是同时频繁出现的数据对象之间的蕴涵关系，序列模式 表明的是时态数据中频繁出现的事件序列。 ( 3 ) 分类 数据分类是根据一个分类模型，在数据库中的对象集合中找到一些共同的属性，并把它 们分成不同类型的过程。其目的在于根据历史数据自动创建能预测未米行为的分类规则。分 类规则反映的是属性数据对象和类别标识之间的因果关系。在分类问题中，待产生的类别的 数目是事先知道的，而且，训练数据中同时包含有属性数据和类别标识数据。 ( 4 ) 聚类 数据的聚类分析是根据使类内部的相似性最大，而使类间的相似性最小化的原则将一 组数据分组( 没有预先定义的类属性) 。这种将实际的或抽象的对象分成相似对象的类的分 组过程叫做聚类。聚类分析有利于在大量对象集合上建立有意义的划分，而这种划分是一种 分而治之的方法，即将大规模的系统分解成较小的组成部分以简化设计和实现。聚类也便丁 分类编制，将观察到的内容组织成类分层结构，把类似的事件组织在一起。 ( 5 ) 依赖建模 依赖建模用于发现反映变量间非平凡依赖关系的模型。依赖模型逻辑上由结构层和苗化 层两部分组成。结构层表明的是变量间的局部相互依赖关系，通常以图形方式描述；而鼙化 层则是对变量间依赖关系强弱的定量描述。利刚依赖建模可以从某一对象的信息推断另一对 象的信息。 ( 6 ) 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这些数据对象 是孤立点( 0 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 n a n a l y s i s ) 描述行为随时间变化的对象的规律或趋势，并对其 建模。尽管也包括了时态数据的分类、聚类利关联分析等，但时问序列数据分析、序列或周 j 明模式匹配利基丁相似性的数据分析等是进化分析区别丁其它方法的特征 8 第2 章数据挖掘和聚类算法分析 2 1 4 数据挖掘方法 数据挖掘方法研究旨在提供数据挖掘的方法论，制定实现知识发现目标的宏观策略，l 种方法可以只能解决一个数据挖掘问题。数据挖掘方法主要包括决策树方法、遗传算法、神 经网络方法、贝叶斯网络方法、粗糙集方法、规则归纳方法、数据库方法、可视化方法等。 另外还有模糊论方法和信息论方法等。其实，随着数据挖掘研究的更加深入和应用的日益、 泛，各种数据挖掘方法会相互融合，全新的数据挖掘方法也会出现。因此，和其它许多领域 一样，数据挖掘方法无法穷尽。 2 2 基于密度的聚类方法 基于密度的聚类方法将数据空间的高密对象区域看成是簇，这一个个簇是被低密度区域 分割开来的，这些簇所代表的区域就称为一个聚类。这类方法的代表算法有：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 d b s c a n p 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 ) 【7 1 是一个基于密度 的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带有“噪音”的空间数据 库中发现任意形状的聚类。它定义簇为密度相连的点的最大集合。 为了能够理解基于密度的聚类算法，必须掌握一些有关密度的相关概念，例如：e 领 域、核心对象、密度可达、密度相连等。 给定对象半径内的区域称为该对象的e 领域。 如果一个对象的领域至少包含有最小数目m i n p t s 个对象，则称该对象为核心对 象。 给定一个对象集合d ，如果p 在q 的- 领域内，而q 是一个核心对象，我们说对象 p 从对象q 出发是直接密度可达的。 如果存在一个对象链p 1 ，p 2 ，p 。，p l = q ，p 。= p ，对p i d ，( 1 白兰n ) ，p i + l 是从 p i 关丁和m i n p t s 直接密度可达的，则对象p 是从对象q 关丁和m i n p t s 密度可 达的( d e n s i i v r e a c h a b l e ) 。 如果对象集合d 中存在一个对象o ，使得对象p 利q 是从。关丁和m i n p t s 密度 9 第2 章数据挖掘和聚类算法分析 可达的，那么对象p 和q 是关于和m i n p t s 密度相连的( d e n s i t y c o n n e c t e d ) 。 密度可达是直接密度可达的传递闭包，这种关系是非对称的。只有核心对象之间是相互 密度可达的。然而，密度相连性是一个对称的关系。 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中 的对象被认为是“噪音”。 d b s a n 通过检查数据库中每个点的e 领域来寻找聚类。如果一个点p 的e 领域包含 多于m i n p t s 个点，则创建一个以p 作为核心对象的新簇。然后，d b s a n 反复地寻找从这 些核心对象密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以 被添加到任何簇时，该过程结束。 如果采用空间索引，d b s a 气n 的计算复杂度是o ( n 1 0 9 ( n ) ) ，这里的n 是数据库中对象的 数目。否则，计算复杂度是o ( n 2 ) 。该算法对用户定义的参数是敏感的 ( 二) o p t l c s 尽管d b s c a n 能根据给定输入参数和m i n p t s 对对象进行聚类，它仍然将选择能产生 可接受的聚类结果的参数值的责任留给了用户。事实上，这也是许多其他聚类算法存在的问 题。对于真实的高维数据集合而言，参数的设置通常是依靠经验，难以确定。绝大多数算法 对参数值是非常敏感：设置的细微不同可能导致差别很大的聚类结果。而且，真实的高维数 据集合经常分布不均，全局密度参数不能刻画其内在的聚类结构。 为了解决这个问题，提出了o p t l c s ( o r d e r i n gp o i n t st ol d e n t i f yt h ec l u s t e r i n gs t m c t u r e ) 聚类分析方法。o p t i c s 没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算 一个簇次序( c l u s t e ro r d e r i n g ) 。这个次序代表了数据的基于密度的聚类结构。它包含的信息， 等同于从一个宽j 。的参数设置范围所获得的基于密度的聚类。 考察d b s c a n ，我们可以看到，对一个恒定的m i n p t s ，关丁高密度的( 即较小的值) 聚类结果被完全包含在根据较低密度所获得的密度相连的集合中。记住参数e 是距离，它是 邻域的半径。因此，为了生成基于密度聚类的集合或次序，我们可以扩展d b s c a n 算法米 同时处理一组距离参数值。为了同时构建不同的聚类，对象应当以特定的顺序来处理。这个 次序选择根据最小的e 值密度可达的对象，以便高密度的聚类能被首先完成。基丁这个思想， 每个对象需要存储两个值核心距离( c o r ed i s t a n c e ) 和可达距离( r e a c h a b l ed i s t a n c e ) ： 一个对象p 的核心距离是使得p 成为核心对象的最小。如果p 不是核心对象，p 的核 心距离没有定义。 一个对象q 关丁另一个对象p 的可达距离是p 的核心距离利p 与q 的欧儿里得距离两者 1 0 第2 章数据挖掘和聚类算法分析 中的较火值。如果p 不是核心对象，p 和q 之间的可达距离没有定义。 o p t l c s 算法创建了数据库中对象的一个次序，额外存储了每个对象的核心距离和一个 适当的可达距离。已经提出了一种算法，基于o p t l c s 产生的次序信息来抽取聚类。对于小 于在生成该次序时采用的距离e 的任何距离e ，为提取所有基于密度的聚类，这些信息是 足够的。 由于o p t i c s 算法与d b s c a n 在结构上的等价性，o p t l c s 算法具有和d b s g 气n 相同 的时间复杂度。 ( 三) d e n c l u e d e n c l u e ( d e n s i t y - b a s e dc l u s t e 血g ) 【8 】是一个基于一组密度分布函数的聚类算法。 该算法主要基于下面的想法：( i ) 每个数据点的影响可以用一个数学函数来形式化地模拟，它 描述了一个数据点在领域内的影响，被称为影响函数( i n n u e n c ef u n c t i o n ) ；( i i ) 数据空间的整 体密度可以被模型化为所有数据点的影响函数的总和；( i i i ) 然后聚类可以通过确定密度吸引 点( d e n s i t ya t t r a c t o r ) 来得到，这里的密度吸引点是全局密度函数的局部最大。 假设x 和y 是d 维特征空间f d 中的对象。数据对象y 对x 的影响函数是一个函数 ：f 4 _ 彤，它是根据一个基本的影响函数 彤0 ) = 允 ，y ) ( 2 1 ) 米定义的。原则上，影响函数可以是一个任意的函数，它由某个领域内的两个对象之间的距 离来决定。距离函数d ( x ，y ) 应当是自反的和对称的，例如欧几里得距离。它j i ； j 米计算一个 方波影响函数( s q u a r e w a v ei n f l u e n c ef u n c t i o n ) ： k 炉 0 二e 嬲p 仃偿2 ， 或者一个高斯影响函数： 一蟛 ，l g 口。( z ，y ) = p 2 。二 ( 2 3 ) 在一个对象x ( x 一) 上的密度函数被定义为所有数据点的影响函数的汞l 。给定n 个数 据对象，d = x 1 ，x n ) c f d ，在x 上的密度函数定义如下： 芹( x ) 2 善臂( x ) ( 2 4 ) 例如，根据高斯影响函数得出的密度函数是 簸魏i 第2 章数据挖掘和聚类算法分析 n 一生壁盎 篇一( x ) 2 善p 2 ( 2 5 ) 根据密度函数，我们能够定义该函数的梯度和密度吸引点( 全局密度函数的局部最大) 。 一个点x 是被一个密度吸引点x + 密度吸引的，如果存在一组点】( o ，x 1 ，x k ，x o = x ，x k 对0 2 4 p o i n t st h a td o n tb e l o n gt oa n yc l u s t e ra r eo u t l i e r so rn o i s e s ； 图3 2基于网格的边界处理算法 算法解释如下： 步骤1 将d 维数据空间的每一维划分为k 个大小相等的区间，形成k d 个网格单元，对 每一个网格单元，将其每一维两等分，形成2 0 个网格子单元，为卜一步做准备；步骤2 4 是对划分好的k d 个网格单元进行初始化；步骤5 是通过对数据集d 的一遍扫描，将d 中的 点映射到数据网格空间中；步骤6 9 是检查每一个网格单元，如果一个网格单元空间中点的 个数人丁密度闽值m i n p t s ，则该单元被标记为高密度单元，否则被标记为低密度单元，同 时标识出每一个网格单元的相邻单元。 步骤1 0 1 5 是考虑每一个网格单元，若一个单元是低密度单元，并且它的相邻单元中 不存在高密度单元，则这个单元中的数据点被作为孤立点处理；若一个单元是低密度单元， 并且它的相邻单元中存在高密度单元，! ：1 1 0 划分该网格单元为一些子单元，并将利高密度单元 相邻的子单元连接到高密度单元中。 第3 章网格的边界处理算法 步骤1 6 1 8 是将网格单元中的高密度单元连接起来形成聚类。步骤1 9 2 3 是对生成的 聚类进行处理，如果一个聚类中的数据点数大于指定的值m i n ，将这个聚类作为一个合法的 聚类，否则将其作为小聚类从最终的聚类结果中去掉。步骤2 4 是将数据集中不属于任何一 个聚类的点标识为孤立点或噪声。 3 2 算法分析 g b d 算法的时间复杂度为o ( n + k d + p 2 4 ) ，其中n 是数据点的个数，d 是数据空间的维 数，l 是边界单元的个数，k 是每一维上划分区间的个数。具体分析如下： 1 将数据点映射到已划分好的网格单元中所需时间复杂度是o ( n ) ，其中n 是数据 集中数据点数。 2 在网格单元划分好之后，初始化每个单元以及计算每个单元的相邻单元所需的 时间复杂度均是0 ( k d ) 。 3 对每个边界单元，要将其再划分为2 d 个子单元进行边界处理，所需时间复杂度 为o ( l + 2 0 ) 。 所以，基于网格的边界处理算法的总的时间复杂度为o ( n + k o + l t 2 0 ) 。 由于数据集中的数据点在内存中只存一份，基于网格的边界处理算法的空间复杂度为 o ( n ) ，其中n 是数据集中的数据点数。 3 3 实验结果 本实验所使用的个人计算机具有2 5 6 m b 内存，奔腾c p u2 4 0 g h z ，使用的操作系统 是w i n d o w sx p 专业版，算法是州v c 进行编程设计的。 3 3 1 综合数据集 本实验中使用的数据集总共有1 0 个，其中图3 - 3 3 - 8 中的数据集米白文献【2 8 】，图3 9 图3 一1 0 中的数据集来自文献【2 5 】，图3 - 1 1 图3 - 1 2 中的数据集米臼文献【2 9 】。这1 0 个数据 集中，图3 3 3 8 中的数据集是均匀分布的数据集，而图3 9 3 1 2 中的数据集是多密度数 据集，通过对这1 0 个数据集的测试，我们可以很清楚的看到g b d 算法聚类的精度。实验 的结果通过二维图显示如卜： 第3 章网格的边界处理算法 图3 _ 3 ( 数据集1 w 1 ) 图3 4 ( 数据集1 w 2 ) 图3 - 5 ( 数据集1 w 3 ) 图3 - 6 ( 数据集1 1 w 4 ) 图3 - 3 对应的数据集有9 9 9 3 条记录，从图3 - 3 的聚类结果我们可以看到：此数据集应 该被分为4 类，算法g b d 达到了理想的结果，并且能很好的识别出聚类和孤立点，使聚类 结果的精度达到一个较高的水平。 图3 4 对应的数据集有1 1 1 8 2 条记录。从图3 - 4 的聚类结果我们可以看到：此数据集应 该被分为5 类，算法g b d 的实验结果是5 个类，并且该算法也能很好的识别出聚类和孤立 点，聚类结果的精度很高。 图3 5 对应的数据集有1 2 9 1 7 条记录，从图3 - 5 的聚类结果我们可以看到：此数据集应 该被分为3 类，算法g b d 的实验结果是3 个类，并且该算法也能很好的识别出聚类和孤立 点，聚类结果比较理想。 图3 6 对应的数据集有8 4 8 6 条记录，从图3 6 的聚类结果我们可以看到：此数据集应 该被分为4 类，算法g 肋的实验结果是4 个类，并且该算法也能很好的识别出聚类和孤立 点，聚类结果精度较好。 幽3 7 ( 数据集c u r s e )幽3 8 ( 数据集n o i s e ) 幽3 7 对应的数据集有7 8 2 3 9 条记录，从图3 - 7 的聚类结果我们可以看到：此数据集麻 该被分为4 类，算法g b d 的实验结果是4 个类，图3 7 左、h 部的两个锯齿形的类被很好的 识别【l ；米，同时两个锯齿形的类之间的孤立点也被有效的识别出来，所以该算法能很好的识 别出聚类和孤立点，聚类结果比较理想。 幽3 8 对麻的数据集有1 9 4 4 4 7 个记录，且含有人量的孤立点和噪卢。从幽3 8 的聚类 第3 章网格的边界处理算法