一个强大算法模型，层次聚类 ！！

哈喽，大家好~

今儿和大家聊聊层次聚类。

核心点事，层次聚类是一类通过迭代地合并或分裂簇来构建层级结构（树状）表示的数据聚类方法。

它与基于原型的 k-means 不同，不需要预先固定聚类数  ，而是通过生成一棵树以多尺度地刻画数据的簇结构，随后通过剪枝来选定一个聚类划分。

按照构建方式，层次聚类分为2类：

第一，自底向上的凝聚式：从每个样本一个簇开始，逐步寻找最相似的簇对进行合并，直至形成一棵树。

第二，自顶向下的分裂式：从全体样本作为一个簇开始，逐步将簇分裂为更小的簇。

从优化的视角看，层次聚类可被刻画为在簇之间的合并代价最小化的序列决策问题。不同的合并准则就对应不同的目标函数或启发式近似。

特别地，Ward 链接通过显式最小化类内平方误差（SSE）增长量来实现一个明确的优化目标。

设数据为  ， 。

层次聚类的输出是一棵二叉树  ，其叶子为样本，内部结点表示一次簇合并。设   为最终剪枝后的簇划分，则一个典型的优化目标可表述为最小化某种代价：

其中   描述簇   的紧致度或解释代价，例如 Ward 的 SSE。

下面，再从距离度量与相似性和大家聊聊~

距离度量与相似性

层次聚类的核心是如何度量点与簇、簇与簇的距离，这直接决定了合并策略。

我们常见的点对点距离有四种：

• 欧氏距离：
• 曼哈顿距离：
• 余弦距离：
• 马氏距离： ，其中   是协方差矩阵（或度量学习得到的矩阵）

我们在层次聚类中，簇与簇的距离定义依赖于合并准则，这决定了每一步合并时的最近簇对。常见链接包括：

• 单链接：簇间最近两个点的距离
• 全链接：簇间最远两个点的距离
• 平均链接：簇间所有点对距离的平均
• 加权平均
• Ward（方差最小化）：偏向球形且规模均衡的簇

Lance–Williams 递推公式

统一的合并更新框架。

层次聚类在合并簇   与   后，需要更新新簇   与其他簇   的距离。

Lance–Williams 公式给出了一个统一的递推形式：

不同链接对应不同的系数选择（其中   表示簇   的大小）：

• 单链接：

• 全链接：

• 平均链接：

• 加权平均：

• Ward（最小化 SSE 增长）：对欧氏距离，存在等价的 Lance–Williams 形式（见后续推导）。

  常用表达是：

  其中   是簇   的均值向量。更新时同样可写成 Lance–Williams 的系数形式（略繁，此处给出目标函数推导与等价结论）。

Lance–Williams 的重要性在于：它允许我们在无需回溯原始点对距离的情况下，仅用簇间距离递推地维持簇之间的距离信息。

这使得合并过程的复杂度较可控（但仍通常为   级别内存和时间）。

Ward 链接的优化

Ward 方法在每一步选择那一对簇合并，使得总体类内平方误差（SSE）增加最小。

我们设当前划分为  ，其目标可表述为最小化：

其中   为簇   的质心。

考虑合并两个簇   和  ，合并前的 SSE 为

合并后的新簇为  ，其质心为

合并后的 SSE 为

因此，合并代价（SSE 增量）为

利用均值和方差的分解恒等式（可由平方和展开并整理），可得经典结论：

因此，Ward 合并准则可等价为：每一步选择使   最小的一对簇   进行合并。由此也可得出一个等价的距离定义：

这解释了 Ward 方法偏好簇内方差小、形状近似球形的经验现象，并且在欧氏空间中与最小化 SSE 的目标严格一致。

进一步地，Ward 也可以纳入 Lance–Williams 框架，存在对应的系数组合，令更新与上述距离一致，从而与其他链接共享统一的递推更新机制。

单链接与最小生成树

单链接簇间距离定义为两簇之间最近两点的距离。

该方法易产生连锁效应，但具有一个重要性质：其合并次序等价于图上最小生成树（MST）按边权升序生成的过程（Kruskal 算法）。

直观地，考虑完全图  ，顶点为样本，边权为两点距离。

Kruskal 算法以从小到大的边权依次添加边，跳过会产生环的边。若将单链接聚类过程视为当最短跨簇边足够小则合并两个簇，则其合并序列与 MST 构造中边被接受并连接两个分量的次序一致。

由此也解释了单链接能跨越稀疏区域连接两个簇的现象（因为只要有一条短边便足以触发合并）。

理论上，单链接构建的凝聚树的合并高度等价于 MST 中对应连通分量通过最短边连接时的边长，从而单链接的层次结构与 MST 具有紧密对应关系。

这种关系意味着我们可用高效的 MST 近似策略来加速单链接的实现（如 SLINK 算法），在稀疏图情境下更可利用近邻图替代全图。

树切分与有效性指标

层次聚类得到的是一棵树，如何剪枝得到最终簇划分是一个核心优化问题。

常见策略：

• 指定簇数  ，在树上找到使簇数为   的切割
• 指定距离阈值  ，剪去高于阈值的合并边
• 使用有效性指标（如 Silhouette、CH、DB、Gap）在多种切割候选中选择最优

常见指标：

第一，平均轮廓系数

对样本  ，设其所在簇为  。定义

• ：样本   与同簇其他样本的平均距离
• ：样本   与最近的邻近簇（非  ）的平均距离（取最小者）

则轮廓系数：

整体评价取平均  。  越接近 1 表示聚类越明显，接近 0 表示簇间混合，负值表示可能被误分到错误簇。

第二，Davies–Bouldin（DB）指数

定义簇内散度  （例如均值到质心的平均距离），簇间距离  （例如质心间距离），则

DB 越小越好。

第三，Calinski–Harabasz（CH）指数

令   为类间离差平方和，  为类内离差平方和，样本数  ，簇数  ：

CH 越大越好。

第四，Cophenetic 相关系数

树的共生距离   定义为样本   与   在树上首次合并时对应的高度（合并距离）。

将原始距离   与   对比，计算皮尔逊相关：

该值越接近 1，说明层次树对原始距离结构的刻画越保真。

第五，Gap 统计量

用于选  ，对给定  ，比较数据的类内离差与在参考分布（如均匀）下的期望差异，定义

其中   是数据在   簇下的类内离差，  对参考数据取期望。Gap 越大表示聚类结构越显著。

完整案例

下面咱们使用 sklearn 与 scipy，使用一个合成的数据做层次聚类。

数据集特征：

• 高斯团簇（方差不同）
• 各向异性团簇（线性变换拉伸）
• 同心圆结构（非凸）
• 少量均匀噪声点

为便于 Ward 与欧氏距离，我们对数据进行标准化，注释非常详细，大家可以慢慢理解~

import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm
from sklearn.datasets import make_blobs, make_circles
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_samples, silhouette_score, davies_bouldin_score, calinski_harabasz_score, pairwise_distances
from sklearn.neighbors import kneighbors_graph
from scipy.cluster.hierarchy import linkage, dendrogram, cophenet, leaves_list
from scipy.spatial.distance import pdist, squareform
import warnings

warnings.filterwarnings("ignore", category=UserWarning)

np.random.seed(42)

# 1) 生成多个形态的簇
# 高斯团簇A、B
X1, y1 = make_blobs(n_samples=300, centers=[(-5, 0), (5, 0)], cluster_std=[1.2, 2.0], random_state=42)

# 各向异性簇C（旋转拉伸）
X2, y2 = make_blobs(n_samples=200, centers=[(0, 6)], cluster_std=[1.0], random_state=7)
A = np.array([[0.6, -1.2],
              [1.2,  0.8]])  # 线性变换矩阵
X2 = X2 @ A.T

# 同心圆簇D（非凸）
X3, y3 = make_circles(n_samples=250, factor=0.4, noise=0.06, random_state=21)
X3 = X3 * 4 + np.array([0, -7])  # 平移放缩

# 少量噪声点（均匀分布）
noise = np.random.uniform(low=-10, high=10, size=(60, 2))

# 合并数据
X = np.vstack([X1, X2, X3, noise])
n = X.shape[0]

# 标准化（对 Ward / 欧氏距离尤为重要）
scaler = StandardScaler()
X_std = scaler.fit_transform(X)

# 2) 构造连通性约束（可选）
# 使用 kNN 图约束合并，仅允许近邻合并，缓解非局部错误合并
connectivity = kneighbors_graph(X_std, n_neighbors=10, mode='connectivity', include_self=False)

# 3) 使用 Ward 的凝聚式层次聚类（sklearn）
# 指定聚类数量 K，可根据需求调整；也可先不指定，用阈值剪枝
K = 5
agg = AgglomerativeClustering(
    n_clusters=K,
    metric='euclidean',
    linkage='ward',
    connectivity=connectivity
)
labels = agg.fit_predict(X_std)


# 4) 为绘制树状图（dendrogram），使用 SciPy linkage（与 sklearn 模型等价设置）
# 注：scipy.linkage 的 'ward' 本质上使用欧氏距离与方差最小化准则
Z = linkage(X_std, method='ward', metric='euclidean')

# 5) 计算评估指标
sil_samples = silhouette_samples(X_std, labels, metric='euclidean')
sil_avg = silhouette_score(X_std, labels, metric='euclidean')
db_index = davies_bouldin_score(X_std, labels)
ch_index = calinski_harabasz_score(X_std, labels)

# Cophenetic 相关（衡量树对距离结构的保真度）
condensed_dist = pdist(X_std, metric='euclidean')
coph_corr, coph_dists = cophenet(Z, condensed_dist)

# 6) 距离矩阵热力图（按树的叶序重排）
leaf_order = leaves_list(Z)
Dmat = squareform(condensed_dist)
D_reordered = Dmat[leaf_order][:, leaf_order]

# 7) 可视化分析
# 图 1：Dendrogram
plt.figure(figsize=(8, 6), dpi=130)

heights = Z[:, 2]
if K > 1 and len(heights) >= K:
    color_threshold = np.sort(heights)[-K]
else:
    color_threshold = np.median(heights)

dendrogram(
    Z,
    color_threshold=color_threshold,
    no_labels=True,
    above_threshold_color='grey'
)
plt.title('图1：树状图 Dendrogram（彩色=剪枝阈值下方）', fontweight='bold')
plt.ylabel('合并距离 / 高度')
plt.grid(alpha=0.3)
plt.show()


# 图 2：按聚类结果着色的散点图
plt.figure(figsize=(8, 6), dpi=130)
cmap = cm.get_cmap('tab10', K)

for k in range(K):
    pts = X[labels == k]
    plt.scatter(
        pts[:, 0], pts[:, 1], 
        s=18, c=[cmap(k)], edgecolor='k', linewidth=0.3, 
        label=f'簇{k}'
    )

plt.title('图2：数据散点图（按聚类结果着色）', fontweight='bold')
plt.xlabel('x1')
plt.ylabel('x2')
plt.legend(markerscale=1.5, fontsize=8, frameon=True)
plt.grid(alpha=0.3)
plt.show()


# 图 3：Silhouette 分析
plt.figure(figsize=(8, 6), dpi=130)
y_lower = 10
yticks = []

for k in range(K):
    kth_sil = sil_samples[labels == k]
    kth_sil.sort()
    size_k = kth_sil.shape[0]
    y_upper = y_lower + size_k

    plt.fill_betweenx(
        np.arange(y_lower, y_upper),
        0,
        kth_sil,
        facecolor=cmap(k),
        edgecolor='k',
        linewidth=0.3,
        alpha=0.9
    )
    yticks.append((y_lower + y_upper) / 2)
    y_lower = y_upper + 10

plt.axvline(x=sil_avg, color='red', linestyle='--', linewidth=2, label=f'平均 Silhouette={sil_avg:.3f}')
plt.title('图3：Silhouette 分析', fontweight='bold')
plt.xlabel('轮廓系数 s(i)')
plt.ylabel('样本索引（分段代表不同簇）')
plt.yticks(yticks, [f'簇{k}' for k in range(K)], fontsize=8)
plt.xlim([-0.2, 1.0])
plt.grid(alpha=0.3)
plt.legend()
plt.show()


# 图 4：重排后的距离矩阵热力图
plt.figure(figsize=(8, 6), dpi=130)
im = plt.imshow(D_reordered, cmap='turbo', aspect='auto', interpolation='nearest')
plt.colorbar(im, fraction=0.046, pad=0.04)

plt.title('图4：重排后的距离矩阵热力图（按叶序）', fontweight='bold')
plt.xlabel('样本（树叶序）')
plt.ylabel('样本（树叶序）')
plt.show()


# 顶部指标信息
print(f"层次聚类（Ward, K={K}）")
print(f"Silhouette = {sil_avg:.3f}")
print(f"DB Index   = {db_index:.3f}")
print(f"CH Index   = {ch_index:.1f}")
print(f"Cophenetic = {coph_corr:.3f}")

树状图：

横轴为样本（隐含），纵轴为合并的高度（距离/代价）。每条分叉线表示一次簇合并。

彩色部分表示在指定剪枝阈值（color_threshold）下的合并，意味着在该阈值处剪断可得到若干簇。

可用来判断合理的剪枝位置：当合并高度突然出现跃迁（长枝）时，意味着结构层级显著；在此处剪枝可能得到稳健的簇数。

聚类散点图：

直观展示聚类结果。由于我们混合了各向异性簇与同心圆，Ward 更偏好近似球形、方差小的簇，非凸簇可能被切割成多个簇。

可用于观察聚类是否跨过稀疏区域、是否将不同形状簇切割等行为。

Silhouette 分析：

每个样本的轮廓系数   越接近 1 越好。条带在 0 以上且内部分布集中，意味着簇内部紧凑、簇间分离良好。

红色虚线为平均值，横向偏左侧（负值或接近 0）表示簇可分性不足或误分较多。

距离矩阵热力图：

显示样本两两距离，按树的叶序重排后若呈块对角结构，说明树在一定程度上重现了数据的簇结构。

明显的亮色分割线表示簇间距离较大；块内颜色较暗表示簇内相近。

训练与优化流程

事实上，虽然层次聚类不是典型的可微训练的模型，但我们仍可从优化的角度进行严谨流程设计：

首先，目标与约束方面：

• 若目标是最小化类内离差（SSE），则优先考虑 Ward（且使用欧氏距离与标准化）。
• 若重视簇的紧（直径小）而容忍连锁效应，考虑完全链接（Complete）。
• 若希望保留细长簇或图连通关系，单链接（Single）或图约束更合适。
• 若数据可能非凸且有环状结构，可先做非线性降维或用谱聚类/HDBSCAN 等方法替代。

然后，距离度量与预处理：

• 标准化/白化： ，减少量纲影响。
• 若存在高度相关特征，考虑 PCA/ICA 降维。
• 马氏或度量学习：在有少量监督信息时，可学习度量   替换欧氏距离。

选择簇数   或阈值：

• 在候选   上评估 Silhouette/CH/DB，并以模型选择的角度选择最优  。
• 若使用阈值剪枝，可通过 Dendrogram 的长枝作为启发式阈值。

稳健性与泛化：

• 对随机扰动（加入噪声、子采样）的敏感性评估。如果结果高度不稳定，说明结构不稳健或参数需要调整。
• 可做稳定聚类（bootstrap/子采样重复聚类并比较一致性）以增强置信。

常见问题

非凸簇（如同心圆）对 Ward 并不友好：Ward 倾向将圆环切割为若干扇形或小段，从而提升类内方差的均匀性。这是由 SSE 目标决定的，不是算法错误。

各向异性簇在未进行变换或度量学习时，会被 Ward 拉回近似球形偏好。如果业务上更关注真实几何形状，建议换链接或改度量。

噪声点常被最近的簇吸纳。可先做噪声剔除（如 DBSCAN 标注 outlier 后再做层次聚类），或用 robust 距离。

单链接的链化在高噪声数据中会更严重；Complete 则可能过分碎裂。

总结

我们从优化视角系统剖析了层次聚类：

• 理论与公式：Lance–Williams 统一递推、Ward 的 SSE 最小化推导、单链接与 MST 的等价关系、Cophenetic 等树保真度指标
• 实践与训练：标准化、度量选择、链接选择、连接性约束、剪枝与指标优化、规模化工程策略
• 代码与案例：给出 sklearn + scipy 的完整实现，生成复杂合成数据并完成四图联显分析，定量指标与可视化联动验证结果质量

如果你的数据是非凸结构、簇形态多样或存在大量噪声，可考虑：

• 更换链接或度量
• 使用图方法（谱聚类）或密度方法
• 采用度量学习或半监督策略
• 使用微簇 + 层次法的两阶段流程

层次聚类的优势在于：提供从粗到细的多尺度结构，便于解释与探索；

它的挑战在于：复杂度与度量选择高度敏感。

将其置于优化的框架下，配合合理的工程策略与指标选择，往往能得到兼顾可解释性与实用性的聚类方案。