算法步骤

1. 输入参数：

   • 训练数据：

     • $X$：大小为 $N \times d$ 的训练样本特征矩阵，其中 $N$ 是样本数量，$d$ 是特征维度。
     • $y$：长度为 $N$ 的训练样本标签列表，标签取值为 $0$ 或 $1$。

   • 测试数据：

     • $x_{\text{test}}$：长度为 $d$ 的测试样本特征向量。

   • 参数 K：一个整数，表示选择的最近邻数量。

2. 计算距离：

   • 使用欧几里得距离来衡量测试样本与每个训练样本之间的相似度。欧几里得距离的计算公式为：
   $$d_i = \sqrt{\sum_{j=1}^{d} (x_{\text{test}, j} - x_{i, j})^2}$$

   在代码中，这一步由以下行实现：

   distances = np.linalg.norm(np.array(X) - np.array(x_test), axis=1)
   

   这里，np.array(X) - np.array(x_test) 计算每个训练样本与测试样本的差值，np.linalg.norm(..., axis=1) 计算每个样本的距离。

3. 选择 K 个最近邻：

   • 将所有计算得到的距离按从小到大排序，并获取 K 个距离最小的训练样本的索引。通过 np.argsort 实现索引的获取，代码如下：

   nearest_indices = np.argsort(distances)[:K]
   

   这段代码返回 K 个距离最小的训练样本的下标。

4. 进行投票预测：

   • 根据 K 个最近邻的标签 $y$ 中的值进行投票，选出出现次数最多的标签作为最终的预测结果。可以使用 Python 的 max 函数和集合类型实现这一步骤：

   nearest_labels = [y[i] for i in nearest_indices]
   y_pred = max(set(nearest_labels), key=nearest_labels.count)
   

   • nearest_labels 中存储了 K 个最近邻的标签，而 max(set(...), key=...) 将找到出现次数最多的标签。

5. 返回结果：

   • 将最终预测标签 y_pred 返回。

Python 代码实现

import numpy as np
from typing import List

class Solution:
    def knn_classification(self, X: List[List[float]], y: List[int], x_test: List[float], K: int) -> int:
        """实现KNN分类，根据最近的K个邻居进行多数投票得到最终预测标签"""
        
        # 步骤 1: 计算每个训练样本与测试样本的欧几里得距离
        distances = np.linalg.norm(np.array(X) - np.array(x_test), axis=1)
        
        # 步骤 2: 获取 K 个最近邻的索引
        nearest_indices = np.argsort(distances)[:K]
        
        # 步骤 3: 根据最近邻的标签进行投票
        nearest_labels = [y[i] for i in nearest_indices]
        
        # 步骤 4: 取得出现次数最多的标签作为预测结果
        y_pred = max(set(nearest_labels), key=nearest_labels.count)
        
        # 返回最终预测标签
        return y_pred

题目描述

给定一个测试样本 $x_{\text{test}}$，以及训练集：

$$X = [x_1, x_2, \dots, x_N]^\top \in \mathbb{R}^{N \times d}, \quad y = [y_1, y_2, \dots, y_N]$$

其中：

• 每个样本 $x_i \in \mathbb{R}^d$
• 标签 $y_i \in \{0,1\}$

请你实现 KNN 分类（K-Nearest Neighbors），并根据最近的 $K$ 个邻居进行多数投票得到最终预测标签。

1. 距离计算

$$d_i = \| x_{\text{test}} - x_i \|_2$$

2. 寻找 K 个最近邻

$$\mathcal{N}_K = \{ i_1, i_2, \dots, i_K \}$$

3. 多数投票预测

$$\hat{y} = \text{mode}(y_{i_1}, y_{i_2}, y_{i_K})$$

输入参数

• X：形状为 $N \times d$ 的训练数据矩阵
• y：长度为 $N$ 的训练标签列表
• x_test：长度为 $d$ 的测试样本
• K：要选择的最近邻个数

返回值

• y_pred：最终的预测标签（0 或 1）

示例

输入：

K = 2
X = [[1, 2], [2, 1], [3, 3]]
y = [0, 1, 1]
x_test = [2, 2]

输出：

y_pred = 1

提示

• 样本取值范围： $-1000 \le X[i,j], x_{\text{test}}[j] \le 1000$

• 标签： $y_i \in {0,1}$

• $K$ 的范围： $1 \le K \le N$

• 距离总是非负： $d\_i \ge 0$