层次聚类之经典算法（一） Birch算法

一、Birch算法简介：

BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）全称是：利用层次方法的平衡迭代规约和聚类。
Birch算法就是通过聚类特征(CF)形成一个聚类特征树，root 层的CF个数就是聚类个数。

1.1 算法流程

BIRCH 算法利用了一个树结构来帮助我们快速的聚类，这个树结构类似于平衡 B+ 树，一般将它称之为聚类特征树(Clustering Feature Tree，简称CF Tree)。这颗树的每一个节点是由若干个聚类特征(Clustering Feature，简称CF)组成。

BIRCH 算法流程如下图所示：

整个算法实现共分为 4 个阶段：

1. 扫描所有数据，建立初始化的 CF 树，把稠密数据分成簇，稀疏数据作为孤立点对待。
2. 这个阶段是可选的，阶段 3 的全局或半全局聚类算法有着输入范围的要求，以达到速度与质量的要求，所以此阶段在阶段 1 的基础上，建立一个更小的 CF 树。
3. 补救由于输入顺序和页面大小带来的分裂，使用全局/半全局算法对全部叶节点进行聚类。
4. 这个阶段也是可选的，把阶段 3 的中心点作为种子，将数据点重新分配到最近的种子上，保证重复数据分到同一个簇中，同时添加簇标签。

1.2 算法特点

1. BIRCH算法比较适合于数据量大，类别数 K 也比较多的情况。
2. 由于使用半径和直径概念，特别适用于球形数据的聚类（可以在聚类前进行样本绘图观察后选择该算法）。
3. 它运行速度很快，只需要单遍扫描数据集就能进行聚类。
4. BIRCH算法聚类速度快、能识别噪音点；但对高维、非凸数据效果不好

参考链接
[1] 机器学习之经典算法（十六） Birch算法
[2] BIRCH聚类算法 2017.10
[3] 聚类算法的缺点_聚类算法（BIRCH）2021.1