基于层次的聚类算法 - 图文

独创性声明

本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。

论文题目： 作者签名：

日期： 年 月 日

论文版权使用授权书

本人完全了解吉首大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同意吉首大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。

(保密的学位论文在解密后应遵守此协议)

论文题目：

学生签名： 日期： 年 月 日

导师签名： 日期： 年 月 日

I

基于层次的聚类算法的研究与实现

摘 要

聚类分析是数据挖掘中的一个重要领域，是数据划分或分组处理的重要手段和方法，聚类分析已经应该于广泛的领域。聚类算法可以分为基于层次的方法、基于划分的方法、基于网格的方法、基于密度的方法和基于模型的方法。

层次聚类算法因为算法思想简单，适合于大量数据的聚类，所以是实际应用中聚类分析的支柱。本文重点对层次聚类算法进行了分析和研究，阐述了基于层次聚类的CURE和BIRCH算法，并实现了这两种算法以及给出了它们的聚类结果。

CURE算法是利用代表点聚类，它解决了偏好球形和相似大小的问题，可以发现具有任意大小和形状的聚类，而且在处理孤立点上也更加健壮。BIRCH是用聚类中心和半径来代表聚类，具有一定的处理噪音的能力，而且它是一种增量聚类方法，它不要求所有数据一次性读入内存，所以空间复杂度低，但是BIRCH算法无法发现任意形状和大小的聚类。

关键词：聚类分析；层次聚类；CURE；BRICH

II

Research and Implementation of the algorithm based on

hierarchical clustering

Sun Xili

(College of Information Science and Engineering, Jishou University, Jishou,Hunan

416000)

Abstract:

Clustering analysis is an essential field in data mining and also important means and method of data classification or grouping processing. Cluster analysis has played an important role in a wide range of data partitioning areas. Clustering algorithms can be divided into the method based on hierarchy, the methods based on the partition ,the grid-based methods, the density-based method and the model-based method.

Hierarchical clustering algorithm is a mainstay of the clustering analysis in practical application for its simple algorithm ideas, and suitable for large amounts of data clustering .This paper focuses on the hierarchical clustering algorithm analysis and research,expounds CURE and BIRCH algorithm based on hierarchy clustering algorithm,and implements the two algorithms and their clustering results are given.

CURE algorithm is the use of the clustering of the representative point,itsolved the problem of the preference of spherical and similar size, clusteringcan be found with any size and shape, but also more robust in dealing with the isolated point.BIRCH is using the clustering center and radius to delegate clustering,also with the ability to handling noise,and it is a kind of incremental clustering method,it does’t require all data is read into memory in a single, so the space complexity is low,but the BIRCH algorithm can not find clustering with any shape and size.

Keywords: Cluster analysis; Hierarchical clustering; CURE; BRICH

III

目 录

第一章 绪论 ............................................................................................. 1 1.1 课题的研究意义 .............................................................................. 1 1.2 课题的主要研究内容 ....................................................................... 1 1.3 论文内容和结构安排 ....................................................................... 2 第二章 聚类算法研究 ............................................................................... 3 2.1 聚类分析概述 .................................................................................. 3 2.2 主要聚类算法分类 .......................................................................... 4 2.3 聚类分析中的数据类型 ................................................................... 6 2.4 聚类算法的质量评价标准 ............................................................... 9 2.5 小结 .............................................................................................. 10 第三章 基于层次的聚类算法的分析 ....................................................... 11 3.1层次聚类方法概述 ......................................................................... 11 3.2层次聚类方法存在的不足 .............................................................. 13 第四章 基于层次聚类方法的实现 ........................................................... 15 4.1 CURE算法 ...................................................................................... 15 4.2 BIRCH算法 .................................................................................... 22 4.5 小结 .............................................................................................. 38 第五章 总结 ............................................................................................ 39 致谢 ......................................................................................................... 40 参考文献 .................................................................................................. 41

IV

基于层次的聚类算法的研究与实现 第一章 绪论

第一章 绪论

1.1 课题的研究意义

随着信息技术和数据库技术的迅猛发展，人们可以非常方便地存储和获取大量的数据。面对数据的日新月异，人们利用信息技术生产和搜集数据的能力大幅度提高，大量的数据库被用于科学研究、政府办公、商业管理和工程开发等等，以前的的数据分析工具（如管理系统）只能进行一些表层的处理（如统计、查询等），而不能获得数据之间存在的隐含的信息和内在的关联。为了摆脱“数据丰富，知识贫乏”和困境，人们迫切的需要一种能够自动地智能地把数据转换成有用信息和知识的工具和技术，这种对强有力的数据分析工具的迫切需要使得数据挖掘技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。

聚类分析是根据一批样品的多个观测指标，找出能够试验样品或变量之间相似程度的统计量，并以此为依据，采用某种聚类算法，将所有样品或变量分别聚合到不同的类中，使同一类中的个体有较大的相似性，不同类中的个体差异较大。聚类分析是一种无监督的学习方法，它已经被广泛地应用于统计学、机器学、空间数据库、生物学以及市场营销等领域，聚类分析还可以作为独立的数据挖掘工具来了解数据分布，或者作为其他数据挖掘算法（如关联规则、分类等）的预处理步骤。聚类算法可以分为基于的层次方法、基于划分的方法、基于网格的方法、基于密度的方法和基于模型的方法[2]。

聚类分析已经被广泛的研究了许多年，其中的层次聚类分析是聚类分析中极为重要的一个研究方向。它是由一系列的划分多步完成分类，而不是在一步以内将数据分成n类。层次聚类分为两种，分裂的（divisive）层次聚类和凝聚的（agglomerative）层次聚类。层次聚类算法由于要使用距离矩阵，所以它的时间和空间复杂性都很高，几乎不同在大数据集上使用，而且它在算法执行过程中，一量一个合并或分裂被执行，就不能修正。但是层次聚类算法没有使用准则函数，它所潜含的对数据结构的假设更少，所以它的通用性更强。为了将层次聚类算法应用在大规模的数据集上，许多研究者将采样技术，分块技术及数据压缩技术结合到层次算法中。典型的有：BIRCH、CURE、Chamelcon。

1.2 课题的主要研究内容

本文主要研究层次聚类算法，在系统地归纳层次聚类分析方法的一般原理、一般方法以及相关技术的基础上，分析BIRCH、CURE等层次聚类算法，并对它们加以

1

基于层次的聚类算法的研究与实现 第一章 绪论

实现并进行聚类分析。具体的来说，本论文所研究的主要内容如下：

（1） 分析和研究聚类算法。

（2） 在了解基于层次的聚类分析方法的基础上研究BIRCH、CURE算法，并加以实现。

1.3 论文内容和结构安排

本文共分为四章，各章的主要内容如下：

第一章 绪论。主要介绍的是论文的研究背景和现实意义。 第二章 聚类算法研究。主要介绍了聚类技术的相关概念。

第三章 层次聚类方法。主要传统的层次聚类方法，对其进行了详细的分析，并给出了传统的层次聚类方法存在的缺陷。

第四章 详细分析了层次聚类的各种算法，并阐述了BIRCH、CURE的思想和实现。

2

基于层次的聚类算法的研究与实现 第二章 聚类算法研究

第二章 聚类算法研究

本章系统地归纳聚类分析的基本概念及存在的问题，讨论聚类分析的数据结构

和数据类型，确定聚类的准则。

2.1 聚类分析概述

聚类分析是一种重要的人类行为。早在孩提时代，一个人就通过不断地改进下意识中的聚类模式来学会如何区分猫和狗，或者动物和植物。聚类分析已经广泛地应用在许多应用中，包括心理学和其他社会科学、生物学、统计学、模式识别、信息检索、机器学习和图像处理等领域。聚类即是将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。聚类是一个无监督的学习过程，它同分类的根本区别在于：分类是需要开始知道所根据的特征，而聚类是要准确的找到这个数据特征，因此在许多的应用中，聚类分析更是定义为一种数据预处理的过程，是进一步解析和处理数据的根本。例如，在生物学上，聚类能用于成功的推导植物和动物分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，洗车保险持有者的分组，及根据房子的类型，价值，和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类，以发现信息。作为一个数据挖掘的功能，聚类分析可以作为一个获得数据分布情况，观察每个簇的特征和对特定类进一步分析的独立工具。通过聚类能够了解密集和稀疏的区域，找到全局的分布模式以及数据的两个属性之间的互相联系等等[1]。

但是聚类分析是一个富有挑战性的研究领域，它的潜在应用提出了各种特殊的要求，它们主要表现在[2]：

（1) 可伸缩性。由于数据产生和收集技术的进步，数吉字节、数太字节甚至数拍字节的数据集起来越普遍。在大数据集合样本上进行聚类可能会导致有偏的结果。一般而言，聚类算法的时间复杂度太高，这要求在多项式的时间内完成，所以像这样算法的可伸缩性会更加好。如今已经做了很多的尝试，比如增量式挖掘，可靠的采样，数据挤压等等。例如BIRCH算法中使用CF树就属于数据挤压技术。

（2) 用于决定输入参数的领域知识最小化：许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担，也使得聚类的质量难以控制。

（3) 处理“噪声”的能力：在现实应用的绝大多数数据都可能包含有噪声数据，例如：孤立点、未知数据、空缺或者错误数据等。

3

基于层次的聚类算法的研究与实现 第二章 聚类算法研究

（4) 对于输入记录的顺序不敏感：许多聚类算法，如层次聚类算法对于输入数据的顺序是敏感的。对输入数据的顺序敏感的算法对于同一个数据集，当以不同的顺序提交给算法时，得到的结果可能差别很大。研究和数据输入顺序不敏感的算法具有重要的意义。

（5) 高维度（high dimensionality）：一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的数据，可能只涉及两到三维。人类的眼睛在最多三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的，特别是考虑到这样的数据可能分布非常稀疏，而且高度偏斜。

（6) 基于约束的聚类：现实世界的应用可能需要在各种约束条件下进行聚类。假设你的工作是在一个城市中为给定数目的自动提款机选择安放位置，为了作出决定，你可以对住宅区进行聚类，同时考虑如城市的河流和公路网，每个地区的客户要求等情况。要找到既满足特定的约束，又具有良好聚类特性的数据分组是一项具有挑战性的任务。

（7) 可解释性和可用性：用户希望聚类结果是和可用的、可理解的和可解释的。也就是说，聚类分析极有可能需要和特定的语义解释和应用联系起来。而且应用目标如何影响聚类方法的选择也是一个相当重要的研究课题。

2.2 主要聚类算法分类

目前聚类算法有很多种，算法的选择取决于聚类的目的和应用以及数据的类型。传统的聚类算法可以分为五类：划分方法、层次方法、基于网格方法、基于模型方法和基于密度方法[3]。

2.2.1划分的方法（Partitioning Method）

给定一个数据库包含N个数据对象以及数目K的即将生成的簇,一个划分类的算法将对象分为K个划分（k<=n），其中，这里的每个划分分别代表一个簇。通常会使用一个划分规则（通常称为相似度函数，similarity function）。而传统的划分方法有Kmeans方法和K-medoids以及它们的改进算法。

Kmeans方法采用簇中对象的平均值当做参照点，而K-medoids方法不采用簇中对象的平均值作为参照点，而是选用簇中位置最中心的对象作为参照点。因此，孤立点数据和“噪声”对K-medoids方法的影响相对来说比Kmeans方法小的多，但是复杂度要比Kmeans方法高。

PAM（Partitioning around Medoids,黑线k-medoids的划分）算法对孤立点和“噪声”数据不敏感，并且可以知道由它所发现的簇与聚类数据的输入顺序无关，能够处理不同类型的数据点。PAM对小的数据集合非常有效，但对大的数据集合没有良好的可伸缩性。

4

基于层次的聚类算法的研究与实现 第二章 聚类算法研究

2.2.2层次的方法（Hierarchical Method）

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

层次方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消。这个严格规定是必要的，由于不需要担心组合数目的不一样的选择，计算代价相对会很小。但是该技术的重要的问题是它不能更正错误的决策。因此人们提出了很多的改进方法，一种是加强对象间“连接”的分析，如CURE和Chameleon;另一种是迭代的重定位和综合层次聚类方法，如BIRCH。这几种算法都会在第三章中重点分析并实现。

2.2.3基于密度的方法（Density-based Method）

绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要思想是：只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的聚类。具有代表性的基于密度的聚类方法有DBSCAN，它根据一个密度阈值来调控簇的增长。另一个基于密度的聚类方法是OPTICS，它为自动的交互的聚类分析计算一个聚类顺序。

2.2.4基于网格的方法（Grid-based Method）

在聚类分析方法中，基于网格的聚类方法采用了多给网格数据结构。它将空间划分为有限数目的单元，以构成一个可以进行聚类分析的网格结构，几乎所有的聚类操作都在网格上进行。这种方法的主要优点是处理速度快，其处理时间独立平均数据对象的数目，仅依赖于量化空间中每一维上的单元数目。常用的基于网格聚类算法有STING(Statistieal Information Grid)算法和CLIQUE(Clustering In Quest)算法。

STING算法是一种基于网格多分辨率的聚类方法，它将空间划分为方形单元，不同层次的分辨率与这些不同层次的方形单元相对应，方形单元存放方差、均值、最大值、最小值等统计信息。

CLIQUE是在高维空间中基于网格和密度的聚类方法。CLIQUE对数据的输入顺序不敏感，也不需要假设任何特定的数据分布，输入数据量大小与时间复杂度呈线性关系，它能自动发现最高维中所存大的密集聚类，当数据维数发生变化时具有较好

5

基于层次的聚类算法的研究与实现 第二章 聚类算法研究

的可扩展性，缺点是在追求方法简单化的同时降低了聚类的精度。 2.2.5基于模型的方法（Model-based Method）

基于模型的方法为每个聚类假定了一个模型，然后找出数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类，并且基于标准的统计数字来自动决定聚类的数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类。基于模型的方法主要有两类：神经网络方法和统计学方法。

基于统计学的聚类方法最著名的是COBWEB算法。COBWEB是一种简单流行的增量概念聚类算法，它的输入对象用（分类属性，值）来描述。COBWEB以一个分类树的形式创建层次聚类。COBWEB算法不需要用户提供相应的参数可以自动修正划分中聚类簇的数目。然而它也有局限性。首先，假设在每个属性上的概率分布是彼此独立的。由于属性经常是相关的，这个假设并不总是成立。此外，聚类的概率分布描述使得存储聚类和更新非常昂贵。而且，分类树对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化。

各种聚类算法的适用领域及时间空间复杂度的比较如表2-1所示。

表2-1 各种聚类算法的指标比较

[4]

算法 CURE Chameleon PAM CLARA CLARANS DBSCAN OPTICS WaveCluster COBWEB

时间复杂度 O(n2) O(n2) O(n2) O(n) O(n2) O(nlogn) O(nlogn) O(n) O(nlogn) 空间复杂度 O(n) O(n2) O(n) O(n) O(n) O(n) O(n) O(n) O(n) 适合的数据集 大数据集 大数据集 小数据集 大数据集 大数据集 大数据集 大数据集 大数据集 大数据集 适合领域 任意形状 任意形状 凸形或球形 凸形或球形 凸形或球形 任意形状 任意形状 任意形状 凸形或球形 2.3 聚类分析中的数据类型

6

本文来源：https://www.bwwdw.com/article/0eqt.html