引言

BIRCH聚类算法属于增量聚类算法，聚类的过程只需要单遍依次遍历数据集中的样本即可以完成聚类，不需要一次性全部把所有样本加载到内存完成聚类。因此该算法比较适合大数据量，增量型的聚类过程。BIRCH聚类是一个构建Cluster Feature Tree的过程，而Cluster Feature Tree和B+树非常相似，因此了解BIRCH聚类算法之前，有必要了解一下B+树。

BIRCH相关概念

Cluster Feature 聚类特征

Cluster Feature 简称CF，一个CF是一个三元组，可以用（N，LS，SS）表示。其中N代表了这个CF中拥有的样本点的数量，这个好理解；LS代表了这个CF中拥有的样本点各特征维度的和向量 $\vec{LS}=\sum_{i=1}^{N}\vec{X_i}$ ，SS代表了这个CF中拥有的样本点各特征维度的平方和 $SS=\sum_{i=1}^{N}(\vec{X_i})^2$ 。举例说明，如下面五个样本点所示： $X=\{(3,4),(2,6),(4,5),(4,7),(3,8)\}$ ， $\vec{LS}=(3+2+4+4+3,4+6+5+7+8)=(16,30)$ , $SS=(3^2+2^2+4^2+4^2+3^2+4^2+6^2+5^2+7^2+8^2)=244$ 。
CF有一个很好的性质，就是满足线性关系，也就是 $CF_1+CF_2=(N_1+N_2, LS_1+LS_2,SS_1+SS_2)$ 。这个性质从定义也很好理解。如果把这个性质放在CF Tree上，也就是说，在CF Tree中，对于每个父节点中的CF节点，它的 $(N,\vec{LS},SS)$ 三元组的值等于这个CF节点所指向的所有子节点的三元组之和。如下图所示：

image.png

从上图中可以看出，根节点的 $CF_1$ 的三元组的值，可以从它指向的6个子节点 $(CF_7到CF_{12})$ 的值相加得到。这样我们在更新CF Tree的时候，可以很高效。
对于CF Tree，我们一般有几个重要参数，第一个参数是每个内部节点的最大CF数B，第二个参数是每个叶子节点的最大CF数L，第三个参数是针对叶子节点中某个CF中的样本点来说的，它是叶节点每个CF的最大样本半径阈值T，也就是说，在这个CF中的所有样本点一定要在半径小于T的一个超球体内。对于上图中的CF Tree，限定了B=7， L=5，也就是说内部节点最多有7个CF，而叶子节点最多有5个CF。

Cluster Feature Tree 聚类特征树

Cluster Feature Tree简记为CF Tree，其中的每一个节点由若干个CF组成。构建CF Tree的过程就是对样本完成聚类。构建CF Tree的过程如下：

在最开始的时候，CF Tree是空的，没有任何样本，我们从训练集读入第一个样本点，将它放入一个新的CF三元组A，这个三元组的N=1，将这个新的CF放入根节点，此时的CF Tree如下图：

image.png
现在我们继续读入第二个样本点，我们发现这个样本点和第一个样本点A，在半径为T的超球体范围内，也就是说，他们属于一个CF，我们将第二个点也加入CF A,此时需要更新A的三元组的值。此时A的三元组中N=2。此时的CF Tree如下图：

image.png
此时来了第三个节点，结果我们发现这个节点不能融入刚才前面的节点形成的超球体内，也就是说，我们需要一个新的CF三元组B，来容纳这个新的值。此时根节点有两个CF三元组A和B，此时的CF Tree如下图：

image.png
当来到第四个样本点的时候，我们发现和B在半径小于T的超球体，这样更新后的CF Tree如下图：

image.png
那个什么时候CF Tree的节点需要分裂呢？假设我们现在的CF Tree 如下图，叶子节点LN1有三个CF， LN2和LN3各有两个CF。我们的叶子节点的最大CF数L=3。此时一个新的样本点来了，我们发现它离LN1节点最近，因此开始判断它是否在sc1,sc2,sc3这3个CF对应的超球体之内，但是很不幸，它不在，因此它需要建立一个新的CF，即sc8来容纳它。问题是我们的L=3，也就是说LN1的CF个数已经达到最大值了，不能再创建新的CF了，怎么办？此时就要将LN1叶子节点一分为二了。

image.png
我们将LN1里所有CF元组中，找到两个最远的CF做这两个新叶子节点的种子CF，然后将LN1节点里所有CF sc1, sc2, sc3，以及新样本点的新元组sc8划分到两个新的叶子节点上。将LN1节点划分后的CF Tree如下图：

image.png
如果我们的内部节点的最大CF数B=3，则此时叶子节点一分为二会导致根节点的最大CF数超了，也就是说，我们的根节点现在也要分裂，分裂的方法和叶子节点分裂一样，分裂后的CF Tree如下图：

image.png
总结CF Tree的建树过程如下：
第一步：从根节点开始向下寻找与新样本距离最近的叶子节点（PS. 没有去阅读原论文，个人直觉猜测这里的距离计算应该是通过CF三元组中的 $\vec{LS}$ 计算得到），以及找到该叶子节点中和新样本距离最近的CF。
第二步：如果新样本插入CF后，该CF对应的超球体半径依然小于预设的阈值T，则更新路径中所有的CF三元组，新样本插入结束，否则转入3。
第三步：如果新样本加入当前叶子节点中任何一个CF，超球体半径都会超过阈值T，并且此时叶子节点的CF个数小于L，则新建一个CF并将新样本纳入其中，更新路径上所有的CF三元组，插入结束。
第四步：如果第三步中叶子节点中的CF数量已经超过了L个，则将当前叶子节点划分为两个新叶子节点，选择旧叶子节点中所有CF三元组里超球体距离最远的两个CF元组，分别作为两个新叶子节点的第一个CF节点。将其他元组和新样本元组按照距离远近原则放入对应的叶子节点。依次向上检查父节点是否也要分裂，如果需要按和叶子节点分裂方式相同。

BIRCH算法

上面讲了半天的CF Tree，终于我们可以步入正题BIRCH算法，其实将所有的训练集样本建立了CF Tree，一个基本的BIRCH算法就完成了，对应的输出就是若干个CF节点，每个节点里的样本点就是一个聚类的簇。也就是说BIRCH算法的主要过程，就是建立CF Tree的过程。
当然，真实的BIRCH算法除了建立CF Tree来聚类，其实还有一些可选的算法步骤的，现在我们就来看看 BIRCH算法的流程。

将所有的样本依次读入，在内存中建立一颗CF Tree, 建立的方法参考上一节。
2.（可选）将第一步建立的CF Tree进行筛选，去除一些异常CF节点，这些节点一般里面的样本点很少。对于一些超球体距离非常近的元组进行合并
3.（可选）利用其它的一些聚类算法比如K-Means对所有的CF元组进行聚类，得到一颗比较好的CF Tree.这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构，以及一些由于节点CF个数限制导致的树结构分裂。
4.（可选）利用第三步生成的CF Tree的所有CF节点的质心，作为初始质心点，对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。
从上面可以看出，BIRCH算法的关键就是步骤1，也就是CF Tree的生成，其他步骤都是为了优化最后的聚类结果。

总结：

BIRCH算法的主要优点有：

节约内存，所有的样本都在磁盘上，CF Tree仅仅存了CF节点和对应的指针。
聚类速度快，只需要一遍扫描训练集就可以建立CF Tree，CF Tree的增删改都很快。
可以识别噪音点，还可以对数据集进行初步分类的预处理
BIRCH算法的主要缺点有：
由于CF Tree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同.
对高维特征的数据聚类效果不好。此时可以选择Mini Batch K-Means;
如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。

参考文献：

https://www.cnblogs.com/pinard/p/6179132.html

BIRCH(Balanced Iterative Reducing and Clustering Using Hierarchies)