（计算机软件与理论专业论文）基于数据分区的密度聚类算法应用研究.pdf

大连理工大学硕士学位论文 摘要 聚类分析是数据挖掘的核心技术，是指将物理或抽象对象的集合分组成为由类似的 对象组成的多个类的过程。数据对象根据最大类内的相似性，最小类间的相似性原则进 行聚类。聚类是数据挖掘的前期预处理过程。 密度的聚类算法具有快速、有效处理噪音点和发现任意形状的簇的优点，但是在数 据集的密度分布并不均匀的情况下，难以得到较高质量的聚类结果。本文详细研究了基 于密度的聚类算法d b s c a n 以及基于数据分区的密度聚类算法p d b s c a n 。其中 p d b s c a n 算法运用数据分区预处理时，由于算法中对数据的分区不够准确，常常影响 了聚类效果。本文给出了一种改进的数据分区算法，实现了对密度分布不均匀的数据空 间进行更精确的分区。试验证明，改迸后的算法的聚类效果更佳。 大连市国民经济潜力动员分析系统，是根据国民经济动员潜力调查总体实施方案， 结合大连市国民经济动员潜力调查的特点，建成可靠、先进的国民经济动员信息化平台， 为高效、高质量的完成国家经济动员办公室组织实施的全国国民经济动员工作提供了保 障。 在系统中的决策支持平台中，针对怎样选择最合适的地理位置建立战时伤病人员中 心的问题，将改进后的算法应用于系统中，可以实现自动选择建立战时伤病人员中心的 最佳位置，从而完善了地理信息决策支持的功能。 关键词：数据挖掘；聚类算法；密度聚类；数据分区 大连理工大学硕士学位论文 r e s e a r c ha n da p p l i c a t i o no f d e n s i t yc l u s t e r i n ga l g o r i t h mb a s e do n d a t ap a r t i t i o n a b s t r a c t c l u s t e r i n ga n a l y s i si st h ec o r et e c h n o l o g yo f d a t am i n i n g 、) l ，i 也t h ep r o c e s so f d i v i d i n gt h e p h y s i c a lo ra b s t r a c tc o l l e c t i o n si n t om a n yc l u s t e r s d a t ao b j e c t sa r ec l u s t e r e dw i t ht h e p r i n c i p l eo fl a r g e s ts i m i l a r i t yi nt h es a m ec l u s t e ra n dl e a s ts i m i l a r i t yb e t w e e nd i f f e r e n t c l u s t e r s c l u s t e r i n gi s 也ep r e t r e a t m e n to ft h ed a t am i n i n g d e n s i t y b a s e dc l u s t e r i n gi sq u a l i f i e dw i t hf a s t , e f f i c i e n ti nh a n d l i n gt h ep r o b l e mo fn o i s e p o i n t sa n df i n d i n ga n ys h a p e b u ti nt h ed a t as p a c e sw h i c hd e n s i t yi sr n e v e nd i s t r i b u t e d ，i ti s h a r dt og e tt h eg o o dr e s u l t s t i l i sp a p e rr e s e a r c h e dt h ed e n s i t y b a s e dc l u s t e r i n ga l g o r i t h m d b s c a na n dp a r t i t i o nd b s c a ni ne v e r yd e t a i l p d b s c a nu s e dt h em i n do fd a t ap a r t i t i o n a n dc o u l dg e tb e t t e rq u a l i t yo fc l u s t e ri nr e s u l to nt h ed a t as p a c ew h o s ed e n s i t yi su n e v e l lb u t b e c a u s et h ed e f i n i t i o no fh ed a t ap a r t i t i o no fp d bs c a ni sn o tp r e c i s e i nt h i sp a p e l ，w eu s e d t h ed a t ap a r t i t i o na l g o r i t h mr e d e f i n et h ed a t ap a r t i t i o n , p r e c i s e l yp a r t i t i o n i n gt h ed e n s i t y u n e v e nd a t a e x p e r i m e n tp r o v e dt h a tt h er e s u l to ft h ea l g o d t h mi sb e t t e r d a l i a nn a t i o n a le c o n o m ym o b i l i z a t i o np o t e n t i a la n a l y s i ss y s t e mi sb a s e do nt h en a t i o n a l e c o n o m yi n v e s t i g a t i o no v e r a l li m p l e m e n t a t i o no ft h ep r o g r a m m e a n w h i l e ，j o i n i n gt h e c h a r a c t e r i s t i c so fd a l i a nn a t i o n a le c o n o m ym o b i l i z a t i o np o t e n t i a l ，b u i l d i n gt h ea d v a n c e da n d p r a c t i c a ln a t i o n a le c o n o m ym o b i l i z a t i o np o t e n t i a ld a t a b a s e ，f o rt h ep u r p o s eo fp r o v i d i n gt h e s e c u r i t yo ff i n i s h i n gt h e o bw h i c hi so r g a n i z e da n di m p l e m e n t e dn a t i o n a le c o n o m yo f f i c e e f f i c i e n t l ya n dr e l i a b l y ，b e c a u s et h a td a t am i n i n ga n a l y s i sp l a t f o r mn e e d sc l a s s i f y i n gs o m e e c o n o m i ci n s t i t u t i o n sb ys o m ei n d i c a t o r s s oi tn e e d st h ec l u s t e r i n ga l g o r i t h mt of i n i s ht h i s j o b i nt h i sp a p e r , i no r d e rt os o l v i n gt h ef u n c t i o no fe n s u r i n gt h em o s ta p p r o p r i a t ep o s i t i o no f c e n t e ro fw a r t i m ec a s u a l t i e s ，w eu s et h ei m p r o v e da l g o r i t h mi n t ot h es y s t e ma n db e t t e rt h e r e s u l to ft h ec l u s t e r i n g a n dw i t ht h i sa l g o r i t h mb u i l dt h ec e n t e ro fw a r t i m ec a s u a l t i e sa ta t t h em o s ta p p r o p r i a t ep o s i t i o n i nt h i ss i t u a t i o n , w ep e r f e c t e dt h ef u n c t i o no ft h ed a t ag e o g r a p h y i n f o r m a t i o nd e c i s i o nm a k i n gs u p p o r t 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 ；d e n s i t y b a s e dc l u s t e r i n g ；d a t ap a r t i t i o n i i i - - 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：差量麴整金壁亟壅盘望三囊魁鸯近 作者签名：型二塑日期：圣竺坚! 葫些 导师签名： 大连理工大学硕士学位论文 1绪论 1 1 选题背景 本文的选题来自于一个项目大连市国民经济潜力动员分析系统。这个项目是与 大连市发改委合作的项目。项目是按照国家经济动员办公室下发的关于开展国民经济动 员工作的相关指示，为了完成国民经济动员相关工作，建立的一个功能强大的信息化平 台，以更加有效的完成国民经济动员的相关工作。国民经济动员是指在战争或者遭受强 大自然灾害条件下，调整组织国民经济的供求关系，使国家经济有效运行，人民生活得 到保证l l j 。 本文所讨论的就是在国民经济动员潜力数据库平台上通过聚类算法实现的地理信 息决策支持平台的实现。 1 2 国内外研究现状 经典的聚类分析算法主要有：划分方法、层次方法、基于密度的方法、基于网格的 方法、基于模型的方法。 这些经典的聚类算法在各种领域已经得到了广泛的应用。 近几年，随着物理学和生物工程学等领域的不断发展，也随之产生了一些新的聚类 方法【2 】，这些方法中虽然有些还不够完善与成熟，但是也处在不断发展与改进的过程中。 下面对这些算法做些简单的介绍： ( 1 ) 基于蚁群聚类方法：意大利学者d o r i g o 等人提出了蚁群算法，该算法不依赖于 具体问题的数字描述，具有全局优化能力。后来，l a b r o c h e 等人提出基于蚂蚁化学识别 系统的聚类方法。总的说来，基于蚁群算法的聚类方法从原理上可以分为四种：运用蚂 蚁觅食的原理，利用信息素来实现聚类：利用蚂蚁自我聚集行为来聚类：基于蚂蚁堆 的形成原理实现数据聚类：运用蚁巢分类模型，利用蚂蚁化学识别系统进行聚类。 ( 2 ) 免疫进化算法：借鉴生命科学中的免疫概念和理论在保留原算法优良特性的前 提下，力图有选择、有目的地利用待求问题中的一些特征或知识来抑制其优化过程中出 现的退化象。 ( 3 ) 量子聚类：聚类是一种无监督的学习方法。在现有的聚类算法中，聚类数目一 般需要事先指定，如k 0 h e n o n 自组织算法、k 1 l l c a n s 算法和k 中心算法。在很多情况下类 别数是不可知的，而且绝大多数聚类算法的结果一般都要依赖于初值，即使类别数目 保持不变，聚类的结果也可能相差很大。受到物理学中量子机理和特性的启发，可以用 量子理论解决此类问题。一个很好的例子就是基于相关点的p o r t 自旋和统计机理提出的 基于数据分区的密度聚类算法的研究 量子聚类模型。它把聚类问题看作一个物理系统。许多算例表明：对于传统聚类算法无 能为力的几种聚类问题，该算法都得到了比较满意的结果。 ( 4 ) 谱聚类法：该类方法建立在谱图理论基础之上，并利用数据的相似矩阵的特征 向量进行聚类，因而统称为谱聚类方法。 ( 5 ) 基于粒度的聚类方法：从表面上看，聚类和分类有很大的差异，聚类是无导师 的学习，而分类是有导师的学习。更进一步地说，聚类的目的是发现样本点之间最本质 的抱团性质的一种客观反映：分类在这一点上却不大相同。分类需要一个训练样本集， 由领域专家指明哪些样本属于一类，哪些样本数据属于另一类，但是分类的这种先验 知识却常常是纯粹主观的。如果从信息粒度的角度来看的话，就会发现聚类和分类有很 大的相通之处：聚类操作实际上是在一个统一粒度下进行计算的：分类操作是在不同 粒度下进行计算的。所以说在粒度原理下，聚类和分类是相通的，很多分类的方法也可 以用在聚类方法中。 1 3 本文所做的工作 ( 1 ) 密度聚类d b s c a n 算法在全局数据空间上使用统一的邻域半径进行聚类，因此 在密度分布不均匀的数据空间上，这种方法聚类效果不理想并不好。p d b s c a n 算法使 用了数据分区的方法对其进行修改。本文针对p d b s c a n 算法对于数据分区预处理不准 确的问题，使用了改进的数据分区算法对数据分区，通过实验证实了这种方法具有更好 的预处理效果，并且提高了聚类的效果。 ( 2 ) 最后，针对需要提供确定战时伤病人员中心地理位置的决策支持功能，将改进 后的算法应用于大连市国民经济动员潜力分析系统上，提供了相应的决策支持。 1 4 本文的组织结构 本文的主要研究工作包括以下几个方面： 第一章绪论。介绍了本文的选题背景，研究现状，本文所做的工作以及本文的组 织结构。 第二章对数据挖掘与聚类算法进行了详细的阐述，并对各种聚类算法的过程以及 评价聚类算法的各项指标进行了全面的介绍。 第三章对基于数据分区的密度聚类算法进行了详细的研究与分析。分别指出了 d b s c a n 与p d b s c a n 算法的缺陷并针对p d b s c a n 算法的不完善之处，使用了改进 的数据分区算法进行改进。 第四章通过实验验证了算法，实验结果证明改进后的算法在密度分布不均空间上 的聚类效果更好。 一2 一 大连理工大学硕i - q = 位论文 第五章使用改进后的基于数据分区的密度聚类算法，同时综合运用多种技术，完 善了大连市国民经济动员潜力分析系统中的地理信息决策支持平台。 基于数据分区的密度聚类算法的研究 2 数据挖掘与聚类算法 2 1 数据挖掘技术概述 2 1 1 数据挖掘技术 进入2 l 世纪，人类已经生活在一个信息化的时代中，计算机、通信和网络技术正 在以惊人的速度影响着整个人类社会。然而海量信息在给人们带来方便的同时，也带来 了许多问题，使我们惊讶于信息爆炸的同时又不得不面对知识贫乏的苦恼，例如：信息 过量难以消化、信息真伪难以辨别、信息安全难以保证、信息表示形式相异难以统一处 理。人们开始考虑不被海量信息淹没，而是从中及时发现有用的知识、提高信息利用率， 面对这一挑战，数据挖掘( d a t am i n i n g ) 技术应运而生。 数据挖掘，又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) ，就是从 大量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程，简单 的说，数据挖掘就是从大量数据中提取或“挖掘”知识p j 。 人们很早就认识到应从海量的数据中归纳发现知识。7 0 年代就提出了知识发现，在 1 9 8 9 年有人提出了机器学习的概念，近年来研究者使用了更形象的概念，即“数据挖掘”。 数据挖掘是一个众多学科诸如人工智能、机器学习、模式识别、统计学、数据库和知识 库、数据可视化等相互交叉、融合所形成的一个新兴的且具有广阔前景的领域。 数据挖掘的诞生是人们对数据库技术进行长期研究和开发的结果，而数据挖掘技术 发展的同时又反过来促使数据库技术进入了一个更高级的阶段。传统的数据环境基本上 是数据操作型的，传统的信息系统只负责数据的增加、删除及修改操作，而在数据库的 基础上可实现的工作就是联机事务处理( o l t p ) 。现在由于数据积累的不断增多，人们需 要分析型的数据环境，于是就出现了由数据库导出的数据仓库，以此为基础则可以实现 联机分析处理( o l a p ) 。随着海量数据搜集的可能、计算机处理技术的增强和先进数据挖 掘算法的提出，数据挖掘技术不仅能对数据进行查询和遍历，而且能够找出过去数据之 间潜在有价值的联系，并以一定的形式表现出来，从而极大的满足了人们对知识的迫切 需求，也为企业、商家的决策者提供了有效的决策支持。 2 1 2 数据挖掘过程 许多人把数据挖掘视为另一个常用的术语“数据库中知识发现”或k d d 的同义词。 而另一些人只是把数据挖掘视为数据库中知识发现过程的一个基本步骤。数据挖掘也可 以被称为知识发现，而数据挖掘最终目的也是为了寻找“知识 。过程如图2 1 所示。 一4 一 大连理工大学硕士学位论文 图2 1 数据挖掘的实施过程 f i g 2 1 t h ei m p l e m e n t a t i o no fd a t am i n i n gp r o c e s s 由以下步骤组成： ( 1 ) 数据清理( 消除噪音或不一致数据) 数据集中不可避免地存在着不完整、不一致、不精确和重复的数据，这些数据统称 为脏数据。数据抽取之后须利用领域专门知识对脏数据进行清洗。通常采用基于规则的 方法、神经网络方法和模糊匹配技术分析多数据源数据之间的联系，然后再对它们实施 相应的处理。 ( 2 ) 数据集成( 多种数据源可以组合在一起) 建立目标数据集。根据数据挖掘目标，从原始数据中选择相关数据集，并将不同数 据源中的数据集成起来，以确定数据挖掘的操作对象，需要解决平台、操作系统和数据 类型不同产生的数据物理格式差异。信息产业界的一个流行趋势是将数据清理和数据集 成作为预处理步骤执行，结果数据存放在数据仓库中。 ( 3 ) 数据选择( 从数据库中提取与分析任务相关的数据) 从数据源中检索与分析任务相关的数据。有时，数据变换和数据统一在数据选择过 程之前进行，特别是在数据仓库情况下。 ( 4 ) 数据变换( 数据变换或统一成适合挖掘的形式。如：通过汇总或聚集操作) 根据分析任务目标，选用关键特征表示数据，并将数据通过汇总或聚集等操作转换 为适于数据挖掘处理的形式。 ( 5 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) 使用智能方法提取数据模式。这些方法包括概括、分类、回归和聚类等。 ( 6 ) 模式评估( 根据某种兴趣度度量，识别提供知识的真正有趣的模式) _ 采用有关方法对数据挖掘发现的模式进行评价，根据某种兴趣度度量，识别的真正 基于数据分区的密度聚类算法的研究 兴趣的模式。 ( 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 使用可视化和知识表示技术，向用户提供挖掘的知识，帮助用户理解发现的模式。 2 。2 数据挖掘的对象 一般来说，数据挖掘可以在任何类型的信息存储上进行。这包括关系数据库、数据 仓库、事务数据库、先进的数据库、展平的文件和万维网。先进的数据库包括面向对象 和对象一关系数据库；面向特殊应用的数据库，如空间数据库、时间序列数据库、文本 数据库和多媒体数据库。具体的挖掘技术可能因存储系统而异。下面简单介绍几种数据 挖掘的对象。 2 2 1 关系数据库 数据库系统，是建立在集合代数基础上，应用数学方法来处理数据库中的数据。关 系数据库是目前各类数据库中最重要、最流行的数据库。 现实世界中的各种实体以及实体之间的各种联系均用关系模型来表示。关系数据库 是建立在关系模型基础上的数据库。标准数据查询语言s q l 就是一种基于关系数据库的 语言，这种语言执行对关系数据库中数据的检索和操作。关系数据库是表的集合，每个 表都赋予一个唯一的名字。每个表包含一组属性( 列或字段) ，并通常存放大量元组( 记 录或行) 1 4 j 。 2 2 2 数据仓库 数据仓库是一个面向主题、集成、时变、非易失的数据集合，是支持管理部门的决 策过程。面向主题性表示数据仓库中数据组织的基本原则，数据仓库中的所有数据都是 围绕着某一主题组织、展开的。通常是结合多个异种数据源构成的，异种数据源可能包 括关系数据库、面向对象数据库、文本数据库、w e b 数据库、一般文件掣5 1 。数据存储 从历史的角度提供信息，数据仓库中包含时间元素，它所提供的信息总是与时间相关联 的。数掘仓库中存储的是一个时间段的数据，而不仅仅是某一个时刻的数据。 数据仓库总是与操作环境下的实时应用数据物理地分离存放，因此不需要事务处 理、恢复和并发控制机制。数据仓库里的数据通常只需要2 种操作：初始化载入和数据 访问。因此其数据相对稳定，极少或根本不更新。有三种类型的数据仓库的应用，分别 是信息处理、分析处理和数据挖掘。 综上所述，数据仓库是一种语义上一致的数据存储，它充当决策支持数据模型的物 理实现，并存放企业战略决策所需信息。数据仓库也常常被视为一种体系结构，通过将 一6 一 大连理工大学硕士学位论文 异种数据源中的数据集成在一起而构成，支持结构化和专门的查询、分析报告和决策制 c j 匕o 2 2 3 对象一关系数据库 对象关系数据库基于对象关系数据模型构造。该模型通过提供处理复杂对象的丰 富数据类型和对象定位，扩充关系模型。此外，它还包含关系查询语言的特殊构造，以 便管理增加的数据类型。通过增加处理复杂数据类型、类层次结构和如上所述的对象继 承，对象关系模型扩充了基本关系模型。对象关系数据库在工业界正日趋流行。 2 2 4 其他类型的挖掘对象 空间数据库，空间数据库包含涉及空间的信息。这种数据库包括地理( 地图) 数据 库、v l s i 芯片设计数据库、医疗和卫星图像数据库。多媒体数据库存放图像、音频和 视频数据。它们用于基于图像内容的提取、声音传递、录像点播、万维网和识别口语命 令的基于语音的用户界面等方面。多媒体数据库必须支持大对象，因为图像视频这样的 数据对象可能需要数十亿字节的存储。 2 3 数据挖掘方法分类 数据挖掘需要为用户提供有用的知识，但是通常用户不知道什么模式是有用的，因 此数据挖掘可以利用各种知识发现算法帮助用户从数据库数据中发现有关的知识，以及 能够挖掘多种类型的模式，以适应不同用户的需要。数据挖掘的模式类型介绍如下： ( 1 ) 特征( c h a r a c t e r i z a t i o n ) ：从与学习任务相关的一组数据中提取出关于这些数据的 特征式，这些特征式表达了该数据集的总体特征。 但) 区分( d i s c r i m i n a t i o n ) ：通过对学习数据和对比数据的处理，提取出关于学习数 据的主要特征，这些特征可以将学习数据与对比数据分开来。例如：通过对某种疾病与 其他疾病的症状的比较，可以提取出该疾病相对于其他疾病的区分规则，利用这些规则 就可以区分出这种疾病。 ( 3 ) 分类( c l a s s i f i c a t i o n ) ：根据数据的不同特征，将其划归为不同的类，这些类是事 先利用训练数据建立起来的。例如：利用当前的病例数据可以建立各种疾病的分类规则。 对于新的病人，根据其症状及分类规则，可以知道疾病的种类。 ( 4 ) 关联规则( a s s o c i a t i o nr u l e ) 是发现数据对象间的相互依赖关系，一个关联规 则的形式为：关联规则是形如x - y ，即“a 1 八八a m = b 1 八八b n 的规则；其 中，a i ( i l ，m ) ，b j o l ，n ) 是属性值对。关联规则解释为“满足x 中条件的数 据库元组多半也满足y 中条件。例如：在对疾病状的研究过程中，人们也许会发现，某 基于数据分区的密度聚类算法的研究 些症状的出现一定会伴随其他一些症状的出现，通过对这种现象的深入研究，也许会找 到攻克疾病的方法。 ( 5 ) 聚类( c l u s t e r i n g ) ：根据所处理的数据的一些属性，对这批数据进行分类，这种 分类是基于当前所处理的数据。经过分类以后的数据，在各类之间其相似程度很小，而 在某一类内部，其数据的相似度则很大。分类结束后，每类中的数据由唯一的标志进行 标识，类中数据的共同特征也被提取出来用于对该类的特征描述。例如：可以通过对一 组新型疾病的聚类，形成每类疾病的特征描述，这样可以对这些疾病进行识别。 ( 6 ) 预测( p r e d i c t i o n ) ：预测性挖掘任务是在当前数据上进行推断，通过对数据的分 析处理，估计数据库中某些丢失数据的可能值或一个数据集中某种属性值的分布情况。 一般是利用数学统计的方法，找出与所要预测的属性相关的属性并根据相似数据的分析 估算属性值的分布情况。例如：根据同一单位内其他职工的工资，可以预测某一职工的 可能工资。 2 4 数据挖掘系统的分类 数据挖掘是一个交叉科学领域，受多个学科影响，如图2 2 所示。包括数据库系统、 统计、机器学习、可视化和信息科学。此外，依赖于所用的数据挖掘方法，可以使用其 它学科的技术，如神经网络、模糊粗糙集理论、知识表示、归纳逻辑程序设计、或高 性能计算。依赖于所挖掘的数据类型或给定的数据挖掘应用，数据挖掘系统也可能集成 空间数据分析、信息提取、模式识别、图象分析、信号处理、计算机图形学、w e b 技术、 经济、或心理学领域的技术。数据挖掘中涉及主要的相关领域如图2 2 所示。 图2 2 数据挖掘相关领域 f i g 2 2 d a t am i n i n gr e l a t e d8 r e , 8 s 在这里，需要强调一下有些人认为数据挖掘是统计学的一个分支。但事实上这是不 正确的【7 1 。数据挖掘中使用了统计学的方法，但是也用到了其它领域的方法。另外，统 一8 一 大连理工大学硕士学位论文 计学的研究对象是数值型的数据，而数据挖掘研究的对象不仅包括了数值型，还包括很 多其它类型的数据。因此不能将二者混为一谈。 由于数据挖掘源于多个学科，因此数据挖掘研究就产生了大量的、各种不同类型数 据挖掘系统。这样，就需要对数据挖掘系统给出一个清楚的分类。这种分类可以帮助用 户区分数据挖掘系统，确定最适合其需要的数据挖掘系统。 一个全面的数据挖掘系统应当提供多种或集成的数据挖掘功能。此外，数据挖掘系 统可以根据所挖掘的知识的粒度或抽象层进行区分，包括泛化知识( 在高抽象层) ，原始 层知识( 在原始数据层) ，或多层知识( 考虑若干抽象层) 。一个先进的数据挖掘系统应当 支持多抽象层的知识发现。 数据挖掘系统还可以分类为挖掘数据规律( 通常出现的模式) 和数据反规律( 如例外 或局外者) 。 一般地，概念描述、关联分析、分类、预测和聚类挖掘数据规律，将局外者作为噪 音排除。这些方法也能帮助检测局外者。 根据不同的标准，数据挖掘系统可以分类如下： ( 1 ) 根据挖掘的数据库类型分类：数据挖掘系统可以根据挖掘的数据库类型分类。 数据库系统本身可以根据不同的标准( 如数据模型，或数据或所涉及的应用类型) 分类， 每一类可能需要自己的数据挖掘技术。这样，数据挖掘系统就可以相应分类。 例如，如果根据数据模型分类，我们可以有关系的、事务的、面向对象的、对象一 关系的、或数据仓库的数据挖掘系统。如果根据所处理的数据的特定类型分类，我们有 空间的、时间序列的、文本的、或多媒体的数据挖掘系统，或w w w 数据挖掘系统。 ( 2 ) 根据挖掘的知识类型分类：数据挖掘系统可以根据所挖掘的知识类型分类。即， 根据数据挖掘的功能，如特征、区分、关联、聚类、局外者、趋势和演化分析、偏差分 析、类似性分析等分类。 ( 3 ) 根据所用的技术分类：数据挖掘系统也可以根据所用的数据挖掘技术分类。这 些技术可以根据用户交互程度( 例如，自动系统、交互探查系统、查询驱动系统) ，或所 用的数据分析方法( 例如，面向数据库或数据仓库的技术，机器学习、统计、可视化、 模式识别、神经网络等等) 描述。复杂的数据挖掘系统通常采用多种数据挖掘技术，或 采用有效的、集成的技术，结合一些方法的优点。 ( 4 ) 根据应用分类：数据挖掘系统可以根据其应用分类。例如，可能有些数据挖掘 系统特别适合财政、电讯、d n a 、股票市场、e m a i l 等等。不同的应用通常需要集成对 于该应用特别有效的方法。因此，普通的、全能的数据挖掘系统可能并不适合特定领域 的挖掘任务。 基于数据分区的密度聚类算法的研究 2 5聚类算法 聚类分析是数据挖掘的核心技术，是指将物理或抽象对象的集合分组成为由类似的 对象组成的多个类的过程。对象根据最大化类内的相似性，最小化类间的相似性原则进 行聚类。聚类是数据挖掘的前期预处理过程，良好的聚类会对数据挖掘的结果起到很大 的作用。聚类分析的研究领域包括：数据挖掘，统计学，机器学习，空间数据库技术， 生物学，以及市场营销。目前，聚类分析已经成为数据挖掘领域中的一个非常活跃的研 究课题。聚类分析是一种重要的人类行为，早在孩提时代，一个人就通过不断地改进下 意识中的聚类模式来学会如何区分猫和狗，或者动物和植物。聚类分析已经广泛地用在 许多应用中，包括模式识别，数据分析，图像处理，以及市场研究。通过聚类，一个人 能识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间的有趣的相 互关系。 聚类分析的应用领域很广泛，包括：在商业上，聚类能帮助市场分析人员从客户基 本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上聚 类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚 类在地球观测数据库中的相似地区的确定，汽车保险持有者的分组，及根据房子的类型， 价值，和地理位置对一个城市中的房屋的分组上也可以发挥作用。同时，聚类也可以用 于对w e b 上的文档进行分类，以发现信息。 聚类算法包括： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) 给定k ，即要构建的划分数目，首先创建一个初始划分。然后采用一种迭代的重定 位技术，尝试通过对象在划分间的移动来改进划分。一个好的划分的一般准则是：在同 一类的对象之间的距离尽可能小，而不同类的对象之间的距离尽可能大。主要包括的方 法有： k 平均( k - m e a n s ) ：随机地选择k 个对象，每个对象初始地代表了一个簇中心。 对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每 个簇的平均值。这个过程不断重复，直到准则函数收敛。 k 中心张m e d o i d s ) ：k m e d o i d s 算法用中心对象代替中j 心。首先为每个簇 随意选择选择一个代表对象；剩余的对象根据其与代表对象的距离分配给最近的一个 簇。然后反复地用非代表对象来替代代表对象，以改进聚类的质量。 c l a r a n s ( 大规模数据库中的划分方法) ：不考虑整个数据集合，选择实际数据 的- - 4 , 部分作为数据的样本。然后用p a m ( p a r t i t i o na r o u n dm e d o i d s ，围绕中心点的划分) 大连理工大学硕士学位论文 方法从样本中选择代表对象。如果样本是以非常随机的方式选取的，它应当足以代表原 来的数据集合。从中选出的代表对象很可能与从整个数据集合中选出的非常近似。 ( 2 ) 层次方法( h i e r ：l r c 灶c a lm e t h o d ) 一个层次的聚类方法将数据对象组成一棵聚类的树。根据层次分解是自底向上，还 是自顶向下形成，层次的聚类方法可以进一步分为凝聚( a g g l o m e r a t i v e ) 和分裂( d i v i s i v e ) 层次聚类。各种合并型层次聚类算法的基本步骤相同，它们的差别在于聚类间的距离的 定义不同。两个聚类间距离的计算方法主要有：最小距离、最大聚类间距离、类平均距 离、中心距离等等。层次方法要求用户给定一个合并或分解的终止条件，例如聚类的个 数或者两个聚类间的最小距离。主要方法有 b i r c h ：是一个综合的层次聚类方法。其主要思想是：扫描数据库，建立一个初 始存放于内存中的c f 树，然后采用某个聚类算法对c f 树的叶子结点进行聚类。通过聚类 特征可以方便地进行中心、半径、直径及类内、类间距离的运算。 c u r e ：采用了抽样和分区的技术。首先对数据随机抽样，把样本划分成若干 个分区，在每个分区内部进行局部聚类，得到固定数目的局部聚类。然后，对所有的局 部聚类进行全局聚类。 ( 3 ) 基于密度的方法( d e n s i t y b a s e dm e t h o d ) 这类方法根据每个簇的密度阈值、而不是簇的数目阈值控制聚类的过程，即只要临 近簇的密度超过某个阈值，就继续聚类，聚类终止的条件是满足密度要求。 ( 4 ) 基于网格的方法( 面d b a s e dm e 也o ：基于网格的聚类方法采用一个多分辨率 的网格数据结构。基于网格的方法把对象空间量化为有限数目的单元，形成网格结构。 所有的聚类操作都在这个网格结构上进行。它将空间量化为有限数目的单元，这些单元 形成了网格结构，所有的聚类操作都在网格上进行。这处理时间独立于数据对象的数目， 仅依赖于量化空间中每一维上的单元数目，只与量化空间中每一维的单元数目有关。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e m o d ) ：基于模型的聚类方法试图优化给定的数 据和某些数学模型之间的适应性。基于模型的聚类方法试图优化给定的数据和某些数学 模型之间的适应性，为每个簇假定一个模型，寻找数据对给定模型的最佳匹配。 除了以上各种经典的算法外，新出现了一种模糊算法也成为热点研究方向。 ( 6 ) 糊聚类方法 随着近年来计算机技术的发展，聚类分析越来越多地用于大量的未知类别数据的分 类。在模糊聚类分析中，首先需要计算模糊相似矩阵，而不同的模糊相似矩阵就会产生 不同的分类结果。即使采用相同的模糊相似矩阵，不同的截集水平也会产生不同的分类 结果。代表方法是f c m 算法。 基于数据分区的密度聚类算法的研究 2 6 各种聚类算法的比较 各种聚类算法相继提出，每种新算法都声称至少比以前的一种算法优越，这使得各 种聚类算法之间的比较变得越来越困难。实际上任何算法都不能够证明自己比其它所有 的算法在每个方面都优越，许多聚类算法都是为特定的领域设计的，都有各自的特点和 应用范围，因而任何聚类算法都不可能在每个标准上都优越于其它算法。表2 1 根据聚 类算法的特点，对各种聚类算法进行了总结评价。 表2 1 各种聚类算法的比较 t a b 2 1t h ec o m p a r i s o no f e a c hc l u s t e r i n ga l g o r i t h m 类型算法聚类质量聚类形状 输入顺序 噪声处理数据类型时间 敏感 复杂度 划分 k m 哐a n s 一般球形是差数值o ( n k d ) c l a r a n s 一般球形是一般数值o 层次 b i r c h 好球形是 一般 数值o c u r e 好任意否较好数值0 心s 撇0 l o g n s p l a c h a m e l e o n 较好任意否较好数值o ) 密度 d b s c a n 好任意否好数值o ( n l o g n ) o p t i c s 好任意 否好数值 o ( n l o g n ) 网格 s t 玎、j g 一般任意否好数值o ( k m n ) c l i q u e一般任意否好数值o 模型 c o b 吧b 好特定 否 好任意o 2 7 几种常用的聚类质量评价方法 一般来说评价聚类和选择最优聚类模式的原则有两个：紧密度，即簇中的成员必须 尽可能地相互靠近。分离度，即簇与簇之间的距离尽可能地远。大多数评价聚类质量的 方法都是基于这两个原则。目前聚类质量的度量方法大致可分为外部度量、内部度量和 相对度量3 大类【8 】。对以这几种度量方法都有其适用的范围，其中使用最广泛的度量方 法就是内部度量方法。 ( 1 ) 内部度量 如果处理的数据集结构未知，聚类结果的评价就只能依赖数据集自身的特征和量 值。在这种情况下聚类分析的度量追求两个目标紧密度和分离度。此外还要考虑单个簇 的大小以达到均衡较好的解。如果不考虑簇的数目，直接将最优化标准应用于评价度量， 大连理工大学硕士学位论文 那么上述两个目标就有可能产生没有价值的平凡解。一般来说，使用簇内方差来评价聚 类的质量。用簇内方差即误差平方或最小方差标准，寻求簇内距离最小化。 定义为公式( 2 1 ) ： 矿( c ) = 艿( f ，p 七) 2( 2 1 ) 其中c 为所有的簇，后从是簇c 的质心，万( d 为距离函数，计算数据点f 与其对 应的簇中心的距离。簇内方差最小值取决于簇的数目，最佳聚类质量的期望为零，即其 值越小，聚类质量越好。 ( 2 ) 外部度量 是指聚类分析的评价函数是针对基准问题的其簇的，个数及每个数据项的正确的分 类均为已知。在这种情况下忽略划分的期望特征，只注重所得簇的分配的有效性，评价 变得很直接。 如果已知数据的结构，那么确定簇的数目是算法性能的第1 个指标。许多算法需要 事先给出簇的数目，并且簇的数目会极大地影响其它分析性能的度量。目前普遍使用的 规则是c 眦刀，c 雠是最大聚类数，刀为数据集中的数据对象数。 下面2 个度量将产生的类与标准的类进行比较，评价簇的纯净度与完整度。 ( 1 ) 簇c k 的纯净度定义为：根据已知正确类标识t t ，标识为该类的数据占整个簇的 比例，即公式( 2 2 ) 。 酬回= 哗t e l 篙 ( 2 2 ) ，、 其中n k 是簇c k 的大小，n t k 是该簇中表示为t 的数量。整个聚类的纯净度p ( c ) 是所有簇 的纯净度的均值，其范围为 0 ，1 ，期望为最大化，即纯净度越高，聚类质量越好。 ( 2 ) 划分的相对随机性程度可以用聚类熵来评价。聚类考虑各个簇内的所有类的分布 情况，比纯净的使用更为广泛。一个聚类熵定义为公式( 2 3 ) 。 删一南蒜， 3 ， 其中整个熵f 倒是所有簇集合的均值，其范围( 0 ，1 ，1 表示各个簇内的类是均匀 分布的，0 表示各个簇是完全由一个类组成的纯净簇。最优化分期望划分后得到的熵能 够最小化。 ( 3 ) 相对度量 相对度量是在确定聚类算法的基础上，采用预定义的评价标准，针对该算法不同的 参数设置进行算法测试，最终选择最优的参数设置和聚类模式。常用的方法是：簇内和 基于数据分区的密度聚类算法的研究 簇间的距离度量的线性组合，定义为公式( 2 4 ) 。 s d ( c ) = 0s c a t ( c ) + d i s ( c )( 2 4 ) 其中秒是加权参数，s c a t 是簇的平均分散度，d i s ( c ) 是簇件总体分离度。分别定义为 公式( 2 5 ) 和公式( 2 6 ) 。 s c a t ( c ) ：上y 丛盟( 2 5 ) 、7 k 毒品仃( c ) 、7 d i s ( c ) = 业( ( 艿( 七，t ，) ) ) 一1 (26)dmi n 复c ”舞c “： “。、。 其中笔掣是c 中簇的最大值和最小值的比例，仃( c ) 是数据项与其他分配的簇中心 标准差，a ( c k ) 是簇的标准差。腻分配到簇馓的数据量。是质心，巧是距离函数。 2 8 相似性和相异性的度量方法 对象间的距离或相似度是聚类的核心，常常按照对象之间的相似性进行划分，划分 的结果使某种表示聚类质量的评价函数最优。数据的类型不同，相似性的含义也不同。 例如在数值型数据库中，两个对象的相似度是指它们在几何空间中互相邻近的程度；在 分类型数据库中，两个对象的相似性是指它们在同一个属性上取值相同；在交易型数据 库中，两个交易相似是指它们包含相同的数据项。相似性的度量方法很多，有的用于专 门领域，也有的适用于特定类型的数据，如何选择相似性的度量方法是一个相当复杂的 问题，选择相似性的一个重要因素是属性的类型。 假设每个对象有k 个属性，可以把一个对象视为k 维空间的一个点，n 个对象就是k 维 空间中的r 1 个点。从直观上看，属于同一类的对象在空间中应该互相靠近，而不同类的 对象之间的距离要大得多，很自然地想到用它们之间的距离来衡量它们之间的相似程 度。距离越小，对象间的相似性越大。 定义i = ( x i l ，x i ：，x i k ) 和j = ( x j l ，x 2 ，x j k ) 是两个k 维的数据对象，则距离的定义应 满足如下的数学要求： ( 1 ) d ( i j ) ：o ：距离是一个非负的数值； ( 2 )