Birch聚类算法解析：从原理到大规模数据实战

1次阅读

共计 1755 个字符，预计需要花费 5 分钟才能阅读完成。

在处理 TB 级数据时，传统聚类算法如 K -means 面临显著挑战：

计算复杂度高 ：K-means 需要多次遍历整个数据集，时间复杂度为 $O(n \times k \times i)$，其中 $n$ 是数据量，$k$ 是聚类数，$i$ 是迭代次数
内存占用大 ：需要将所有数据加载到内存中进行计算
参数敏感 ：初始质心的选择会极大影响最终结果

特性	Birch	DBSCAN	K-means
时间复杂度	$O(n)$	$O(n\log n)$	$O(n\times k\times i)$
内存占用	低 (CF 树压缩)	中	高
参数敏感性	中等 (主要依赖 T)	高 (ε 和 minPts)	高 (初始质心)
形状适应性	球形簇	任意形状	球形簇

CF(Clustering Feature) 是 Birch 的核心数据结构，包含三个统计量：

$N$：簇中点的数量
$LS$：线性和 (各维度之和)
$SS$：平方和 (各维度平方和)

CF 树的构建分为 4 个步骤：

初始化空树，设置阈值参数 T
逐个插入数据点，寻找最近叶节点
如果点能被当前 CF 吸收 (距离 <T)，则更新 CF
否则创建新 CF 节点，必要时分裂父节点

T 值控制聚类粒度：

T 较大时：生成较少但较大的簇
T 较小时：生成较多但紧凑的簇
最优 T 值通常通过肘部法则确定

from sklearn.cluster import Birch
from sklearn.preprocessing import StandardScaler
import numpy as np

# 生成示例数据
np.random.seed(42)
X = np.concatenate([np.random.normal(0, 1, (1000, 10)),
    np.random.normal(5, 1, (1000, 10))
])

# 数据标准化
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# 创建 Birch 模型
# n_clusters=None 表示使用 CF 树结构直接输出
# 设置为 K 值时等效于 Birch+K-means 两阶段聚类
birch = Birch(
    threshold=0.5,          # 阈值参数 T
    branching_factor=50,    # 分支因子 B
    n_clusters=2            # 最终聚类数
)

# 训练模型
birch.fit(X_scaled)

# 获取聚类结果
labels = birch.predict(X_scaled)

from pyspark.ml.clustering import BisectingKMeans
from pyspark.ml.feature import VectorAssembler

# 数据准备
assembler = VectorAssembler(inputCols=[f'col_{i}' for i in range(10)],
    outputCol='features'
)

# 使用二分 K -means 近似实现 (Spark 暂无原生 Birch)
bkm = BisectingKMeans(
    k=2,
    minDivisibleClusterSize=1.0
)

# 构建 Pipeline
pipeline = Pipeline(stages=[assembler, bkm])
model = pipeline.fit(spark_df)