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

课题名称： 数据挖掘中的聚类算法研究 研究生姓名： 焦守荣 指导教师： 何建忠 计算机应用技学位级别： 硕士 学科专业： 术 档号： 学号：0228202 关键词： 数据挖掘 聚类分析 簇 代表点 密度 摘 要： 聚类分析是数据挖掘的重要组成部分，近年来在该领域的研究取得了长足的发展。通过对现有的聚类算法的研究，如基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法以及整合了多种聚类算法的综合算法，可以发现，这些算法在特定的领域中、特定的情形下取得了良好的效果。但由于数据集的增大和数据复杂性的提高，聚类算法无论是从算法运算的时间上，还是从算法本身所需要的存储空间上都急剧的膨胀，使得在现有资源下很难实现 数据集的最终聚类。本论文在对各种算法深入分析的基础上，尤其在对基于密度的聚类算法、基于层次的聚类算法和基于划分的聚类算法的深入研究的基础上，提出了一种新的基于密度和层次的快速聚类算法。该算法保持了基于密度聚类算法发现任意形状簇的优点，而且具有近似线性的时间复杂性，因此该算法适合对大规模数据的挖掘。理论分析和实验结果也证明了基于密度和层次的聚类算法具有处理任意形状簇的聚类、对噪音数据不敏感的特点，并且其执行效率明显高于传统的DBSCAN算法。

目 录

摘 要

Abstract

第一章 绪 论

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

第二章 数据挖掘简介

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

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

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

第六章 总结和展望

参考文献

致 谢

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

目 录 摘要

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

致 谢.

摘要

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

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

通过对现有的聚类算法的研究，如基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法以及整合了多种聚类算法的综合算法，可以发现，这些算法在特定的领域中、特定的情形下取得了良好的效果。但由于数据集的增大和数据复杂性的提高，聚类算法无论是从算法运算的时间上，还是从算法本身所需要的存储空间上都急剧的膨胀，使得在现有资源下很难实现数据集的最终聚类。

本论文在对各种算法深入分析的基础上，尤其在对基于密度的聚类算法、基于层次的聚类算法和基于划分的聚类算法的深入研究的基础上，提出了一种新的基于密度和层次的快速聚类算法。该算法保持了基于密度聚类算法发现任意形状簇的优点，而且具有近似线性的时间复杂性，因此该算法适合对大规模数据的挖掘。理论分析和实验结果也证明了基于密度和层次的聚类算法具有处理任意形状簇的聚类、对噪音数据不敏感的特点，并且其执行效率明显高于传统的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

第一章 绪论

§1.1 数据挖掘产生的背景

随着计算机技术和信息技术的发展，信息的增长速度呈现指数上升，已远远超出了人们分析它们并从中提取有用信息的能力。虽然数据库系统可以高效地实现数据的录入、查询、简单统计等功能，但却无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势，也就是说使用传统分析方法远远不能满足现实的需求。面对海量数据，如何从中发现有价值的信息或知识，成为一项非常艰巨的任务。人们迫切需要一种去粗存精、去伪存真的技术，迫切需要一种能够对数据进行深层次加工的自动化技术。能够从海量的数据中提取知识和信息的数据挖掘技术应运而生。

数据挖掘DM（Data Mining）技术就在这样的背景下诞生了。它出现于20世纪80年代后期，90年代有了突飞猛进的发展，并在21世纪继续繁荣。还有很多和这一术语相近似的术语,如从数据库中发现知识(KDD)、数据分析、数据融合(Data Fusion)以及决策支持等。数据挖掘将数据库管理系统和人工智能中机器学习两种技术相结合，用数据库管理系统来存储数据，用机器学习的方法来分析数据，自动发现大量数据中隐含的知识。数据挖掘是一门交叉性学科，涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、高性能计算、专家系统等多个领域，集中探讨关于隐藏在大型数据库中的模式发现技术的可行性、有用性、有效性和可伸缩性问题[2]。从数据库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许多方面。数据挖掘技术是面向应用的，它不仅是面向特定数据库的简单检索查询调用,而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理,以指导实际问题的求解,企图发现事件间的相互关联,甚至利用已有的数据对未来的活动进行预测[3]。

[1]

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

数据库的知识发现KDD一词首次出现在19年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等。虽然其中有些算法己经得到成功应用，但是，聚类分析也面临着越来越多的新问题。如海量数据的处理、高维数据的聚类、子空间聚类、带有约束条件的聚类、数据流聚类等。针对这些新问题，很多人在不断研究新的算法，也有人在以前算法的基础上不断地进行改进。

本文研究的主要内容是设计高效的且能发现任意形状簇的聚类分析算法及该算法的系统实现。具体的讲，研究的内容包括以下几个方面：

1． 调查研究当前主要的聚类分析算法 2． 聚类分析算法优化的研究

3． 提出一种基于密度和层次的聚类分析算法，该算法能够达到理想的聚类算法的多项要求

4． 基于密度和层次聚类算法的实现与测试

5． 基于密度和层次聚类算法与现有算法在聚类效果和效率上的比较

第二章 数据挖掘简介

§2.1 数据挖掘的定义

1． 技术上的定义

数据挖掘 (Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程[4,5]。

这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的;发现的是用户感兴趣的知识；发现的知识要求可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。

从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，

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

也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。

这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果[5]。 2． 商业角度的定义

数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。

简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身己经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算能力的，对大数据量进行分析的复杂数据分析方法受到很大。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的(Opportunistic)商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。

因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化为先进有效的方法。

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

随着数据挖掘研究逐步走向深入，数据挖掘的研究己经形成了三根强大的技术支柱：数据库、人工智能和数理统计[6]。目前数据挖掘的主要研究内容包括基础

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

理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识（或模式）发现以及网上数据挖掘等。

数据挖掘所发现的知识（或模式）最常见的有以下几类[7]： 1． 概念描述 (Concept Description)

概念描述是指提供给定数据集的概貌，或将它与对比类相区别，从而产生数据的特征化和比较描述。对于存在数据库中的大量数据，能够以简洁的形式在更抽象的层次上描述数据，能够帮助用户考察数据的一般行为。概念描述的典型应用是概念层次树，即按照某种偏序关系建立一种描述数据的结构。

2． 关联分析 (Association Analysis)

关联分析反映一个事件和其他事件之间依赖或关联的规则。如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。关联规则是形如XY的规则，其中X,Y为属性-值对集(或称项目集)且X∩Y为空集。在数据库中若A的实例同时包含X和Y(或s%的实例包含X∪Y)则关联规则XY的支持率为s%。若c%的包含属性-值对集X的事务也包含属性-值对集Y，则关联规则XY的置信度为c%。一般来说，需要找出的是支持率和置信度分别大于或等于用户指定的最小支持率(minsup)和最小置信度(minconf)的关联规则。关联规则采掘过程可以分解为以下两个子问题：找出所有的频繁项目集及其支持率；根据找到的频繁项目集导出所有的置信度大于或等于用户指定的最小置信度的关联规则

[8]

。第二个子问题的解决是直截了当的，所以一般的研究集中在第一个子问题上。 3． 分类 (Classification)

分类模式是指通过训练数据集导出描述并区分数据类的模型或函数，用于预

测新的数据集[9]。一般在建立分类模型时，使用一部分数据作为训练样本，用另一部分数据来检验、校正模型。由于在建立模型之前,训练样本的结果是已知的，模型的产生是在受监督的情况下进行的，因此分类模式属于有监督的学习。导出模型可以表现为多种形式，如决策树、数学公式或神经元网络等。

4． 聚类分析（Clustering Analysis）

聚类分析是指把数据划分到不同的组中，使得不同组之间的差异性尽可能大，同一组内的相似性尽可能高[10]。根据不同的应用，对差异性有不同的数学定义。与分类模式不同，进行聚类之前并不知道数据要划分成几个组以及划分成什么样的组。因此，聚类分析在模型建立前结果是未知的，属于典型的非监督学习。本文将在后续章节详细讨论聚类分析。

5． 预测型知识(Prediction)

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

它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也可以认为是以时间为关键属性的关联知识。

目前，时间序列预测方法有经典的统计方法、神经网络和机器学习等。1968年Box和Jenkins提出了一套比较完善的时间序列建模理论和分析方法，这些经典的数学方法通过建立随机模型，如自回归模型、自回归滑动平均模型、求和自回归滑动平均模型和季节调整模型等，进行时间序列的预测。由于大量的时间序列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化。因此，仅仅通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法完成准确的预测任务。为此，人们提出了基于统计学和基于精确性的再训练方法，当发现现存预测模型不再适用于当前数据时，对模型重新训练，获得新的权重参数，建立新的模型。也有许多系统借助并行算法的计算优势进行时间序列预测。

6． 偏差型知识(Deviation)

偏差性知识是对差异和极端特例的描述，揭示事物偏离常规的异常现象，如标准类外的特例，数据聚类外的离群值等。所有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的需要。

§2.3 数据挖掘的流程

作为一个学术领域，数据挖掘和数据库知识发现具有很大的重合度，大部分学者认为数据挖掘和知识发现是等价的概念，相对来讲，数据挖掘主要流行于统计、数据分析和数据库领域，而知识发现则主要流行于人工智能和机器学习领域。从数据处理的过程看，可以把数据挖掘看作知识发现过程中同算法相关的关键一步，借助于算法在可接受的计算范围内从数据中枚举模式或模型结构。

一般来讲，数据挖掘的整个过程由若干步骤组成（如图2-1），其基本过程包括数据准备、数据挖掘和结果的解释和评估[10]。

数据收集 预处理 数据挖掘 解释评价 数据源 数据库 特定数据集

图 2-1数据挖掘的过程

模式 知识

1． 数据准备

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

数据准备又可分为三个子步骤：数据选取、数据预处理和数据变换。数据选取的目的是搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数据挖掘应用的数据。数据预处理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换等。当数据挖掘的对象是数据仓库时，一般来讲，数据预处理己经在生成数据仓库时完成了。数据变换的主要目的是消减数据维数即降维，即从初始特征中找出真正有用的特征以减少数据挖掘时要考虑的特征或变量个数。

2． 数据挖掘阶段

数据挖掘阶段首先要确定挖掘的任务或目的。清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最后结构是不可预测的，但要探索的问题应是有预见的。然后，决定使用什么样的挖掘算法。同样的任务可以用不同的算法来实现，选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户可能希望获取描述型的、容易理解的知识，而有的用户或系统的目的是获取预测准确度尽可能高的预测型知识。

3． 结果解释和评价

数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求，这时则需要整个挖掘过程重新选取数据、采用新的数据变换方法、设定新的数据挖掘参数值，甚至采用其它的挖掘算法。因此，数据挖掘的过程一般要经过反复多次，是一个不断反馈的过程。

值得注意的是，可视化在数据挖掘的整个过程中的各个阶段都起着重要作用。在数据准备阶段，用户可能要使用直方图等统计可视化技术来显示有关数据，以期对数据有一个初步的理解，从而为更好的选取数据打下基础；在挖掘阶段，用户则要使用与领域问题有关的可视化工具；在对数据挖掘的结果进行解释和评价时，通常对发现的模式进行可视化。

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

数据挖掘是从存放在数据库、数据仓库或其它数据源中的大量数据中挖掘有趣知识的过程。一般情况下，一种数据挖掘算法不可能适合所有的挖掘问题的需要。一种算法可能只适合特定的问题和特定的领域。例如：决策树分类比较适合于发现高维空间的结构，但是并不适合于决策类间的边界是由二次多项式描述的

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

问题。因此，没有通用的数据挖掘算法。为特定问题挑选一个特定的合适的算法是困难的，但是已经有了一些相关研究。

数据挖掘过程中常用的算法包括：关联规则、分类算法、预测、聚类分析、组合学习技术以及 Web 挖掘和文本挖掘算法等内容。

§2.4.1 关联规则

在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题。关联规则的一个典型例子就是:“90%的客户在购买面包的同时也会购买牛奶”,其直观意义为顾客在购买某些商品的时候有多大的倾向会购买另外一些商品。关联规则的发现可分为两步：第一步是迭代识别所有的频繁项目集，要求频繁项目集的支持率不低于用户设定的最低值；第二步是从频繁项目集中构造可信度不低于用户设定的最低值的规则。识别或发现所有频繁项目集是关联规则发现算法的核心，也是计算量最大的部分。

最为著名的关联规则发现方法是R.Agrawal提出的Apriori算法。Apriori算法通过多次迭代来找出所有的频繁项目集，在第k次迭代过程中找出所有的频繁k项目集Lk。该算法使用如下启发式规则：一个项目集是频繁项目集，则此项目集的所有子集构成的项目集也一定是频繁项目集；一个项目集是非频繁项目集，则此项目集的所有超集(即包含此项目集的项目集)一定是非频繁项目集。因此，第k次迭代时的候选项目集可由第k-1次迭代时找出的所有频繁(k-1)项目集之间通过连接运算得到。

此后，涌现出大量的apriori的改进算法。如利用hash表的DHP算法，基于采样的算法，并行关联规则算法，分布式关联规则算法，多层关联规则算法，数值扩展的关联规则算法，利用关联规则进行分类，具有条件的关联规则等等。由于典型的关联规则的算法会产生大量无意义的规则，因此出现了基于兴趣度的规则后处理算法。

[7]

§2.4.2 分类算法

分类算法具有相当多的方法。我们这里只讨论常见的几种算法：决策树、 AQ、 Bayes、SVM、神经网络和粗糙集等。

1． 决策树

决策树是最常用的一类分类算法。构造一个决策树分类器通常分为两步：树

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

的生成和剪枝。树的生成采用自上而下的递归分治法。如果当前训练例子集合中的所有实例是同类的，构造一个叶节点，节点内容即是该类别。否则，根据某种策略选择一个属性，按照该属性的不同取值，把当前实例集合划分为若干子集合。对每个子集合重复此过程，直到当前集中的实例是同类的为止。剪枝就是剪去那些不会增大树的错误预测率的分枝。经过剪枝，不仅能有效的克服噪声，还使树变得简单，容易理解。生成最优的决策树是NP问题（在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题，没有找到多项式时间算法解的一类问题，称之为NP类问题）。目前的决策树算法一般通过启发式属性选择策略来解决问题。

ID3 及其后续版本 C4.5，C4.5 是使用最为广泛的决策树方法。它采用信息熵增益及其改进增益率进行属性选择。增益率能克服增益偏向于多值属性特点。CART则采用基于最小距离的Gini index标准和为了克服Gini在处理很多类问题上的困难而做的改进twoing rule。事实上还有许多其他选择属性的方法，例如χ2统计，C-Sep，Impurity，MDL等等。

有些研究者对决策树在超大规模数据集中的应用作了研究，提出了一些扩展。如SLIQ，它采用预排序技术来克服将所有数据同时放入内存的方法，从而能处理更大的数据库，并用了MDL剪枝算法，使树更小和精度更高。SPRINT引入了并行算法的方式，具有良好的可扩展性[11]。

许多研究者对决策树方法进行了各种各样的扩展。如神经网络、模糊数学、概率论的结合，使用遗传算法对树的优化，新的属性选择算法，剪枝策略，树的增量算法，处理缺失值的方法等等。

2． AQ

目前已经提出大量的基于规则的分类方法，对规则进行后处理如剪枝等工作也做了大量研究。AQ是一种典型的基于规则的方法。在这里，我们将会简要讨论用 AQ方法构造决策树。

AQ是一种覆盖算法，由Micalski和洪家荣提出。算法的核心是所谓的“星”

[12]

。一个正例集合在反例集合背景下的星是覆盖所有正例而排斥所有反例的极大

复合的集合。算法就是要求得这样的最大复合。算法从正例中的一个种子的一个选择子（属性值对）出发，逐渐地增加选择子，直到找到覆盖所有正例的最大复合。在最初的AQ11基础上，AQ15增加了渐近学习，构造学习和近似推理等功能，成为比较成熟的覆盖算法。

为了改进星算法的效率，不进行复杂的逻辑推理，洪家荣提出了扩张矩阵的概念及相应的AE1，AE9算法。扩张矩阵把正例在反例之间的关系表示成矩阵，把

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

搜索最大复合的过程转换成在矩阵中找寻一条“最大公共路”的过程。并提出了相应的启发式搜索方法。后来吴信东在其博士论文中推广了扩充矩阵的概念，并提出一种改进算法 HCV。

3． Bayes方法

贝叶斯统计分析方法最早是由英国学者Bayes T.R.在他的一篇论文《An Essay towards solving a Problem in the Doctrine of Chances》中提出的，论文给出了著名的贝叶斯公式和一种归纳推理方法。其后一些统计学家将其发展成一种系统的统计推断方法，到本世纪30年代形成了贝叶斯学派，50～60年代发展成了一个有影响的统计学派。

贝叶斯方法的学习机制是利用贝叶斯公式将先验信息与样本信息综合，得到后验信息。在数据挖掘中，主要有两种Bayes方法，即Naive-Bayes方法和Bayes网络

[13]

。前者直接利用Bayes公式进行预测，把从训练样本中计算出的各个属性

值和类别频率比作为先验概率，并假定各个属性之间是的，就可以用Bayes公式和相应的概率公式计算出要预测实例的对各类别的条件概率值。选取概率值最大的类别作为预测值。此方法简单易行并且具有较好的精度。

Bayes网络是一个带有概率注释的有向无环图。这个图模型能有效地表示大的变量集合的联合概率分布(物理的或Bayes的)，从而适合用来分析大量变量之间的相互关系，利用Bayes公式的学习和推理功能，可以实现预测、分类等数据挖掘任务。因为关于变量组X的贝叶斯网络表示了X的联合概率分布，所以，一旦网络及其参数确定，原则上可以用它来推断任何感兴趣的概率。Bayes网络也是一种适合处理不确定性知识问题的知识表示方法，因为它可以从部分概率中进行推导。

构造Bayes网络需要进行网络结构和网络参数两部分的学习。为了建立Bayes网络，首先确定问题的变量组，接着通过对变量之间条件性的分析，建立一个表示这些变量之间的关系的有向无环图。最后需要对变量指派局部概率分布。在离散的情况下，需要为每一个变量的各个父节点的状态指派一个分布。但是获得最优的结构和参数都是NP问题。因此提出了许多启发式方法。

关于离散变量的任意Bayes网络的精确推断也是NP难题。即使是近似推断，例如使用Monte-Carlo方法也是NP难的。其主要原因是任意Bayes网络中存在环路（不考虑弧的方向），这使得推断难以实施。不过在许多实际应用中，只要网络结构足够简单，或者可以在不牺牲太多准确性的前提下将结构简化，则推理仍可有效地进行。

4． 神经网络

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

神经网络是一种很好的函数逼近工具，在过去十几年里取得了飞速的发展，提出了很多的模型及其改进，例如：BP、Hopfield、Kohonen、ART、RNN、KBANN、RBF等等。虽然试验表明，神经网络在某些分类问题上具有比符号方法更好的表现，但是神经网络用于数据挖掘主要不利之处在于无法获取显式的规则。近年来许多学者提出了从神经网络中提取规则的方法，典型的如KBANN等[14]。主要可以分为三类方法：分解法、学习法以及这两种的折衷方法。

分解抽取方法的最大特点是对神经元网络内部的单个节点（隐含和输出）所表示的概念进行解释，从每个节点中抽取的规则是由与此节点相连的诸输入节点来表示的，典型的分解算法有SUBSET及其改进 MOFN、KT和RULEX[16]。

学习抽取方法的基本思想是将训练后的神经元网络看成一个黑箱，而把规则抽取过程看成是一个学习过程，其中所学的目标概念由神经元网络函数计算得到，而其输入变量则为神经元网络的输入特征组成。学习抽取方法主要是利用符号学习算法作为学习工具，而利用神经元网络作为学习例子生成器，主要代表方法有TREPAN和RL算法。

[15]

§2.4.3 聚类分析

一般把学习算法分成有监督和无监督学习两种方式。主要区别是有没有类信息作为指导。聚类分析是典型的无监督学习算法，一般用于自动分类。

聚类分析是按照某个特定标准(通常是某种距离)把一个数据集分割成不同的类（Class），使得类内相似性尽可能的大，同时使得不同的类之间区别性也尽可能的大。直观的说，最终形成的每个聚类，在空间上都是一个稠密的区域。

聚类方法主要分为划分聚类、层次聚类、基于密度的聚类、基于网格的聚类和基于模型的聚类。在第三章将详细介绍这些聚类算法。

聚类方法具有广泛的应用。典型的如文档的聚类以及一些特定领域的成功应用。但是由于聚类是无导师的学习方法，其所研究的数据没有类别标签，我们很难判断得到的聚类划分是否反映了事物的本质。

[17]

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

随着数据仓库和数据挖掘技术的日益发展，数据挖掘技术研究目标主要集中在以下几点：

1． 处理不同类型数据

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

绝大多数数据库是关系型的，因此在关系数据库上有效地执行数据挖掘是至关重要的。但是在不同应用领域中存在着各种数据和数据库，而且经常包含复杂的数据类型，例如结构数据、复杂对象、事务数据、历史数据等。由于数据类型的多样性和不同的数据挖掘目标，一个数据挖掘系统不可能处理各种数据。因此针对特定的数据类型，需要建立特定的数据挖掘系统。

2． 数据快照和时间戳

现实数据库通常是庞大、动态、不完全、不准确、冗余和稀疏的，这给知识发现系统提出了许多难题。数据库中数据的不断变化造成先前发现的知识很快过时，利用数据快照和时间戳方法可解决这一问题。前者特别适用于阶段性搜索集的数据，但需要额外空间存储快照。数据的不准确性使知识挖掘过程需要更强的领域知识和更多的抽样数据，同时导致发现结果的不正确；不完全数据包括缺少单个记录的属性值或缺少关系的字段；重复出现的信息称为冗余信息，为避免将对用户毫无意义的函数发现作为知识发现的结果，系统必须了解数据库的固有依赖。另外数据的稀疏性和不断增加的数据量增加了知识发现的难度。

3． 数据挖掘算法的有效性和可测性

海量数据库通常有上百个属性和表及数百万个元组。GB量级数据库已不鲜见，TB量级数据库已经出现，高维大型数据库不仅增大了搜索空间，也增加了发现错误模式的可能性。因此必须利用领域知识降低维数，除去无关数据，从而提高算法效率。从一个大型数据库中抽取知识的算法必须高效、可测量，即数据挖掘算法的运行时间必须可预测，且可接受，指数和多项式复杂性的算法不具有实用价值。但当算法用有限数据为特定模型寻找适当参数时，有时会导致物超所值，降低效率[19]。

4． 交互性用户界面

数据挖掘的结果应准确地描述数据挖掘的要求，并易于表达。从不同的角度考察发现的知识，并以不同形式表示，用高层次语言和图形界面表示数据挖掘要求和结果。目前许多知识发现系统和工具都缺乏与用户的交互，难以有效利用领域知识，对此可以利用贝叶斯方法和数据库本身的演绎能力发现知识。

5． 在多抽象层上交互式挖掘知识

很难预测从数据库中会挖掘出什么样的知识，因此一个高层次的数据挖掘查询应作为进一步探查的线索。交互式挖掘时用户能交互地定义一个数据挖掘要求，深化数据挖掘过程，从不同角度灵活看待多抽象层上的数据挖掘结果。

6． 从不同数据源挖掘信息

局域网、广域网及Internet网将多个数据源联成一个大型分布、异构的数据

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

库，从包含不同语义的格式化和非格式化数据中挖掘知识是对数据挖掘的一个挑战。数据挖掘可以揭示大型异构数据库中存在的普通查询不能发现的知识。数据库的巨大规模、广泛分布及数据挖掘方法的计算复杂性，要求建立并行分布的数据挖掘[20]。

7． 私有性和安全性

数据挖掘能从不同角度、不同抽象层上看待数据，将影响到数据挖掘的私有性和安全性。通过研究数据挖掘导致的数据非法侵入，可改进数据库安全方法，以避免信息泄漏。

8． 和其他系统的集成

方法功能单一的发现系统的适用范围必然受到一定的。要在更广泛的领域发现知识，系统就应该是数据库、知识库、专家系统、决策支持系统、可视化工具、网络等技术的集成。

9． Internet上的知识发现

从WWW信息的海洋中可以发现大量的新知识，已有资源发现工具发现含有关键值的文本。Han等人提出利用多层次结构化方法，通过对原始数据的一般化，构造多层次的数据库。

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

§3.1 聚类分析的定义

聚类是人类一项最基本的认识活动。通过适当聚类，事物才便于研究，事物的内部规律才可能为人类所掌握。所谓聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小，类内相似性尽可能大[20,21,22]。聚类是一个无监督的学习过程，它同分类的根本区别在于：分类是需要事先知道所依据的数据特征，而聚类是要找到这个数据特征，因此，在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的基础。例如在商务中，聚类分析能够帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学中，聚类分析能用于推导植物和动物的分类，对基因进行分析，获得对种群中固有结构的认识。聚类分析也可以用于在泥土观测数据库中对相似地区的区分，也可以根据房子的类型、价值和地域对一个城市中的房屋进行分类。聚类分析也能用于分类Web文档来获得信息。作为数据挖掘的功能，聚类分析可以作为一个获得数据分布情况、观察每个类的特征和对特定类进

[23]

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

一步分析的工具。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。

一个能产生高质量聚类的算法必须满足下面两个条件: (1) 类内(intra-class)数据或对象的相似性最强； (2) 类间(inter-class)数据或对象的相似性最弱。

聚类质量的高低通常取决于聚类算法所使用的相似性测量的方法和实现方式，同时也取决于该算法能否发现部分或全部隐藏的模式。

[24]

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

许多基于内存的聚类算法选择两种有代表性的数据结构：数据矩阵和相异度矩阵

[20,25]

。

数据矩阵是一个对象-属性结构。它是由n个对象组成，如：人；这些对象是利用p个属性来进行描述的，如：年龄、高度、重量等。数据矩阵采用关系表形式或n×p矩阵来表示，如图3-1所示。

相异度矩阵是一个对象-对象结构。它存放所有n个对象彼此之间所形成的差异。它一般采用n×n矩阵来表示，如图3-2所示。

图3-1数据矩阵

图3-2相异度矩阵

其中d(i,j)表示对象i和对象j之间的差异（或不相似程度）。通常d(i,j)为一个非负数；当对象i和对象j非常相似或彼此“接近”时，该数值接近0；该数值越大，就表示对象i和对象j越不相似。由于有d(i,j)=d(j,i)且d(i,i)=0，因此就有上面所示三角矩阵。

在具体的应用中，我们可以根据聚类所采用的算法，选择一种适合该算法的数据矩阵形式。

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

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

聚类分析起源于统计学，传统的分析方法大多是在数值类型数据的基础上研究的。然而数据挖掘的对象复杂多样，要求聚类分析的方法不仅能够对属性为数值类型的数据进行，而且要适应数据类型的变化。一般而言，在数据挖掘中，对象属性经常出现的数据类型有：区间标度变量，二元变量，标称型、序数型和比例标度型变量以及混合类型的变量。

1． 区间标度变量

区间标度变量是一个粗略线性标度的连续度量。典型的例子则包括重量和高度，经度和纬度坐标，以及大气温度等。为了将数据或对象集合划分成不同类别，必须定义差异性或相似性的测度来度量同一类别之间数据的相似性和不属于同一类别数据的差异性。同时要考虑到数据的多个属性使用的是不同的度量单位，这些将直接影响到聚类分析的结果，所以在计算数据的相似性之前先要进行数据的标准化。

对于一个给定的有n个对象的m维(属性)数据集，主要有两种标准化方法[27]： 平均绝对误差Sp

Sp1nn[26]

|xi1ipmp|

这里xip表示的是第i个数据对象在属性p上的取值，mp是属性p上的平均值，即：

mp1nn

标准化度量Zp

xi1ip

ZpxipmpSp

|xipmp|这个平均的绝对误差Sp比标准差σp对于孤立点具有更好的鲁棒性。在计算平均绝对偏差时，属性值与平均值的偏差一定程度上被减小了。

数据标准化处理以后就可以进行属性值的相似性测量，通常是计算对象间的距离。对于n维向量xi和xj，有以下几种距离函数:

欧氏距离：

n没有平方，因此孤立点的影响在

D(xi,xj)||xixj||

(xk1ikxjk)2

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

曼哈顿距离：

nD(xi,xj)|xk1ikxjk|

m1/mn一般化的明氏(Minkowaki)距离：

k1Dm(xi,xj)[(xikxjk)]

当m=2时，明氏距离Dm即为欧氏距离；当m=1时，明氏距离马即为曼哈顿距离。 对于欧氏距离和曼哈顿距离满足以下条件： (i) D(xi,xj)0：距离是一个非负数值； (ii) D(xi,xj)0：对象与自身的距离是零； (iii) D(xi,xj)D(xj,xi)：距离函数具有对称性；

(iv) D(xi,xj)D(xi,xk)D(xk,xj)：xi到xj的距离不会大于xi到xk和xk到xj

的距离之和（三角不等式）。

2、二元变量

二元变量只有两个状态：0和1。其中二元变量又分为对称的二元变量和不对称的二元变量。前者是指变量的两个状态不具有优先权，后者对于不同的状态其重要性是不同的。

对于二元变量，度量两个变量的差异度由简单匹配系数（对称的情况）和Jaccard系数（非对称的情况）决定。设两个对象xi和xj，q是属性值在两个对象中都为1的属性个数，r是属性值在xi中为1而在xj中为0的属性个数，s是属性值在xi中为0而在xj中为1的属性个数，t是属性值在两个对象中都为0的属性个数。则简单匹配系数：

d(xi,xj)rsqrst

Jaccard系数:

d(xi,xj)rsqrs

3、标称型、序数型和比例标度型变量

标称变量是二元变量的推广，它可以有多个状态值，状态之间是无序的。具有这种数据类型的属性也称分类(categorical)属性。

它的差异度可用简单匹配法来计算：

d(xi,xj)pmp

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

其中，m是对象xi和xj中匹配的属性个数，而p是全部属性个数。

序数型变量类似于标称型变量，但它的各个状态是有意义的序列。比例标度型变量再非线性的标度取正的度量值，例如指数标度，近似遵循Ae或Ae中A，B是正常数。

4、混合类型的变量

以上讨论了各种数据类型和它们差异度的计算方法，在实际数据库中，对象是由混合类型的变量描述的。在实际聚类分析中，将不同的类型属性组合在同一个差异度矩阵中进行计算。设数据包含m个不同类型的属性，对象xi和xj之间的差异度定义为：

mBtBt，其

d(xi,xj)p1m(p)ijdij(p)p1(p)ij

(p)其中如果xip或缺失，或xip＝＝0，且变量是不对称二元变量，则指示项ij(p)ij＝0；否则＝1。

如果属性p是二元变量或标称变量：如果xip＝，

d(p)ijdij(p)＝0，否则，

dij(p)＝1。

|xip|maxh如果属性p是区间标度变量：属性p的所有数据对象。

xhpminhxhp，这里的h取遍具有非空

如果属性p是序数型或比例标度型变量：将其转化为区间标度变量值对待。

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

目前存在着大量的聚类算法，算法的选择取决于数据的类型、聚类的目的和应用。从总体上来看，聚类算法可以分为串行算法和并行算法两类[28]。

§3.4.1 串行聚类算法

目前采用的聚类算法大都属于串行算法，我们分别研究其算法思想、聚类效果。

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

§3.4.1.1 划分方法（partitioning method）

给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚簇，并且k≤n[29]。也就是说，它将数据划分为k个组，同时满足如下的要求：（a）每个组至少包含一个对象；（b）每个对象必须属于且只属于一个组。但在某些模糊划分技术中第二个要求可以放宽。

划分方法首先根据给定要构建划分的数目k创建一个初始划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是：在同一类中的对象之间尽可能“接近”或相关，而不同类中的对象之间尽可能“远离”或不同。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方法：（a）K-平均（K-MEANS）算法，在该算法中，每个簇用该簇中对象的平均值来表示。（b）K-中心点（K-MEDOIDS）算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。下面详细介绍这两种算法。

1． K-means算法

K-means算法首先随机选择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。然后，计算每个聚类的新质心。重复上述过程，直到准则函数会聚。通常采用的准则函数是平方误差准则函数。

K-means聚类算法的具体步骤如下：

1) 从数据集中选择k个质心C1，C2，„ ，Ck作为初始的聚类中心；

2) 把每个对象分配到与之最相似的聚合。每个聚合用其中所有对象的均值来代表，“最相似”就是指距离最小。对于每个点Vi，找出一个质心Cj，使它们之间的距离d(Vj，Cj)最小，并把Vi分配到第j组；

3) 把所有的点都分配到相应的组之后，重新计算每个组的质心Cj； 4) 循环执行第2)步和第3)步，直到数据的划分不再发生变化。

该算法具有很好的可伸缩性，其计算复杂度为O(nkt)，其中，t是循环的次数。K-means聚类算法的不足之处在于它要多次扫描数据库，此外，它只能找出球形的类，而不能发现任意形状的类。还有，初始质心的选择对聚类结果有较大的影响，该算法对噪声很敏感。

2． K-medoids算法

K-medoids算法的过程和上述k-means的算法过程相似，唯一不同之处是：k-medoids算法用类中最靠近中心的一个对象来代表该聚类，而k-means算法用质

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

心来代表聚类。在k-means算法中，对噪声非常敏感，因为一个极大的值会对质心的计算带来很大的影响。而k-medoid算法中，通过用中心来代替质心，可以有效地消除该影响。

K-medoids算法首先随机选择k个对象，每个对象代表一个聚类，把其余的对象分别分配给最相似的聚类。然后，尝试把每个中心分别用其他非中心来代替，检查聚类的质量是否有所提高。若是，则保留该替换。重复上述过程，直到不再发生变化。

常见的k-medoids算法有PAM(Partitioning Around Medoids)算法、CLARA(Clustering LARge Application)算法、CLARANS(Clustering LARge Application based upon Randomized Search)算法。当存在“噪声”和孤立点数据时，k-medoids算法比可k-means更健壮，这是因为中心点不像平均值那么容易被极端数据影响。但是，k-medoids算法的执行代价比k-means高。

总之，划分方法具有线性复杂度，聚类的效率高的优点。然而，由于它要求输入数字k确定结果簇的个数，并且不适合于发现非凸面形状的簇，或者大小差别很大的簇，所以这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。

§3.4.1.2 层次方法（hierarchical method）

层次方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和的[30]。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件。的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中，在迭代的每一步中，一个簇被为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。

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

凝聚的

的

图3-3 在数据对象集合{a,b,c,d,e}上的凝聚和层次

让我们看一个图就可以理解，层次聚类方法。图3-3描述了一个凝聚的层次聚类方法AGNES(Agglomerative NESting) 和一个的层次聚类方法DIANA（Divisive ANAlysis）在一个包含五个对象的数据集合{a,b,c,d,e}上的处理过程。最初，AGNES将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。在DIANA方法的处理过程中，所有的对象初始都放在一个簇中。根据一些原则（如簇中最临近对象的最大欧式距离），将该簇。簇的过程反复进行，直到最终每个新的簇只包含一个对象。

主要的凝聚聚类算法有CURE,CHAMELEON,BIRCH,ROCK等。下面逐一介绍。 1．BIRCH算法

BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)算法使用了一种叫做CF-树(聚类特征树，即Clustering Feature Tree)的分层数据结构，来对数据点进行动态、增量式聚类。CF-树是存储了层次聚类过程中的聚类特征信息的一个加权平衡树，树中每个节点代表一个子聚类，并保持有一个聚类特征向量CF。每个聚类特征向量是一个三元组，存储了一个聚类的统计信息。聚类特征向量CF{N,LS,SS}中包含了一个聚类的三个统计信息：数据点的数目N，这N个数据点的线性和LS，以及这N个数据点的平方和SS。一个聚类特征树是用于存储聚类特征CF的平衡树，它有两个参数：每个节点的最大子节点数和每个子聚类的最大直径。当新数据插入时，就动态地构建该树。与空间索引相似，它也用于把新数据加入到正确的聚类当中。

BIRCH算法的主要目标是使I/0时间尽可能小，原因在于大型数据集通常不能完全装入内存中。BIRCH算法通过把聚类分为两个阶段来达到此目的。首先通过构建CF-树对原数据集进行预聚类，然后在前面预聚类的基础上进行聚类。该算法的具体过程如下：

1) 预聚类(precluster)阶段：扫描整个数据库，构建初始聚类特征树，该树保存在内存中，用简洁的汇总信息或者叶子节点中的子聚类(subcluster)来代表

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

数据点的密集区域。

2) (可选阶段)重新扫描叶子节点项，来构建一个更小的CF-树。通过本阶段，可以去除噪声，并从子聚类中得到相对较大的聚类。

3) 采用别的聚类算法，对CF-tree的叶子节点进行聚类。它使用现有的基于质心的聚类算法或者现有算法的改进形式，把每一个子聚类当作一个单一的数据点，对叶子节点的子聚类进行聚类。BIRCH算法需要用户输入参数，如期望得到的聚类数目或者聚类的期望大小阀值(半径或直径)。

4) (可选阶段)把前一个阶段中找到的聚类的质心，用作种子来创建最终的聚类。其他数据点根据到这些种子所代表聚类的远近来重新分配到各个聚类中。该阶段还可以用于减少噪声数目。

以上各阶段中，第2)、4)阶段是可选的，它们用来实现聚类过程的优化。 建造CF-树的过程相当于一种预处理，大大减少了总的数据处理量，提高了算法的处理速度。BIRCH算法只对原数据集进行一次初始扫描，所以其计算复杂度是O(N)。不过，这是在N>>K的前提下得到的，其中K是子聚类的数目。当K接近于N时，复杂度就变成O(N2)，因此，在第一阶段中选择合适的阀值是非常必要的。BIRCH的主要缺点之一就是在初始扫描完成之后，它使用基于质心的方法来形成聚类，当聚类的形状不同或大小各异的情况下，就容易出现问题。此外，该算法采用直径作为控制参数，所以当类的形状非球形或不同大小的类时，聚类效果不佳。还有，该算法对数据的输入顺序很敏感，还需要用户手工设置一些参数。

2．CURE算法

CURE(Clustering Using Representative)算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。针对大型数据库，CURE采用随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分再被部分聚类。该算法的具体过程如下：

1) 源数据对象中抽取一个随机样本S； 2) 将样本S分割为一组划分； 3) 4)

对每个划分局部地聚类；

通过随机取样剔除孤立点。如果一个簇增长的太慢，就去掉它；

5) 对局部的簇进行聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子α收缩或向簇中心移动。这些点代表和捕捉到了簇的形状；

6) 用相应的簇标签来标记数据。

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

CURE算法中每个簇有多于一个的代表点，使得CURE可以适应非球形的几何形状；该算法对孤立点的处理更加健壮，而且能够识别非球形和大小变化较大的簇；CURE的复杂性为O(n)。但是，该算法从源数据对象中抽取一个随机样本S，基于对此样本的划分进行聚类，如果抽取的样本发生倾斜，则会严重影响聚类结果[41]。

3．ROCK算法

CURE算法不能处理枚举型数据，而ROCK算法是在CURE基础之上适用于枚举数据的聚结分层聚类算法。通过把两个聚类的聚集相互连接度(aggregate interconnectivity)与用户定义的静态相互连接模型相比较，从而度量两个聚类之间的相似度。其中，两个聚类的相互连接度是指两个聚类之间的交叉连接数目，而连接link(pi,pj)是指这两点之间的共同邻居数。换句话说，聚类相似度是用不同聚类中又共同邻居的点的数目来确定的。

ROCK算法首先用相似度阀值和共同邻居的概念，从给定的数据相似度矩阵中构建一个稀疏图，然后对该稀疏图使用分层聚类算法进行聚类。

4．Chameleon算法

Chameleon（变色龙）是一个利用动态模型的层次聚类算法。算法思想是：首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。它既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子簇[31]。

Chameleon跟CURE和DBSCAN相比，在发现高质量的任意形状的聚类方面有更强的能力。但是，在最坏的情况下，高维数据的处理代价可能对n个对象需要O(n)的时间。

总的来说，层次的方法的缺陷在于，一旦一个步骤（合并或）完成，它就不能被撤消，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：（a）在每层划分中，仔细分析对象间的“联接”，例如CURE中的做法。（b）综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。

2

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

绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域

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

中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。常见的基于密度的聚类算法有DBSCAN,OPTICS,DENCLUE等。

1．DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一个基于高密度连接区域的密度聚类方法。DBSCAN通过检查数据库中每个点的ε-邻域来寻找聚类。如果一个点p的ε-邻域包含多于MinPts个点，则创建一个以p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。具体过程如下：

DBSCAN(D, Eps, MinPts)

//input: D:数据对象集合，Eps:邻域或称为半径，MinPts:密度阈值 1) 读取D中任意一个未分类的对象o；

2) 检索出与o的距离不大于Eps的所有对象Neps(o)；

3) 如果|Neps(o)|4) 否则（即o为核心对象），给Neps(o)中的所有对象打上一个新的类标签newid，然后将这些对象压入堆栈的Seeds

中；

5) 让CurrentObject = Seeds.top；然后检索属于Neps(CurrentObject)的所有对象；如果|Neps(CurrentObject)|>MinPts，

则剔除已经打上标记的对象，将余下的未分类对象打上类标签newid，然后压入堆栈； 6) Seeds.pop，判断Seeds是否为空，是，则执行步骤1)，否则执行步骤5)。

从上面的算法中可以分析得到，DBSCAN算法不仅可以发现任意形状的聚类，对数据输入顺序不敏感，并且具有处理异常数据（噪音）的能力。但是，该算法对用户定义的参数是敏感的，而参数的恰当选择是需要有相关经验的；同时，该算法的时间复杂性是O(n2)，用这种复杂度的算法聚类大型数据库是不太现实的，如果采用空间索引，基于R*-树的DBSCAN算法的复杂性为O(n.logn)，是相当高效的，此时是忽略建立索引的时间，而建立索引通常需要消耗大量的时间。

2． OPTICS算法

OPTICS(Ordering Points To Identify the Clustering Structure)通过对象排序识别聚类结构。OPTICS没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇次序（cluster ordering）。这个次序代表了数据的基于密度的聚类结构。它包含的信息，等同于从一个宽广的参数设置范围所获得的基于密度的聚类。也就是说，对于一个恒定的参数MinPts值，可以同时处理一组距离参数值。

OPTICS在选择参数方面具有比DBSCAN较高的灵活性，在采用空间索引时，复

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

杂度为O(nlogn)，和DBSCAN时间复杂度相同。但是，它需要额外的空间存储每个对象的核心距离和一个适当的可达距离。

3． DENCLUE算法

DENCLUE(DENsity based CLUstEring)是一个基于一组密度分布函数的聚类算法。它是对k-means聚类算法的一个推广：k-means算法得到的是对数据集的一个局部最优划分，而DENCLUE得到的是全局最优划分。

该算法主要基于下面的想法：

（1） 每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一

个数据点在邻域内的影响，被称为影响函数（influence function）；

（2） 数据空间的整体密度可以被模型化为所有数据点的影响函数的总和； （3） 然后聚类可以通过确定密度吸引点（density attractor）来得到，这

里的密度吸引点是全局密度函数的局部最大。

DENCLUE算法有一个坚实的数学基础，概括了其他的聚类方法，包括基于划分的、层次的、及基于位置的方法；同时，对于有大量“噪声”的数据集合，它有良好的聚类特征；对于高维数据集合的任意形状的聚类，它给出了一个基于树的存储结构来管理这些单元，因此比一些有影响的算法（如DBSCAN）速度要快。但是，这个方法要求对密度参数σ和噪声阈值ξ进行仔细的选择，如果选择不当则可能显著地影响聚类结果的质量。

[32]

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

基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构（即量化的空间）上进行。基于网格的聚类算法主要有STING, WaveCluster, CLIQUE等。

1．STING算法

STING(Statistical Information Grid-based method)是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。这些统计信息用于回答查询。

STING有几个优点：（i）由于存储在每个单元中的统计信息提供了单元中的数据不依赖于查询的汇总信息，所以基于网格的计算是于查询的；（ii）网格结构有利于并行处理和增量更新；（iii）该方法的主要优点是效率很高：STING扫描

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

数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O(n)，其中n是对象的数目。在层次结构建立后，查询处理时间是O(g)，这里g是最低层网格单元的数目，通常远远小于n。该算法的缺点：由于STING采用了一个多分辨率的方法进行聚类分析，STING聚类的质量取决于网格结构的最低层的粒度。如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的力度太粗，将会降低聚类分析的质量；而且，STING在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是isothetic，即所有的聚类边界或者是水平的，或者是竖直的，没有对角的边界。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性。

2． WaveCluster算法

WaveCluster(Clustering with Wavelets)采用小波变换聚类，它是一种多分辨率的聚类算法，它首先通过在数据空间上加一个网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换后的空间中找到密集区域。

WaveCluster的计算复杂度是O(n)，能有效地处理大数据集合；发现任意形状的簇；成功地处理孤立点；对于输入的顺序不敏感；不要求指定诸如结果簇的数目或邻域的半径等输入参数；在实验分析中，WaveCluster在效率和聚类质量上优于BIRCH，CLARANS和DBSCAN；实验分析也发现WaveCluster能够处理多达20维的数据。但是，对数学建模的知识要求较高[33]。

3． CLIQUE算法

CLIQUE(Clustering In QUEst)算法综合了基于密度和基于网格的聚类方法,它的中心思想是:首先，给定一个数据点的集合，数据点在数据空间中通常不是均衡分布的。CLIQUE区分空间中稀疏的和“拥挤的”区域（或单元），以发现数据集合的全局分布模式。接着，如果一个单元中的包含数据点超过了某个输入模型参数，则该单元是密集的。在CLIQUE中，簇定义为相连的密集单元的最大集合。

CLIQUE算法能自动发现最高维中所存在的密集聚类；它对输入数据元组顺序不敏感；也不需要假设（数据集中存在）任何特定的数据分布；它与输入数据大小呈线性关系；并当数据维数增加时具有较好的可扩展性。但是，在追求方法简单化的同时往往就会降低聚类的准确性。

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

基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。

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

它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类方法。基于模型聚类方法主要有两种：统计学方法和神经网络方法。

1．统计学方法

机器学习中的概念聚类就是一种形式的聚类分析。给定一组无标记数据对象，它根据这些对象产生一个分类模式。与传统聚类不同，后者主要识别相似的对象；而概念聚类则更进一步，它发现每组的特征描述；其中每一组均代表一个概念或类，因此概念聚类过程主要有两个步骤：首先完成聚类；然后进行特征描述。因此它的聚类质量不再仅仅是一个对象的函数；而且还包涵了其它因素，如所获特征描述的普遍性和简单性。

大多概念聚类都采用了统计方法，也就是利用概率参数来帮助确定概念或聚类。每个所获得的聚类通常都是由概率描述来加以表示。

COBWEB是一种流行的简单增量概念聚类算法。它的输入对象用分类属性-值对来描述。它以一个分类树的形式创建层次聚类。分类树的每个节点对应一个概念，包含该概念的一个概率描述，概述被分在该节点下的对象。在分类树某个层次上的兄弟节点形成了一个划分。为了用分类树对一个对象进行分类，采用了一个部分匹配函数沿着“最佳”匹配节点的路径在树中向下移动。寻找可以分类该对象的最好节点。这个判定基于将对象临时置于每个节点，并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点一个好的选择。但如果对象不属于树中现有的任何概念，则为该对象创建一个新类。

CORWEB的优点在于：他不需要用户输入参数来确定分类的个数，它可以自动修正划分中类的数目。缺点是：首先，它基于这样一个假设：在每个属性上的概率分布是彼此的。由于属性间经常是相关的，这个假设并不总是成立。此外，聚类的概率分布表示使得更新和存储类相当昂贵。因为时间和空间复杂度不只依赖于属性的数目，而且取决于每个属性的值的数目，所以当属性有大量的取值时情况尤其严重。而且，分类树对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化。

2．神经网络方法

神经网络聚类方法是将每个簇描述成一个标本。标本作为聚类的一个“原型”；它不一定对应一个特定的数据实例或对象。可以根据新对象与哪个标本最相似（基于某种距离计算方法）而将它分派到相应的聚类中。可以通过聚类的标本来预测分派到该聚类的一个对象的属性。上一章对此已经作了详细描述，这里不再详述。

[34]

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

§3.4.2并行聚类算法

聚类算法中的另一大分支是并行聚类算法。数据挖掘并行聚类算法和数据挖掘串行算法的研究几乎是同时进行的。这是因为数据挖掘的兴起正是因为数据量过大，超出了人们可以“手工”处理的范围，随着数据量的增多计算量也会超出一台计算机的存储能力和计算能力。所以，并行数据挖掘从数据挖掘研究伊始就成为一个重要的研究课题。

对于并行算法而言，由于数据量非常庞大，通常情况下，数据挖掘算法对内存和硬盘的需求非常大。特别是对内存的需求，经常会出现内存不能一次装载所需的数据，需要备用存储设备的情况，此时如果处理不好就会严重降低算法的性能。开发数据挖掘并行方法有两种途径[35]：其一是对已有的串行算法进行改进，挖掘其中的并行性质并加以利用，使得串行程序并行化；其二是对问题的本质重新审视，设计全新的并行算法。第一种途径相对容易一些，但是并行粒度较小，通信量较大。第二种途径需要全新设计，但如果成功，就会得到粗粒度并行算法，适合于在分布式并行机上应用。其实，数据挖掘算法天生就具有丰富的并行性能。但是，对于给定的串行算法，却很难找到一个理想的并行化方案，硬件特征和问题的性质对于并行化有重要影响。几乎所有的数据挖掘算法以组合最优化过程为特征，其模型建立以训练集上的启发式贪婪搜索为基础。

在数据挖掘算法中有两种形式的并行性质：任务并行和数据并行。对于任务并行，计算模型被划分到各个处理器中，并分别计算模型的一部分，然后再同其它处理器通过消息通信等方式进行协调，以得到一个全局模型。其实，这里的“任务并行”就是“串行程序并行化”。负载均衡可能是任务并行关注的主要问题[36]。对于数据并行，训练集首先被划分到各个处理器中（或者数据集本身就是分布式存储的），然后各个处理器同时工作，建立各自的局部模型。最后各个局部模型被整合为一个全局模型。其实，这里的“数据并行”就是“分布式并行”[37]。

§3.5 设计聚类算法的准则

通过上面对聚类算法的分析，我们可以看出各种算法各自有其优点和不足，我们究竟应当本着怎样的原则进行算法设计呢？聚类作为数据挖掘中的重要的一个环节，已经形成了一些准则，我们在设计聚类算法时，应当以下列准则来规范自己的算法[38]：

 可伸缩性：许多聚类算法在小于200个数据对象的小数据集合上工作得很

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

好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进聚类可能会导致有偏差的结果。我们需要具有高度可伸缩性的聚类算法。

 处理不同类型属性的能力：由于数据库中数据类型不可能是单一的某一

种，所以算法应当被设计的能够聚类各种类型数据。

 发现任意形状的聚类：许多聚类算法基于欧几里得距离或者曼哈坦距离度

量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。

 用于决定输入参数的领域知识最小化：许多聚类算法在聚类分析中要求用

户输入一定的参数，例如产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说，更是如此。要求用户输入参数不仅加重了用户的负担，也使得聚类的质量难以控制。

 处理噪声数据的能力：绝大多数现实世界中的数据库都包含了孤立点，空

缺，未知数据或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。

 对于输入记录的顺序不敏感：一些聚类算法对于输入数据的顺序是敏感

的。例如，同一个数据集合，当以不同的顺序提交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。

 高维性:一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算

法擅长处理低维的数据，可能只涉及两到三维。人类最多在三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的，特别是考虑到这样的数据可能非常稀疏，而且高度偏斜[39]。  基于约束的聚类：现实世界的应用可能需要在各种约束条件下进行聚类。

假设你的工作是在一个城市中为给定数目的自动提款机选择安放位置。为了做出决定，你可以对住宅区进行聚类，同时考虑如城市的河流和公路网，每个地区的客户要求等情况。要找到既满足特定的约束，又具有良好聚类特性的数据分组是一项具有挑战性的任务[40]。

 可解释性和可用性：用户希望聚类结果是可解释的，可理解的，和可用的。

也就是说，聚类可能需要和特定的语释和应用联系。应用目标如何影响聚类方法的选择也是一个重要的研究课题。

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

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

§4.1 算法思想的形成过程

通过对现有的大量聚类算法进行了仔细的分析，分析每种算法的优缺点，根据上面提到的对聚类算法的评价标准，选择一种较好的聚类算法雏形，研究并发现该雏形的技术瓶颈，研究如何改进该算法成为形成算法思路的关键。最终，提出了基于密度和层次的快速聚类算法。下面以对一个好的聚类算法所应追求层面的理解为顺序，描述新算法的形成。

首先，一个聚类算法应该能发现任意形状的簇。因为，聚类其实就是将数据对象分组成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。而相关的数据不可能在映射到聚类的结果簇中时正好是很规整的圆形或方形。这时，我们如果非要用圆圈或方格把数据套在里面，说落在一个圆圈或方格里的数据是相似的（联系紧密的），这是不客观的。事实上，聚类的结果可能是任何形状、不以我们的意志为转移的，我们所应作的工作就是设计好的算法去反映这样的客观事实，而不是通过一些不好的算法得出的结果反推事实的“”。

基于密度的聚类方法能够发现任意形状的聚类结果，这类方法将簇看作是数据空间中被低密度区域分割开的

高密度对象区域。从上一章我们得知，基于密度的DBSCAN算法通过检查数据库中每个点的ε-邻域来寻找聚类。如果一个点p的ε-邻域包含多于MinPts个点，则创建一个以p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。必须承认DBSCAN算法是一种较好的聚类算法，因为，首先它可以发现任意形状的聚类，对数据输入顺序不敏感，并且具有处理异常数据（噪音）的能力。但是，该算法的时间复杂性是O(n2)，用这种复杂度的算法聚类大型数据库是不太现实的；如果采用空间索引，基于R*-树的DBSCAN算法的复杂性为O(n.logn)，是相当高效的。但是，DBSCAN算法没有考虑建立索引的时间，而建立索引通常需要消耗大量的时间[42]。

所以，能够在这个有很好聚类效果的算法基础上对其执行效率作进一步改进，是非常有意义的。

其次，一个聚类算法在处理大数据集时，应该具有可伸缩性和高效性。因为数据挖掘的目的是从海量的数据中提取信息知识，这里的数据不是仅仅包含几百个数据对象的小数据集，而可能是包含几百万个数据对象的大数据集。如果一个聚类算法只能在小数据集上工作得很好，那么它不是一个好的聚类算法。

在形成聚类的形状和排除孤立点时DBSCAN算法是针对所有点进行筛选的。这

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

就意味着对于一个大的数据集来说，对每个点都要分析其ε-邻域内是否包含MinPts个对象，确认其为核心对象后，再寻找它的直接密度可达对象，进行簇的合并。

能不能首先从n个数据点中选出m（m<于是可以借鉴凝聚的层次聚类CURE算法。CURE算法是一种新颖的层次聚类算法，它选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。所以，我们可以考虑，使用CURE形成代表点的思想来形成DBSCAN算法所需要的m(m<然而，针对大型数据库，CURE采用随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分都被部分聚类[44]。这样，代表点是来自一组随机抽取的样本集，而且它的最初数目也是人为确定的，这是需要改进的地方。

那么怎样选取代表点呢？所有的数据点都要参与这个过程，可以考虑基于一个距离值（半径）来确定各个点是否属于同一个集合，即是否拥有共同的代表点。属于同一个集合的数据点的坐标的中心即为代表点的坐标，代表点是一些虚构的点，主要反映一个集合中数据的总体相对位置。而且代表点的数目并非人为确定，而是自动产生。这样要比人为指定代表点和确定代表点的数目要好的多。

尽管这样选取代表点比CURE算法中的选取代表点的方法好了很多，但是经过对数据的一遍扫描并不能很可观的确定代表点的位置。这一点从K-means算法中得到一些启示。

K-means算法是一种划分方法，它以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而簇间的相似度较低。相似度的计算根据一个簇中对象的平均值（或中心点）来进行。上一章详细介绍了它的算法。

K-means算法中确定中心点的过程是值得借鉴的。我们可以多次扫描数据集，根据点与点之间的距离是否小于等于某一个值（半径）来确定它们是否属于同于集合，属于同一集合的点的坐标的平均值即为该集合代表点的坐标，代表点为虚构的点。第一次扫描完毕产生许多候选代表点，保留这些代表点，作为第二次扫描整个数据集的输入条件。将上面的过程重复几次，就可以保证所输出的代表点集合能够较为客观的表示空间数据的分布情况，它们就最终被确定为整个数据集

[43]

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

的代表点集合。

此外，K-means算法的复杂度是O(nkt)，其中，n是所有对象的数目，k是簇的数目，t是迭代的次数。通常地，k<§4.2 基于密度和层次的快速聚类算法的思想

经过上面的分析，我们头脑中原先比较模糊的概念渐渐的清晰，形成了新算法的轮廓。

从该算法的框架来看，采用了基于层次的聚类算法。从实现过程来看，整个算法分两步来完成。首先，在面对所有的数据点，以效率为瓶颈的地方，采用了目前速度最快的聚类算法K_平均算法，从而使得整个算法的时间复杂性不会很高，并通过对K_平均算法改进，摒弃了该算法的不利因素；第二步，在对代表点进行簇的划分时，聚类效果是这里的瓶颈，我们采用DBSCAN这样一种聚类效果很好的算法。从理论上看，这个基于密度和层次的聚类算法是可行的。

接着，根据第三章提到的衡量聚类算法的标准，我们来分析一下新算法的可行性：

首先，在寻找候选代表点，对整个数据集合进行扫描时，通过分析数据点之间的相对距离以及相对稠密程度，来确定代表点的坐标，这与数据的输入顺序是没有关系的，因此，实现了良好聚类的标准：数据输入顺序对聚类结果的不敏感性；

其次，在将代表点划分为不同聚类的簇时，采用密度阈值来分析每个代表点与周围点的紧密程度，从而将低于阈值要求的代表点视为孤立点，将其排除掉，因此，它达到了标准：能处理异常数据的能力；

第三，该算法对代表点采用基于密度的方法进行簇的划分，因此达到了标准：发现任意形状的聚类的能力；

第四，由于依据数据点寻找候选代表点，以及依据密度阈值判断代表点的相对稠密时，采用距离度量的方式，因此达到了标准：处理高维数据的能力；

第五，该算法采用了层次聚类，因此，在处理大型数据库时会具有良好的伸缩性；

第六，任意类型的数据都可以映射到数字0和1之间，都可以用于度量数据之间的距离，因此，该算法达到标准：处理不同数据类型的能力。

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

§4.3 算法相关的基本概念

基于密度和层次的快速聚类算法的基本思想涉及一些新的定义。我们先给出这些定义，然后再详细描述算法。

 点的密度: 对空间中任意点p和距离Radius，以p点为中心，半径为

Radius的区域内的点的个数称为点p基于距离Radius的密度(density)，记作Density(p，Radius)。

 代表点: 对空间中任意点p、距离Radius和阈值t，如果满足Density(p，

Radius)>=t，则称p为代表点(reference)，同时我们称t为密度阈值(density threshold)。

代表点不是实际输入数据中的点，而是虚拟的点或称为假想点。

 代表区域: 每个代表点代表了以该点为圆心、半径为Radius的圆形区域，

我们称该区域为代表点的代表区域(representing region)。

 邻接代表点: 给定距离Radius和阈值t，如果代表点p，q满足Distance

(p，q)<=2·Radius，即p和q之间的距离小于或等于2倍的Radius，则称p，q为邻接代表点(neighboring references)。

实际上，如果两个代表点的代表区域相切、相交或重合(圆心距离小于或等于半径之和)，那么这两个代表点就是邻接代表点。

§4.4 算法描述

在本节中，我们将详细介绍基于密度和层次的快速聚类算法。空间与二维空间的距离计算相似，为了方便地描述算法，在本文中以二维空间为例来分析基于密度和层次的聚类算法。

本算法采用的是凝聚的层次聚类方法，即自底向上的方法。该凝聚过程由三层组成，如图4-1所示。最底层所有的数据对象被视为各自处于一个簇中，作为该算法的输入参数。我们将整个数据集中的数据凝聚为以候选代表点为中心的一个个集合，并通过密度阈值筛选，去掉一些过稀疏的候选代表点，如图中代表集和“ab”的代表点，留下的代表点即为排除孤立点的中间层聚类结果。最高层，也就是最终的聚类结果层，它是在中间层的基础上，将邻接代表点聚类形成的簇，一个簇中由多于一个的代表点构成，使得它能够适应非球形的几何形状。

算法的整体框架如图4-2所示。

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

数据点集 扫描数据点集，确定候选代表点 筛选候选代表点，确定代表点 确定代表点代表区域内的点集 对代表点进行簇的划分 将代表点的聚类划分映射到数据点 聚类结果 图4-2 基于密度和层次的快速聚类算法 该算法分为五步：

1. 用改进的K_平均算法确定候选代表点； 2. 以密度阈值筛选候选代表点，确定代表点； 3. 确定代表点代表区域内的点集； 4. 用DBSCAN算法对代表点进行簇的划分； 5. 将代表点的聚类划分映射到数据点。

图4-1基于密度和层次的聚类算法结构

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

§4.4.1 数据结构

数据点的数据结构: class Point {

}

其中，pk代表该数据在数据库中的主键，用于唯一地标示数据。x、y分别表示该数据点第一维和第二维的坐标。其中重载的方法distance一个用于计算该数据点与其它数据点之间的距离，另一个用于计算数据点与代表点之间的距离，以便确定代表点代表区域内的点集。另外需要说明，表示数据点的类Point存放在一个一维数组PointSet中,通过访问数组中的每个元素，就可以得到每个数据点的信息。在扫描数据点时，就是从数组中提取信息。

代表点的数据结构： class Reference {

float xm; float ym; float xs; string pk; float x; float y;

public float distance(class Point) { }

public float distance(class Reference) { }

float d;

d=abs(x-Reference.xm)+abs(y-Reference.ym); return d;

d=abs(x-Point.x)+abs(y-Point.y); return d;

float d;

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

}

float ys; int

ns;

ArrayList ps; int clflag; public Reference() {

clflag=0; } { }

d=abs(xm-Reference.xm)+abs(ym-Reference.ym); return d;

public float distance(class Reference) float d;

其中：xm表示代表点的x坐标，ym表示代表点的y坐标；xs表示代表点代表区域内的所有点的x坐标之和，ys表示代表点代表区域内的所有点的y坐标之和；ns表示代表点代表区域内点的总数，在算法中将要用这个参数来表示代表点的密度；ps是一个集合的实例，表示代表点代表区域内的点的集合；clflag是在对代表点进行簇的划分时，用于标记该代表点被划分在第几个簇中。其中方法distance用于对代表点进行簇的划分时计算各个代表点之间的距离，如果两个代表点的距离小于或等于2倍的Radius则他们为邻接代表点，即它们处于同一簇中。

§4.4.2 确定候选代表点集合

多次扫描数据点集，寻找候选代表点的过程(如图4-3所示)。 Finding_Candidate_References (PointSet， dRadius){ //Input: data set: PointSet， distance: dRadius

//Output: candidate reference set: CandidateReferenceSet Begin

Step 1. CandidateReferenceSet= Ø，CandidateReferenceSet1= Ø，flag=false

Step 2. Single_Scan (PointSet， dRadius， CandidateReferenceSet)

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

Step 3. While (!flag) {

Step 4. CollectionCopy(CandidateReferenceSet)

Step 5. Regenerate_Candidate_References(CandidateReferenceSet) Step 6. Single_Scan (PointSet， dRadius， CandidateReferenceSet) Step 7. Compare(CandidateReference,CandidateReference1)} End

图4-3 Finding_Candidate_References过程

从图4-3可以看出，生成候选代表点（Finding_Candidate_References）的过程实际上是对CollectionCopy过程、Regenerate_Candidate_Reference 过程、Single_Scan过程和Regenerate_Candidate_References过程的反复调用。因为，对代表点的选择不是一步到位的，必须经过多次扫描数据点集，每一次扫描都要参考上一次扫描后产生的代表点集，然后在这次循环中还要纠正代表点的位置，每循环一次都趋向于产生更加能够准确表示输入数据空间几何特征的候选代表点集。

其中输入参数为：数据点构成的数组：PointSet；给定的距离度量值dRadius。Single_Scan过程完成对整个数据点集的一次扫描，将数据点分别放在不同代表点的代表区域内，并输出本次扫描所确定的候选代表点的集合。该候选代表点集合存放在CandidateReferenceSet中。

过程Compare将本次扫描所确定的代表点的坐标与上次扫描所确定的代表点的坐标一次作比较，如果有不同则返回值false，否则，就认为扫描过程可以结束，返回值true,这样确定候选代表点的循环结束。

过程CollectionCopy的功能是完成集合之间的复制。将当前扫描结束后的候选代表点集合CandidateReferenceSet复制一分放在集合CandidateReferenceSet1中。

Regenerate_Candidate_References过程修改代表点集合中每个代表点的相关信息，作为下一次扫描时的初始值。

每次调用Single_Scan过程都会产生新的候选代表点集，其主要操作是将点p的坐标信息加入到候选代表点集中。如果点p与所有的候选代表点的距离都大于Radius，则生成一个新的候选代表点;否则将点p的坐标信息加入到所有与点p距离小于等于Radius的候选代表点，如图4-4所示。

Single_Scan (PointSet， dRadius， CandidateReferenceSet)

//Input: data set: PointSet， distance: dRadius， candidate reference

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

set: CandidateReferenceSet

//Output: candidate reference set: CandidateReferenceSet Begin Step 1. i=1

Step 2. While (i<=PointSet.Length) { Step 3. Foreach Pi in PointSet:

Adding Pi’s information to every candidate reference R， whose distance with p is equal to or less than the distance dRadius: R.xs=R.xs +Pi.x， R.ys=R.ys+Pi.y， R.ns=R.ns+1. If the distances between Pi and all candidate references are larger than the distance dRadius， a new candidate reference R is generated: R.xm=Pi.x， R.ym=Pi.y， R.xs=Pi.x， R.ys=Pi.y， R.ns=1， which is added to CandidateReferenceSet Step 4. i++} End

图4-4 Single_Scan过程

过程Regenerate_Candidate_References生成新的候选代表点，将候选代表点代表区域内的点的中心作为新的候选代表点。在Single_Scan过程中已经保存了候选代表点代表区域内所有点的X坐标和、Y坐标和以及代表点的密度。在Regenerate_Candidate_References过程中，对于所有候选代表点R，重新修改其初始值，以便进行下一次扫描，算法如图4-5所示。

Regenerate_Candidate_References(CandidateReferenceSet) //Input: candidate reference set: CandidateReferenceSet //Output: candidate reference set: CandidateReferenceSet Begin Step 1. i=1

Step 2. While (i<=CandidateReferenceSet.Count) {

Step 3. Ri.xm=Ri.xs/Ri.ns，Ri.ym=Ri.ys/Ri.ns，Ri.xs=0，Ri.ys=0，Ri.ns=0 Step 4. i++}

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

End

图4-5 Regenerate_Candidate_References过程

寻找候选代表点的过程即Finding_Candidate_References算法需要多次调用Single_Scan过程和Regenerate_Candidate_References过程，在每次调用Single_Scan过程后产生新的候选代表点集，在Compare过程中用该候选代表点集与上一次产生的候选代表点集中的代表点的坐标一一作比较，如果都相同，则表示现在所确定的代表点的位置是客观反映数据点的分布的。否则，则表示这个迭代的过程还要进行，于是调用过程Regenerate_Candidate_References初始化新的代表点，以便进行下一次数据点集合的扫描。

§4.4.3 确定代表点集合

经过一系列的优化，使得产生的候选代表点就可以粗略地反映输入点集的空间几何特征，然后就可以筛选候选代表点了，调用过程

Filter_CandidateReferenceSet将密度小于密度阈值t的候选代表点过滤掉,算法如图4-6所示。

Filter_CandidateReferenceSet(CandidateReferenceSet) //Input: candidate reference set: CandidateReferenceSet //Output: candidate reference set: ReferenceSet Begin

Step 1. i=1, ReferenceSet= Ø

Step 2. While (i<=CandidateReferenceSet.Count) { Step 3. foreach Ri in CandidateReferenceSet Step 4. if Ri.ns >= t

Step 5. then ReferenceSet.Add(Ri) Step 4. i++} End

图4-6 Filter_CandidateReferenceSet过程

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

这一步，可以通过检查候选代表点集合中的每一个候选代表点的ns的属性值。当ns的值小于密度阈值t时就认为该代表点附近的点的密度较稀疏，将其代表区域内的所有点都视为噪音数据，将其删掉。这样得到的代表点集就可以准确地反映输入数据的空间几何特征。该过程的输出结果就是代表点的集合ReferenceSet。

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

在生成候选代表点的过程中，任意点p的坐标信息是加入到所有与点p距离小于等于Radius的候选代表点的信息中，那么，任意点p具体划分给哪一个代表点的代表区域是不是会对聚类的结果产生影响呢？

定理：在基于密度和层次的聚类算法中，点p具体与哪个代表点之间建立映射不会对聚类的结果产生影响，只需满足点p与该代表点的距离小于等于Radius。

证明：如果代表点R1和R2与点p的距离都小于等于Radius，由三角形边长定理：任意一边的边长小于其余两边的边长之和可知，代表点R1和R2之间的距离小于2倍的Radius，因此代表点R1和R2是邻接代表点。在空间中，由于任意不在同一直线上的3个点形成一个平面，因此上面的三角形定理仍然适用。当点p，R1和R2在同一直线时，R1和R2之间的距离小于等于2倍的Radius，R1和R2是邻接代表点。该聚类算法中相邻代表点属于同一个聚类的基本信息，因此点p无论在代表点R1的代表区域还是在代表点R2的代表区域，点p最终都属于同一个聚类，上述论点得证。

Mapping_References_and_Points过程建立代表点与其代表区域内输入数据的对应关系。理论上，对于任意点p将其划分为属于所有代表点中距离最近的代表点比较合理，由定理1可知，点p具体划分给哪个代表点不会对聚类的结果产生影响，只要点p与该代表点的距离小于等于Radius。因此，在

Mapping_References_and_Points过程中，点p顺序地与代表点集中的代表点进行比较，如果两者之间的距离小于等于Radius，则点p划分给该代表点，这样的处理可以提高算法的效率，如图4-7所示。

Mapping_References_and_Points (PointSet， ReferenceSet，dRadius) //Input: data set: PointSet， reference set: ReferenceSet， density threshold: t， distance: dRadius

//Output: reference set: ReferenceSet Begin Step 1. i=1

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

Step 2. While (i<=PointSet.Count) { Step 3. Foreach Rj in ReferenceSet Step 4. If Pi.distance(Rj) <=dRadius Step 5. then Rj.Ps.Add(Pi) break Step 6. i++} End

图4-7 Mapping_References_and_Points过程

注意，这里的输入参数中ReferenceSet为代表点集合，而不是最初产生的候选代表点的集合。

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

在给定距离Radius和阈值t产生的代表点集中，如果两个代表点R1和R2的距离小于等于2倍的Radius，则R1和R2是邻接代表点。如果两个代表点属于邻接代表点，则它们一定被划分在同一个簇中。该过程采用稍加修改的DBSCAN算法，如图4-8过程Cluster_devision。

Cluster_devision(ReferenceSet, 2dRadius)

//Input: reference set: ReferenceSet， distance: 2dRadius //Output: reference array: ReferenceSet Begin

Step1. i=0；

Step2. i++，读取代表点集ReferenceSet 中任意一个clflag=0的代表点R； Step3. 检索出R的2dRadius邻域内的所有代表点；

Step4. 将这些代表点的簇标记clflag赋值为i；然后将这些对象压入堆栈的Seeds中；

Step5. 让CurrentReference = Seeds.top；然后检索属于CurrentObject的2dRadius邻域的所有代表点；剔除已经打上簇标记的代表点，将余下的未划分的代表点打上簇标记clflag=i，然后压入堆栈； Step6. Seeds.pop，判断Seeds是否为空，是，则执行步骤2，否则执行步骤5。

End

图4-8 Cluster_devision过程

最后访问集合ReferenceSet中的所有代表点的clflag属性，属于相同簇的

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

代表点，具有相同的非零clflag值。

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

由于数据点已经被划分到代表点的代表区域内了，在对代表点进行簇的划分过程中实际上已经建立了聚类的簇和数据点之间的关系，属于同一个划分中的代表点代表区域内的数据点的集合就是一个聚类的簇。

§4.4.7 聚类结果

要得到图形化的聚类输出结果，只需要访问集合ReferenceSet，分两种情况： 1. 用代表点表示聚类结果。只需将集合中代表点的坐标R.xm,R.ym输出到屏

幕；

2. 用数据点表示聚类结果。需要访问每个代表点的属性Ps，将它当中数据点

的坐标Px,Py输出到屏幕上。

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

我们假定数据量为N，在生成候选代表点集的过程中，候选代表点的数目最大为K，确定候选代表点总共迭代了I次，代表点的最大数目为M，聚类的个数为C。

§4.5.1 时间复杂度

首先分析各个子算法的时间复杂度，最后推出该算法总的复杂度。 1． 确定候选代表点集合

Single_Scan过程中，总共有N个数据点，每一个数据点都要与K个候选代表点进行比较，所以它的时间复杂度为O(K*N)；CollectionCopy过程是将一个K个候选代表点的集合复制到另一个候选代表点集合，它的时间复杂度为O(K)；Regenerate_Candidate_References过程将候选代表点集合中的K个代表点的坐标进行调整，为下一次迭代作准备，它的时间复杂度为O(K)；Compare过程是将两个代表点的集合中的代表点的坐标进行比较，其时间复杂度为O(K)。因此寻找候选代表点的过程的时间复杂度为O(I*K*N+3*(I−1)*K)。

2． 确定代表点集合

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

对候选代表点的筛选过滤要扫描一遍候选代表点集以确定它是否该被排除，可以在O(K)内完成。这样，整个寻找代表点的过程的时间复杂度为O(I*K*N+3*(I−1)* K)+O(K)。

3． 确定代表点代表区域内的点集

这个过程是将所有的N个数据点与M个代表点计算距离，所以，每个点可以在O(M)时间内找到对应的代表点，因此确定代表点与数据点映射的时间复杂度为O(M*N)。

4． 对代表点集合进行簇的划分

前面我们早已分析过，对代表代点进行簇的划分使用DBSCAN算法，它的时间复杂度为O(M*M)。

5． 将代表点的聚类划分映射到数据点

该映射实际上在对代表点进行分类后就已经建立了。

从上面的分析可以看出，基于密度和层次的聚类算法的时间复杂度为O(I*K*N +3*(I-1)*K)+O(K)+O(M*N)+O(M*M)，通常，K，I，M<§4.5.2 空间复杂度

总共需要存储N个数据对象，最多K个候选代表点信息和C个簇信息，所以算法的空间复杂度是O(N)+O(K)+O(C)。

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

测试数据集是某公司的客户信息数据库，数据量为181200。我们实验的硬件环境是PC计算机，CPU为PⅣ2.0G，内存为256M；软件环境是：操作系统为Windows Professional 2000，编程环境Visual C++ 6.0。

§5.1 聚类效果的比较

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

图5-1 DBSCAN算法聚类结果

图5-2 基于密度和层次的算法聚类结果

Radius=0.02 t=80

图5-3 候选代表点 图5-4 代表点

基于密度和层次的聚类算法是从DBSCAN算法演变而来，因此用该算法与DBSCAN算法进行比较。图5-1、图5-2分别是DBSCAN算法和基于密度和层次的聚类算法对数据集聚类的结果。图5-3、图5-4是基于密度和层次的聚类算法发现的候选代表点和代表点。

可以看出，基于密度和层次的聚类算法可以很好地处理任意形状的数据集，同

时也较好地屏蔽了异常数据的影响。比较图5-1和图5-2也可以发现，该算法和DBSCAN算法聚类的结果非常接近。从图5-3可以看出，候选代表点基本上反映了输入数据的几何空间特征，但是仍然受到噪音数据的影响;从图5-4可以看出，经过对候选代表点的筛选过滤，得到的代表点准确地反映了原有数据的空间几何特征。

§5.2 输入参数的设定

基于密度和层次的聚类算法有2个主要参数:距离Radius和密度阈值t。参数的选择会影响算法的聚类结果和执行效率。

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

在实验中我们发现，如果距离Radius，密度阈值t与DBSCAN算法的参数Eps，MinPts取值相同，则两个算法会产生类似的结果。在DBSCAN算法中，参数Eps，MinPts的取值通常难以确定，但是在基于密度和层次的聚类算法中，距离Radius和密度阈值t的选取可以近似得到。距离Radius需要考虑的是整个数据的空间，距离Radius越小，聚类的结果越好，但是代表点的数目也就越多，算法的执行效率就会变低。我们经过实验还发现，我们的数据空间是1×1的二维空间，取距离值为[0.01,0.02]之间的数据通常会取得比较好的聚类效果；使用数据总量与候选代表点的数目比值，即候选代表点的平均密度作为密度阈值可以取得较好的效果。

图5-5 性能比

§5.3 执行效率的比较

如图5-5，我们用DBSCAN算法、基于R*-树的DBSCAN算法和基于密度和层次的聚类算法进行效率的比较。可以看出基于密度和层次的聚类算法的效率明显高于DBSCAN算法且略高于基于R*-树的DBSCAN算法，因此该算法是一种效率非常高的聚类算法。此外，由于基于R*-树的DBSCAN算法需要建立索引，而建立索引的时间代价是很大的；如果把建立索引的时间也考虑进去，则基于密度和层次的聚类算法将会大大优于DBSCAN算法。

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

第六章 总结和展望

本文以改进当前已存在的聚类算法的效率与效果为目的，在对现存算法进行大量的学习与研究的基础上提出了一种使用代表点来描述数据空间几何特征的方法，并提出了一种基于密度和层次的快速聚类算法。为了对该算法进行透彻的分析与试验，构建了基于该算法进行聚类的数据挖掘系统。通过理论分析和试验结果数据表明将该算法推广到实际应用中是可行的。下面就将我的工作成果以及遇到的问题总结做一个总结。

§6.1 工作总结

1.首先，该算法是在对大量已有算法研究的基础上，通过严密的逻辑分析和推理假设逐步构思而成的。仅从理论研究的角度来看，所采用的方法和步骤是严谨的、科学合理的。为以后在该领域进行更深层次的研究打下了坚实的理论和方法基础。

2.该算法形成的最基本的原则就是，必须要保证可以聚类任意形状的簇。因此在对代表点进行簇的划分时，我们采用了用密度阈值来排除孤立点并形成聚类簇的方法。从试验的结果来看，它达到了与DBSCAN相近的聚类效果，达到了良好聚类的标准：发现任意形状簇、处理噪声数据的能力。

3.基于划分的聚类方法——K_平均方法具有线性复杂性，而且采用了循环迭代的方法来确定簇的中心位置，在我们的算法中最消耗时间的“确定代表点位置的过程”中引入了K_平均算法的思想，使得我们的聚类方法在整体上具有线性复杂性，适合对大规模数据的挖掘。而且由于采用了循环迭代，最终使得代表点能够比较客观地反映数据点集合的相对位置。代表点的产生是通过对整个数据点的扫描并由他们的相对位置确定，故代表点的数目不是通过人为输入参数确定，而是由算法自动产生。因此，该算法达到了良好聚类的标准：对输入记录的顺序不敏感、可伸缩性。

4.该算法采用了适当的公式或规则将不同类型的属性映射到数字[0，1]之间，并采用距离的方法将对高维数据的处理转换到一维空间，从这个意义上看，基于密度和层次的聚类算法可以处理高维数据。达到了良好聚类的标准：处理不同类型属性的能力、高维性。

5.本文的主旨是对算法进行深入透彻的研究，但同时也提供了系统实现的思

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

路。本算法的应用并不局限于此，它还可以作为一个功能模块，嵌入到其他类型的数据挖掘系统中，作为它的一部分使用。

§6.2 问题与展望

1.本文提出的算法只是在理论上证明它具有处理高维数据的能力和良好的效果，由于人类对多于三维的空间不具有良好的判断力，我们很难确定算法的结果究竟能否真正的反映事实。下一步的工作，就是测试该算法在高维情况下的性能。

2.为了使得聚类算法适用于超大型规模的数据库，下一步工作的重点放在基于大型数据库的有效样本集的抽取上。

参考文献

[1] Z.Huang.Extensions to the k-means algorithm for clustering large data sets with

categorical values. Data Mining and Knowledge Discovery.1998.283~304 [2] Ester M, Kriegel HP, Sander J, Xu X. A density based algorithm for discovering

clusters in large spatial databases with noise. In: Simoudis E, Han JW, Fayyad UM, eds. Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland: AAAI Press, 1996

[3] V. Ganti, J. E. Gehrke, and R. Ramakrishnan. CACTUS-clustering categorical data

using summaries. In Proc. 1999 Int. Conf. Knowledge Discovery and Data Mining, San Diego, CA, 1999

[4] U. Fayyad,G .Piatetsky-Shapiro, and Padhraic Smyth. Knowledge Discovery and

Data Mining: Towards a Unifying Framework. Proceedings of Second International Conference on Knowledge Discovery and Data Mining ( KDD-96).AAAI Press, 1996.82-86

[5] Jiawei Han, Micheline Kamber. Data Mining: Concepts and Techniques. Simo

Fraser University, 2000. 187~198

[6] J.C Bezdek and S. K. Pal. Fuzzy Models for Pattern Recognition: Methods That

search for structures in Data. IEEE Press, 1992

[7] S. Guha, R. Rastogi, and K.Shim. Rock: A robust clustering algorithm for

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

categorical attributes. In Proc. 1999 Int. Conf. Data Engineering (ICDE’99), Sydney, Australia, Mar. 1999

[8] S. Sarawagi, R. Agrawal, and N. Megiddo. Discovery-driven exploration of OLAP

data cubes. In Proc. Int. Conf. Extending Database Technology, Valencia, Spain, 1998

[9] 刘同明. 数据挖掘技术及其应用. 国防工业出版社, 2001 [10] 朱明. 数据挖掘. 中国科学技术大学出版社，2002

[11] Manish Mehta, Rakesh Agrawal, Jorma Rissanen. SLIQ: A Fast and Scalable

Classifier for Data Mining. IBM Almaden Research Center, 1996

[12] 谢季坚， 刘承平. 模糊数学方法及其应用. 华中科技大学出版社，2001 [13] Agrawal R, Stolorz P, Piatetsky-Shapiro G. Proceedings of the Fourth International

Conferenceon Knowledge Discovery and Data Mining. Menlo Park: AAAI Press,1998

[14] 张乃尧，阎平凡. 神经网络与模糊控制. 清华大学出版社， 2000 [15] 张际先， 宓霞. 神经网络及其在工程中的应用. 机械工业出版社，1996 [16] Ed Wilson. The Knowledge Discovery Process, A Problem Solving Methodology.

Computer Associates International, Inc, 1998

[17] Jiawei Han, Micheline Kamber,范明，孟小峰译.数据挖掘概念与技术.北京: 机

械工业出版社，2001

[18] L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: an Introduction to

Cluster Analysis. New York: John Wiley & Sons, 1990

[19] Claude Seidman. SQL Server 2000数据挖掘技术指南. 机械工业出版社，2002 [20] David Hand, Heikki Mannila, Padhraic Smyth. 数据挖掘原理. 机械工业出版

社，2003

[21] Daniel A, keim steve Eick .Workshop On Visual Data Mining. SanFrancisco,

California: USA KDD,2001

[22] R.Agrawal,J.Gehrke,D.Gunopulos, P.Raghavan. Automatic subspace clustering of

high dimensional data mining applications.In Proc, 1998

[23] 武森，高学东，M.巴斯蒂安. 高维稀疏聚类知识发现. 冶金工业出版社，2003 [24] 田盛丰， 黄厚宽. 人工智能与知识工程. 中国铁道出版社， 1999

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

[25] 陆伟民. 人工智能技术及应用. 同济大学出版社， 1998 [26] 何新贵. 模糊知识处理的理论与技术. 国防工业出版社， 1998

[27] 林杰斌，刘明德，陈湘. 数据挖掘与OLAP理论与实务. 清华大学出版社，2003 [28] Padhraic Smyth, Breaking Out of the Black-Box: Rearch Challenges in Data

Mining, SIGKDD,2001

[29] A. K. Jain, and R. C. Dubes. Algorithms for Clustering Data. Englewood Cliffs, NJ:

Prentice Hall, 1988

[30] A. Arning, R. Aggarwal, and P. Raghavan. A linear method for deviation detection

in large databases. In Proc. 1996 Int. Conf. Data Mining and Knowledge Discovery, Portland, OR, Aug. 1996

[31] D. Gibson, J. M. Kleinberg, and P. Raghavan. Clustering categorical data: An

approach based on dynamical systems. In Proc. 1998 Int. Conf. Very Large Data Bases, New York, 1998

[32] E. Knorr and R. Ng. Algorithms for mining distance-based outliers in large datasets.

In Proc. 1998 Int. Conf. Very Large Data Bases, New York, Aug. 1998

[33] H. V. Jagadish, N. Koudas, and S. Muthukrishnan: Mining deviants in a time series

database. In Proc. 1999 Int. Conf. Very Large Data Bases, Edinburgh, UK, Sept. 1999

[34] 黄崇福，王家鼎. 模糊信息分析与应用. 北京师范大学出版社， 1992 [35] Heikki Mannila. Theoretical Frameworks for Data Mining. ACM SIGKDD, 2000 [36] V. Barnett and T. Lewis. Outliers in Statistical Data. New York: John Wiley &

Sons, 1994

[37] I.Dhillon, D.Modha, W.Spangler . Class Visualization of High-Dimensional

DataWith Application. New York: IBM Almaden Research Center,1999 [38] Kelly M.G, Hand D.J, Adams N.M. The impactof changing populations on

classifier performance. OpenUniversity Department of Statistics Technical Report,1999

[39] Alexandros N, Yannis T, Yannis M. C2P: clustering based on closest pairs. In:

Apers PMG, Atzeni P, Ceri S, Paraboschi S, Ramamohanarao K, Snodgrass RT, eds. Proceedings of the 27th International Conference on Very Large Data Bases.

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

Roma: Morgan Kaufmann Publishers, 2001

[40] Berchtold S, Bohm C, Kriegel H-P. The pyramid-technique: towards breaking the

curse of dimensionality. In: Haas LM, Tiwary A, eds. Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle: ACM Press, 1998

[41] A. K. Jain, M.N. Murty, and P. J. Flynn. Data clustering: A survey. ACM Comput.

Surv. 1999

[42] KA Smith, RJ Willis, M Brooks. An analysis of Customer retention and insurance

claim patterns using data mining: a case study. Journal of the Operational Research Society, vol.51.2000

[43] 朱扬勇，周欣，施伯乐. 规则型数据采掘工具集AMINER. 高技术通讯Vol.10

No.3, 2000

[44] G.Sheikholeslami, S.Chatterjee, A.Zhang. WaveCluster: A multiresolution

clustering approach for very large spatial database. New York :In Proc.1998 [45] Nandini Raghavan, Robert M.bell, Matthias Schonlau, Defection Detection : Using

Online Activity Profiles to Predict ISP Customer Vulnerability, KDD,2000. 506~515

致 谢

本论文的完成，不仅仅是我个人努力的结果，还应归功于许许多多在背后关心我、支持我和帮助我的人。他们的关心和帮助给予我一个舒适的学习和工作环境；他们的帮助使我的工作事半功倍。在此，谨对他们表示感谢。

感谢我的导师----何建中副教授两年半来对我的关心和指导。何老师治学严谨、待人真诚，时时刻刻关心着他的每一个硕士研究生的学习和生活，让我们有如沐春风之感。何老师不仅帮助我实现了从本科到硕士的跨越，而且告诉我许多职业发展及做人的道理，并且在我气馁的时候，是他一直在鼓励我继续坚持努力。借此机会，向何老师表示最忠心的感谢。

感谢茅忠明老师、张红老师、丁岳伟老师、陈家琪老师、蒋念平老师、陈玮老师，还有更多的老师无法一一列举，他们给予我学习和生活很多的帮助和关怀，我将铭刻在心。

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

感谢远在故乡善良的父母赐予我生命和多年来一如既往的关爱、支持与期待。 感谢我的爱人杨芳，是她在生活上给我坚实的后盾，让我一心一意投入到学习和科研中。

感谢我的师兄、师弟、师妹们，感谢我的同学和舍友们，预祝他们获得更多的成功。

最后，衷心感谢百忙之中抽出宝贵时间来参加论文审阅和答辩的各位老师!

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

一、 论文

焦守荣、何建中. 基于CAN总线的汽车监测系统的设计与实现. 计算机科学与实践，2005.3

二、 科研项目

何建中、焦守荣. 光栅莫尔信号数字化细分技术研究. 2004

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

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

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

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