k-Nearest Neighbors(k近邻算法)

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1454167

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

k-Nearst Neighbors(k近邻算法

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

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

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

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