← 返回Book 7

第23章：层次聚类

自底向上聚合与自顶向下分裂

基于距离或亲和度逐层构建树状图

章节概述

层次聚类：一种构建树结构（树状图）的聚类算法，显示不同尺度下的嵌套分组。与K-Means或GMM不同，它不需要事先指定K。

两种方法：聚合式（自底向上）：从单个点开始，合并最近的簇。分裂式（自顶向下）：从一个簇开始，递归分割。

关键挑战：定义簇之间的"距离"（连接方法）：单连接、完全连接、平均连接、质心连接或Ward方法。不同的连接方法产生不同的层次结构。

23.1 层次聚类介绍

🌳 构建层次结构

层次聚类创建树状结构，同时显示所有尺度上的关系。 树状图可视化揭示细粒度结构（许多小簇）和粗粒度结构（少数大簇）。

聚合式（自底向上）：
  • • 开始：每个点都是自己的簇
  • • 迭代：合并两个最近的簇
  • • 结束：所有点在一个簇中
  • • 结果：从叶到根的树状图
分裂式（自顶向下）：
  • • 开始：所有点在一个簇中
  • • 迭代：将簇分成两个
  • • 结束：每个点都是自己的簇
  • • 结果：从根到叶的树状图

优点与缺点

✓ 优点
  • • 无需指定K：可在任何层级探索层次结构
  • • 确定性：每次运行结果相同（无随机初始化）
  • • 视觉解释：树状图清晰显示结构
  • • 灵活性：多种距离/连接方法
  • • 嵌套簇：揭示层次关系
✗ 缺点
  • • 计算成本：聚合式为O(n²log n)
  • • 不可扩展：大数据集（>10k点）处理困难
  • • 贪婪合并：无法撤销早期错误决策
  • • 连接敏感性：不同方法结果差异显著
  • • 距离假设：需要有意义的距离度量

23.2 树状图构建：逐步演示

📊 树状图如何构建

树状图逐层构建，从单个数据点开始。 在每一层，我们合并距离最小的两个簇。 树状图中的垂直位置表示合并距离。

5层构建过程：
第0层：12个单独的点（距离=0）
第1层：合并d=1的点对→9个簇
第2层：合并d=√2的点对→6个簇
第3层：合并d=2的簇→5个簇
第4层：合并d=√5的簇→3个簇
第5层：合并d≈3.61的簇→2个簇
🌳

树状图构建：逐步演示

观察层次聚类如何自底向上构建树

层级：0 / 512 个簇
初始：12个单独的点作为簇

Data Points & Clusters

00224466881010abcdefghijklx₁x₂

Dendrogram (Tree)

012345flidgacbhejkDistance

Distance Matrix Heatmap

Pairwise Euclidean Distances
Hover over cells to see distances

🌳 Bottom-Up Agglomerative Clustering:Start with each data point as its own cluster. At each layer, merge the two closest clusters (single linkage: nearest neighbor distance). Continue until all points belong to one cluster. The dendrogram visualizes this hierarchical structure, where vertical position indicates merge distance.

读取树状图

横轴：
数据点标签或索引。顺序由层次结构决定，将相似点分组在一起。
纵轴：
簇合并时的连接距离。越高意味着越不相似的簇在合并。
切割树：
在高度h处的水平切割创建簇。切割线下连接的点属于同一簇。

23.3 连接方法：簇距离定义

📏 核心挑战

虽然计算两个单独点之间的距离很简单， 但我们如何测量包含多个点的两个簇之间的距离？ 不同的连接方法给出不同的答案，导致不同的层次结构。

5种常见连接方法：
单连接：最小成对距离（最近邻）
完全连接：最大成对距离（最远邻）
平均连接：所有成对距离的均值
质心连接：簇质心之间的距离
Ward方法：簇内方差增量（SSE）
📏

Linkage Method Comparison

Different ways to measure distance between clusters

Select Linkage Method:

Linkage Distance: 3.162

Visual Explanation

00224466881010Cluster CⱼCluster Cₖx₁x₂
SINGLE

Single Linkage (Nearest Neighbor)

Distance between two clusters is the minimum distance between any two points from the two clusters.

Formula:
d(Cⱼ, Cₖ) = min dist(x, z) for x∈Cⱼ, z∈Cₖ
✓ Pros
Can handle non-elliptical clusters
✗ Cons
Sensitive to noise and outliers; tends to create unbalanced dendrograms
Visual Key:
🔴 Red line: Nearest neighbor pair (minimum distance)

📏 Choosing Linkage Method:Different linkage methods produce different clustering results.Single linkage can capture elongated clusters but is sensitive to noise.Complete linkage prefers compact clusters.Average linkage balances the two extremes.Ward's method minimizes within-cluster variance (like K-Means) and is the default in sklearn.Centroid linkage is intuitive but may produce non-monotonic dendrograms.

单连接 vs 完全连接

单连接（最近邻）：
可以检测非椭圆形、细长的簇（"链式效应"）。对噪声和异常值敏感。倾向于创建具有长链的不平衡树状图。
完全连接（最远邻）：
偏好紧凑、球形的簇。对异常值的敏感性低于单连接。可能过早分裂大簇。

Ward方法（默认）

Ward连接是sklearn中的默认方法，通常产生最佳结果。 它将合并两个簇的"成本"衡量为总簇内方差（SSE）的增加。

d(Cⱼ, Cₖ) = SSE(Cⱼ∪Cₖ) - [SSE(Cⱼ) + SSE(Cₖ)]

Ward方法在每次合并时最小化总簇内方差的增加， 类似于K-Means的目标。它倾向于创建平衡、紧凑的簇。

23.4 交互式探索

🎛️

Interactive Hierarchical Clustering

Adjust cut height to control number of clusters

3 Clusters
0 (12 clusters)2.5 (3 clusters)5 (1 cluster)
How to use: Drag the cut height slider to see how clusters merge/split. Lower values = more clusters (fine-grained). Higher values = fewer clusters (coarse-grained).

Scatter Plot & Clustering

00224466881010abcdefghijklx₁x₂

Dendrogram with Cut Line

012345flidgacbhejkCutLinkage Distance

Reordered Distance Matrix

flidgacbhejk
Same cluster pairs highlighted
🔪 Cutting the Dendrogram
A horizontal cut through the dendrogram at height h creates clusters. Points connected below the cut line belong to the same cluster. Lower cut = more clusters (fine detail). Higher cut = fewer clusters (coarse structure).
📊 Matrix Reorganization
The dendrogram reorders data points to group similar ones together. The reorganized distance matrix reveals block structure - same-cluster pairs form low-distance blocks (darker blue regions with red borders).

🎛️ Interactive Exploration:Hierarchical clustering doesn't require specifying K beforehand. Instead, you build a complete hierarchy and then choose where to "cut" based on your needs. Try different cut heights: low values preserve fine structure (many small clusters), high values capture only major groups (few large clusters). The dendrogram visually shows the hierarchical relationships at all scales simultaneously.

🎯 选择切割高度
切割高度决定簇的数量。较低的切割创建更多簇（细粒度）， 较高的切割创建较少簇（粗粒度结构）。使用领域知识或肘部法则来选择。
📊 矩阵重排
树状图重新排列数据点，将相似的点放在一起。 重排后的距离矩阵揭示块结构：同簇点对形成深蓝色区域。
🔧 方法选择
不同的连接方法产生不同的层次结构。Ward对一般用途很稳健。 单连接适用于细长簇。完全连接适用于紧凑簇。尝试多种方法！

实际应用

层次聚类因其揭示多尺度结构的能力而在各个领域广泛应用：

🧬 基因组学与系统发育学
基因表达聚类、系统发育树构建、蛋白质家族分类。揭示进化关系。
🛒 市场细分
多粒度客户细分。同时识别广泛群体和利基子细分。
📄 文档聚类
将文档组织为主题和子主题。创建层次主题分类法。用于搜索引擎。
🖼️ 图像分割
从细像素到粗区域的层次分割。用于计算机视觉流程。
🗺️ 地理聚类
在不同尺度上聚类位置：社区→地区→城市→区域。
📊 推荐系统
协同过滤的用户/物品聚类。层次用户偏好和物品类别。

章节总结

关键要点

🌳 核心算法

• 聚合式：从n个簇开始，合并直到1个簇
• 树状图：显示层次结构的树形可视化
• 切割高度：决定簇的数量
• 无需K：同时探索所有尺度

📏 连接方法

• 单连接：min(dist) - 检测链
• 完全连接：max(dist) - 紧凑簇
• 平均连接：mean(dist) - 平衡
• Ward：最小化SSE - 默认选择

🔗 与其他方法的比较

vs K-Means：
无需K。确定性。层次结构。但更慢且可扩展性较差。
vs GMM：
对簇形状无假设。算法更简单。但无概率解释。
vs DBSCAN：
适用于任何距离。层次视图。但需要距离矩阵（O(n²)空间）。
🌳
层次结构
揭示所有尺度的关系
📏
连接方法
5种衡量簇距离的方法
🎯
无需K
在任何层级探索层次结构