数据挖掘中的BIRCH

BIRCH（平衡迭代聚类层次结构）是一种无监督数据挖掘算法，可对大型数据集执行层次聚类。通过修改，它还可以用于加速 k-means 聚类和期望最大化算法的高斯混合模型。BIRCH 的一个优点是它能够渐进式地、动态地聚类传入的多维度度量数据点，以在给定资源（内存和时间限制）下实现最佳聚类质量。在大多数情况下，BIRCH 仅需一次数据库扫描。

其发明者声称 BIRCH 是“数据库领域提出的第一个有效处理‘噪声’（不属于底层模式的数据点）的聚类算法”，比 DBSCAN 早两个月。BIRCH 算法于 2006 年获得了 SIGMOD 十年最佳论文奖。

K-means 和凝聚聚类等基本聚类算法是最常用的聚类算法。但当对非常大的数据集进行聚类时，BIRCH 和 DBSCAN 是适用于对大型数据集进行精确聚类的先进聚类算法。此外，BIRCH 由于其易于实现而非常有用。BIRCH 是一种聚类算法，它首先对数据集进行小摘要聚类，然后对小摘要进行聚类。它不直接聚类数据集。这就是为什么 BIRCH 经常与其他聚类算法一起使用；在制作摘要后，摘要也可以被其他聚类算法聚类。

它被提供为 MinibatchKMeans 的替代方案。它将数据转换为树形数据结构，其中质心从叶节点读取。这些质心可以是最终的簇质心，也可以是 Agglomerative Clustering 等其他簇算法的输入。

先前聚类算法的问题

先前的聚类算法在非常大的数据库上性能较差，并且没有充分考虑数据集过大而无法放入主内存的情况。此外，BIRCH 的大多数前身在每次聚类决策时都平等地检查所有数据点（或所有现有簇）。它们不根据数据点之间的距离执行启发式加权。结果是，在最大限度地降低额外 I/O（输入/输出）操作成本的同时，保持高聚类质量会产生大量开销。

BIRCH 的阶段

BIRCH 通常通过创建数据集的摘要来补充其他聚类算法，其他聚类算法现在可以使用该摘要。但是，BIRCH 有一个主要缺点，它只能处理度量属性。度量属性是其值可以在欧几里得空间中表示的属性，即不应存在分类属性。BIRCH 聚类算法包含两个阶段：

1. 构建 CF 树： BIRCH 将大型数据集汇总为较小的、密集区域，称为聚类特征（CF）条目。形式上，CF 条目定义为有序三元组（N、LS、SS），其中“N”是簇中的数据点数量，“LS”是数据点的线性总和，“SS”是簇中数据点的平方和。CF 条目可以由其他 CF 条目组成。可选地，我们可以将此初始 CF 树压缩为较小的 CF。
2. 全局聚类： 将现有聚类算法应用于 CF 树的叶节点。CF 树是一种树，其中每个叶节点包含一个子簇。CF 树中的每个条目都包含指向子节点的指针，以及由子节点 CF 条目总和组成的 CF 条目。可选地，我们可以细化这些簇。

由于这种两步过程，BIRCH 也被称为两步聚类。

算法

给定数据的树结构由 BIRCH 算法构建，称为聚类特征树（CF 树）。该算法基于 CF（聚类特征）树。此外，该算法使用树状摘要来创建簇。

在 CF 树的上下文中，算法将数据压缩到 CF 节点集合中。拥有多个子簇的节点可以称为 CF 子簇。这些 CF 子簇位于非终端 CF 节点中。

CF 树是一个高度平衡的树，它收集和管理聚类特征，并保存给定数据的必要信息以供进一步的层次聚类。这避免了处理整个输入数据的需要。由 CF 表示的数据点的树簇由三个数字（N、LS、SS）表示。

• N = 子簇中的项目数
• LS = 数据点的向量和
• SS = 数据点的平方和

BIRCH 算法主要遵循四个阶段。

• 将数据扫描到内存中。
• 压缩数据（调整数据大小）。
• 全局聚类。
• 细化簇。

这四个阶段中有两个（调整数据大小和细化簇）是可选的。当需要更高的清晰度时，它们会出现在过程中。但扫描数据就像将数据加载到模型中一样。加载数据后，算法会扫描整个数据并将其拟合到 CF 树中。

在压缩中，它会重置和调整数据大小，以便更好地拟合到 CF 树中。在全局聚类中，它使用现有的聚类算法将 CF 树发送进行聚类。最后，细化修复了 CF 树中相同值的点被分配到不同叶节点的问题。

聚类特征

BIRCH 聚类通过巧妙地使用一组小的汇总统计信息来表示大量数据点，从而实现高效率。这些汇总统计信息构成了 CF，并足以替代用于聚类的实际数据。

CF 是一个由三个汇总统计信息组成的集合，代表了一个簇中的一组数据点。这些统计信息如下：

• 计数 [簇中数据值的数量]
• 线性总和 [各个坐标的总和。这是簇位置的度量]
• 平方和 [平方坐标的总和。这是簇分布的度量]

注意：线性总和与平方和分别等同于数据点的均值和方差。

CF 树

CF 树的构建过程可以总结为以下步骤，例如：

步骤 1：对于每个给定的记录，BIRCH 将该记录的位置与根节点中每个 CF 的位置进行比较，使用 CF 的线性总和或平均值。BIRCH 将传入的记录传递给最接近传入记录的根节点 CF。

步骤 2：然后，记录会下降到步骤 1 中选择的根节点 CF 的非叶子节点。BIRCH 将记录的位置与每个非叶子 CF 的位置进行比较。BIRCH 将传入的记录传递给最接近传入记录的非叶子节点 CF。

步骤 3：然后，记录会下降到步骤 2 中选择的非叶子节点 CF 的叶子子节点。BIRCH 将记录的位置与每个叶子的位置进行比较。BIRCH 会暂时将传入的记录传递给最接近传入记录的叶子。

步骤 4：执行以下任一（i）或（ii）点：

1. 如果选定叶子的半径（包括新记录）不超过阈值 T，则将传入记录分配给该叶子。叶子及其父 CF 会更新以考虑新数据点。
2. 如果选定叶子的半径（包括新记录）超过阈值 T，则会形成一个新叶子，仅包含传入记录。父 CF 会更新以考虑新数据点。

如果执行了步骤 4(ii)，并且叶节点中已有最大 L 个叶子，则叶节点会拆分为两个叶节点。如果父节点已满，则拆分父节点，依此类推。距离最远的叶节点 CF 用作叶节点种子，其余 CF 被分配给离它们最近的叶节点。请注意，即使不知道数据点，只要我们有计数 n、线性总和 LS 和平方和 SS，就可以计算簇的半径。这使得 BIRCH 能够在不扫描原始数据集的情况下评估给定数据点是否属于特定子簇。

对子簇进行聚类

一旦 CF 树构建完成，任何现有的聚类算法都可以应用于子簇（CF 叶节点），将这些子簇合并成簇。聚类任务变得容易得多，因为子簇的数量远少于数据点的数量。当添加新数据值时，可以轻松更新这些统计信息，从而提高计算效率。

BIRCH 参数

此算法中有三个需要调整的参数。与 K-means 不同，用户无需输入最佳簇数 (k)，因为算法会自行确定。

• 阈值：阈值是 CF 树叶节点中子簇可以容纳的最大数据点数。
• 分支因子：此参数指定每个节点（内部节点）中 CF 子簇的最大数量。
• n_clusters：在整个 BIRCH 算法完成后的返回的簇数，即最终聚类步骤后的簇数。如果设置为 none，则不执行最终聚类步骤，并返回中间簇。

BIRCH 的优点

它是局部的，因为每个聚类决策都是在不扫描所有数据点和现有簇的情况下做出的。它利用了数据空间通常不是均匀分布的观察，并且并非所有数据点都同样重要。

它利用可用内存生成最精细的子簇，同时最大限度地降低 I/O 成本。它也是一种增量方法，不需要提前准备整个数据集。