聚类算法——层次方法.ppt

层次聚类方法 万义飞 Page ? * 概要 层次聚类方法将数据对象组成一棵聚类树。 根据层次分解是以自底向上（合并）还是自顶向下（分裂）方式，层次聚类方法可以进一步分为凝聚的和分裂的。 一种纯粹的层次聚类方法的质量受限于：一旦合并或分裂执行，就不能修正。也就是说，如果某个合并或分裂决策在后来证明是不好的选择，该方法无法退回并更正。 Page ? * 层次聚类方法 一般来说，有两种类型的层次聚类方法： 凝聚层次聚类：采用自底向上策略，首先将每个对象作为单独的一个原子簇，然后合并这些原子簇形成越来越大的簇，直到所有的对象都在一个簇中（层次的最上层），或者达到一个终止条件。绝大多数层次聚类方法属于这一类。 输入：n个对象，终止条件簇的数目k。 输出：k个簇，达到终止条件规定簇数目。 (1)将每个对象当成一个初始簇； (2)REPEAT (3)根据两个簇中最近的数据点找到最近的两个簇； (4)合并两个簇，生成新的簇的集合； (5)UNTIL达到定义的簇的数目；  分裂层次聚类：采用自顶向下策略，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一个簇，或者达到某个终止条件，例如达到了某个希望的簇的数目，或者两个最近的簇之间的距离超过了某个阈值。 输入：n个对象，终止条件簇的数目k。 输出：k个簇，达到终止条件规定簇数目。 （1）将所有对象整个当成一个初始簇； （2） FOR （i=1; i≠k; i++) DO BEGIN （3） 在所有簇中挑出具有最大直径的簇C； （4） 找出C中与其它点平均相异度最大的一个点p并把p放入splinter group，剩余的放在old party中； （5） REPEAT （6） 在old party里找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点，并将该点加入splinter group。 （7） UNTIL 没有新的old party的点被分配给splinter group； （8） splinter group和old party为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。 （9） END. Page ? * Page ? * 例子 下图描述了一种凝聚层次聚类算法和一种分裂层次聚类算法对一个包含五个对象的数据集合{a,b,c,d,e}的处理过程。 Step 0 Step 1 Step 2 Step 3 Step 4 b d c e a a b d e c d e a b c d e Step 4 Step 3 Step 2 Step 1 Step 0 agglomerative divisive 图1 对数据对象{a,b,c,d,e}的凝聚和分裂层次聚类 Page ? * 层次聚类步骤 初始，凝聚层次聚类算法将每个对象自为一簇，然后这些簇根据某种准则逐步合并，直到所有的对象最终合并形成一个簇。 例如，如果簇C1中的一个对象和簇C2中的一个对象之间的距离是所有属于不同簇的对象间欧氏距离中最小的，则C1和C2合并。 在分裂层次聚类算法中，所有的对象用于形成一个初始簇。根据某种原则（如，簇中最近的相邻对象的最大距离），将该簇分裂。簇的分裂过程反复进行，直到最终每个新簇只包含一个对象。 在凝聚或者分裂层次聚类方法中，用户可以定义希望得到的簇数目作为一个终止条件。 Page ? * 树状图 通常，使用一种称作树状图的树形结构表示层次聚类的过程。它展示出对象是如何一步步分组的。图2显示图1的五个对象的树状图。 图2 数据对象{a,b,c,d,e}层次聚类的树状图表示 Page ? * 簇间距离 四个广泛采用的簇间距离度量方法如下，其中|p-p|是两个对象或点p和p之间的距离，mi是簇Ci的均值，而ni是簇Ci中对象的数目。 最小距离： 最大距离： 均值距离： 平均距离： Page ? * 簇间距离 最小距离 最大距离 均值距离 平均距离 Page ? * 当算法使用最小距离 衡量簇间距离时，有时称它为最近邻聚类算法。此外，如果当最近的簇之间的距离超过某个任意的阈值时聚类过程就会终止，则称其为单连接算法。 当一个算法使用最大距离 度量簇间距离时，有时称为最远邻聚类算法。如果当最近簇之间的最大距离超过某个任意阈值时聚类过程便终止，则称其为全连接算法。 Page ? * 单连接算法例子 先将五个样本都分别看成是一个簇，最靠近的两个簇是3和4，因为他们具有最小的簇间距离D（3，4）=5.0。 第一步：合并簇3和4，得到新簇集合1