层次聚类

聚类算法 - 层次聚类

层次聚类简介

层次聚类（Hierarchical Clustering）是一种无监督学习技术，用于构建一个聚类层次结构。与 K-Means 不同，它不需要预先指定聚类数量。相反，它会创建一个树状结构，称为树状图 (dendrogram)，该图可视化了聚类的合并或分裂过程。

层次聚类主要有两种类型：

凝聚式 (Agglomerative / Bottom-Up): 从每个数据点作为一个单独的簇开始，然后迭代地合并最近的一对簇，直到只剩下一个簇（包含所有数据点）。
分裂式 (Divisive / Top-Down): 从所有数据点都在一个簇中开始，然后递归地分裂簇，直到每个数据点都成为一个单独的簇（不如凝聚式常见）。

本章重点介绍使用更广泛的凝聚式层次聚类。

凝聚式层次聚类过程

凝聚式算法按照以下步骤进行：

初始化: 将每个数据点视为一个独立的簇（N 个数据点对应 N 个簇）。
迭代: 重复以下步骤，直到只剩下一个簇为止：
a. 计算相似度: 计算当前所有簇对之间的距离（或相似度）。这需要定义距离度量 (distance metric)（例如，欧几里得距离、曼哈顿距离）和连接标准 (linkage criterion)。
b. 合并: 将两个最近的簇合并成一个新的簇。
结果: 生成一个表示合并序列的树状图。

连接标准

连接标准定义了如何计算两个簇（而不仅仅是数据点）之间的距离：

Ward (常用默认): 最小化每个簇内的方差。合并那些导致总簇内平方和增加最小的簇。
Complete (最大连接): 簇之间的距离是第一个簇中的任何点与第二个簇中的任何点之间的最大距离。
Average Linkage: 簇之间的距离是所有点对（一个来自第一个簇，一个来自第二个簇）之间距离的平均值。
Single (最小连接): 簇之间的距离是第一个簇中的任何点与第二个簇中的任何点之间的最小距离。可能对异常值敏感，并导致“链状”结构。

连接标准的选取显著影响最终聚类结果的形状和构成。

树状图的作用

树状图是层次聚类的主要输出。它可视化了簇如何合并（凝聚式）或分裂（分裂式）。

Y 轴通常表示簇合并时的距离（或相异度）。
X 轴表示单个数据点或簇。
水平线连接合并的簇。水平线的高度表示簇在合并时的距离。
较长的垂直线表明在该点合并的簇更不相似（相距更远）。

通过在特定距离阈值处水平“切割”树状图，你可以获得特定数量的簇。一条与 K 条垂直线相交的切割线将产生 K 个簇。

示例：可视化树状图

让我们创建一个简单数据集，并使用 Scipy 和 Matplotlib 可视化其树状图。

import matplotlib.pyplot as plt
import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.preprocessing import StandardScaler

# 样本数据 (两个不同的组)
X = np.array([
    [7, 8], [10, 8], [9, 11], [12, 9], # 大约是 Group 1
    [25, 30], [28, 35], [32, 31], [30, 28] # 大约是 Group 2
])

# 可选但推荐：缩放数据
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# --- 使用 Ward 连接生成连接矩阵 ---
# 'ward' 最小化待合并簇的方差。
linked = linkage(X_scaled, method='ward')

# --- 绘制树状图 ---
plt.figure(figsize=(10, 7))
dendrogram(linked,
            orientation='top', # 树形结构向上生长
            # labels=range(1, len(X) + 1), # 可选：叶子节点标注 1 到 N
            distance_sort='descending', # 按距离降序排列链接
            show_leaf_counts=True) # 显示叶子节点中的数据点数量 (如果节点代表 > 1个点)

plt.title('Hierarchical Clustering Dendrogram (Ward Linkage)')
plt.xlabel('数据点 (或簇索引)')
plt.ylabel('距离 (Ward)')
plt.grid(axis='y', linestyle='--')

# 可选：添加一条水平线表示切割以获得 k=2 个簇
# 找到最大的距离跳跃来建议切割，或根据期望的 k 值选择
# 这通常通过目视检查或特定标准来完成
# plt.axhline(y=..., color='r', linestyle='--')

plt.show()

这段代码生成了样本数据的树状图。你会观察到两个主要分支在相对较大的距离处合并，表明存在两个不同的簇。（图表显示了一个树形图，底部叶子代表单个数据点，分支向上合并。合并高度表示距离/相异度）。

使用 Scikit-learn 获取簇标签

虽然树状图提供了很好的洞察，但我们通常需要每个数据点的实际簇分配。Scikit-learn 的 AgglomerativeClustering 类允许我们执行层次聚类并直接获取标签，通常通过指定所需的聚类数量 (n_clusters)。

示例：应用凝聚式聚类

import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler

# 样本数据 (与之前相同)
X = np.array([
    [7, 8], [10, 8], [9, 11], [12, 9],
    [25, 30], [28, 35], [32, 31], [30, 28]
])

# 缩放数据
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# --- 应用凝聚式聚类 ---
# 指定聚类数量 (例如，根据树状图检查选择 k=2)
# 使用 'ward' 连接，通常是一个不错的默认选择
# 'affinity' 是距离度量 ('euclidean' 是 Ward 的默认值)
cluster_model = AgglomerativeClustering(n_clusters=2, linkage='ward', affinity='euclidean')

# 拟合模型并预测簇标签
# 注意：fit_predict 很方便，但它结合了拟合和预测步骤
labels = cluster_model.fit_predict(X_scaled)

print("Cluster Labels:", labels)

# --- 可视化聚类结果 ---
plt.figure(figsize=(8, 6))
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='viridis', s=50)
plt.title('Agglomerative Clustering Results (k=2)')
plt.xlabel('Feature 1 (Scaled)')
plt.ylabel('Feature 2 (Scaled)')
plt.grid(True)
plt.show()

输出 (示例)

Cluster Labels: [1 1 1 1 0 0 0 0]

输出显示了每个数据点被分配的簇标签（0 或 1）。图表直观地证实了算法找到的两个不同组，并根据分配的簇进行了着色。（图表将显示 8 个点，前 4 个点与后 4 个点的颜色不同）。

示例 2：聚类真实数据 (Iris 数据集)

让我们将层次聚类应用于 Iris 数据集（仅使用花瓣长度和宽度进行二维可视化）。

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

# 加载 Iris 数据集
iris = load_iris()
X = iris.data[:, 2:4] # 仅使用花瓣长度 (索引 2) 和花瓣宽度 (索引 3)
y_true = iris.target # 真实标签用于比较 (不用于聚类)
feature_names = iris.feature_names[2:4]

# 缩放特征
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# --- 树状图 ---
linked = linkage(X_scaled, method='ward')
plt.figure(figsize=(12, 7))
dendrogram(linked,
            orientation='top',
            distance_sort='descending',
            show_leaf_counts=True)
plt.title('Iris Dataset Dendrogram (Petal Features, Ward Linkage)')
plt.xlabel('样本索引')
plt.ylabel('距离')
plt.show()

# --- 凝聚式聚类 (k=3，根据领域知识或树状图判断) ---
cluster_model = AgglomerativeClustering(n_clusters=3, linkage='ward', affinity='euclidean')
labels = cluster_model.fit_predict(X_scaled)

# --- 可视化聚类结果 ---
plt.figure(figsize=(8, 6))
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='viridis', s=50)
plt.title('Hierarchical Clustering on Iris Petals (k=3)')
plt.xlabel(f'{feature_names[0]} (Scaled)')
plt.ylabel(f'{feature_names[1]} (Scaled)')
plt.grid(True)
plt.show()

# 可选：与真实标签比较 (如果可用)
from sklearn.metrics import adjusted_rand_score
ari = adjusted_rand_score(y_true, labels)
print(f"\nAdjusted Rand Index (vs true labels): {ari:.4f}")

这个示例首先展示了 Iris 数据集花瓣特征的树状图，它通常暗示存在三个主要组。然后，应用 AgglomerativeClustering 并设置 n_clusters=3，可视化了结果聚类。调整兰德指数 (Adjusted Rand Index, ARI) 提供了一个量化指标，衡量聚类结果与真实物种标签的匹配程度（这需要真实标签，但在聚类过程中不使用真实标签）。

优点和缺点

优点

无需指定 K: 无需预先指定聚类数量 K；树状图提供了相关洞察。
直观可视化: 树状图清晰地展示了合并过程和簇之间的关系。
层次结构: 捕捉数据中可能存在的层次结构。
灵活性高: 可使用各种距离度量和连接标准。

缺点

计算成本高: 通常时间复杂度为 O(N³)，内存复杂度为 O(N²)，对于超大型数据集（N=数据点数量）来说速度较慢。Scikit-learn 的实现进行了一些优化，但仍可能要求较高。
无修正机制: 合并是最终的；一旦合并，数据点就不能被重新分配（与 K-Means 不同）。
对连接/度量敏感: 结果会因选择的距离度量和连接标准而显著不同。
树状图解释: 决定在哪里“切割”树状图以获得最佳聚类数量可能是主观的。

应用场景

层次聚类在各个领域都有用武之地：

生物学: 创建物种分类（系统发育树）。
社交网络分析: 识别社区或层次结构。
市场研究: 基于相似性层次对客户进行细分。
图像分析: 对相似图像区域进行分组。