【干货】KNN简明教程

2018 年 3 月 27 日 专知 Yingying

【导读】本文是Devin Soni撰写的博文，主要介绍k-近邻算法（KNN）的工作原理和常见应用。KNN可以说是机器学习算法中最普遍、最简单的分类方法了，其拥有思想简单、易于实现等优点，但是也存在若干缺点，如需要计算量大、耗费计算资源等。因此KNN适用于小样本分类任务。本文简明扼要地介绍了KNN的原理和若干要点，相信对于机器学习初学者能有帮助。

Introduction to k-Nearest-Neighbors

KNN 简介

k-最近邻（kNN）分类方法是机器学习中最简单的算法之一，并且是机器学习和分类入门的算法之一。最基本的，它是通过在训练数据中找到最相似的数据点进行分类，并根据他们的分类做出有根据的猜测。虽然KNN理解和实现起来非常简单，但是这种方法在很多领域都有广泛的应用，例如推荐系统，语义搜索和异常检测。

正如我们在其他机器学习问题中需要的那样，我们必须首先找到一种将数据点表示为特征向量的方法。特征向量是我们对数据的数学表示，并且由于我们的数据的期望特征可能不是固有数值，因此可能需要预处理和特征工程来构建这些向量。给定具有N个特征的数据，特征向量将是长度为N的向量，其中向量的入口I代表特征I的数据点值。因此，每个特征向量可以被认为是R ^ N中的点。

现在，与大多数其他分类方法不同，kNN属于惰性学习，这意味着在分类之前没有明确的训练阶段。相反，任何对数据进行概括或抽象的尝试都是在分类时进行的。虽然这确实意味着我们可以立即开始分类，但是这种类型的算法存在一些固有的问题。我们必须能够将整个训练集保存在内存中，除非我们利用某种方法对数据集进行一定的减少，并且执行分类可能在需要耗费巨大的计算量，因为算法需要通过每个分类的所有数据点进行解析。因此，kNN往往适用于特征不多的小型数据集。

一旦我们形成了我们的训练数据集，表示为M×N矩阵，其中M是数据点的数量，N是特征的数量，我们现在可以开始分类。对于每个分类，kNN方法的要点是：

计算要分类的样本与训练数据集中的每个样本之间的距离值
选取k个最近的数据点（k个最低距离的项目）
在这些数据点之间进行“多数投票” - 该样本范围中的主要类别被确定为最终分类。

在进行分类前必须确定两个超参数的值。一个是将要使用的k的值;这可以任意决定，也可以尝试交叉验证以找到最佳值。接下来也是最复杂的是将要使用的距离度量。

有很多不同的方法来计算距离，因为它是一个相当模糊的概念，并且最好的距离计算方式总是由数据集和分类任务决定。两种比较流行的是欧几里得距离和余弦相似性。

欧几里得距离最广为人知;它通过从待分类点减去训练数据点而得到向量。

另一个常用指标是余弦相似度。余弦相似性使用两个向量之间的方向差来计算量值。

选择度量标准通常会非常棘手，最好使用交叉验证来决定，除非您有一些先前的知识能清楚地了解一种肯定比另一种好。例如，对于词向量，您可能会使用余弦相似度，因为词的方向比分量值的大小更有意义。一般来说，这两种方法的运行时间所差无几，并且都会受到高维数据的影响。

在完成上述所有步骤并确定度量之后，kNN算法的结果是将R ^ N划分为多个部分的决策边界。每个部分（在下面明显着色）表示分类问题中的一个类。边界不需要与实际的训练样例一起形成 - 而是使用距离度量和可用的训练点来计算边界。通过在（小）块中取R ^ N，我们可以计算出该区域内假设数据点的最可能类别，因此我们将该块标记为该类的区域。