AGNES聚类算法：从原理到实战的高维数据聚类指南

1次阅读

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

在数据分析和机器学习领域，聚类是一种常见的无监督学习技术。面对高维数据时，传统聚类算法如 K -Means 往往表现不佳。本文将深入探讨 AGNES（Agglomerative Nesting）层次凝聚聚类算法，它在处理非球形分布数据时展现出独特优势。

K-Means 的不足
需要预先指定簇数量 K
对初始中心点选择敏感
只能发现球形簇
对噪声和离群点敏感
高维数据挑战
维度灾难导致距离度量失效
数据稀疏性问题
可视化困难

特性	AGNES	K-Means	DBSCAN
时间复杂度	O(n^3)	O(nki)	O(n log n)
需要预设 K 值	否	是	否
簇形状适应	任意形状	球形簇	任意形状
噪声处理	中等	差	好
参数敏感性	距离度量敏感	初始中心敏感	ε 和 MinPts 敏感

初始化 ：将每个样本视为一个簇
计算距离矩阵 ：存储所有簇间距离
合并最近簇 ：根据链接准则合并最接近的两个簇
更新矩阵 ：重新计算新簇与其他簇的距离
重复：直到所有样本合并为一个簇

单链接 (Single Linkage): 取两个簇中最近样本对的距离
$$d(C_i,C_j) = \min_{x\in C_i, y\in C_j} d(x,y)$$
全链接 (Complete Linkage): 取两个簇中最远样本对的距离
$$d(C_i,C_j) = \max_{x\in C_i, y\in C_j} d(x,y)$$
平均链接 (Average Linkage): 取两个簇所有样本对距离的平均值
$$d(C_i,C_j) = \frac{1}{|C_i||C_j|}\sum_{x\in C_i}\sum_{y\in C_j} d(x,y)$$

def AGNES(data, linkage='average'):
    # 初始化: 每个样本是一个簇
    clusters = [{i} for i in range(len(data))]

    # 计算初始距离矩阵
    dist_matrix = compute_pairwise_distance(data)

    # 记录合并历史
    merge_history = []

    while len(clusters) > 1:
        # 找到距离最近的两个簇
        i, j = find_closest_clusters(dist_matrix)

        # 记录合并操作
        merge_history.append([i, j, dist_matrix[i][j], len(clusters[i])+len(clusters[j])])

        # 合并簇
        new_cluster = clusters[i] | clusters[j]

        # 更新簇列表
        clusters = [c for idx, c in enumerate(clusters) if idx not in (i,j)] + [new_cluster]

        # 更新距离矩阵
        dist_matrix = update_distance_matrix(dist_matrix, i, j, linkage)

    return merge_history

from sklearn.datasets import load_iris
from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt

# 加载数据
iris = load_iris()
X = iris.data

# 计算链接矩阵 - 尝试不同链接方法
# linkage_methods = ['single', 'complete', 'average', 'ward']
Z = linkage(X, method='average', metric='euclidean')

# 绘制树状图
plt.figure(figsize=(10, 5))
plt.title('Iris Dataset Dendrogram')
dendrogram(Z, truncate_mode='lastp', p=12, show_leaf_counts=True)
plt.xlabel('Sample Index or Cluster Size')
plt.ylabel('Distance')
plt.show()

method: 链接方法（’single’/’complete’/’average’/’ward’）
metric: 距离度量（’euclidean’/’cosine’/’cityblock’ 等）
optimal_ordering: 是否优化叶子节点排序

AGNES 的 O(n^3) 复杂度主要来自：

初始距离矩阵计算：O(n^2)
每次迭代中查找最近簇对：O(n^2)
共需 n - 1 次迭代

对低维数据（d < 20），可使用 KD-tree 加速最近邻搜索：

from sklearn.neighbors import KDTree

def compute_distance_matrix_kd(X):
    tree = KDTree(X)
    dist_mat = tree.query(X, k=len(X), return_distance=True)[0]
    return dist_mat