k近邻算法（k-NN）是一种用于分类和回归的非参数、基于实例的学习方法。在两种情况下，输入都包含特征空间中距离最近的k个训练样本。输出取决于k-NN用于分类还是回归：在分类中，输出是类别成员，由k个最近邻中的多数投票决定；在回归中，输出是k个最近邻值的平均值（或加权平均值）。k-NN是一种惰性学习，函数仅在局部进行近似，所有计算都推迟到函数评估时进行。由于依赖距离计算，该算法对数据的局部结构和距离度量的选择很敏感。
该算法最初由Evelyn Fix和Joseph Hodges于1951年在美国空军航空医学学校开发，最初作为一种非参数分类技术。后来，Thomas Cover和Peter Hart于1967年对其进行了扩展和形式化，确立了其渐近误差界。此后，k-NN已成为机器学习、模式识别和数据挖掘中的基础工具，通常用作更复杂模型的基线。
工作原理
给定一个查询点，算法计算其到每个训练样本的距离（通常为欧几里得、曼哈顿或闵可夫斯基距离）。然后选择距离最小的k个训练样本。对于分类，预测标签是这k个邻居中出现频率最高的标签。对于回归，预测值是邻居目标值的平均值。k的选择至关重要：较小的k（例如1）会导致高方差和对噪声的敏感性，而较大的k可能会平滑局部模式，增加偏差。常见做法是通过交叉验证选择k，对于二分类通常使用奇数值以避免平局。
该算法还需要距离度量。欧几里得距离是连续特征的标准选择，但对于高维或分类数据，可以使用汉明距离或余弦相似度等其他度量。特征缩放（例如归一化或标准化）至关重要，因为范围较大的特征会主导距离计算。
性质与变体
k-NN是非参数的，意味着它对底层数据分布不做强假设。它也是基于实例的，存储整个训练集并在预测时直接使用。这使得训练变得简单（本质上只是存储数据），但预测计算成本高，每次查询的时间复杂度为O(nd)，其中n是训练样本数，d是特征数。
几种变体解决了这些局限性。加权k-NN赋予更近的邻居更高影响力，通常使用逆距离权重。局部加权回归在邻域内拟合线性模型。对于大型数据集，近似最近邻搜索技术（如k-d树、球树或局部敏感哈希）可降低搜索成本。在高维空间中，维度灾难会降低性能，因为距离变得不那么有区分度；通常应用降维或特征选择。
应用
该算法广泛应用于计算机视觉中的图像分类、自然语言处理中的文本分类以及生物信息学中的基因表达分析等领域。它出现在推荐系统中，用于寻找具有相似偏好的用户或物品。在金融领域，它用于信用评分和欺诈检测。其简单性和可解释性使其成为探索性分析和作为更复杂模型（如神经网络）基准的常见首选。
优势与局限
k-NN的主要优势在于其简单性、易于实现以及在低至中等维度的小型到中型数据集上的有效性。它不需要训练阶段，适合增量学习。然而，其局限性包括高内存使用（存储所有训练数据）、预测时间慢、对不相关特征和噪声敏感，以及在高维空间中性能不佳。它还假设所有特征同等重要，这在实践中很少成立。
与其他方法的关系
k-NN常与决策树和支持向量机等其他非参数方法进行比较。它是机器学习中的基础技术，经常与人工智能课程一起教授。其原理支撑了更高级的方法，如生成合成邻居的数据增强技术，并用于课程学习中，按难度对训练样本进行排序。在现代实践中，k-NN有时用作深度学习模型中度量学习的最后一层，其中学习到的嵌入通过最近邻搜索进行比较。
参见
参考文献
- Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
- Fix, E., & Hodges, J. L. (1951). Discriminatory analysis, nonparametric discrimination: consistency properties. USAF School of Aviation Medicine.
- Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician.