层次聚类（Hierarchical Clustering）无需预先指定簇数量 $K$，通过自底向上（凝聚式 AGNES）或自顶向下（分裂式 DIANA）的策略构建数据的层次化嵌套结构，输出一棵完整的聚类树（Dendrogram）。本文用Java实现AGNES算法，并支持单链接、全链接、平均链接和Ward四种距离度量。
算法原理
AGNES凝聚式聚类
- 初始化：每个样本自成一簇，共 $N$ 个簇
- 迭代合并：计算所有簇对之间的距离，合并距离最近的两个簇
- 终止：当簇数量达到预设值 $K$ 或仅剩一个簇时停止
簇间距离度量
| 方法 | 公式 | 特点 |
|---|---|---|
| 单链接 (Single) | $d(C_i, C_j) = \min_{x \in C_i, y \in C_j} d(x, y)$ | 易产生链式效应，对噪声敏感 |
| 全链接 (Complete) | $d(C_i, C_j) = \max_{x \in C_i, y \in C_j} d(x, y)$ | 倾向于生成紧凑球形簇 |
| 平均链接 (Average) | $d(C_i, C_j) = \frac{1}{ | C_i |
| Ward法 | 合并后簇内方差增量最小 | 倾向于等大小簇，效果稳健 |
Java实现
import java.util.*;
/**
* AGNES凝聚式层次聚类
* 支持单链接、全链接、平均链接和Ward法
*/
public class HierarchicalClustering {
public enum Linkage { SINGLE, COMPLETE, AVERAGE, WARD }
static class Cluster {
int id;
List<double[]> points; // 簇内所有点
double[] centroid; // 质心（Ward法需要）
List<Cluster> children; // 子簇（用于构建树）
double mergeDistance; // 合并时的距离
Cluster(int id, double[] point) {
this.id = id;
this.points = new ArrayList<>();
this.points.add(point.clone());
this.centroid = point.clone();
this.children = new ArrayList<>();
this.mergeDistance = 0;
}
Cluster(int id, Cluster a, Cluster b, double dist) {
this.id = id;
this.points = new ArrayList<>(a.points);
this.points.addAll(b.points);
this.children = new ArrayList<>();
this.children.add(a);
this.children.add(b);
this.mergeDistance = dist;
// 重新计算质心
int dim = a.centroid.length;
this.centroid = new double[dim];
for (double[] p : this.points) {
for (int i = 0; i < dim; i++) centroid[i] += p[i];
}
for (int i = 0; i < dim; i++) centroid[i] /= this.points.size();
}
}
private static double euclidean(double[] a, double[] b) {
double sum = 0;
for (int i = 0; i < a.length; i++) {
double d = a[i] - b[i];
sum += d * d;
}
return Math.sqrt(sum);
}
/**
* 计算两个簇之间的距离
*/
private static double clusterDistance(Cluster a, Cluster b, Linkage linkage) {
switch (linkage) {
case SINGLE:
double min = Double.MAX_VALUE;
for (double[] pa : a.points)
for (double[] pb : b.points)
min = Math.min(min, euclidean(pa, pb));
return min;
case COMPLETE:
double max = 0;
for (double[] pa : a.points)
for (double[] pb : b.points)
max = Math.max(max, euclidean(pa, pb));
return max;
case AVERAGE:
double sum = 0;
for (double[] pa : a.points)
for (double[] pb : b.points)
sum += euclidean(pa, pb);
return sum / (a.points.size() * b.points.size());
case WARD:
// Ward距离 = 合并后簇内平方和增量
double[] mergedCentroid = new double[a.centroid.length];
int total = a.points.size() + b.points.size();
for (int i = 0; i < mergedCentroid.length; i++) {
mergedCentroid[i] = (a.centroid[i] * a.points.size() + b.centroid[i] * b.points.size()) / total;
}
double wardDist = 0;
for (double[] p : a.points) {
for (int i = 0; i < p.length; i++) {
double d = p[i] - mergedCentroid[i];
wardDist += d * d;
}
}
for (double[] p : b.points) {
for (int i = 0; i < p.length; i++) {
double d = p[i] - mergedCentroid[i];
wardDist += d * d;
}
}
return wardDist;
default:
throw new IllegalArgumentException("Unknown linkage");
}
}
/**
* AGNES聚类主算法
* @param data 数据集
* @param k 目标簇数
* @param linkage 链接方式
* @return 最终簇列表
*/
public static List<Cluster> cluster(double[][] data, int k, Linkage linkage) {
List<Cluster> clusters = new ArrayList<>();
for (int i = 0; i < data.length; i++) {
clusters.add(new Cluster(i, data[i]));
}
int nextId = data.length;
while (clusters.size() > k) {
// 找到距离最近的两个簇
double minDist = Double.MAX_VALUE;
int mergeA = -1, mergeB = -1;
for (int i = 0; i < clusters.size(); i++) {
for (int j = i + 1; j < clusters.size(); j++) {
double dist = clusterDistance(clusters.get(i), clusters.get(j), linkage);
if (dist < minDist) {
minDist = dist;
mergeA = i;
mergeB = j;
}
}
}
// 合并
Cluster merged = new Cluster(nextId++,
clusters.get(mergeA), clusters.get(mergeB), minDist);
// 移除被合并的簇（先移除索引较大的）
clusters.remove(Math.max(mergeA, mergeB));
clusters.remove(Math.min(mergeA, mergeB));
clusters.add(merged);
}
return clusters;
}
/** 打印树状图结构（缩进表示层次） */
public static void printDendrogram(Cluster node, String indent) {
if (node.children.isEmpty()) {
System.out.printf("%sLeaf #%d (%.2f, %.2f)%n",
indent, node.id, node.centroid[0], node.centroid[1]);
} else {
System.out.printf("%sCluster #%d [mergeDist=%.3f, n=%d]%n",
indent, node.id, node.mergeDistance, node.points.size());
for (Cluster child : node.children) {
printDendrogram(child, indent + " ");
}
}
}
public static void main(String[] args) {
// 构造两组明显分离的二维数据
double[][] data = new double[12][];
// 簇1: 围绕 (2, 2)
data[0] = new double[]{1.8, 2.1}; data[1] = new double[]{2.2, 1.9};
data[2] = new double[]{2.0, 2.3}; data[3] = new double[]{1.9, 1.8};
data[4] = new double[]{2.1, 2.2}; data[5] = new double[]{2.3, 2.0};
// 簇2: 围绕 (7, 7)
data[6] = new double[]{6.9, 7.1}; data[7] = new double[]{7.2, 6.8};
data[8] = new double[]{7.0, 7.3}; data[9] = new double[]{6.8, 7.0};
data[10] = new double[]{7.1, 7.2}; data[11] = new double[]{7.3, 6.9};
System.out.println("=== 全链接 (Complete Linkage) ===");
List<Cluster> result = cluster(data, 2, Linkage.COMPLETE);
for (Cluster c : result) {
System.out.printf("簇 #%d: %d 个点，质心 (%.2f, %.2f)%n",
c.id, c.points.size(), c.centroid[0], c.centroid[1]);
}
System.out.println("\n=== Ward法 ===");
result = cluster(data, 2, Linkage.WARD);
for (Cluster c : result) {
System.out.printf("簇 #%d: %d 个点，质心 (%.2f, %.2f)%n",
c.id, c.points.size(), c.centroid[0], c.centroid[1]);
}
}
}
复杂度与优化
| 方面 | 朴素实现 | 优化策略 |
|---|---|---|
| 时间复杂度 | $O(N^3 \cdot d)$ | Lance-Williams递推公式 $O(N^2)$ |
| 空间复杂度 | $O(N^2)$ | 距离矩阵缓存 |
| 距离计算 | 每次重新计算 | 优先队列维护最近邻 |
对于 $N > 1000$ 的数据集，建议使用BIRCH或Mini-Batch K-Means等可扩展算法作为预处理，再对代表点执行层次聚类。
树状图（Dendrogram）解读
聚类树的高度表示簇间距离：
– 切割线位置决定簇数量，切割位置越高，簇越少
– 长垂直分支表示两个子簇差异显著
– 通过轮廓系数（Silhouette Score）或间隙统计（Gap Statistic）可自动确定最优切割高度
层次聚类的最大优势在于不预设簇数，让数据自身的结构决定聚类粒度，为探索性数据分析提供了强大的可视化工具。
