思路

• 初始化: 用 train 的前 3 行作为质心 c0,c1,c2。

• 迭代(≤100轮):

  • 计算每个训练样本到 3 个质心的欧氏距离，按最小距离分配簇（并列取索引小者）。
  • 逐簇取均值作为新质心；若簇空则质心不变。
  • 收敛判定：所有质心各坐标变化量的最大绝对值 < 1e-6 即停止。

• 重映射: 将 3 个质心按坐标字典序升序排序，并据此将质心编号重置为 0/1/2。

• 预测: 用排序后的质心对 test 逐行取最近质心编号，输出 JSON 数组。

Python 实现

import sys
import json
import numpy as np

def kmeans_predict(train, test, k=3, max_iter=100, tol=1e-6):
    X = np.asarray(train, dtype=float)
    T = np.asarray(test, dtype=float)

    # 初始化质心：前3行
    centroids = X[:k].copy()

    for _ in range(max_iter):
        # 计算距离并分配簇（并列索引最小者优先由 argmin 保证）
        dists = np.linalg.norm(X[:, None, :] - centroids[None, :, :], axis=2)
        labels = np.argmin(dists, axis=1)

        # 备份质心用于收敛判断
        old = centroids.copy()

        # 重新计算质心；空簇保持不变
        for i in range(k):
            mask = (labels == i)
            if np.any(mask):
                centroids[i] = X[mask].mean(axis=0)

        # 收敛判断：所有坐标变化量 < tol
        if np.max(np.abs(centroids - old)) < tol:
            break

    # 质心排序（按第一维、再第二维... 升序），并重置编号为 0/1/2
    order = np.lexsort(centroids.T[::-1])
    centroids_sorted = centroids[order]

    # 用最终质心为 test 打标签
    tdists = np.linalg.norm(T[:, None, :] - centroids_sorted[None, :, :], axis=2)
    preds = np.argmin(tdists, axis=1)
    return preds.tolist()

def main():
    data = json.loads(sys.stdin.read())
    train = data["train"]
    test = data["test"]
    preds = kmeans_predict(train, test, k=3, max_iter=100, tol=1e-6)
    sys.stdout.write(json.dumps(preds, separators=(',', ':')))

if __name__ == "__main__":
    main()

• 读取单行 JSON，按要求进行 K-Means（初始化、空簇处理、收敛阈值 1e-6、最多 100 轮），质心按字典序排序后对测试集输出 [0,1,2] 标签。

题目内容

请你实现 $K-Means$ 聚类 $(K=3)$ 并用训练好的质心为测试样本打上“簇标签”。

步骤

1.读取数据：$train$ 为二维数值列表(无标签)，$test$ 同维度：所有元素整数或浮点数

2.初始化质心：取训练集的前 $3$ 行作为初始质心 $c_0,c_1,c_2$ (保持原序)

3.迭代更新：最多 $100$ 轮；每轮 $①$ 计算训练样本到 $3$ 个质心的欧氏距离；分配到最近质心 $②$ 重新计算各簇均值作为新质心；若某簇空，其质心保持不变 $③$ 收敛条件：若 $3$ 个质心中每个质心的每个坐标分量相比上一轮的变化量(绝对值)都小于 $1e-6$ ，则算法收敛。

4.质心排序与重映射：迭代结束后，将 $3$ 个质心按第一维坐标升序排序(若相等再按第二维、依此类推)，并将它们重新编号为标签 $0、1、25$ . 测试预测：用最终质心为 $test$ 每行计算最近质心编号(重映射后的 $0/1/2$ )；依次输出

输入描述

标准输入仅 一行 $JSON$ ：

{

"train":[[f11,...,f1m],

​ ...

​ [fn1,...,fnm]],

"test":[[t11,...,t1m],

​ ...

​ [tk1,...,tkm]]

}

• 训练样本数 $n≥3$ ，特征维度 $m≥1$，测试样本数 $k≥1$ 。

• 行与行之间无额外空白

输出描述

标准输出仅一行——测试集中每个样本对应的簇标签 $(0/1/2)$ 组成的 $JSON$ 数组，例如： $[0,1,2]$

补充说明

1.距离并列时，$numpy.argmin$ 自带的“索引最小者优先”即可

2.排序后的质心重新编号为 $0、1、2$

3.精度判断阈值为 $1e-6$ ；不用额外随机种子

样例1

输入

{"train":[[0,0],[5,5],[10,0],[0,1],[6,6],[10,1]],"test":[[0.2,0.1],[5.5,5.2],[9,0]]}

输出

[0,1,2]