分类目录：《深入理解机器学习》总目录
k近邻（k-Nearest Neighbor，kNN）算法是一种常用的有监督学习算法，可以完成分类与回归的任务，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的 k k k个训练样本，然后基于这 k k k个“邻居”的信息来进行预测。通常，在分类任务中可使用“投票法”，即选择这 k k k个样本中出现最多的类别标记作为预测结果；在回归任务中可使用“平均法”，即将这 k k k个样本的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。 k k k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。
与前面介绍的学习方法相比，k近邻学习有一个明显的不同之处：它似乎没有显式的训练过程。事实上，它是“懒惰学习”（lazy learning）的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理；相应的，那些在训练阶段就对样本进行学习处理的方法，称为“急切学习”（eager learning）.。
上给出了k近邻分类器的一个示意图。显然， k k k是一个超参数，当 k k k取不同值时，分类结果会有显著不同。另一方面，若采用不同的距离计算方式，则找出的“近邻”可能有显著差别，从而也会导致分类结果有显著不同。暂且假设距离计算是“恰当”的，即能够恰当地找出 k k k个近邻，我们来对“最近邻分类器”（1NN，即k k k k=1）在二分类问题上的性能做一个简单的讨论。
给定测试样本 x x x，若其最近邻样本为 y y y，则最近邻分类器出错的概率就是 x x x与 y y y类别标记不同的概率，即：
p ( err ) = ∑ c ∈ Y p ( c ∣ x ) p ( c ∣ y ) p(\text{err})=\sum_{c\in Y}p(c|x)p(c|y) p(err)=c∈Y∑p(c∣x)p(c∣y)
假设样本独立同分布，且对任意 x x x和任意小正数 δ \delta δ，在 x x x附近 δ \delta δ距离范围内总能找到一个训练样本；换言之，对任意测试样本，总能在任意近的范围内找到上式中的训练样本 y y y.令 c ∗ = arg max c ∈ Y p ( c ∣ x ) c^*=\argmax_{c\in Y}{p(c|x)} c∗=argmaxc∈Yp(c∣x)表示贝叶斯最优分类器的结果，有：
p ( err ) ≤ 2 × ( 1 − p ( c ∗ ∣ x ) ) p(\text{err})\leq 2\times(1-p(c^*|x)) p(err)≤2×(1−p(c∗∣x))
即最近邻分类器虽简单，但它的泛化错误率不超过贝叶斯最优分类器的错误率的两倍。
