【数据挖掘】AGNES聚类算法（python实现）

偏执的太偏执、 2023-03-01 10:15 275阅读 0赞

# 一、python代码 #

'''
    Author: Vici__
    date: 2020/5/21
    '''
    
    import math
    
    '''
    Point类，记录坐标x，y和点的名字id
    '''
    class Point:
        '''
        初始化函数
        '''
        def __init__(self, x, y, id):
            self.x = x # 横坐标
            self.y = y # 纵坐标
            self.id = id # 名字（编号） 
        '''
        计算两点之间的欧几里得距离
        '''
        def calc_Euclidean_distance(self, p2):
            return math.sqrt((self.x - p2.x) * (self.x - p2.x) + (self.y - p2.y) * (self.y - p2.y))
    
    '''
    1. 获取数据集
    '''
    def get_dataset():
        # 原始数据集以元组形式存放，(横坐标，纵坐标，编号)
        datas = [(0, 2, 'A'), (0, 0, 'B'), (1.5, 0, 'C'), (5, 0, 'D'), (5, 2, 'E')]
        dataset = [] # 用于计算两点之间的距离，形式 [point1, point2...]
        C = {} # 用于簇之间的合并操作，形式{index1:[p1], index2:[p2]...}
        for i in range(len(datas)): # 遍历原始数据集
            point = Point(datas[i][0], datas[i][1], datas[i][2]) # 利用(横坐标，纵坐标，编号)实例化
            dataset.append(point) # 放入dataset中
            C[str(i)] = [point] # 编号和点做映射
        return dataset, C # [p1, p2], {index:[p1]}
    
    '''
    2. 计算任意两点之间的距离
    '''
    def get_dist(dataset):
        n = len(dataset) # 点的个数
        dist = [] # 存放任意两点之间的距离
        for i in range(n):
            dist_i = [] # 临时列表
            for j in range(n): # 遍历数据集
                # 计算距离并放入临时列表中
                dist_i.append(dataset[i].calc_Euclidean_distance(dataset[j]))
            dist.append(dist_i) # 利用临时列表创建二维列表
        # 打印dist
        print("任意两点之间的距离：")
        for d in dist:
            print(d)
        print()
        return dist
    
    '''
    3. 寻找最小距离，并返回这两点的编号
    '''
    def find_Min(dist):
        n = len(dist)
        (p1, p2) = (-1, -1) # 定义两个点的编号
        Min = float("INF")  # 初始化最小值为无穷大
        for i in range(n): # 遍历dist列表
            for j in range(i+1, n): # 从i+1开始即可，因为这个列表是对称矩阵
                if dist[i][j] < Min and dist[i][j] != 0: # 当前两点距离小于最小值
                    Min = dist[i][j] # 更新最小距离
                    (p1, p2) = (i, j) # 更新两点编号
        return p1, p2 # 返回这两点的编号
    
    '''
    4. 更新距离列表，将此列表扩大一行一列
    '''
    def update_dist(index, dist, p1, p2):
        last_row = [] # 新加的最后一行
        n = len(dist)
        for i in range(n):
            Min = min(dist[p1][i], dist[p2][i]) # 取这两个点和其它点之间较小的距离，作为这新簇和其它点的距离
            dist[i].append(Min) # 增加最后一列
            last_row.append(Min) # 增加最后一行
        last_row.append(0)
        dist.append(last_row) 
    
        for i in range(n): # 遍历原dist列表，使p1, p2失效，新增的簇代替了他们
            dist[p1][i] = float("INF")
            dist[p2][i] = float("INF")
            dist[i][p1] = float("INF")
            dist[i][p2] = float("INF")
    
    '''
    5. AGNES算法主函数
    '''
    def AGNES(dataset, C, k):
        dist = get_dist(dataset) # 计算任意两点之间的距离
        index = count = len(dataset) # index是用来给新簇编号的，count是用来记录簇的个数的
        while count > k: # 当簇等于k个时，结束循环
            p1, p2 = find_Min(dist) # 找到当前最短距离的两个簇
            C[str(index)] = C[str(p1)] + C[str(p2)] # 新簇是两个簇的合并
            del C[str(p1)] 
            del C[str(p2)] # 删除两个旧簇
            update_dist(index, dist, p1, p2) # 更新dist列表
            index += 1 # 新簇编号前移
            count -= 1 # 簇的个数减少1个
            print("合并后的新簇：")
            for value_set in C.values():
                for element in value_set:
                    print(element.id, end="")
                print()
        # 打印结果
            
    
    dataset, C = get_dataset()
    k = 2
    AGNES(dataset, C, k)

# 二、测试 #

要求输出聚类后各个簇中数据点的编号。实验数据：设有5个样本点。设终止条件为“k=2”。样本数据集如下表所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70]: /images/20230209/c59ac9759f7541d2be938be005cee04c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70 1]: /images/20230209/76342ace95604e588d72b40a34729272.png