从零解析agnes聚类算法原理：新手入门指南与实战代码

1次阅读

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

层次聚类（Hierarchical Clustering）是一种常用的无监督学习算法，它将数据集中的样本组织成一个层次结构。AGNES（Agglomerative Nesting）是层次聚类中自底向上（bottom-up）的一种方法，特别适合处理中小规模数据集。与 K -means 等划分式聚类不同，AGNES 不需要预先指定聚类数量，而是通过逐步合并最相似的簇来构建树状图（dendrogram），让用户可以直观地根据需求选择切割层级。

AGNES 的适用场景包括：

生物信息学中的基因表达数据分析
社交网络中的社区发现
文档主题聚类
任何需要展示数据层次关系的场景

AGNES 算法的核心思想是：初始时每个样本自成一簇，然后递归地合并最相似的两个簇，直到所有样本合并为一个大簇。具体步骤如下：

初始化距离矩阵 ：计算所有样本点两两之间的距离，形成一个 n×n 的距离矩阵，其中 n 是样本数量。
寻找最小距离 ：在当前距离矩阵中找到距离最小的两个簇（初始时每个簇就是一个样本点）。
合并簇 ：将这两个簇合并为一个新簇。
更新距离矩阵 ：根据选定的连接标准（linkage criterion）重新计算新簇与其他簇之间的距离。
重复过程 ：重复步骤 2 -4，直到所有样本合并为一个簇。

常见的连接标准有三种：

单连接（Single Linkage）：两个簇之间的距离定义为它们最近的两个样本点之间的距离
全连接（Complete Linkage）：两个簇之间的距离定义为它们最远的两个样本点之间的距离
平均连接（Average Linkage）：两个簇之间的距离定义为所有样本点对之间距离的平均值
Ward 方法（Ward’s Method）：合并后使得所有簇内方差增加最小的两个簇

下面我们使用 Python 和 numpy 实现一个基本的 AGNES 算法：

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

class AGNES:
    def __init__(self, n_clusters=2, linkage='average'):
        self.n_clusters = n_clusters
        self.linkage = linkage

    def fit(self, X):
        n_samples = X.shape[0]

        # 初始化：每个样本是一个簇
        clusters = [[i] for i in range(n_samples)]

        # 计算初始距离矩阵
        distances = squareform(pdist(X))

        # 保存合并历史用于绘制树状图
        self.merge_history = []

        while len(clusters) > 1:
            # 找到距离最小的两个簇
            min_dist = np.inf
            for i in range(len(clusters)):
                for j in range(i+1, len(clusters)):
                    # 根据连接标准计算簇间距离
                    if self.linkage == 'single':
                        dist = self._single_linkage(clusters[i], clusters[j], distances)
                    elif self.linkage == 'complete':
                        dist = self._complete_linkage(clusters[i], clusters[j], distances)
                    elif self.linkage == 'average':
                        dist = self._average_linkage(clusters[i], clusters[j], distances)

                    if dist < min_dist:
                        min_dist = dist
                        merge_i, merge_j = i, j

            # 记录合并历史
            self.merge_history.append((clusters[merge_i], clusters[merge_j], min_dist))

            # 合并簇
            new_cluster = clusters[merge_i] + clusters[merge_j]
            clusters.pop(merge_j)
            clusters.pop(merge_i)
            clusters.append(new_cluster)

        # 根据指定的簇数切割树状图
        self.labels_ = self._cut_tree(n_samples)

        return self

    def _single_linkage(self, cluster1, cluster2, distances):
        min_dist = np.inf
        for i in cluster1:
            for j in cluster2:
                if distances[i,j] < min_dist:
                    min_dist = distances[i,j]
        return min_dist

    def _complete_linkage(self, cluster1, cluster2, distances):
        max_dist = -np.inf
        for i in cluster1:
            for j in cluster2:
                if distances[i,j] > max_dist:
                    max_dist = distances[i,j]
        return max_dist

    def _average_linkage(self, cluster1, cluster2, distances):
        total = 0
        count = 0
        for i in cluster1:
            for j in cluster2:
                total += distances[i,j]
                count += 1
        return total / count

    def _cut_tree(self, n_samples):
        # 初始化每个样本为一个簇
        labels = np.arange(n_samples)

        # 按合并顺序分配标签
        # 我们只需要保留前 n_samples - n_clusters 次合并
        for i, (cluster1, cluster2, _) in enumerate(self.merge_history[:n_samples - self.n_clusters]):
            # 为 cluster2 中的所有样本分配 cluster1 中第一个样本的标签
            for idx in cluster2:
                labels[idx] = labels[cluster1[0]]

        # 重新映射标签为连续的整数
        unique_labels = np.unique(labels)
        label_map = {old: new for new, old in enumerate(unique_labels)}
        return np.array([label_map[l] for l in labels])

    def plot_dendrogram(self):
        """绘制树状图"""
        from collections import defaultdict

        # 创建合并历史的数据结构
        merge_history = self.merge_history
        n_samples = len(self.labels_)

        # 初始化每个样本为一个叶子节点
        clusters = [{'id': i, 'size': 1, 'height': 0} for i in range(n_samples)]

        # 记录每个簇的 ID
        cluster_id = n_samples

        # 记录每次合并的信息
        linkage_matrix = []

        for cluster1_idx, cluster2_idx, distance in merge_history:
            # 找到对应的簇对象
            c1 = None
            c2 = None
            for c in clusters:
                if set(cluster1_idx) == set(c.get('members', [c['id']])):
                    c1 = c
                if set(cluster2_idx) == set(c.get('members', [c['id']])):
                    c2 = c

            # 创建新簇
            new_cluster = {
                'id': cluster_id,
                'left': c1['id'],
                'right': c2['id'],
                'height': distance,
                'size': c1['size'] + c2['size'],
                'members': c1.get('members', [c1['id']]) + c2.get('members', [c2['id']])
            }

            # 更新簇列表
            clusters = [c for c in clusters if c not in [c1, c2]]
            clusters.append(new_cluster)

            # 添加合并记录
            linkage_matrix.append([c1['id'], c2['id'], distance, new_cluster['size']])

            cluster_id += 1

        # 绘制树状图
        from scipy.cluster.hierarchy import dendrogram
        plt.figure(figsize=(10, 5))
        dendrogram(np.array(linkage_matrix))
        plt.title('AGNES 聚类树状图')
        plt.xlabel('样本索引')
        plt.ylabel('距离')
        plt.show()

可视化聚类结果：

# 测试数据集
from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples=50, centers=3, random_state=42)

# 运行 AGNES
agnes = AGNES(n_clusters=3, linkage='average')
agnes.fit(X)

# 绘制结果
plt.scatter(X[:, 0], X[:, 1], c=agnes.labels_)
plt.title('AGNES 聚类结果')
plt.show()

# 绘制树状图
agnes.plot_dendrogram()

AGNES 算法中有几个关键参数会影响聚类结果：

连接标准（linkage）：
单连接：对噪声敏感，容易产生 ” 链式效应 ”，适合细长或不规则形状的簇
全连接：对噪声和离群点更鲁棒，倾向于发现紧凑的、大小相似的簇
平均连接：折中方案，通常效果较好
Ward 方法：倾向于发现大小相近的簇，最小化簇内方差
距离度量 ：
欧氏距离：适用于连续数值数据
曼哈顿距离：对离群点更不敏感
余弦相似度：适用于文本或高维稀疏数据
簇的数量（n_clusters）：
可以通过观察树状图的 ” 最长竖线 ” 来确定
使用轮廓系数等指标评估

AGNES 算法的时间和空间复杂度较高：

时间复杂度 ：O(n³)，因为每次合并都需要计算和更新距离矩阵
空间复杂度 ：O(n²)，需要存储距离矩阵

对于大规模数据集的优化思路：

使用更高效的距离矩阵计算方法
采用采样或分治策略
使用近似算法或并行计算
结合其他聚类方法（如先使用 K -means 预处理）

内存不足 ：处理大数据集时，距离矩阵会占用大量内存。解决方案：
使用稀疏矩阵
分批处理
选择内存效率更高的实现
连接标准选择不当 ：
单连接可能导致 ” 链式效应 ”
全连接可能导致过度分割
根据数据特性选择合适的连接标准
距离度量选择不当 ：
非数值数据需要特殊处理
高维数据可能需要降维
忽略数据标准化 ：
不同尺度的特征会影响距离计算
标准化或归一化是必要步骤
错误解释树状图 ：
切割高度的选择需要结合业务需求
可以结合其他评估指标验证

让我们使用鸢尾花数据集来演示 AGNES 的应用：

from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler

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

# 标准化
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# 运行 AGNES
agnes = AGNES(n_clusters=3, linkage='ward')
agnes.fit(X_scaled)

# 评估
from sklearn.metrics import adjusted_rand_score
print("调整兰德指数:", adjusted_rand_score(y, agnes.labels_))

# 可视化
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=agnes.labels_)
plt.title('鸢尾花数据集 AGNES 聚类结果')
plt.show()