10
9
8
7
6
5
4
3 2
1
0 0
1
2
3
4
5
6
7
8
9
10
6/6/2020
10
9
8
7 6
5
4
3
2
1
0 0
1
2
3
4
5
6
7
8
9
10
10
9
8
7
6
5
4
3 2
1
0 0
1
2
3
4
5
6
7
8
9
10
层次方法(续)
四个广泛采用的簇间距离度量方法
最小距离：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’|
智能数据挖掘
Topic3--聚类分析
层次聚类方法（Hierarchical Methods）
层次方法
层次的聚类方法将数据对象组成一棵聚类的树 根据层次分解是自底向上, 还是自顶向下形成, 层次的聚类方
法可以进一步分为凝聚的(agglomerative)和分裂的(divisive) 层次聚类 纯粹的层次聚类方法的聚类质量受限于如下特点：一旦一个 合并或分裂被执行，就不能修正 最近的研究集中于凝聚层次聚类和迭代重定位方法的集成 使用距离矩阵作为聚类标准. 该方法不需要输入聚类数目 k, 但需要终止条件
在阶段三和四采用任何聚类算法，例如典型的划分方法 BIRCH的性能
支持增量聚类：因为它对每一个数据点的聚类的决策都是基于当前 已经处理过的数据点，而不是基于全局的数据点。
线性可伸缩性: 计算复杂性O(n), 单遍扫描, 附加的扫描可以改善聚类 质量
较好的聚类质量
缺点
只能处理数值数据 对数据的输入次序敏感 CF树结点不总是对应于[用户考虑的]自然簇(参数B和T) 簇非球形时效果不好(使用半径/直径控制簇边界)
Ø 阶段四：通过上阶段得出聚类质心，将其作为 种子节点，将其他对象分配给质心，构成新的聚 类。
6/6/2020
BIRCH算法流程如下图所示：
BIRCH算法流程如下图所示：
6/6/2020
BIRCH (续)
重建过程从旧树的叶子节点建造一个新树。这样，重建树的过程不需要重 读所有的对象 ----建树只需读一次数据
Leaf node
prev CF1 CF2
CF6 next
CF5
child5
prev CF1 CF2
Leaf node CF4 next
6/6/2020
CF树构造过程
(1)从根节点开始，自上而下选择最近的孩子节点
(2)到达叶子节点后，检查最近的元组CFi能否吸收此数 据点
是，更新CF值
否，是否可以添加一个新的元组
分支因子B: 定义非树叶节点的孩子的最大个数 阈值T: 给出了存储在树的叶子节点中的子类的最大直径
6/6/2020
CF tree的结构类似于一棵B-树，它有3个参数： 内部节点平衡因子B，叶节点平衡因子L，簇直径 阈值T。树中每个Nlonleaf节点最多包含B个孩子 节点，Leaf最多只能有L个MinCluster（初始划分 子簇），而一个MinCluster的直径不能超过T。
是，添加一个新的元组
否则，分裂最远的一对元组，作为种子，按最近
距离重新分配其它元组
(3)更新每个非叶节点的CF信息，如果分裂节点，在父 节点中插入新的元组，检查分裂，直到root
6/6/2020
构造CF树
算法起初，我们扫描数据库，拿到第一个data point instance--（1,2,3）,我们创建一个空的Leaf 和MinCluster，把点（1,2,3）的id值放入 Mincluster，更新MinCluster的CF值为（1, （1,2,3），（1,4,9）），把MinCluster作为Leaf 的一个孩子，更新Leaf的CF值为（1,（1,2,3）， （1,4,9））。实际上只要往树中放入一个CF （这里我们用CF作为Nonleaf、Leaf、 MinCluster的统称），就要更新从Root到该叶子 节点的路径上所有节点的CF值。
因此得到CF3为： CF3=（2+3，（4+5，4+4，4+5），（10+9，8+6，10+9））=（5，
（9，8，9），（19，14，19））
6/6/2020
簇的质心和簇的半径。
假如一个簇中包含n个数据点：{Xi}，i=1,2,3...n.， 则质心C和半径R计算公式如下：
C=(X1+X2+...+Xn)/n，（这里X1+X2+...+Xn是向 量加）
6/6/2020
Birch算法的阶段：
Ø 阶段一：扫描数据库，构造一颗CF树，并定 义相关阈值，把稠密数据分成簇。
Ø 阶段二：对CF树进行压缩，通过改变T值，将 部分簇进行压缩合并，建立一个更小的CF树。
Ø 阶段三：采用其他的聚类算法对其叶节点进行 聚类，将稀疏的簇当作离群值进行删除，补救由 于输入顺序和页面大小带来的分裂。
记录了计算聚类和有效利用存储的关键度量, 并有效地利用了存储,因 为它汇总了关于子类的信息，而不是存储所有的对象
CF 树是高度平衡的树，它存储了层次聚类的聚类特征
树中的非叶节点有后代或“孩子” 非叶节点存储了其孩子的CF的总和，即汇总了关于其孩子的聚类信
息
CF树有两个参数 ----影响CF树的大小
6/6/2020
有意思的是簇中心、簇半径、簇直径以及两簇之 间的距离D0到D3都可以由CF来计算，比如
簇直径 簇间距离 这里的N，LS和SS是指两簇合并后大簇的N，LS
和SS。所谓两簇合并只需要两个对应的CF相加 那可
6/6/2020
BIRCH的CF树
聚类特征
从统计学的观点来看，聚类特征是对给定子类统计汇总: 子聚类的0 阶, 1阶和 2阶矩( moments )
两个重要概念
聚类特征(Clustering Feature, CF) 聚类特征树(Clustering Feature Tree, CF树)
聚类特征
聚类特征(CF)是一个三元组，给出对象子类的信息的汇总描述
设某个子类中有N个d维的点或对象{oI}，则该子类的CF定义如下
6/6/2020
C F (N ,L S
假定簇C1中有两个点（1，2，3），（3，2，1），簇C2 有三个点（1，1，2），（2，2，1），（2，1，2），簇 3由C1和C2构成，则：
CF1=（2，（1+3，2+2，3+1），（ ））=（2，（4，4，4）， （10，8，10））
CF2=（3，（1+2+2，1+2+1，2+1+2），（ ））=（3，（5，4， 5），（9，6，9））
聚类特征
Clustering Feature:CF = (N, LS, SS)
N: 数据点数目
LS: Ni=1 Xi SS: Ni=1Xi2
CF = (5, (16,30),(54,190))
10
9
8
7
6
5
4
3 2
1
0 0
1
2
3
4
5
6
7
8
9
10
(3,4) (2,6) (4,5) (4,7) (3,8)
/ninj
其中, |p-p’|是两个对象p和p’之间的距离 mi是簇Ci 的平均值，ni是簇Ci中对象的数目
6/6/2020
层次方法(续)
层次聚类的主要缺点
不具有很好的可伸缩性: 时间复杂性至少是 O(n2), 其中 n 对象总数 合并或分裂的决定需要检查和估算大量的对象或簇 不能撤消已做的处理, 聚类之间不能交换对象. 如果某一步没有很好地
个指定的收缩因子向着聚类中心对它们进行收缩
6/6/2020
BIRCH (1996)
Birch (Balanced Iterative Reducing and Clustering using Hierarchies): 利用层次方法的平衡迭代归约和聚类由Zhang, Ramakrishnan和Livny 提出(SIGMOD’96), 该算法的特点是能利用有限的内存资源完成对大数 据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。
选择合并或分裂的决定, 可能会导致低质量的聚类结果
6/6/2020
层次方法(续)
改进层次方法的聚类质量的方法: 将层次聚类和其他的聚类 技术进行集成, 形成多阶段聚类
BIRCH (1996): 使用 CF-tree对对象进行层次划分, 然后采用其他的聚 类算法对聚类结果进行求精
ROCK1999：基于簇间的互联性进行合并 CHAMELEON (1999): 使用动态模型进行层次聚类 CURE (1998):采用固定数目的代表对象来表示每个簇，然后依据一
例如，一棵高度为3，B为6，L为5的一棵CF树的 例子如图所示：
6/6/2020
CF树的样子
6/6/2020
CF Tree
Root
B=5 L=6
CF1 CF2 CF3
child1 child2 child3
CF6
child6
Non-leaf node CF1 CF2 CF3