系统聚类法（层次聚类）

方法	\( \alpha_i \)	\( \alpha_j \)	\( \beta \)	\( \gamma \)
最短距离	\( 1/2 \)	\( 1/2 \)	\( 0 \)	\( -1/2 \)
最长距离	\( 1/2 \)	\( 1/2 \)	\( 0 \)	\( 1/2 \)
类平均	\( n_i/(n_i+n_j) \)	\( n_j/(n_i+n_j) \)	\( 0 \)	\( 0 \)
Ward	\( (n_l+n_i)/(n_l+n_k) \)	\( (n_l+n_j)/(n_l+n_k) \)	\( -n_l/(n_l+n_k) \)	\( 0 \)

树状图（Dendrogram）

树状图是层次聚类结果的标准可视化方式，它完整记录了聚类的合并过程和合并距离。

树状图的结构与解读

树状图由叶节点（样本）、内部节点（合并事件）和连线高度（合并距离）构成。解读要点：

确定聚类数：选择截断高度，切割线穿过的分支数即为聚类数
评估聚类质量：较大的高度差表示类间差异显著，是良好的切割位置
识别离群点：在较低高度才被合并的孤立分支可能是离群点

截断准则

肘部法则：观察合并距离的跳跃点
不一致系数：比较某次合并距离与其子树平均合并距离的差异
Calinski-Harabasz 指数：类间方差与类内方差之比

实际案例分析

通过一个完整的数值案例，展示系统聚类法的详细计算过程。

问题设定

设有 5 个样本，每个样本有 2 个特征：

样本	\( x_1 \)	\( x_2 \)
A	1	1
B	1.5	1.5
C	5	5
D	3	4
E	4	4

采用欧氏距离和最短距离法（Single Linkage）进行聚类。

计算初始距离矩阵

\[ d(A,B) = \sqrt{0.5} \approx 0.707, \quad d(A,C) = \sqrt{32} \approx 5.657, \quad d(A,D) = \sqrt{13} \approx 3.606 \]

\[ d(A,E) = \sqrt{18} \approx 4.243, \quad d(B,C) = \sqrt{24.5} \approx 4.950, \quad d(B,D) = \sqrt{8.5} \approx 2.915 \]

\[ d(B,E) = \sqrt{12.5} \approx 3.536, \quad d(C,D) = \sqrt{5} \approx 2.236, \quad d(C,E) = \sqrt{2} \approx 1.414 \]

\[ d(D,E) = \sqrt{1} = 1.000 \]

初始距离矩阵：

	A	B	C	D	E
A	0	0.707	5.657	3.606	4.243
B	0.707	0	4.950	2.915	3.536
C	5.657	4.950	0	2.236	1.414
D	3.606	2.915	2.236	0	1.000
E	4.243	3.536	1.414	1.000	0

合并步骤	合并的类	合并距离
1	A, B	0.707
2	D, E	1.000
3	C, \({D,E}\)	1.414
4	\({A,B}\), \({C,D,E}\)	2.915

若选择 \( k=2 \)，在距离 1.414 与 2.915 之间截断，得到：\( {A, B} \) 和 \( {C, D, E} \)。

Python 代码实现

使用 SciPy 和 scikit-learn 两个库分别实现层次聚类，并绘制树状图。

使用 SciPy 实现

import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt

# 定义样本数据
data = np.array([
    [1, 1],       # A
    [1.5, 1.5],   # B
    [5, 5],       # C
    [3, 4],       # D
    [4, 4],       # E
])
labels = ['A', 'B', 'C', 'D', 'E']

# 计算压缩距离矩阵
dist_matrix = pdist(data, metric='euclidean')

# 不同链接准则的树状图比较
methods = ['single', 'complete', 'average', 'ward']
fig, axes = plt.subplots(2, 2, figsize=(14, 10))

for ax, method in zip(axes.ravel(), methods):
    Z = linkage(dist_matrix, method=method)
    dendrogram(Z, labels=labels, ax=ax)
    ax.set_title(f'链接准则: {method}')
    ax.set_xlabel('样本')
    ax.set_ylabel('距离')

plt.tight_layout()
plt.savefig('dendrogram_comparison.png', dpi=150, bbox_inches='tight')
plt.show()

# Ward 法聚类并提取结果
Z_ward = linkage(dist_matrix, method='ward')
print("聚类合并矩阵 (Ward法):")
print("格式: [类1索引, 类2索引, 合并距离, 样本数]")
print(Z_ward)

# 按聚类数提取标签
k = 2
cluster_labels = fcluster(Z_ward, t=k, criterion='maxclust')
print(f"\n聚为 {k} 类的结果:")
for label, cluster in zip(labels, cluster_labels):
    print(f"  样本 {label} -> 类 {cluster}")

# 按距离阈值提取标签
threshold = 3.0
cluster_labels_t = fcluster(Z_ward, t=threshold, criterion='distance')
print(f"\n距离阈值 {threshold} 的聚类结果:")
for label, cluster in zip(labels, cluster_labels_t):
    print(f"  样本 {label} -> 类 {cluster}")

使用 scikit-learn 实现

import numpy as np
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score, calinski_harabasz_score
import matplotlib.pyplot as plt

# 生成模拟数据
np.random.seed(42)
X, y_true = make_blobs(n_samples=150, centers=3,
                       cluster_std=0.8, random_state=42)

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

# 层次聚类
model = AgglomerativeClustering(
    n_clusters=3, metric='euclidean', linkage='ward'
)
cluster_labels = model.fit_predict(X_scaled)

print("各类样本数:", np.bincount(cluster_labels))

# 可视化
plt.figure(figsize=(10, 6))
scatter = plt.scatter(X_scaled[:, 0], X_scaled[:, 1],
                      c=cluster_labels, cmap='viridis',
                      edgecolors='k', linewidth=0.5, alpha=0.7)
plt.colorbar(scatter, label='类别')
plt.title('层次聚类结果 (Ward法, k=3)')
plt.xlabel('特征 1（标准化）')
plt.ylabel('特征 2（标准化）')
plt.savefig('hierarchical_clustering_result.png', dpi=150, bbox_inches='tight')
plt.show()

# 选择最佳聚类数
scores_silhouette = []
scores_ch = []
k_range = range(2, 8)

for k in k_range:
    model = AgglomerativeClustering(n_clusters=k, linkage='ward')
    labels = model.fit_predict(X_scaled)
    scores_silhouette.append(silhouette_score(X_scaled, labels))
    scores_ch.append(calinski_harabasz_score(X_scaled, labels))

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5))
ax1.plot(k_range, scores_silhouette, 'bo-')
ax1.set_xlabel('聚类数 k')
ax1.set_ylabel('轮廓系数')
ax1.set_title('轮廓系数随聚类数变化')

ax2.plot(k_range, scores_ch, 'rs-')
ax2.set_xlabel('聚类数 k')
ax2.set_ylabel('CH 指数')
ax2.set_title('Calinski-Harabasz 指数随聚类数变化')

plt.tight_layout()
plt.savefig('cluster_evaluation.png', dpi=150, bbox_inches='tight')
plt.show()

结合 SciPy 树状图与真实数据集

import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score
import matplotlib.pyplot as plt

# 鸢尾花数据集
iris = load_iris()
X = iris.data
y = iris.target

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# 树状图（截断显示）
Z = linkage(X_scaled, method='ward')

plt.figure(figsize=(14, 7))
dendrogram(
    Z,
    truncate_mode='lastp', p=30,
    leaf_rotation=90, leaf_font_size=9,
    show_contracted=True,
)
plt.title('鸢尾花数据集层次聚类树状图 (Ward法)')
plt.xlabel('样本索引或（聚合的样本数）')
plt.ylabel('合并距离')
plt.axhline(y=7.5, color='r', linestyle='--', label='截断线 (k=3)')
plt.legend()
plt.tight_layout()
plt.savefig('iris_dendrogram.png', dpi=150, bbox_inches='tight')
plt.show()

# 聚类评估
model = AgglomerativeClustering(n_clusters=3, linkage='ward')
pred_labels = model.fit_predict(X_scaled)

ari = adjusted_rand_score(y, pred_labels)
nmi = normalized_mutual_info_score(y, pred_labels)
print(f"调整兰德指数 (ARI): {ari:.4f}")
print(f"标准化互信息 (NMI): {nmi:.4f}")

自定义距离矩阵的层次聚类

import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage
from scipy.spatial.distance import squareform
import matplotlib.pyplot as plt

# 6个城市之间的地理距离 (km)
city_names = ['北京', '上海', '广州', '成都', '武汉', '西安']
dist_full = np.array([
    [0,    1068, 1888, 1524, 1052, 913],
    [1068, 0,    1213, 1660, 688,  1367],
    [1888, 1213, 0,    1235, 838,  1523],
    [1524, 1660, 1235, 0,    988,  643],
    [1052, 688,  838,  988,  0,    674],
    [913,  1367, 1523, 643,  674,  0],
])

dist_condensed = squareform(dist_full)
Z = linkage(dist_condensed, method='average')

plt.figure(figsize=(10, 6))
dendrogram(Z, labels=city_names, leaf_font_size=12)
plt.title('中国主要城市层次聚类（类平均法）')
plt.xlabel('城市')
plt.ylabel('距离 (km)')
plt.tight_layout()
plt.savefig('city_clustering.png', dpi=150, bbox_inches='tight')
plt.show()

# 输出合并过程
print("合并过程:")
n = len(city_names)
current_labels = list(city_names)
for i, row in enumerate(Z):
    c1, c2, dist, count = row
    c1, c2 = int(c1), int(c2)
    label1 = current_labels[c1]
    label2 = current_labels[c2]
    new_label = f"({label1}, {label2})"
    current_labels.append(new_label)
    print(f"  步骤 {i+1}: {label1} + {label2}, 距离 = {dist:.1f}")

应用注意事项与局限性

在实际应用中，层次聚类方法有诸多需要注意的问题，了解其局限性有助于合理选择和使用该方法。

数据预处理

标准化：当特征量纲不同时，必须先进行标准化。常用 Z-score 标准化 \( x’ = (x - \mu) / \sigma \) 或 Min-Max 归一化 \( x’ = (x - x_{\min}) / (x_{\max} - x_{\min}) \)
缺失值处理：层次聚类无法直接处理缺失值，需要事先插补或删除
异常值检测：离群点会严重影响聚类结果，建议先进行异常值检测和处理

链接准则的选择建议

Single Linkage：适用于发现不规则形状的簇，但容易产生链式效应
Complete Linkage：适用于寻找紧凑的球形簇，对噪声敏感
Average Linkage：较为稳健的折中方案，适用于大多数场景
Ward：假设簇为球形且大小相近时效果最佳，是实际中最常用的方法

计算复杂度与可扩展性

层次聚类的主要局限在于计算复杂度：

时间复杂度：\( O(n^2 \log n) \) 至 \( O(n^3) \)
空间复杂度：\( O(n^2) \)（需存储完整距离矩阵）

当样本量 \( n \) 超过 10000 时，层次聚类可能不可行。应对策略：

先用 K-means 进行预聚类，再对聚类中心进行层次聚类
使用 BIRCH 等增量式层次聚类方法
对大数据集进行随机采样后聚类

不可逆性

凝聚式层次聚类的合并操作不可逆——一旦两个类被合并，后续步骤无法将其拆开。早期的错误合并会传播到后续步骤，不保证找到全局最优解。

聚类数的确定

常用方法：

视觉检查树状图：寻找合并距离的明显“跳跃“
轮廓系数：\( s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))} \)，其中 \( a(i) \) 为样本到同类其他样本的平均距离，\( b(i) \) 为样本到最近邻类的平均距离
Gap Statistic：比较实际数据与均匀分布数据的类内离差
肘部法则：观察合并距离曲线的拐点

与其他聚类方法的比较

方法	是否需指定 k	时间复杂度	簇形状假设	可扩展性
层次聚类	否（后切割）	\( O(n^2 \log n) \)	取决于链接准则	差
K-means	是	\( O(nkt) \)	球形	好
DBSCAN	否	\( O(n \log n) \)	任意形状	中等
高斯混合	是	\( O(nk^2p) \)	椭球形	中等

适用场景与实践建议

层次聚类特别适合以下场景：

样本量较小（\( n < 5000 \)）
需要探索不同层次的聚类结构
不确定最佳聚类数，希望通过树状图辅助决策
数据具有自然的层次结构（如生物分类、组织架构）

实践建议：

优先尝试 Ward 法，它在多数情况下表现良好
通过 Bootstrap 重采样检验聚类结果的稳健性
结合多种内部评价指标综合判断最佳聚类数
对于高维数据，先进行降维（PCA）再聚类

小结

系统聚类法是一种经典且直观的聚类方法，通过逐步合并或分裂构建层次化的聚类结构。其优势在于无需预设聚类数、结果可通过树状图完整呈现、适合探索性分析。主要局限为计算复杂度高、合并不可逆、对噪声和离群点敏感。在数学建模实践中，建议将层次聚类与其他方法结合使用，取长补短，以获得更可靠的聚类结果。

数学建模指南

系统聚类法（层次聚类）

基本原理

核心思想

距离度量

凝聚式与分裂式

凝聚式层次聚类（Agglomerative）

分裂式层次聚类（Divisive）

链接准则（Linkage Criteria）

最短距离法（Single Linkage）

最长距离法（Complete Linkage）

类平均法（Average Linkage）

Ward 法（Ward’s Method）

Lance-Williams 递推公式