小红正在研发一款部署在智能音箱上的语音意图识别系统。该系统的核心逻辑是将用户输入的语音信号转化为一个三维特征向量，并通过比较该向量与已知样本库中向量的距离来进行分类。 具体而言，小红采用了 K 最近邻（KNN）算法。对于一个待识别的特征向量，系统会在样本库中寻找欧氏距离最近的 K 个已知样本。接着，系统会统计这 K 个样本所属的意图类别标签，并将出现频率最高的标签作为预测结果。如果存在多个类别标签的出现次数相同且均为最高，小红规定输出其中数值最小的那个标签。 题目保证在距离第 K 近的边界上不会出现多个样本距离相等而导致的歧义。
输入描述:
第一行包含两个正整数 N 和 K，分别表示样本库中已知语音特征向量的数量，以及分类时需要参考的最近邻个数（）。接下来的 N 行，每行包含三个浮点数 x1, x2, x3 和一个整数 label。其中 (x1, x2, x3) 是特征向量在三维空间中的坐标（取值范围在 -1000.0 到 1000.0 之间），label 是该样本对应的意图类别标签（取值范围为 0 到 之间的整数）。最后一行包含三个浮点数，代表当前需要进行意图识别的目标语音特征向量坐标。
输出描述:
输出一个整数，代表分类器预测出的意图类别标签。
示例1
输入
4 3
0.0 0.0 0.0 10
1.0 1.0 1.0 20
0.0 1.0 0.0 10
10.0 10.0 10.0 30
0.1 0.1 0.1
说明
目标特征向量为 (0.1, 0.1, 0.1)。计算它到样本库中四个点的欧氏距离，距离最近的三个样本分别是：
1. (0.0, 0.0, 0.0)，标签为 10；
2. (0.0, 1.0, 0.0)，标签为 10；
3. (1.0, 1.0, 1.0)，标签为 20。
在这三个最近邻中，标签 10 出现了 2 次，标签 20 出现了 1 次。因此，出现次数最多的标签是 10。
示例2
输入
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
说明
The target feature vector is (2.2, 2.1, 2.3). Its squared Euclidean distances to the known vectors are calculated. The 3 nearest neighbors are (2.1, 2.3, 2.2) of category 1, (2.3, 2.2, 2.4) of category 1, and (2.2, 2.4, 2.3) of category 1. Since all 3 nearest neighbors belong to category 1, the target vector is classified as category 1.
加载中...