Skip to content
返回搜索结果

K-Nearest Neighbors

提出者
Cover, T.M. & Hart, P.E.
年份
1967
类型
Instance-based (non-parametric) learning

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

K-Nearest Neighbors (KNN),由 Cover 和 Hart 于 1967 年正式提出,是一种非参数、基于实例的方法,它通过查看训练数据中 k 个最近的样本来对新观测进行分类或预测。对于分类,它在这些邻居中进行多数投票;对于回归,它计算这些邻居值的平均数。

方法背后的直觉

其思想很简单:相似的输入倾向于产生相似的输出。要标记一个新点,KNN 会找到特征空间中离它最近的少数几个训练样本,并让它们来决定。没有预先拟合的方程——训练数据本身就是模型,只有当新点到来时才会做出预测。

历史学

最近邻模式分类由 Thomas Cover 和 Peter Hart 在其 1967 年发表于 IEEE Transactions on Information Theory 的论文中正式确立了统计学基础,该论文分析了最近邻规则的误差率。KNN 成为最早且最持久的基于实例的学习方法之一,至今仍是标准的基线分类器。

何时使用

将 KNN 用于具有连续、二元或有序特征且至少有约 30 个观测值的表格数据进行分类或预测。它不假设任何特定的分布,但确实要求特征被归一化,并且特征数量相对于样本量保持较小(p 远小于 n 为佳)。在小样本或高维样本中,维度灾难占主导地位——邻近距离变得无信息量——此时参数模型(如逻辑回归或朴素贝叶斯)是更好的选择。

局限与注意事项

  • 对特征缩放敏感;未经标准化,大尺度特征会主导距离。
  • 在高维空间中性能迅速下降(维度灾难),邻近距离失去意义。
  • 每次预测都需要扫描整个训练集,在大数据集上预测时速度很慢。
  • 需要至少中等样本量;在小样本中,最近邻距离无意义。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 概念简单且易于解释:没有训练时方程,数据即模型。
  • 非参数——不对底层分布做任何假设。
  • 自然地处理多类问题和复杂、非线性决策边界。
  • 可用于分类和回归,基本思想相同。

应用

  • 将表格数据分类到两个或多个类别中。
  • 通过平均最近样本值进行数值预测(回归)。
  • 在尝试更复杂的模型之前,一个简单、可解释的基线。
  • 模式识别,其中与已知样本的相似性驱动决策。

使用方式

使用方式

1

对于一个新观测,KNN 会计算它与每个训练样本的距离,通常使用欧氏距离跨特征进行计算。由于距离对尺度敏感,因此必须先对特征进行标准化——否则,在较大数值尺度上测量的变量将主导计算,并扭曲哪些邻居被认为是最近的。

公式
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}
2

与新观测距离最小的 k 个训练点被选为其邻居。k 值控制着决策的局部性:小的 k 值紧密跟随数据但对噪声敏感,而较大的 k 值则平滑边界。k 值应通过交叉验证(例如,肘部法则)来选择,而不是猜测。

3

邻居决定预测:对于分类,新点采用其 k 个邻居中最常见的类别(多数投票);对于回归,它采用这些邻居值的平均数。这使得该方法易于理解,但每次预测都需要扫描训练集。

公式
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}

常见陷阱

  • 跳过特征标准化,导致一个大尺度变量悄无声息地控制了距离。
  • 手动选择 k 值,而不是通过交叉验证选择。
  • 在具有许多特征和少量观测值的样本中应用 KNN,此时维度/样本比例会破坏其性能。
  • 仅报告准确率,而不是精确率、召回率、F1 分数和混淆矩阵。

常见问题

如何选择 k 值?

k 值应通过交叉验证来选择,而不是猜测——例如,尝试一系列值并使用肘部法则找到错误停止改进的点。小的 k 值紧密跟随数据但对噪声敏感,而较大的 k 值则平滑决策边界。

为什么必须标准化特征?

KNN 使用距离来决定谁是“最近”的,而距离对尺度敏感。如果一个特征的数值尺度远大于其他特征,它就会主导距离并扭曲邻居集。需要标准化特征(例如使用 StandardScaler),以便每个特征都能公平地贡献。

为什么 KNN 在许多特征时会遇到困难?

在高维空间中,所有点都变得大致等距——维度灾难——因此“最近”的邻居不再有意义地接近。KNN 的性能迅速下降,通常更倾向于参数模型,如朴素贝叶斯或逻辑回归。保持 p 远小于 n 有所帮助。

是否存在训练步骤?

通常意义上不存在。KNN 是基于实例的(惰性的):它只是存储训练数据,并在预测时执行所有工作,此时它计算距离以找到新点的最近邻居。

相关方法

参考文献

  1. Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.

    打开 DOI 文献
    已复制。