解题思路

这道题本质上就是使用 $KNN$ 算法 对一个待分类的 $3$ 维特征向量进行分类。

已知有 $N$ 个带类别的语音特征向量，每个向量有 $3$ 个特征值和一个类别 $label$。对于待分类向量，我们需要：

1. 计算它与所有已知向量之间的欧式距离
2. 按距离从小到大排序
3. 取距离最近的 $K$ 个邻居

题目内容

在终端穿戴场景中，往往涉及到用户和终端设备之间的语音交互，通常由用户唤醒相关的设备并进行语音命令控制设备完成相应的操作，设备在收到语音命令时会对用户的意图进行识别，例如识别“拍照”“摄像”等意图，从而进行对应的操作。

要求使用 $KNN$ 算法对用户输出的语音特征进行分类：

语音片段经过特征提取后是一个 $3$ 维的向量

所有距离使用欧式距离公式计算，即对于两个 $N$ 维向量

$\vec{x} = (x_1, x_2, \dots, x_N), \quad \vec{y} = (y_1, y_2, \dots, y_N)$

两个向量间的距离为：$d_{(\vec{x},\vec{y})} = \sqrt{\sum_{k=1}^N (x_k - y_k)^2}$。

输入描述

第一行：正整数 $N$ 和 $K$，分别表示给定的已知语音特征向量的数量和邻居数量 $K$

第 $2$ ~ $13$ 行：已知语音的特征向量和 $label$，其中最后一位表示类别 $label$

第 $14$ 行：待分类的语音特征向量

输出描述

给出待分类语音的类别，该值为正整数在输入给定范围内.

样例1

输入

10 3  
0.5 0.3 0.4 0  
0.6 0.2 0.5 0  
0.4 0.3 0.3 0  
0.7 0.4 0.6 0  
2.1 2.3 2.2 1  
2.3 2.2 2.4 1  
2.2 2.4 2.3 1  
4.5 4.3 4.4 2  
4.4 4.5 4.6 2  
4.6 4.4 4.5 2  
2.2 2.1 2.3

输出

1

说明

待分类的语音特征向量为 $(2.2, 2.1, 2.3)$。计算其与所有已知向量的欧式距离后，最近的 $3$ 个邻居分别是：

• $(2.1, 2.3, 2.2)$ 类别 $1$
• $(2.3, 2.2, 2.4)$ 类别 $1$
• $(2.2, 2.4, 2.3)$ 类别 $1$

这3个邻居都属于类别 $1$ ，因此待分类向量被判定为类别 $1$ 。

样例2

输入

12 4  
1 0.9 1 1  
0.8 0.9 0.7 1  
1.3 1 1.2 1  
1.2 0.9 1 1  
2 2.2 2.1 2  
2.3 2.2 2 2
2 2.2 1.9 2  
1.9 2.2 2.1 2  
3.1 3.1 3 3  
2.8 2.9 3.1 3  
2.9 3 3.2 3  
3.1 3 3.1 3  
2.2 1.2 1.9

输出

2

说明

与 $2.2, 1.2, 1.9$ 最近的 $4$ 个邻居中，类别最多的是 $2$ ，故被分类为 $2$ 。