BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）详解

第三十次写博客，本人数学基础不是太好，如果有幸能得到读者指正，感激不尽，希望能借此机会向大家学习。这一篇作为可伸缩聚类（Scalable Clustering）算法的第三篇，主要是对BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）算法进行详细介绍，其他可伸缩聚类算法的链接可以从《可伸缩聚类算法综述（可伸缩聚类算法开篇）》这篇文章中找到。

CF和CF-Tree

  聚类特征（Clustering Feature，简称CF）是一种用来表征聚类特征的数据格式，他由以下三部分组成：簇中所含样本点的个数（用 N N N来表示）、簇中所有点的各项属性的线性和（用 L S LS LS来表示）以及簇中所有点的各项属性的平方和（用 S S SS SS来表示），假设存在簇 C = { ( 1 , 2 ) , ( 2 , 1 ) , ( 1 , 1 ) , ( 2 , 2 ) } C=\{\left(1,2\right),\left(2,1\right),\left(1,1\right),\left(2,2\right)\} C={
(1,2),(2,1),(1,1),(2,2)}，那么 N = 4 N=4 N=4， L S = ( { 1 + 2 + 1 + 2 } , { 2 + 1 + 1 + 2 } ) = ( 6 , 6 ) LS=\left(\{1+2+1+2\},\{2+1+1+2\}\right)=\left(6,6\right) LS=({
1+2+1+2},{
2+1+1+2})=(6,6)， S S = 1 2 + 2 2 + 1 2 + 2 2 + 2 2 + 1 2 + 1 2 + 2 2 = 20 SS=1^2+2^2+1^2+2^2+2^2+1^2+1^2+2^2=20 SS=12+22+12+22+22+12+12+22=20。因此这种结构具有很好的线性性质，即当需要合并两个簇时，总的聚类特性可以简单的通过两者聚类特性之和来表示。有了上述信息之后，就可以计算簇的质心以及方差（或标准差），其中方差可以用来表征簇的半径，还可以间接的计算两个簇质心之间的距离。
  聚类特征树（Clustering Feature Tree，简称CF-Tree）是一棵高度平衡的树，这棵树由根节点、内部节点（或者称为非叶节点）以及叶节点，其中每个非叶节点和根节点都由形如 [ C F i , c h i l d i ] [CF_{i},child_{i}] [CFi​,childi​]的项组成， c h i l d i child_i childi​代表第 i i i个节点的子节点，而叶节点（或者称为簇）通过 C F i CF_i CFi​组成的序列来表示每个簇的特征，下图（图1）所示是一个CF-Tree实例。

图1 实例

CF-Tree的构建

  如上图（图1）所示，在构建CF-Tree的过程中，其（占用的空间或内存）大小受到以下三方面的约束：非叶节点中所含子结点的个数（用 B B B来表示）、叶结点中所含子簇的个数（用 L L L来表示）以及子簇的半径（用 T T T来表示）， T T T越大树的规模越小，通过这些参数可以有效的控制树的高度以及簇的规模。
  CF-Tree的构建只需要扫描一次数据集就可以完成，每次从数据集中读入一个样本点，然后增量的更新每个节点，下面对该过程进行简要描述：

1)读取到一个样本点后，从根节点开始遍历整个树，并将这个样本点加入到最近的结点中，当遍历到距离最近的叶结点时，根据不同的情况执行步骤2或3；如果将该样本点加入到叶结点的某个距离最近的子簇中，而不会使得该子簇的半径大于之前设定的阈值 T T T，那么就将该样本加入并对该子簇的聚类特征进行更新，本次更新结束；

2)如果将该样本点加入到叶结点的某个距离最近的子簇中，使得该子簇的半径大于之前设定的阈值 T T T，根据具体情况执行步骤4或5；

3)如果将该样本点作为一个新的子簇加入到该叶节点中，而不会使得叶结点中所含子簇的个数大于阈值 L L L，那么就执行创建新子簇的操作，本次更新结束；

4)如果将该样本点作为一个新的子簇加入到该叶节点中，使得叶结点中所含子簇的个数大于阈值 L L L，那么就将当前叶节点分裂为两个叶节点，分裂方法是从当前叶节点中选择距离最远的两个子簇作为“种子”，再将该叶结点下的其他子簇划分到距离最近的“种子”所在的组中，这两个组就是分裂后形成的新叶节点，然后根据具体情况执行步骤6或7；

5)如果分裂产生的叶节点数量不大于其所在非叶节点中所要求的的上限 B B B时，本次更新结束；

6)如果分裂产生的叶节点数量大于其所在非叶节点中所要求的的上限 B B B时，继续使用类似于上述步骤5中的方法对该非叶节点进行分裂，并向上递归直到满足约束条件为止。
  下面通过一个实例来进行说明，在根节点为空时读入一个样本点，然后将该点放入叶节点的子簇A中并更新根节点和A（图2），

图2 加入一个样本点

然后加入第二个样本点，该样本点与上一个样本点同时放在A中不会使得A的半径超过阈值 T T T的限制并对 A进行更新（图3），

图3 加入第二个样本点

再读入一个样本点，该样本点加入A后使得半径超过阈值 T T T，因此将其作为一个新的子簇加到根节点下（图4），

图4 加入第三个样本点

再读入第四个样本点，这个样本点与B的距离最近并且加入到B中不会违反约束条件，因此将其加入到B中（图5），

图5 加入第四个样本点

在多次读入样本点后得到一棵层数为3的CF-Tree，再读入下一个样本点后，向下递归寻找距离其最近的叶结点，由于子簇半径的约束 T T T，故将其作为新的子簇加入到叶节点LN1中（图6），

图6 加入样本点到叶节点中

如果发现此时叶节点中的子簇数量超过阈值 L L L，那么就对叶节点LN1进行分裂操作，得到LN1’和LN1”（图7），

图7 分裂叶节点

在上一步分裂叶节点的过程中发现，根节点中的子节点数目超过阈值 B B B，这时需要对根节点进行分裂，并使树的层数增一，得到非叶节点NLN1和NLN2（图8）。

图8 分裂根节点产生非叶节点

BIRCH算法

  BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）算法主要分为以下四步：
  1)扫描一遍数据集汇总数据，生成初始的CF-Tree并存储在内存中；
  2)通过再创建一棵较小的CF-Tree，将初始的CF-Tree压缩到期望的长度；
  3)进行全局聚类；
  4)对聚类结果进行细化，这一步是可选的而且往往需要更多次的数据传递来细化结果。
下面分别对这四步进行详细描述。
(1)扫描一遍数据集汇总数据，生成初始的CF-Tree并存储在内存中
  a)在设置好初始阈值（ B B B、 L L L、 T T T）后，开始向树中插入数据；
  b)对节点进行分裂后，往往跟随一个合并步，在分裂停止的内部节点中，找出两个距离最近的节点，如果这两个节点不是由同一个节点分裂产生的，那么就递归的合并这两个节点及其子节点，这个操作是为了提高空间利用率，并且避免由数据输入顺序带来的问题；
  c)如果在构建树的过程中内存用尽，那么就要提高阈值，并且通过将原CF-Tree中的值根据重新设置好的阈值进行重新插入来创建一个较小的树，并将数据集中剩下的样本点插入到这个树中；
  d)可以看出选择较好的初始阈值很重要，但是难以通过计算得出；
  e)在b中进行树的重建时，可以根据原CF-Tree找出数据集中的离群点，并将它们写入内存中，在重建过程中，可以对这些离群点进行扫描，看是否可以将它们加入到树中，而不导致树增长，如果可以就吸收它们，如果不可以，就丢弃它们。
(2)通过再创建一棵较小的CF-Tree，将初始的CF-Tree压缩到期望的长度
  a)这一步是可选的；
  b)有些时候第3步需要最小规模的树来达到更好的聚类效果，这时就需要这一步为其做好准备；
  c)这一步与第1步中重建CF-Tree的过程是同样的，为了减小树的大小都需要将阈值提高，来使得某些簇合并到一起。
(3)进行全局聚类
  a)由于第1不执行过后会存在两个问题：样本点输入顺序对结果会产生影响、节点大小会触发分裂而导致一个完整的簇被分开，因此需要对叶节点使用已有的聚类方法进行全局聚类；
  b)这里使用的聚类方法是凝聚层次聚类。
(4)对聚类结果进行细化，这一步是可选的而且往往需要更多次的数据传递来细化结果
  a)这一步是可选的；
  b)根据上一步发现的质心，对数据集重新扫描，并将样本点分配到这些质心所属的簇中；
  c)更新质心和然后重新分配样本点；
  d)重复上述操作直到算法收敛；
  e)实际上这一步相当是使用上一步得到的质心作为K-Means的初始质心，在进行K-Means聚类得到最终的聚类模型。

----

参考资料

【1】《机器学习》周志华
【2】文中CF-Tree图片来自BIRCH：使用聚类特征树（CF-树）的多阶段聚类算法
【3】《Birch: An efficient data clustering method for very large databases》Zhang, T., Ramakrishnan, R., & Livny, M.