2017/12/8
构造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值。
2017/12/8
插入一个节点

当又有一个数据点要插入树中时，把这个点封装 为一个MinCluster（这样它就有了一个CF值）， 把新到的数据点记为CF_new，我们拿到树的根 节点的各个孩子节点的CF值，根据D2来找到 CF_new与哪个节点最近，就把CF_new加入那个 子树上面去。这是一个递归的过程。递归的终止 点是要把CF_new加入到一个MinCluster中，如 果加入之后MinCluster的直径没有超过T，则直接 加入，否则譔CF_new要单独作为一个簇，成为 MinCluster的兄弟结点。插入之后注意更新该节 点及其所有祖先节点的CF值。

2017/12/8
CF树的样子
2017/12/8
CF Tree
B=5 CF1
child1
Root CF2 CF3
child2 child3
CF6
child6
L=6
Non-leaf node CF1
child1
CF2 CF3
child2 child3
CF5
child5
Leaf node
prev CF1 CF2



2017/12/8
簇的质心和簇的半径。
假如一个簇中包含n个数据点：{Xi}，i=1,2,3...n.， 则质心C和半径R计算公式如下： C=(X1+X2+...+Xn)/n，（这里X1+X2+...+Xn是向 量加） R=(|X1-C|^2+|X2-C|^2+...+|Xn-C|^2)/n 其中，簇半径表示簇中所有点到簇质心的平均距 离。CF中存储的是簇中所有数据点的特性的统计 和，所以当我们把一个数据点加入某个簇的时候， 那么这个数据点的详细特征，例如属性值，就丢 失了，由于这个特征，BIRCH聚类可以在很大程 度上对数据集进行压缩。
ab abcde cde de
Step 3 Step 2 Step 1 Step 0
divisive (DIANA)
2017/12/8
AGNES (Agglomerative Nesting)
由 Kaufmann和Rousseeuw提出(1990) 已在一些统计分析软件包中实现 . 如 Splus 使用单链接(Single-Link)方法和相异度矩阵 合并具有最小相异度的节点 以非递减的方式继续 最终所有的节点属于同一个簇
2017/12/8
BIRCH (1996)

Birch (Balanced Iterative Reducing and Clustering using Hierarchies): 利用层次方法的平衡迭代归约和聚类由Zhang, Ramakrishnan和Livny 提出(SIGMOD’96), 该算法的特点是能利用有限的内存资源完成对大数 据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。

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 10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10
2017/12/8
DIANA (Divisive Analysis)
2017/12/8
CF tree的结构类似于一棵B-树，它有3个参数： 内部节点平衡因子B，叶节点平衡因子L，簇直径 阈值T。树中每个Nlonleaf节点最多包含B个孩子 节点，Leaf最多只能有L个MinCluster（初始划分 子簇），而一个MinCluster的直径不能超过T。 例如，一棵高度为3，B为6，L为5的一棵CF树的 例子如图所示：
其中, |p-p’|是两个对象p和p’之间的距离 mi是簇Ci 的平均值，ni是簇Ci中对象的数目
2017/12/8
层次方法(续)

层次聚类的主要缺点

不具有很好的可伸缩性: 时间复杂性至少是 O(n2), 其中 n 对象总数 合并或分裂的决定需要检查和估算大量的对象或簇 不能撤消已做的处理, 聚类之间不能交换对象. 如果某一步没有很好地 选择合并或分裂的决定, 可能会导致低质量的聚类结果
CF ( N , LS , SS)
聚类特征
Clustering Feature:CF = (N, LS, SS) N: 数据点数目 LS: Ni=1 Xi SS: Ni=1Xi2
10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10
CF = (5, (16,30),(54,190))

CF 树是高度平衡的树，它存储了层次聚类的聚类特征

树中的非叶节点有后代或“孩子”
非叶节点存储了其孩子的CF的总和，即汇总了关于其孩子的聚类信 息 分支因子B: 定义非树叶节点的孩子的最大个数 阈值T: 给出了存储在树的叶子节点中的子类的最大直径

CF树有两个参数 ----影响CF树的大小


2017/12/8
BIRCH算法流程如下图所示：

BIRCH算法流程如下图所示：

2017/12/8
BIRCH (续)

重建过程从旧树的叶子节点建造一个新树。这样，重建树的过程不需要重 读所有的对象 ----建树只需读一次数据

2017/12/8
有意思的是簇中心、簇半径、簇直径以及两簇之 间的距离D0到D3都可以由CF来计算，比如 簇直径 簇间距离 这里的N，LS和SS是指两簇合并后大簇的N，LS 和SS。所谓两簇合并只需要两个对应的CF相加 那可

2Байду номын сангаас17/12/8
BIRCH的CF树

聚类特征

从统计学的观点来看，聚类特征是对给定子类统计汇总: 子聚类的0 阶, 1阶和 2阶矩( moments ) 记录了计算聚类和有效利用存储的关键度量, 并有效地利用了存储,因 为它汇总了关于子类的信息，而不是存储所有的对象
10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10
2017/12/8
层次方法(续)

四个广泛采用的簇间距离度量方法

最小距离：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’| /n i n j

使用距离矩阵作为聚类标准. 该方法不需要输入聚类数目 k, 但需要终止条件
2017/12/8
层次方法(续)

凝聚的(agglomerative)和分裂的(divisive)层次聚类图示
Step 0 Step 1 Step 2 Step 3 Step 4
a
b c d e
Step 4
agglomerative (AGNES)

两个重要概念

聚类特征(Clustering Feature, CF) 聚类特征树(Clustering Feature Tree, CF树) 聚类特征(CF)是一个三元组，给出对象子类的信息的汇总描述 设某个子类中有N个d维的点或对象{oI}，则该子类的CF定义如下

聚类特征

2017/12/8
由 Kaufmann和Rousseeuw提出 (1990) 已在一些统计分析软件包中实现 . 如 Splus 是 AGNES的逆 最终每个节点自己形成一个簇

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
Leaf node
prev CF1 CF2
CF6 next
CF4 next
2017/12/8
CF树构造过程




(1)从根节点开始，自上而下选择最近的孩子节点 (2)到达叶子节点后，检查最近的元组CFi能否吸收此数 据点 是，更新CF值 否，是否可以添加一个新的元组 是，添加一个新的元组 否则，分裂最远的一对元组，作为种子，按最近 距离重新分配其它元组 (3)更新每个非叶节点的CF信息，如果分裂节点，在父 节点中插入新的元组，检查分裂，直到root
2017/12/8
层次方法(续)

改进层次方法的聚类质量的方法: 将层次聚类和其他的聚类 技术进行集成, 形成多阶段聚类


BIRCH (1996): 使用 CF-tree对对象进行层次划分, 然后采用其他的聚 类算法对聚类结果进行求精 ROCK1999：基于簇间的互联性进行合并 CHAMELEON (1999): 使用动态模型进行层次聚类 CURE (1998):采用固定数目的代表对象来表示每个簇，然后依据一 个指定的收缩因子向着聚类中心对它们进行收缩