科普君上线：k近邻算法的简单介绍！

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

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

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

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

1.计算要分类的项目与训练数据集中的每个项目之间的距离值

2.选取k个最近的数据点（k个最小距离的项目）

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

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

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

欧几里德距离可能是你最熟悉的那个，它基本上是通过从待分类点减去训练数据点而获得的矢量的大小。

欧几里德距离的一般公式

另一个常用指标是余弦相似度。与计算一个大小不同，余弦相似度代替了两个向量的方向上的不同。

余弦相似度的通用公式

选择度量标准通常会非常棘手，最好使用交叉验证来决定，除非你有一些先前的洞察力，清楚地了解了相互之间的使用。例如，对于像词向量之类的东西，你可能会想要使用余弦相似度，因为词的方向比组件值的大小更有意义。一般来说，这两种方法都会在大致相同的时间运行，并且会受到高维数据的影响。

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

这些信息是开始实施算法所需要的，而且这样做应该相对简单。当然，有许多方法可以改进这种基本算法。常见的修改包括加权和特定的预处理以减少计算和降低噪声，例如用于特征提取和降维的各种算法。 此外，kNN方法也被用于回归任务，尽管不太常见，并且通过平均来以与分类器非常相似的方式运行。但它的操作方式与分类器的平均方式非常相似。