（计算机软件与理论专业论文）基于k距离的孤立点和聚类算法研究.pdf

郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 摘要 从大型数据集中发现有趣的，有用的且预先未知的知识的过程被称为数据挖 掘。数据挖掘又称数据库中的知识发现，是数据库研究最活跃的领域之一。通过 数据挖掘可以从大型数据集中提取可信、新颖、有效并易于理解的知识、规律或 高层信息。这给人们在信息时代所积累的海量数据赋予了新的意义。随着数据挖 掘技术的迅速发展，作为其重要组成部分，聚类分析和孤立点检测技术已经厂泛 应用于模式识别、数据分析、图象处理、市场研究等许多领域。聚类及孤立点检 测算法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。 本文介绍了数据挖掘理论，对聚类及孤立点检测算法进行了深入地分析研 究。在分析了基于密度的聚类算法和基于密度的孤立点算法的基础上，提出了基 于局部孤立系数的孤立点检测和基于局部孤立系数的聚类算法；基于k 一距离因 子和增强的k 一距离因子的孤立点检测算法。 本文使用v i s u a lc + + 6 0 实现了基于局部孤立系数的聚类算法、基于局部孤 立系数的孤立点算法、基于k 一距离因子的孤立点算法、增强的k 一距离因子的孤 立点算法、l o f 算法、r d b k n n 算法。在综合数据集上和真实数据集上做了大 量的对比实验来验证孤立点算法的正确性，在综合数据集上验证孤立点算法的效 率；在综合数据集上、真实数据集上和多密度数据集上验证基于局部孤立系数的 聚类算法的正确性，在综合数据集上验证聚类算法的效率。 实验结果表明，基于局部孤立系数的聚类、基于局部孤立系数的孤立点、基 于k 一距离因子的孤立点、增强的k 一距离因子的孤立点算法能够准确、有效的发 现聚类和孤立点。聚类和孤立点检测算法在执行效率、聚类及孤立点检测效果等 方面有一定的优越性。 总之，基于局部孤立系数的聚类算法不仅适合于均匀密度的数据集，而且 对多密度数据集上也适合。该算法能有效的识别出各种形状的聚类，而且也能有 效的识别出孤立点或噪声，在和r d b k n n 算法对比中显示出了一定的优越性。最 后，实验结果表明，无论是聚类算法还是孤立点检测算法都比原来的算法效率高。 关键词：数据挖掘，聚类算法，孤立点检测， p 的k 一距离，k 一距离邻居 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 a b s h 丑c t t h ep r o c e s so fd i s c d v e r i n gi n t e r e s t i n g ，u s e f h la n dp r e v i o u s l yu n k h 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 sl 【n o w na s d 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 0 v e r yi nd a t a b a s e ( k d d ) i so n eo ft h em o s ta c t i v ef i e l d s i 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 im a n yt r i l s t f u l ，n o v e l ，u s e f u la n dr e a d a b l e k n o w l e d g e ，n l l e so ra b s t r a c ti n f o 玎n a t i o nf r o mv e r yl a 曙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 tf o l et ot h es t o r e dd a t ai l lt h ei n f b 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 ft h e d a t am i n i n gt e c h n i q u e s ，d u s t e r m g 卸a l y s i sa n do u t l i e rd e t e c t i o n ，a si h l p o n a n tp a r t so f d a t am i n i n g ，a r ew i d e l y 印p l i e dt ot h ef i e l d ss u c ha s p a t t e mr c c o g n n i o n ，d a t a a i l a l y s i s ，i m a g ep r o c e s s i n g ，a dm a r k e t r e s e a r c h r e s e a r c ho nd 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 e c o m ea l l i g h l ya c t i v et 叩i ci nt h ed a t am i n i n g i e s e a r c h h 1t h i st h e s i s ，t i l ea u t h o ri n t r o d u c e st h et h e o r yo fd a t a m 血i n g ，a i l dd e e p l ya i l a l y z e s t h e a l g o r i t h m s o f c l u s t e r i n g a n do u t l i e rd e t e c t i o n b a s e do nt h e a n a l y s i s o f d e n s i t y - b a s e dd u s t e f i n ga n do u t l i e ra l g 嘶t h m s ，w ep r e s c n tl o c a lo u t l i c fc o e 伍c j e n t ( l o c ) ，k - d i s t 柚c ef a c t o r ( k d f )，e n h a c e d k d i s t a n c e f a c t o r k d f ) o u t l i e r a l g o r i t h ma n db c a l0 u t l i e rc o e 厢c i e n t - b a s e dc l u s t e 咖g ( l o c b c ) a l g o r i t h m i nt h i st h e s i s ，w eh a v ed e v e l 叩e dl d c ，k d f e k d f ，l d c b c ，l o fa i l d r d n k n na l g o r i t h ma n di m p l e m e n t e di tu s i n g s u a lc + + 6 o w ec o n d u c t e das e r i e s o fe 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 sa n dt h er e a ld a t a b a s et ov e r i f yt h ec o n - c c t n e s so f o u t l i e ra l g o r i t l l i i l ，t ov e r i f ym ee f i 晤c i e n c yo fo u t l i e ra l 鲥t t l mo ns y n t h e t i cd a t a s e t s w eh a v ev e i i f i e dt h ec o f f e c t n e s so fc k s t e r i n ga l g o r i t h mo ns y n t h c t i cd a t a s e t ，o nt h e r c a ld a t a b a s ea n do nt h ed a t a s e tw i t l ld i 圩e r e n td e n s i t y ；t ov e r i f yt h ee f f i d e n c yo f c l u s t e r i n ga l g o r i t h m 0 ns ”t h e t i cd a t a s c t s a ss h a w ni nt l l ee x p e r i m e n t a lr e s u l t s ，l o c b c ，l o c ，k d f ，e k d fa l g o r i c h m s c a nc l u s t e rc o r r e c t l ya n dd i s c 0 v e ro u t l i e r s c l u s t e r i n ga n do u t l i e ra l g o r i t l i r l l sa r eb e t t e r o nt h er e s p o n s et i m e ，c l u s t e r i n gp r e c i s i o na n do u t l i e rd e t e t i o nt h a nt h a to fr d b k n n a n d l of t os u mu p ，l o c b cl g o r i t h mc a nn o to n l yd u s t e ro nt h ed a t a b a s ew j l he v e n d e n s i t y ，b u ta l s oo nt h ed a t a b a s ew i t hm u l t i d e n s i ty t h el o c b ca l g o r i t h mc a nn o t l i 郑州大学硕士学位论文 基于k 一距离的孤立点和聚类算法研究 i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i j i i i i i i i i i i i i i i i i i i i i i 。 o n l yd i s c o v e rc l u s t e ：o fa r b i t r a r ys h a p e sb u ta l s o f i n do u t l i e r si nt h ed a t a s e t t h e p r e d s j o n o fl o c b ca l g o r i t h j ni sb e t t e rt h a nt h a to fr d b k n n f i n a l iy t h e e x p e r 主m e n t a lr e s u l t ss h o w st h a tc l u s t e r i n g 柚do u t l i e ra l g o r i t h m sa r ea l lb e t t e rt h a n r d b k n na n dl o f a l g o r i t l l i l l k e y w o r d s ： d a t a m i n i n g ， c l u s t e fa l g o r i t h m s，o u t l i e r s d e t e c t i o n ， k d i s t a n c eo f p ，k d i s t a n c en e i g h b o u r h o o d 1 i i 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 。 第1 章引言 1 1 研究背景与意义 现在信息技术，数据处理技术发展迅速，收集、存储在数据库中的数据以极 快的速度增长，而它们所能揭示的知识很少。其结果是数据丰富，知识亏乏。如 何有效地分析这些数据，发现在这些数据中有用的知识，以便更好地为决策服务。 这时，数据挖掘应云而生。数据挖掘也称为数据库中的知识发现( k d d ) 。指的是 从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘出人们感兴趣的知 识，这些知识是隐含的、事先未知的潜在有用信息。目的是帮助决策者寻找数据 间潜在的关联，发现被忽略的要素，而这些信息对预测趋势和决策行为也许是十 分有用的。数据挖掘定义为在数据中识别有效的，新颖的，潜在有用的且最终可 解释摸式的重要过程。 聚类分析是数据挖掘的重要的组成部分，所谓聚类就是将数据对象分组成多 个类或簇( c l u s t e r ) ，在同一个簇中的对象之间具有较高的相似度，而不同簇中， 对象之间差别较大。用一个相似性函数来度量记录之间的相似度，这个距离函数 有两个输入，返回一个它们相似度的度量的值“3 。聚类可以发现属性之间所存在 的联系，从而找出数据分布的模式，目前它已经广泛应用于模式识别、数据分析、 图象处理和市场分析。聚类分析所涉及的领域包括：数据挖掘、统计学、机器学 习、空间数据技术、生物学、市场学等。 由于聚类被广泛地应用在许多领域，迄今为止，研究人员已经提出了许多聚 类算法，聚类算法大体上主要可以分为基于划分的方法、基于层次的方法、基于 密度的方法、基于网格的方法和基于模型的方法。 孤立点检测是数据挖掘中的一项重要技术，其目标是发现数据集中行为异常 的少量的数据对象。在数据挖掘领域，孤立点检测的研究对象是数据集中偏离绝 大多数对象的很小一部分。在很多k 叻应用中，发现孤立点比发现普通情况更有 用，更重要。例如在欺诈探测中，孤立点可能预示着欺诈行为。在市场分析中， 可用于确定极低或极高收入的消费行为，或者在医疗分析中用于发现对多种治疗 方式的不寻常的反映。孤立点挖掘还可应用于金融欺诈、网络监控、数据清洗、 电予商务、职业运动员的成绩分析、故障检测、天气预报、医药研究、信贷信用 郑州大学硕士学位论文 基于k 一距离的孤立点和聚类算法研究 等领域。 在数据挖掘中，孤立点检测算法大体上可分为：基于统计学的方法，基于距 离的方法，基于密度的方法、基于偏离的方法等。研究孤立点的异常活动有助于 发现隐藏在数据集中有价值的知识。 1 2 论文内容与思路 本篇论文的重点是基于密度的聚类和孤立点挖掘。基于密度的方法在探测所 有形式的孤立点上更有效。然而，基于密度算法有下面的缺点：( 1 ) 在探测到少 数几个孤立点以前，它需要计算每个对象的局部可达距离和局部可达密度；( 2 ) 为了把具有很高l o f 值的那些数据对象作为孤立点，就要计算数据集中每个对象 的局部孤立因子。由于孤立点仅占整个数据集的很小一部分，必须避免这么多非 常昂贵的计算。本论文根据对象和它k 一近邻之间的距离，提出了局部孤立系数 ( i d c ) 算法；根据对象的k 一距离和它k 一近邻的k 一距离，提出了k 一距离因子 ( k d f ) 和增强的k 一距离因子( e k d f ) 算法，这些算法都不需要计算每个对象 的局部可达距离和局部可达密度。这就减少了l o f 技术中的计算和比较的次数。 在e k d f ，根据它们k 一近邻的k 距离来剪除不可能包含孤立点的数据对象，剩 余的数据构成侯选集，在侯选集中挖掘孤立点。 由于基于密度的聚类方法能够发现任意形状的簇。一个典型的基于密度的聚 类算法是d b s o n 。但d b s a 气n 算法依赖两个参数：对象的邻域半径和邻域半 径内最少点数m i n p t s 。d b s c a n 对用户的参数非常敏感，使用全局密度参数来 刻画内在聚类。为了解决这个缺点，研究人员提出了r d b 叮n 算法。它是针对 d b s c a n 的这些缺点提出的一种新的聚类算法。 然而，r d b k n n 有下列缺点。首先，在计算相对密度以前，需要计算数 据集中每个对象的最近邻居距离和最近邻居密度。为了计算最近邻居距离至少需 要k n 次的计算与比较；计算最近邻居密度至少需要k n 次的计算，其中，k 是 最近邻居数，n 是数据集的大小。由于n 通常是很大，在计算相对密度时，k n 的影响是非常巨大的。其次，r d b k n n 聚类算法中，把满足条件的核心对象既 加入核心集，又加入种子集。最后，在判断一个数据对象能否加入一个聚类c ， 都要计算该对象与聚类c 的相对系数，大大增加了算法计算量。 为了解决上述问题，本文提出了一种局部孤立系数的计算方法，以此为基础 郑州大学硕士学位论文 基于k 一距离的孤立点和聚类算法研究 开发了l o c b c 聚类算法。 1 3 论文贡献 i 这篇论文的贡献是提出了三个孤立点算法和个聚类算法。本论文根据对象 和它k 一近邻之间的距离，提出了局部孤立系数( l o c ) 算法；根据对象的k 一距 离和它k 一近邻的k 一距离，提出了k 一距离因子( k d f ) ，增强的k 一距离因子( e k d f ) 算法和基于局部孤立系数的聚类算法( l 0 c b c ) ，这些算法实际上都不用计算它 们的局部可达距离和局部可达密度，因此我们的算法与局部孤立因子算法相比花 费更小，效率更高。由于孤立点仅占整个数据集的很小一部分，e k d f 算法根据 它k 一近邻的k 一距离剪除数据对象。一旦发现不可能是孤立点的数据对象就剪除 它。这个过程再一次减少了不必要的计算次数，因此提高了效率。 1 4 论文结构 本论文共分五章。论文其余部分组织如下：在第二章中，系统分析了聚类分 析和孤立点检测的相关工作，重点分析了基于密度的聚类算法和孤立点检测算 法。 第三章在孤立点检测算法的研究基础上，提出了局部孤立系数，k 一距离因子， 增强的k 一距离因子三个孤立点检测算法，并对三个算法进行了深入地分析。通 过实验，分析了三个算法的正确性与性能，并将它们与l o f 算法的实验结果进行 了对比分析。 第四章在聚类算法的研究基础上，提出了基于局部孤立系数的聚类算法，并 对该算法进行了深入地分析。通过实验，分析了该算法的正确性与性能，并将该 算法与r d b k n n 算法的实验结果进行了对比分析。 第五章对前面研究工作进行了总结。 3 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 第2 章相关知识 2 1 数据挖掘概述 随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的 数据急剧增加，可是用于对这些数据进行分析处理的工具却很少。目前数据库系 统所能做到的只是对数据库中已有的数据进行存取和简单的操作，人们通过这些 数据所获得的信息量仅仅是整个数据库所包含的信息量的很少的一部分，隐藏在 这些数据之后的更重要的信息是关于这些数据的整体特征的描述及对其发展趋 势的预测，这些信息在决策生成的过程中具有重要的参考价值。这就引起了对强 有力的数据分析工具的急切需求。对于飞速增长的信息数据，如果没有强有力的 分析工具，来帮助人们理解这些海量的数据，单靠人脑来处理它，这已经远远超 出了人的能力。 面对这种挑战，数据库中的知识发现( k d dk o w l e d g ed i s c o v e r vi n d a t a b a s e s ) 技术逐渐发展起来。k d d 就是从大量、不完全、有噪声的异质模糊 数据中挖掘隐含的潜在有用知识的过程，它不但能够学习已有的知识，而且又可 以发现未知的规律。同时，砌) d 也是一门新兴的交叉学科，汇聚了数据库、人 工智能、统计、可视化和并行计算等不同领域的研究人员。 知识发现k d d 是指从大量数据中提取出可信的、新颖的、有效的、潜在有 用的并能被人理解的模式的非平凡处理过程【2 】。这种处理过程是一种高级的处理 过程。 一般将k d d 中进行知识学习的阶段称为数据挖掘( d a t am i n i n g ) ，它是整 个数据库中的知识发现过程中一个非常重要的处理环节，所以两者往往混用。一 般而言，在数据库、统计和数据分析等工程应用领域称为数据挖掘，而在m 和 机器学习界等研究领域人们则称之为数据库中的知识发现。本文将不加区分地使 用两者。 2 2 聚类分析 聚类是把一组个体按照相似性归成若干类别，即“物以类聚”。它的目的是 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 使得属于同一类别的个体之问的距离尽可能的小而不同类别上的个体间的距离 尽可能的大。聚类的结果可以得到一组数据对象的集合，我们称其为簇。簇中的 对象彼此相似，而与其它簇中的对象相异。在许多应用中，可以将一个簇中的数 据对象作为一个整体来对待。 聚类技术最早在统计学和人工智能等领域得到广泛的研究。 在统计方法中，聚类是多元数据分析的三大方法之一( 其它两种是回归分析 和判别分析) 。它主要研究基于几何距离的聚类，如欧式距离、明考斯基距离等。 传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序 样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类， 它需要考察所有的个体才能决定类的划分。因此它要求所有的数据必须预先给 定，而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度，难 以适用于数据库非常大的情况。 在人工智能中，聚类又称作无监督归纳( u n s u p e r v i s e dj n d u c t i o n ) 。因为和分 类学习相比，分类学习的例子或数据对象有类别标记，而要聚类的例子则没有标 记，需要由聚类学习算法来自动确定。很多人工智能文献中，聚类也称概念聚类 ( c o n c e p tc l u s t e r i n g ) 。因为这里的距离不再是统计方法中的几何距离，而是根据 概念的描述来确定的。当聚类对象可以动态增加时，概念聚类则称是概念形成 ( c o n c e p tf o n a t i o n ) 。 近几年来，随着数据挖掘的发展，聚类以其特有的优点，成为数据挖掘研究 领域中一个非常活跃的研究课题。在数据挖掘里，面临的常常是含有大量数据的 数据库，因此要探讨面向大规模数据库的聚类方法，以适应新问题带来的挑战。 2 2 1 聚类算法介绍 目前在文献中存在大量的聚类算法【2 9 】。算法的选择取决于数据的类型、聚类 的目的和应用。大体上，主要的聚类算法可以划分为如下几类： ( 1 ) 划分方法( p a n i t i o n i n gm e t h o d ) i 批3 6 】 给定一个n 个对象或元组的数据库，一个划分方法构建数据的k 个划分，每 个划分表示一个聚类簇，并且k n 。也就是说，它将数据划分为k 个组，同时 满足如下的要求：( i ) 每个组至少包含一个对象；( i i ) 每个对象必须属于且只属于 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 一个组。注意在某些模糊划分技术中，第二个要求可以放宽。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一 种迭代的重定位技术，尝试通过对象在划分问移动来改进划分。一个好的划分的 一般准则是：在同一个类中的对象之间尽可能“接近”或相关，而不同类中的对 象之间尽可能“远离”或不同。还有许多其他划分质量的评判标准。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际 二， 绝大多数应用采用了以下两个比较流行的启发式方法：( i ) k 平均算法，在该算法 中，每个簇用该簇中对象的平均值来表示。( i i ) k - 中心点算法，在该算法中，每个 簇用接近聚类中心的一个对象来表示。这些启发式聚类方法，对在中小规模的数 据库中，发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形 状的聚类，基于划分的方法需要进一步的改进。 ( 2 ) 层次的方法( 1 1 i e r a r c h i c a lm e t h o d ) 1 2 6 】 层次的方法对给定的数据对象集合进行层次的分解。根据层次的分解如何形 成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法， 一开始将每个对象作为单独的一个组，然后相继合并相近的对象或组，直到所有 的组合并为一个( 层次的最上层) ，或者达到一个终止条件。分裂的方法，也称 为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一 个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终 止条件。 层次的方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤 销。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较 小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改 进层次聚类的结果：( i ) 在每层划分中，仔细分析对象间的“联接”，例如c u r e 和c h a m e l e o n 中的做法。( i i ) 综合层次聚类和迭代的重定位方法。首先用自底向 上的层次算法，然后用迭代的重定位来改进结果。例如在b i r c h 中的方法。 ( 3 ) 基于密度的方法( d e n s i t v - b a s e dm e t b o d ) 【8 9 1 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状 的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类 方法，其主要思想是：只要临近区域的密度( 对象或数据点的数目) 超出某个闽 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域 中必须包含一定数目的点。这样的方法可以用来过虑“噪音”孤立点数据，发现 任意形状的簇。 d b s c a n 是一个有代表性的基于密度的方法，它根据一个密度闽值来控制簇 的增长。0 p t i c s 是另一个基于密度的方法，它为自动的和交互的聚类分析提供 一个聚类顺序。 ( 4 ) 基于网格的方法( g r i d b a s e dm e t h o d ) 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。 所有的聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优 点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每 一维的单元数目有关。 s l r i n g 是基于网格方法的一个典型例子。c l l q u e 和w a v e c l u s t e r 这两种算 法既是基于网格的，又是基于密度的。 ( 5 ) 基于模型的方法( m o d e l - b 鹤e dm e t h o d ) 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。 一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。 它也基于标准的统计数字自动决定聚类的数目，考虑“噪音”数据或孤立点，从 而产生健壮的聚类方法。 一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算法划分 为属于某类聚类方法是很困难的。此外，某些应用可能有特定的聚类标准，要求 综合多个聚类技术。 在接下来的一节中，我们将详细讨论上述的基于密度的聚类方法。 2 2 2 基于密度的聚类方法 为了发现任意形状的聚类结果，提出了基于密度的聚类方法。这类方法将簇 看作是数据空间中被低密度区域分割开的高密度对象区域。 ( 1 ) d b s c a n 【8 j ：一个基于高密度连接区域的密度聚类方法 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 f j n go fa p p l j c a t i o n sw i t hn o i s e ) 是+ 个 基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带有 7 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 “噪音”的空间数据库中发现任意形状的聚类。它定义簇为密度相连的点的最大 集合。 。 基于密度的聚类算法涉及一些新的定义。 给定对象半径e 内的区域称为该对象的e 领域。 如果一个对象的e 领域至少包含有最小数目m i n p t s 个对象，则称该对象 为核心对象。 给定一个对象集合d ，如果p 在q 的e - 领域内，而q 是一个核心对象， 我们说对象p 从对象q 出发是直接密度可达的。 如果存在一个对象链p 1 ，p 2 ，p 丑，p l = q ，p n = p ，对p i d ，( 1 = i _ 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 t v r c a c h a b l e ) 。 如果对象集合d 中存在一个对象o ，使得对象p 和q 是从。关于e 和 m i n p t s 密度可达的，那么对象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 c a n 通过检查数据库中每个点的e 一领域来寻找聚类。如果一个点d 的 一领域包含多于m i n p t s 个点，则创建一个以p 作为核心对象的新簇。然后， d b s o 气n 反复地寻找从这些核心对象密度可达的对象，这个过程可能涉及一些 密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。 如果采用空间索引，d b s c a n 的计算复杂度是o ( n l o g ( n ) ) ，这里的n 是数据库 中对象的数目。否则，计算复杂度是o ( n 2 ) 。该算法对用户定义的参数是敏感的。 ( 2 10 p t i c s 【9 】：通过对象排序识别聚类结构 尽管d b s c a n 能根据给定输入参数e 和m i n p t s 对对象进行聚类，它仍然将 选择能产生可接受的聚类结果的参数值的责任留给了用户。事实上，这也是许多 其他聚类算法存在的问题。对于真实的高维数据集合而言，参数的设置通常是依 靠经验，难以确定。绝大多数算法对参数值是非常敏感：设置的细微不同可能导 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 致差别很大的聚类结果。而且，真实的高维数据集合经常分布不均，全局密度参 数不能刻画其内在的聚类结构。 i 为了解决这个问题，提出了o p t i c s ( o r d e r i n g p o i n t st oi d e n t j 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 j n g ) 。这个次序代表了数据的基 于密度的聚类结构。它包含的信息，等同于从一个宽广的参数设置范围所获得的 基于密度的聚类。 考察d b s c a n ，我们可以看到，对一个恒定的m i n p t s ，关于高密度的( 即 较小的e 值) 聚类结果被完全包含在根据较低密度所获得的密度相连的集合中。 记住参数e 是距离，它是邻域的半径。因此，为了生成基于密度聚类的集合或次 序，我们可以扩展d b s c a n 算法来同时处理一组距离参数值。为了同时构建不 同的聚类，对象应当以特定的顺序来处理。这个次序选择根据最小的e 值密度可 达的对象，以便高密度的聚类能被首先完成。基于这个思想，每个对象需要存储 两个值核心距离( c o r cd i s t a l l c e ) 和可达距离( r e a c h a b l ed j s t a i l c e ) ： 一个对象p 的核心距离是使得p 成为核心对象的最小。如果p 不是核心对 象，p 的核心距离没有定义。 一个对象q 关于另一个对象p 的可达距离是p 的核心距离和p 与q 的欧几里 得距离两者中的较大值。如果p 不是核心对象，p 和q 之间的可达距离没有 定义。 o p t i c s 算法创建了数据库中对象的一个次序，额外存储了每个对象的核心 距离和一个适当的可达距离。已经提出了一种算法，基于0 p t i c s 产生的次序信 息来抽取聚类。对于小于在生成该次序时采用的距离e 的任何距离e ，为提取 所有基于密度的聚类，这些信息是足够的。 由于o p t i c s 算法与d b s c a n 在结构上的等价性，o p t i c s 算法具有和 d b s c a n 相同的时间复杂度。 ( 3 ) d e n c l u e ：基于密度分布函数的聚类 d e n c u j e ( d e n s i t y - b a s e dc l u s t e r i n g ) 是一个基于一组密度分布函数的聚 类算法。该算法主要基于下面的想法：( i ) 每个数据点的影响可以用一个数学函数 来形式化地模拟，它描述了一个数据点在领域内的影响，被称为影响函数 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 ( i n f l u e n c ef u n c l i o n ) ；( j 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 的影响函数是一个 函数眉：，。一瑶，它是根据一个基本的影响函数 彤( x ) = 矗( z ，y ) ( 2 1 ) 来定义的。原则上，影响函数可以是一个任意的函数，它由某个领域内的两个对 象之间的距离来决定。距离函数d ( x ，y ) 应当是自反的和对称的，例如欧几里得 距离。它用来计算一个方波影响函数( s q u a r ew a v ei n n u e n c cf i l n c t j o n ) ： k ) 一 0 二兰卜仃( 2 z ) 或者一个高斯影响函数： 一! 垒! 垣 尼一( 墨y ) = e 2 4 2 ( 2 3 ) 在一个对象x ( x f d ) 上的密度函数被定义为所有数据点的影响函数的和。 给定n 个数据对象，d = x 1 ，x 。) c 】一，在x 上的密度函数定义如下： 芹o ) = 臂( z ) ( 2 4 ) 例如，根据高斯影响函数得出的密度函数是： nd o ) 2 芘。 ) 一e 一可( 2 5 ) 根据密度函数，我们能够定义该函数的梯度和密度吸引点( 全局密度函数的 局部最大) 。一个点x 是被一个密度吸引点x 密度吸引的，如果存在一组点x 0 ， x 1 ，x k ，x o = x ，x k = x ，对0 i k ，x h 的梯度是在x i 的方向上。对一个连 续的和可微的影响函数，一个用梯度指导的爬山算法能用来计算一组数据点的密 度吸引点。 基于这些概念，能够形式化地定义中心定义的簇( c e n t e p d e f i n e dc l u s t e r ) 和 任意形状的簇( a r b i t r a r y - s h a p ec l u s t e r ) 。密度吸引点x + 的中心定义的簇是一个被 x + 密度吸引的子集c ，在x 的密度函数不小于一个阈值毫；否则，它被认为是孤 郑州大学硕士学位论文 基于k 一距离的孤立点和聚类算法研究 立点。一个任意形状的簇是子集c 的集合，每一个是密度吸引的，有不小于闽 值e 的密度函数值，并从每个区域到另一个都存在一条路径p ，该路径上的每个 点的密度函数值都不小于l 。 d e n c l u e 的优点有：( i ) 它有一个颦实的数学基础，概括了其他的聚类方法， 包括基于划分的、层次的、及基于位置的方法。( i i ) 对于有大量“噪音”的数据 集合，它有良好的聚类特性。衄) 对高维数据集合的任意形状的聚类，它给出了 简洁的数学描述。( i v ) 它使用了网格单元，只保存关于实际包含数据点的网格单 元的信息。它以一个基于树的存取结构来管理这些单元，因此比一些有影响的算 法( 如d b s o 蝌) 速度要快。但是这个方法要求对密度参数。和“噪音”阈值鼍 进行仔细的选择，因为这些参数的选择可能显著地影响聚类结果的质量。 ( 4 ) r d b k n n 【1 3 】：基于相对密度的k 近邻聚类算法 r d b 蝌( r e l a t i v ed e n s i t yb a s e dk - n e a r c s tn e i g h b o r sc l u s t e r i n g ) 也是一种 基于密度的聚类算法，由于d b s c a n 算法依赖两个参数：对象的邻域半径和点 的邻域半径内最少点数m i n p t s 。d b s c a n 对用户的参数非常敏感，使用全局密 度参数来刻画内在聚类。它是针对d b s c a n 的这些缺点提出的一种新的聚类算 法。 基于相对密度的聚类算法涉及一些新的定义。 定义1 对象p 的k 距离 对任意的正整数k 和数据集d ，对象p 的k _ 距离，记作k d i s t ( p ) ，定义为对 象p 与对象o d 之间的距离d i s 如，0 ) ，且满足： ( 1 ) 至少有k 个对象q d p ) ，使得： d i s t ( p ，q ) sd i s t ，o ) ： ( 2 ) 并且至多有( k - 1 ) 个对象q d p ，使得： d i s t ( p ，q ) o 和数据集d ，p d ，如果ir d k 懒o ) ( p ) - l i k d i s t a n c e ( o ) ) 。然而，当p 靠近。时，对象p 关于。的可达距离就是对 象。的k 距离。可达距离的目的就是确保在邻域内所有对象非常接近，这样可以 消除在可达距离上存在的任何波动。另外，当邻域内的对象更加接近时，即便k 发生变化，l o f 值也保持稳定。同样，通过选择大一点儿的k 值也可以消除在 可达距离上的波动。由于在同样的邻域内，当k 值很大时与可达距离很相似。因 此，关于。对象 p可达距离记作 r c a c h d i s t _ k ( p ，o ) ，是 r e a c h - d i s t _ k ( p ，o ) = m a x ( k d i s t 卸c e ( 0 ) ，d 0 ，o ) ) 。使用上面的数据来说明如何计算p - ， p 。，p ，和r 的可达距离。 计算p 的可达距离： 1 首先，找出p l 的k 一距离邻居：即，n k ( p 。) = ( p 。，p 。) 。 2 由于p 。的k 一距离邻居包括p 。和n ，计算基于r 和p 。的可达距离。 在p 。关于p 2 的可达距离： r e a c h - d i s l k ( p 1 ，p 2 ) = m a ) 【体- d i s t a i i c c ( p 2 ) ，d i s t ( p 1 ，p 2 ) ) = m a x ( 5 ，4 ) ，由于k - d i s t a n c e ( p 2 ) = 5 ，d ( p 1 ，p 2 ) = 4 。 = 5 。 p 关于p 3 的可达距离： r c a c h d i s t _ k ( p 1 ，p 3 ) = m a x ( k d i s t 锄c e ( p 3 ) ，d i s t ( p l ，3 ) ) = m a 】( ( 5 ，3 ) ，由于k - d i s t a l l c e ( p 3 ) = 5 ，d ( p l ，p 3 ) = 3 。 = 5 。 因此，r e a c h d i 吼一k ( p 。，o ) 。它是p 邻居的可达距离的结合。同样，p ：，p ； 郑州大学硕士学位论文基于k 一距离的孤立点和聚类算法研究 和r 的可达距离分别是r e a c h d i 趴一k ( p ：，o ) = ( 5 ，4 ) ，r e a c h d i 虬一k ( p 。，o ) = ( 5 ， 4 ) 和r e a c h d i s t k ( ，o ) = ( 6 ，7 ) 。 1 4 计算p 的局部可达密度 一个对象的邻居可能大于k 个对象，因此，比较可达距离非常不现实。也就 是说，对同一个k 值不同的对象有不同个数邻居。因为不能有效地比较可达距离 才来计算局部可达密度。对象p 的局部可达密度，记作1 r d k 0 ) 是与p 的k 近邻平 均可达距离的反比。 圳f 簪1 ， 【 j 使用样本数据计算p 1 ，p 2 ，p 3 和p 4 的局部可达密度是：l f d k ( p 1 ) = 1 ( 5 + 5 ) 2 ，= 2 1 0 ，由于( 5 ，5 ) 组成了p 1 的可达距离并且k 一距离邻居数是2 。网理，p 2 ， p 3 和p 4 的可达密度分别是l r d k ( p 2 ) = 2 9 ，1 r d k 口3 ) = 2 9 ，l r d 】【( p 4 ) = 2 1 3 。 5 计算p 的局部孤立因子 局部孤立因子就是决定一个对象对于它的邻居来说是不是一个孤立点的比 率。k 值影响局部孤立因子。由于依赖k 值，同一个对象可能有不同的局部孤立 因子值。但是，当选择足够大的k 时，局部孤立因子值不变。对象p 的局部孤立 因子，记作l o f k 是p 的局部可达密度与p 的k - 近邻的局部可达密度比率的平 均值。一般来说，如果p 的局部可达密度比p 的k 一近邻的局部可达密度更低， u 0 f k 0 ) 将会很