数据挖掘中的聚类算法研究

VIP免费

3.0 赵德峰 2024-11-19 4 4 653.46KB 56 页 15积分

侵权投诉

摘要

聚类分析是数据挖掘的重要组成部分，近年来在该领域的研究取得了长足的

发展。

通过对现有的聚类算法的研究，如基于划分的聚类方法、基于层次的聚类方

法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法以及整合

了多种聚类算法的综合算法，可以发现，这些算法在特定的领域中、特定的情形

下取得了良好的效果。但由于数据集的增大和数据复杂性的提高，聚类算法无论

是从算法运算的时间上，还是从算法本身所需要的存储空间上都急剧的膨胀，使

得在现有资源下很难实现数据集的最终聚类。

本论文在对各种算法深入分析的基础上，尤其在对基于密度的聚类算法、基

于层次的聚类算法和基于划分的聚类算法的深入研究的基础上，提出了一种新的

基于密度和层次的快速聚类算法。该算法保持了基于密度聚类算法发现任意形状

簇的优点，而且具有近似线性的时间复杂性，因此该算法适合对大规模数据的挖

掘。理论分析和实验结果也证明了基于密度和层次的聚类算法具有处理任意形状

簇的聚类、对噪音数据不敏感的特点，并且其执行效率明显高于传统的 DBSCAN 算

法。

关键词：数据挖掘聚类分析簇代表点密度

Abstract

Clustering 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,

Hierarchical 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 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 algorithm, 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 method’s good features, and it can reach high efficiency because of its

linear time complexity, so it can be used in mining 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 Mining, Clustering Algorithm, Cluster, Reference,

Density

摘要

ABSTRACT

第一章绪论 ..........................................................1

§1.1 数据挖掘产生的背景 ......................................... 1

§1.2 国内外研究的现状及发展 ..................................... 1

§1.3 本文研究的主要内容 ......................................... 2

第二章数据挖掘简介 ..................................................4

§2.1 数据挖掘的定义 ............................................. 4

§2.2 数据挖掘的研究内容和本质 ................................... 5

§2.3 数据挖掘的流程 ............................................. 6

§2.4 数据挖掘涉及的主要技术 ..................................... 8

§2.4.1 关联规则 .............................................. 8

§2.4.2 分类算法 .............................................. 9

§2.4.3 聚类分析 ............................................. 11

§2.5 目前数据挖掘领域研究方向 ................................. 12

第三章数据挖掘中的聚类分析 ........................................14

§3.1 聚类分析的定义 ............................................ 14

§3.2 聚类分析中的数据结构 ...................................... 14

§3.3 聚类分析中的数据类型 ...................................... 15

§3.4 对现有聚类算法的研究 ...................................... 18

§3.4.1 串行聚类算法 ......................................... 18

§3.4.1.1 划分方法（partitioning method） ................ 18

§3.4.1.2 层次方法（hierarchical method） ................ 19

§3.4.1.3 基于密度的方法（density-based method） ......... 22

§3.4.1.4 基于网格的方法（grid-based method） ............ 24

§3.4.1.5 基于模型的方法（model-based method） ........... 26

§3.4.2 并行聚类算法 ......................................... 27

§3.5 设计聚类算法的准则 ........................................ 27

第四章基于密度和层次的快速聚类算法 .................................30

§4.1 算法思想的形成过程 ........................................ 30

§4.2 基于密度和层次的快速聚类算法的思想 ........................ 32

§4.3 算法相关的基本概念 ........................................ 33

§4.4 算法描述 .................................................. 33

§4.4.1 数据结构 ............................................. 35

§4.4.2 确定候选代表点集合 ................................... 36

§4.4.3 确定代表点集合 ....................................... 39

§4.4.4 确定代表点代表区域内的点集 ........................... 40

§4.4.5 对代表点集合进行簇的划分 ............................. 41

§4.4.6 将代表点的聚类划分映射到数据点 ....................... 42

§4.4.7 聚类结果 ............................................. 42

§4.5 算法的时空复杂度分析 ...................................... 42

§4.5.1 时间复杂度 ........................................... 42

§4.5.2 空间复杂度 ........................................... 43

第五章实验分析及性能比较 ..........................................44

§5.1 聚类效果的比较 ............................................ 44

§5.2 输入参数的设定 ............................................ 45

§5.3 执行效率的比较 ............................................ 45

第六章总结和展望 ..................................................47

§6.1 工作总结 .................................................. 47

§6.2 问题与展望 ................................................ 48

参考文献 ............................................................ 49

在读期间公开发表的论文和承担科研项目及取得成果 ...................... 53

致谢 ..............................................................54

第一章绪言

第一章绪论

§1.1 数据挖掘产生的背景

随着计算机技术和信息技术的发展，信息的增长速度呈现指数上升，已远远

超出了人们分析它们并从中提取有用信息的能力。虽然数据库系统可以高效地实

现数据的录入、查询、简单统计等功能，但却无法发现数据中存在的关系和规则，

无法根据现有的数据预测未来的发展趋势，也就是说使用传统分析方法远远不能

满足现实的需求。面对海量数据，如何从中发现有价值的信息或知识，成为一项

非常艰巨的任务。人们迫切需要一种去粗存精、去伪存真的技术，迫切需要一种

能够对数据进行深层次加工的自动化技术。能够从海量的数据中提取知识和信息

的数据挖掘技术应运而生[1]。

数据挖掘DM（Data Mining）技术就在这样的背景下诞生了。它出现于20世纪

80年代后期，90年代有了突飞猛进的发展，并在21世纪继续繁荣。还有很多和这

一术语相近似的术语,如从数据库中发现知识(KDD)、数据分析、数据融合(Data

Fusion)以及决策支持等。数据挖掘将数据库管理系统和人工智能中机器学习两种

技术相结合，用数据库管理系统来存储数据，用机器学习的方法来分析数据，自

动发现大量数据中隐含的知识。数据挖掘是一门交叉性学科，涉及到机器学习、

模式识别、统计学、智能数据库、知识获取、数据可视化、高性能计算、专家系

统等多个领域，集中探讨关于隐藏在大型数据库中的模式发现技术的可行性、有

用性、有效性和可伸缩性问题[2]。从数据库中发现出来的知识可以用在信息管理、

过程控制、科学研究、决策支持等许多方面。数据挖掘技术是面向应用的，它不

仅是面向特定数据库的简单检索查询调用,而且要对这些数据进行微观、中观乃至

宏观的统计、分析、综合和推理,以指导实际问题的求解,企图发现事件间的相互

关联,甚至利用已有的数据对未来的活动进行预测[3]。

§1.2 国内外研究的现状及发展

数据库的知识发现KDD一词首次出现在1989年8月举行的第11届国际联合人工

智能学术会议上。迄今为止, 世界上有许多国家的专家和学者都在致力于数据挖

掘的研究，研究方面主要有：对知识发现方法的研究进一步发展；传统的统计学

回归法在KDD中的应用；KDD与数据库的紧密结合及多种学科之间的相互渗透。致

力于数据挖掘算法研究的学术团体、会议和组织有很多，其中比较著名有ACM

数据挖掘中聚类算法的研究

SIGKDD、IEEE ICDM、SDM、PAKDD、VLDB、FSKD、MLDM等。目前，国外数据挖掘的

发展趋势在应用方面包括：KDD商业软件工具不断产生和完善，注重建立解决问题

的整体系统，而不是孤立的过程。用户主要集中在大型银行、保险公司、电信公

司和销售业。国外很多计算机公司非常重视数据挖掘的开发应用，IBM和微软都成

立了相应的研究中心进行这方面的工作，此外，一些公司的相关软件也开始在国

内外销售，如Platinum、BO以及IBM。

与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。目前，从事

数据挖掘研究的人员主要在大学，也有部分在研究所或公司，所涉及的研究领域

很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论

方面的研究，并且大多数研究项目是由政府资助进行的。比如清华大学、中科院

计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京系统工程

研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展

对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、中国科技大学、

中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优化和改造；

南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数据的知

识发现以及Web数据挖掘。

一份Gartner报告中列举了在今后几年内对工业将产生重要影响的五项关键

技术，其中KDD和人工智能排名第一。同时，这份报告将并行计算机体系结构研究

和KDD列入今后5年内公司应该投资的10个新技术领域。可以看出，数据挖掘的研

究和应用受到了学术界和实业界越来越多的重视。

§1.3 本文研究的主要内容

目前，数据挖掘领域中已经有许多研究成果在商业上得到广泛的应用。聚类

(clustering)则是数据挖掘技术中一个重要的研究方向，它对数据对象进行分组

簇，使组内各对象间具有较高的相似度，而不同组的对象差别较大。在许多应用

中，可以将一个簇中的数据对象作为一个整体来对待。通过聚类，可以识别密集

和稀疏的区域，因而发现全局的分布模式及数据属性之间有趣的相互关系。作为

一个数据挖掘的功能，聚类能作为一个独立的工具来获得数据分布的情况，通过

观察每个簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类还可以作

为其它算法(如:关联规则和分类)的预处理步骤。

现有的聚类算法大致可以分为四大类:划分聚类算法、层次聚类算法、密度型

聚类算法、网格型聚类算法。目前已经有很多比较成熟的聚类算法，如KMeans，

K-Medoids， BIRCH，CURE，DBSCAN，STING等。虽然其中有些算法己经得到成功

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

1摘要聚类分析是数据挖掘的重要组成部分，近年来在该领域的研究取得了长足的发展。通过对现有的聚类算法的研究，如基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法以及整合了多种聚类算法的综合算法，可以发现，这些算法在特定的领域中、特定的情形下取得了良好的效果。但由于数据集的增大和数据复杂性的提高，聚类算法无论是从算法运算的时间上，还是从算法本身所需要的存储空间上都急剧的膨胀，使得在现有资源下很难实现数据集的最终聚类。本论文在对各种算法深入分析的基础上，尤其在对基于密度的聚类算法、基于层次的聚类算法和基于划分的聚类算法的深入研究的基础上，提出了一种新的...

展开>> 收起<<

数据挖掘中的聚类算法研究.pdf

共56页,预览6页

还剩页未读，继续阅读

数据挖掘中的聚类算法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: