Birch层次聚类算法

标签（空格分隔）： CF树建立

---

主要借鉴的网文地址，并进行大量引用：【非常浅显易懂】
http://www.cnblogs.com/pinard/p/6179132.html 【主要以此文为主】
http://www.cnblogs.com/tiaozistudy/p/6129425.html
根据上述第二个网址的步骤，进行代码化的代码地址：
https://github.com/AresAnt/ML-DL/tree/master/Clustering/Birch

BIRCH算法比较适合于数据量大，类别数K也比较多的情况。它运行速度很快，只需要单遍扫描数据集就能进行聚类，当然需要用到一些技巧，下面我们就对BIRCH算法做一个总结。
【个人建议，如想要自己写CF树生成代码前，请先了解一下B+树的构造与写法对之后的代码完成将会有帮助。】

1.聚类特征CF与聚类特征树CF Tree

在聚类特征树中，一个聚类特征CF是这样定义的：每一个CF是一个三元组，可以用（N，LS，SS）表示。其中N代表了这个CF中拥有的样本点的数量，这个好理解；LS代表了这个CF中拥有的样本点各特征维度的和向量，SS代表了这个CF中拥有的样本点各特征维度的平方和。举个例子如下图，在CF Tree中的某一个节点的某一个CF中，有下面5个样本(3,4), (2,6), (4,5), (4,7), (3,8)。则它对应的N=5， LS= (3+2+4+4+3,4+6+5+7+8) =(16,30), SS = (32+22+42+42+32+42+62+52+72+82) = (54+190) = 244。具体内容可如下所示：

CF有一个很好的性质，就是满足线性关系，也就是CF1+CF2=(N1+N2,LS1+LS2,SS1+SS2)。这个性质从定义也很好理解。如果把这个性质放在CF Tree上，也就是说，在CF Tree中，对于每个父节点中的CF节点，它的(N,LS,SS)三元组的值等于这个CF节点所指向的所有子节点的三元组之和。如下图所示：

从上图中可以看出，根节点的CF1的三元组的值，可以从它指向的6个子节点（CF7 - CF12）的值相加得到。这样我们在更新CF Tree的时候，可以很高效。

对于CF Tree，我们一般有几个重要参数，第一个参数是每个内部节点的最大CF数B，第二个参数是每个叶子节点的最大CF数L，第三个参数是针对叶子节点中某个CF中的样本点来说的，它是叶节点每个CF的最大样本半径阈值T，也就是说，在这个CF中的所有样本点一定要在半径小于T的一个超球体内。对于上图中的CF Tree，限定了B=7， L=5， 也就是说内部节点最多有7个CF，而叶子节点最多有5个CF。

2.聚类特征树CF Tree的生成

下面我们看看怎么生成CF Tree。我们先定义好CF Tree的参数： 即内部节点的最大CF数B， 叶子节点的最大CF数L， 叶节点每个CF的最大样本半径阈值T

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

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

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

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

那个什么时候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叶子节点一分为二了。

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

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

有了上面这一系列的图，相信大家对于CF Tree的插入就没有什么问题了，总结下CF Tree的插入：

1. 从根节点向下寻找和新样本距离最近的叶子节点和叶子节点里最近的CF节点
2. 如果新样本加入后，这个CF节点对应的超球体半径仍然满足小于阈值T，则更新路径上所有的CF三元组，插入结束。否则转入3.
3. 如果当前叶子节点的CF节点个数小于阈值L，则创建一个新的CF节点，放入新样本，将新的CF节点放入这个叶子节点，更新路径上所有的CF三元组，插入结束。否则转入4。
4. 将当前叶子节点划分为两个新叶子节点，选择旧叶子节点中所有CF元组里超球体距离最远的两个CF元组，分布作为两个新叶子节点的第一个CF节点。将其他元组和新样本元组按照距离远近原则放入对应的叶子节点。依次向上检查父节点是否也要分裂，如果需要按和叶子节点分裂方式相同

3.Birch算法流程

如不愿看下列粗糙流程，可以参考：http://www.cnblogs.com/tiaozistudy/p/twostep_cluster_algorithm.html【之前给出的第二个网站，根据其步骤进行操作】

# 获取的初始化参数的值，枝平衡银子β，叶平衡因子λ，空间阈值T，以及是否
class Birch_Class():

    # 获取的初始化参数的值，枝平衡因子β，叶平衡因子λ，空间阈值T，以及是否
    def __init__(self,branch_balance=2,leaf_balance=3,threshold=3,compute_labels=True):
        self.branch_balance = branch_balance
        self.leaf_balance = leaf_balance
        self.threshod = threshold
        self.compute_labels=compute_labels

传入参数:

• 分支平衡参数： branch_balance
• 叶子平衡参数： leaf_balance
• 空间阈值： threshold
  ---以上三者数据用来初始化类的基本属性

1.初始化CF树为空树（建立一个TreeNode,每个TreeNode有N个CFNode）【N与分支平衡因子与叶平衡因子有关】
2.逐条导入数据（后面统一用簇来代替），进行CF树的填充
3.判断当前插入的簇与TreeNode中最近的的CFNode（CF簇），然后筛选出该簇，进行同样的递归计算，直到叶子节点。

#伪代码：
    if TreeNode is Leaf:
        find nearest CFNode
    else:
        TreeNode = min(Dist(TreeNode.CFnode,传进来的簇))

4.到叶子节点后发现，不满足叶平衡因子，或计算的阈值超出了范围，则进行叶节点分裂。
5.叶节点分裂后，会增加分支节点上的CFNode增加，此时需要判断增加CFNode后的TreeNode是否满足分支平衡因子，如果不满足则当前分支节点进行分裂，同时上一层的分支节点进行CFNode数量增加。

#伪代码：
    # 计算叶节点是否要分裂,len(TreeNode)就是指CFNode的数量
    if len(TreeNode) < leaf_balance or Dist(CFNode,传入的簇) < threshold:
        TreeNode.add(CFNode)
    else:
        TreeNode.split()
        
        # 分裂后，判断上一层分支数量会不会超出
        @递归的函数 
        if len(TreeNode.parent) < branch_balance:
            TreeNode.parent.add(TreeNode)
        else:
            TreeNode = TreeNode.parent （开始上面的函数递归）
        

6.簇插入到叶子节点时候，需要更新当前插入路径下的聚类特征值，即L，SS，LS等
7.输出CF树，然后可以进行优化

4.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算法的优缺点：

BIRCH算法的主要优点有：

1) 节约内存，所有的样本都在磁盘上，CF Tree仅仅存了CF节点和对应的指针。

2) 聚类速度快，只需要一遍扫描训练集就可以建立CF Tree，CF Tree的增删改都很快。

3) 可以识别噪音点，还可以对数据集进行初步分类的预处理

BIRCH算法的主要缺点有：

1) 由于CF Tree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同.

2) 对高维特征的数据聚类效果不好。此时可以选择Mini Batch K-Means

3) 如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。