1、第三章 数据挖掘中的聚类分析课题名称： 数据挖掘中的聚类算法研究研究生姓名： 焦守荣 指导教师： 何建忠 学位级别： 硕士 学科专业： 计算机应用技术 档号： 学号：0228202 关键词： 数据挖掘 聚类分析 簇 代表点 密度摘 要： 聚类分析是数据挖掘的重要组成部分，近年来在该领域的研究取得了长足的发展。通过对现有的聚类算法的研究，如基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法以及整合了多种聚类算法的综合算法，可以发现，这些算法在特定的领域中、特定的情形下取得了良好的效果。但由于数据集的增大和数据复杂性的提高，聚类算法无论是从算法运算的
2、时间上，还是从算法本身所需要的存储空间上都急剧的膨胀，使得在现有资源下很难实现数据集的最终聚类。本论文在对各种算法深入分析的基础上，尤其在对基于密度的聚类算法、基于层次的聚类算法和基于划分的聚类算法的深入研究的基础上，提出了一种新的基于密度和层次的快速聚类算法。该算法保持了基于密度聚类算法发现任意形状簇的优点，而且具有近似线性的时间复杂性，因此该算法适合对大规模数据的挖掘。理论分析和实验结果也证明了基于密度和层次的聚类算法具有处理任意形状簇的聚类、对噪音数据不敏感的特点，并且其执行效率明显高于传统的 DBSCAN 算法。目 录摘 要Abstract第一章 绪 论第三章 数据挖掘中的聚类分析第二
3、章 数据挖掘简介第三章 数据挖掘中的聚类分析第四章 基于密度和层次的快速聚类算法第五章 实验分析及性能比较第六章 总结和展望参考文献致 谢在读期间公开发表的论文和承担科研项目及取得成果目 录摘要ABSTRACT第一章 绪论. 11.1 数据挖掘产生的背景. 11.2 国内外研究的现状及发展. 11.3 本文研究的主要内容. 2第二章 数据挖掘简介. 42.1 数据挖掘的定义. 42.2 数据挖掘的研究内容和本质. 52.3 数据挖掘的流程. 62.4 数据挖掘涉及的主要技术. 82.4.1 关联规则. 82.4.2 分类算法. 9第三章 数据挖掘中的聚类分析2.4.3 聚类分析. 112.5
4、目前数据挖掘领域研究方向. 12第三章 数据挖掘中的聚类分析. 143.1 聚类分析的定义. 143.2 聚类分析中的数据结构. 143.3 聚类分析中的数据类型. 153.4 对现有聚类算法的研究. 183.4.1 串行聚类算法. 183.4.1.1 划分方法（partitioning method ）. 183.4.1.2 层次方法（hierarchical method ）. 193.4.1.3 基于密度的方法（density-based method）. 223.4.1.4 基于网格的方法（grid-based method）. 243.4.1.5 基于模型的方法（model-base
5、d method ）. 263.4.2 并行聚类算法. 273.5 设计聚类算法的准则. 27第四章 基于密度和层次的快速聚类算法. 304.1 算法思想的形成过程. 304.2 基于密度和层次的快速聚类算法的思想. 324.3 算法相关的基本概念. 334.4 算法描述. 334.4.1 数据结构. 354.4.2 确定候选代表点集合. 36第三章 数据挖掘中的聚类分析4.4.3 确定代表点集合. 394.4.4 确定代表点代表区域内的点集. 404.4.5 对代表点集合进行簇的划分. 414.4.6 将代表点的聚类划分映射到数据点. 424.4.7 聚类结果. 424.5 算法的时空复杂度
6、分析. 424.5.1 时间复杂度. 424.5.2 空间复杂度. 43第五章 实验分析及性能比较. 445.1 聚类效果的比较. 445.2 输入参数的设定. 455.3 执行效率的比较. 45第六章 总结和展望. 476.1 工作总结. 476.2 问题与展望. 48参考文献. 49在读期间公开发表的论文和承担科研项目及取得成果. 53致 谢. 54摘要聚类分析是数据挖掘的重要组成部分，近年来在该领域的研究取得了长足的发展。第三章 数据挖掘中的聚类分析通过对现有的聚类算法的研究，如基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法以及整合了多
7、种聚类算法的综合算法，可以发现，这些算法在特定的领域中、特定的情形下取得了良好的效果。但由于数据集的增大和数据复杂性的提高，聚类算法无论是从算法运算的时间上，还是从算法本身所需要的存储空间上都急剧的膨胀，使得在现有资源下很难实现数据集的最终聚类。本论文在对各种算法深入分析的基础上，尤其在对基于密度的聚类算法、基于层次的聚类算法和基于划分的聚类算法的深入研究的基础上，提出了一种新的基于密度和层次的快速聚类算法。该算法保持了基于密度聚类算法发现任意形状簇的优点，而且具有近似线性的时间复杂性，因此该算法适合对大规模数据的挖掘。理论分析和实验结果也证明了基于密度和层次的聚类算法具有处理任意形状簇的聚类
8、、对噪音数据不敏感的特点，并且其执行效率明显高于传统的 DBSCAN算法。关键词：数据挖掘 聚类分析簇 代表点 密度AbstractClustering analysis is an important part of the whole Data Mining system. The research in this field has got a great advancement in recent years.By the studying of these clustering algorithms, such as, Partitioning methods, Hierarchic
9、al methods, Density-based methods, Grid-based methods, Model-based methods and some clustering algorithms integrate the ideas of several clustering methods. We will find, although all these methods have got great achievement in different fields, the huge quantity and high complexity of the original
10、data set make clustering algorithm needs more and more time and memory to deal with them. It is not accuracy in limited resource. Based on the analysis on clustering algorithms especially on Density-Based clustering algorithm、Hierarchical-Based clustering algorithm and Partition-Based clustering alg
11、orithm, in this paper, a new kind of clustering algorithm that is clustering based on density and hierarchy is presented. This algorithm keeps the ability of density based clustering methods good features, and it can reach high efficiency because of its linear time complexity, so it can be used in m
12、ining very large databases. Both theory analysis and experimental results confirm that this algorithm can discover clusters with arbitrary shape and is insensitive to noise data. In the meanwhile, its executing 第三章 数据挖掘中的聚类分析efficiency is much higher than traditional DBSCAN algorithm.Key words: Data
13、 Mining, Clustering Algorithm, Cluster, Reference, Density第一章 绪论1.1 数据挖掘产生的背景随着计算机技术和信息技术的发展，信息的增长速度呈现指数上升，已远远超出了人们分析它们并从中提取有用信息的能力。虽然数据库系统可以高效地实现数据的录入、查询、简单统计等功能，但却无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势，也就是说使用传统分析方法远远不能满足现实的需求。面对海量数据，如何从中发现有价值的信息或知识，成为一项非常艰巨的任务。人们迫切需要一种去粗存精、去伪存真的技术，迫切需要一种能够对数据进行深层次加工的自
14、动化技术。能够从海量的数据中提取知识和信息的数据挖掘技术应运而生 1。数据挖掘 DM（Data Mining）技术就在这样的背景下诞生了。它出现于 20 世纪 80 年代后期，90 年代有了突飞猛进的发展，并在 21 世纪继续繁荣。还有很多和这一术语相近似的术语,如从数据库中发现知识(KDD)、数据分析、数据融合(Data Fusion)以及决策支持等。数据挖掘将数据库管理系统和人工智能中机器学习两种技术相结合，用数据库管理系统来存储数据，用机器学习的方法来分析数据，自动发现大量数据中隐含的知识。数据挖掘是一门交叉性学科，涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、高性
15、能计算、专家系统等多个领域，集中探讨关于隐藏在大型数据库中的模式发现技术的可行性、有用性、有效性和可伸缩性问题 2。从数据库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许多方面。数据挖掘技术是面向应用的，它不仅是面向特定数据库的简单检索查询调用,而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理,以指导实际问题的求解,企图发现事件间的相互关联,甚至利用已有的数据对未来的活动进行预测 3。1.2 国内外研究的现状及发展数据库的知识发现 KDD 一词首次出现在 1989 年 8 月举行的第 11 届国际联合第三章 数据挖掘中的聚类分析人工智能学术会议上。迄今为止,
16、世界上有许多国家的专家和学者都在致力于数据挖掘的研究，研究方面主要有：对知识发现方法的研究进一步发展；传统的统计学回归法在 KDD 中的应用；KDD 与数据库的紧密结合及多种学科之间的相互渗透。致力于数据挖掘算法研究的学术团体、会议和组织有很多，其中比较著名有ACM SIGKDD、IEEE ICDM、SDM、PAKDD、VLDB、FSKD、MLDM 等。目前，国外数据挖掘的发展趋势在应用方面包括：KDD 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。国外很多计算机公司非常重视数据挖掘的开发应用，IBM 和微软都成立
17、了相应的研究中心进行这方面的工作，此外，一些公司的相关软件也开始在国内外销售，如 Platinum、BO 以及 IBM。与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。目前，从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司，所涉及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论方面的研究，并且大多数研究项目是由政府资助进行的。比如清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、中国科
18、技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及 Web 数据挖掘。一份 Gartner 报告中列举了在今后几年内对工业将产生重要影响的五项关键技术，其中 KDD 和人工智能排名第一。同时，这份报告将并行计算机体系结构研究和 KDD 列入今后 5 年内公司应该投资的 10 个新技术领域。可以看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重视。1.3 本文研究的主要内容目前，数据挖掘领域中已经有许多研究成果在商业上得到广泛的应用。聚类(clustering)则是数据挖掘技术中一
19、个重要的研究方向，它对数据对象进行分组簇，使组内各对象间具有较高的相似度，而不同组的对象差别较大。在许多应用中，可以将一个簇中的数据对象作为一个整体来对待。通过聚类，可以识别密集和稀疏的区域，因而发现全局的分布模式及数据属性之间有趣的相互关系。作为一个数据挖掘的功能，聚类能作为一个独立的工具来获得数据分布的情况，通过第三章 数据挖掘中的聚类分析观察每个簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类还可以作为其它算法(如:关联规则和分类)的预处理步骤。现有的聚类算法大致可以分为四大类:划分聚类算法、层次聚类算法、密度型聚类算法、网格型聚类算法。目前已经有很多比较成熟的聚类算法，如KMea
20、ns，K-Medoids， BIRCH，CURE，DBSCAN，STING 等。虽然其中有些算法己经得到成功应用，但是，聚类分析也面临着越来越多的新问题。如海量数据的处理、高维数据的聚类、子空间聚类、带有约束条件的聚类、数据流聚类等。针对这些新问题，很多人在不断研究新的算法，也有人在以前算法的基础上不断地进行改进。本文研究的主要内容是设计高效的且能发现任意形状簇的聚类分析算法及该算法的系统实现。具体的讲，研究的内容包括以下几个方面：1 调查研究当前主要的聚类分析算法2 聚类分析算法优化的研究3 提出一种基于密度和层次的聚类分析算法，该算法能够达到理想的聚类算法的多项要求4 基于密度和层次聚类算
21、法的实现与测试5 基于密度和层次聚类算法与现有算法在聚类效果和效率上的比较第二章 数据挖掘简介2.1 数据挖掘的定义1 技术上的定义数据挖掘 (Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程 4,5。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的;发现的是用户感兴趣的知识；发现的知识要求可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作
22、是形成知识的源泉。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和第三章 数据挖掘中的聚类分析图像数据；甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究
23、领域，形成新的技术热点。这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果 5。2 商业角度的定义数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身己经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计
24、算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的(Opportunistic)商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐
25、藏的、未知的或验证已知的规律性，并进一步将其模型化为先进有效的方法。2.2 数据挖掘的研究内容和本质随着数据挖掘研究逐步走向深入，数据挖掘的研究己经形成了三根强大的技第三章 数据挖掘中的聚类分析术支柱：数据库、人工智能和数理统计 6。目前数据挖掘的主要研究内容包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识（或模式）发现以及网上数据挖掘等。数据挖掘所发现的知识（或模式）最常见的有以下几类 7：1 概念描述 (Concept Description)概念描述是指提供给定数据集的概貌，或将它与对比类相区别，从而产生
26、数据的特征化和比较描述。对于存在数据库中的大量数据，能够以简洁的形式在更抽象的层次上描述数据，能够帮助用户考察数据的一般行为。概念描述的典型应用是概念层次树，即按照某种偏序关系建立一种描述数据的结构。2 关联分析 (Association Analysis)关联分析反映一个事件和其他事件之间依赖或关联的规则。如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。关联规则是形如 XY 的规则，其中 X,Y 为属性-值对集(或称项目集)且 XY 为空集。在数据库中若 A 的实例同时包含 X 和 Y(或 s%的实例包含 XY)则关联规则XY 的支持率为 s%。若 c%的包
27、含属性-值对集 X 的事务也包含属性-值对集 Y，则关联规则 XY 的置信度为 c%。一般来说，需要找出的是支持率和置信度分别大于或等于用户指定的最小支持率(minsup)和最小置信度(minconf)的关联规则。关联规则采掘过程可以分解为以下两个子问题：找出所有的频繁项目集及其支持率；根据找到的频繁项目集导出所有的置信度大于或等于用户指定的最小置信度的关联规则 8。第二个子问题的解决是直截了当的，所以一般的研究集中在第一个子问题上。3 分类 (Classification)分类模式是指通过训练数据集导出描述并区分数据类的模型或函数，用于预测新的数据集 9。一般在建立分类模型时，使用一部分数据作为训练样本，用另一部分数据来检验、校正模型。由于在建立模型之前,训练样本的结果是已知的，模型的产生是在受监督的情况下进行的，因此分类模式属于有监督的学习。导出模型可以表现为多种形式，如决策树、数学公式或神经元网络等。4 聚类分析（Clustering Analysis）聚类分析是指把数据划分到不同的组中，使得不同组之间的差异性尽可能大，同一组内的相似性尽可能高 10。根据不同的应用，对差异性有不同的数学定义。与分类模式不同，进行聚类之前并不知道数据要划分成几个组以及划分成什么样的组。因此，聚类分析在模型建立前结果是未知的，属于典型的非监督学习。本
