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