聚类分析—层次聚类.ppt

文档介绍：智能数据挖掘
Topic3--聚类分析
层次聚类方法(Hierarchical Methods)
层次方法
层次的聚类方法将数据对象组成一棵聚类的树
根据层次分解是自底向上, 还是自顶向下形成, 层次的聚类方法可以进一步分为凝聚的(agglomerative)和分裂的(divisive)层次聚类
纯粹的层次聚类方法的聚类质量受限于如下特点:一旦一个合并或分裂被执行,就不能修正
最近的研究集中于凝聚层次聚类和迭代重定位方法的集成
使用距离矩阵作为聚类标准. 该方法不需要输入聚类数目 k, 但需要终止条件
2/9/2018
层次方法(续)
凝聚的(agglomerative)和分裂的(divisive)层次聚类图示
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)
2/9/2018
AGNES (Agglomerative Nesting)
由 Kaufmann和Rousseeuw提出(1990)
已在一些统计分析软件包中实现. 如 Splus
使用单链接(Single-Link)方法和相异度矩阵
合并具有最小相异度的节点
以非递减的方式继续
最终所有的节点属于同一个簇
2/9/2018
DIANA (Divisive Analysis)
由 Kaufmann和Rousseeuw提出(1990)
已在一些统计分析软件包中实现. 如 Splus
是 AGNES的逆
最终每个节点自己形成一个簇
2/9/2018
层次方法(续)
四个广泛采用的簇间距离度量方法
最小距离:dmin(Ci,Cj) = min p∈Ci, p’∈Cj |p-p’|
最大距离:dmax(Ci,Cj) = max p∈Ci, p’∈Cj |p-p’|
平均值的距离:dmean(Ci,Cj) = | mi - mj |
平均距离(簇的直径D ):davg(Ci,Cj) =∑ p∈Ci ∑p’∈Cj |p-p’| /ninj
其中, |p-p’|是两个对象p和p’之间的距离
mi是簇Ci 的平均值,ni是簇Ci中对象的数目
2/9/2018
层次方法(续)
层次聚类的主要缺点
不具有很好的可伸缩性: 时间复杂性至少是 O(n2), 其中 n 对象总数
合并或分裂的决定需要检查和估算大量的对象或簇
不能撤消已做的处理, 聚类之间不能交换对象. 如果某一步没有很好地选择合并或分裂的决定, 可能会导致低质量的聚类结果
2/9/2018
层次方法(续)
改进层次方法的聚类质量的方法: 将层次聚类和其他的聚类技术进行集成, 形成多阶段聚类
BIRCH (1996): 使用 CF-tree对对象进行层次划分, 然后采用其他的聚类算法对聚类结果进行求精
ROCK1999:基于簇间的互联性进行合并
CHAMELEON (1999): 使用动态模型进行层次聚类
CURE (1998):采用固定数目的代表对象来表示每个簇,然后依据一个指定的收缩因子向着聚类中心对它们进行收缩
2/9/2018
BIRCH (1996)
Birch (Balanced Iterative Reducing and Clustering using Hierarchies): 利用层次方法的平衡迭代归约和聚类由Zhang, Ramakrishnan和Livny 提出(SIGMOD’96), 该算法的特点是能利用有限的内存资源完成对大数据集的高质量的聚类,同时通过单遍扫描数据集能最小化I/O代价。
两个重要概念
聚类特征(Clustering Feature, CF)
聚类特征树(Clustering Feature Tree, CF树)
聚类特征
聚类特征(CF)是一个三元组,给出对象子类的信息的汇总描述
设某个子类中有N个d维的点或对象{oI},则该子类的CF定义如下
2/9/2018
聚类特征
Clustering Feature:CF = (N, LS, SS)
N: 数据点数目
LS: Ni=1 Xi
SS: Ni=1Xi2
CF = (5, (16,30),(54,190))
(3,4)
(2,6)
(4,5)
(4,7)
(3,8)
2/9/2018