【数据聚类】第六章第二节：层次聚类算法之BIRCH算法

注意：文章中部分内容来自刘建平博客，多谢多谢：刘建平：BIRCH聚类算法原理

文章目录

一：BIRCH算法概述
二：BIRCH算法流程

一：BIRCH算法概述

BIRCH算法：该算法于1996年提出，尤其适用于大型数据库。它会增量地对输入数据进行聚类，有时甚至只需对所有数据扫描一遍就可以产生结果，当然额外的扫描肯定可以提升聚类效果，而且还可以有效处理噪声。BIRCH算法需要引入以下两个概念

聚类特征（CF）
聚类特征数（CF树）

聚类特征数类似于平衡B+树，CF树的每个结点是由若干聚类特征CF组成的

（1）聚类特征CF

聚类特征CF：一个聚类特征由一个三元组表示，它给出了一个簇的汇总描述。在大小为 $N$ 的 $d$ 维数据集 ${x_{1},x_{2},...,x_{N}\}$ 上，定义聚类特征如下

$CF=(N,\vec{LS},SS)$

$N$ ：数据数量
$\vec{LS}$ ： $N$ 个数据点的线性和，也即 $\sum\limits_{i=1}^{N} \vec{x_{i}}$
$SS$ ： $N$ 个数据点的平方和，也即 $\sum\limits_{i=1}^{N} \vec{x_{i}^{2}}$

聚类特征是可以求和的

$CF_{1}=(N_{1},\vec{LS_{1}},SS_{1})$
$CF_{2}=(N_{2},\vec{LS_{2}},SS_{2})$
$CF_{1}+CF_{2}=(N_{1}+N_{2},\vec{LS_{1}}+\vec{LS_{2}},SS_{1}+SS_{2})$

如下图，有5个样本形成的一个簇，分别是 $(3, 4), (2, 6), (4, 5), (4, 7), (3, 8)$ ，则有

$N$ ：5
$\vec{LS}$ ： $(3 + 2 + 4 + 4 + 3, 4 + 6 + 5 + 7 + 8) = (16, 30)$
$SS$ ： $3^{2}+2^{2}+4^{2}+4^{2}+3^{2} +4^{2}+6^{2}+5^{2}+7^{2}+8^{2})=244$

在这里插入图片描述

（2）聚类特征树

聚类特征树：一个CF树存储了层次聚类的聚类特征。它存储了层次聚类的聚类特征。下图是一个典型的CF树。CF树中每个非叶结点存储的CF是其孩子结点的CF总和，也即父结点存储的信息是其子结点存储信息的汇总。一个叶子结点至多包含 $L$ 个条目，每个条目是一个聚类特征三元组，每个叶子结点有两个指针，即prev和next，用来把所有的叶子结点连接起来

一个CF树有如下两个参数，当阈值 $T$ 越大时树就会越小，它们决定了树的大小

分支因子 $B$ ：表示每个非叶结点最大的孩子数目
阈值 $T$ ：：表示存储在树的叶子结点中的子聚类的最大半径

在这里插入图片描述

如下图，在CF树中，对于父结点的每个CF结点，它的 $(N,\vec{LS},SS)$ 三元组的值等于这个CF结点所指向的所有子结点的三元组之和

在这里插入图片描述

（3）聚类特征树的生成

A：生成规则

聚类特征树的生成规则：CF树是随数据的输入动态增长的，生成CF树的步骤如下

找到要插入的叶子结点：从CF树根结点开始，通过比较结点的CF值找到距离最近的簇，然后从该簇的孩子结点中继续找到距离最近的簇，直到最后找到叶子结点
修改叶子结点：找到叶子结点中距离最近的条目，检查该叶子结点能够再加入新条目，可以的话直接加入，不可以的话分裂叶子结点并加入条目
更新路径的CF信息：从插入的叶子结点自下而上更新CF树上的CF值信息