系统聚类与K均值聚类算法原理

小象实战讲义 · 多元统计分析

聚类分析是探索数据内在结构、发现自然分组的重要工具。本节将系统讲解两种最经典的聚类算法：系统聚类（谱系聚类） 和 K均值聚类。通过本节学习，你将掌握从距离定义到完整聚类流程的核心原理，理解不同类间距离更新方法的差异，并能够使用Python实现这两种算法，为实际数据的分组分析打下坚实基础。

💡 核心导读

• 系统聚类基本思想：从每个样本自成一类开始，逐步合并距离最近的类，直至所有样本聚为一类，形成完整的谱系图。
• 核心类间距离方法：重点掌握最短距离法、最长距离法、类平均法和离差平方和法（Ward法）的计算原理与适用场景。
• 谱系图解读与应用：通过谱系图可视化聚类过程，根据实际需求确定最佳分类数。
• K均值聚类动态调整：理解K均值聚类的迭代优化思想，掌握初始中心选择、样本重分配和中心更新的完整流程。
• 算法对比与选择：分析系统聚类与K均值聚类在计算复杂度、结果稳定性和适用场景上的差异。

系统聚类（谱系聚类）的基本原理

系统聚类的基本思想

系统聚类（Hierarchical Clustering）是一种自底向上的聚类方法，其核心思想是：距离相近的样本先聚成类，距离相远的样本后聚成类。整个过程是一个不可逆的、一次性的合并过程。

系统聚类的基本步骤：

1. 初始化：将 $n$ 个样本各自视为一类，共 $n$ 类。
2. 计算初始距离矩阵：计算所有样本两两之间的距离，形成 $n \times n$ 的距离矩阵 $D^{(0)}$。
3. 合并最近类：找到距离矩阵中最小元素 $D_{pq}$，将对应的类 $G_p$ 和 $G_q$ 合并为新类 $G_r$。
4. 更新距离矩阵：计算新类 $G_r$ 与其他各类的距离，形成新的距离矩阵。
5. 迭代合并：重复步骤3-4，直到所有样本聚为一类。

谱系图：聚类过程的可视化

谱系图（Dendrogram）是系统聚类过程的直观表示。以常用的竖版谱系图为例：

• 横轴：表示样本索引或原始样本标签。
• 纵轴：表示样本或类之间的距离。
• 连接线的高度：表示合并时两类之间的距离（对应纵轴坐标）。

谱系图不仅展示了完整的聚类过程，还允许我们根据实际需求确定最佳分类数。通过在特定距离阈值处“切割”谱系图（画一条水平线），可以得到不同粒度的分类结果。

类间距离的计算方法

系统聚类的核心问题在于：合并形成新类后，如何计算新类与其他类之间的距离？ 针对这个问题，统计学家提出了八种不同的类间距离定义方法，本节重点讲解实践中最常用的四种。

1. 最短距离法（Single Linkage）

最短距离法定义类 $G_p$ 与 $G_q$ 之间的距离为两类中最近样本的距离： $$D_{pq} = \min_{X_i \in G_p, X_j \in G_q} d_{ij}$$

合并为新类 $G_r$ 后，新类与任意类 $G_k$ 的距离为： $$D_{kr} = \min(D_{kp}, D_{kq})$$

特点：容易形成“链状”结构，对噪声和异常值敏感。

2. 最长距离法（Complete Linkage）

最长距离法定义类 $G_p$ 与 $G_q$ 之间的距离为两类中最远样本的距离： $$D_{pq} = \max_{X_i \in G_p, X_j \in G_q} d_{ij}$$

合并后的距离更新公式为： $$D_{kr} = \max(D_{kp}, D_{kq})$$

特点：倾向于生成紧凑的、大小相近的类。

3. 类平均法（Average Linkage）

类平均法定义类 $G_p$ 与 $G_q$ 之间的距离为两类中所有样本对距离的平均值： $$D_{pq}^2 = \frac{1}{n_p n_q} \sum_{X_i \in G_p} \sum_{X_j \in G_q} d_{ij}^2$$

合并后的距离更新公式为： $$D_{kr}^2 = \frac{n_p}{n_r} D_{kp}^2 + \frac{n_q}{n_r} D_{kq}^2$$ 其中 $n_r = n_p + n_q$。

特点：平衡了最短和最长距离法的优缺点，是实践中常用的方法。

4. 离差平方和法（Ward法）

离差平方和法基于方差分析的思想：好的分类应该使类内离差平方和尽可能小，类间离差平方和尽可能大。

设类 $G_t$ 的离差平方和为： $$S_t = \sum_{X_i \in G_t} (X_i - \bar{X}_t)'(X_i - \bar{X}_t)$$ 其中 $\bar{X}_t$ 是类 $G_t$ 的重心。定义类 $G_p$ 与 $G_q$ 之间的距离为合并后离差平方和的增加量： $$D_{pq}^2 = S_r - (S_p + S_q)$$ 其中 $G_r = G_p \cup G_q$。

合并 $G_p$、$G_q$ 为 $G_r$ 后，任意类 $G_k$ 到新类的平方距离按 Lance-Williams 递推公式更新： $$D_{kr}^2 = \frac{n_k+n_p}{n_k+n_r} D_{kp}^2 + \frac{n_k+n_q}{n_k+n_r} D_{kq}^2 - \frac{n_k}{n_k+n_r} D_{pq}^2$$ 其中 $n_r = n_p + n_q$。注意上式是平方距离的递推，不要与（非平方）距离的递推混用。

特点：倾向于生成大小相近的类；由于其距离定义同样基于类均值与类内离差平方和（机制与K均值同源），对异常值同样敏感，使用前宜做离群点筛查。

K均值聚类（快速聚类法）

K均值聚类的基本思想

K均值聚类是一种动态的、迭代的聚类方法，也称为快速聚类法。与系统聚类不同，K均值聚类需要预先指定聚类数 $K$，然后通过迭代优化将样本分配到 $K$ 个类中。

K均值聚类的基本步骤：

1. 初始化：随机选择 $K$ 个样本作为初始聚类中心。
2. 分配样本：计算每个样本到各聚类中心的距离，将其分配到最近的类。
3. 更新中心：重新计算每个类的中心（均值）。
4. 迭代优化：重复步骤2-3，直到聚类中心不再变化或达到最大迭代次数。

K均值聚类的数学描述

设有 $n$ 个样本 $X_1, X_2, \ldots, X_n \in \mathbb{R}^p$，要将其分为 $K$ 个类 $C_1, C_2, \ldots, C_K$。K均值聚类的目标是最小化类内离差平方和： $$J = \sum_{k=1}^K \sum_{X_i \in C_k} \|X_i - \mu_k\|^2$$ 其中 $\mu_k = \frac{1}{|C_k|} \sum_{X_i \in C_k} X_i$ 是类 $C_k$ 的中心。

K均值聚类的优缺点

优点：计算效率高，适合大规模数据集；算法简单，易于实现；对于球形分布的数据效果很好。 缺点：需要预先指定 $K$ 值；对初始中心敏感，可能收敛到局部最优；对异常值敏感；假设各类呈球形分布、各向同性。

Python实战：聚类算法实现与比较

下面我们通过Python代码演示系统聚类和K均值聚类的实现，并比较不同类间距离更新方法的效果。

"""
多元统计分析 系统聚类与K均值聚类实战
核心功能：层次聚类四种距离比较 + K均值聚类效果验证
"""
import numpy as np
from scipy.spatial.distance import pdist
from scipy.cluster.hierarchy import linkage, cophenet, fcluster
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_blobs
from sklearn.metrics import adjusted_rand_score

# 设置随机种子确保结果可复现
np.random.seed(42)

# 生成模拟数据：3个明显分离的簇，共150个样本
X, y_true = make_blobs(n_samples=150, centers=3, cluster_std=0.8, random_state=42)
# 数据标准化（消除量纲影响）
X_scaled = StandardScaler().fit_transform(X)

# ---------------------- 1. 系统聚类：四种方法对比 ----------------------
# 计算样本间欧氏距离（压缩格式）
dist_condensed = pdist(X_scaled, metric='euclidean')
methods = ['single', 'complete', 'average', 'ward']  # 四种常用链接方法
best_c, best_method = 0, ''

for method in methods:
    # 执行层次聚类
    Z = linkage(dist_condensed, method=method)
    # 计算共性相关系数：衡量聚类结果与原始距离的一致性，越接近1越好
    c, _ = cophenet(Z, dist_condensed)
    if c > best_c:
        best_c, best_method = c, method
    print(f"{method.capitalize()} 共性相关系数: {c:.4f}")
print(f"\n最优方法: {best_method} (共性相关系数: {best_c:.4f})")

# 从最优谱系图中提取3类聚类结果
Z_best = linkage(dist_condensed, method=best_method)
clusters_hier = fcluster(Z_best, t=3, criterion='maxclust')

# ---------------------- 2. K均值聚类 ----------------------
# 执行K均值聚类（K=3，k-means++初始化优化初始中心）
kmeans = KMeans(n_clusters=3, init='k-means++', n_init=10, random_state=42)
clusters_kmeans = kmeans.fit_predict(X_scaled)

# ---------------------- 3. 算法效果对比 ----------------------
# 计算类内离差平方和（越小说明类内越紧凑）
def calc_inertia(X, labels):
    inertia = 0
    for label in np.unique(labels):
        cluster = X[labels == label]
        centroid = cluster.mean(axis=0)
        inertia += np.sum((cluster - centroid) ** 2)
    return inertia

inertia_hier = calc_inertia(X_scaled, clusters_hier)
inertia_kmeans = kmeans.inertia_
acc = adjusted_rand_score(clusters_hier, clusters_kmeans) * 100

print(f"\n系统聚类类内离差平方和: {inertia_hier:.2f}")
print(f"K均值聚类类内离差平方和: {inertia_kmeans:.2f}")
print(f"两种方法结果一致性: {acc:.2f}%")

运行上述代码可得：四种系统聚类方法中，类平均法（average）的共性相关系数最高（约0.9859），说明其聚类结果与原始样本距离的一致性最好；系统聚类与K均值聚类的结果完全一致（100%匹配），类内离差平方和约为6.07，均能准确识别出3个天然簇。

📝 动手练一练

1. 谱系图解读练习 假设你得到了一个包含20个样本的谱系图，在距离阈值为3.5处切割得到4个类。请回答：

   • 如果要将样本分为更细的类别，应该提高还是降低距离阈值？
   • 如果某个类在距离1.2处形成，另一个类在距离4.8处形成，这说明了什么？

   参考答案：

   • 要得到更细的类别，应该降低距离阈值，更早切割谱系图会得到更多、更紧凑的类。
   • 距离1.2处形成的类内部样本相似度高，是紧密的自然簇；距离4.8处形成的类内部差异较大，可能由多个松散子类合并而成。

2. K均值聚类参数选择 使用肘部法则时，K值与类内离差平方和对应关系为：K=1→250.0，K=2→120.0，K=3→65.0，K=4→40.0，K=5→30.0。根据肘部法则，最佳K值是多少？为什么？

   参考答案： 最佳K值是3。K从1到3时，离差平方和大幅下降，说明增加聚类数显著提升效果；K=3之后下降幅度明显放缓，出现“肘部”拐点，增加聚类数的收益骤降，因此K=3是最优选择。

本章小结

本节深入讲解了两种核心聚类算法：系统聚类和K均值聚类。系统聚类通过自底向上的合并过程构建完整的谱系结构，提供了数据层次关系的全景视图；而K均值聚类通过迭代优化快速找到紧凑的球形簇，适合大规模数据分析。

关键要点回顾：

1. 系统聚类是不可逆的层次聚类过程，四种核心类间距离方法各有特点，类平均法和Ward法在实践中最为常用。
2. 谱系图是系统聚类的可视化工具，通过切割谱系图可以在不同粒度上获取聚类结果。
3. K均值聚类需要预先指定K值，通过迭代优化最小化类内离差平方和，对初始中心敏感。
4. 肘部法则是确定K均值最佳聚类数的实用方法，通过观察离差平方和随K值变化的拐点选择K。

聚类分析是探索性数据分析的强大工具，正确的方法选择和结果解读同样重要。实际应用中，建议结合业务背景和多种评估指标选择最合适的聚类方案。

— 小象教研组