K-最近邻算法（k-NN）是一种非参数监督学习算法，用于分类和回归。在分类中，新数据点被分配为其在特征空间中距离最近的k个邻居中最常见的类别，该距离通过某种距离度量来确定。在回归中，输出是这些邻居值的平均值（或加权平均值）。该算法是基于实例的，意味着它存储整个训练数据集，并且仅在需要进行预测时才执行计算，将所有泛化工作推迟到查询时进行。
该方法由Evelyn Fix和Joseph Hodges于1951年首次提出，后由Thomas Cover扩展。它是最简单的机器学习算法之一，但在许多领域都能达到有竞争力的准确度，尤其是在决策边界不规则的情况下。其性能在很大程度上取决于k值的选择、距离度量以及特征缩放。
历史发展
k-NN的起源可以追溯到1951年，当时在美国空军航空医学院工作的Evelyn Fix和Joseph Hodges提出了一种基于最近邻的非参数分类方法。他们的研究动机是在不假设特定统计分布的情况下对观测数据进行分类。1967年，Thomas Cover和Peter Hart发表了一篇具有里程碑意义的论文，正式阐述了该算法的性质，包括其相对于贝叶斯最优分类器的错误率界限。这使k-NN在模式识别领域确立了理论基础。随着20世纪60年代和70年代计算能力的提升，该算法逐渐流行，因为它训练时间短，但需要大量存储空间。后续发展，如引入加权投票和距离度量学习，解决了其部分局限性。
算法概述
在k-NN分类中，输入是一个带标签的训练样本集，每个样本用多维特征向量表示。算法存储这些向量及其标签。当出现一个查询点时，算法计算该查询点与所有训练点之间的距离，选出最近的k个点，并在这k个点中分配出现频率最高的类别。当k=1时，查询点直接被分配为其最近邻居的类别。k值的选择至关重要：k值过小会导致高方差和对噪声敏感，而k值过大则可能使决策边界过于平滑，从而包含其他类别的点。
对于回归，输出是k个最近邻居的目标值的平均值。这被称为最近邻平滑。如果k=1，则预测值就是最近邻点的值，这被称为最近邻插值。加权变体赋予距离更近的邻居更高的权重，通常使用与距离成反比的权重（如1/d）。
距离度量与特征缩放
距离度量的选择至关重要。对于连续特征，欧几里得距离最为常用。对于离散特征，如在文本分类中，则使用汉明距离或重叠度量。在基因表达分析等专业领域，也使用了相关系数（如皮尔逊相关系数、斯皮尔曼相关系数）。由于算法依赖距离，不同单位或尺度的特征可能会主导计算结果。因此，将每个特征归一化到统一尺度（如z-score归一化或最小-最大缩放）对于确保各特征贡献均衡至关重要。这一预处理步骤能显著提高准确度。
统计性质
从统计角度看，k-NN是一种非参数方法，因为它不对潜在的数据分布做任何函数形式的假设。训练数据被视为成对样本(X_i, Y_i)，其中X_i是特征向量，Y_i是类别标签。对于给定的查询点x，训练点按与其距离的远近重新排序。随着样本量n的增加，如果k也随之适当增长且k/n趋近于0，算法的错误率会收敛于贝叶斯错误率。这一性质由Cover和Hart确立，使得k-NN具有渐近最优性。然而，在有限样本情况下，该算法会遭遇维度灾难：随着特征数量增加，空间体积呈指数增长，数据点变得稀疏，使得距离度量不再有效。
优点与缺点
k-NN的主要优点是简单且无需训练阶段。它可以轻松地通过添加新的数据点进行更新。它也能有效处理多类别问题，并能捕捉复杂的决策边界。然而，它也有明显的缺点。预测时，它需要计算查询点与所有训练点之间的距离，速度较慢，对于大型数据集，若不使用优化方法（如KD树或球树）则难以应用。它对不相关的特征和噪声数据敏感。此外，算法对数据的局部结构敏感，异常值或类别分布不平衡可能会扭曲结果。在类别不平衡的情况下，多数类会因其在k个邻居中更常见而占据主导。通过使用距离反比加权或采用抽象技术可以缓解这些问题。
变体与扩展
针对k-NN的局限性，出现了多种变体。加权k-NN根据距离对邻居赋予不同权重，距离越近的邻居影响力越大。距离度量学习方法（如大间隔最近邻和邻域成分分析）旨在学习一个定制的距离度量以提高准确度。编辑k-NN通过移除噪声或错误分类的训练点来改进泛化能力。压缩k-NN通过仅保留对分类至关重要的点来减小训练集规模。局部自适应k-NN根据查询点周围区域的密度来调整k值。这些变体已在机器学习和人工智能等领域得到应用，以提升性能。
应用
k-NN算法应用于多个领域。在模式识别中，它被用于图像分类和手写识别。在医学中，它根据患者特征进行诊断。在金融领域，它用于信用评分和欺诈检测。在推荐系统中，它通过寻找相似用户或物品来提供推荐。在生物信息学中，它用于基因表达数据分类。由于其简单性，它常被用作比较更复杂模型（如神经网络和深度学习）的基准。
与其他方法的关系
k-NN是一种基于实例的学习方法，与构建显式模型的神经网络或支持向量机等方法不同。它与非参数密度估计密切相关。在更广泛的机器学习背景下，k-NN常被用作基准方法。它也对局部敏感哈希和近似最近邻搜索等领域的发展产生了影响，这些技术用于大规模系统。尽管现代方法（如深度学习）在许多任务上已超越k-NN，但k-NN在处理小数据集和需要可解释预测的场景中仍有其价值。
实践注意事项
实现k-NN时，需要注意几个实际问题。k值通常通过交叉验证来选择。在二分类问题中，通常选择奇数k值以避免平局。特征缩放是必要的。KD树等高效数据结构可以加速最近邻搜索，但在高维空间中性能会下降。对于非常大的数据集，需要使用近似方法。算法的内存占用与训练集大小成正比，这可能是一个限制。在现代应用中，k-NN有时会与其他算法结合使用，例如，在从神经网络提取的嵌入表示之上作为最终分类器。