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