AGNES算法实战：用Python对西瓜数据集进行聚类（附源码）

K-means 要求必须预设 k 值 - 需要事先知道或估计簇的数量，且其出初始点十分敏感，不同的初始中心可能导致不同结果，且其直接假设簇是球形的，这在一定程度上是不可能的，而层次聚类 (hierarchical clustering) 则没有这种问题，他在使用前不需要提前限定簇的个数，且也不强求分类之后的簇必须是球形的，这给层次聚类带来了巨大的应用前景，层次聚类在实际问题的解决上分为两种算法:

相较而言，AGNES 算法在使用中有着更广泛的应用前景，且其也已经研究较为透彻。

在 AGNES 中，由于簇的生成不是事先预定的，因此我们需要考虑距离采取的是哪一种度量方法，一般来说有三种距离统计方法:

其表示如下，在度量距离时，我们采取的是不同簇之间的最短距离:d(R, S) = \min_{x_R \in R, x_S \in S} d(x_R, x_S)

2. 最大连接距离法 (Complete Linkage)

取两个簇中距离最远的两个点的距离作为这两个簇的距离。 其表示的关系如下图所示，计算公式为:d(R, S) = \max_{x_R \in R, x_S \in S} d(x_R, x_S)

3. 平均关联 (Average-Linkage)

这种方法是 AGNES 算法常用的距离计算方法，其方法是将两个簇之间的所有点的距离两两算在一起，全部求平均值，这种方法是最为可靠的，其计算的公式如下:d(R, S) = \frac{1}{|R||S|} \sum_{x_R \in R, x_S \in S} d(x_R, x_S)

AGNES 的算法流程如下:

某农业研究所收集了 30 个西瓜样本的数据，包括每个西瓜的密度和含糖量两个特征。现在需要利用 AGNES（层次聚类）算法对这些西瓜进行分类，以帮助农民识别不同品质的西瓜。

实验的数据集如下:

处理的 python 代码如下:

import math
import matplotlib.pyplot as plt
import numpy as np


def dist(node1, node2):
    """
    计算欧几里得距离,node1,node2分别为两个元组
    :param node1: 第一个数据点
    :param node2: 第二个数据点
    :return: 欧几里得距离
    """
    return math.sqrt(math.pow(node1[0]-node2[0], 2) + math.pow(node1[1]-node2[1], 2))


def dist_min(cluster_x, cluster_y):
    """
    Single Linkage (最小距离)
    又叫做 nearest-neighbor，就是取两个类中距离最近的两个样本的距离作为这两个集合的距离。
    :param cluster_x: 簇类x
    :param cluster_y: 簇类y
    :return: 最小距离
    """
    return min(dist(node1, node2) for node1 in cluster_x for node2 in cluster_y)


def dist_max(cluster_x, cluster_y):
    """
    Complete Linkage (最大距离)
    这个则完全是 Single Linkage 的反面极端，取两个集合中距离最远的两个点的距离作为两个集合的距离。
    :param cluster_x: 簇类x
    :param cluster_y: 簇类y
    :return: 最大距离
    """
    return max(dist(node1, node2) for node1 in cluster_x for node2 in cluster_y)


def dist_avg(cluster_x, cluster_y):
    """
    Average Linkage (平均距离)
    这种方法就是把两个集合中的点两两的距离全部放在一起求均值，相对也能得到合适一点的结果。
    :param cluster_x: 簇类x
    :param cluster_y: 簇类y
    :return: 平均距离
    """
    return sum(dist(node1, node2) for node1 in cluster_x for node2 in cluster_y) / (len(cluster_x) * len(cluster_y))


def find_min(distance_matrix):
    """
    找出距离最近的两个簇下标
    :param distance_matrix: 距离矩阵
    :return: (x索引, y索引, 最小距离)
    """
    min_dist = float('inf')
    x = 0
    y = 0
    for i in range(len(distance_matrix)):
        for j in range(len(distance_matrix[i])):
            if i != j and distance_matrix[i][j] < min_dist:
                min_dist = distance_matrix[i][j]
                x = i
                y = j
    return (x, y, min_dist)


def AGNES(dataset, distance_method, k):
    """
    AGNES聚类算法模型
    :param dataset: 数据集
    :param distance_method: 计算簇类距离的方法
    :param k: 目标簇类数目
    :return: 聚类结果
    """
    print(f"数据集大小: {len(dataset)}")
    
    # 初始化簇类集合 - 每个样本作为一个簇
    cluster_set = []
    for node in dataset:
        cluster_set.append([node])
    
    print('初始簇类集合:')
    print(f"共有 {len(cluster_set)} 个簇")
    
    # 计算初始距离矩阵
    distance_matrix = []
    for cluster_x in cluster_set:
        distance_list = []
        for cluster_y in cluster_set:
            if cluster_x == cluster_y:
                distance_list.append(0)
            else:
                distance_list.append(distance_method(cluster_x, cluster_y))
        distance_matrix.append(distance_list)
    
    print(f'初始距离矩阵维度: {len(distance_matrix)} x {len(distance_matrix[0])}')
    
    q = len(dataset)
    iteration = 0
    
    # 合并更新
    while q > k:
        iteration += 1
        print(f"第 {iteration} 次迭代，当前簇数: {q}")
        
        # 找到距离最近的两个簇
        id_x, id_y, min_distance = find_min(distance_matrix)
        print(f"合并簇 {id_x} 和簇 {id_y}，距离: {min_distance:.4f}")
        
        # 合并簇（确保id_x < id_y，先删除索引大的）
        if id_x > id_y:
            id_x, id_y = id_y, id_x
            
        cluster_set[id_x].extend(cluster_set[id_y])
        del cluster_set[id_y]  # 删除已合并的簇
        
        # 重新计算距离矩阵
        distance_matrix = []
        for cluster_x in cluster_set:
            distance_list = []
            for cluster_y in cluster_set:
                if cluster_x == cluster_y:
                    distance_list.append(0)
                else:
                    distance_list.append(distance_method(cluster_x, cluster_y))
            distance_matrix.append(distance_list)
        
        q -= 1
    
    print(f"聚类完成！最终得到 {len(cluster_set)} 个簇")
    return cluster_set


def draw(cluster_set):
    """
    绘制聚类结果
    :param cluster_set: 聚类结果
    :return: None
    """
    # 设置中文字体
    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.rcParams['axes.unicode_minus'] = False
    
    color_list = ['red', 'blue', 'green', 'orange', 'purple', 'brown', 'pink', 'gray', 'olive', 'cyan']
    marker_list = ['o', 's', '^', 'D', 'v', '<', '>', 'p', '*', 'h']

    plt.figure(figsize=(10, 8))
    
    for cluster_idx, cluster in enumerate(cluster_set):
        coo_x = []  # x坐标列表（密度）
        coo_y = []  # y坐标列表（含糖量）

        for node in cluster:
            coo_x.append(node[0])
            coo_y.append(node[1])
        
        plt.scatter(coo_x, coo_y, 
                   marker=marker_list[cluster_idx % len(marker_list)], 
                   color=color_list[cluster_idx % len(color_list)], 
                   label=f'簇 {cluster_idx + 1} ({len(cluster)}个样本)',
                   s=100, alpha=0.7)

    plt.xlabel('密度')
    plt.ylabel('含糖量')
    plt.title('AGNES聚类结果 - 西瓜数据集')
    plt.legend(loc='upper right')
    plt.grid(True, alpha=0.3)
    plt.tight_layout()
    plt.show()


def print_cluster_details(cluster_set):
    """
    打印聚类详细信息
    :param cluster_set: 聚类结果
    """
    print("\n聚类详细结果:")
    print("=" * 50)
    for i, cluster in enumerate(cluster_set):
        print(f"簇 {i+1}: 包含 {len(cluster)} 个样本")
        for j, point in enumerate(cluster):
            print(f"  样本 {j+1}: 密度={point[0]:.3f}, 含糖量={point[1]:.3f}")
        
        # 计算簇中心
        center_x = sum(point[0] for point in cluster) / len(cluster)
        center_y = sum(point[1] for point in cluster) / len(cluster)
        print(f"  簇中心: 密度={center_x:.3f}, 含糖量={center_y:.3f}")
        print()


if __name__ == "__main__":
    # 数据集：每三个是一组分别是西瓜的编号，密度，含糖量
    data = """
    1,0.697,0.46,2,0.774,0.376,3,0.634,0.264,4,0.608,0.318,5,0.556,0.215,
    6,0.403,0.237,7,0.481,0.149,8,0.437,0.211,9,0.666,0.091,10,0.243,0.267,
    11,0.245,0.057,12,0.343,0.099,13,0.639,0.161,14,0.657,0.198,15,0.36,0.37,
    16,0.593,0.042,17,0.719,0.103,18,0.359,0.188,19,0.339,0.241,20,0.282,0.257,
    21,0.748,0.232,22,0.714,0.346,23,0.483,0.312,24,0.478,0.437,25,0.525,0.369,
    26,0.751,0.489,27,0.532,0.472,28,0.473,0.376,29,0.725,0.445,30,0.446,0.459"""

    # 数据处理 dataset是30个样本（密度，含糖量）的列表
    a = data.split(',')
    dataset = [(float(a[i]), float(a[i+1])) for i in range(1, len(a)-1, 3)]

    print("开始AGNES聚类算法")
    print("=" * 30)
    
    # 执行聚类（聚成3类）
    cluster_set = AGNES(dataset, dist_avg, 3)
    
    print('\n最终聚类结果:')
    print(cluster_set)
    
    # 打印详细信息
    print_cluster_details(cluster_set)
    
    # 绘制结果
    draw(cluster_set)
    
    print("聚类完成！")

最终的聚类结果如下的表格所示:

簇中心: 密度 =0.732, 含糖量 =0.423

簇中心: 密度 =0.630, 含糖量 =0.177

簇中心: 密度 =0.397, 含糖量 =0.290