BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)是一个综合的层次聚类算法。它用到了聚类特征(Clustering Feature, CF)和聚类特征树(CF Tree)两个概念，用于概括聚类描述。聚类特征树概括了聚类的有用信息，并且占用空间较元数据集合小得多，可以存放在内存中，从而可以提高算法在大型数据集合上的聚类速度及可伸缩性。

Zhang 等人提出了Birch（Blanced Iterative Reducing and Clustering）算法来对大规 模数据集进行聚类。Birch 算法是一种非常有效的、传统的层次聚类算法，该算法能够用一 遍扫描有效地进行聚类，并能够有效地处理离群点。Birch 算法是基于距离的层次聚类，综 合了层次凝聚和迭代的重定位方法，首先用自底向上的层次算法，然后用迭代的重定位来改 进结果。[2]层次凝聚是采用自底向上策略，首先将每个对象作为一个原子簇，然后合并这些 原子簇形成更大的簇，减少簇的数目，直到所有的对象都在一个簇中，或某个终结条件被满足。

核心思想

Birch 算法的主要思想是：通过扫描数据库，建立一个初始存放于内存中的聚类特征树， 然后对聚类特征树的叶结点进行聚类。它的核心是聚类特征（CF）和聚类特征树（CF Tree）。 2.1.1 CF CF 是指三元组CF=（N，LS，SS），用来概括子簇信息，而不是存储所有的数据点。 其中：N：簇中d 维点的数目； LS：N 个点的线性和；SS：N 个点的平方和。比如给定一 个由二维点组成的集合{(3,4),(2,6),(4,5)}，那么： CF 结构概括了簇的基本信息，并且是高度压缩的，它存储了小于实际数据点的聚类信 息。[3]同时CF 的三元结构设置使得计算簇的半径、簇的直径、簇与簇之间的距离等非常容易。

CF Tree

CF 树是一棵具有两个参数的高度平衡树，用来存储层次聚类的聚类特征。它涉及到两 个参数分支因子和阈值。其中，分支因子B 指定子节点的最大数目，即每个非叶节点可以 拥有的孩子的最大数目。阈值T 指定存储在叶节点的子簇的最大直径，它影响着CF 树的大 小。改变阈值可以改变树的大小。CF 树是随着数据点的插入而动态创建的，因此该方法是 增量的。 CF 树的构造过程实际上是一个数据点的插入过程[4]，其步骤为:

(1) 从根节点root 开始递归往下，计算当前条目与要插入数据点之间的距离，寻找距 离最小的那个路径，直到找到与该数据点最接近的叶节点中的条目。

(2) 比较计算出的距离是否小于阈值T，如果小于则当前条目吸收该数据点；反之，则 继续第三步。

(3) 判断当前条目所在叶节点的条目个数是否小于L，如果是，则直接将数据点插入作 为该数据点的新条目，否则需要分裂该叶节点。分裂的原则是寻找该叶节点中距离最远的两 个条目并以这两个条目作为分裂后新的两个叶节点的起始条目，其他剩下的条目根据距离最 小原则分配到这两个新的叶节点中，删除原叶节点并更新整个CF 树。

当数据点无法插入时，这个时候需要提升阈值T 并重建树来吸收更多的叶节点条目， 直到把所有数据点全部插入完毕。

在 CF 树重建过程中，通过利用老树的叶节点来重新构建一棵新树，因而树的重建过程 不需要访问所有点，即构建CF 树只需访问数据一次就行。

算法步骤

Birch 算法主要分为以下两个阶段：

(1) 扫描数据库，动态的建立一棵存放在内存的CF 树。若内存不够，则增大阈值，在 原树基础上构造一棵较小的树。

(2) 对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。 由于 CF 树的叶节点代表的聚类可能不是自然的聚类结果，原因是给定的阈值限制了簇 的大小，并且数据的输入顺序也会影响到聚类结果。因此，需要对叶节点进一步利用一个全 局性的聚类算法，改进聚类质量。