BIRCH 概述

BIRCH 算法属于层次聚类算法的一种,全称是利用层次方法的平衡迭代规约和聚类 (Balanced Iterative Reducing and Clustering Using Hierarchies)。
BIRCH 算法利用了一个树结构进行快速的聚类,这个数结构类似于平衡 B+ 树,一般将它称之为聚类特征树 (Clustering Feature Tree,简称 CF Tree)。这颗树的每一个节点是由若干个聚类特征 (Clustering Feature,简称 CF)组成。聚类特征树的样子:每个节点包括叶子节点都有若干个 CF,而内部节点的 CF 有指向孩子节点的指针,所有的叶子节点用一个双向链表链接起来。
聚类特征树

聚类特征 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=(33+22+44+44+33+44+66+55+77+88)=(54+190)=244
举个例子

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

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

聚类特征树 CF Tree 的生成

先定义好 CF Tree 的参数: 即内部节点的最大 CF 数 B, 叶子节点的最大 CF 数 L, 叶节点每个 CF 的最大样本半径阈值 T。
在最开始的时候,CF Tree 是空的,没有任何样本,从训练集读入第一个样本点,将它放入一个新的 CF 三元组 A,这个三元组的 N=1,将这个新的 CF 放入根节点,此时的 CF Tree 如下图:
CF Tree 的生成1

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

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

当来到第四个样本点的时候,发现和 B 在半径小于 T 的超球体,这样更新后的 CF Tree 如下图:
CF Tree 的生成4

那什么时候 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 叶子节点一分为二。
CF Tree 的生成5

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

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

BIRCH 算法

将所有的训练集样本建立了 CF Tree,一个基本的 BIRCH 算法就完成了,对应的输出就是若干个 CF 节点,每个节点里的样本点就是一个聚类的簇。也就是说 BIRCH 算法的主要过程,就是建立 CF Tree 的过程。
BIRCH 算法的流程:

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

Pros and Cons

优点:

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