我要招人

去企业版

首页 > 试题广场 >

标签在前K个近邻中的出现次数

[编程题]标签在前K个近邻中的出现次数

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

你需要为一个简单的多分类识别器补上“K 近邻”判别模块。做法是：先度量待测样本与训练样本的距离，挑选出距离最近的 K 个样本，再用多数票决定最终类别。
操作要点（按流程执行）：
- 先计算待测点到每个样本点的距离（为了效率，可直接用“平方欧氏距离”参与排序，结果等价）。
- 将样本按距离升序排列，截取前 K 个作为近邻。
- 统计这 K 个近邻的标签出现次数，频数最高的标签即为预测值。
- 如出现“最高频数并列”，只在并列标签对应的近邻里，按由近到远的顺序挑第一个的标签。
约束与假设：
- 数据集已做归一化处理（不同维度量纲一致），特征保留两位小数。
- 每个类别在数据集中都至少有一个样本。
- 距离采用欧氏距离： $d(q,x)=\sqrt{\sum_{i=1}^{n}(q_i-x_i)^2}$

输入描述:

第 1 行：k m n s
k 为最近邻个数（≤20），m 为样本数（≤200），n 为特征维度（不含标签，≤5），s 为类别个数（≤5）。
第 2 行：待分类样本的 n 维特征。
第 3 行至第 m+2 行：每行 n+1 列，前 n 列为特征，最后 1 列为类别标签（整数，以浮点给出）。

输出描述:

输出两项：预测标签 与 该标签在前 K 个近邻中的出现次数  
  格式：label count

示例1

输入

3 6 2 2
0.00 0.00
0.20 0.10 0.0
0.30 0.00 0.0
0.00 0.40 1.0
0.60 0.60 1.0
0.05 0.02 0.0
0.90 0.90 1.0

输出

0 3

说明

距离最近的 3 个样本依次为 (0.05,0.02,0), (0.20,0.10,0), (0.30,0.00,0)。  
多数票为标签 0，且在前 K=3 个邻居中出现 3 次，故输出“0 3”。

示例2

输入

4 6 2 3
1.00 1.00
0.95 0.95 2.0
1.10 1.00 2.0
0.90 1.10 1.0
0.80 0.90 1.0
2.00 2.00 3.0
1.30 1.40 1.0

输出

2 2

说明

最近的 4 个邻居按距离为：(0.95,0.95,2)、(1.10,1.00,2)、(0.90,1.10,1)、(0.80,0.90,1)。  
标签 1 与 2 在前 K=4 中均出现 2 次，构成并列；比较并列集合中“最近”的样本，其最近者为 (0.95,0.95,2)，因此最终返回标签 2；同时输出该标签在前 K 中出现的次数 2。

备注:

本题由牛友@Charles 整理上传

算法知识视频讲解

Python3

ClydeSpeed

k, m, n, s = map(int, input().split())

test_features = list(map(float, input().split()))

train_samples = []

for _ in range(m):

data = list(map(float, input().split()))

features = data[:n]

label = int(data[n])

train_samples.append((features, label))

# 计算待测样本到每个训练样本的平方欧氏距离

distances = []

for features, label in train_samples:

sq_dist = sum((test_features[i] - features[i]) ** 2 for i in range(n))

distances.append((sq_dist, label, features))

# 按距离升序排序，取前K个近邻

distances.sort(key=lambda x: x[0])

k_nearest = distances[:k]

# 统计前K个近邻中各类别的出现频次

count = {}

for _, label, _ in k_nearest:

count[label] = count.get(label, 0) + 1

max_count = max(count.values())

# 找出具有最高频数的标签

max_labels = [label for label, count in count.items() if count == max_count]

if len(max_labels) == 1:

predicted_label = max_labels[0]

else:

for _, label, _ in k_nearest:

if label in max_labels:

predicted_label = label

break

print(f"{predicted_label} {max_count}")

发表于 2025-09-03 13:36:27 回复(0)

提交观点

问题信息

难度：

1条回答 24收藏 216浏览

标签在前K个近邻中的出现次数

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

相关试题