机器学习中的 K 近邻

在这篇文章中，您将了解用于分类和回归的 K 近邻 (KNN) 算法。阅读本文后，您将了解：

• KNN 使用的模型表示。
• 如何使用 KNN 学习模型（提示：它不学习）。
• 如何使用 KNN 进行预测。
• KNN 的许多名称，包括不同领域如何称呼它。
• 如何准备数据以充分利用 KNN。
• 在哪里可以找到更多关于 KNN 算法的信息。

这篇文章是为开发人员撰写的，不假定有统计学或数学背景。重点在于算法的工作原理以及如何将其用于预测建模问题。如果您有任何问题，请留言，我将尽力回答。

通过我的新书《掌握机器学习算法》启动您的项目，其中包括所有示例的分步教程和Excel 电子表格文件。

让我们开始吧。

机器学习中的 K 近邻
图片由 Valentin Ottone 提供，保留部分权利。

KNN 模型表示

KNN 的模型表示是整个训练数据集。

就这么简单。

KNN 除了存储整个数据集外没有模型，因此不需要学习。

高效的实现可以使用复杂的树状数据结构（如 k-d 树）来存储数据，以提高预测期间新模式的查找和匹配效率。

由于存储了整个训练数据集，您可能需要仔细考虑训练数据的一致性。定期整理、在新数据可用时经常更新以及删除错误和异常数据可能是个好主意。

获取您的免费算法思维导图

方便的机器学习算法思维导图样本。

我创建了一份方便的思维导图，其中包含60多种按类型组织的算法。

下载、打印并使用它。

使用 KNN 进行预测

KNN 直接使用训练数据集进行预测。

对新实例 (x) 进行预测时，通过在整个训练集中搜索 K 个最相似的实例（邻居），并汇总这 K 个实例的输出变量来完成。对于回归，这可能是平均输出变量；对于分类，这可能是众数（或最常见）类别值。

为了确定训练数据集中 K 个实例中哪些与新输入最相似，使用距离度量。对于实值输入变量，最流行的距离度量是 欧几里得距离。

欧几里得距离计算为新点 (x) 和现有点 (xi) 在所有输入属性 j 上的平方差之和的平方根。

欧几里得距离(x, xi) = sqrt( sum( (xj – xij)^2 ) )

其他流行的距离度量包括：

• 汉明距离：计算二进制向量之间的距离（更多）。
• 曼哈顿距离：使用它们的绝对差之和计算实向量之间的距离。也称为城市街区距离（更多）。
• 闵可夫斯基距离：欧几里得距离和曼哈顿距离的推广（更多）。

还有许多其他距离度量可以使用，例如 Tanimoto、Jaccard、Mahalanobis 和 余弦距离。您可以根据数据的特性选择最佳距离度量。如果不确定，可以尝试不同的距离度量和不同的 K 值，看看哪种组合能产生最准确的模型。

如果输入变量类型相似（例如，所有都是宽度和高度），欧几里得距离是一个很好的度量。如果输入变量类型不相似（例如年龄、性别、身高等），曼哈顿距离是一个很好的度量。

K 的值可以通过算法调优找到。尝试许多不同的 K 值（例如，从 1 到 21 的值）并查看哪一个最适合您的问题是个好主意。

KNN 的计算复杂度随训练数据集的大小而增加。对于非常大的训练集，可以通过从训练数据集中抽取样本来计算 K 个最相似的实例，从而使 KNN 变为随机。

KNN 已经存在很长时间了，并且得到了很好的研究。因此，不同学科对它有不同的名称，例如：

• 基于实例的学习：使用原始训练实例进行预测。因此，KNN 通常被称为基于实例的学习或基于案例的学习（其中每个训练实例都是问题领域的一个案例）。
• 懒惰学习：不需要学习模型，所有工作都在请求预测时发生。因此，KNN 通常被称为懒惰学习算法。
• 非参数：KNN 对所解决问题的功能形式不作任何假设。因此，KNN 被称为非参数机器学习算法。

KNN 可用于回归和分类问题。

用于回归的 KNN

当 KNN 用于回归问题时，预测基于 K 个最相似实例的平均值或中位数。

用于分类的 KNN

当 KNN 用于分类时，输出可以计算为 K 个最相似实例中频率最高的类别。每个实例本质上都会为其类别投票，得票最多的类别被视为预测结果。

类别概率可以计算为在一组 K 个最相似实例中属于每个类别的新数据实例的标准化频率。例如，在二元分类问题中（类别为 0 或 1）：

p(class=0) = count(class=0) / (count(class=0)+count(class=1))

如果您正在使用 K 并且您有偶数个类别（例如 2 个），那么选择一个奇数 K 值以避免平局是一个好主意。反之，当您有奇数个类别时，使用偶数 K 值。

平局可以通过将 K 增加 1 并查看训练数据集中下一个最相似实例的类别来一致地打破。

维度灾难

KNN 在输入变量数量较少 (p) 时表现良好，但在输入变量数量非常大时会遇到困难。

每个输入变量都可以被视为 p 维输入空间的一个维度。例如，如果您有两个输入变量 x1 和 x2，则输入空间将是二维的。

随着维度的增加，输入空间的体积以指数级增长。

在高维空间中，可能相似的点之间的距离可能非常大。所有点将彼此相距遥远，我们在简单的二维和三维空间中对距离的直觉失效。这起初可能感觉不直观，但这个普遍问题被称为“维度灾难”。

最佳 KNN 数据准备

• 重新缩放数据：如果所有数据都具有相同的尺度，KNN 的性能会好得多。将数据标准化到 [0, 1] 范围是一个好主意。如果数据具有高斯分布，对其进行标准化也可能是个好主意。
• 处理缺失数据：缺失数据意味着无法计算样本之间的距离。这些样本可以被排除，或者可以估算缺失值。
• 降低维度：KNN 适用于低维数据。您可以在高维数据（数百或数千个输入变量）上尝试它，但请注意，它可能不如其他技术表现良好。KNN 可以从特征选择中受益，这可以降低输入特征空间的维度。

进一步阅读

如果您有兴趣在 Python 中从头开始实现 KNN，请查看帖子

• 在 Python 中从头开始实现 K 近邻的教程

以下是一些涵盖 KNN 算法的优秀机器学习书籍，它们从预测建模的角度进行介绍。

1. 应用预测建模，回归第 7 章，分类第 13 章。
2. 数据挖掘：实用机器学习工具和技术，第 76 和 128 页
3. 数据科学实践：来自前线的直言不讳，第 71 页
4. 机器学习，第 8 章

另请参阅维基百科上的 K 近邻。

总结

在这篇文章中，您发现了 KNN 机器学习算法。您了解到：

• KNN 存储整个训练数据集，并将其用作其表示。
• KNN 不学习任何模型。
• KNN 通过计算输入样本与每个训练实例之间的相似性来即时进行预测。
• 有许多距离度量可供选择，以匹配您的输入数据结构。
• 在使用 KNN 时，最好重新缩放您的数据，例如使用归一化。

如果您对此帖子或 KNN 算法有任何疑问，请在评论中提问，我将尽力回答。

了解机器学习算法的工作原理！

几分钟内了解算法如何工作

...只需算术和简单示例

在我的新电子书中探索如何实现
精通机器学习算法

它涵盖了**10种顶级算法**的**解释**和**示例**，例如：
_线性回归_、_k-近邻_、_支持向量机_等等...

最后，揭开
机器学习算法的神秘面纱

跳过学术理论。只看结果。

查看内容