什么是 kNN？

kNN，或 k 近邻算法，是一种机器学习算法，它使用邻近度来比较一个数据点与一组它所训练并记忆的数据，从而做出预测。 这种基于实例的学习使 kNN 具有“惰性学习”的称号，并使该算法能够执行分类或回归问题。kNN 的工作原理是假设相似的点可以在彼此附近找到——物以类聚。

作为一种分类算法，kNN 将新的数据点分配到其邻居中的多数集合。作为一种回归算法，kNN 基于最接近查询点的值的平均值进行预测。

kNN 是一种监督学习算法，“k”表示分类或回归问题中考虑的最近邻居的数量，“NN”表示为 k 选择的数字的最近邻居。

kNN 最早由 Evelyn Fix 和 Joseph Hodges 于 1951 年在为美国军方进行的研究中开发¹。他们发表了一篇解释判别分析的论文，判别分析是一种非参数分类方法。1967 年，Thomas Cover 和 Peter Hart 扩展了非参数分类方法，并发表了他们的论文“最近邻模式分类”²。近 20 年后，James Keller 对该算法进行了改进，他开发了一种产生较低错误率的“模糊 KNN”³。

如今，kNN 算法由于其对大多数领域的适应性而成为使用最广泛的算法，从遗传学到金融和客户服务。

kNN 算法作为监督学习算法工作，这意味着它被馈送它记忆的训练数据集。它依靠此标记的输入数据来学习一个函数，该函数在给定新的未标记数据时产生适当的输出。

这使该算法能够解决分类或回归问题。虽然 kNN 的计算发生在查询期间而不是训练阶段，但它具有重要的数据存储要求，因此严重依赖内存。

对于分类问题，KNN 算法将根据多数分配类标签，这意味着它将使用给定数据点周围最频繁出现的标签。换句话说，分类问题的输出是最近邻居的众数。

一个区别：多数投票与多元投票

多数投票表示任何超过 50% 的都为多数。如果考虑两个类标签，则适用。但是，如果要考虑多个类标签，则适用多元投票。在这些情况下，任何超过 33.3% 的都足以表示多数，从而提供预测。因此，多元投票是定义 kNN 众数的更准确的术语。

如果我们用图示来说明这种区别

二元预测

Y: 🎉🎉🎉❤️❤️❤️❤️❤️

多数投票：❤️

多元投票：❤️

多类设置

Y: ⏰⏰⏰💰💰💰🏠🏠🏠🏠

多数投票：无

多元投票：🏠

回归问题使用最近邻居的均值来预测分类。回归问题将产生实数作为查询输出。

例如，如果您要制作一个图表来根据身高预测某人的体重，则表示身高的值将是独立的，而体重的值将是相关的。通过执行平均身高体重比的计算，您可以根据一个人的身高（自变量）来估计他们的体重（因变量）。

kNN算法的关键是确定查询点与其他数据点之间的距离。确定距离度量可以实现决策边界。这些边界创建不同的数据点区域。计算距离有不同的方法。

• 欧几里得距离是最常见的距离度量，它测量查询点和被测量的其他点之间的直线距离。
• 曼哈顿距离也是一种常用的距离度量，它测量两个点之间的绝对值之和。它在网格上表示，通常被称为出租车几何——你如何从A点（你的查询点）到B点（被测量的点）？
• 闵可夫斯基距离是欧几里得距离和曼哈顿距离度量的概括，它可以创建其他距离度量。它是在赋范向量空间中计算的。在闵可夫斯基距离中，p是定义计算中使用的距离类型的参数。如果p=1，则使用曼哈顿距离。如果p=2，则使用欧几里得距离。
• 汉明距离，也称为重叠度量，是一种与布尔或字符串向量一起使用的技术，用于识别向量不匹配的位置。换句话说，它测量两个等长字符串之间的距离。它对于错误检测和纠错码特别有用。

要选择最佳的k值（即考虑的最近邻居的数量），你必须尝试几个值，以找到产生最准确的预测且错误最少的k值。确定最佳值是一项平衡的工作。

• 较低的k值使预测不稳定。
  举个例子：一个查询点被2个绿点和一个红色三角形包围。如果k=1，并且恰好最接近查询点的点是其中一个绿点，则算法将错误地预测一个绿点作为查询的结果。较低的k值具有高方差（模型过于紧密地拟合训练数据）、高复杂性和低偏差（模型足够复杂以很好地拟合训练数据）。
• 较高的k值会产生噪声。
  较高的k值将提高预测的准确性，因为有更多的数字可以计算众数或均值。但是，如果k值太高，则很可能会导致低方差、低复杂性和高偏差（模型不够复杂以很好地拟合训练数据）。

理想情况下，你希望找到一个介于高方差和高偏差之间的k值。还建议为k选择一个奇数，以避免在分类分析中出现平局。

正确的k值也与你的数据集有关。要选择该值，你可以尝试找到N的平方根，其中N是训练数据集中的数据点数。交叉验证策略也可以帮助你选择最适合你的数据集的k值。

kNN算法通常被描述为“最简单”的监督学习算法，这带来了它的几个优点

• 简单：kNN易于实现，因为它简单且准确。因此，它通常是数据科学家学习的第一个分类器之一。
• 适应性强：一旦将新的训练样本添加到其数据集中，kNN算法就会调整其预测以包括新的训练数据。
• 易于编程：kNN仅需要几个超参数——一个k值和一个距离度量。这使得它成为一个相当简单的算法。

此外，kNN算法不需要训练时间，因为它存储训练数据，并且其计算能力仅在进行预测时使用。

虽然kNN算法很简单，但它也有一系列的挑战和局限性，部分原因是它的简单性

• 难以扩展：由于kNN占用大量内存和数据存储，因此增加了与存储相关的费用。这种对内存的依赖还意味着该算法是计算密集型的，这反过来又是资源密集型的。
• 维度灾难：这是计算机科学中出现的一种现象，其中一组固定的训练示例受到维度数量增加以及这些维度中特征值固有增加的挑战。换句话说，模型的训练数据无法跟上超空间不断演变的维度。这意味着预测变得不那么准确，因为查询点和相似点之间的距离在其他维度上会变得更宽。
• 过拟合：如前所示，k的值会影响算法的行为。当k的值太低时，尤其会发生这种情况。较低的k值可能会使数据过拟合，而较高的k值会“平滑”预测值，因为该算法会在更大的区域上平均值。

kNN算法以其简单性和准确性而闻名，具有多种应用，尤其是在用于分类分析时。

• 相关性排名：kNN使用自然语言处理 (NLP) 算法来确定哪些结果与查询最相关。
• 图像或视频的相似性搜索：图像相似性搜索使用自然语言描述来查找与文本查询匹配的图像。

• 模式识别：kNN可用于识别文本或数字分类中的模式。
• 金融：在金融领域，kNN可用于股票市场预测、汇率等。
• 产品推荐和推荐引擎：想想 Netflix！“如果你喜欢这个，我们认为你也会喜欢……”任何使用该句子（无论是公开还是不公开）的网站都可能正在使用 kNN 算法为其推荐引擎提供支持。
• 医疗保健：在医学和医学研究领域，kNN算法可用于遗传学，以计算某些基因表达的概率。这使医生能够预测患癌症、心脏病发作或任何其他遗传性疾病的可能性。
• 数据预处理：kNN算法可用于估计数据集中缺失的值。

Elasticsearch 使你能够实现 kNN 搜索。支持两种方法：近似 kNN 和精确的暴力 kNN。你可以在相似性搜索、基于 NLP 算法的相关性排名以及产品推荐和推荐引擎的上下文中使用 kNN 搜索。

使用 Elastic 实现 kNN 搜索

• 深入了解 kNN 搜索
• aNN 与 kNN
• 了解近似最近邻算法
• 了解 AI 搜索算法

kNN 代表 k 最近邻算法，其中 k 表示在分析中考虑的最近邻居的数量。