（计算机软件与理论专业论文）聚类的边界点检测算法研究.pdf

郑州大学硕士学位论文 聚类的边界点检测算法的研究 摘要 从大型数据集中发现有趣的，有用的且预先未知的知识的过程被称为数据挖 掘。数据挖掘又称数据库中的知识发现，是数据库研究最活跃的领域之一。通过 数据挖掘可以从大型数据集中提取可信、新颖、有效并易于理解的知识、规律或 高层信息。这给人们在信息时代所积累的海量数据赋予了新的意义。随着数据挖 掘技术的迅速发展，作为其重要组成部分，聚类分析和孤立点检测技术已经广泛 应用于模式识别、数据分析、图象处理、市场研究等许多领域。聚类及孤立点检 测算法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。聚类的边界 点检测有时比聚类分析和孤立点检测更重要，但是聚类的边界点检测却不及聚类 分析和孤立点检测受到重视。因此本论文重点对聚类的边界点检测算法进行了研 究。 论文首先介绍了数据挖掘、聚类分析、孤立点检测和聚类的边界点检测等基 本理论以及几种主要的聚类分析算法、孤立点检测算法。本文详细介绍了一种典 型的聚类的边界点算法b o r d e r ，在实验的基础上讨论了b o r d e r 算法的优缺 点。针对b o r d e r 算法时问复杂度高和精度不高的不足，本文提出了三种不同 的聚类的边界点检测算法：噪声数据上的聚类边界点算法b o u n d 、改进的 b o u n d 算法b r i m 和基于引力的聚类边界点检测算法g r e e n 。并利用对象的 反向鼹近邻的性质，提出一种新的孤立点检测算法。在综合数据集和真实数据 集上做了大量的实验来验证算法的有效性，并用不同规模的综合数据集来验证算 法的响应时间。实验结果表明：本文提出的三种边界点检测算法的精度和执行效 率均比b o r d e r 算法高：本文提出的基于反向尽近邻的孤立点检测算法在保证 精度的情况下，其执行效率高于典型的孤立点检测算法l o f 。 关键词：数据挖掘，聚类算法，孤立点检测，边界点检测 郑州大学硕士学位论文 聚类的边界点检测算法的研究 a b s t r a c t t h ep r o c e s so fd i s c o v e r i n gi i l t e 陀她u s e f u la n dp r e v i o u s l yu n k l l o w l l 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 sk n o w na sd a t am i n i n g d a t am i n i n g , a l s o k n o w na sk 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 ) ，i so n eo f t h em o s ta c t i v ef i e l d si n d a t a b a s e d a t am i n i n ga i m st od i s c o v e rm a n yt r u s t f u l ，n o v d ，u s e f u la n dr e a d a b l e k n o w l e d g e , r u l e so ra b s t r a c ti n f o r m a t i o nf r o mv e r yl a r g ed a t a b a s e t h i sp l a y san e w s 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 h ei n f o - t i m e s w i t ht h er a p i dd e v e l o p m e n to f t h e d a t am i n i n gt e c h n i q u e s ，c l u s t e r i n ga n a l y s i sa n do u t l i e rd e t e c t i o n , a si m p o r t a n tp a r t so f d a t am i n i n g , a r ow i d e l ya p p l i e dt ot h ef i e l d ss u c h 鹪p a t t e r nr e c o g n i t i o n ，d a t a a 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 ho nc l u s t e r i n ga n a l y s i sa n d o u t l i e rd e t e c t i o na l g o r i t h m sh a sb c c d m eah i g h l ya c t i v et o p i ci l lt h ed a t am i n i n g r e s e a r c h s o m e t i m e sd e t e c t i n gb o r d e ro fc l u s t e r si sm o r ei m p o r t a n tt h a nc l u s t e r i n g a n do u t l i e r sa n a l y s i s ，w h i l ei th e s n tr e c e i v e ds om u c ha t t e n t i o na st h a to fc l u s t e r i n g a n do u t l i e r sa n a l y s i s s ot h i sp a p e rm a i n l yd os o m er e s e a r c ho nt h ea l g o r i t h m so f d e t e c i n gb o r d e ro f c l u s t e r s i nt h i st h e s i s ，t h ea u t h o ri n l x o d u c e st h et h e o r yo fd a t am i n i n g , a n dd e e p l ya n a l y z e s t h ea l g o r i t h m so fc l u s t e r i n ga n a l y s i sa n do u t l i e r sd e t e c t i o n w ei n t r o d u c eac l a s s i c a l a l g o r i t h mo fd e t e c t i n gb o r d e ro fc l u s t e r sn a m e db o r d e r i nd e t a i l s , a n da n a l y z et h e a d v a n t a n g e sa n dd i s a d v a n t a n g e so fb o r d e rb a s e do ne x p e r i m e n t sa n dt h e o r y a i m i n gt o t h ed i s a d v a n t a n g e st h a tb o r d e rh a sl o we f f i c i e n c ya n dd e t e c t i n g p r e c i s i o n , w ed e v e l o p et h r e ed i f f e r e n tm e t h o d so fd e t e c t i n gb o r d e ro fc l u s t e r s ：( 1 ) d e t e c t i n gb o u n d a r yp o i n t so fc l u s t e r si nn o i s yd a t a s e t0 3 0 t n 岫) a ne f f i c i e n t b o u n d a r yp o i n t sd e t e c t i n ga l g o r i t h m ( b r i m ) a n dg r a v i t y - b a s e db o u n d a r yp o i n t s d e t e c t i n ga l g o r i t h m ( g i 也e n ) w ea l s op r e s e n tan o wo u t l i e r sd e t e c t i n ga l g o r i t h m m a k i n gu s eo f o b j e e t s c h a r a c t e ro f r e v e r s ekn e i g h b o u r s 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 so i ls y n t h e t i cd a t a s e t sa n dt h er e a ld a t a s e t s t ov e r i 匆t h ec o r r e c t n e s sa n de f f i c i e n c yo f a l g o r i t h m s i no r d e rt ov 耐匆t h ee f f i c i e n c y o fa l g o r i t h m so fd e t e c i n gb o r d e ro fc l u s t e r s , w eh a v ec o n d u c t e das e r i e so f e x p e r i m e n t so ns y n t h e t i cd a t a s e t sw i t hd i f f e r e n ts i z e a ss h o w ni nt h ee x pe | f a n e n t a l r e s u l t s ，t h et h r e en e w l yp r o p o s e da l g o r i t h m so fd e t e c i n gb o r d e ro fc l u s t e r s ( 8 0 u n d , i i 郑州大学硕士学位论文聚类的边界点检测算法的研究 b r i ma n dg r e e n ) h a sh i g e rp r e c i s i o na n de f f i c i e n c yt h a nt h a to fb o r d e r ；t h e p r o p o s e do u t l i e r sd e t e c t i n ga l g o r i t h mh a sh i g e re f f i c i e n c yt h a nt h a to f l o f a n dl s c k e y w o r d s ：d a t am i n i n g , c l u s t e ra l g o r i t h m s ，o u f l i e r sd e t e c t i o n , d e t e c t i n gb o r d e ro f c l u s t e r s 1 i i 郑州大学硕士学位论文聚类的边界点检测算法的研究 第1 章引言 1 1 研究背景与意义 随着数据库技术的成熟和数据应用的普及，人类积累的数据量正在以指数速 度迅速增长。进入九十年代，伴随着因特网( i n t e r n e t ) 的出现和发展，以及随 之而来的企业内部网( i n t r a n e t ) 和企业外部网( e x t r a n e t ) 以及虚拟私有网 ( v p n v i r t u a l p r i v a t e n e t w o r k ) 的产生和应用，将整个世界联成一个小小的地球 村，人们可以跨越时空地在网上交换数据信息和协同工作。这样，展现在人们面 前的已不是局限于本部门，本单位和本行业的庞大数据库，而是浩瀚无垠的信息 海洋，数据洪水正向人们滚滚涌来。当数据量极度增长时，如果没有有效的方法， 由计算机及信息技术来提取有用信息和知识，人们也会感到面对信息海洋像大海 捞针一样束手无策。其结果是数据丰富，知识亏乏。如何有效地分析这些数据， 发现在这些数据中有用的知识，以便更好地为决策服务。这时，数据挖掘应运而 生。数据挖掘也称为数据库中的知识发现( k d d ) 。指的是从存放在数据库、数据 仓库或其他信息库中的大量数据中挖掘出人们感兴趣的知识，这些知识是隐含 的、事先未知的潜在有用信息。目的是帮助决策者寻找数据间潜在的关联，发现 被忽略的要素，而这些信息对预测趋势和决策行为也许是十分有用的。数据挖掘 定义为在数据中识别有效的，新颖的，潜在有用的且最终可解释摸式的重要过程。 聚类分析是数据挖掘的重要的组成部分，所谓聚类就是将数据对象分组成多 个类或簇( c l u s t e r ) ，在同一个簇中的对象之间具有较高的相似度，而不同簇中， 对象之间差别较大。聚类可以发现密集的和稀疏的区域，以及属性之间所存在 的有趣的相互联系，从而发现全局的分布模式。目前它已经广泛应用于模式识别、 数据分析、图象处理和市场分析。聚类分析所涉及的领域包括：数据挖掘、统计 学、机器学习、空间数据技术、生物学、市场学等。由于数据库中收集了大量的 数据，聚类分析已经成为数据挖掘领域中一个非常活跃的研究课题。迄今为止， 研究人员已经提出了许多聚类算法。这些聚类算法大体上可以分为基于划分的方 法，基于层次的方法，基于密度的方法，基于网格的方法和基于模型的方法。一 些聚类算法继承了多种聚类方法的思想，所以有时将某个给定的算法划分为属于 郑州大学硕士学位论文聚类的边界点检测算法的研究 某类聚类方法是困难的 孤立点检测是数据挖掘中的一项重要技术，其目标是发现数据集中行为异常 的少量的数据对象。在数据挖掘领域，孤立点检测的研究对象是数据集中偏离绝 大多数对象的很小一部分。在很多k d d 应用中，发现孤立点比发现普通情况更有 用，更重要。例如在欺诈探测中，孤立点可能预示着欺诈行为。在市场分析中， 可用于确定极低或极高收入的消费行为，或者在医疗分析中用于发现对多种治疗 方式的不寻常的反映。孤立点挖掘还可应用于金融欺诈、网络监控、数据清洗、 电子商务、职业运动员的成绩分析、故障检测、天气预报、医药研究、信贷信用 等领域。在数据挖掘中，孤立点检测算法大体上可分为：基于统计学的方法基 于距离的方法基于密度的方法，基于偏离的方法等。研究孤立点的异常活动有 助于发现隐藏在数据集中有价值的知识。 聚类的边界点检测是数据挖掘中一个前沿的研究方向。边界点是位于分布 稠密的数据( 如聚类) 边缘的点，它们可能同时具有两个或两个以上聚类的特征， 例如在临床医学上，对一些人群是否患有某种疾病的研究中，边界点可能代表某 些人群的集合，从数据分析上看这些人群本来应该患有这种疾病，然而事实上这 些人并没有这种疾病，由于他们具有不确定性，因而这个集合更应该引起高度重 视，他们身上可能蕴含某些重要的、有趣的特征。边界点在分类上也应引起注意， 因为他们容易被误分类“1 。在k d d 应用中，研究聚类的边界点有时比研究聚类、 孤立点更重要。目前涉及到的边界点研究算法并不多，对边界点的研究远远不及 对聚类和孤立点的研究活跃。 1 2 论文的思路 本篇论文共包含两部分：聚类的边界点检测和孤立点检测。由于目前对聚类 的边界点检测算法的研究远远不及对聚类和孤立点检测的研究活跃，因此涉及到 的边界点研究算法并不多，因此本文的重点放在对聚类的边晃点检测算法研究 上。 b o r d e r 是一个有代表性的聚类的边界点检测算法，它利用对象的反向斤近 邻的性质来检测边界点。如果一个对象p 在某个对象。的萨近邻中，则称对象。 是对象p 的反向肛近邻；b o r d e r 首先计算出每个对象的反向萨近邻个数，然后 根据每个对象的反向萨近邻值按从小到大的顺序排列整个数据集，并把前7 个 2 郑州大学硕士学位论文聚类的边界点检测算法的研究 对象作为边界点，因为边界点的反向萨近邻个数往往比聚类内部点的反向斤近 邻个数更少。 该算法可以在不含噪声的空间数据集中有效地检测到边界点，但是算法仍然 有一些不足：( 1 ) 在含有噪声的数据集中，因为噪声点的反向斤近邻个数往往 比聚类边界点的反向斤近邻个数更少，因此按照对象的反向肛近邻值从小到大 的顺序排列整个数据集之后取出的前刀个对象既包含孤立点又包含边界点；所以 该算法在含有噪声的数据集上不能正确地识别出边界点；( 2 ) b o r d e r 算法需要 找出每个对象的个最近邻，进而计算出每个对象的反向萨近邻个数，算法的 时间复杂度是0 ( 矿，是数据集规模大小) ，算法的执行效率不高。 针对b o r d e r 算法中精度不高和效率低的问题，本文提出了三种不同的解决 方案，以此为基础分别开发了b o u n d 、b r i m 和g r e e n 算法。 1 3 论文贡献 这篇论文的贡献是提出了三个聚类的边界点检测算法和一个孤立点检测算 法。论文中根据数据集中对象的e p s - 邻域中包含的对象个数来估计该对象的密 度，利用密度参数m i n p t s 来过滤掉噪声点孤立点，然后根据对象的e p s - 邻域 中包含的对象与其密度吸引点的方向关系计算过滤掉之后的对象的边界度，提出 了基于对象的方向关系的边界点检测算法( b o u n d ) ；先统计出对象的e p s - 邻域 中正半邻域和负半邻域内包含的对象个数，然后根据对象的e p s - 邻域中包含的 对象与其密度吸引点的方向关系计算每个对象的边界度，提出了改进的基于对象 的方向关系的边界点检测算法( b r i m ) ；将数据集中的对象看成是欧几里德空间 中有质量的质点，并假设对象在e p s - 邻域内互相之间有引力作用，对每个对象 进行受力分析，计算每个对象受到的合力，提出了一种基于引力作用的边界点检 测算法( g r e e n ) 。在综合数据集上的实验结果表明：这三种算法能够在含有噪声 的数据集上有效的检测到聚类的边界点，检测的边界点精度比b o r d e r 检测的边 界点结果要高；由于算法实际上都只需要计算每个对象的e p s - 邻域，并不需要 计算它们的反向k 一近邻，因此我们的算法与b o r d e r 算法相比花费更小，效率更 高。 对象的反向肛近邻是基于全局的角度( 而不是从对象本身) 来检查它的邻 域，因此一个对象的反向萨近邻不仅与它周围的对象有关，而且与数据集中的 郑州大学硕士学位论文聚类的边界点检测算法的研究 其他对象分布也有关系。数据分布的改变会导致每个对象的反向萨近邻发生改 变，因此反向萨近邻能反映潜在的数据的分布特征。对象的反向萨近邻个数越 小说明它的偏离程度越大，则该对象越有可能是一个孤立点。于是利用对象的反 向萨近邻的这个性质提出一个孤立点检测算法o d r k n n 。虽然该算法与l o f 的时 间复杂度一样都是0f j l j 彬，但是由于不需要计算对象的局部可达密度和局部孤 立因子，因此o d r k n n 算法的效率高于l o f 的效率。 1 4 论文结构 本论文共分五章。论文其余部分组织如下：在第二章中，系统分析了聚类分 析、聚类的边界点检测和孤立点检测的相关工作，重点分析了种典型的利用对 象的反向萨近邻的性质的边界点检测算法b o r d e r 。 第三章则分别介绍为解决b o r d e r 算法的缺点，而提出的三种不同的解决方 案：提出了基于对象的方向关系的边界点检测算法( b o u n d ) ，改进的基于对象的 方向关系的边界点检测算法( b r i h ) 和一种基于引力作用的边界点检测算法 ( g r e e n ) ，并对三个算法进行了深入地分析。通过实验，分析了三个算法的正确 性与效率，并将它们与b o r d e r 算法的实验结果进行了对比分析。 第四章在对b o r d e r 算法研究的基础上，提出了基于反向肛近邻的孤立点检 测算法，并对该算法进行了深入地分析。通过实验，分析了该算法的正确性与性 能，并将该算法与l o f 算法的实验结果进行了对比分析。 第五章对前面研究工作进行了总结。 4 郑州大学硕士学位论文聚类的边界点检测算法的研究 第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 是指从大量数据中提取出可信的、新颖的、有效的、潜在有 用的并能被人理解的模式的非平凡处理过程。这种处理过程是一种高级的处理过 程。 一般将k d d 中进行知识学习的阶段称为数据挖掘( d a t am i n i n g ) ，它是整 个数据库中的知识发现过程中一个非常重要的处理环节，所以两者往往混用。一 般而言，在数据库、统计和数据分析等工程应用领域称为数据挖掘，而在a i 和 机器学习界等研究领域人们则称之为数据库中的知识发现。本文将不加区分地使 用两者。 2 2 聚类分析 聚类是把一组个体按照相似性归成若干类别，即“物以类聚”。它的目的是 使得属于同一类别的个体之间的距离尽可能的小而不同类别上的个体间的距离 尽可能的大。聚类的结果可以得到一组数据对象的集合，我们称其为簇。簇中的 郑州大学硕士学位论文聚类的边界点检测算法的研究 对象彼此相似，而与其它簇中的对象相异。在许多应用中，可以将一个簇中的数 据对象作为一个整体来对待。 聚类技术最早在统计学和人工智能等领域得到广泛的研究。 在人工智能中，聚类又称作无监督归纳( u n s u p e r v i s e di n d u c t i o n ) 。因为和分 类学习相比，分类学习的例子或数据对象有类别标记，而要聚类的例子则没有标 记，需要由聚类学习算法来自动确定。近几年来，随着数据挖掘的发展，聚类以 其特有的优点，成为数据挖掘研究领域中一个非常活跃的研究课题。在数据挖掘 里，面临的常常是含有大量数据的数据库，因此要探讨面向大规模数据库的聚类 方法，以适应新问题带来的挑战。 2 2 1 聚类算法介绍 目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的 目的和应用。大体上，主要的聚类算法可以划分为如下几类： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) 给定一个n 个对象或元组的数据库，一个划分方法构建数据的k 个划分， 每个划分表示一个聚类簇，并且k n 。也就是说，它将数据划分为k 个组，同 时满足如下的要求：( i ) 每个组至少包含一个对象；( i i ) 每个对象必须属于且只属 于一个组。注意在某些模糊划分技术中，第二个要求可以放宽。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一 种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的 一般准则是：在同一个类中的对象之间尽可能“接近”或相关，而不同类中的对 象之间尽可能“远离”或不同。还有许多其他划分质量的评判标准。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上， 绝大多数应用采用了以下两个比较流行的启发式方法：0 ) k - 平均算法，在该算法 中，每个簇用该簇中对象的平均值来表示”。0 i ) i ( - $ 心点算法，在该算法中， 每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法，对在中小规模 的数据库中，发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复 杂形状的聚类，基于划分的方法需要进一步的改进。 ( 2 ) 层次的方法( h i e r a r c h i c a lm e t h o d ) 层次的方法对给定的数据对象集合进行层次的分解。根据层次的分解如何形 6 郑州大学硕士学位论文聚类的边界点检测算法的研究 成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法， 一开始将每个对象作为单独的一个组，然后相继合并相近的对象或组，直到所有 的组合并为一个( 层次的最上层) ，或者达到一个终止条件。分裂的方法，也称 为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一 个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终 止条件。 层次的方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤 销。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较 小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改 进层次聚类的结果：( i ) 在每层划分中，仔细分析对象问的“联接一，例如c u r e 铂 和c h a m o l c o n ”。中的做法。( i i ) 综合层次聚类和迭代的重定位方法。首先用自底向 上的层次算法，然后用迭代的重定位来改进结果。例如在b i r c h e j 中的方法。 ( 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 8 1 是另一个基于密度的方法，它为自动的和交互的聚类分析 提供一个聚类顺序。 ( 4 ) 基于网格的方法( g r i d - b a s e dm e t h o d ) 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。 所有的聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优 点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每 一维的单元数目有关。 s t i n g 【l 卅是基于网格方法的一个典型例子。c l i q u e 9 1 和w 机c 1 瑚t 1 0 3 这 7 郑州大学硕士学位论文聚类的边界点检测算法的研究 两种算法既是基于网格的，又是基于密度的。 ( 5 ) 基于模型的方法( m o d e l - b 勰e dm e t h o d ) 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟 合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚 类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪音”数据或孤立点， 从而产生健壮的聚类方法。 一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算法划分 为属于某类聚类方法是很困难的。此外，某些应用可能有特定的聚类标准，要求 综合多个聚类技术。 在接下来的一节中，我们将详细讨论上述的基于密度的聚类方法。 2 2 2 基于密度的聚类方法d b s c a n 为了发现任意形状的聚类结果，提出了基于密度的聚类方法。这类方法将簇 看作是数据空问中被低密度区域分割开的高密度对象区域。 ( 1 ) d b s c a n ：一个基于高密度连接区域的密度聚类方法 d b s c a n ( d c 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 ) 是一个 基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带有 “噪音”的空间数据库中发现任意形状的聚类。它定义簇为密度相连的点的最大 集合。 基于密度的聚类算法涉及一些新的定义。 给定对象半径c 内的区域称为该对象的e 领域。 如果一个对象的e 领域至少包含有最小数目m i n p t s 个对象，则称该对象 为核心对象。 给定一个对象集合d ，如果p 在q 的- 领域内，而q 是一个核心对象， 我们说对象p 从对象q 出发是直接密度可达的。 如果存在一个对象链p i ，p 2 ，p n ，p t - - q ，p n = p ，对p i e d ，( 1 虫) ， p i + l 是从p i 关于e 和m i n p t s 直接密度可达的，则对象p 是从对象q 关于 c 和m i n p t s 密度可达的( d e n s i t y - r e a c h a b l e ) 。 如果对象集合d 中存在一个对象o ，使得对象p 和q 是从o 关于e 和m i n p t s 密度可达的，那么对象p 和q 是关于e 和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 c a n 通过检查数据库中每个点的e 领域来寻找聚类。如果一个点p 的 e - 领域包含多于m i n p t s 个点，则创建一个以p 作为核心对象的新簇。然后， d b s c a n 反复地寻找从这些核心对象密度可达的对象，这个过程可能涉及一些 密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。 如果采用空间索引，d b s c a n 的计算复杂度是o ( r a o 颤n ) ) ，这里的n 是数据 库中对象的数目。否则，计算复杂度是o ( n 2 ) 。 d b s c a n 可以在带有“噪音”的空间数据库中发现任意形状的聚类它能根 据给定的输入参数e p s 和m i n p t s 对对象进行聚类，但是它将能产生可接受的聚 类结果的参数值的责任交给了用户。事实上，对于真实的高位数据集和而言，参 数的设置通常是依靠经验难以确定的。参数设置的细微差别有可能导致差别很大 的聚类结果。而且真实的高维数据集通常分布不均，全局密度参数不能可能刻画 其内在的聚类结构，因此该算法不能在多密度的数据集将各个聚类区分开，且算 法对用户定义的参数是敏感的。 2 3 孤立点分析 孤立点是数据集中不符合一般模型的那些对象，即和其它的数据有着不同 的性质。它可能是度量或执行错误所导致的，也可能是固有数据变异的结果。例 如，一个人的年龄为一1 0 0 ，这是一个由于执行错误而产生的孤立点；一个公司的 首席执行官的工资远远高于其他的员工，而成为一个孤立点，这是一个固有的数 据变异的结果。 孤立点的研究非常重要。主要是由于：( 1 ) 它对数据分析的结果有很大的 影响；( 2 ) 虽然它通常是测量，记录错误，但有些可能代表应用领域中感兴趣的 ，有意义的知识；( 3 ) 确定孤立点经常导致发现新的知识。 孤立点检测有着广泛的应用领域。在信用卡欺诈探测中发现的孤立点可能 预示着欺诈行为，而及时发现这种信用卡欺诈行为对商业银行而言相当重要，可 9 郑州大学硕士学位论文聚类的边界点检测算法的研究 以避免重要的经济损失。在市场分析中，可用于确定极低或极高收入的客户的消 费行为。在医疗分析中，可用于对多种治疗方式的不同寻常的反映等。 发现孤立点是数据挖掘中的一项重要技术，其目标是发现数据集中行为异 常的少量的数据对象。但是对孤立点还没有普遍接受的定义，所以对孤立点的研 究都是在一定的定义下进行研究的，例如局部孤立点、子空间孤立点等。在数据 挖掘中，孤立点检测的方法可分为四类：统计学方法基于距离的方法、基于偏 离的方法和基于密度的方法。 2 3 1 孤立点检测算法介绍 目前已经提出了很多种孤立点检测方法，这些大致可以分为三类：统计学方 法，基于距离的方法和基于偏离的方法。下面将对这些方法进行详细介绍： ( 1 ) 基于统计的孤立点检测 基于统计的方法使用著名的标准统计分布( 即正态分布，帕松等) 来拟合 数据点。孤立点是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离 并非由随机因数产生，而是产生于完全不同的统计分布。不一致检验是为了在不 同条件下挖掘孤立点而设计的统计检验。由于检验的范围很广，因此就有许多支 持不同假设和应用的统计分布。 应用不一致检验到一个具体的数据集需要依赖许多条件和假设。首先，假 设数据支持的统计分布是已知的。在这个情况下，测验数据应该服从一个标准统 计分布( 即正态分布，帕松分布等) 。下一个假定是分布参数是否是已知( 即分 布的平均值和方差等) 。期望的孤立点个数也很重要。根据期望的孤立点个数使 用不同的不一致检验。例如，挖掘一个孤立点的检验和挖掘多个或两个孤立点的 检验是不一样的。 ( 2 ) 基于距离的孤立点检测“。脚 基于距离孤立点挖掘算法根据某个距离函数计算数据对象之间的距离。孤 立点是那些与所有其他的数据对象相比有更高距离的数据对象。这些算法目的是 解决在早期算法中所遇到的扩展性问题。孤立点是那些相对于所有其它的对象有 更高距离的对象。如果数据集s 中至少有p 部分对象与对象。的距离大于d ，则 对象0 是一个带参数p 和d 的基于距离的孤立点，即d b ( p ，d ) 。换句话说，我们 可以将基于距离的孤立点看作是那些没有“足够多”邻居的对象。这里的邻居是 l o 郑州大学硕士学位论文聚类的边界点检测算法的研究 基于与给定对象的距离来定义的。基于距离的孤立点检测方法可以在未知数据分 布状态下对多维数据进行分析，避免了过多的计算，而大量的计算正是使观察到 的分布拟合某个标准分布，及选择不一致性检验所需要的。 基于距离的孤立点探测要求用户设置参数p 和d ，而寻找这些参数的合适设 置可能会涉及多次试探和错误。 ( 3 ) 基于偏离的孤立点检测 基于密度的孤立点算法关注一个对象周围的密度( 最近邻居数) 。具有高密 度邻域的数据对象不是孤立点，然而，低密度邻域的数据对象可能就是孤立点。 在决定孤立点方面，基于密度的孤立点挖掘技术更注重对象的局部性。现有算法 计算局部孤立因子( l o f ) 并把那些具有很高l o f 。值的数据对象作为孤立点。 也就是说，l o f 表示了一个对象对于它的邻居来说孤立的程度。 b r e u a i n g 等认为成为孤立点并不是像于距离的孤立点挖掘概念那样不仅仅 是一个二分属性，即：数据对象不能仅被分成是孤立点或者不是孤立点，而是每 个对象有某个孤立度。他们认为，在许多情况下，对每个对象赋予是孤立点的度 这样更正确。这个度成为局部孤立因子( l o f ) 因为这个度依赖于该对象关于它 周围邻居的遥远程度。孤立点就是有高l o f 值的对象。为了挖掘局部孤立点提 出的算法成为局部孤立因子( l o f ) 。l o f 能够探测所有形式的孤立点，包括那 些不能被早期( 基于距离的，基于分布的和基于偏离的) 算法探测到的孤立点。 2 4 聚类的边界点分析 边界点是位于分布稠密的数据( 如聚类) 边缘的点，它们可能同时具有两个 或两个以上聚类的特征。例如在临床医学上，对一些人群是否患有某种疾病的研 究中，边界点可能代表某些人群的集合，从数据分析上看这些人群本来应该患有 这种疾病，然而事实上这些人并没有这种疾病。或者在生物学上，对下列动物： 羊、狗、猫( 哺乳动物) 、麻雀、海鸥( 鸟类) 、毒蛇、蜥蜴( 爬虫类) 、金鱼、 蓝鲨( 鱼) 、青蛙( 两栖类) 进行聚类的过程中，如果聚类的相似度准则定义为 动物的生活环境，那么羊、猫、狗、麻雀、海鸥、毒蛇、蜥蜴、将是一类( 非水 生动物) ，则金鱼，绯鲵鲣和蓝鲨将是第二类( 水生动物) 。由于青蛙既可以生活 在水中，又可以生活在陆地上，同时具有这两个类的特征，因此可将青蛙看成是 这两个聚类的边界点。由于边界点具有不确定性，因而这个集合更应该引起高度 郑州大学硕士学位论文聚类的边界点检测算法的研究 重视，因为他们身上可能蕴含某些重要的、有趣的特征。边界点在分类上也应引 起注意，因为他们容易被误分类。边界点不同于孤立点噪声点，边界点是紧紧 分布在稠密数据( 如聚类) 的周围，它与聚类内部的点在很大程度上有着相似的 性质；而孤立点噪声点分布比较稀疏，它与聚类内部的点在本质上有着不同的 性质。 2 4 1 边界点检测算法介绍 在k d d 应用中，研究聚类的边界点有时比研究聚类、孤立点更重要。目前涉 及到的边界点研究算法并不多，对边界点的研究远远不及对聚类和孤立点的研究 活跃。 ( 1 ) d b s c a n 中对边界点的处理 d b s c a n 基于密度定义了边界点：如果某个对象p 不是核心对象，但它是 从某个核心对象d 直接密度可达的，则定义p 是边界点，并把它添加到核心对象 o 所在的簇中。该算法对边界点的处理有两个不足之处：( 1 ) 对于不同的数据输 入顺序，这些边界点可能会添加到不同的聚类中。例如：当两个聚类。和g 比 较接近时，对于两个聚类交界处的某个非核心对象p ，它既是从聚类c ，中的某 个核心对象d j 直接密度可达的，又是从聚类。中的某个核心对象d 2 直接密度可 达的；如果d b s c a n 先处理核心对象d j ，对象p 被添加到聚类c ，中；反之，则被 添加到聚类。中。( 2 ) 数据集中各个聚类的密度通常是不均匀的，通常聚类内 部的密度较高，而聚类的边界处的密度较低，由于d b s c a n 使用的是全局密度 阈值，所以边界点的定义与m i n p t s 密切相关即对不同的m i n p t s ，得出的边界点 也不相同；所以按照d b s c a n 对边界点的定义很难正确检测到聚类的边界。( 3 ) d b s c a n 作为一种聚类算法，虽然提出了边界点的定义，但是并没有专门把聚 类的边界点提取出来。 ( 2 ) 基于对象的反向尽近邻的边界点检测算法b o r d e r b o r d e r 是c h e n y ix i a 等提出的利用对象的反向萨近邻来检测边界点的算 法。由于目前对边界点没有明确的定义，为此b o r d e r 算法给出了他们自己的 对边界点的形式化定义。如果一个点p 是聚类的边界点，那么它应该满足下面两 个条件： 1 它一定属于某个稠密的区域r l ； 2 在p 附近一定存在某个稠密的区域r 2 ，使得 郑州大学硕士学位论文聚类的边界点检测算法的研究 d e n s i t y ( r 1 ) ) ) d e n s i t y ( r 2 ) 或者d e n s i t y ( r 1 ) ( ( d e n s i t y ( r 2 ) 。 这两个条件说明：如果某个点是边界点，那么它本身的密度要达到一定值，而且 它所在的稠密区域和周围的某个区域形成明显的密度差。 如果一个对象p 在某个对象o 的斤近邻中，则称对象o 是对象。的反向忌 近邻；对反向尽近邻的形式化定义如下； 给定一个数据集d ，其中的一个对象p ，正整数k ，一个距离度量函数；其 中k 是对象的近邻个数，那么对象p 的反向忌近邻( 计作r k n n ( p ) ) 是满足下 面条件的一个集合； v q ，e 戤 ( p ) ，则对象p 是吼的其中一个k - i 邻即p d 、j r n ( q j ) 。 从上面的定义可以看出：对象的尽近邻与它的反向尽近邻有密切的关系， 下面我们用一个图来表示他们之间的关系： 但) b ) 图2 - 1 对象的尽近邻与反向尽近邻的关系 图2 1 ( a ) 是对象的尽近邻图，其中向量p i p j 表示对象p i 是对象p i 的一个 珏近邻；图2 1 ( b ) 是对象的反向k - 近邻图，其中向量p i p j 表示对象p i 是对象 p i 的一个反向忌近邻。从两个图的对比，可以看出：我们只需要讲对象的尽近 邻中的向量进行反向逆转，从给对象出发的向量的终端所对应的对象即为该对象 的反向尽近邻。因此对象的反向尽近邻是从全局( 而不是从局部) 的角度来考 察该对象的邻域，因此它能反映数据的潜在分布，有助于确定两个或多个分布的 数据的边界。b o r d e r 分三个步骤来处理数据集：( 1 ) 计算数据集中的每个点的 尽近邻，获得点对( p i ，p j ) ( 对象p j 是对象p i 的其中一个尽近邻) ，并记录到一 个k n n 文件中。( 2 ) 按照步骤l 中产生的k 最近邻文件，计算出数据集每个点的 反向尽近邻个数；( 3 ) 根据每个点的反向忌近邻个数，对整个数据集中的对象 按从小到大的顺序排序，并把反向妊近邻个数小于某个阈值的点作为边界点。 郑州大学硕士学位论文聚类的边界点检测算法的研究 b o r d e r 算法对边界点的提取基于这样的经验：边界点通常比聚类内部的点的反 向尽近邻个数更少。因此b o r d e r 可以在不含噪声的数据集上有效的提取出聚类 的边界点。 2 5 本章小结 本章对数据挖