K近邻算法入门

2018 年 3 月 18 日 论智 Devin Soni

来源：Devin Soni

编译：weakish

编者按：Towards Data Science博主Devin Soni简明扼要地介绍了kNN是什么，kNN的应用，以及kNN是如何工作的。

K近邻（k-Nearest-Neighbors，kNN）分类方法是最简单的机器学习方法之一，也是引导你入门机器学习和分类问题的一个非常好的方式。在最基本的层面，kNN本质上是通过在训练数据中寻找最相似的数据点进行分类，并基于分类做出有根据的推测（educated guess）。尽管非常易于理解和实现，这一方法在许多领域中得到了广泛应用，例如推荐系统（recommendation system）、语义搜索（semantic searching）、异常检测（anomaly detection）。

和其他机器学习问题一样，我们必须找到将数据点表示为特征向量（feature vector）的方式。特征向量是数据的数学表示，由于数据所需的特性的内在形式可能并非是数值，在创建这些向量前，可能需要进行预处理和特征工程。给定具有N个不同特征的数据，特征向量将是维度为N的向量，其中向量的I条目表示数据点对应特征I的值。因此，每个特征向量可以看成是R^N中的点。

和其他大多数分类方法不同，kNN属于惰性学习（lazy learning），这意味着在分类之前没有显式的训练阶段。相反，任何概括或抽象数据的尝试是在分类中做出的。尽管这确实意味着一旦我们有了数据，就可以立刻开始分类，这种算法有一些固有的问题。我们必须能够将整个训练集保存在内存中，除非我们对数据集应用了某种降维方法，进行分类可能在算力上非常昂贵，因为算法需要为每次分类解析所有数据点。基于这些原因，一般而言，kNN在并不具备很多特征的较小的数据集上效果最好。

一旦我们加工好了训练数据集（表示为一个M x N矩阵，其中M为数据点的数目，而N为特征数目），我们就可以开始分类了。kNN方法的精髓是，为每个分类查询：

计算将要分类的项目和训练集中所有其他项目的距离
选择k个最接近的数据点（距离最近的k个数据点）
在这些数据点间进行一次“多数投票（majority vote）”——占统治地位的分类成为最终分类。

在进行分类前，必须做出两个重要的决定。一个是即将使用的k值；它可能是任意决定的，也可能是通过交叉验证（cross-validation）找到的最优值。另一个，也是最复杂的决定，是即将使用的距离测度（distance metric）。

距离是一个相当含糊的概念，因此存在很多不同的计算距离的方法。适当的测度总是由数据集和分类任务决定。不过，比较流行的两个测度是欧几里得距离（Euclidean distance）和余弦相似度（Cosine similarity）。

欧几里得距离大概是你最熟悉的测度；基本上，从要分类的点中减去训练数据点，得到一个向量，其长度就是欧几里得距离。

另一个常用的测度是余弦相似度。余弦相似度计算两个向量的方向间的差异。

选择测度经常很棘手，也许最好的办法是直接通过交叉验证决定测度，除非你具有某种先验洞见，能够清晰地揭示一种测度比另一种测度更好。例如，对于单词向量，你可能想要使用余弦相似度，因为单词的方向比组成部分值的长度要有意义得多。一般而言，这两个方法的运行时间差不多，也都不擅长处理高维数据。

进行所有上述步骤，决定测度之后，kNN算法的结果是一个分区R^N的判定边界。每个分区（在下图中使用不同颜色表示）表示分类问题中的一个分类。边界不一定需要由实际的训练样本构成——它们其实是通过距离测度和现有训练点计算出来的。将R^N切分为小块之后，我们可以计算该区域内的假想数据点最有可能的分类，从而根据分类区域给小块上色。

这些就是开始实现这一算法需要知道的所有信息了，实现kNN相对而言比较简单。当然，有很多改善这一基本算法的方式。常见的修正包括加权，以及降低运算量和噪声的特定预处理方法，比如多种特征提取和降维算法。此外，kNN也被用于回归任务（不过这一用法不那么常见），用于回归任务的kNN的做法和基于平均的分类器非常相似。

原文地址：https://towardsdatascience.com/introduction-to-k-nearest-neighbors-3b534bb11d26