题目内容

$KNN$ 算法通过特征空间中的邻近关系判断未知样本的类别：未知样本的类别取决于与其距离最近的 $k$ 个已知样本中出现次数最多的类别。请根据这一思想完成分类任务。

给定待分类样本后，先计算它与每个已知样本之间的欧氏距离。距离函数定义为：

其中 $x$ 和 $y$ 表示两个样本的特征向量，$n$ 为特征维度。

按距离值从小到大对所有已知样本排序，并取前 $k$ 个样本作为最近邻。统计这些最近邻的类别标签出现频次，将频次最高的标签作为待分类样本的类别标签。

如果出现并列最高频次，即多个标签的频次相同且均为最大值，则在这些并列最高频的标签中，选择距离待分类样本最近的那个邻居对应的标签作为最终结果。

所有样本特征均已做归一化处理并保留两位小数，以消除不同特征之间的权重影响。数据集中每个类别都有样本，不会出现某类样本数量为 0 的情况。

最终需要输出两个值：待分类样本的类别标签，以及前 $k$ 个最近邻中该标签的出现次数。

约束条件：

• 最近邻居个数 $k$ 不超过 20。
• 样本数量 $m$ 不超过 200。
• 特征维度 $n$ 不超过 5。
• 类别个数 $s$ 不超过 5。

输入描述

第一行包含四个整数 k、m、n、s，依次表示最近邻居个数、已知样本数量、每个样本的特征维度（不含标签列）以及类别个数。

第二行包含 n 个浮点数，表示待分类样本的特征。

接下来 m 行，每行包含 n+1 个浮点数，表示一个已知样本。前 n 个数为该样本的特征，最后一个数为该样本的类别标签。

输出描述

输出一行，包含两个整数，用空格分隔。第一个整数为待分类样本的最终类别标签，第二个整数为该标签在距离最小的 k 个点中的出现次数。

样例1

输入

3 4 2 2
1.00 1.00
0.90 0.90 1.0
0.85 0.90 1.0
0.80 0.80 0.0
9.00 9.00 0.0

输出

1 2

说明

待分类样本为 $(1.00,1.00)$。计算各已知样本到它的欧氏距离：

0.90 0.90 1.0：$\sqrt{(0.90-1.00)^2+(0.90-1.00)^2}=\sqrt{0.02}$； 0.85 0.90 1.0：$\sqrt{(0.85-1.00)^2+(0.90-1.00)^2}=\sqrt{0.0325}$； 0.80 0.80 0.0：$\sqrt{(0.80-1.00)^2+(0.80-1.00)^2}=\sqrt{0.08}$； 9.00 9.00 0.0：距离最远。

按距离从小到大取前 3 个最近邻，标签依次为 1、1、0。类别 1 出现 2 次，类别 0 出现 1 次，因此最终标签为 1，出现次数为 2。

样例2

输入

4 5 2 3
0.50 0.50
0.60 0.50 2.0
0.50 0.61 1.0
0.70 0.50 2.0
0.50 0.71 1.0
8.00 8.00 3.0

输出

2 2

说明

待分类样本为 $(0.50,0.50)$。按距离从小到大排序，前 4 个样本为：

0.60 0.50 2.0：$\sqrt{(0.60-0.50)^2+(0.50-0.50)^2}=\sqrt{0.01}$； 0.50 0.61 1.0：$\sqrt{(0.50-0.50)^2+(0.61-0.50)^2}=\sqrt{0.0121}$； 0.70 0.50 2.0：$\sqrt{(0.70-0.50)^2+(0.50-0.50)^2}=\sqrt{0.04}$； 0.50 0.71 1.0：$\sqrt{(0.50-0.50)^2+(0.71-0.50)^2}=\sqrt{0.0441}$。

前 4 个最近邻的标签依次为 2、1、2、1。类别 2 和类别 1 都出现 2 次，出现次数并列最大。此时选择距离最近的那个邻居对应的标签：标签 2 的最近距离为 $\sqrt{0.01}$，标签 1 的最近距离为 $\sqrt{0.0121}$，因此最终标签为 2，出现次数为 2。

样例3

输入

1 3 1 2
0.30
0.10 1.0
0.20 0.0
0.45 1.0

输出

0 1

说明

待分类样本为 0.30。三个已知样本到它的距离分别是：

0.10：$|0.30-0.10|=0.20$； 0.20：$|0.30-0.20|=0.10$； 0.45：$|0.30-0.45|=0.15$。

由于 k 等于 1，只取距离最小的 1 个邻居，即 0.20，其标签为 0。因此最终标签为 0，在前 1 个最近邻中出现 1 次。

样例4

输入

5 6 3 3
1.00 1.00 1.00
0.90 1.00 1.00 2.0
0.80 1.00 1.00 2.0
0.70 1.00 1.00 2.0
0.60 1.00 1.00 1.0
0.50 1.00 1.00 1.0
0.40 1.00 1.00 0.0

输出

2 3

说明

待分类样本为 $(1.00,1.00,1.00)$。所有已知样本的后两维都与待分类样本相同，只有第一维不同，因此距离由第一维差的绝对值决定：

0.90：$|0.90-1.00|=0.10$； 0.80：$|0.80-1.00|=0.20$； 0.70：$|0.70-1.00|=0.30$； 0.60：$|0.60-1.00|=0.40$； 0.50：$|0.50-1.00|=0.50$； 0.40：$|0.40-1.00|=0.60$。

k 等于 5，取距离最小的前 5 个邻居。它们的标签依次为 2、2、2、1、1。类别 2 出现 3 次，类别 1 出现 2 次，因此最终标签为 2，出现次数为 3。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写