大家好，欢迎来到IT知识分享网。

BIRCH，Balanced Iterative Reducing and Clustering Using Hierarchies，翻译过来就是“利用层次方法的平衡迭代规约和聚类“，全称非常复杂。

1、birch概述

简单来说，BIRCH 算法利用了一个树结构来帮助我们快速的聚类，这个特殊的树结构，就是我们后面要详细介绍的聚类特征树（CF-tree）。
可以说只要构造好了CF-树，BIRCH算法也就完成了。BIRCH算法比较适合于数据量大，类别数K也比较多的情况。它运行速度很快，只需要单遍扫描数据集就能进行聚类
该算法笼统的说，可以分为两步：
（1）扫描数据库，建立一棵存放于内存的 CF-Tree，它可以被看作数据的多层压缩，试图保留数据的内在聚类结构；
（2）采用某个选定的聚类算法，如 K-means或者凝聚算法，对CF树的叶节点进行聚类，把稀疏的簇当作离群点删除，而把更稠密的簇合并为更大的簇。

2、概念准备

BIRCH算法利用了一个树结构来帮助我们快速的聚类，这个数结构类似于平衡B+树，一般将它称之为聚类特征树(Clustering Feature Tree，简称CF Tree)。这颗树的每一个节点是由若干个聚类特征(Clustering Feature，简称CF)组成。从下图我们可以看看聚类特征树是什么样子的：每个节点包括叶子节点都有若干个CF，而内部节点的CF有指向孩子节点的指针，所有的叶子节点用一个双向链表链接起来。

2.1、 CF-Tree

CF-tree，Clustering Feature Tree，聚类特征树。

2.1.1、CF 聚类特征

CF聚类特征用一个三元组概括描述各簇的信息，每一个 CF 都可以用（N，LS，SS）表示。

假设某簇中有 N 个 D 维数据点
矢量 $\overrightarrow{LS}$ 是个各点的线性求和，公式如下：

$$\sum \vec{l}=\sum _{n=1}^N\overrightarrow{x_n}={(\sum _{n=1}^N{x}_{n1},\sum _{n=1}^N{x}_{n2},...,\sum _{n=1}^N{x}_{nD})}^T$$
标量 SS 是各数据点的平方和，公式如下：

$$\sum s=\sum _{n=1}^N{\overrightarrow{x_n}}^2=\sum _{n=1}^N{\overrightarrow{x_n}}^T\overrightarrow{x_n}=\sum _{n=1}^N\sum _{i=1}^D{x_{ni}}^2$$

可加性：
对于两个不相交的簇 C₁ 和 C₂ ,
聚类特征分别为 CF₁ = <N₁, LS₁, SS₁> 和 CF₂ = <N₂, LS₂, SS₂> ,
如果将这两个簇合并成一个大簇，则大簇的聚类特征为：
CF₁ + CF₂ = <N₁+N₂, LS₁+LS₂, SS₁+SS₂>

2.1.2、CF的三个统计量

簇质心：
$$\overrightarrow{X_0}=\frac{\sum _{i=1}^N\overrightarrow{X_i}}{N}=\frac{LS}{N}$$
簇半径：
$$R=\frac{\sum _{i=1}^N{(\overrightarrow{X_i}-\overrightarrow{X_0})}^2}{N}=\sqrt{\frac{NSS-L{S}^2}{N^2}}$$
簇半径 R 是成员对象到质心的平均距离；

簇直径：
$$D=\sqrt{\frac{\sum _{i=1}^N\sum _{j=1}^N{(\overrightarrow{X_i}-\overrightarrow{X_j})}^2}{N(N-1)}}=\sqrt{\frac{2NSS-2L{S}^2}{N(N-1)}}$$
簇直径D是簇中两两数据点的平均距离；

簇半径与簇直径这两个统计量都反映了簇内紧密程度。

因此我们说，CF 结构概括了簇的基本信息，并且是高度压缩的，它存储了小于实际数据点的聚类信息。

2.2、簇间距离

利用 CF 的三个统计量，我们还可以度量不同簇间的距离。

簇间距离的度量方式比较多：

（1）中心点欧基里得距离（centroid Euclidian distance）
$$d_0=\sqrt{{(\overline{\overrightarrow{x_1}}-\overline{\overrightarrow{x_2}})}^2}=\sqrt{{(\frac{\sum \overrightarrow{l_1}}{N}-\frac{\sum \overrightarrow{l_2}}{N})}^2}$$
（2）中心点曼哈顿距离（centroid Manhattan distance）

$$d_0=|\overline{\overrightarrow{x_1}}-\overline{\overrightarrow{x_2}}|=|\frac{\sum \overrightarrow{l_1}}{N}-\frac{\sum \overrightarrow{l_2}}{N}|$$
（3）簇连通平均距离（average inter-cluster distance）【常用】

$$d_2=\sqrt{\frac{{\sum }_{m=1}^{N_1}{\sum }_{n=1}^{N_2}(\overrightarrow{x_{1m}}-\overrightarrow{x_{2n}}{)}^2}{N_1{N}_2}}=\sqrt{\frac{\sum s_1}{N_1}-2\frac{\sum \overrightarrow{l_1^T}}{N_1}\frac{\sum \overrightarrow{l_2}}{N_2}+\frac{\sum s_2}{N_2}}$$

3、生成聚类特征树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节点。将其他元组和新样本元组按照距离远近原则放入对应的叶子节点。依次向上检查父节点是否也要分裂，如果需要按和叶子节点分裂方式相同。

4、BIRCH算法

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

4.1 二度聚类

在解释 CF树瘦身之前，我们先来看二度聚类。这一步，在某些博客中标记为可选，有些博客中将其视为Birch算法必要的流程。二度聚类主要是针对数据中存在极大的分布不均衡情况，以及数据点插入顺序不同可能导致分类效果偏差，对全部叶节点二次聚类，即簇与簇之间聚类。二度聚类在聚类方法上几乎没有限制，常用K-means或者凝聚算法。二度聚类使用到的叶节点（簇），一般有三种选择：
（1）把中心点作为簇的代表，把每个簇作为单点来对待
（2）把簇作为中心点的n次重复
（3）直接使用簇的CF向量信息

4.2 CF树瘦身（可选）

在二度聚类之前，我们可以选择先对 CF树进行瘦身。进行这一步的原因，主要是因为二度聚类常用的聚类方法，如K-means，在小数据集上效果更好。因此，对输入的簇的个数有一定的要求，于是我们需要简化初始生成的CF树。这个简化的过程，一般是通过增加最大样本半径阈值T来完成。通过增加叶节点超球体的范围大小，来减小叶节点子簇的数量。另一方面，瘦身也可能是内存空间的要求。在将数据点插入到CF树的过程中，用于存储CF树节点及其相关信息的内存有限，导致部分数据点生长形成的CF树占满了所有内存，因此需要对CF树进行瘦身在将数据库中数据点插入到CF树的过程中，一般会给一个较小的最大样本半径阈值T，当内存溢出时，再逐步增加空间阈值τ，对CF树进行修身，再插入后续数据点。

4.3 离群点处理

离群点处理，其实也属于CF树瘦身的内容，这里单独提出来说明一下。BIRCH算法预留出一定空间用于潜在离群点的回收。
（1）在每次对当前CF树进行瘦身之后，搜索叶节点中的稀疏子簇，作为离群点放入回收空间中，同步剔除CF树上的相关路径及节点。（此处的稀疏子簇表示，簇内数据点数量远远少于所有簇平均数据点数的叶节点子簇。）
（2）当回收空间溢出时，逐个尝试将潜在离群点插入到现有CF树中。逐个判断：单个潜在离群点是否可以在不增加CF树节点数量的条件下被某个叶元组吸收？可以，该潜在离群点将从回收空间中取出；否则继续留在回收空间中。（
3）在数据库中所有数据点都被实施插入CF树的操作后，扫描所有潜在离群点，并尝试插入到CF树中，如果仍未能插入CF树中，可以确定为真正离群点，得以删除。

优缺点

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的最终形式影响很大。
优点：

1. 节约内存，所有的样本都在磁盘上，CF Tree仅仅存了CF节点和对应的指针。
2. 聚类速度快，只需要一遍扫描训练集就可以建立CF Tree，CF Tree的增删改都很快。
3. 可以识别噪音点，还可以对数据集进行初步分类的预处理
4. 可以不用输入类别数K值。如果不输入K值，则最后的CF元组的组数即为最终的K，否则会按照输入的K值对CF元组按距离大小进行合并。

缺点：

1. 由于CF Tree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同，一个CF数节点并不总是对应于用户所考虑的一个自然簇
2. 对高维特征的数据聚类效果不好。此时可以选择Mini Batch K-Means
3. 因为其使用半径或者直径的概念来定义簇的边界，所以如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。
4. BIRCH适合于处理需要数十上百小时聚类的数据，但在整个过程中算法一旦中断，一切必须从头再来。

python实现

from __future__ import division
import warnings
import numpy as np
from math import sqrt
from sklearn.utils import check_array
from sklearn.metrics.pairwise import euclidean_distances
from sklearn.utils.extmath import row_norms,safe_sparse_dot
from sklearn.cluster.hierarchical import AgglomerativeClustering

def _split_node(node, threshold, branching_factor):
   new_subcluster1 = _CFSubcluster()
   new_subcluster2 = _CFSubcluster()
   new_node1 = _CFNode(
       threshold, branching_factor, is_leaf=node.is_leaf,
       n_features=node.n_features)
   new_node2 = _CFNode(
       threshold, branching_factor, is_leaf=node.is_leaf,
       n_features=node.n_features)
   new_subcluster1.child_ = new_node1
   new_subcluster2.child_ = new_node2

   if node.is_leaf:
       if node.prev_leaf_ is not None:
           node.prev_leaf_.next_leaf_ = new_node1
       new_node1.prev_leaf_ = node.prev_leaf_
       new_node1.next_leaf_ = new_node2
       new_node2.prev_leaf_ = new_node1
       new_node2.next_leaf_ = node.next_leaf_
       if node.next_leaf_ is not None:
           node.next_leaf_.prev_leaf_ = new_node2

   dist = euclidean_distances(
       node.centroids_, Y_norm_squared=node.squared_norm_, squared=True)
   n_clusters = dist.shape[0]

   farthest_idx = np.unravel_index(
       dist.argmax(), (n_clusters, n_clusters))
   node1_dist, node2_dist = dist[[farthest_idx]]

   node1_closer = node1_dist < node2_dist
   for idx, subcluster in enumerate(node.subclusters_):
       if node1_closer[idx]:
           new_node1.append_subcluster(subcluster)
           new_subcluster1.update(subcluster)
       else:
           new_node2.append_subcluster(subcluster)
           new_subcluster2.update(subcluster)
   return new_subcluster1, new_subcluster2

class _CFSubcluster(object):
   def __init__(self, linear_sum=None):
       if linear_sum is None:
           self.n_samples_ = 0
           self.squared_sum_ = 0.0
           self.linear_sum_ = 0
       else:
           self.n_samples_ = 1
           self.centroid_ = self.linear_sum_ = linear_sum
           self.squared_sum_ = self.sq_norm_ = np.dot(
               self.linear_sum_, self.linear_sum_)
       self.child_ = None

   def update(self, subcluster):
       self.n_samples_ += subcluster.n_samples_
       self.linear_sum_ += subcluster.linear_sum_
       self.squared_sum_ += subcluster.squared_sum_
       self.centroid_ = self.linear_sum_ / self.n_samples_
       self.sq_norm_ = np.dot(self.centroid_, self.centroid_)

   def merge_subcluster(self, nominee_cluster, threshold):
       """ 检查是否可以合并，条件符合就合并. """
       new_ss = self.squared_sum_ + nominee_cluster.squared_sum_
       new_ls = self.linear_sum_ + nominee_cluster.linear_sum_
       new_n = self.n_samples_ + nominee_cluster.n_samples_
       new_centroid = (1 / new_n) * new_ls
       new_norm = np.dot(new_centroid, new_centroid)
       dot_product = (-2 * new_n) * new_norm
       sq_radius = (new_ss + dot_product) / new_n + new_norm
       if sq_radius <= threshold ** 2:
           (self.n_samples_, self.linear_sum_, self.squared_sum_,self.centroid_, self.sq_norm_) = new_n, new_ls, new_ss, new_centroid, new_norm
           return True
       return False
   
class _CFNode(object):
   #初始化函数
   def __init__(self, threshold, branching_factor, is_leaf, n_features):
       self.threshold = threshold
       self.branching_factor = branching_factor
       self.is_leaf = is_leaf
       self.n_features = n_features
       # 列表subclusters, centroids 和 squared norms一直贯穿始终
       self.subclusters_ = []
       self.init_centroids_ = np.zeros((branching_factor + 1, n_features))
       self.init_sq_norm_ = np.zeros((branching_factor + 1))#一维列表
       self.squared_norm_ = []
       self.prev_leaf_ = None
       self.next_leaf_ = None

   def append_subcluster(self, subcluster):
       n_samples = len(self.subclusters_)
       self.subclusters_.append(subcluster)
       self.init_centroids_[n_samples] = subcluster.centroid_
       self.init_sq_norm_[n_samples] = subcluster.sq_norm_
       # 扩容
       self.centroids_ = self.init_centroids_[:n_samples + 1, :]
       self.squared_norm_ = self.init_sq_norm_[:n_samples + 1]
   
   def update_split_subclusters(self, subcluster,new_subcluster1, new_subcluster2):
       #从一个节点去掉一个subcluster，再添加两个subcluster.
       ind = self.subclusters_.index(subcluster)#找到索引位置
       self.subclusters_[ind] = new_subcluster1
       self.init_centroids_[ind] = new_subcluster1.centroid_
       self.init_sq_norm_[ind] = new_subcluster1.sq_norm_
       self.append_subcluster(new_subcluster2)

   def insert_cf_subcluster(self, subcluster):
       #插入一个新的subcluster.
       if not self.subclusters_:
           self.append_subcluster(subcluster)
           return False

       # 首先，在树中遍历寻找与当前subcluster最近的subclusters，再将subcluster插入到此处.
       dist_matrix = np.dot(self.centroids_, subcluster.centroid_)# dot矩阵相乘
       print len(self.centroids_)
       dist_matrix *= -2.
       dist_matrix += self.squared_norm_
       closest_index = np.argmin(dist_matrix)
       closest_subcluster = self.subclusters_[closest_index]#距当前点最近的subclusters集
       # 如果closest_subcluster有孩子节点，递归遍历
       if closest_subcluster.child_ is not None:
           split_child = closest_subcluster.child_.insert_cf_subcluster(subcluster)
           if not split_child:
               # 如果孩子节点没有分裂，仅需要更新closest_subcluster
               closest_subcluster.update(subcluster)
               self.init_centroids_[closest_index] = self.subclusters_[closest_index].centroid_
               self.init_sq_norm_[closest_index] = self.subclusters_[closest_index].sq_norm_
               return False

           # 如果发生了分割，需要重新分配孩子节点中的subclusters，并且在其父节点中添加一个subcluster.
           else:
               new_subcluster1, new_subcluster2 = _split_node(closest_subcluster.child_, threshold, branching_factor)
               self.update_split_subclusters(closest_subcluster, new_subcluster1, new_subcluster2)
               if len(self.subclusters_) > self.branching_factor:
                   return True
               return False

       #没有孩子节点
       else:
           merged = closest_subcluster.merge_subcluster(subcluster, self.threshold)
           if merged:
               #更新操作
               self.init_centroids_[closest_index] =closest_subcluster.centroid_
               self.init_sq_norm_[closest_index] = closest_subcluster.sq_norm_
               return False
           # 待插入点和任何节点相距较远
           elif len(self.subclusters_) < self.branching_factor:
               self.append_subcluster(subcluster)
               return False
           # 如果没有足够的空间或者待插入点与其它点相近，则分裂操作.
           else:
               self.append_subcluster(subcluster)
               return True
           
class Birch():
   #初始化函数
   def __init__(self, threshold=0.5, branching_factor=50, n_clusters=3,
                compute_labels=True):
       self.threshold = threshold
       self.branching_factor = branching_factor
       self.n_clusters = n_clusters
       self.compute_labels = compute_labels

   def fit(self, X, y=None):
       threshold = self.threshold
       X = check_array(X, accept_sparse='csr', copy=True)
       branching_factor = self.branching_factor
       if branching_factor <= 1:
           raise ValueError("Branching_factor should be greater than one.")
       n_samples, n_features = X.shape
       #初次建立树，并且root节点是叶子.
       self.root_ = _CFNode(threshold, branching_factor, is_leaf=True,n_features=n_features)
       # 便于恢复subclusters.
       self.dummy_leaf_ = _CFNode(threshold, branching_factor,is_leaf=True, n_features=n_features)
       self.dummy_leaf_.next_leaf_ = self.root_
       self.root_.prev_leaf_ = self.dummy_leaf_
       # 未能向量化. 
       for sample in iter(X):
           subcluster = _CFSubcluster(linear_sum=sample)
           split = self.root_.insert_cf_subcluster(subcluster)
           if split:
               new_subcluster1, new_subcluster2 = _split_node(self.root_, threshold, branching_factor)
               del self.root_
               self.root_ = _CFNode(threshold, branching_factor,is_leaf=False,n_features=n_features)
               self.root_.append_subcluster(new_subcluster1)
               self.root_.append_subcluster(new_subcluster2)

       centroids = np.concatenate([leaf.centroids_ for leaf in self._get_leaves()])
       self.subcluster_centers_ = centroids

       self._global_clustering(X)
       return self

   def _get_leaves(self):

       #返回CFNode的叶子节点
       leaf_ptr = self.dummy_leaf_.next_leaf_
       leaves = []
       while leaf_ptr is not None:
           leaves.append(leaf_ptr)
           leaf_ptr = leaf_ptr.next_leaf_
       return leaves

   def predict(self, X):
       reduced_distance = safe_sparse_dot(X, self.subcluster_centers_.T)
       print reduced_distance
       reduced_distance *= -2
       reduced_distance += self._subcluster_norms
       return self.subcluster_labels_[np.argmin(reduced_distance, axis=1)]
   
   def _global_clustering(self, X=None):

       #对fitting之后获得的subclusters进行global_clustering
       clusterer = self.n_clusters
       centroids = self.subcluster_centers_
       compute_labels = (X is not None) and self.compute_labels

       # 预处理
       not_enough_centroids = False
       if isinstance(clusterer, int):
           clusterer = AgglomerativeClustering(n_clusters=self.n_clusters)
           if len(centroids) < self.n_clusters:
               not_enough_centroids = True
       elif (clusterer is not None):
           raise ValueError("n_clusters should be an instance of " "ClusterMixin or an int")

       # 避免predict环节，重复运算
       self._subcluster_norms = row_norms(
           self.subcluster_centers_, squared=True)

       if clusterer is None or not_enough_centroids:
           self.subcluster_labels_ = np.arange(len(centroids))
           if not_enough_centroids:
               warnings.warn(
                   "Number of subclusters found (%d) by Birch is less than (%d). Decrease the threshold."% (len(centroids), self.n_clusters))
       else:
           # 对所有叶子节点的subcluster进行聚类，它将subcluster的centroids作为样本，并且找到最终的centroids.
           self.subcluster_labels_ = clusterer.fit_predict(
               self.subcluster_centers_)

       if compute_labels:
           self.labels_ = self.predict(X)

···
参考刘建平
知乎 Loss Dragon
github