（计算机应用技术专业论文）基于数据场的聚类方法研究.pdf

哈尔滨_ 亡程大学硕士学位论文 摘要 随着信息化时代的来临，大量数据的产生和收集导致信息大爆炸，数据 挖掘技术已成为现在计算机科学的研究热点。聚类分析是数据挖掘中一种重 要的挖掘任务和挖掘方法，使得聚类算法的效率和聚类质量在数据挖掘中起 着至关重要的作用，也成了计算机科学领域的难题之一。 基于密度的聚类算法是聚类分析的重要分支，以其能够发现任意形状的 聚类、能够有效地处理噪声数据的优点在聚类算法中占有很重要的地位。 d b s c a n 算法是经典的基于密度聚类算法，它不但具有基于密度聚类算法的 优点，而且聚类速度较快。但是该算法也有不足之处：聚类参数选择困难； 当数据集密度分布不均匀时聚类质量差；初始聚类对象随机选择造成时间浪 费；对所有种子对象进行区域查询造成时间和内存浪费。 为解决d b s c a n 算法中存在的问题，作者考虑到数据空间中的数据并不 是独立的而是有一定的相互影响，结合数据场的思想对d b s c a n 算法进行了 改进，提出了一种新的基于数据场的密度聚类算法叫f d b s c a n 。该算法 将物质粒子间的相互作用及其场的描述方法引入抽象的数据空间，利用数据 空间中数据场场势与数据密度分布之间的关系，对d b s c a n 算法几个不足之 处进行了改进。 该算法采用了动态计算聚类半径的策略，使得算法在密度分布不均匀的 情况下聚类质量良好。同时算法还利用了场势和数据空间中数据分布密度的 之间的关系对初始聚类对象的选择和种子对象的选择问题上进行了改进。使 得算法在时间复杂度与d b s c a n 算法相当的情况下提高了聚类质量，并且在一 定程度上提高了算法的执行效率，既节约了时间资源又节约了内存资源。该 算法有一定的数学基础，也有一定的理论依据，同时也通过了实验数据下的 验证。 关键词：聚类分析；数据场；d f d b s c a n ；聚类质量 哈尔滨丁程大学硕十学位论文 a b s tr a c t w i t ht h ea d v e n to ft h ei n f o r m a t i o na g e ，p r o d u c t i o na n dc o l l e c t i o no fm a s s d a t al e a d st oi n f o r m a t i o ne x p l o s i o n ，a n dd a t am i n i n gh a sb e c o m eh o tr e s e a r c h s p o t i nc o m p u t e rs c i e n c ea r e a a sa ni m p o r t a n c et a s ka n dm e t h o df o rd a t a m i n i n g ，c l u s t e r i n ga n a l y s i sh a sag r e a ti m p a c to na l g o r i t h m i ce f f i c i e n c ya n d c l u s t e r i n gq u a l i t y , w h i c hi so n eo fd i f f i c u l tp r o b l e m si nc o m p u t e rs c i e n c ea r e a a sa ni m p o r t a n tb r a n c ho fc l u s t e r i n ga n a l y s i s ，c l u s t e r i n ga l g o r i t h mb a s e do n d e n s i t yh a s ap r i n c i p a lp o s i t i o nb e c a u s ei ti sa b l et od i s c o v e r c l u s t e r i n go f a r b i t r a r ys h a p ea n di tc a nd e a lw i t hn o i s ed a t ae f f e c t i v e l y d b s c a ni sac l a s s i c d e n s i t y - b a s e dm e t h o d ，a n di th a sn o to n l ya d v a n t a g e so fg e n e r a ld e n s i t y - b a s e d m e t h o d ，b u ta l s oh i g hs p e e d h o w e v e r , i th a sm a n yd i s a d v a n t a g e s f o ri n s t a n c e ， c l u s t e rp a r a m e t e r sa r eh a r dt o c h o o s e ；c l u s t e r i n gq u a l i t yi sl o ww h e np a r t i t i o n d e n s i t i e sa r en o te q u a l ；t h er a n d o mc h o i c e o fi n i t i a lc l u s t e r i n go b j e c tw a s t e st i m e ； f i e l ds e a r c h i n gt oa l ls e e do b j e c t sc o s t sc o m p u t e rm e m o r ya n dt i m e t or e s o l v ed i s a d v a n t a g e so fd b s c a n ，c o n s i d e r i n gt h a td a t ai nd a t as p a c ei s n o ti n d 印e n d e n tb u th a si n f l u e n c ew i t he a c ho t h e r , t h ea u t h o rc o m b i n e sc l u s t e r w i t l lt h et h e o r y0 1 1d a t af i e l dt oi m p r o v ed b s c a n t h ea u t h o rp u tf o r w a r dan o w d e n s i t y - b a s e dc l u s t e r i n g m e t h o db a s e do nd a t a f i e l d ( d f d b s c a n ) t h e a l g o r i t h mp u t st h ei n t e r a c t i o nb e t w e e nm a t e r i a lp a r t i c l e sa n dt h ef i e l dm e t h o d s i n t oa b s t r a c td a t as p a c e ，a n di m p r o v e sd b s c a n a l g o r i t h mf o ri t si n a d e q u a c i e sb y u s i n gt h er e l a t i o n s h i pb e t w e e nd a t af i e l dp o w e ri nt h ed a t as p a c ea n dd a t ad e n s i t y d i s t r i b u t i o n t h ea l g o r i t h ma d o p t sd y n a m i cs t r a t e g yt oc a l c u l a t et h ec l u s t e r i n gr a d i u s ，a n d s o l v e st h ep r o b l e mo fd a t am i s d i s t r i b u t i o n a tt h es a m et i m e ，a l g o r i t h mu t i l i z e s r e l a t i o n s h i pb e 铆e e nf i e l dp o t e n t i a la n dt h ed e n s i t yo fd a t ad i s t r i b u t i o nt oi m p r o v e t h ec h o i c eo fi n i t i a lc l u s t e r i n go b j e c ta n ds e e do b j e c t s t h e r e f o r e ，s a i n e 勰t i m e c o m p l e x i t yo fd b s c a n ，d f d b s c a na s c e n d sc l u s t e r i n gq u a l i t y 鹪w e l l 弱 c l u s t e r i n ge f f i c i e n c y t h u s ，t h ea l g o r i t h me f f i c i e n c yh a sb e e ni m p r o v e dt os o m e 哈尔滨_ 丁程大学硕七学位论文 e x t e n ta n dt h ea l g o r i t h md o e sn o to n l ys a v et i m eb u ta l s ot h em e m o r yr e s o u r c e s t h ea l g o r i t h mb a s e do nm a t h e m a t i c sa n dh a v et h e o r e t i c a lb a s i s a tt h es a m e t i m e ， t h ea l g o r i t h mi sv e r i f i e db yt h ee x p e r i m e n t a ld a t a k e yw o r d s ：c l u s t e r i n ga n a l y s i s ，d a t af i e l d ，d f d b s c a n ，c l u s t e r i n gq u a l i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ： 飞乍凡锄 日期：晰年月厂弓日 ) 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ： m - 导师( 签字) 日期：乙叼年月房1 日。乙叼年；月， 日 哈尔滨工程大学硕士学1 ：i 7 ：论文 第1 章绪论 1 1 课题的研究背景及意义 二十一世纪是信息化的时代，数据早已充满了人们的日常生活，大量数 据的产生和收集导致信息爆炸，大量的信息在给人们提供方便的同时也带来 了一系列问题：由于信息量过大，超出了人们掌握、理解的能力，因而给正 确运用这些信息带来了困难。目前的数据库系统可以高效地实现数据的录入、 查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的 数据预测未来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段，从而导致 了“数据爆炸但知识贫乏的现象。为了进一步提高信息的利用率，科学界 引发了一个新的研究方向：数据挖掘。 近些年，不同领域的学者利用各自不同的技术和方法对数据挖掘进行了 卓有成效的研究，然而，如何将不同领域的理论、技术等进行融合将是下一 阶段的研究中心，这些研究将行进在充满挑战而又极富发展潜力的漫长之路 上。 聚类分析【l 】是数据挖掘中一种重要的挖掘任务和挖掘方法。聚类就是将 数据对象分组成多个类或簇，在同一个类中的对象之间具有较高的相似度， 而不同类中的对象差别较大。通过聚类，人们能够识别密集和稀疏的区域， 从而发现全局的分布模式及数据属性之间的有趣的相互关系。 聚类分析已经广泛地用在许多应用中，包括模式识别、数据分析、图像 处理、市场研究以及生物学等。在生物学上，聚类能用于推导植物和动物的 分类，对基因进行分类，获得对种群中固有结构的认识。在市场研究方面， 聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模 式来刻画不同的客户群特征。聚类也能用于对w e b 上的文档进行分类，以发 现信息。作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得 数据分布情况。可见，聚类分析有必要而且已经成为数据挖掘领域中一个非 常活跃的研究课题。 哈尔滨t 程大学硕士学位论文 1 2 数据挖掘的定义 数据挖掘【l 】( d m ，d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、 模糊的、随机的数据中，提取隐含在其中的，人们事先不知道的、但又是潜 在的有用信息和知识的过程。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定 义包括几层含义：数据源必须是真实的、大量的、有噪声的：所发现的是用 户感兴趣的知识；所发现的知识要可接受、可理解、可运用；所发现的知识 仅支持特定的发现问题。 人们把原始数据看作是形成知识的源泉，数据挖掘就像从矿石中采矿一 样。数据挖掘所依赖的原始数据来源多种多样，可以是我们平时常用的关系 数据库、事务数据库、文本数据库、多媒体数据库等，主要取决于用户的使 用目的及所处的科学领域。目前，数据挖掘的数据大多取自关系数据库与数 据仓库。原始数据可以是结构化的，如关系数据库中的数据，也可以是半结 构化的，如文本、图形、图像数据，甚至可以是分布在网络上的异构型数据。 发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以 是归纳的。发现的知识可以被用于信息管理、查询优化、决策支持、过程控 制等，还可以用于数据自身的维护。因此，决定了数据挖掘是一门复合型的 交叉学科，是当前计算机界的一大热点研究领域，现阶段数据挖掘已经被广 泛应用于商务管理、生产控制、遥感图片分析、情报分析、工程设计以及科 学探索等很多领域。由此，它吸收采用了数据库、人工智能、数理统计、可 视化、并行计算等多个领域的最新成果，被学术界和工业界以及很多科研领 域所广泛重视。 1 3 数据挖掘的分类 数据挖掘涉及的学科、领域很广泛，以至于目前数据挖掘的方法和算法 种类很多，有必要对这些方法分类。数据挖掘分类方法很多。根据挖掘任务 的不同，可分为分类或预测模型发现、数据总结、聚类、关联规则发现、序 列模式发现、依赖关系或依赖模型发现、异常和趋势发现等。根据挖掘对象 2 哈尔滨丁程大学硕士学何论文 的不同，有关系数据库挖掘、面向对象数据库挖掘、空间数据库挖掘、时态 数据库挖掘、文本数据库挖掘、多媒体数据库挖掘、异构数据库和遗产数据 库挖掘以及w c b 挖掘。根据挖掘方法的不同，可分为机器学习方法、统计方 法、神经网络方法和数据库方法。机器学习包含归纳学习方法、基于案例学 习、遗传算法等。统计方法包含回归分析、判别分析、聚类分析、探索性分 析等。神经网络方法包含前向神经网络、自组织神经网络等。这里我们根据 挖掘任务的不同对其进行分类简单介绍。 1 分类与预测 分类是一种重要的数据挖掘技术，数据分类的目的根据数据集的特点构 造一个分类函数或分类模型，此模型能够把未知类别的样本映射到给定类别 之一。这里用于建立模型的数据称为训练集，通常是已经掌握其特性或规律 的历史数据。实际使用时，既可以用此模型分析已有的数据，也可以用它来 预测未来的数据。 预测数据是构造和使用模型评估无标号样本类，或评估给定样本可能具 有的属性值或值区间。预测数据先用已知数据对象组成一个训练数据集，并 在训练集中取值，然后建立起描述数据对象特征与预测属性值之间相关关系 的预测模型，最终利用这个预测模型对预测属性取值未知的数据对象进行预 测。 2 聚类分析 将一组对象的集合划分为由类似的对象所组成的多个类的过程称为聚 类。聚类如同通常所说的“物以类聚 ，是考察个体或对象间的相似性，把 它们按照相似性归成若干类别，它的目的是使属于同一类别的个体之间的“距 离 尽可能小，而不同类别上个体间的“距离 尽可能的大，反映的是同类 事物共同性质的特征型知识和不同事物之间差异性质的特征型知识。 3 关联规则挖掘 关联分析的目的就是为了挖掘出隐藏在数据间的关联模式，即从数据中 挖掘出满足一定条件的依赖性关系。关联规则形式：( x = y ，支持度= s ， 置信度= c ) ，这里x 称为规则的条件，y 称为规则的结果。规则x y 的支 持度s 是指含有x 的记录在全体记录中所占的比率，置信度c 是指同时含有 x 和y 的记录数与含有x 的记录数的比率。“尿布和啤酒 的问题就是种 3 哈尔滨工程大学硕十学位论文 典型的关联模式。 4 序列分析及时间序列 序列分析及时间序列描述对象行为随时间变化的规律或趋势，并对其建 模。序列分析和时间序列说明数据中的序列信息和与时间相关的序列分析。 这可能包括与时间相关数据的特征化、区分、关联、分类或聚类，但这类分 析的不同特点包括时间数据分析、序列或周期模式匹配和基于相似性的数据 分析。例如：“在某一时间购买v c d 的顾客，有8 0 在一周内会购买光碟 就是一个序列模式。 5 孤立点分析 任何事物都要一分为二来看，就像有时一个人认为是毫无价值的消息对 另一个人来说却非常重要。孤立点可以看作是实际生活中的反常现象的写照。 从距离的观点来看，孤立点就是那些离密度较高的大部分点较远的点。孤立 点分析可以使用统计试验检测或基于偏差的方法。 1 。4 本文的研究内容及组织结构 本文首先介绍了课题的研究背景和意义，介绍了各种聚类分析方法以及 聚类算法的研究方向。然后重点介绍了聚类分析，并且详细介绍了基于密度 的聚类算法d b s c a n 。在分析d b s c a n 算法的不足之处后，本文介绍了数 据场的相关概念，提出了基于数据场的d b s c a n 算法d f d b s c a n ，接 着以一系列对比实验验证了算法的正确性。 本文共分五章，各章的内容安排如下： 第1 章为绪论部分，介绍了课题的研究背景及意义，数据挖掘的分类以 及论文的组织结构。 第2 章主要介绍了聚类分析，首先介绍了聚类分析的各种方法，有基于 划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模 型的方法；然后介绍了聚类分析中的数据类型和聚类算法的研究方向；最后 较详细地介绍了基于密度的聚类算法中的d b s c a n 。 第3 章首先分析了d b s c a n 算法的局限性，针对其不足结合数据场的思 想提出了基于数据场的密度聚类算法一一d f d b s c a n ，并介绍了 4 哈尔滨工程大学硕士学何论文 d f d b s c a n 算法的概念及其思想。 第4 章详细描述了d f d b s c a n 算法，从初始对象的选择、参数的动态 变化以及种子对象的选择三个方面进行了详细说明，并且在最后给出了时间 复杂度分析。 第5 章为实验阶段，从正确性、聚类质量和效率三个方面测试该算法， 通过实验证明了该算法的正确性和可扩展性，同时证明了算法在执行效率上 的优势。 哈尔滨t 程大学硕十学位论文 第2 章聚类分析 在数据挖掘中，聚类技术一直是一个研究热点，它是将物理或抽象对象 的集合分割为由类似对象组成的多个类的过程，使得位于同一类中的对象具 有高度的相似性，而不属于同一类的对象之间差异较大。基于密度的聚类方 法以可以发现任意形状的聚类结果在聚类算法中占有很重要的地位，而 d b s c a n 算法则是基于密度的聚类算法中的经典算法。本章将向读者展示聚 类分析以及d b s c a n 算法的相关知识。 2 1 聚类分析概述 聚类又被称为非监督分类，因为和分类学习相比，分类学习的例子或对 象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确 定，即把所有样本作为未知样本进行聚类。因此，分类问题和聚类问题根本 的不同点为：在分类问题中，知道训练样本例的分类属性值，而在聚类问题 中，需要在训练样例中找到这个分类属性值。 一方面，聚类可以作为数据挖掘中一个独立的分析工具；而在某些实际 应用中，聚类又作为整个挖掘系统中的一项预处理，对数据进行聚类后，其 结果可以作为数据挖掘中其它分析的数据源。 由于聚类在数据挖掘中的广泛应用，国内外学者对聚类算法进行了各种 不同的研究，出现许多不同的方法和技术。现有的聚类算法大体可划分为以 下五类：基于划分的方法、层次聚类方法、基于密度的方法、基于网格的方 法和基于模型的方法。 2 1 1 基于划分的方法( p a r t i t i o n i n gm e t h o d ) 基于划分的方法( p a r t i t i o n i n gm e t h o d ) 是发展比较早、也比较基本的一 大类聚类分析算法。划分聚类是由一个初始划分开始，通过优化一个评价函 数把数据划分成若干子类，因此事实上已经把聚类问题转化成了优化问题。 其基本思路是：给定含有n 个样本的数据库，划分方法将数据分为k 个划分 ( 七胛) ，每个划分表示一个簇，同时满足：每个簇至少包含一个样本；每个 6 哈尔滨工程大学硕士学位论文 样本必须属于且仅属于一个簇。对于基于划分的方法，一般需要一种迭代控 制策略，对原型不断地进行调整，从而使得整个聚类得到优化。常见的基于 划分的方法有k m e a i l s ( k 均值方法) 和k m e d o i d s ( k 中心点方法) ，其它 的基于划分的方法都是基于这两种方法的变形。 1 k m e a i l s 算法 假设有n 个对象的数据库需要分成k 个簇，在k - m e a i l s 算法中，首先随 机选择k 个对象代表k 个簇，每一个对象初始地作为一个类平均值或中心， 然后计算对象与各个簇的质心距离，将剩余的对象划分到距离其最近的簇。 在完成首次对象的分配之后，以每一个类中所有对象的各属性均值( m e 肌s ) 作为该类新的中心，进行对象的再分配，重复该过程直到类的中心不再变化 为止，从而得到最终的k 个类。k - m e 锄s 算法处理大规模数据集时，该算法 是相对可扩展的，并且具有较高的效率。它的计算复杂度是o ( n k t ) ，其中，n 是数据集中所有对象的数目，k 是期望得到的簇的数目，t 是迭代的次数。通 常k n 且t m i n p t s ，则点p 从点q 直接密度可达( d i r e c t l yd e n s i t y - r e a c h a b l e ) 。 对于两个点，直接密度可达不是对称的。如图2 2 ，p 从q 直接密度可达， 但q 却不从p 直接密度可达。 定义2 - 4 给定e p s 、m i n p t s ，若存在点的一个链p l ，p 2 ，p 一，其中 p l = p ，力= g 且有p 到p + - 直接密度可达，则点p 从点q 密度可达 ( d e n s i t y - r e a c h a b l e ) 。 对于两个点，密度可达也不是对称的。如图2 3 ，p 从q 密度可达，但q 却不从p 密度可达。 图2 2 直接密度可达示意图 图2 3 密度可达示意图 1 9 哈尔滨下程大学硕士学侮论文 i ili- i 定义2 5 给定e p s ，m i n p t s ，若存在点o ，使得点p 和点q 都从o 密度可 达，则点p 和点q 是密度相连( d e n s i t y - c o n n e c t e d ) 的 如图2 4 ，p 和q 密度相连。 - 图2 4 密度相连示慈图 定义2 6 数据集d 的非空子集c 是一个簇( c l u s t e r ) ，当且仅当c 满足以 下两个条件： ( 1 ) ( 极大性) 对于坳，留，若p c ，且q 从p 密度可达，则留c ； ( 2 ) ( 连通性) 对于砌，鼋，若有p c 和q c ，则p 和q 是密度相连的。 定义2 7 簇中密度不低于m i n p t s 的点称为核心点( c o r ep o i n t ) 。 定义2 8 不是核心点、但是从某核心点密度可达的点，由于位于簇的边 界，因此被称为边界点( b o r d e rp o i n t ) 。 定义2 - 9 数据集d 中不属于任何簇的点称为噪声( n o i s e ) 。 核心点、边界点和噪声如图2 5 【1 7 】： 图2 5 核心点、边界点和噪声示意图 2 0 哈尔滨工程大学硕士学位论文 引理2 1 若p 是核心点，且o 是从p 密度可达的点集，则o 是一个簇。 引理2 2 假定c 是一个簇，p 是c 中的任意一个核心点，则c 等价于从 p 密度可达的点集。 由定义2 6 及两个引理知，一个簇就是密度相连的点的最大集合，且可 以由其中任意一个核心点唯一确定。 基于上述事实，d b s c a n 的算法思想是：从数据集d 中的任意一个点p 开始，查找d 中所有关于e p s 和m i n p t s 的从p 密度可达的点。若p 是核心 点则其邻域内的所有点和p 同属于一个簇，这些点将作为下一轮的考察对象 ( 即种子点) ，并通过不断查找从种子点密度可达的点来扩展它们所在的簇， 直至找到一个完整的簇；若p 不是核心点即没有对象从p 密度可达，则p 被 暂时地标注为噪声，如果p 已经被标注为簇，则p 为该簇的边界点，噪声和 边界点都不进行扩展。然后，算法对d 中的下一个对象重复上述过程。当所 有种子点都被考察过，一个簇就扩展完成了。此时，若d 中还有未处理的点， 算法则进行另一个簇的扩展；否则，d 中不属于任何簇的点即为噪声。 假定输入参数为e p s 和m i n p t s ，d b s c a n 的算法描述如下： ( 1 ) 先从数据集d 中找到任意一个对象p ，并查找d 中关于半径e p s 和最小对象数m i n p t s 的从p 密度可达的所有对象； ( 2 ) 如果p 是核心点，即半径为e p s 的p 的邻域内所包含的对象不少于 m i n p t s 个，则确定一个关于参数e p s 和m i n p t s 的簇； ( 3 ) 如果半径为e p s 的p 的邻域中所包含的对象少于m i n p t s 个，则p 被暂时标注为噪声点； ( 4 ) 访问数据集中的下一个点，重复上述过程，直到数据集中所有的点 都被处理。 从d b s c a n 算法的聚类过程可知，获取从一个核心对象密度可达的所有 数据对象是通过反复进行区域查询( r e g i o nq u e r y ) 来实现。一次区域查询返 回给定查询区域中的所有对象。这种查询由r 树帮助实施。因此在进行聚类 之前，必须先建立树。 d b s c a n 算法使用两个参数，e p s 和m i n p t s 来控制类的密度。其中m i n p t s 是类内某一点的e p s 邻域必须包含的点的最小数目，为了减少计算量m i n p t s 在二维数据的情况下设为4 。 2 l 哈尔滨t 程大学硕十学位论文 萱ii宣iiiiiiiiiiiiii宣iiiiiiiiiiiiiiti f | 【 e p s 和m i n p t s 作为d b s c a n 算法的输入参数在该算法运行之前必须确 定。要确定e p s ，d b s c a n 算法需要计算所有数据对象与它的第k 个最临近 的对象之间的距离，并将结果按距离排序，产生k d i s t 图。k d i s t 图中的纵坐 标表示数据对象与它的第k 最临近的对象间的距离：横坐标则为对应于某一 k - d i s t 距离值的数据对象的个数，用户可以根据k d i s t 图的第一个“谷来 确定e p s 。建立r + 树和绘制k d i s t 图都是非常耗费时间的工作，大规模数据 库尤为如此。此外，用户需反复试验，选择合适的k d i s t 值以达到较好的聚 类效果。 d b s c a n 算法是典型的基于密度的聚类方法，具有聚类速度快，可以发 现任意形状的类，不受数据输入顺序的影响，能有效处理孤立点等优点。 2 5 本章小结 本章主要介绍了聚类分析方面的知识，首先介绍了聚类分析的方法，有 基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基 于模型的方法。在第二节中向读者展示了聚类分析中常用的数据类型，这里 聚类分析的数学基础，第三节介绍了聚类算法的研究方向。在最后详细介绍 了一种基于密度的聚类算法d b s c a n 。 哈尔滨工程大学硕+ 学位论文 第3 章基于数据场的密度聚类算法 d b s c a n 算法虽然具有聚类速度快，可以发现任意形状的类等优点，但 它也存在一些缺点和不足。本章将根据数域空间中数据之间并不是孤立而是 相互有影响的这一特点，把数据场引入d b s c a n 算法提出一种基于数据场的 密度聚类算法。 3 1d b s c a n 算法的局限性 d b s c a n 算法是一种典型的空间基于密度的聚类算法，该算法利用邻域 ( e p s ) 和密度的概念，要求数据空间中一定区域( e p s ) 内所包含的对象数 目不小于某一阈值( m i n p t s ) 。d b s c a n 算法的聚类速度较快，能够有效地 处理“噪声点”和发现任意形状的聚类，但是它也有一些缺陷和局限性。 1 参数选择困难 d b s c a n 要求用户输入聚类半径( e p s ) 和m i n p t s 两个参数，对于用户 来说，确定这两个参数值是比较困难的。虽然m i n p t s 值的选择已经有基于经 验的方法( 如一般二维空间将该值定为4 ) ，但是对于e p s ( 区域半径) 还要 用户根据k d i s t 图试探选定合适的值，在无形中给用户增加了很重的负担， 而且把聚类效果的好坏一部份责任推给了用户。而且算法对参数值非常敏感， 参数值的微小变化往往会导致差异很大的聚类结果。 2 数据分布不均时聚类质量差 d b s c a n 算法虽然可以发现任意形状的聚类，但是在数据稀疏程度不均 匀时聚类质量会比较差。这一点主要归究于d b s c a n 算法的参数e p s ( 聚类 半径) 是一个全局参数，这使得当数据稀疏程度不均匀的时候，若根据较密 的那些簇来选取较小的e p s 值，那么对于客观上相对分布较稀疏的那些簇中 的对象，他们邻域中的数据对象的数目将可能要小于m i n p t s ，也就是说这些 对象将被认为是“噪声点 ，从而不被用于所在簇的扩展。因此相对分布较稀 疏的簇被分成多个性质相似的簇。与此相反，若根据分布较稀疏的那些簇来 选取较大的e p s 值，那么离的较近而且密度较大的那些簇将很可能被合并为 哈尔滨t 程大学硕士学位论文 同一个类，它们之间的差异也就因为选取较大的e p s 值而被忽略。很明显， 在数据稀疏程度不均匀情况下，其实很难选取一个合适的全局e p s 值来进行 聚类且得到比较准确的聚类结果。 3 聚类时初始点的选择问题 d b s c a n 算法是从数据集d 中任意一数据对象p 开始聚类，如果p 是核 心点则其邻域内的所有对象和p 同属于一个簇，若p 不是核心点即没有对象 从p 密度可达，则p 被暂时地标注为噪声，如果p 已经被标注为簇，则p 为 该簇的边界点。在d b s c a n 算法里，只有选择到的用来开始聚类的点是核心 点才可以从该点向外扩展聚类。在这里可以作如下设想，如果算法刚开始选 择到的数据都是簇的边界或者“噪声点，那无形中是对时间的浪费，当然这 种想法是比较极端的，但并不是不可能出现。 4 用于簇扩展的种子点的选择问题 d b s c a n 算法的聚类过程其实就是一个不断进行区域查询、向簇的边界 扩张的过程。d b s c a n 算法在选择种子对象进行簇扩展的过程中，核心点邻 域内的所有对象都作为种子对象进行区域查询。这一点对于分布稀疏的数据 区域并不会造成太大影响，而对于数据分布较密集的区域，一个核心对象邻 域内的数据对象就比较多，而这些对象中有一些是没有必要作为种子对象进 行区域查询的，显然在这种情况下，对这些种子进行区域查询无形中也增加 了算法的执行时间。 3 2 数据场 现实中的大部分数据之间都不是独立的，有些数据还具有不确定性，特 别是对于空间数据尤为如此。其实每个数据都对数据空间具有影响力，而每 一个数据又受到数据空间其它数据的影响，数据作用遵循距离衰减的原则辐 射。数据场能把处于规则或散乱状态的数据的能量扩展到规则的笛卡儿网格 上，这既考虑了数据不确定性【l 引，又使数据挖掘易于操作。 1 数据场的概念和性质 数据通过数据辐射将其数据能量从样本空间辐射到整个数据空间，接受 数据能量并被数据辐射所覆盖的空间叫做数据场【1 9 】( 如图3 1 ) 。数据场可以 被看成一个充满数据能量的空间，数据通过自己的数据场对场中的其它数据 发射能量，从而产_ l f 作川。 蚓31 数据场 数据场的性质有独立性、叠加性、遍历性和衰减性。 独立性：每个数据在辐射数据能量的过程中都以自己为中心，j 曲外独立 辐射能昔，其特性不因其他数据的存在而改变。 叠加性：当几个数据同时存在于一个数据空问发牛数据辐射并彼此相遇 时，某观测点的数据能量等于各个数据独立辐射数据能量在该点所引起的数 据能量之和( 如图3 2 ) 。 ：117 ? ： t 、1jj ，一 ， ，、 、， ，一 l - - - t 。- - jo ， 一一、p ，、 。，、_ ，、 。，i 、一、 ，l 、 图3 , 2 两个对象叠加的数据场示意幽 遍历性：数据辐射将数据能量辐射到整个空问，实现全域覆盖，形成了 该空间数据场。在数据场中数域空间的所有区域都接受来自该空间数据辐 射的数据能量。 衰减性：数据辐射在空间中具有随距离增加而衰减的特性，衰减性建立 在数据场的遍历性基础之卜。在单一数据的数据空间中，数据样本附近得到 2 5 哈尔滨工程大学硕十学位论文 的数据能量强于远离样本的位置。当超出一定距离时，样本辐射的数据能量 能达到可以忽略的程度。 定义3 1 势函数对于1 1 维向量空间尺“中的一个向量x ，它在某点y 产 生的势定义如下： 巡兰! 丛8 z ( y ) = ( d e c r 2 ( 3 一1 ) 其中，i i d c x , y ) 2 | | 表示点y 到对象x 欧氏空间距离：仃为参量，称为辐 射因子；c o 为该数据点的权重，因为不同数据的影响力可能会不同，就代 表了这个数据对象对其它数据对象影响力的大小。但在通常情况下，我们可 以认为各个数据具有相同的权值，即各个数据不论其数值的大小，对外界有 着相同的影响力，那么数据的权重缈就相等，均可作为l 来处理，此时公式 3 1 就变为： 坚! 三：兰血 六( 少) = e 1 r 2 数据场空间中每个数据点都对周围的空间产生影响，所以数据集 d = 五，x 2 ，) 在数据场一点y 处产生的势函数满足叠加定理。 定义3 2 数据集的势函数对于d r ”，在向量空间尺”内某一点y 所产 生的势如下： i i d ( x ，j ，) 2 | | o ( y ) - y , 。五( y ) = 叩， l = i 仃取值要适中，取值太小的话会使所有的点都是彼此孤立，每个点都自 成一类；取值太大就会所有的数据都归为一类。其值的选取可采用文献 2 0 】 所给的基于熵的盯优选方法，该方法在第4 章的改进算法里会介绍。 2 等势线( 面) 与势心 在数据空间中，把其所形成数据场的势相等的每个点，用平滑的陷线连 接在一起，形成的等值线叫数据场的等势线。根据给定的势值，可以得到等 势面。 由等势线( 面) 围绕的中心，称为势心。数据空间内，一个数据形成的 势场中，其势心就是该数据本身所在的位置；多个数据叠加而形成的势场中， 哈尔滨工科人学硕士学侍论二： 其势心会靠近于权值较大的数据点，凼为权值较大的数据点在叠加过程中起 到的作用比权值较小的数据点起到的作用大。数据集的势心是该类数据对数 域空间中的某个概念的隶属中心，也即足数据在该概念特征聚粪的中心点。 如图33 ： 壤戮 糕 图3 3 等势线 3 3 基于数据场的密度聚类算法- - d f d b s c a n 基于31 节中提到的d b s c a n 算法存在的问题，本文将d b s c a n 算法 结合数据场的思想，提出了种基f 数据场的密度聚类算法d f 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 r i n go fa p p l i c a t i o n sw i t hn o i s eb a s e do nd a t a f i e l d ) 。该算法利用空间中数据能量辐射的作用，i = 但为基于d b s c a n 的密 度聚类提供了可行的参数计算方法，同时也为解决d b s c a n 算法存在的一些 问题找到了切入点。 3 3 】相关概念 定义3 ，3 ：空间中任意一点的e p s 邻域( e p s n e i 曲b o r h o o do f a p o i n t ) 是 以该点为圆心、以e p s 为半径的球形区域内包含的点的集合，记作 n c p s ( p ) = q dd i s t ( p ，g ) e p s ) ，其中，d 为数据集，d i s t ( p ，q ) 表示点p 与点 q 的距离。 定义3 - 4 ：空问中任意一点的e p s 密度是该点e p s 邻域内包含的点数。 定义3 - 5 ：给定e p s ，m i n p t s ，若点p 和点q 满足：p 访( q ) ，而且 n e p , ( q ) 肛m i n p t s ，则点p 从苣q 以e p s 直接密度可达。 对于两个点，以e p s 直接密度可达不是对称的。如图3 4 ，p 从q 以e p s 哈尔滨t 程大学硕十学位论文 直接密度可达，但q 却不从p 以e p s 直接密度可达。 图3 4 直接密度可达不恿图 定义3 - 6 ：给定e p s 、m i n p t s ，若存在点的一个链p l ，p 2 ，胁，其中 p l = p ，胁= g 且有p 到p + - 以e p s 直接密度可达，则点p 从点q 以e p s 密度 可达。 对于两个点，以e p s 密度可达也不是对称的。如图3 5 ，p 从q 以e p s 密 度可达，但q 却不从p 以e p s 密度可达。 图3 5 密度司达不葸图 定义3 - 7 ：如果点r 从p 以e p s l 密度可达、点q 从r 以e p s 2 密度可达， 且e p s l e p s 2 则 e p s 2 占= 二_ 一 e p s l 称为点r 的关于p 、q 密度可达的e p s 比。 定义3 8 ：给定阈值善( 0 - 1 0 0 o 1 0 02 0 0 3 0 04 0 0 a x i s t 硪e 图5 4d f d b s c a n 算法对d a t a b a s e 3 的聚类结果 在聚类同时，对每个簇进行了不同的标记，而标记的号码顺序就是簇的 生成顺序。可以看到，三个数据集用d f d b s c a n 算法的聚类结果与采用 d b s c a n 算法的聚类结果基本一致。虽然结果一致，但在算法的运行过程中 的处理过程却不相同：对数据集进行聚类的过程中，d b s c a n 算法的簇生成 顺序是随机的，因为d b s c a n 算法从数据集中随机选取一个数据对象判定该 数据对象是否为核心点，如果是核心点从该点开始进行簇扩展，如果该不是 核心点则重新选择数据对象进行判定；而对于d f d b s c a n 算法来说，是采 用了从数据场势最大的数据对象开始扩展，也就是说从数据集的中心也即簇 的中心开始向外扩展，可见d f d b s c a n 算法的簇产生顺序与d b s c a n 算法 簇的产生顺序是不一样的。在对数据进行跟踪的过程中可以看到， d f d b s c a n 算法中簇的产生顺序正如理论上