1、Pattern Recognition &artificial IntelligenceLecture 7: 聚 类 算法（三）1Hierarchical Clustering 基于分层的聚类算法凝聚和分裂层次聚类BIRCH：利用层次方法的平衡迭代归约和聚类Chameleon：利用动态建模的层次聚类算法ROCK:分类属性的层次聚类算法CURE： 基于质心和基于代表对象方法之间的中间策略2概要层次聚类方法将数据对象组成一棵 聚类树 。根据 层次分解 是以自底向上（合并）还是自顶向下（分裂）方式，层次聚类方法可以进一步分为 凝聚 的和 分裂的。一种纯粹的层次聚类方法的质量 受限 于： 一旦合并或分
2、裂执行，就不能修正。 也就是说，如果某个合并或分裂决策在后来证明是不好的选择，该方法无法退回并更正。3层次聚类方法一般来说，有两种类型的 层次聚类方法 ： 凝聚 层次聚类： 采用自底向上策略，首先将每个对象作为单独的一个原子类，然后合并这些原子类形成越来越大的类，直到所有的对象都在一个类中（层次的最上层），或者达到一个终止条件。绝大多数层次聚类方法属于这一类。 分裂 层次聚类： 采用自顶向下策略，首先将所有对象置于一个类中，然后逐渐细分为越来越小的类，直到每个对象自成一个类，或者达到某个终止条件，例如达到了某个希望的类的数目，或者两个最近的类之间的距离超过了某个阈值。4例子 下图描述了一种凝聚
3、层次聚类算法 AGNES（AGlomerative NESting） 和一种分裂层次聚类算法 DIANA （ Divisive Analysis ） 对一个包含五个对象的数据集合a,b,c,d,e的处理过程。Step 0 Step 1 Step 2 Step 3 Step 4bdcea a bd ec d ea b c d eStep 4 Step 3 Step 2 Step 1 Step 0agglomerative(AGNES)divisive(DIANA)图 1 对数据对象 a,b,c,d,e的凝聚和分裂层次聚类 5 初始， AGNES将每个对象自为一类，然后这些类根据某种准则逐步合并，
4、直到所有的对象最终合并形成一个类。 例如，如果类 C1中的一个对象和类 C2中的一个对象之间的距离是所有属于不同类的对象间欧氏距离中最小的，则 C1和 C2合并。 在 DIANA中，所有的对象用于形成一个初始类。根据某种原则（如，类中最近的相邻对象的最大欧氏距离），将该类分裂。类的分裂过程反复进行，直到最终每个新类只包含一个对象。 在凝聚或者分裂层次聚类方法中，用户可以 定义 希望得到的类数目作为一个 终止条件 。例子6树状图 通常，使用一种称作 树状图 的树形结构表示层次聚类的过程。它展示出对象是如何一步步分组的。图 2显示图 1的五个对象的树状图。图 2 数据对象 a,b,c,d,e层次聚类的树状图表示7类间距离 四个广泛采用的 类间距离 度量方法如下，其中 |p-p|是两个对象或点 p和 p之间的距离， mi是类 Ci的均值，而 ni是类 Ci中对象的数目。 最小距离： 最大距离： 均值距离： 平均距离：8最小距离 最大距离均值距离 平均距离类间距离9 当算法使用最小距离 衡量类间距离时，有时称它为 最近邻聚类算法 。此外，如果当最近的类之间的距离超过某个任意的阈值时聚类过程就会终止，则称其为 单连接算法 。 当一个算法使用最大距离 度量类间距离时，有时称为 最远邻聚类算法 。如果当最近类之间的最大距离超过某个任意阈值时聚类过程便终止，则称其为 全连接算法 。10
