层次聚类分析算法的思考及实现
一．概述
对急剧增长的数据加以组织和从数据中学习有价值信息的需要，使得聚类成为一个非常
活跃的研究领域。不采用概括技术，人们很难从充斥着大量信息的数据库中发现知识。基本
的统计量（如均值、方差）或者直方图可以提供对于数据的初步感觉。然而，聚类分析可以
解释对象之间、特征之间以及对象和特征之间错综复杂的关系。它是数据挖掘中研究和应用
的一个重要部分。
聚类分析简单来讲就是将数据对象分组成多个类或簇，在同一个簇中的对象之间具有较
高的相似度，而不同簇中的对象差别较大。聚类分析是无指导学习。它与数据挖掘中的的分
类不同，在分类模块中，对于目标数据库中存在哪些类这一信息我们是知道的，在那里要做
的就是将每一条记录属于哪一类标记出来；与此相似但又不同的是，聚类是在预先不知道目
标数据库到底有多少类的情况下，希望将所有的纪录组成不同的类或者说“聚类”(cluster)
并且使得在这种分类情况下，以某种度量为标准的相异度，在同一聚类之间最小化，而在不
同聚类之间最大化。
二．算法分析
1．传统算法介绍
聚类分析方法主要有以下几种：划分方法，层次方法，基于密度的方法，基于网格的方
法和基于模型的方法。本文主要讨论层次聚类方法。
层次聚类方法是聚类分析的一个重要方法。这种方法对给定的数据集合进行层次的分解，
根据层次的分解如何形成，它又可分为凝聚法(也称自底向上方法)和分裂法(也称为从上向下
方法)，而凝聚的层次聚类方法应用得更多，该方法采用自底向上的策略，首先将每个对象
作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某
个终结条件被满足。资格广泛采用的簇间距离度量方法分别为：最小距离、最大距离、平均
值的距离、平均距离。本文主要讨论层次聚类算法中的平均距离算法。
层次聚类算法基本思想及其分析：
假定有 N 个对象被聚类，其距离矩阵大小为 N*N，采用平均距离的凝聚层次聚类方法
的基本过程如下：
1） 将每一个数据对象视为一类，每类仅一个对象，计算它们之间的最短距离 D，
类与类之间的距离就是她们所包含对象之间的距离，得到初始化距离矩阵；（或
者初始化矩阵作为已知参数给出）
2） 将距离最近的两个类合并成一个新的类；
3） 重新计算所有类之间的距离；
4） 重复 2 和 3 步，知道所有类最后合并成一个类或者达到结束条件（该条件可人
为指定）
评论0