k 近邻法（k-nearest neighbor, K-NN）是一种基本分类与回归方法。此处只讨论分类问题中的 k 近邻法。

k 近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。

因此， k 近邻法不具有显式的学习过程。 k 近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

k 值的选择、距离度量及分类决策规则是 k 近邻法的三个基本要素。

k 近邻法 1968 年由 Cover 和 Hart 提出。

k 近邻算法

k 近邻算法简单、直观：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的 $k$ 个实例，这 $k$ 个实例的多数属于某个类，就把该输入实例分为这个类：

1. 根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖这 $k$ 个点的 $x$ 的邻域 记作 $N_k(x)$
2. 在 $N_k(x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别 $y$

$$y=\argmax_{c_j}\sum_{x_i\in N_k(x)}[y_i=c_j]$$

k 近邻法的特殊 $k=1$ 的情况，称为最近邻算法。对于输入的实例点（特征向量） $x$ ，最近邻法将训练数据集中与 $x$ 最邻近点的类作为 $x$ 的类。

k 近邻法没有显式的学习过程。

k 近邻模型

k 近邻模型使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、 k 值的选择和分类决策规则决定。

模型

k 近邻算法中，当训练集、距离度量（如欧氏距离）、 k 值及分类决策规则（如多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一地确定。这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。这一事实从最近邻算法中可以看得很清楚。

特征空间中，对每个训练实例点 $x_i$ ，距离该点比其他点更近的所有点组成一个区域，叫作单元（cell）。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。最近邻算法将实例 $x_i$ 的类 $y_i$ 作为其单元中所有点的类标记（class label）。这样，每个单元的实例点的类别是确定的。

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。 k 近邻模型的特征空间一般是 $n$ 维实数向量空间 $\mathbf R^n$ 。使用的举例是欧式距离，但也可以是其他距离，如更一般的 $L_p$ 距离（$L_p$ distance）或 Minkowski 距离（Minkowski distance）。

设特征空间 $\mathcal X$ 是 $n$ 维实数向量空间 $\mathbf R^n$ ， $x_i,x_j\in\mathcal X, x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T,x_j=(x_j^{(1)},x_j^{(2)},\cdots,x_j^{(n)})^T,x_i,x_j$ 的 $L_p$ 距离定义为

$$L_p(x_i, x_j)=\left(\sum_{l=1}^n\left|x_i^{(l)}-x_j^{(l)}\right|^p\right)^\frac1p$$

其中， $p\ge1$

当 $p=2$ 时，称为欧氏距离/欧几里得距离（Euclidean distance）

$$L_2(x_i, x_j)=\sqrt{\sum_{l=1}^n\left(x_i^{(l)}-x_j^{(l)}\right)^2}$$

当 $p=1$ 时，称为曼哈顿距离（Manhattan distance）

$$L_1(x_i, x_j)=\sum_{l=1}^n\left|x_i^{(l)}-x_j^{(l)}\right|$$

当 $p=\infty$ 时，称为切比雪夫距离（Chebyshev distance）

$$L_\infty(x_i, x_j)=\max_l\left|x_i^{(l)}-x_j^{(l)}\right|$$

由不同距离度量所确定的最近邻点是不同的

k 值的选择

k 值的选择会对 k 近邻算法的结果产生重大影响。

选择较小的 k 值，学习的近似误差(approximation error)会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用；但估计误差(estimation error)会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说， k 值的减小就意味着整体模型变得复杂，容易发生过拟合。

选择较大的 k 值，就相当于用较大邻域中的训练实例进行预测。估计误差会减小，但近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。 k 值的增大就意味着整体的模型变得简单。

如果 $k=N$ ，那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。

在应用中， k 值一般取一个比较小的数值。通常采用交叉验证法来选取最优的 k 值。

分类决策规则

k 近邻法中的分类决策规则往往是多数表决，即由输入实例的 k 个临近的训练实例中的多数类决定输入实例的类。

多数表决规则(majority voting rule)有如下解释：如果分类的损失函数为0-1损失函数，分类函数为

$$f:\mathbf R^n\to\{c_1,c_2,\cdots,c_K\}$$

那么误分类概率是 $P(Y\ne f(X))=1-P(Y=f(X))$

对给定的实例 $x\in\mathcal X$，其最近邻的 $k$ 个训练实例点构成集合 $N_k(x)$ 。如果涵盖 $N_k(x)$ 的区域的类别是 $c_j$ ，那么误分类率是

$$\frac1k\sum_{x_i\in N_k(x)}[y_i\ne c_j]=1-\frac1k\sum_{x_i\in N_k(x)}[y_i=c_i]$$

要使误分类率最小即经验风险最小，就要使 $\sum\limits_{x_i\in N_k(x)}[y_i=c_i]$ 最大，所以多数表决规则等价于经验风险最小化。

k 近邻法的实现：kd 树

实现 k 近邻法时，主要考虑的问题是如何对训练数据进行快速 k 近邻搜索。这点在特征空间的维数大及训练数据容量大时尤其必要。

k 近邻法最简单的实现方法是线性扫描(linear scan)。这时要计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。

为了提高 k 近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。具体方法有很多，下面介绍其中的 kd tree方法。

构造 kd 树

略，可以参考各种题解

平衡的 kd 树搜索时的效率未必是最优的。

搜索 kd 树

以最近邻为例加以叙述，同样的方法可以应用到 k 近邻。

给一个目标点，搜索其最近邻。首先找到包含目标点的叶节点，然后从该叶节点出发，依次退回到父结点。不断查找与目标点最临近的节点，当确定不可能存在更近的节点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高。

包含目标点的叶节点对应包含目标点的最小超矩形区域。以此叶节点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体内部。然后返回当前结点的父亲，如果父结点的另一子结点的超矩形区域与超球体相交，那么在相交区域内寻找与目标点更近的实例点。如果存在这样的点，将此点作为新的当前最近点。算法转到级的父结点，继续上述过程。

1. 在 kd 树中找出包含目标点 $x$ 的叶结点
2. 以此叶结点为当前最近点
3. 递归地向上回退，在每个结点进行以下操作：
   1. 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为当前最近点
   2. 当前最近点一定存在于该结点一个子结点对应的区域。检查子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；如果不相交，向上回退。
4. 当回退到根节点时，搜索结束。最后的“当前最近点”即为 $x$ 的最近邻点。

如果实例点是随机分布的， kd 树搜索的平均计算复杂度是 $O(\log N)$ ，这里 $N$ 是训练实例数。 kd 树更适合用于训练实例数远大于空间维数时的 $k$ 近邻搜索。当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。

理解了最近邻搜索的思路，就很容易实现 k 近邻搜索了，k近邻搜索的思路是：同样是先遍历kdtree，将遍历到的节点加入到搜索路径中，然后回溯路径；建立最大堆，在回溯路径中，将小于堆顶最大距离的节点加入堆，直到搜索路径为空。

实际实现过程中，需要注意的是，先出队列的是叶子节点，距离查找点比较近，最先加入最大堆，从而堆顶距离比较小，在最大堆不满时，进行距离判断，可能会将在k近邻范围内的节点排除掉，因此预先加入一个极大距离节点，可避免最大堆不满时，排除掉正确的节点。