5分钟学习KNN 算法

什么是KNN？下文作者会介绍它的工作原理，以及它的重要应用。

KNN（k-Nearest-Neighbors）方法是Machine learning中最简单的方法之一，也是介绍ML和分类的一种很好的方法之一。在最基本的层次上，它是通过在训练数据中找到最相似的数据点来分类，并根据它们的分类作出有根据的猜测。该方法虽然理解和实现起来非常简单，但是这种方法在很多领域有广泛的应用，比如推荐系统、语义搜索和异常检测。

在任何机器学习问题中，我们都需要首先找到一种将数据点表示为特征向量的方法。特征向量是我们数据的数学表示，并且由于我们数据的期望特性可能不是固有的数值，因此可能需要预处理和特征工程来创建这些向量。给定具有N个唯一特征的数据，特征向量将是长度为N的向量，其中向量的条目I表示该数据点对于特征I的值，因此，每个特征向量可以被认为是R ^ N中的点。

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

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

l计算待分类项与训练数据集中的每个项之间的距离值

l选择k个最接近的数据点(距离最小的项目)

l在这些数据点之间进行“多数投票”—该池中的主要分类被确定为最终分类

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

欧几里得距离可能广为人知的；它本质上是通过从要分类的点减去训练数据点而获得的矢量的幅度。

一般公式另一个常见指标是余弦相似性。余弦相似性不是计算幅度，而是使用两个向量之间的方向差来计算量值。

余弦相似性的一般公式

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

在执行上述所有操作并确定度量之后，kNN算法的结果是将R ^ N划分为多个部分的决策边界。每个部分(下面清楚地着色)表示分类问题中的一个类。边界不需要通过实际训练示例形成，而是使用距离度量和可用训练点来计算。通过在(小)块中取R N，我们可以计算该区域中假设数据点的最可能类别，因此我们将该块着色为该类的区域。

这是开始实现算法所需的全部信息，这样做应该相对简单。当然，有许多方法可以改进这个基本算法。常见的修改包括加权、特定的预处理，以减少计算和减少噪声，例如各种算法的特征提取和减少尺寸。

此外，kNN方法也已经被用于回归任务，虽然不太常见，但它的操作方式和分类器十分相似。