以下参考文章-brich聚类算法原理

纯笔记,加入自己的一些理解。

层次聚类的改进

之前介绍过层次聚类的缺点,聚类结果不可逆性,后期不可更改。
以下就是一个改进的方向:集成层次聚类和其他的聚类方法,形成多阶段聚类。

以下介绍的就是Brich算法。
BIRCH方法通过集成层次聚类和其他聚类算法来对大量数值数据进行聚类。

Brich算法

思想:首先用树结构对对象进行层次划分,其中叶节点或者是低层次的非叶节点可以看作是由分辨率决定的“微簇”,然后使用其他的聚类算法对这些微簇进行宏聚类。

以上说过这是集成多种聚类算法的,其中层次聚类用于初始的微聚类阶段,而其他方法如迭代划分(在后来的宏聚类阶段)。

它克服了凝聚聚类方法所面临的两个困难:

  • ①可伸缩性;
  • ②不能撤销前一步所做的工作。

BIRCH使用聚类特征来概括一个簇,使用聚类特征树 (CF树)来表示聚类的层次结构。这些结构帮助聚类方法在大型数据库中取得好的速度和伸缩性,还使得BIRCH 方法对新对象增量和动态聚类也非常有效。

聚类特征CF树

在聚类特征树中,一个聚类特征CF是这样定义的:
每一个CF是一个三元组,可以用(N,LS,SS)表示。

  • 其中N代表了这个CF中拥有的样本点的数量,这个好理解;
  • LS代表了这个CF中拥有的样本点各特征维度的和向量;
  • SS代表了这个CF中拥有的样本点各特征维度的平方和

一个聚类特征代表一个簇,使用聚类特征概括簇可以避免存储个体对象或点的详细信息。我们只需要固定大小的空间来存放聚类特征。这是空间中BIRCH有效性的关键。(浅显的就是,当我们非叶子结点只存储各个子节点的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举例

聚类特征本质上是给定簇的统计汇总:从统计学的观点来看,它是簇的零阶矩、一阶矩和二阶矩。

CF Tree的参数

B:非叶子结点可以拥有的子节点数。
L:叶子节点可以拥有的最大CF数。
阈值T:簇可以拥有的最大簇半径。

CF的性质

线性可加性:

C1C2CF1=<n1LS1SS1>CF2=<n2LS2SS2>C1C2CF1+CF2=<n1+n2LS1+LS2SS1+SS2>也就是说,对于两个不相交的簇C_1和C_2,其聚类特征分别为CF_1=<n_1,LS_1,SS_1>和CF_2=<n_2,LS_2,SS_2>,合并C_1和C_2后的簇的聚类特征是 CF_1+CF_2=<n_1+n_2,LS_1+LS_2,SS_1+SS_2>

聚类特征树性质

  • CF树是一棵高度平衡的树,它存储了层次聚类的聚类特征。下图给出了一个例子。根据定义,树中的非叶节点有后代 或“子女”。非叶节点存储了其子女的CF的总和,因而汇 总了关于其子女的聚类信息。

  • CF树有两个参数:分支因子B和阈值T。

    • 分支因子定义了每个非叶节点子女的最大数目。
    • 而阈值参数给出了存储在树的叶节点中的子簇的最大直径。
    • 这两个参数影响结果数的大小。

特征树示意图

CF中常用到的统计量

  • 簇(形心)几何中心x0x_0

x0=i=1nxin=LSnx_{0}=\frac{\sum_{i=1}^{n} x_{i}}{n}=\frac{L S}{n}

  • 簇半径RR

R=i=1n(xix0)2n=nSS2LS2n2R=\sqrt{\frac{\sum_{i=1}^{n}\left(x_{i}-x_{0}\right)^{2}}{n}}=\sqrt{\frac{n S S-2 L S^{2}}{n^{2}}}

  • 簇直径DD

D=i=1nj=1n(xixj)2n(n1)=nSS2LS2n(n1)D=\sqrt{\frac{\sum_{i=1}^{n} \sum_{j=1}^{n}\left(x_{i}-x_{j}\right)^{2}}{n(n-1)}}=\sqrt{\frac{n S S-2 L S^{2}}{n(n-1)}}

其中R是簇中每个对象到形心的平均距离,D是簇中每对对象的平均距离。
R和D反应形心周围的对象紧密程度。
通过以上公式可知,一个CF记录了一个簇的形心、半径。

聚类特征树的构造

我们先定义好CF Tree的参数: 即内部节点的最大CF数B=3, 叶子节点的最大CF数L=3, 叶节点每个CF的最大样本半径阈值T.

  1. 添加节点
  • 初始时,root为空节点,没有任何样本,我们从训练集读入第一个样本点,将它放入一个新的CF三元组A,这个三元组的N=1,将这个新的CF放入根节点,此时的CF Tree如下图:

初始

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

新增样本点1

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

新增节点1

  • 当来到第四个样本点的时候,判断该样本点离我们的哪个(簇)CF节点更近,发现离B(簇)Cf更近,就继续判断该样本点是否在B簇半径小于T的超球体,这样更新后的CF Tree如下图:

新增样本点2

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

分裂节点

  • 我们将LN3里所有CF元组中,找到两个最远的CF做这两个新叶子节点的种子CF(比如sc8与sc6),然后将LN3节点里其他CF sc5, sc7按照就近原则将划分到两个新的叶子节点上。将LN3节点划分后的CF Tree如下图:

分裂节点2

  • 但是我们处理好了,LN3的CF个数,但是Root的子节点个数却超过了3,B=3,也就是说,Root也需要分裂。分裂规则和叶子节点一样。

分裂节点3

新节点插入总结:

  1. 从根节点向下寻找和新样本距离最近的叶子节点和叶子节点里最近的CF节点。
  2. 如果新样本加入后,这个CF节点对应的超球体半径仍然满足小于阈值T,则更新路径上所有的CF三元组,插入结束。否则转入3.(或者说新的样本点的加入,判断是否在,该CF代表的簇以 到其形心距离为(簇半径/给定阈值T?)的长度范围内,在就放入,不在就分裂。)
  3. 如果当前叶子节点的CF节点个数小于阈值L,则创建一个新的CF节点,放入新样本,将新的CF节点放入这个叶子节点,更新路径上所有的CF三元组,插入结束。否则转入4。
  4. 将当前叶子节点划分为两个新叶子节点时,选择旧叶子节点中所有CF元组里超球体距离最远的两个CF元组,分别作为两个新叶子节点的第一个CF节点。将其他元组和新样本元组按照距离远近原则放入对应的叶子节点。依次向上检查父节点是否也要分裂,如果需要按和叶子节点分裂方式相同。

brich算法核心

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

当然,真实的BIRCH算法除了建立CF Tree来聚类,其实还有一些可选的算法步骤的,现在我们就来看看 BIRCH算法的流程。

  1. 将所有的样本依次读入,在内存中建立一颗CF Tree, 建立的方法参考上一节。

  2. (可选)将第一步建立的CF Tree进行筛选,去除一些异常CF节点,这些节点一般里面的样本点很少。对于一些超球体距离非常近的元组进行合并

  3. (可选)利用其它的一些聚类算法比如K-Means对所有的CF元组进行聚类,得到一颗比较好的CF Tree.这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构,以及一些由于节点CF个数限制导致的树结构分裂。

  4. (可选)利用第三步生成的CF Tree的所有CF节点的质心,作为初始质心点,对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。

从上面可以看出,BIRCH算法的关键就是步骤1,也就是CF Tree的生成,其他步骤都是为了优化最后的聚类结果。

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算法的主要优点有:

  • 节约内存,所有的样本都在磁盘上,CF Tree仅仅存了CF节点和对应的指针。
  • 聚类速度快,只需要一遍扫描训练集就可以建立CF Tree,CF Tree的增删改都很快。
  • 可以识别噪音点,还可以对数据集进行初步分类的预处理

BIRCH算法的主要缺点有:

  • 由于CF Tree对每个节点的CF个数有限制,导致聚类的结果可能和真实的类别分布不同.
  • 对高维特征的数据聚类效果不好。此时可以选择Mini Batch K-Means
  • 如果数据集的分布簇不是类似于超球体,或者说不是凸的,则聚类效果不好。