5.3.3.1　BIRCH算法概述

BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）的全称是利用层次方法的平衡迭代规约和聚类，它是用层次方法来聚类和规约数据。BIRCH只需要单遍扫描数据集而进行聚类。

BIRCH是一个综合的层次聚类算法，它的第一步是建立一棵CF Tree（Clustering Feature Tree，简称CF Tree）放在内存中，然后才是利用一种聚类算法对CF Tree的叶结点进行聚类。这棵树的每一个节点是由聚类特征（Clustering Feature，简称CF）组成。

对于聚类特征CF有如下性质，即假设分别为两个类的聚类特征，合并后的新类特征为

也就是说，在CF Tree中，对于每个父节点中，它的三元组的值等于这个CF节点所指向的所有子节点的三元组之和。

在这棵树中有三种类型的节点，即Nonleaf、Leaf、MinCluster，而Root可能是一种Nonleaf，也可能是一种Leaf。每一个节点都包含一个CF值，通常情况下，我们用CF作为Nonleaf、Leaf、MinCluster的统称。对于CF Tree，我们一般有几个重要参数，第一个参数是每个Nonleaf的最大子节点CF数为B，第二个参数是每个Leaf的最大CF数为L，第三个参数是针对Leaf中每个CF的最大半径阈值T，也就是说，MinCluster中的所有样本点一定要在半径小于T的一个超球体内。CF Tree是一棵高度平衡树。CF Tree支持增量聚类，它可以动态地构造。每个样本点插入的位置总是那个距离它最近的Leaf，如果插入后经过计算使得该Leaf的MinCluster的直径大于阈值，则该Leaf或其他节点很有可能被分裂。插入新样本点后，要更新整个CF Tree的信息，从插入节点的父节点开始一直到Root。

BIRCH算法偏好于处理球形的数据，能够取得较好的聚类效果。BIRCH算法可以方便地对中心、半径、直径和簇内、簇间距离进行计算，具有良好的聚类质量。

5.3.3.2　BIRCH算法的思想

BIRCH算法主要分为两个阶段：

第一个阶段对整个数据集进行扫描，根据给定的初始阈值T建立一棵初始聚类特征树。

拿到第一个样本点a＝（x11，x12，…，x1p），我们创建一个空的Leaf和MinCluster，把点a的ID值放入Mincluster，更新MinCluster的CF值为

把MinCluster作为Leaf的一个孩子，同时更新Leaf的CF值。实际上只要往树中放入一个CF，就要更新从Root到该叶子节点的路径上所有节点的CF值。

第二阶段通过提升阈值T重建CF Tree，得到一棵压缩的CF Tree。CF Tree在数据扫描时创建。每当遇到（扫描）一个样本点，就从根结点开始遍历CF Tree，每层选择最近的结点。当最终识别出当前样本点的最近的Leaf时，就进行测试，检查将该数据项添加到候选MinCluster中是否导致MinCluster的直径大于给定的阈值T。如果不是，则通过更新CF信息将样本点添加到候选MinCluster中。从该Leaf到Root的所有结点的信息也都需要更新。如果MinCluster的直径大于T，若Leaf不满就创建一个单独新MinCluster，成为MinCluster的兄弟节点，否则必须分裂Leaf。此时，在该Leaf中选择两个相距最远的MinCluster作为种子，而其余的项分布到两个新的Leaf中，分布基于哪个Leaf包含最近的种子MinCluster。一旦分裂Leaf，就要更新父母节点，并且在必要时分裂父母节点。这一过程可能继续，一直到根结点。

5.3.3.3　BIRCH算法的流程

具体建树阶段算法步骤如下：

算法：BIRCH算法

输入：n个训练数据（训练集），参数Nonleaf的最大子节点CF数B，Leaf的最大CF数L，MinCluster的最大半径阈值T

输出：CF Tree

步骤：

（1）扫描训练集并取出一个数据对象，从CF Tree的Root开始，自顶向下找到选择距离自己最近的节点。

（2）到达Leaf后，首先找到距离自身最近的MinCluster，检查最近的MinCluster能否吸收此数据，若能吸收，则更新此MinCluster的CF值，否则检查该Leaf是否能添加一个新的MinCluster，若能添加，则在该Leaf中添加新的MinCluster，若不能，则必须将这个Leaf一分为二，找到此Leaf中距离最远的两个MinCluster，然后将这两个MinCluster作为种子形成新的两个Leaf，并将原Leaf中的MinCluster按照距离最近的原则，重新分配到这两个新的Leaf中。

（3）当数据对象插入到CF Tree中后，要对插入路径上的每一个Nonleaf的CF信息进行更新，在Leaf没有被拆分的情况下，只更新Nonleaf已有的CF信息，反映出CF Tree中插入了新的数据信息。若在Leaf被拆分的情况下，则要对父节点添加一个该数据对象存储新增加节点的信息，如果父节点有空间存放该数据对象，则进行添加，否则参照子节点的方式对父节点进行拆分，如果分拆到根节点时，CF Tree的高度增加一层。(www.daowen.com)

（4）如果CF Tree超过了阈值T，可以通过调节阈值重建一颗CF Tree，树的重建过程不需要重新扫描待聚类数据集，而是把所有Leaf中的元组作为输入，重新插入到CF Tree中。

在上述构建CF Tree的基本步骤基础上，需要注意以下四点：

（1）延时分裂。当我们在扫描某个样本数据并据插入CF Tree中时，超出了约束M，此时我们可以选择暂时不对CF Tree重建，因为可能还有更多的满足约束M的数据样本等待插入CF Tree中，此时我们选择延时分裂，将此数据点暂时存储起来，继续扫描不会改变CF Tree尺寸的点并插入树中。

（2）延时分裂点处理。在（1）中形成的延时分裂点，待数据集扫描完成后，将逐一地向CF Tree中插入，在插入过程中若CF Tree没超出阈值M，则正常对节点进行插入，否则在插入延时分裂点的过程中能被某个Leaf的聚类特征融合，插入成功，否则将该延时分裂点加入离散点队列中。

（3）离散点的处理。在重建CF Tree的过程中，会把一些密度低于一定阈值的Leaf作为离散点隔离出来。当CF Tree构建完成，即对所有样本数据点扫描完成后，将离散点队列中的所有数据点重新插入CF Tree中，离散点的插入与延时分裂点的插入算法相同，若能被某个聚类融合则插入成功。

（4）阈值T的处理。阈值T的默认值为0，当CF Tree进行重建时，阈值T也要随之增加，但是阈值T增加太大会使CF聚类信息不够详细，太小则会引起重建次数增多。

5.3.4.4　BIRCH的优势和劣势

算法优势。

（1）节省存储空间。Leaf放在磁盘分区上，Nonleaf仅仅是存储了一个CF值，外加指向父节点和子节点的指针。

（2）计算速度快。合并两簇只需要两个CF算术相加即可，计算两个簇的距离只需要用到而已。

（3）一遍扫描数据库即可建立CF Tree。

（4）可识别噪声点。建立好CF Tree后把那些包含数据点少的MinCluster当作outlier。

（5）由于CF Tree是高度平衡的，所以在树上进行插入或查找操作很快。

算法缺点

（1）算法结果依赖于数据点的插入顺序。本属于同一个簇的点可能由于插入顺序相差很远而分到不同的簇中，即使同一个点在不同的时刻被插入，也会被分到不同的簇中。

（2）对非球状的簇聚类效果不好。这取决于簇直径和簇间距离的计算方法。

（3）对高维数据聚类效果不好。

（4）由于每个节点只能包含一定数目的子节点，最后得出来的簇可能和自然簇相差很大。

（5）BIRCH适合于处理需要数十上百小时聚类的数据，但在整个过程中算法一旦中断，一切必须从头再来。

（6）局部性也导致了BIRCH的聚类效果欠佳。