首页 > 试题广场 >

聚类识别

[编程题]聚类识别

热度指数：107 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出 m 个终端的四维数值特征，需将它们用 KMeans 聚成 k 类，并输出各簇的样本数，从小到大排序后以空格分隔打印。实现规则如下：
初始质心：直接取数据中的前 k 个样本。
距离：使用四维欧氏距离的平方（少一次开方，比较大小结果不变）。
更新：每轮按最近质心分配样本，再用簇内四维特征的平均值更新该簇质心。
收敛判定：若所有质心的新旧位置变化量（平方距离）最大值小于 1e-8，或已达到最多迭代次数 n，则停止。
空簇处理：若某簇本轮没有样本，保持该簇质心不变，避免除零错误。

输入描述:

第一行：k m n
接下来 m 行：每行 4 个浮点数，表示一个终端的四维特征

输出描述:

一行：k 个整数（各簇样本数），升序排列，用空格分隔

示例1

输入

2 4 100
0.00 0.00 0.00 0.00
10.00 10.00 10.00 10.00
0.20 0.00 0.00 0.00
9.80 10.00 10.00 10.00

输出

2 2

说明

前两行即初始两个质心，后两点分别更接近对应质心；每簇各 2 个样本，升序输出为 2 2。

算法知识视频讲解

Python

Omitze

# 输入例子：
# 2 4 100
# 0.00 0.00 0.00 0.00
# 10.00 10.00 10.00 10.00
# 0.20 0.00 0.00 0.00
# 9.80 10.00 10.00 10.00
# 输出例子：
# 2 2
# 例子说明：
# 前两行即初始两个质心，后两点分别更接近对应质心；每簇各 2 个样本，升序输出为 2 2。

import pdb
import sys
import numpy as np

line = sys.stdin.readline().strip() # 读一行
k, m, n = map(int, line.split())
num_in_centroids = m // k

points = []
for _ in range(m):
line = sys.stdin.readline().strip() # 每次只读一整行
points.append(list(map(float, line.split())))
points = np.asarray(points)

centroids = points[:k].copy()
pre_centroids = centroids.copy()
points_labels = [[] for _ in range(k)]
counts = [0] * k

for i in range(n):
if i > 0 and np.max(np.linalg.norm(centroids - pre_centroids, axis=1)) < 1e-8:
break
counts = [0] * k
pre_centroids = centroids.copy()
for point in points:
dists = np.linalg.norm(point - centroids, axis=1)
label = np.argmin(dists)
points_labels[label].append(point)
counts[label] += 1
for idx in range(k):
if len(points_labels[idx]) > 0:
centroids[idx] = np.mean(points_labels[idx], axis=0)
points_labels[idx] = []

counts.sort()
print(' '.join(map(str, counts)))

编辑于 2025-11-30 22:24:50 回复(0)

牛客741040134号

import sys import numpy as np

ls = sys.stdin.readline().strip().split()
k, m, n = list(map(int, ls))
eles = np.zeros((k, m, 4)) # k,m,n = 2,4,4 # eles = np.array([[ 10.,10.,10.,10.], #   [9.8,10.,10.,10.], #   [ 0.  , 0., 0.,   0. ], #   [ 0.2  , 0., 0.,0. ]], dtype=np.float32) # eles = eles[None,:].repeat(2,0) for i, line in enumerate(sys.stdin):
    ls = sys.stdin.readline().strip().split()
    fls = list(map(float, ls)) try:
        eles[:, i] = fls except Exception: break  centers = eles[None, 0, :k].transpose((1, 0, 2)).repeat(m, 1)

new_centers = centers.copy() for i in range(n):
    dis = np.sum((eles - centers)**2, axis=-1)
    groups = np.argmin(dis, 0) for i in range(k):
        mean = eles[0, groups == i].mean(axis=0)
        new_centers[i, :] = mean[None, :] if np.allclose(new_centers, centers, atol=1e-8): break  centers = new_centers.copy() print(centers[:, 0]) for i in range(k): print(sum(groups == i), end=' ')

发表于 2025-11-28 01:39:09 回复(0)

提交观点

问题信息

难度：

2条回答 3收藏 54浏览

聚类识别

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题