用户分群

题目分析

电商平台需要根据用户的购物行为（月均消费金额、月均访问次数、退货率三个维度）对用户进行聚类分群。给定 个初始聚类中心和指定迭代次数，实现标准 KMeans 算法，输出最终的聚类中心坐标，保留两位小数。

思路

KMeans 算法模拟

这道题不需要任何花哨的优化，就是忠实模拟 KMeans 的两个核心步骤，反复执行指定次数即可。

每轮迭代分两步：

1. 分配阶段：对每个数据点，计算它到所有 个聚类中心的欧氏距离（比较距离时用距离平方即可，省去开根号），将其归入距离最近的聚类
2. 更新阶段：对每个聚类，将中心更新为该聚类内所有点各维度的算术平均值。若某聚类没有点被分配到，中心保持不变

注意欧氏距离公式为 ，但由于只需要比较大小，计算时省略 不影响结果。

以样例 1 验证：，初始中心 和 ，6 个数据点，迭代 2 次。

• 第 1 轮： 距第一个中心更近，归入第一组；另外三个点归入第二组
• 更新中心为 和
• 第 2 轮：分配结果不变，中心不变，输出即为答案

复杂度

• 时间复杂度：，其中 为特征维度
• 空间复杂度：

代码

import sys

def main():
    data = sys.stdin.read().split()
    idx = 0
    K = int(data[idx]); idx += 1
    centers = []
    for i in range(K):
        c = [float(data[idx]), float(data[idx+1]), float(data[idx+2])]
        idx += 3
        centers.append(c)
    iters = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    points = []
    for i in range(m):
        p = [float(data[idx]), float(data[idx+1]), float(data[idx+2])]
        idx += 3
        points.append(p)

    for _ in range(iters):
        clusters = [[] for _ in range(K)]
        for p in points:
            best = -1
            best_dist = float('inf')
            for j in range(K):
                d = sum((p[d2] - centers[j][d2]) ** 2 for d2 in range(3))
                if d < best_dist:
                    best_dist = d
                    best = j
            clusters[best].append(p)

        for j in range(K):
            if clusters[j]:
                n = len(clusters[j])
                centers[j] = [sum(p[d2] for p in clusters[j]) / n for d2 in range(3)]

    for c in centers:
        print(f"{c[0]:.2f} {c[1]:.2f} {c[2]:.2f}")

main()