算法介绍

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

聚类算法有很多种，K-Means 是聚类算法中的最常用的一种，算法最大的特点是简单，好理解，运算速度快，但是只能应用于连续型的数据，并且一定要在聚类前需要手工指定要分成几类。

K-Means 聚类算法的大致意思就是“物以类聚，人以群分”：

• 对于m组数据点，首先输入 k 的值，即我们指定希望通过聚类得到 k 个分组；
• 从数据集中随机选取 k 个数据点作为初始中心（一般选取前k个）；
• 对集合中每一个数据点，计算与每一个中心的距离（可选曼哈顿距离），离哪个中心距离近，就归类哪个中心。
• 这时每一个中心手下都聚集了一群点，这时候召开选举大会，每一群选出新的中心（即通过算法选出新的中心）。
• 如果新中心和老中心之间的距离小于某一个设置的阈值（表示重新计算的中心的位置变化不大，趋于稳定，或者说收敛），可以认为我们进行的聚类已经达到期望的结果，算法终止。
• 如果新中心和老中心距离变化很大，需要迭代3~5步骤。

算法实现

import math

# k-means 曼哈顿距离
class kmeans:
    def __init__(self, m, k):
        self.m = m  # 坐标点个数
        self.k = k  # 分组个数

    # 输入坐标列表
    def input_coordinate(self):
        coordinate_list = [[0 for i in range(2)] for j in range(self.m)]  # 坐标列表
        for i in range(self.m):
            coordinate_list[i][0], coordinate_list[i][1] = map(int, input().split())  # 输入坐标
        return coordinate_list

    # 计算相异矩阵
    def calculate_distance(self, coordinate_list):
        distance_list = [[0 for i in range(self.m)] for j in range(self.m)]  # 相异矩阵列表m*m
        for i in range(self.m):
            for j in range(i+1):
                distance_list[i][j] = abs(coordinate_list[i][0] - coordinate_list[j][0]) + abs(coordinate_list[i][1] - coordinate_list[j][1])
        return distance_list
    
    # 输出相异矩阵
    def output_distance(self, distance_list):
        for i in range(self.m):
            for j in range(i+1): # 输出一半矩阵
                print(distance_list[i][j], end=' ')
            print()
    
    # 初始分组
    def min_distance1(self, distance_list):
        k = self.k # 分组个数
        klist = []  # 起始中心点id
        min_distance = []  # 最小距离
        min_distance_id = [[0 for i in range(self.m)] for j in range(k)] # 最小距离对应id列表k*m
        for i in range(k):
            klist.append(int(input())-1) # 输入起始中心点id,从1开始
        
        for i in range(self.m):
            mindist = 20 # 初始化最小距离(要大于任意两点间距离)
            for j in klist:
                if distance_list[i][j] < mindist:
                    mindist = distance_list[i][j]
                    kid = j
            min_distance.append(mindist)
            min_distance_id[kid][i] = i+1
        return min_distance_id
    
    # 更新中心点
    def update_center(self, coordinate_list, min_distance_id):
        center_point = [[0 for i in range(2)] for j in range(self.k)]
        for i in range(self.k):
            count = 0
            for j in range(self.m):
                mindstid = min_distance_id[i][j]
                if(mindstid != 0):
                    count += 1
                    center_point[i][0] += coordinate_list[mindstid-1][0]
                    center_point[i][1] += coordinate_list[mindstid-1][1]
            center_point[i][0] = round(center_point[i][0]/count, 3)
            center_point[i][1] = round(center_point[i][1]/count, 3)
        return center_point

    #  再次分组
    def min_distance2(self, coordinate_list, center_point):
        k = self.k
        min_distance = []  # 最小距离
        min_distance_id = [[0 for i in range(self.m)] for j in range(k)] # 最小距离对应id
        for i in range(self.m):
            mindist = 20 # 初始化最小距离
            for j in range(k):
                center_distance = abs(coordinate_list[i][0] - center_point[j][0]) + abs(coordinate_list[i][1] - center_point[j][1])
                if center_distance < mindist:
                    mindist = center_distance
                    kid = j
            min_distance.append(mindist)
            min_distance_id[kid][i] = i+1
        return min_distance_id

    # 输出分组结果
    def output_result(self, min_distance_id):
        for i in range(self.k):
            for j in range(self.m):
                if min_distance_id[i][j] != 0:
                    print(min_distance_id[i][j], end=' ')
            print()


if __name__ == '__main__':
    m = 12 # 坐标点个数
    k = 3 # 分组个数
    kme= kmeans(m,k)
    print('依次输入坐标列表,如 3 4')
    coordinate_list = kme.input_coordinate()
    distance_list = kme.calculate_distance(coordinate_list)
    kme.output_distance(distance_list)

    # 初始分组
    print("初始分组，从1开始依次输入中心点id：")
    min_distance_id =  kme.min_distance1(distance_list)
    kme.output_result(min_distance_id)
    # print(min_distance_id)
    while True:
        center_point = kme.update_center(coordinate_list, min_distance_id)
        print(center_point)
        new_min_distance_id = kme.min_distance2(coordinate_list, center_point)
        # print(new_min_distance_id)
        if min_distance_id == new_min_distance_id:
            break
        min_distance_id = new_min_distance_id
        kme.output_result(min_distance_id)