（计算机软件与理论专业论文）一种基于密度的动态参数单元聚类算法.pdf

山东大学硕士学位论文 摘要 本文讨论数据挖掘中聚类的相关概念、技术和算法，在对常见聚类算法进 行评价的基础上，针对密度聚类的参数选取问题，提出了一种动态参数解决方 案 目前己提出的聚类算法中，基本上都是基于“距离”的概念，不管是传统 的欧氏几何距离还是其它意义上的距离，如常见的k - - m e a n s 、k - - m e d o i d s 算法， 这类算法的缺点在于处理大数据集和高维数据集时不够有效，另一方面它能发 现的聚类个数常常依赖于用户参数的指定，而这对用户来说经常是很困难的。 本文针对聚类算法中参数选取的问题，对参数选取问题给出了一种解决办 法，提出了一种动态计算参数的算法本文讨论的算法与已有算法的根本不同 在于，它抛弃了距离的概念，采取一种新的思路，是一种基于密度的动态参数 的单元聚类算法，它的优点在于能够自动发现包含有趣知识的子空间，并将里 面存在的所有聚类挖掘出来；另一方面它能很好的处理高维数据和大数据集的 数据表格。算法将最后的结果用d n f 的形式表示出来 关键词：数据挖掘、聚类、密度、动态参数、d n f 山东大学硕士学位论文 b s t r a c t i nt h i sa r t i c l e ，c o n c e p t s ，t e c h n i q u e sa n da l g o r i t h m sa b o u tc l u s t e r i n g w i l l b ed i s c u s s e d w eg i v ead y n a m i cp a r a m e t e rs o l u t i o nf o rp a r a m e t e r s e l e c t i o np r o b l e mi nd e n s i t yb a s e dc l u s t e r i n ga l g o r i t h m a m o n gt h ev a r i o u sa l g o r i t h m sp u tf o r w a r d ，am a i nc l a s so f t h e ma r eb a s e d o n “d i s t a n c e ”，w h e t h e ri ti si nt h es e n s eo ft r a d i t i o n a le c u l i dd i s t a n c e o ro t h e r s “k - m e a n s ”a n d “k - m e d o i d s ”a r et w oo ft h i sk i n & h o w e v e r t h e s ea l g o r i t h m sa r ei n e f f i c i e n tw h e nd e a l i n gw i t hl a r g ed a t as e t sa n d d a t a s e t so fh ig hd i m e n s i o n f u r t h e rm o r e ，t h en u m b e ro fc l u s t e r st h e yc a nf i n d u s u a l l yd e p e n d so nu s e r s i n p u t b u tt h i st a s ki so f t e nav e r yt o u g ho n e f o rt h eu s e r i nt h i sa r t i c l ew eg i v eas o l u t i o nf o rt h i sp a r a m e t e rs e l e c t i o n p r o b l e m ，c a l l e dad y n a m i cp a r a m e t e rc o m p u t i n ga l g o r i t h m t h ea l g o r i t h mi n t h i sa r t i c l ed i f f e r sm u c hw i t ha b o v eo n e sa n di tt a k e sat o t a l l yd i f f e r e n t a p p r o a c h ，w h i c hw ec a l lag r i da n dd e n s i t yb a s e da l g o r i t h mi tc a n a u t o m a t i c a l l yf i n do u ts u b s p a c e sc o n t a i n i n gi n t e r e s t i n gp a t t e r n sw ew a n t a n dd i s c o v e ra l lc l u s t e r si nt h a ts u b s p a c e b e s i d e s ，i tp e r f o r m sw e l1w h e n d e a l i n gw i t hh i g hd i m e n s i o n a ld a t aa n dh a sg o o ds c a l a b i l i t yw h e nt h es i z e o ft h ed a t as e t si n c r e a s e s a sr e s u l t s ，c l u s t e r sf o u n da r ep r e s e n t e dt o u s e r si nd n fe x p r e s s i o n s k e y w o r d s ：d a t am i n i n g c l u s t e r ，d e n s i t y , d y n a m i cp a r a m e t e r ，d n f 原创性声町 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明弓i 用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 屋蓬叁日期：丝芝二生二f 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：座堕垄导师签名： 山东大学硕士学位论文 1 引言 1 。1 问题研究的背景 数据挖掘( d a t am i n i n g ) 就是从大量的不完全的有噪声的模糊的随机的数据中 提取隐含在其中的人们事先不知道的但又是潜在有用的信息和知识的过程人们把 原始数据看作是形成知识的源泉就像从矿石中采矿一样原始数据可以是结构化的 如关系数据库中的数据也可以是半结构化的如文本图形图像数据甚至是分布在网 络上的异构型数据发现知识的方法可以是数学的也可以是非数学的可以是演绎的 也可以是归纳的挖掘出的知识可以被用于信息管理查询优化决策支持过程控制等 还可以用于数据自身的维护因此数据挖掘是- - f - j 很广义的交叉学科涉及人工智能 技术统计技术与数据库技术等多种技术它汇聚了不同领域的研究者尤其是数据库 人工智能数理统计可视化并行计算等方面的学者和工程技术人员。 将物理或抽象对象的集合分组为由类似对象组成的多个簇( d u s t e r ) 的过程被称 为聚类。聚类所生成的簇是一组数据对象的集合，这些对象于同一簇中的彼此相 似，与其他簇中的对象相异。相异度根据描述对象的属性值来计算，距离是经常 被采用的度量形式。与分类不同的是，聚类的目的是寻找隐藏在数据中简单有效 的结构。而不只是为数据建立一个分类规则。 聚类分析是当今飞速发展的数据采掘和探查性数据分析中一个极为重要的技 术，它已被广泛地应用于工程、生物、心理、计算机视觉和遥感等领域仁1 7 1 聚 类算法是将一组分布未知的数据进行分类，尽可能使得同类中的数据具有相同 的性质，而不同类的数据其性质各异聚类的目的是寻找隐藏在数据中的结构。 由于聚类算法不对数据做任何统计假设，故在模式识别和人工智能等领域，聚类 算法常被称为“无导师学习”或“自组织算法”。 聚类分析是数据分析的一个重要工具。己经被广泛的应用于数据挖掘、统计 学、机器学习、生物学以及商务等众多领域。作为统计学的一个分支，基于k m e a n s ( k - 平均值) ，a m c d i a s ( 中心点) 和其他的一些方法的聚类分析工具己被加入到许多 统计分析软件包或系统中，如s - p l u s ，s p s s 以及s a s 。在机器学习领域，聚类是无 山东大学硕士学位论文 指导学习的一个例子区别于分类，聚类不依赖于预先定义的类或带类标号的训 练实例。在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群， 且用购买模式来刻画不同客户群的特征。在生物上，聚类能用于推导动植物分类， 对基因进行分类，获得对种群固有结构的认识。聚类在地球观测数据库中相似地 区的确定，汽车保险单持有者的分组，及根据房子的类型、价值和地理位置对一 个城市中房屋的分组上可以发挥作用。聚类也能用于对w e b 上文档进行分类，以发 现信息。近十几年来人们利用信息技术生产和搜集数据的能力大幅度提高。千万 个数据库被用于商业管理政府办公科学研究和工程开发等等要想使数据真正成为 一个公司的资源只有充分利用它为公司自身的业务决策和战略发展服务才行否则 大量的数据可能成为包袱甚至成为垃圾因此面对人们被数据淹没却饥饿于知识的 挑战数据挖掘和知识发现技术应运而生并得以蓬勃发展越来越显示出其强大的生 命力。 聚类是数据挖掘中一种重要的挖掘方法它从数据库中寻找数据间的相似性并 依此对数据进行分类使得不同类中的数据尽可能相异而同一类中的数据尽可能相 似即物以类聚从而优化大规模数据库的查询和发现数据中隐含的有用信息或知识 聚类分析就是用数学方法研究和处理给定对象的分类人以群分物以类聚聚类问题 是一个古老的问题是伴随着人类的产生和发展不断深化的一个问题人类要认识世 界就必须区别不同的事物并认识事物问的相似性。 1 2 数据挖掘的研究意义 最近的一、二十年，我们生产、获取各种数据的能力提高得很快。原因有很多， 例如：商品条形码的广泛使用。企业的信息化程度的提高，科学研究和政府部门 中电子化事务处理技术的运用，以及数据收集工具和技术的多元化( 从文本扫描 到卫星遥感) 等等。除此之外，互联网的发展更是为我们带来了海量的数据和信 息。但存储在各种数据媒介中的海量的数据，在缺乏强有力的工具的情况下，已 经远远的超出了人的理解和概括的能力为此，这种大量的原始数据和对功能强 大的数据分析工具的需求共存的局面，被有的人描述为“胖数据，瘦信息”( d a t a r i c hb u ti n f o r m a t i o np o o r ) 许多的 山东大学硕士学位论文 数据厍管理系统的出现t七十年代矾十年代早 期 层汝和网络数据库鬏统的出现， 曼系数据摩系统的出现； 数据摩建馍工具：买辩壤系摸垄苷； 歉据的组织、舅羁i 按术。b + 树，啥希表等， 数据霞查诲语害ts o l 等； 用户界面、表格和报告； 壹询处璎和纛询铣纯技术， 嘉务管理，箦发控制，安全管瑗和数据露豹曦复， 联机事务处理( 0 l t p ) ， 高级数据慝系统：( 八十 款据仓库和效据挖掘一尺 基于w 曲的数据蓐系筑i 年代中期至今) 十年代后期至今) 丸十年代至今 根据效裾最鹜分t 扩展关 我据仓慝及联机分褥处瑗 基于儿的数据露系 系型、对象受殛对象关系 ( o l a p ) l统i 蛩毒t 数据挖强、知识处理， w 出挖掘； 根据应翔豹颁域分，空 间、射阅、多婊俸、剽学 应用数据鼙及知谀摩； 图l2 1 ：数据库系统及相关技术的演化 数据库也就成了“数据坟墓”( d a t at o m b ) 换句话说，这些数据很少被再访问。 而与此同时，拥有这些数据库的决策者们，在做决策时不是基于数据库中蕴含的 大量信息，而是基于决策者的直觉。让我们在考察一下当前解决这个问题的方法 之一：专家系统技术。这种技术的一个很大的特点就是：用于辅助决策的系统信 息依赖于用户或某一领域的专家手工输入的知识，这个过程一方面是十分费时的， 另一方面它又是很难避免这样或那样的人为的偏见和错误的。而我们即将谈到的 数据挖掘技术可以在一定程度上克服上述缺点：从数据中产生知识的过程是自动 的，我们使用的数据是经过预处理( 包括：去掉坏的数据、消除数据之间的矛盾、 山东大学硕士学位论文 来自不同数据源的数据的集成、数据的转换、以及必要的数据精简和数据抽象) 的历史数据，这样我们就提高了所获知识的可靠性。 以上是从数据应用方面分时了一下数据挖掘技术的出现，下面再从信息技术 的演化的角度分析一下数据挖掘技术怎样成为这种演化的自然结果( 如图1 2 1 ) 。 由该图我们可以看到，信息技术的发展大致可以描述为如下的过程：初期的是简 单的数据收集和数据库的构造；后来发展到对数据的管理，这包括：数据存储、 检索以及数据库事务处理；再后来发展到对数据的分析和理解，这时候出现了数 据仓库技术和数据挖掘技术。早期的数据收集和数据库的建造为数据存储、检索、 和事务处理的技术的发展创造了必要条件，同样随着查询、事务处理等成熟技术 被频繁的应用在大量的数据库系统上，队员是数据的分析和理解也就当然的成为 了信息技术要发展的下一个目标。 数据挖掘( d a t am i n i n g ) ，简单的讲，就是要从大量的数据中整理出或者说 挖掘出有用的知识，这些知识是隐含的、事先未知的潜在有用信息。注意这个词： “有用”，对谁有用是未知的。计算机中程序的运行是基于符号处理的，符号本身是 没有意义的，至于从符号中所所看出的意义对不同的人是不一样的。这种“语义” 方面的东西对数据挖掘算法的影响在后面我们还会提到，我认为注意到这一点对 数据挖掘工具的有效使用至关重要。与数据挖掘这个词意思相近的、常用的术语 还有：知识挖掘( k n o w l e d g em i n i n g ) 、知是获取( k n o w l e d g ee x t r a c t i o n ) 、模式 分析( p a t t e r na n a l y s i s ) 、数据考古( d a t aa r c h a e o l o g y ) 等。还有一个经常与之 相混的术语：k d d ( k n o w l e d g ed i s c o v e r yf r o md a t a b a s e ) ，一般的看法是d m 只是 k d d 的一个步骤( 见图1 2 2 ) 。但是由于删这个词的广泛使用，我们也可不对他 俩进行严格的区分，而把他们看成同义词。 山东大学硕士学位论文 1 磊菌f 、 、 l 数据规范化：包括去掉异常数据和不相干数据p l 数据集成：将不同数据源中舶数据集成到单个 系统中 i 数据转化：如将数据转变成统一的表现形式以 i方便挖掘算法的实现 i 撮蠡黼脚岳一些智能的被用来发现目标数 i据库中的一些模式 t i 模式评价：识别上= 步得到自9 模式中真正有价 l值的樟式一 图1 2 2 ：数据挖掘d m 怎样被看作为k d d 的一个步骤 数据挖掘技术是在2 0 世纪8 0 年代被提出来的，并在9 0 年代取得了长足的发 展，是当今数据库系统及其应用领域中的一个热点话题。数据挖掘技术的研究和 开发要涉及到多个领域的知识，如：数据库技术、人工智能、神经网络、统计科 学、模式识别、知识库、知是获取技术、信息索引技术、高性能计算以及数据的 可视化等。从数据挖掘所要解决的问题来看，数据挖掘技术以及应用此技术所获 得知识和信息可以被广泛的应用于诸如商务管理、生产控制、市场分析、工程设 计和科学探索等众多领域，这些领域的管理决策层可以通过对历史数据的分析， 发现诸如市场供需规律、商品价格走势，家庭收入与消费特点、购买商品的习惯 等规律，以支持企业的生产、经营和销售决策。一个典型的数据挖掘系统的体系 酲解 d胁 、llliiil7fllilii， 山东大学硕士学位论文 结构如下( 图1 2 3 ) ： 数据规范和集 图1 2 3 ：一个典型的数据挖掘系统 其中，数据库、数据仓库或者是其他一些信息存储媒介为数据挖掘的工作对象； 服务器主要是响应数据挖掘引擎的请求，提取相应的数据；领域知识库主要用来 指导挖掘的过程，以及用来评价挖掘出来的候选模式；数据挖掘引擎是整个系统 的核心部分，可以由以下模块组成：分类模块、关联规则模块、聚类分析模块、 时序模块和异常分析模块等；模式评价模块主要是根据一定的度量标准来与数据 挖掘模块交互，以使得数据挖掘向着我们感兴趣的方向进行，往往越是高效的数 据挖掘系统这种交互影响的程度越高；图形用户界面主要是为方便用户与数据挖 掘系统的交互：由用户提出挖掘任务、指定重要的挖掘参数以及由当前返回的结 果指导进行更进一步的挖掘工作。从上述关于数据挖掘系统的讨论来看，它所有 功能的完全实现决非一件简单的事情，正因为如此，目前市场上出现的很多“数 山东大学硕士学位论文 ! i i 一i _ _ - - _ 一 据挖掘”系统并不是严格意义上的这类系统。一个不能处理大数据量的系统可能 划分为其它类型的系统更为适合，如它可能是一个机器学习系统、或者一个统计 分析工具、或一个实验性系统原型等。同样，如果一个系统仅能执行一些数据或 信息检索任务，包括执行一些求和运算、或推导型查询问答，也只能被称为信息 检索系统或者推导型数据库系统。 1 3 本文的主要工作 本文主要做了下述工作： ( 1 ) 研究了数据挖掘的概念和一般方法，对数据挖掘的概念、方法进行了深入 的研究，对数据挖掘及其应用进行了研究。 ( 2 ) 对数据中的聚类分析方法作出了详细的介绍，对其数据类型作出了描述和 比较，对主要的聚类算法做了叙述和对比。 ( 3 ) 在对聚类方法作出介绍的前提下，把模糊数学的理论应用到聚类挖掘中， 得到模糊聚类挖掘的定义；并提出了种经典的算法一模糊c 均值聚类算法，并 对其加以改进，得出结论：改进的模糊c 均值算法较以前的模糊c 均值方法有更好 的鲁棒性，不但可以在有野值存在的情况下得到较好的聚类结果，而且因为放松 的隶属度条件，使最终聚类结果对预先确定的聚类数目不十分敏感 首先，深入的分析及研究了密度聚类算法，对其运行机制及参数选取进行了 深入的分析，针对其参数选取存在的缺陷提出了一种改进参数选取的方法，并对 该改进方法进行了实例验证 其次，将常用的基于密度的聚类方法进行了改进，提出了一类新的算法：基于 密度的动态参数聚类算法该算法克服了原有算法的一些缺点，并保持了原有算 法的优点。如：能发现任意形状的簇( 类) ；能有效的过滤噪声点或孤立点：不依赖任 何初始值；也没有任何领域知识输入要求；能找到最优的聚类；聚类质量高等特点 本文内容主要由五部分组成，第一章简要的介绍了聚类分析的有关知识，聚 类算法研究及应用的特殊要求，及本文主要工作；第二章对常用的聚类算法进行了 简介与比较研究，对各类常用算法的优缺点有所揭示：第三章对d b s c a n 进行仔 细分析研究的基础上，针对其参数选取的缺陷，论述了一种新的方法，并用实例 山东大学硕士学位论文 进行了验证，证实该类算法是行之有效的；第四章对全文进行了概括总结。 山东大学硕士学位论文 2 聚类算法研究 2 1 聚类分析算法 聚类与数据挖掘中的分类不同，在分类模块中，对于目标数据库中存在那 些类这一信息我们是知道的，在那里我们要做的就是将每条记录分别属于哪一 类标记出来；与此相似但又不同的是，聚类是在预先不知道目标数据库到底有多 少类的情况下，希望将所有的纪录组成不同的类或者说“聚类”( c l u s t e r ) ，并且 使得在这种分类情况下，以某种度量为标准的相似性，在同一聚类之间最小化， 而在不同聚类之间最大化。事实上，聚类算法中一大类算法中的相似性都是基于 距离的，而且由于现实数据库中数据类型的多样性，关于如何度量两个台有非数 值型字段的记录之间的距离的讨论有很多，并提出了相应的算法。在很多应用中， 由聚类分析得到的每一个聚类中的成员都可以被统一看待。聚类分析的算法可以 分为以下几大类：分裂法、层次法、基于密度的方法、基于网格的方法、和基于 模型的方法等。 聚类的用途是很广泛的在商业上，聚类可以帮助市场分析人员从他们的 消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式 或者说习惯；在生物学中，它可以被用来辅助研究动、植物的分类，可以用来分 类具有相似功能的基因，还可以又来发现人群中的一些潜在的结构等等；聚类还 可以用来从地理数据库中识别出具有相似土地用途的区域；可以从保险公司的数 据库中发现汽车保险中具有较高索赔概率的群体；还可以从一个城市的房地产信 息数据库中，根据房型、房价及地理位置分成不同的类；还可以用来从万维网上 分类不同类型的文档等。同时，聚类分析作为数据挖掘中的一个模块，它既可以 作为一个单独的工具以发现数据库中数据分布的一些深入的信息，并且概括出每 一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；聚类分析 也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。 聚类分析是一个具有很强挑战性的领域，它的一些潜在的应用对分析算法提出 山东大学硕士学位论文 了特别的要求，下面列出一些典型的要求： 可伸缩性：这里的可伸缩性是指算法要能够处理大数据量的数据库对象，比如 处理上百万条纪录的数据库。这就要求算法的时间复杂度不能太高，最好当然 是多项式时间的算法。值得注意的是，当算法不能处理大数据量时，用抽样的 方法来弥补也不是一个好主意，因为这通常导致歪曲的结果。 处理不同字段类型的能力：也即算法不仅要能处理数值性的字段，还要有处理 其它类型字段的能力，例如：布尔型、枚举型、序数型、以及混合型等。 发现具有任意形状的聚类的能力：很多聚类分析算法采用基于欧几里德距离的 相似性度量方法，这一类算法发现的聚类通常是一些球状的，大小和密度相近 的类；但可以想见，现实数据库中的聚类可以是任意的形状，甚至是具有分形 维度的形状，故要求算法有发现任意形状的聚类的能力。 输入参数对领域知识的弱依赖性：很多聚类算法都要求用户输入一些参数，例 如需要发现的聚类数，结果的支持度、置信度等，聚类分析的结果通常都对这 些参数很敏感，但另一方面，对于高维数据，这些参数又是相当难以确定的。 这样就加重了用户使用这个工具的负担，使得分析的结果很难控制。一个好的 聚类算法应该针对这个问题，给出一个好的解决方法。 能够处理异常数据：现实数据库中常常包含有异常数据，或者数据不完整，缺 乏某些字段的值，甚至是包含错误数据的现象，有一些聚类算法可能会对这些 数据很敏感，从而导致错误的分析结果。 结果对输入记录顺序的无关性：有些分析算法对纪录的输入顺序是敏感的，也 即，对同一个数据集，将它以不同的顺序输入到分析算法，得到的结果会不同， 这是我们不希望的。 处理高维数据的能力：一个数据库或者数据仓库都有很多的字段或者说维，一 些分析算法再处理维数比较少的数据集时表现不错，例如两、三维的数据；人 的理解能力也可以对两、三维数据的聚类分析结果的质量作出较好的判别，但 对于高维数据就没有那么直观了所以对于高维数据的聚类分析是很具有挑战 性的，特别是考虑到在高维空间中，数据的分布是极其稀疏的，而且形状也可 能是极其不规则的。 增加限制条件后的聚类分析能力：现实的应用中总会出现各种其它限制，我们 山东大学硕士学位论文 希望聚类算法可以在考虑这些限制的情况下，仍就有较好的表现。 结果的可解释性和可用性：聚类的结果最终都是要面向用户的，所以结果应该 是容易解释和理解的，并且是可应用的。这就要求聚类算法必须与一定的语义 环境，语义解释相关联。领域知识是如何影响聚类分析算法的设计是很重要的 个研究方面 下面是常见的几大类聚类分析算法的基本思想： 1 分裂法( p a r t i t i o n i n gm e t h o d s ) ：给定一个有n 个元组或者纪录的数据集，分 裂法将构造k 个分组，每一个分组就代表一个聚类，k n 。而且这k 个分组满 足下列条件：( 1 ) 每一个分组至少包含一个数据纪录；( 2 ) 每一个数据纪录 属于且仅属于一个分组( 注意：这个要求在某些模糊聚类算法中可以放宽) ； 对于给定的k ，算法首先给出一个初始的分组方法，以后通过反复迭代的方法 改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就 是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。使用这个基 本思想的算法有：k - m e a n s 算法、k - m e d o i d s 算法、c l a r a n s 算法； 2 层次法( h i e r a r c h i c a lm e t h o d s ) ：这种方法对给定的数据集进行层次似的分 解，直到某种条件满足为止具体又可分为“自底向上”和“自顶向下”两种 方案。例如在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的 组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记 录组成一个分组或者某个条件满足为止。代表算法有：b i r c h 算法、c u r e 算法、 c h a m e l e o n 算法等； 3 基于密度的方法( d e n s i t y b a s e dm e t h o d s ) ：基于密度的方法与其它方法的一 个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克 服基于距离的算法只能发现“类圆形”的聚类的缺点。这个方法的知道思想就 是，只要一个区域中的点的密度大过某个阀值，就把它加到与之相近的聚类中 去。代表算法有：d b s c a n 算法、o p t i c s 算法、d e n c l u e 算法等； 4 基于网格的方法( g r i d b a s e dm e t h o d s ) ：这种方法首先将数据空间划分成为有 限数目单元( c e l l ) 的网格结构，所有的处理都是以单个的单元为对象的。这 山东大学硕士学位论文 么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的 个数无关的，它只与把数据空间分为多少个单元有关。代表算法有：s t i n g 算 法、c l i q u e 算法、w a v e c l u s t e r 算法； 5 基于模型的方法( m o d e l b a s e dm e t h o d s ) ：基于模型的方法给每一个聚类假定 一个模型，然后去寻找能很好的满足这个模型的数据集。这样个模型可能是 数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数 据集是由一系列的概率分布所决定的。通常有两种尝试方向：统计的方案和神 经网络的方案。 2 2 算法性能的比较框架 2 2 1 算法的比较标准 把空间数据对象集合分割成一组子集或簇是数据挖掘的基本操作，可以用于 分类( 无监督) 、聚合和分割、剖析、数据缩减、预测等。其准则是使得属于同一簇 内的数据对象之间具有高度的相似性，不同簇之间性质各异。为了找到一个效率 高且通用性强的聚类方法，长期以来，人们从不同角度提出了近百种聚类算法。 典型的有k - m e a m 算法，k - m e d i a s 算法、c l a r a n 算法、b i r c h 算法、d b s c a n 算法和c u r e 算法等。但是各个算法存在本身的缺陷和优点，又有各自的适用领 域。为了更好的使用这些算法，本章综合的提出了评价聚类算法好坏的5 个标准， 基于这5 个标准，对数据挖掘中近几年提出的常用聚类方法作了比较分析，以利 于人们更容易，更快速的找到一种适用于特定问题及用户的聚类算法。 现存的聚类算法中，尽管已有算法被广泛应用于众多的邻域，但它们普遍还 存在各自的缺陷，和各自的适用领域按照聚类算法的出发点不同，对聚类算法 本身有很多种分类。常见分类如下：划分方法、分层方法、基于密度方法和基于网 格方法。这不是严格的划分，因为有些算法集成了多种聚类算法的思想。各个聚 类算法的出发点不同，导致了各个算法的优缺点不同，适用范围也有很大的不同。 为了对常用聚类算法的优缺点，适用范围有一定程度的了解，本章对常用的聚类 算法进行了比较研究，本章中对常用聚类算法的比较研究是基于以下5 个标准： 2 山东大学硕士学位论文 i ) 是否适用于大数据量，算法的效率要满足大数据集的大数据量、高复杂性、 高增量的要求： 2 1 是否能应付不同的数据类型，至少能处理数值属性和符号属性； 3 ) 是否能发现不同类型不同形状的聚类； 4 ) 是否能应付噪声数据或异常数据； 5 1 是否对数据的输入顺序不敏感。 2 2 2 数据变换与分类尺度 一、数据变换 五l2 x 2 1 砀 ll l 矗2 l 而t l 屯t l l l 设有n 个样品，每个样品测量了k 项因素( 变量) ，得出的数据矩阵如下： 它有n 行k 列，n 行表示n 个样品，k 列表示k 个因素，丑，表示第i 行第j 列的矩阵元素，代表了第i 个样品的第j 个因素( 变量) 的测量值。 对于任何研究对象，要进行分类，首先应确定分类标准或尺度，这就要求所要 分类的对象必须有相同的量纲，否则无法在它们之间进行比较。因此，在聚类分 析以前，应注意被分类对象的量纲和量级是否一样。如果不一样，则要作数据的 正规化变换和标准化变换。 l 、正规化变换就是对任何一个测量因素，把力个样品的值化为 0 ，1 之间的 数据。为此作如下变换： z j r = ( x i 广毋) 4 ( i = 1 ，2 ，亿卢1 ，2 ，( 2 2 2 2 ) 其中 = m a x x 口一m i n x , j ( 因素，的极差) ， = r a i n ，( 2 2 2 3 ) i g g ni g 甜 i g 如 这样得到的数据称为正规化矩阵数据，蜀，与测量时所取的度量单位无关。 一i 山东大学硕士学位论文 z = 毛i z t 2 z 2 i ：乞2 ll 乙1 乙2 l 钆 l 锄 l l l ( 2 2 2 - 4 ) 2 、数据标准化是指把每一因素( 变量) 化为均值为0 ，方差为1 的标准化变 量。具体对 z 口= ( 一x ) 仃 ( j = 1 , 2 ，l ， ；j = 1 ，2 ，l ，k ) ( 2 2 2 5 ) 式中 一x j 丢静旷佶喜c 和d 2 ( 6 1 ) 式，就是每一列的均值为0 ，方差为1 。为此作如下变换 这样得到数据阵同( 6 3 ) 一样，只是元素值不一样而已，同样与测量时所采用的 度量单位无关。 ( 二) 、分类标准 对于( 6 一1 ) 式所反映的原始观测数据矩阵的元素，可以考察三种情况：( 1 ) 对应元素接近程度；( 2 ) 对应元素成比例程度；( 3 ) 对应元素相互消长程度。我 们用以下几种相似统计量来衡量样品之间或变量( 指标) 之间相似程度。 1 、距离 吒国) = 一) 9 】， k = l 当g = 1 时，称为绝对距离 吒( 1 ) = i 一 当g = 2 时，称为欧氏距离 吃( 2 ) = 【瓯一工业) 2 】- ( 2 2 2 - s ) k = l 当9 2 0 0 时t 称为切比雪夫距离 吒( o 。) 2 譬嚣l x 口- - b i ( 2 2 2 9 ) 明考斯基距离： ( 1 ) 、如果把7 个样品的七个指标( 变量) 看成k 维空间的个样品点。则样 品间的亲疏程度可用它们相互间的欧氏距离来衡量。第一个样品与第j 个样品间 的距离为 l t 吒= e “。一_ 。) 2 】_ o ，j = l ，2 ，l ，疗) ( 2 2 2 1 0 ) ol - i 山东大学硕士学位论文 有时，为使所求距离在某一确定范围变化，常采用以下公式来计算第f 个点与第j 个点之间的距离。优的值越小，表示二样品点相似程度越大。求出所有两两点之 间的距离后，可得到距离系数矩阵庐 d ， 。，它是一个n 阶对称矩阵，即d j - d i ， d 。= 0 ( 2 ) 、如果对指标( 变量) 豹聚类，则把7 个样品的k 个指标看成是7 维空间 f 月i 吃= e 瓯一x 0 ) 2 】 ( f ，j = t ，2 ，l ，七)( 2 2 2 - 1 1 ) k - i 点，仿此，得到第j 个变量与第j 个变量间的距离为 求出两两变量之间的距离，；得到矩阵伊 d 。j 。 2 、相似系数 给定原始数据矩阵( 铲1 ) ，把每个样品看成k 维空间中的个向量，此时第i 个样品向量 x n ，x 。，x 。】与第j 个向量 x 。x j ：，x j 。 之间的夹角余弦c o s 口 。称为此二样品的相似系数，即 。 圭b c o s 岛= 一l 一 m 铮c o r e r , ( o ) ( 2 ) d i r r e a e h 。s , ( o ，g ) 营c o r e s , ( o ) q 彬( d ) c c o r e s ( d ) d i s t q r s ( d ) ，r s ( g ) ) 占 c o r e s ( d ) f ( ( 口) 一( g 扩- 8 y q e s 仃c j s x ”c o r a d ) f 医再历而 vd e t 营c o r e r , ( o ) d i s t q r r ( d ) ，研( g ) ) s d i r r e a c h r 。( d ，g ) ( 3 ) r e a e l t 乙( d g ) 铮劲l ，磊6 d 口：a - - o a p = g v f l ，疗一1 ：d i r r e a c t , p j “) ( t k s x 2 ) ：，劫i ，p 。d b ：p l = o a p 。= q v i ( 1 ，n - i ：d i r r e a c h r 。( 只，p f + i ) 山东大学硕士学位论文 r e a c h r 月( d ，g ) ( 4 ) c b n 月p “0 i ( c ) 3 x e - d b ：r e a c h s 。 ，o ) r e a c h s ( x ，g ) 苫”孤d b ：r e a c h r ，( r e五。) r e 口c 乙( x ，g ) = ：k x d 1 口c 矗7r x 口、 铮c o n n e c t r , 。( o ，g ) ( 5 ) c o n s e t s , 。( c ) v o ，口c ：c o n n e c t s , 。( d ，g ) ( r c s x 4 ) v o ，q c ：c o n n e c t r j , ( o ，g ) c o n s e t r 。 3 2 算法中的数据预处理 1 样本数据矩阵 可以用样本数据矩阵代表数据库中的数据，在样本数据矩阵中，每一行表示数据 库中的一条记录。行中的每一列表示一条记录的某个属性。样本数据矩阵如下所 示： 五1 毛2x i $ 而1 如砀 弓ix 3 , b l 矗i 矗2 毛3 工茹 2