1. KNN概述

k近邻法（K-Nearest neighbor，kNN）是一种常用的监督学习方法，其工作机制为：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。通常，在分类任务中使用投票法计算最终预测结果，在回归任务中使用平均法，还可基于距离远近进行加权平均或加权投票。

kNN是懒惰学习（lazy learning）的典型代表，不具有显式的学习过程。懒惰学习技术在训练阶段仅仅将样本保存起来，训练开销为0，等收到测试样本时再进行处理，相应的，那些在训练阶段就怼样本进行学习处理的方法，称为“急切学习（eager learning）”。

2. K近邻模型三要素

kNN使用的模型实际上对应于对特征空间的划分。kNN模型由三个及基本要素组成：

距离度量；
k值的选择；
决策规则。

2.1 距离度量

kNN中使用的距离度量可以是欧式距离、曼哈顿距离、切比雪夫距离或者一般的闵可夫斯基距离。具体定义可参见上一篇博客【机器学习】LP距离、欧氏距离、曼哈顿距离、切比雪夫距离。

2.2 k值选择

如果k值较小，则训练误差减少，只有与输入实例相似的训练实例才会对于预测结果起作用，但泛化误差提高了，预测结果会对近邻实例点非常敏感。k值较小意味着模型变得复杂，容易发生过拟合。

如果k值较大，可以减少泛化误差，但训练误差会增加，这时与输入实例相差较远的训练实例也会对预测结果起作用。k值较大意味着模型变得简单，容易发生欠拟合。

当 $k=1$ 时，k近邻算法就是最近邻算法。k值一般采用交叉验证法选取最优值。

2.3 决策规则

通常，在分类任务中使用投票法计算最终预测结果，在回归任务中使用平均法，还可基于距离远近进行加权平均或加权投票。

3. KNN算法描述

下面以分类任务为例，介绍KNN算法，回归任务与此类似，区别不大。

输入：训练数据集 $D = \\left\\{ \\left( x _ { i } , y _ { i } \\right) \\right\\} _ { i = 1 } ^ { m }$ ，其中， $x _ { i } \\in \\mathcal { X } \\subseteq \\mathbf { R } ^ { n }$ ， $y _ { i } \\in \\mathcal { Y } = \\left\\{ c _ { 1 } , c _ { 2 } , \\cdots , c _ { K } \\right\\}$ 是实例的类别。
过程：
（1）根据给定的距离度量，在训练集 $D$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖着 $k$ 个点的领域记为 $N _ { k } ( x )$ ；

（2）在 $N _ { k } ( x )$ 中根据分类决策规则决定 $x$ 的类别 $y$ ：
$y = \\arg \\max _ { c _ { j } } \\sum _ { x _ { i } \\in N _ { k } ( x ) } I \\left( y _ { i } = c _ { j } \\right) , \\quad i = 1,2 , \\cdots , N ; \\quad j = 1,2 , \\cdots , K$
输出：测试样本 $x$ 所属的类别 $y$ 。