k-Nearest Neighbors(k近邻算法)

内容总结自花书《deep learning》Chapter5，由英文版翻译而来，英文版可以在其官网免费查阅。同时博主也发明中文翻译版的诸多错误和不细致的地方，建议阅读英文版。

k-Nearst Neighbors(k近邻算法)

近邻回归算法(nearest neighbor regression)模型简单地存储来自训练集的$X\text{X}X$和$y\text{y}y$，当被要求分类一个测试点时，模型查询训练集中与该点最近的项并且返回相关的目标(即label)。换句话说，$\hat{y}=y_i$当$i=argmin||X_{i,:}-x\text{Xi,:−x}{X}_{i,:}-x|{|}_2^2$。算法也可以泛化到使用除$L^2$范数之外其他距离度量。如果该算法被允许通过平均$X_{i;:}$ 中所有邻近的向量对应的$y_i$来打破必须是最近的关联，那么该算法会在任意回归数据集上达到最小的可能的训练误差(如果存在两个相同的输入对应不同的输出，训练误差有可能会大于0）。

更一般的，k-nearest neighbors是一类可以被应用于分类或者回归的技术。作为一个非参数学习算法，k-nearest neighbors不受限于固定数量的参数。我们通常认为k-nearest neighbors算法没有任何参数，而是实现了一个训练数据的简单函数。事实上，甚至不需要一个训练阶段或者学习过程。取而代之的是，在测试时，当我们需要为一个新的测试输入$x\text{x}x$产生一个输出$y$时，我们在训练集中找到k个与$x\text{x}x$最近的邻居，返回它们对应的$k$个$y$的平均值。这基本上对任何种类的能在$y$值上取平均的监督算法都有效。

作为一个非参数学习算法，k-nearest neighbors能够实现非常高的容量(capacity)。例如，我们有一个多分类任务，使用0-1损失函数来衡量性能。在这样的设定下，1-nearest neighbor在训练样本接近无穷大时收敛到2倍贝叶斯误差。多出来的贝叶斯误差来自随机在两个距离相同的邻居里选一个。当有无穷多训练数据时，所有测试点$x\text{x}x$都会有无穷多邻接距离为0。如果算法被允许在这些邻居上投票，而不是随机选择一个，则该过程会收敛到贝叶斯误差率。k-nearest neighbors的高容量使我们在给定一个大型训练集能够取得高准确度。它以高计算量实现这点，然而，给定一个小的有限的数据集，它会泛化得很差。

k-nearest neighbors的一个缺点是它不能学习到一个特征比另一个特征更有判别性。