k 近邻法

k 近邻算法

k 近邻（k-Nearest Neighbors, kNN）是最直觉的分类算法：给定训练集，对新输入实例，找到与它距离最近的 k 个训练样本，然后用多数表决决定它的类别。

没有显式的训练过程——模型就是训练数据本身。这种方式叫做懒惰学习（lazy learning）：把所有计算推迟到预测阶段。

形式化描述：给定训练数据集 $T = \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_N, y_N)\}$，对新输入 $\mathbf{x}$：

1. 根据距离度量，在 $T$ 中找到与 $\mathbf{x}$ 最近的 $k$ 个点，记这个邻域为 $N_k(\mathbf{x})$
2. 在 $N_k(\mathbf{x})$ 中按多数表决规则决定 $\mathbf{x}$ 的类别：

就这么简单。但这三行描述里藏了三个关键选择：距离度量、k 值、决策规则——它们共同决定了模型的行为。

k 近邻模型

kNN 的模型实际上对应了对特征空间的一种划分。当训练集、距离度量、k 值和决策规则确定后，任意一个新输入点的分类结果也就确定了——整个特征空间被切成了若干区域，每个区域对应一个类别。

这就是 kNN 的决策边界：它不是一条线或一个面，而是由数据点的分布和 k 值共同"雕刻"出来的复杂形状。

拖动下面的查询点，观察 k 怎么改变决策：

距离度量

"最近"是怎么定义的？这取决于距离度量的选择。最常用的是 $L_p$ 距离（闵可夫斯基距离）：

三个特殊情况：

距离度量的选择会直接改变"谁是邻居"——同样的数据，换一种距离，最近的 k 个点就可能完全不同，分类结果也会翻转。

实践中最常用欧氏距离。但要注意：如果特征的量纲不同（比如身高 cm 和体重 kg），必须先做标准化，否则量纲大的特征会主导距离计算。

k 值的选择

k 是 kNN 唯一的超参数，但它对模型的影响是根本性的。

k 太小（极端情况 k=1）：模型对噪声极度敏感。一个噪声点就能主导附近的决策区域——决策边界变得锯齿状、极度复杂。这是过拟合：训练误差为 0（每个点的最近邻就是自己），但泛化误差高。

k 太大（极端情况 k=N）：模型变得极度平滑。无论输入什么，预测结果都是训练集中最多的那个类——决策边界消失了。这是欠拟合：模型完全忽略了输入的局部结构。

最佳的 k 通常通过交叉验证选取。

多数表决与经验风险最小化的等价性：多数表决等价于在 0-1 损失下最小化经验风险。设分类函数 $f: \mathbb{R}^n \to \{c_1, \ldots, c_K\}$，误分类率为：

要使这个值最小，$f(\mathbf{x})$ 就应该取 $N_k(\mathbf{x})$ 中出现最多的类——正是多数表决。

kd 树

暴力搜索最近邻的复杂度是 $O(N)$——对每个查询都要扫描全部训练样本。当 $N$ 很大时，这不可接受。kd 树（k-dimensional tree）通过预先组织数据结构，把搜索加速到平均 $O(\log N)$。

构建：递归地用超平面切分空间。每一层选一个坐标轴，取该维度上的中位数作为切分点，左子树包含该维度值更小的点，右子树包含更大的点。坐标轴在各层交替使用。

构建过程的伪代码：

• 选择当前深度对应的坐标轴 $j = \text{depth} \mod n$
• 找到该轴上的中位数点作为节点
• 递归构建左子树（该轴值 < 中位数的点）和右子树（> 中位数的点）

结果是一棵平衡二叉树，每个内部节点对应一个超平面切分。

搜索：从根节点出发，按目标点在切分维度上的值决定先进左子树还是右子树（跟普通 BST 一样）。到达叶节点后回溯，核心剪枝条件是：如果目标点到当前节点切分超平面的距离，大于已经找到的最近距离，则另一侧子树不可能包含更近的点——直接跳过。

这个回溯剪枝在数据分布均匀时非常有效。但在高维空间中（维度 > 20），由于"维度灾难"，kd 树退化到接近暴力搜索。此时可以用近似最近邻算法（如 LSH、HNSW）来替代。