毕业设计（论文）-基于层次的聚类算法的研究与实现、.doc

独创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。论文题目： 作者签名： 日期： 年 月 日论文版权使用授权书本人完全了解吉首大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同意吉首大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。(保密的学位论文在解密后应遵守此协议)论文题目： 学生签名： 日期： 年 月 日 导师签名： 日期： 年 月 日42基于层次的聚类算法的研究与实现摘 要聚类分析是数据挖掘中的一个重要领域，是数据划分或分组处理的重要手段和方法，聚类分析已经应该于广泛的领域。聚类算法可以分为基于层次的方法、基于划分的方法、基于网格的方法、基于密度的方法和基于模型的方法。层次聚类算法因为算法思想简单，适合于大量数据的聚类，所以是实际应用中聚类分析的支柱。本文重点对层次聚类算法进行了分析和研究，阐述了基于层次聚类的CURE和BIRCH算法，并实现了这两种算法以及给出了它们的聚类结果。CURE算法是利用代表点聚类，它解决了偏好球形和相似大小的问题，可以发现具有任意大小和形状的聚类，而且在处理孤立点上也更加健壮。BIRCH是用聚类中心和半径来代表聚类，具有一定的处理噪音的能力，而且它是一种增量聚类方法，它不要求所有数据一次性读入内存，所以空间复杂度低，但是BIRCH算法无法发现任意形状和大小的聚类。关键词：聚类分析；层次聚类；CURE；BRICHResearch and Implementation of the algorithm based on hierarchical clusteringSun 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.CUREalgorithmistheuseoftheclusteringoftherepresentativepoint,itsolvedtheproblemofthepreferenceofsphericalandsimilarsize,clusteringcanbefoundwith anysizeandshape,butalso more robust in dealing with theisolatedpoint.BIRCHisusingtheclusteringcenterandradiusto delegate clustering,alsowiththeabilitytohandlingnoise,anditisakindofincrementalclusteringmethod,itdoest requirealldataisreadintomemory in a single, sothespacecomplexityislow,buttheBIRCHalgorithmcannot find clusteringwithanyshapeandsize.Keywords: Cluster analysis; Hierarchical clustering; CURE; BRICH目 录第一章绪论11.1 课题的研究意义11.2课题的主要研究内容11.3论文内容和结构安排2第二章 聚类算法研究32.1聚类分析概述32.2主要聚类算法分类42.3聚类分析中的数据类型62.4 聚类算法的质量评价标准102.5 小结10第三章 基于层次的聚类算法的分析113.1层次聚类方法概述113.2层次聚类方法存在的不足13第四章 基于层次聚类方法的实现154.1 CURE算法154.2 BIRCH算法224.5 小结38第五章 总结39致谢40参考文献41基于层次的聚类算法的研究与实现 第一章 绪论第一章 绪论1.1 课题的研究意义随着信息技术和数据库技术的迅猛发展，人们可以非常方便地存储和获取大量的数据。面对数据的日新月异，人们利用信息技术生产和搜集数据的能力大幅度提高，大量的数据库被用于科学研究、政府办公、商业管理和工程开发等等，以前的的数据分析工具（如管理系统）只能进行一些表层的处理（如统计、查询等），而不能获得数据之间存在的隐含的信息和内在的关联。为了摆脱“数据丰富，知识贫乏”和困境，人们迫切的需要一种能够自动地智能地把数据转换成有用信息和知识的工具和技术，这种对强有力的数据分析工具的迫切需要使得数据挖掘技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。聚类分析是根据一批样品的多个观测指标，找出能够试验样品或变量之间相似程度的统计量，并以此为依据，采用某种聚类算法，将所有样品或变量分别聚合到不同的类中，使同一类中的个体有较大的相似性，不同类中的个体差异较大。聚类分析是一种无监督的学习方法，它已经被广泛地应用于统计学、机器学、空间数据库、生物学以及市场营销等领域，聚类分析还可以作为独立的数据挖掘工具来了解数据分布，或者作为其他数据挖掘算法（如关联规则、分类等）的预处理步骤。聚类算法可以分为基于的层次方法、基于划分的方法、基于网格的方法、基于密度的方法和基于模型的方法2。聚类分析已经被广泛的研究了许多年，其中的层次聚类分析是聚类分析中极为重要的一个研究方向。它是由一系列的划分多步完成分类，而不是在一步以内将数据分成n类。层次聚类分为两种，分裂的（divisive）层次聚类和凝聚的（agglomerative）层次聚类。层次聚类算法由于要使用距离矩阵，所以它的时间和空间复杂性都很高，几乎不同在大数据集上使用，而且它在算法执行过程中，一量一个合并或分裂被执行，就不能修正。但是层次聚类算法没有使用准则函数，它所潜含的对数据结构的假设更少，所以它的通用性更强。为了将层次聚类算法应用在大规模的数据集上，许多研究者将采样技术，分块技术及数据压缩技术结合到层次算法中。典型的有：BIRCH、CURE、Chamelcon。1.2 课题的主要研究内容本文主要研究层次聚类算法，在系统地归纳层次聚类分析方法的一般原理、一般方法以及相关技术的基础上，分析BIRCH、CURE等层次聚类算法，并对它们加以实现并进行聚类分析。具体的来说，本论文所研究的主要内容如下：（1） 分析和研究聚类算法。（2） 在了解基于层次的聚类分析方法的基础上研究BIRCH、CURE算法，并加以实现。1.3 论文内容和结构安排本文共分为四章，各章的主要内容如下：第一章 绪论。主要介绍的是论文的研究背景和现实意义。第二章 聚类算法研究。主要介绍了聚类技术的相关概念。第三章 层次聚类方法。主要传统的层次聚类方法，对其进行了详细的分析，并给出了传统的层次聚类方法存在的缺陷。第四章 详细分析了层次聚类的各种算法，并阐述了BIRCH、CURE的思想和实现。基于层次的聚类算法的研究与实现 第二章 聚类算法研究第二章 聚类算法研究本章系统地归纳聚类分析的基本概念及存在的问题，讨论聚类分析的数据结构和数据类型，确定聚类的准则。2.1 聚类分析概述聚类分析是一种重要的人类行为。早在孩提时代，一个人就通过不断地改进下意识中的聚类模式来学会如何区分猫和狗，或者动物和植物。聚类分析已经广泛地应用在许多应用中，包括心理学和其他社会科学、生物学、统计学、模式识别、信息检索、机器学习和图像处理等领域。聚类即是将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。聚类是一个无监督的学习过程，它同分类的根本区别在于：分类是需要开始知道所根据的特征，而聚类是要准确的找到这个数据特征，因此在许多的应用中，聚类分析更是定义为一种数据预处理的过程，是进一步解析和处理数据的根本。例如，在生物学上，聚类能用于成功的推导植物和动物分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，洗车保险持有者的分组，及根据房子的类型，价值，和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类，以发现信息。作为一个数据挖掘的功能，聚类分析可以作为一个获得数据分布情况，观察每个簇的特征和对特定类进一步分析的独立工具。通过聚类能够了解密集和稀疏的区域，找到全局的分布模式以及数据的两个属性之间的互相联系等等1。但是聚类分析是一个富有挑战性的研究领域，它的潜在应用提出了各种特殊的要求，它们主要表现在2：（1) 可伸缩性。由于数据产生和收集技术的进步，数吉字节、数太字节甚至数拍字节的数据集起来越普遍。在大数据集合样本上进行聚类可能会导致有偏的结果。一般而言，聚类算法的时间复杂度太高，这要求在多项式的时间内完成，所以像这样算法的可伸缩性会更加好。如今已经做了很多的尝试，比如增量式挖掘，可靠的采样，数据挤压等等。例如BIRCH算法中使用CF树就属于数据挤压技术。（2) 用于决定输入参数的领域知识最小化：许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担，也使得聚类的质量难以控制。（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对小的数据集合非常有效，但对大的数据集合没有良好的可伸缩性。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对数据的输入顺序不敏感，也不需要假设任何特定的数据分布，输入数据量大小与时间复杂度呈线性关系，它能自动发现最高维中所存大的密集聚类，当数据维数发生变化时具有较好的可扩展性，缺点是在追求方法简单化的同时降低了聚类的精度。2.2.5基于模型的方法（Model-based Method）基于模型的方法为每个聚类假定了一个模型，然后找出数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类，并且基于标准的统计数字来自动决定聚类的数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类。基于模型的方法主要有两类：神经网络方法和统计学方法。基于统计学的聚类方法最著名的是COBWEB算法。COBWEB是一种简单流行的增量概念聚类算法，它的输入对象用（分类属性，值）来描述。COBWEB以一个分类树的形式创建层次聚类。COBWEB算法不需要用户提供相应的参数可以自动修正划分中聚类簇的数目。然而它也有局限性。首先，假设在每个属性上的概率分布是彼此独立的。由于属性经常是相关的，这个假设并不总是成立。此外，聚类的概率分布描述使得存储聚类和更新非常昂贵。而且，分类树对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化。各种聚类算法的适用领域及时间空间复杂度的比较如表2-1所示。表2-1 各种聚类算法的指标比较4算法时间复杂度空间复杂度适合的数据集适合领域CUREO()O(n)大数据集任意形状ChameleonO()O()大数据集任意形状PAMO()O(n)小数据集凸形或球形CLARAO(n)O(n)大数据集凸形或球形CLARANSO()O()大数据集凸形或球形DBSCANO(log)O(n)大数据集任意形状OPTICSO(log)O(n)大数据集任意形状WaveClusterO(n)O(n)大数据集任意形状COBWEBO(log)O(n)大数据集凸形或球形2.3 聚类分析中的数据类型聚类分析不仅可以揭示数据间内在的联系和区别，同时也可以为进一步的数据分析与知识发现提供重要的依据，主要用于进行数据探索，并给出数据描述，而且还可以作为数据预测、内容检索、模式识别等其它方面应用的前期准备工作2.3.1数据的表示在聚类分析中有许多不同的数据类型。假设要聚类的数据集合包含n个数据对象，这些数据对象可能表示人、房子、文档、国家等。许多聚类算法选择如下两种代表性的数据结构：1.数据矩阵（data matrix）用p个变量来表示n个对象，例如用年龄、身高、体重、性别、种族等属性来表现对象“人”。这种数据结构是关系表的形式，或者是看成n*p(n个对象*p个变量)的矩阵，如图2.1所示。图2.1 数据矩阵2.相异度矩阵（dissimilarity matrix）存储n个对象两两之间的近似性，表现形式是一个n*n维的矩阵，如图2.2所示。图2.2 相异度矩阵在这里d(i,j)是对象i和对象j之间相异性的量化表示，通常它是一个非负的数值，当对象i和j越相似或相近，其值就越接近0，两个对象越不同，其值越大。如果数据是用数据矩阵的形式表现的，在使用聚类算法之前需要将其转化为相异度矩阵。2.3.2数据的类型下面将讨论如何计算区间标度变量，二元变量，标称型，序数型，比例标度型以及混合类型的变量描述的数据对象之间的差异值。利用数据 对象差异值就可以对对象进行聚类分析了。1区间标度变量，线性标度的连续变量为了将数据划分成不同的的类别，必须定义差异度或相似性的测试来度量同一类别之间数据的相似性和不同类别数据的差异性。同时要考虑到数据的多个属性属性使用的是不同的度量单位，这些将直接影响到聚类分析的结果，为了避免对度量单位选择的依赖，数据应当标准化。数据标准化常用的方法是将原来的度量值转换为无单位的值。给定一个具有p个属性的变量f的度量值，可以进行如下的变换：（1）计算平均的绝对偏差（mean absolute deviation）Sf如公式2.1所示。其中，是f的n个度量值，是f的平均值，如公式2.2所示。 （公式2.1） = （公式2.2）（2） 计算标准化的度量值，或Z-SCORE如公式2.3所示。 = （公式2.3）这个平均的绝对偏差比标准的偏差对于孤立点具有更好的鲁棒性。在计算平均绝对偏差时，度量值与平均值的偏差没有被平方，因此孤立点的影响在一定程度上被减小了。虽然存在更好的对偏差的度量方法，例如中值绝对偏差（median absolute deviation），但采用平均绝对偏差的优点在于孤立点的z-score值不会太小，因此孤立点仍可以被发现。2.二元变量一个二元变量只有两个状态：0或1，0表示该变量为空，1表示该变量存在。二元变量又分为对称和不对称，对称的二元变量的两个状态有相同的权重。如果两个状态的输出不是同样重要，那么该二元变量的相似度称为恒定的相似度。3.标称型、序数型和比例标度型变量（1) 标称变量标称变量是二元变量的推广，它可以具有多于两个的状态值。例如：map_color是一个标称变量，它有五个状态：红色、黄色、绿色、粉红色和蓝色。假设一个标称变量的状态数目是M，每一个状态值可以用字母，符号或者一组整数来表示，则两个对象i和j之间的相异度可以用简单匹配方法来计算，如公式2.4所示。这里m是匹配数即i和j取值相同的变量的数目而p是全部变量的数目。 d(i,j) = （公式2.4）（2) 序数型变量序数型变量可以是离散的，也可以是连续的。在连续型的序数变量中，值的相对顺序是必要的，而其实际的大小则不重要。在相异度的计算中，需要把每个变量的值域映射到0.0，1.0上，以便每个变量都有相同的权重。然后可以采用距离的计算方法进行相异度的计算。（3) 比例标度型变量比例标度型变量是非纯属的标度取正的度量值，例如指数标度，A计算时可以采用与处理区间标度变量相同的方法;也可以先进行对数变换，再进行计算;也可以借用序数变量，采用秩作为区间标度的值来对待。4.混合类型的变量在许多真实的数据库中，对象是由混合类型的变量描述的。一般来说，一个数据库可能包含上面列出的全部类型。计算相异度时，一种方法是将变量按类型分组，对每种类型的变量进行单独聚类分析，如果这些分析得到兼容的结果，这种方法是可行的。但是，在实际的应用中，这种情况是不大可能的。因为数据对象可能包含多种变量类型。另一种方法是把所有的变量一起来处理，只进行一次聚类分析。但是这需要将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间0.0,1.0上，这样，当描述对象的变量是不同类型时，对象之间的相异度也能够进行计算。2.3.3数据的相似性度量聚类分析按照样本点之间的亲疏远近程度进行分类。为了使类分得合理，必须描述样本之间的亲疏远近程度。刻画聚类样本点之间的亲疏远近程度主要有以下两类函数：(1) 相似系数函数：两个样本点愈相似，则相似系数值愈接近1；样本点愈不相似，则相似系数值愈接近0。这样就可以使用相似系数值来刻画样本点性质的相似性。(2) 距离函数：可以把每个样本点看作高维空间中的一个点，进而使用某种距离来表示样本点之间的相似性，距离较近的样本点性质较相似，距离较远的样本点则差异较大。相似性的度量方法很多，有的用于专门领域，也有的适用于特定类型的数据，如何选择相似性的度量方法是一个相当复杂的问题，需要由领域专家确定采用哪些指标特征变量来精确刻画样本的性质，以及如何定义样本之间的相似性测度2。2.4 聚类算法的质量评价标准聚类质量的好坏通常取决于聚类算法所使用的相识性测量方法和实现方式和改算法能否发现部分和全部隐藏的模式。判断聚类结果有效性及准确性，对于每个数据点对，存在4种可能 4:（1) 结果中它们归于一类，而实际上它们确实是一类。（2) 结果中它们归于不同类，但是实际上它们应该是同一类（3) 结果中它们归于不同类，实际上它们确实不是同一类。（4) 结果中它们归于同一类，但是实际上它们不属于同一类。设满足上一条件的样本对数分别为：a、b、c、d,总样本对数为n.评价标准常采用正确的样本对数与总样本对数之比（rand系数）:（a+c）/(n*(n-1)/2)。2.5 小结在数据挖掘，聚类分析是一个活跃的研究领域。本章讨论了数据结构和数据类型的聚类分析，聚类准则来确定。随着大型数据库技术的发展，计算机技术，数据挖掘不仅继承了传统的聚类方法，但也提出了新的要求对数据进行聚类。可以看到，目前的研究重点和趋势数据挖掘中的聚类：聚类算法的发展具有很强的可扩展性，以满足海量数据的处理，有效的检测和噪声和异常数据对象聚类算法解释聚类结果的有效性评价研究;聚类高维数据空间;考虑尺寸，噪声和异常统计量的分布，聚类形状，规模和类簇密度分离，非欧几里德数据空间，非数值属性的数据类型和一系列强大的集聚。 分层聚类方法的聚类分析方法的重要组成部分。层次聚类法的困难是合并或分割点的选择。在下一章的层次聚类算法进行探索性研究。基于层次的聚类算法的研究与实现 第三章 基于层次的聚类算法分析第3章 基于层次的聚类算法的分析3.1层次聚类方法概述层次聚类算法，也称为聚类算法，它是通过将数据组织为若干组并形成一个相应的树来进行聚类的。根据层次是自底向上还是自顶而下形成，层次聚类算法可以进一步分为凝聚型的聚类算法和分裂型的聚类算法。一个完全层次聚类的质量由于无法对已经做的合并或分解进行调整而受到影响。但是层次聚类算法没有使用准则函数，它所含的对数据结构的假设更少，所以它的通用性更强。3.1.1两种基本的层次聚类方法在实际应用中一般有两种层次聚类方法：(1) 凝聚的层次聚类：这种自底向上的策略首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被达到要求。大部分的层次聚类方法都属于一类，它们在簇间的相似度的定义有点不一样。(2) 分裂的层次聚类：像这样的自顶向下的策略与凝聚的层次聚类有些不一样，它首先将所有对象放在一个簇中，然后慢慢地细分为越来越小的簇，直到每个对象自行形成一簇，或者直达满足其他的一个终结条件，例如满足了某个期望的簇数目，又或者两个最近的簇之间的距离达到了某一个阈值。图3-1描述了一个凝聚层次聚类方法AGENES和一个分裂层次聚类方法DIANA在一个包括五个对象的数据的集合a,b,c,d,e上的处理的过程。初始时，AGENES将每个样本点自为一簇，之后这样的簇依照某一种准则逐渐合并，例如，例如簇C1中的某个样本点和簇C2中的一个样本点相隔的距离是所有不同类簇的样本点间欧几里得距离最近的，则认为簇C1和簇C2是相似可合并的。这就是一类单链接的方法，基每一个簇能够被簇中其他所有的对象所代表，两簇之间的相似度是由这里的两个不同簇中的距离最相近的数据点对的相似度来定义的。聚类的合并进程往复的进行直到其他的对象合并形成了一个簇。而DIANA方法的运行过程中，初始时DIANA将所有样本点归为同一类簇，然后根据某种准则进行逐渐分裂，例如类簇C中两个样本点A和B之间的距离是类簇C中所有样本点间距离最远的一对，那么样本点A和B将分裂成两个簇C1和C2，并且先前类簇C中其他样本点根据与A和B之间的距离，分别纳入到簇C1和C2中,例如，类簇C中样本点O与样本点A的欧几里得距离为2，与样本点B的欧几里得距离为4，因为Distance(A，O)NumMembers=u-NumMembers+v-NumMembers;for(i=0;iMeansi=(u-Meansi*u-NumMembers+v-Meansi*v-NumMembers)/w-NumMembers;for(i=0;iNumMembers;i+)w-Memberi=u-Memberi;for(i=u-NumMembers;iNumMembers;i+)w-Memberi=v-Memberi-u-NumMembers;if(w-NumMembers=NUMPRE)for(i=0;iNumMembers;i+)w-PreMemberi=w-Memberi;elsefor(i=0;iNUMPRE;i+) MaxDist=0;for(j=0;jNumMembers;j+)if(i=0)if(j=i)continue;dist=EucNorm(w-Means,Patternw-Memberj);elseif(j=i-1)continue;dist=EucNorm(w-Prei-1,Patternw-Memberj);if(distMaxDist)MaxDist=dist;MaxPoint=j;w-PreMemberi=j;ShrinkPre(w);return w; (4) 聚类void System:RunCure()int i,j,k,u,v;double d,MinDist;ClustNode *w;BuildClustList();k=NUMPATTERNS;for(;kNUMCLUSTER