【聚类】层次聚类

层次聚类

1. 算法介绍

• 背景与目标
  层次聚类（Hierarchical Clustering）是一类无需事先指定簇数的聚类方法，通过构造一棵“树状图”（dendrogram）来呈现数据的多层次聚类结构。常见的有：

  • 凝聚式（Agglomerative）：自底向上，先将每个样本视为一个簇，逐步合并最近的两个簇；
  • 分裂式（Divisive）：自顶向下，先将所有样本视为一个簇，逐步将簇拆分成更小的簇。

• 应用场景

  • 基因表达、文本、图像等需要展示多粒度簇结构的场景
  • 探索数据的树状或层次结构
  • 做可解释性分析，比如客户层次分群

• 核心思路（以凝聚式为例）

  1. 计算所有样本两两之间的距离；

  2. 初始化：每个样本作为一个独立簇；

  3. 迭代合并：

     • 找到当前所有簇对中距离最小的一对；
     • 按照选定的“链接准则”（linkage）合并这两个簇；
     • 更新聚类间距离矩阵；

  4. 停止条件：当只剩下一簇或达到预定簇数时结束，生成完整树状图。

2. 公式及原理

2.1 距离度量
对任意两点 ${\mathbf{x}}_i,{\mathbf{x}}_j$，首先定义距离：

$$d({\mathbf{x}}_i,{\mathbf{x}}_j)=\Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }_2\text{（也可用其他度量如曼哈顿距离）}.$$

2.2 链接准则（Linkage）
当有两个簇 $C_a,C_b$ 时，用以衡量它们之间“距离”的方法：

• 单链接（single）：

  $$d_{\min }(C_a,C_b)=\underset{i\in C_a,j\in C_b}{\min }d({\mathbf{x}}_i,{\mathbf{x}}_j).$$

• 全链接（complete）：

  $$d_{\max }(C_a,C_b)=\underset{i\in C_a,j\in C_b}{\max }d({\mathbf{x}}_i,{\mathbf{x}}_j).$$

• 平均链接（average）：

  $$d_{\mathrm{avg}}(C_a,C_b)=\frac{1}{|C_a||C_b|}\sum _{i\in C_a}\sum _{j\in C_b}d({\mathbf{x}}_i,{\mathbf{x}}_j).$$

• Ward 链接（最小化簇内方差增量）：

  $$\Delta J=\frac{|C_a||C_b|}{|C_a|+|C_b|}\Vert {\mathbf{\mu }}_a-{\mathbf{\mu }}_b{\Vert }^2,$$

  其中 ${\mathbf{\mu }}_a$、${\mathbf{\mu }}_b$ 分别是簇的质心。

2.3 树状图构建

• 在每一步合并时记录所合并的簇对及它们之间的距离，就能得到一棵二叉合并树（dendrogram）；
• 根据树的高度（合并距离）可截取不同层次得到不同数目的簇。

3. 伪代码

# 输入
#   X: 数据矩阵，形状 (n, d)
#   linkage: 链接准则，选项 {single, complete, average, ward}
#   K: 期望最终簇数（或直到合并到 1 簇）
# 输出
#   merges: 合并记录列表，每条 (簇索引 a, 簇索引 b, 距离, 新簇大小)
#   labels: 样本最终簇标号，长度 n

function HierarchicalClustering(X, linkage, K):
    n ← number_of_rows(X)

    # 1) 初始化：每个样本一个簇
    clusters ← [{i} for i in 1…n]
    # 2) 计算初始距离矩阵 D (n×n)，D[i,j]=d(x_i,x_j)
    D ← pairwise_distance_matrix(X)

    merges ← empty_list()

    # 3) 不断合并直到簇个数为 K
    while len(clusters) > K:
        # 3.1 找到距离最小的簇对 (p,q)
        (p, q) ← indices_of_minimum(D)

        # 3.2 记录合并
        new_size ← |clusters[p]| + |clusters[q]|
        merges.append((p, q, D[p,q], new_size))

        # 3.3 合并簇：创建新簇 r
        clusters.append(clusters[p] ∪ clusters[q])

        # 3.4 更新距离矩阵：对所有其它簇 s
        for s in 1…len(clusters)-1 excluding p,q:
            D[s, r] ← compute_linkage_distance(
                          clusters[s], clusters[r], X, linkage)
            D[r, s] ← D[s, r]

        # 3.5 删除旧簇 p,q 及其对应行列
        remove rows/columns p and q from D
        remove clusters[p], clusters[q]

    # 4) 根据合并结果或截断高度，生成每个样本的簇标号 labels
    labels ← assign_labels_from_merges(merges, n, K)

    return merges, labels

• 时间复杂度

  • 计算初始距离矩阵：$O(n^{2}d)$
  • 每次合并更新：$O(n^2)$，共做 $n-K$ 步，整体 $O(n^3)$
  • 可借助优先队列、近似最近邻或稀疏方法加速到 $O(n^2\log n)$ 或更低