什么是桦木?

BIRCH 表示使用层次结构的平衡迭代减少和聚类。它旨在通过集成层次聚类和其他聚类方法(包括迭代分区)来对大量数值记录进行聚类。

BIRCH 提供了聚类特征和聚类特征树(CF 树)两个概念,用于概括聚类描述。这些结构有助于集群方法在庞大的数据库中实现最佳速度和可扩展性,并使其对传入对象的增量和动态集群有效。

给定一个簇中的 n 维数据对象或点,它可以表示簇的质心 x 0、半径 R 和直径 D 如下 -

$$x_{0}=\frac{\sum_{i=1}^{n}x_{i}}{n}$$

$$R=\sqrt{\frac{\sum_{i=1}^{n}(x_{i}-x_{0})^{2}}{n}}$$

$$D=\sqrt{\frac{\sum_{i=1}^{n}\sum_{j=1}^{n}(x_{i}-x_{j})^{2}}{n (n-1)}}$$

其中 R 是成员元素到质心的平均距离,D 是簇内的平均成对距离。R 和 D 都反转了质心周围簇的紧密度。聚类特征 (CF) 是一个 3 维向量,用于汇总有关对象聚类的数据。给定簇中的 n 个 d 维对象或点,{x i },则簇的 CF 表示为

CF=(n,LL,SS)

其中 n 是聚类中的点数,LS 是 n 个点的线性和 $\sum_{i=1}^{n}(x_{i})$,SS 是数据点的平方和(即$\sum_{i=1}^{n}x_{i}^{2}$)

聚类特征是给定聚类的统计信息的汇总:从统计的角度来看聚类的第零、一阶和二阶矩。聚类特征是一个补充。例如,假设我们有两个不相交的集群 C1 和 C2,它们通常具有聚类特征 CF1 和 CF2。通过组合 C1 和 C2 形成的集群的聚类特征是简单的 CF1 +CF2。

聚类特征足以计算在 BIRCH 中制定聚类决策所需的所有测量。BIRCH 通过使用聚类功能来汇总有关对象集群的数据,从而有效地使用存储,从而绕过保存所有对象的要求。

CF树是一种高度平衡的树,它保存了层次聚类的聚类特征。树中的非叶节点有后代或“孩子”。非叶节点存储其子节点的 CF 总和,因此汇总了有关其子节点的聚类数据。

CF 树有两个参数,包括分支因子 B 和阈值 T。分支元素定义每个非叶节点的最大子节点数。阈值参数定义了保存在树叶节点的子簇的最大直径。这两个参数保存结果树的大小。