(计算机软件与理论专业论文)一种带有聚类功能的边界检测算法的研究.pdf_第1页
(计算机软件与理论专业论文)一种带有聚类功能的边界检测算法的研究.pdf_第2页
(计算机软件与理论专业论文)一种带有聚类功能的边界检测算法的研究.pdf_第3页
(计算机软件与理论专业论文)一种带有聚类功能的边界检测算法的研究.pdf_第4页
(计算机软件与理论专业论文)一种带有聚类功能的边界检测算法的研究.pdf_第5页
已阅读5页,还剩57页未读, 继续免费阅读

(计算机软件与理论专业论文)一种带有聚类功能的边界检测算法的研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研 究所取得的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体,均已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者:踢良璃 日期:矽户年5 月) 日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品,知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定,同意学校保留或向国家有关部 门或机构送交论文的复印件和电子版,允许论文被查阅和借阅;本人授权郑州 大学可以将本学位论文的全部或部分编入有关数据库进行检索,可以采用影印、 缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学 位论文或与该学位论文直接相关的学术论文或成果时,第一署名单位仍然为郑 州大学。保密论文在解密后应遵守此规定。 学位论文作者:孺,玖涵日期:2 矿心晖5 月罗日 摘要 摘要 当代世界是一个信息化的世界,各行各业都存在着大量的数据,人们迫切 需要将这些数据转换成有用的信息和知识,以帮助他们进行商务管理,生产控 制,市场分析,工程设计和科学探索等,于是数据挖掘便应运而生,成为信息 产业界关注的焦点。数据挖掘就是从大量数据中提取有用的知识,它涉及到很 多学科领域,包括数据库技术、人工智能、机器学习、模式识别、统计理论、 信息论、高性能计算等等。聚类分析是数据挖掘研究领域中一个重要的研究课 题,已被应用于模式识别、图像处理、数据分析,市场研究等众多领域。同时, 聚类边界分析在数据挖掘中也具有很高的研究价值,已经被广泛应用于生物学、 物理学、图像识别等各种领域。目前已经出现了很多聚类算法和边界检测算法, 但这些算法大部分都是相互独立的,并没有将聚类和边界检测相融合。另外, 己出现的关于边界检测的算法也存在很多缺陷,在实际应用中很难达到用户的 预期效果。 本文总结了前人的研究成果,并对已往的聚类边界检测算法进行了深入地 分析研究,得出这些算法要么效率低,要么边界检测精度低,要么输入参数难 以确定。为克服这些缺点,本文提出了向量夹角熵的概念和基于向量夹角熵的 边界点检测算法b d v e ,该算法充分利用了网格能够提高运算速度且能有效去 除噪声的优点。针对已往聚类算法与边界检测算法相互分离的问题,本文提出 了基于三角剖分的聚类和边界检测算法d t b o u n d ,该算法将聚类和边界检测 融为一体,充分利用了变异系数和三角剖分图能够自然地反映数据点分布特征 的优点。 本文实现了算法b d v e 和d t b o u n d ,在综合数据集上做了大量实验,并 与其它边界检测算法进行了比较,实验结果表明:算法b d v e 和d t b o u n d 都 可以快速、有效地检测出任意形状、不同大小和不同密度聚类的边界点。同时, 算法d t b o u n d 还能快速、有效地识别任意形状、不同大小和不同密度的聚类。 摘要 关键字:数据挖掘;聚类算法;边界点;向量;熵;变异系数;三角剖分 1 1 a b s t r a ( 了r a b s t r a c t t h ec o n t e m p o r a r yw o r l di sa ni n f o r m a t i o n - o r i e n t e dw o r l d ,t h e r ea r el a r g e a m o u n t so fd a t ai na l lw a l k so fl i f e ,i ti sa nu r g e n tn e e dt oc o n v e r tt h e s ed a t ai n t o u s e f u li n f o r m a t i o na n dk n o w l e d g et oh e l pp e o p l e d ob u s i n e s s m a n a g e m e n t , p r o d u c t i o nc o n t r o l ,m a r k e ta n a l y s i s ,e n g i n e e r i n gd e s i g na n ds c i e n t i f i ce x p l o r a t i o n , e t c s od a t am i n i n gh a v ee m e r g e da st h ef o c u so fa t t e n t i o ni nt h ei ti n d u s t r y d a t a m i n i n gi st oe x t r a c tu s e f u lk n o w l e d g ef r o mal a r g en u m b e ro fd a t a ;i ti n v o l v e sm a n y d i s c i p l i n e s ,i n c l u d i n gd a t a b a s et e c h n o l o g y , a r t i f i c i a li n t e l l i g e n c e ,m a c h i n el e a r n i n g , p a t t e r nr e c o g n i t i o n ,s t a t i s t i c a l t h e o r y , i n f o r m a t i o nt h e o r y , h i g h p e r f o r m a n c e c o m p u t i n ga n ds oo n c l u s t e ra n a l y s i si sa ni m p o r t a n tr e s e a r c ht o p i ci nd a t am i n i n g r e s e a r c hf i e l da n dh a sb e e na p p l i e dt op a t t e r nr e c o g n i t i o n ,i m a g ep r o c e s s i n g ,d a t a a n a l y s i s ,m a r k e tr e s e a r c ha n dm a n yo t h e rf i e l d s a tt h es a m et i m e ,c l u s t e rb o u n d a r y a n a l y s i sa l s oh a sah i g hr e s e a r c hv a l u ei nd a t am i n i n g ,a n dh a sb e e nw i d e l yu s e di n b i o l o g y , p h y s i c s ,i m a g er e c o g n i t i o na n do t h e ra r e a s n o wt h e r eh a v eb e e nm a n y c l u s t e r i n ga l g o r i t h m s a n db o u n d a r yd e t e c t i o na l g o r i t h m ,b u tm o s to ft h e s e a l g o r i t h m sa r ei n d e p e n d e n to fe a c ho t h e r , a n dd on o ti n t e g r a t ec l u s t e r i n g a n d b o u n d a r yd e t e c t i o np h a s e i na d d i t i o n ,p r e v i o u sb o u n d a r yd e t e c t i n ga l g o r i t h m sh a v e m a n ys h o r t c o m i n g si np r a c t i c a la p p l i c a t i o n sa n di t i sd i f f i c u l tt oa c h i e v et h eu s e r s d e s i r e de f f e c t t h i sd i s s e r t a t i o ns u m m a r i z e st h er e s u l t so fp r e v i o u ss t u d i e s ,a n dd e p t h l y a n a l y s eb o u n d a r yd e t e c t i o na l g o r i t h m e x i s t e da n df i n dt h a tt h e s ea l g o r i t h m sa l e e i t h e ri n e f f i c i e n t ,o rb o u n d a r yd e t e c t i o na c c u r a c yi sl o w , o rt h ei n p u tp a r a m e t e r s d i f f i c u l tt od e t e r m i n e t oo v e r c o m et h e s es h o r t c o m i n g s ,t h i sp a p e rp r e s e n tt h e c o n c e p t i o no fe n t r o p yo fa n g l eb e t w e e nv e c t o r sa n dab o u n d a r yp o i n t sd e t e c t i n g a l g o r i t h mc a l l e db d v e ( ab o u n d a r yp o i n t sd e t e c t i o na l g o r i t h mb a s e d o ne n t r o p yo f a n g l eb e t w e e nv e c t o r s ) t h ea l g o r i t h mm a k e s u s eo ft h ea d v a n t a g e so fg r i dw h i c h c a ni m p r o v et h ec o m p u t i n gs p e e da n de f f e c t i v e l yr e m o v et h en o i s e f o rt h ep r o b l e m t h a tp r e s e n t c u r r e n tc l u s t e r i n ga l g o r i t h m sa n db o u n d a r yd e t e c t i o na l g o r i t h m sa r e s e p a r a t e d ,t h i sp a p e rp r o p o s e s a na l g o r i t h mn a m e dc l u s t e rb o u n d a r yd e t e c t i n g i i i a l g o r i t h mb a s e d0 1 1d e l a u n a yt r i a n g u l a t i o n ( d t b o u n d ) i ti n t e g r a t e sc l u s t e r i n g a n db o u n d a r yd e t e c t i o n ,a n dm a k e sf u l lu s eo ft h eb e n e f i t st h a tt h ec o e f f i c i e n to f v a r i a t i o na n dd e l a u n a yt r i a n g u l a t i o ng r a p hc a nn a t u r a l l yr e f l e c tt h ed i s t r i b u t i o no f d a t ap o i n t s t h i sd i s s e r t a t i o ni m p l e m e n t st h ea l g o r i t h mb d v ea n dd t b o u n d ,a n dd o e sa 1 0 to fe x p e d m e n t si nt h ei n t e g r a t e dd a t as e t s ,a n dc o m p a r ew i t ho t h e rb o u n d a r y d e t e c t i o na l g o r i t h m s e x p e r i m e n t a lr e s u l t ss h o wt h a tb o t hb d v ea n dd t b o u n d c a nq u i c k l ya n de f f e c t i v e l yi d e n t i f yc l u s t e rb o u n d a r yp o i n t so fc l u s t e r so fa r b i t r a r y s h a p e s ,d i f f e r e n ts i z e sa n dd i f f e r e n td e n s i t i e s a tt h es a m et i m e ,d t b o u n dc a n q u i c k l ya n de f f e c t i v e l yi d e n t i f yc l u s t e r so fa r b i t r a r ys h a p e s ,d i f f e r e n ts i z e sa n d d i f f e r e n td e n s i t i e s 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 l g o r i t h m s ;b o u n d a r yp o i n t s ;v e c t o r ;e n t r o p y ; c o e f f i c i e n to fv a r i a t i o n ;d e l a u n a yt r i a n g u l a t i o n i v 目录 目录 摘要i a b s t r a c t i i i 目录v 1 引言1 1 1 研究背景及意义1 1 2 研究内容与思路2 1 3 论文组织结构3 2 数据挖掘和聚类分析4 2 1 数据挖掘概述4 2 2 聚类分析综述5 2 2 1 聚类概述5 2 2 2 聚类方法介绍6 2 2 3 基于网格的聚类算法9 2 2 4 多密度聚类算法1 1 2 3 边界点分析综述1 3 2 3 1 边界概念的提出及发展1 3 2 3 2 边界点检测算法b o r d e r 1 4 2 3 3 边界点检测算法b r i m 1 6 2 3 4 基于变异系数的边界点检测算法b a n d 1 8 2 4 本章小结2 0 3 基于向量夹角熵的边界检测算法2 1 3 1 算法提出2 1 v 目录 3 2 相关定义2 1 3 3 算法描述2 5 3 4 实验结果及分析2 6 3 4 1 参数的选择2 6 3 4 2 算法有效性验证2 7 3 4 3 时间复杂度分析3 2 3 5 本章小结3 3 4 基于三角剖分的聚类和边界检测算法3 4 4 1 算法提出3 4 4 2 相关定义3 5 4 3 算法描述3 7 4 4 实验结果及分析3 9 4 4 1 算法有效性验证4 0 4 4 2 时间复杂度分析4 5 4 2 3 参数分析4 6 4 5 小结4 7 5 总结及进一步工作展望4 8 5 1 论文总结4 8 5 2 工作展望4 9 参考文献5 1 致谢5 4 攻读硕士学位期间的研究成果5 5 v i 1 引言 1 引言 1 1 研究背景及意义 随着信息技术的不断发展及数据库系统的广泛应用,数据库中存储的数据 越来越多,尤其是互联网的普及,使得我们彻底淹没在数据和信息的汪洋大海 中,在这大量数据中潜藏着很多有用的信息和知识,如果能把这些信息和知识 从数据库中提取出来,就可以帮助我们做很多事情,如:进行商业分析、疾病 诊断、科学研究等等。要想从如此量大且涉及面宽的数据中获取知识,就需要 一种快速有效地方法和工具,传统的统计学方法已不再适合这类数据的分析, 因此一种智能化的,综合应用各学科领域知识的数据分析方法:数据挖掘( d a t a m i n i n g ) 便应运而生。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用 数据中,识别出隐含在其中的、有效的、新颖的、人们无法预知的、潜在有用 的信息和知识的过程。数据挖掘是一个多学科交叉的研究课题,它涉及到:机 器学习、数理统计、神经网络、数据库、模式识别、高性能计算等众多学科。 聚类分析作为数据挖掘领域中的关键技术之一,已被广泛应用在众多领域。 聚类_ 羽就是对数据库中的数据对象进行分组,使同一个组内的数据对象之间尽 可能相似,而不同组中的对象尽可能相异。聚类是一种无监督式的学习,通过 对大量数据进行聚类,我们能够很容易地得到数据的分布模式以及数据属性之 间的相似性关系。在数据挖掘领域中,聚类的研究主要集中在以下几个方面: 可伸缩性、处理不同数据类型的能力、发现任意形状聚类的能力、输入参数的 自动化、处理噪声数据的能力、对高维数据集的处理能力、聚类结果的可解释 性和可用性等。迄今为止,已经出现了很多聚类算法,根据算法思想,可以分 为以下几类:基于划分的方法、基于层次的方法、基于密度的方法、基于网格 的方法、基于模型的方法。划分法这要包括k 平均算法、k 中心点算法等。层 次法主要有c u r e 3 、r o c k 4 】、c h a m e l e o n 5 等。基于密度的方法主要 有d b s c a n 6 、o p t i c s 7 、d e n c l u e 8 等。基于网格的方法主要有s t i n g 9 、 w a v e c l u s t e r 1 0 、c l i q u e 1 1 等。基于模型的方法主要有两类:统计学方法和 神经网络方法。 聚类的边界分析在数据挖掘中也具有很高的研究价值,它也代表了一种潜 1 引言 在的模式,已成为数据挖掘领域中一个新兴的研究方向。聚类的边界是那些位 于聚类密度发生跳变的区域中的数据对象。这些边界数据对象可能同时具有两 个或两个以上聚类的特征,例如:在临床医学方面,对病人某种疾病特征的研 究中,有些人群可能具有这种疾病所表现出的特征,但事实上并没有该疾病, 边界点就代表了这些人群的集合,这个集合更应该引起人们的关注,因为在他 们身上可能蕴含某些重要且有趣的疾病特征n2 | 。通过对这些特殊人群深入的研 究,可能会找到某些疾病产生的深层次原因,从而做到疾病的早预防和早治疗。 边界点在数据分类中是很容易被错误分类的点,如果聚类之间分离不好,那么 处于聚类之间的边界点就很有可能被错误的分类,也可能使得本来不是同一类 的两个聚类被合并为一个聚类。另外在生物学、物理学、图像识别等各种领域 中,边界分析的应用也是很普遍的,利用边界分析识别图像的形状从而对图像 进行分类,也可以使用边界分析来标记事物对象介于两种状态之间的中间状态。 目前,也出现了一些关于聚类边界检测的算法,如:b o r d e r n 刳、b r i m n 3 1 、 b a n d 1 等,但是它们在算法的设计上都存在很多不足之处,使得在实际应用 中,这些算法表现出可用性差、效率低、边界检测精度低等缺陷。这就需要我 们设计出速度快、精度高,简单易用的边界检测算法。同时,目前所存在的聚 类算法和边界检测算法大部分都是相互独立的,并没有将聚类和边界检测相融 合。但是,在实际应用中,人们不仅需要通过聚类来发现全局数据分布模式还 需要通过边界分析来发现局部更加特殊的分布特征。因此,有必要对聚类和边 界检测进行更深入的研究,将两种算法融合在一起。 1 。2 研究内容与思路 本文主要研究聚类分析技术和聚类边界点检测技术,并对各种聚类和边界 检测算法的优缺点进行分析比较,设计出更加实用的聚类和边界检测算法,使 得它们的优点得以利用,缺点得以摒弃。由于边界点检测是数据挖掘中一个新 兴的研究领域且对实际应用有很重要的意义,因此本文将边界检测作为研究的 重点。本文的主要研究内容包括以下几个方面: ( 1 ) 本文在分析各种聚类算法优缺点的基础上,结合空间向量和信息论中 熵的概念,将网格技术,空间向量及信息熵相结合,提出一种新的基 于向量夹角熵的边界点检测算法,并通过大量实验对比,来验证算法 2 1 引言 的正确性和有效性。 ( 2 ) 由于传统的聚类算法和边界点检测算法都是相互独立的,并没有将聚类 和边界检测相融合。但是,在实际应用中,人们不仅需要通过聚类来发 现全局数据分布模式还需要通过边界分析来发现局部更加特殊的分布 特征。针对该问题本文将基于密度的聚类方法和变异系数及三角剖分相 结合,提出了基于三角剖分的聚类和边界检测算法,并在综合数据集上 进行测试,给出实验结果,同时分析了算法的时间复杂度和运行效率。 1 3 论文组织结构 本文共分五章,各章节主要内容安排如下: 第一章为引言部分,主要介绍了本课题研究的背景与意义,同时简要地说 明了研究内容与思路及论文的组织结构。 第二章主要介绍了和数据挖掘相关的理论知识,并对数据挖掘中聚类技术 做了分类总结,并对网格聚类算法和多密度聚类算法做了深入的分析,指出它 们各自存在的优缺点以及可借鉴之处。同时还详细介绍了边界检测算法 b o r d e r 、b r i m 和b a n d ,并对这些边界检测算法的优缺点进行了总结和对 比。 第三章针对第二章介绍的多密度数据集上边界检测算法所存在的一些缺 点,提出了一种基于向量夹角熵的边界检测算法。然后通过在多个综合数据集 上进行实验对比验证了算法的有效性,同时对算法的参数选择做了详细的讲解, 另外,通过在各个数据集上的时间对比分析了算法的时间复杂度。 第四章针对已往聚类算法与边界检测算法相互分离的问题,同时借鉴了变 异系数能够反映数据的分布特征并能够消除数据单位或平均数的不同对数据 空间或邻域内数据分布的变异程度比较时产生的影响这一优点,通过建立 数据集的剖分图来反映数据分布的自然结构特征,提出了基于三角剖分的聚 类和边界检测算法d t b o u n d ,该算法将聚类和边界检测融为一体,不但能够 进行边界检测还能够进行聚类分析。然后通过大量的实验对比检验了算法的有 效性,可用性和时间复杂度。 第五章对前面的研究进行了总结并对下一步工作进行了展望。 2 数据挖掘和聚类分析 2 数据挖掘和聚类分析 2 1 数据挖掘概述 随着电子信息技术和数据库技术的不断发展,人们在日常生活和实际商业 应用中积累了大量数据,而且这些数据呈爆炸式增长。面对如此海量的数据, 简单的存取和查询等操作已经无法满足人们的需要,这些操作只能从整个数据 库中提取很少一部分知识信息,而且所提取出的这些信息还是依赖于人们的经 验积累,而大部分潜在的重要信息和知识就无法提取出来,这些潜在信息对于 市场分析、商业决策、疾病诊断、科学研究等都具有很重要的参考价值。如此 大量的信息虽然给人们带来了方便,但同时也给人们带来了一个非常严峻的问 题:“数据丰富而知识贫乏”n j 引。面对如此海量的数据,如果没有一种强有力 的知识发现工具来挖掘知识,那就等于是在浪费庞大的数据资源,好比地下蕴 藏着大量的石油,去没有先进的开采设备将其开发利用。为满足人们的这种需 求,数据挖掘技术边应运而生,并显示出其强大的生命力和巨大的发展潜力。 数据挖掘又称数据库中的知识发现( k d d ) ,就是从大量的、不完全的、 有噪声的、模糊的、随机的实际应用数据中,识别出隐含在其中的、有效的、 新颖的、人们无法预知的、潜在有用的信息和知识的过程。它是一个多学科交 叉的研究课题,它涉及到:机器学习、数理统计、神经网络、数据库、模式识 别、高性能计算等众多学科。 数据挖掘过程主要由以下步骤组成:数据清理、数据集成、数据选择、数 据变换、挖掘过程、模式评估和知识表示【1 , 1 6 , 1 7 。数据挖掘系统主要有以下组成 部分:( 1 ) 数据库、数据仓库或其他信息库( 2 ) 数据库或数据仓库服务器( 3 ) 知识库( 4 ) 数据挖掘引擎( 5 ) 模式评估模块( 6 ) 图形用户界面。 数据挖掘系统可以挖掘多种类型的模式,以适应不同用户的需求和不同的 应用。同时,数据挖掘系统还能发现不同抽象层上的模式。在实际应用中,系 统允许用户给出提示,指导特定有趣模式的搜索,被发现的模式通常都有一个 可信性度量,以表示该模式可信任的程度。总之,数据挖掘功能可以分为以下 几类:概念类描述、关联分析、分类和预测、聚类分析、孤立点分析、演变分 析等。 4 2 数据挖掘和聚类分析 2 2 聚类分析综述 2 2 1 聚类概述 聚类分析是一种重要的人类行为,人类就是通过不断地改进下意识中的聚 类模式来学会如何区分各种自然界的生物对象的,如:大猩猩和猴子,动物和 植物等。聚类就是将数据对象分组成多个类或簇,使得同一个类中的对象尽可 能相似,不同类中的对象尽可能相异。聚类分析内容非常丰富,如系统聚类法、 有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。聚 类分析在现实中也有很多用途,在商业上,聚类可以帮助市场分析人员从客户 数据库中识别出不同的客户群体来,并且概括出每一类客户的购买模式或者说 习惯。从而使企业按客户的不同需求来提供相应的产品和服务。在生物学上, 聚类可以被用来对基因进行分类,帮助人们认识不同种群的固有结构和特征。 在保险行业上,聚类分析能够用来对汽车保险单持有者进行分组,同时根据住 宅类型,价值,地理位置来鉴定一个城市的房产分组。聚类分析还可以用在电 子商务网站的建设上,通过分组聚类出具有相似浏览行为的客户,并分析他们 的共同特征,从而帮助电子商务的用户更加了解不同的客户群,向客户提供更 加细致入微的服务。 数据挖掘对聚类分析的要求主要有以下几个方面: ( 1 ) 可伸缩性。现实中我们所要处理的数据往往规模很大,经常都是几百万条 的数据,如果聚类算法时间复杂度过高,就需要很长时间才能完成一次聚类, 显然是不能容忍这种情况的。这就要求我们在设计聚类算法时尽量降低时间复 杂度,使算法具有高度的可伸缩性。 ( 2 ) 处理不同类型属性的能力。实际应用中,我们需要处理的数据类型有很多, 如:数值类型、布尔型、序数型、分类或标称型、比例标度型和混合型等。这 就要求聚类算法能够处理各种数据类型。 ( 3 ) 发现任意形状聚类的能力。现实生活中的真实数据集往往是任意形状的, 而且数据集的数据分布很可能是不均匀的,而以往的很多聚类算法,只能发现 均匀密度数据集中球形的、大小相差不大的聚类。如基于划分的聚类算法只适 合发现凸面形的聚类,并且要求各个簇间的大小差别不能太大,分离的比较好。 因此设计出能够处理任意形状聚类算法是很有必要的。 ( 4 ) 最小化输入参数对领域知识的依赖性。很多聚类算法都要求用户输入一定 2 数据挖掘和聚类分析 的参数,比如期望得到的聚类数目。但是实际应用中人们往往事先不知道聚类 的个数,这就使得没有任何专业知识的用户很难选择正确的参数值。有时参数 值的一个微小变化就会导致截然不同的聚类结果。因此,在开发聚类算法时必 须最小化算法对输入参数的依赖性,尽量减少输入参数,甚至无参数聚类。 ( 5 ) 处理噪声数据的能力。现实世界中人们所收集的数据包含了很多错误数据 或未知数据,同时数据库中的记录也可能存在很多孤立点和空缺。如果聚类算 法对以上这些数据比较敏感,就可能导致低质量的聚类结果。 ( 6 ) 对记录输入顺序的无关性。有的聚类算法对数据的输入顺序比较敏感,如 同一个数据集以不同的顺序输入给同一个算法时可能会产生不同的聚类结果, 因此降低算法对数据输入顺序的敏感性具有非常重要的意义。 ( 7 ) 处理高维数据的能力。现实中数据库和数据仓库中的数据都包含了很多属 性或者若干维,有的聚类算法适合处理低维数据,在只涉及两到三维数据集上 能得到很好的聚类结果,但在聚类高维数据时很难得到理想的结果。因此,对 高维数据集进行聚类分析是一项很有挑战性的工作,且意义重大。 ( 8 ) 在各种约束条件下进行聚类的能力。在实际应用中,人们在各种约束条件 下进行聚类的事情经常发生。这就需要提高算法的灵活性以适应各种约束条件 下的聚类。 ( 9 ) 聚类结果的可解释性和可用性。一个好的聚类算法其聚类结果应该能够很 容易地被用户所理解,并能清晰直观地表示出来。 2 2 2 聚类方法介绍 到目前为止,研究人员已经提出了大量的聚类算法。在选择算法时,我们 应根据数据的类型、聚类的目的和应用等,从而选择最合适的算法。聚类算法 大致可以分为:基于划分的方法、基于层次的方法、基于密度的方法、基于网 格的聚类方法、基于模型的方法以及模糊的聚类方法。这些方法各有自己的优 缺点。 ( 1 ) 基于划分的方法 划分方法的主要思想为:给定一个包含n 个纪录的数据集,划分法首先确 定初始的k 个簇中心,再利用各个数据对象到簇中心的距离将各个对象分配到 离它最近的簇中从而创建初始的k 个分组,每个组代表一个聚类,这里k s n 。 同时这k 个分组必须满足以下条件:( 1 ) 每个分组至少包含一个数据纪录;( 2 ) 6 2 数据挖掘和聚类分析 每个纪录属于且仅属于一个分组( 说明:对于某些模糊聚类算法,这个要求可 以放宽) 。划分法在创建一个初始分组后,采用迭代重定位技术,通过将一个对 象从一个簇移到另一个簇来改进划分的质量,直到簇中心稳定。一个好的划分 准则就是:同一个分组中的记录要尽可能接近或相似,而不同组的记录要尽可 能远离或相异。 基于划分的方法主要有以下缺点:( 1 ) 要求用户必须事先给出要生成的聚 类的数目;( 2 ) 不适合于发现非凸面形状的簇;( 3 ) 不适合于发现大小差别很 大的簇;( 4 ) 对噪声点和孤立点数据非常敏感,少量的这些数据就会对聚类结 果产生极大的影响。 基于划分的算法主要有:k - m e a n s 算法【1 8 1 ,k - m o d e s 算法【1 9 1 、c l a r a n s 算法【2 0 】等。 ( 2 ) 基于层次的方法 这种方法是对给定的数据集进行层次似的分解,按照层次分解的方向不同, 可以分为两类:凝聚的方法和分裂的方法。凝聚的方法主要思想是:初始时每 一个数据点都作为一个单独的组,然后根据合并条件合并相近或相似的数据点, 直到所有分组被合并为一个组或者满足了某个停止条件。这正好是一个自底向 上的聚类过程。与之相反,分裂的方法采用自顶向下的策略,初始时,将所有 数据对象置于同一个聚类中,然后采用迭代法并按照某种分裂原则将一个聚类 分裂为更小的类,直到每个数据对象都是单独的一个聚类,或者满足给定的停 止条件。 基于层次的方法的优点是:能够发现复杂形状和不同大小的聚类,对不同 规模的数据集具有较好的线性伸缩性,一般时间复杂度都是0 ( n ) ,能得到较好 的聚类质量。但是这种方法的缺点是:一旦一个合并或分裂步骤完成,将不能 被撤销,聚类之间也不能通过交换数据对象来改变聚类结果。这就导致如果某 一步没有选择好合并或分裂的条件,就会产生低质量的聚类结果。 典型的层次聚类算法有:b i r c h 算法瞳、c u r e 算法。、c h a m e l e o n 算 法旧等; ( 3 ) 基于密度的方法 基于密度的聚类方法的提出是为了发现任意形状的聚类。该方法认为聚类 是数据空间中被低密度区域分割开的高密度区域。该方法以对象的局部密度的 高低作为聚类的判断标准,将具有足够高密度的区域作为聚类。 2 数据挖掘和聚类分析 聚类算法:d b s c a n 呻1 、o p t i c s 订1d e n c l u e 隅1 等都是基于密度的方法的 代表。 ( 4 ) 基于网格的方法 基于网格的方法首先将数据空间划分为有限数目的网格单元,然后以单个 的网格单元作为处理的对象。这就大大提高了算法的运行速度,通常处理时间 独立于目标数据库中记录的个数,只与数据空间中每一维上的单元数目有关。 该方法可以有效地取出噪声点和孤立点的影响,发现任意形状的聚类,能够很 容易地扩展到高位数据空间,但对输入参数比较敏感。时间复杂度最快可达到 o ( n ) 级别,但这可能降低聚类的质量和精确性。 基于网格的聚类算法主要有:s t i n g 算法1 、w a v e c l u s t e r 算法n 川、 c u q u e 算法n 、s c i 瞳2 1 算法等。 ( 5 ) 基于模型的方法 基于模型的方法通常假设数据是根据潜在的概率分布生成的。这种方法可 以分为两类:统计学方法和神经网络方法。该方法主要是寻找能够匹配数据分 布特征的数学模型,充分运用了数理统计和概率论中的相关理论知识。聚类模 型对数据分布的拟合性直接影响着聚类质量,因此一个适合具体应用的数学模 型的选择至关重要。神经网络聚类方法是在模拟动物神经网络行为特征上发展 起来的,是一种能够进行分布式并行信息处理的算法数学模型。神经网络方法 通常具有较长的处理时间和较高的时间复杂度,很难适应大型数据库的聚类。 基于模型的方法有的通过构建反映数据点空间分布的密度函数来定位聚类,有 的根据标准的统计数字自动确定聚类的数目,由于基于模型的方法在设计时考 虑到了噪声和异常数据,并可以自动确定聚类的个数,因此能够产生鲁棒的聚 类算法。 基于模型的聚类算法主要有:统计学方法c o b w e b 算法、神经网络方法 s o m ,l v q ( l e a r n i n g v e c t o rq u a n t i z a t i o n ) 。 ( 6 ) 模糊聚类方法 传统的聚类算法成为硬分类算法,即一个数据对象属于且仅属于另一个聚 类,具有非此即彼的性质。而模糊聚类方法则是一种软分类方法,一个数据对 象不再只属于一个类,而是用概率来表示属于某个类的程度。这是由于事物之 间的界限,有些是确切的,有些是模糊的。因此在某些应用中,如:判断人的 面貌相似程度、预测天气的阴与晴,使用模糊聚类能够更好地反映事物的本质 2 数据挖掘和聚类分析 特征。目前,模糊聚类分析广泛应用在气象预报、地质、农业、林业等方面。 模糊聚类分析可分为:系统聚类法和逐步聚类法。模糊聚类分析是建立在模糊 相似矩阵的基础上,不同的模糊相似矩阵会产生不同聚类结果,即使模糊相似 矩阵相同,但不同的参数阈值也会产生不同的聚类结果,因此研究模糊聚类有 效性的判断标准一个非常重要的问题。主要的模糊聚类算法有模糊c 均值f c m ( f u z z yc m e a n s ) 比3 2 钔算法等。 在实际应用中,采用单一的聚类算法往往不能达到理想的效果,因此将不 同的聚类算法结合起来,集他们的优点于一体,摒弃缺点便成为数据挖掘的一 个重要研究方向。 2 2 3 基于网格的聚类算法 ( 1 ) s t i n 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 ) 旧。是一种基于网格的多分辨率聚类算 法。在该算法中,数据空间被划分成具有多个级别的网格单元,不同级别的网 格单元具有不同的分辨率,这些网格单元形成了一个层次结构:高层的网格单 元由多个低一层的网格单元所组成。每个网格单元的属性统计信息被事先计算 和存储。我们可以通过计算低层网格单元的统计信息来得到高层网格单元的统 计参数,这对我们满足客户的查询处理至关重要。 该算法采用自顶向下的基于网格的方法回答用户提出的各种查询。首先, 从层次结构中选择一个包含较少网格单元的层次开始查询处理。计算当前层次 中每个网格单元的置信度区间,以评估该单元与给定查询的关联程度,若关联 程度没有达到要求则不予考虑。然后开始处理相关单元中低一层次的单元。重 复上述过程,一直到最低层。在查询过程中如果相关单元的区域满足了查询要 求则返回该区域。否则,继续查询相关单元中的数据,知道满足查询要求。 s t i n g 主要优点是:( 1 ) 基于网格的计算事先将有关网格单元属性的信息 计算好并存储起来,方便用户查询;( 2 ) 网格结构使得在计算时可以采用并行 计算和增量更新;( 3 ) 网格技术使得算法时间复杂度低,执行效率高。 s t i n g 设计也有它自身的缺点如:s t i n g 聚类结果的质量依赖于网格结构 最低层的粒度,若最低层网格的粒度太细,就会增加算法的处理时间:相反, 若最低层的粒度太粗,就会产生低质量的聚类结果。另外,该算法会导致聚类 边界的丢失,降低聚类结果的精确性。 9 2 数据挖掘雨i 聚类分析 ( 2 ) c l i q u e c l i q u e 1 是一个经典的融基于密度和基于网格的方法为一体的网格聚类 算法,适合于大规模高维数据集。多维大规模数据空间中的数据点的分布一般 是不均衡的。c u q u e 算法通过识别数据空间中稀疏和稠密单元来找到数据集 合的整体分布模式。另外,如果某个单元格中的数据点个数大于给定的参数值, 则称这个单元为密集单元。否则成为稀疏单元。聚类就是相连密集单元的最大 集合。 c u q u e 分两步来进行多维聚类: 第一步,c l i q u e 算法将整个数据空间中的每一维划分为长度相等的区间, 从而形成互不相交的矩形网格单元,识别其中的稀疏单元和密集单元。这些密 集单元组成了候选搜索空间,低维子空间中密集单元的交集形成了更高维的密 集单元的候选搜索空间,这是由于c u q u e 采用基于关联规则挖掘中的先验性 质:若一个k 维单元是密集的,那么它在k 一1 维空间上的投影也是密集的。利 用这个先验性质可以有效地裁剪数据空间,以减少多余的不必要的数据空间的 搜索。 第二步,c l i q u e 为每个聚类生成最小化的描述。对于每个聚类,c l i q u e 首先确定相连密集单元的最大区域,然后再确定这个最大区域的最小覆盖。 c u q u e 算法的优点是:能够自动发现高维子空间中的聚类、对元组输入 顺序不敏感、时间复杂度低并且当维数增加时具有良好的可伸缩性。但是,该 方法可能会产生过度拟合现象,即把一个类划分为好几个类;还可能会丢失某 个子空间中的聚类;忽略了稀疏单元导致丢失聚类边界;这就降低了聚类的精 确性。 ( 3 )s c i s c i 心羽聚类算法改进了c u q u e ,s t i n g ,w a v e c l u s t e r 算法中的一些缺点 如:它们忽略了稀疏单元,将稀疏单元中的点都作为噪声,但稀疏单元中的有 些数据点如果靠近聚类密集单元,则应将这些数据点划归到稠密单元中;另外, 在高位数据空间中,有些属性可能对于聚类分析没有用,若不去掉这些属性, 则会影响到算法的执行效率。 s c i 为了提高聚类的精度,将非孤立单元中的点和距离它们最近的密集单 元相连接,把这些点分配给距离它们最近的密集单元所属的聚类。同时,s c i 将一个单元的邻居单元定义为那些和该单元有一个共同边或有一个单独的点相 1 0 2 数据挖掘和聚类分析 连的单元的集合。另外,s c i 认为:若一个稀疏单元的所有邻居单元都是稀疏 的,则称该稀疏单元中的点为噪声或孤立点。这就消除了c u q u e ,s t i n g , w a v e c l u s t e r 中的过度拟合现象。s c i 在聚类时,首先通过计算各属性维的信息 熵来除去那些对聚类无用或影响少的属性,然后连接稠密网格单元生成初始聚 类结果,最后识别稀疏网格单元格中的边界点,提高聚类的精度。 该算法采用了基于熵的属性选择方法,把某些没有用的属性去掉,提高了 算法的执行效率,时间复杂度为o ( n ) 。同时也对聚类的边界做了处理,提高了 聚类的精度,能够识别任意形状不同大小的聚类,对数据输入顺序不敏感。 s c i 算法的主要缺点是:对输入参数比较敏感,算法的空间复杂度较高, 为o ( k d ) 。其中,k 是在每一维上划分的间隔数,d 是维度。 2 2 4 多密度聚类算法 目前,已经出现的很多聚类算法都能够在均匀密度数据集上有效地识别不 同形状,不同大小的聚类,但是,这些算法却不能很好地在多密度数据集上聚 类,因为多密度数据集中的数据分布是不均匀的,而且各个

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论