BIRCH聚类算法详解（微信文章未删减版）

欢迎关注”生信修炼手册”!

BIRCH算法全称如下

Balanced Iterative Reducing and Clustering Using Hierarchies

属于树状结构的层次聚类算法的一种，其树状结构的构建是自上而下的，也就是说我们只需要扫描一遍数据，就可以得到树状结构了，因此该算法的运行速度很快。

要理解该算法的运行过程，需要理解以下两个基本概念

1. Cluster Feature

简称CF, 每个CF本质上是一个3元组，由N, LS, SS共3个元素构成，其中

1. N表示样本数目

2. LS表示样本各特征的和

3. SS表示样本各特征的平方和

具体的求解过程图示如下

LS的计算公式如下

对于图中所示的5个点，LS的求解过程如下

>>> ( 3 + 2 + 4 + 4 + 3, 4 + 6 + 5 + 7 + 8)
(16, 30)

SS的计算公式如下

对于图中所示的5个点，SS的求解过程如下

>>> ( 3 ** 2 + 2 ** 2 + 4 ** 2 + 4 ** 2 + 3 ** 2, 4 ** 2 + 6 ** 2 + 5 ** 2 + 7 ** 2 + 8 ** 2)
(54, 190)

2. Cluster Feature Tree

简称CF tree, 其结构如下

可以分为根节点，内部节点，叶子节点3大类，其中每个节点都是有多个CF构成的。对于一颗CF tree, 有以下3个重要参数

1. 内部节点的最大CF数目，称之为枝平衡因子B

2. 叶子节点的最大CF数目，称之为叶平衡因子L

3. 叶子节点的空间阈值T，计算样本点与CF的空间距离，如果小于阈值，则将样本纳入某个CF

3个参数在CF tree中的作用图示如下

定义好上述3个参数之后，就可以开始扫描数据，构建CFtree, 对于第一个样本，CF为空，首先将其自身归入一个CF

对于第二个样本，判断其与样本A的距离是否大于空间阈值T, 因为小于T, 所以该样本也归入A所属的CF

对于第三个样本，同样计算空间距离，因为大于T, 所以该样本归为一个新的CF, 从而实现了节点的分裂

对于第4个样本，计算空间距离，发现属于B所在的空间，则归为B所在的CF

在构建CF tree的过程中，除了空间距离，还需要考虑平衡因子B和L。比如对于以下LN1节点而言，如果叶平衡因子L的值大于3，则sc8这个CF就可以作为LN1的一个叶子节点

如果小于3，就需要分裂出一个新的分支，分裂时，从LN1下所有的CF中挑选出距离最小和最大的两个CF, 作为新的内部节点，图示如下

枝平衡因子B影响内部节点的结构，如果B的值小于3，则要对内部节点进行拆分，分裂的方法是相同的，就是挑选距离最近和最远的两个CF作为新的分支，分裂后的结果图示如下

对于BIRCH算法而言，主要的步骤就是构建CF tree, 树状结构构建好之后，后续还可以有些可选步骤，常见的可选步骤如下

1. 去除异常的CF点，通常是包含样本较少的CF

2. 利用其它聚类算法，比如K-means 对CF Tree进行聚类，用于调整样本读入顺序造成的树状结构的不合理

3. 利用CF节点的质心，对样本点进行聚类

在scikit-learn中，使用BIRCH聚类的代码如下

>>> from sklearn.cluster import Birch
>>> X = [[0, 1], [0.3, 1], [-0.3, 1], [0, -1], [0.3, -1], [-0.3, -1]]
>>> brc = Birch(n_clusters=None)
>>> brc.fit(X)
Birch(n_clusters=None)
>>> brc.predict(X)
array([0, 0, 0, 1, 1, 1])

BIRCH算法的优点是节约内存，聚类速度快，可以不用指定聚类的类别数目K, 适合处理类别数目特别多的大样本数据，缺点则是在给定的平衡因子和空间阈值参数值的约束下，聚类的结果可能和真实分布不一样，而且对于维数特别多的数据，聚类效果不太好。

·end·

—如果喜欢，快分享给你的朋友们吧—

原创不易，欢迎收藏，点赞，转发！生信知识浩瀚如海，在生信学习的道路上，让我们一起并肩作战！

本公众号深耕耘生信领域多年，具有丰富的数据分析经验，致力于提供真正有价值的数据分析服务，擅长个性化分析，欢迎有需要的老师和同学前来咨询。