Agnes聚类算法原理剖析与实战优化指南

1次阅读

共计 2370 个字符，预计需要花费 6 分钟才能阅读完成。

层次聚类（Hierarchical Clustering）作为无监督学习的重要方法，广泛应用于社交网络分析、生物信息学和推荐系统等领域。与 K -means 需要预设聚类数、DBSCAN 依赖密度参数不同，Agnes（Agglomerative Nesting）通过自底向上的合并策略，天然形成树状结构（Dendrogram），更适合需要多粒度分析的场景。

K-means：
优点：计算复杂度 O(nkt) 较低
缺点：需指定 k 值，对非凸分布敏感
DBSCAN：
优点：自动发现任意形状簇
缺点：参数 ε 和 MinPts 调节困难
Agnes：
优点：可视化树状图，无需预设簇数
缺点：O(n^3) 时间复杂度，内存消耗大

Agnes 通过迭代合并最近邻簇实现聚类，关键差异在于簇间距离定义：

单链（Single Linkage）：
$$d(C_i,C_j)=\min_{a\in C_i,b\in C_j} d(a,b)$$
适合发现长条形簇，但易产生链式效应
全链（Complete Linkage）：
$$d(C_i,C_j)=\max_{a\in C_i,b\in C_j} d(a,b)$$
生成紧凑型簇，对噪声敏感
均链（Average Linkage）：
$$d(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum_{a\in C_i}\sum_{b\in C_j} d(a,b)$$
平衡前两种方法的特性

传统实现需要：

计算 O(n^2) 距离矩阵
执行 n - 1 次合并，每次需 O(n^2) 查找最近簇
每次合并后更新 O(n) 距离值

总复杂度达到 O(n^3)，万级数据量时已显吃力。

import numpy as np
from scipy.spatial.distance import pdist, squareform

# 生成模拟数据（1000 个 3 维样本）data = np.random.rand(1000, 3) 

# 向量化计算欧式距离矩阵
def fast_distance_matrix(X):
    return squareform(pdist(X, 'euclidean'))

dist_matrix = fast_distance_matrix(data)

import heapq

class ClusterPriorityQueue:
    def __init__(self, dist_matrix):
        self.n = dist_matrix.shape[0]
        self.queue = []

        # 初始化优先队列（避免重复存储）for i in range(self.n):
            for j in range(i+1, self.n):
                heapq.heappush(self.queue, (dist_matrix[i,j], i, j))

    def pop_nearest(self):
        return heapq.heappop(self.queue)

    def update_distances(self, merged_idx, new_distances):
        # 更新与合并簇相关的距离（剪枝策略见后续章节）for i in range(self.n):
            if i != merged_idx:
                heapq.heappush(self.queue, (new_distances[i], merged_idx, i))

import numpy as np
import os
from tempfile import mkdtemp

# 创建内存映射文件
tmp_dir = mkdtemp()
filename = os.path.join(tmp_dir, 'dist_matrix.dat')
shape = (100000, 100000)  # 10 万样本的矩阵

# 仅实际需要时加载数据块
dist_mmap = np.memmap(filename, dtype='float32', mode='w+', shape=shape)

数据规模	原始版本 (s)	优化版本 (s)	加速比
1,000	12.4	3.2	3.9x
5,000	1,024.7	187.5	5.5x
10,000	内存溢出	892.3	–

通过设置距离阈值提前终止合并：

def agnes_with_pruning(dist_matrix, max_dist):
    clusters = [[i] for i in range(len(dist_matrix))]
    pq = ClusterPriorityQueue(dist_matrix)

    while len(clusters) > 1:
        dist, i, j = pq.pop_nearest()
        if dist > max_dist:  # 剪枝条件
            break

        # 执行合并操作（略）

实验表明，当剪枝阈值设为平均距离的 1.5 倍时，可减少 30% 计算量且保持 90% 以上的聚类准确率。