聚类识别

题目分析

给定 个 4 维样本点，使用 KMeans 算法将其划分为 个簇，最多迭代 次。输出每个簇的样本数量（升序排列）。

思路

模拟 KMeans 聚类

严格按题意实现标准 KMeans 流程即可：

初始化质心：直接取前 个样本作为初始质心。

分配阶段：对每个样本，计算它到所有质心的欧氏距离的平方（4 维空间），将其归入距离最近的簇。

更新阶段：对每个簇，将质心更新为该簇内所有样本的均值。若某个簇为空，则保持质心不变。

收敛判断：计算所有质心移动距离的平方，若最大值小于 ，则提前终止；否则继续迭代直到达到最大迭代次数 。

最后统计每个簇的样本数量，排序后输出。

关键细节：

• 距离使用平方欧氏距离，不开根号。
• 空簇不更新质心，避免除零错误。
• 收敛阈值是质心平方距离变化量的最大值与 比较。

代码

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    k = int(input_data[idx]); idx += 1
    m = int(input_data[idx]); idx += 1
    n = int(input_data[idx]); idx += 1

    points = []
    for i in range(m):
        p = [float(input_data[idx + j]) for j in range(4)]
        idx += 4
        points.append(p)

    # 初始质心：前 k 个样本
    centroids = [points[i][:] for i in range(k)]

    for iteration in range(n):
        # 分配：每个点归入最近质心的簇
        clusters = [[] for _ in range(k)]
        for p in points:
            best = 0
            best_dist = sum((p[d] - centroids[0][d]) ** 2 for d in range(4))
            for c in range(1, k):
                dist = sum((p[d] - centroids[c][d]) ** 2 for d in range(4))
                if dist < best_dist:
                    best_dist = dist
                    best = c
            clusters[best].append(p)

        # 更新质心
        new_centroids = []
        for c in range(k):
            if len(clusters[c]) == 0:
                new_centroids.append(centroids[c][:])
            else:
                sz = len(clusters[c])
                centroid = [0.0] * 4
                for p in clusters[c]:
                    for d in range(4):
                        centroid[d] += p[d]
                for d in range(4):
                    centroid[d] /= sz
                new_centroids.append(centroid)

        # 收敛检查
        max_shift = 0.0
        for c in range(k):
            shift = sum((new_centroids[c][d] - centroids[c][d]) ** 2 for d in range(4))
            if shift > max_shift:
                max_shift = shift

        centroids = new_centroids

        if max_shift < 1e-8:
            break

    # 统计并排序输出
    sizes = [len(clusters[c]) for c in range(k)]
    sizes.sort()
    print(' '.join(map(str, sizes)))

main()

复杂度分析

• 时间复杂度：，其中 为最大迭代次数， 为样本数， 为簇数， 为维度。每轮迭代对每个样本计算到 个质心的距离。
• 空间复杂度：，存储所有样本点和 个质心。