5.2.2 BIRCH聚类算法原理
BIRCH是一个综合的层次聚类算法，比较适合于数据量大、类别数k也比较多的情况。它运行速度很快，只需要单遍扫描数据集就能进行聚类，当然需要用到一些技巧。下面简单介绍BIRCH算法。
1.BIRCH概述
BIRCH的全称是利用层次方法的平衡迭代规约和聚类（balanced iterative reducing and clustering using hierarchies），从名字可以看出其主要是用层次方法来聚类和规约数据。
BIRCH算法利用了一个树结构来快速聚类，这个数结构类似于平衡B+树，一般将它称为聚类特征树（clustering feature tree，CF Tree）。这棵树的每一个节点是由若干个聚类特征（clustering feature，CF）组成。其主要特征是：每个节点包括叶子节点都有若干个CF，而内部节点的CF有指向孩子节点的指针，所有的叶子节点用一个双向链表链接起来。
有了聚类特征树的概念，我们再对聚类特征树和其中节点的聚类特征CF做进一步的讲解。
2.聚类特征CF与聚类特征树CF Tree
在聚类特征树中，一个聚类特征CF是这样定义的：每一个CF是一个三元组，可以用（N，LS，SS）表示。其中，N代表了这个CF中拥有的样本点的数量；LS代表了这个CF中拥有的样本点各特征维度的和向量；SS代表了这个CF中拥有的样本点各特征维度的平方和。
如图5-2所示的例子，在CF Tree中的某一个节点的某一个CF中，有5个样本（3，4），（2，6），（4，5），（4，7），（3，8），则它对应的：
图5-2 聚类特征树实例
CF有一个很好的性质，就是满足线性关系，即
这个性质从定义上也很好理解。如果把这个性质放在CF Tree上，也就是说，在CF Tree中，对于每个父节点中的CF节点，它的（N，LS，SS）三元组的值等于这个CF节点所指向的所有子节点的三元组之和，如图5-3所示。
图5-3 聚类特征线性性质
从图5-3可以看出，根节点的CF1的三元组值，可以从它指向的6个子节点的CF7～CF12的三元组值相加得到。这样在更新CF Tree时，可以很高效。
对于CF Tree，一般有几个重要参数：第一个参数是每个内部节点的最大CF数B；第二个参数是每个叶子节点的最大CF数L；第三个参数是针对叶子节点中某个CF中的样本点，它是叶子节点每个CF的最大样本半径阈值T，也就是说，在这个CF中的所有样本点一定要在半径小于T的一个超球体内。对于图5-3中的CF Tree，限定了B=7，L=5，即内部节点最多有7个CF，而叶子节点最多有5个CF。
3.聚类特征树CF Tree的生成
下面介绍CF Tree的生成过程。首先定义好CF Tree的参数，即内部节点的最大CF数B，叶子节点的最大CF数L，叶子节点每个CF的最大样本半径阈值T。
在最开始的时候，CF Tree是空的，没有任何样本，我们从训练集读入第一个样本点，将它放入一个新的CF三元组A，这个三元组的N=1，将这个新的CF放入根节点，此时的CF Tree如图5-4所示。
继续读入第二个样本点，可以发现这个样本点和第一个样本点A都在半径为T的超球体范围内，也就是说，它们属于一个CF，将第二个点也加入CF A，此时需要更新A的三元组值。此时A的三元组中N=2，CF Tree如图5-5所示。
图5-4 N=1时的CF Tree
图5-5 N=2时的CF Tree
继续读入第三个节点，如果该这个节点不能融入前面的节点形成的超球体内，那么需要增加一个新的CF三元组B，来容纳这个新的值。此时根节点有两个CF三元组A和B，此时的CF Tree如图5-6所示。
当读入第四个样本点时，如果发生新样本点和样本点B都在半径小于T的超球体内，则更新后的CF Tree如图5-7所示。
图5-6 N=3时的CF Tree
图5-7 N=4时的CF Tree
那么什么时候CF Tree的节点需要分裂呢？假设现在的CF Tree如图5-8所示，叶子节点LN1有3个CF，LN2和LN3各有2个CF。叶子节点的最大CF数L=3。此时读入一个新的样本点，发现它离LN1节点最近，因此开始判断它是否在sc1、sc2、sc3这3个CF对应的超球体内，但是很不幸，它不在，因此它需要建立一个新的CF，即sc8来容纳它。问题是L=3，也就是说LN1的CF个数已经达到最大值，不能再创建新的CF了，那怎么办呢？此时就要将LN1叶子子节点一分为二了。(https://www.daowen.com)
图5-8 CF Tree的分裂
在LN1里所有CF三元组中，首先找到2个最远的CF做这两个新叶子节点的种子CF，然后将LN1节点里所有CF sc1、sc2、sc3，以及新样本点的新元组sc8划分到两个新的叶子节点上。将LN1节点划分后的CF Tree如图5-9所示。
图5-9 划分后的CF Tree
如果内部节点的最大CF数B=3，则此时叶子节点一分为二会导致根节点的最大CF数超了，也就是说，根节点也要分裂，分裂的方法和叶子节点分裂一样，分裂后的CF Tree如图5-10所示。
图5-10 分裂后的CF Tree
CF Tree的插入总结如下：
（1）从根节点向下寻找与新样本距离最近的叶子节点和叶子节点里最近的CF节点；
（2）如果新样本加入后，这个CF节点对应的超球体半径仍然满足小于阈值T，则更新路径上所有的CF三元组，插入结束，否则转入（3）；
（3）如果当前叶子节点的CF节点个数小于阈值L，则创建一个新的CF节点，放入新样本，将新的CF节点放入这个叶子节点，更新路径上所有的CF三元组，插入结束，否则转入（4）；
（4）将当前叶子节点划分为2个新叶子节点，选择旧叶子节点中所有CF三元组里超球体距离最远的2个CF三元组，分布作为2个新叶子节点的第一个CF节点。将其他三元组和新样本三元组按照距离远近原则放入对应的叶子节点。依次向上检查父节点是否也要分裂，如果需要则按叶子节点相同的分裂方式进行。
4.BIRCH算法
一个基本的BIRCH算法其实将所有的训练集样本建立了CF Tree，对应的输出就是若干个CF节点，每个节点里的样本点就是一个聚类的簇。也就是说，BIRCH算法的主要过程就是建立CF Tree的过程。下面具体介绍BIRCH算法的流程。
（1）将所有的样本依次读入，建立一棵CF Tree，建立的方法参考上一节。
（2）（可选）将第一步建立的CF Tree进行筛选，去除一些异常CF节点，这些节点的样本点很少，可以对一些距超球体距离非常近的CF元组进行合并。
（3）（可选）利用其他一些聚类算法（如K-Means）对所有的CF元组进行聚类，得到一棵比较好的CF Tree。这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构，以及一些由于节点CF个数限制导致的树结构分裂。
（4）（可选）利用第三步生成的CF Tree的所有CF节点的质心，作为初始质心点，对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。
从上面可以看出，BIRCH算法的关键就是步骤（1），也就是CF Tree的生成，其他步骤都是为了优化最后的聚类结果。
5.BIRCH算法小结
BIRCH算法可以不用输入类别数k值，这点和K-Means、Mini Batch K-Means不同。如果不输入k值，则最后的CF元组的组数即为最终的k值，否则会按照输入的k值对CF元组按距离大小进行合并。
一般来说，BIRCH算法适用于样本量较大的情况，这与Mini Batch K-Means类似；但是BIRCH适用于类别数比较大的情况，而Mini Batch K-Means一般适用于类别数适中或者较少的情况。BIRCH除了聚类，还可以额外做一些异常点检测和数据初步按类别规约的预处理。但是如果数据特征的维度非常大，如大于20，则BIRCH不太适合，此时Mini Batch K-Means的表现较好。
对于调参，BIRCH要比K-Means、Mini Batch K-Means复杂，因为它需要对CF Tree的几个关键参数进行调参，这几个参数对CF Tree的最终形式影响很大。
BIRCH算法的主要优点有：
（1）节约内存，所有的样本都在磁盘上，CF Tree仅仅保存了CF节点和对应的指针；
（2）聚类速度快，只需要扫描一遍训练集就可以建立CF Tree，CF Tree的增删改都很快；
（3）除了可以识别噪声点，还能对数据集进行初步分类的预处理。
BIRCH算法的主要缺点有：
（1）由于CF Tree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同；
（2）对高维特征的数据聚类效果不好，此时可以选择Mini Batch K-Means；
（3）如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。