K近邻算法 · aiwiki.page

K近邻算法（k-NN）是机器学习中用于分类和回归的一种监督学习方法。它从训练数据中找出与待预测样本最相似的 $k$ 个样例，并综合这些样例的结果来预测未知结果。分类通常采用投票方式，回归则采用平均值。这是一种非参数方法：它不预先限定输入与输出之间关系的函数形式。(scikit-learn.org)

预测规则

假设训练集包含 $n$ 对数据 $(x_i,y_i)$ ，其中 $x_i$ 为特征向量， $y_i$ 为类别标签或数值型目标。对于待预测样本 $x$ ，距离函数确定一个邻域 $N_k(x)$ ，其中包含距离它最近的 $k$ 个训练样例的索引。正整数 $k$ 通常不大于 $n$ ，是一个超参数。(arxiv.org)

对于分类任务，预测类别为

\hat y(x)=\arg\max_c\sum_{i\in N_k(x)}\mathbf 1(y_i=c),

其中，当样例 $i$ 属于类别 $c$ 时，示性函数的值为 1。因此，得票最多的类别胜出，不必获得超过半数的票。对于回归任务，

\hat y(x)=\frac{1}{k}\sum_{i\in N_k(x)}y_i.

加权变体不再让所有样例贡献相同，而是赋予它们不同的权重；常见做法是采用距离倒数加权，使较近的样例具有更大的影响。(scikit-learn.org)

当 $k=1$ 时，预测结果直接取自最近样例的结果。类别票数相同，或邻域边界处出现距离相同的样例时，需要按约定规则处理；在某些实现中，调整这些并列训练样例的顺序可能产生不同的结果。(scikit-learn.org)

距离与特征表示

“最近”的含义取决于如何表示和比较观测数据。对于数值向量，欧几里得距离是一种常见选择：

d(x,z)=\sqrt{\sum_{j=1}^{p}(x_j-z_j)^2}.

其他选择包括曼哈顿距离、闵可夫斯基距离，以及针对具体任务定义的相异度。同一数据集在不同度量下可能选出不同的近邻，因此距离函数是预测模型定义的一部分，而不只是实现细节。(arxiv.org)

特征缩放会显著影响基于距离的预测。数值范围较大的变量可能压倒数值范围较小的变量，而不论两者对预测的实际重要性如何。标准化将特征重新缩放，使其均值为零、标准差为一；这可能大幅改变近邻结构和分类边界。但这并不意味着每个特征都包含同等有用的信息。(scikit-learn.org)

类别变量需要合适的表示方式或比较规则。独热编码能够表示无序类别，而不会人为赋予它们数值上的等级，不过它会增加坐标维数。这些选择属于特征工程，决定了算法能够识别哪些相似关系。(sklearn.org)

选择 k 与评估性能

邻域大小控制着一种平滑程度。较小的邻域对个别观测值及噪声更为敏感，因此更容易出现过拟合。较大的邻域通常会产生更平滑的预测，但可能掩盖局部差异，导致欠拟合。这体现了偏差-方差权衡：增大 $k$ 通常会降低预测的变异性，同时增加近似偏差。没有一个取值对所有数据集都最优。(arxiv.org)

可以通过交叉验证或单独的验证集，评估 $k$ 、距离度量和加权规则的选择。在模型选择完成后，使用留出的测试集对泛化（机器学习）能力进行最终评估。评估指标取决于任务：分类和回归需要不同的指标，其中均方误差是常见的回归评估指标之一。(scikit-learn.org)

预处理也必须遵守数据评估时的划分边界。缩放、需要从数据中学习的变换，以及特征选择，都应只在每次划分的训练部分上拟合，再原样应用于留出部分。在整个数据集上拟合这些操作，可能引入数据泄漏（机器学习），使性能评估过于乐观。流水线提供了一种机制，可以确保预处理始终在每次交叉验证划分内部进行。(scikit-learn.org)

计算与维度

K近邻算法常被称为惰性学习或基于实例的学习，因为它的大部分工作发生在预测阶段，而非拟合阶段。存储的样例始终是预测器的核心，不过拟合时也可能构建搜索索引。直接搜索需要计算查询样本到全部 $n$ 个样例的距离；对于 $p$ 维稠密向量，每次查询所需的距离计算工作量约为 $O(np)$ 。(arxiv.org)

对于适合的数据，KD树和球树可以加速精确近邻搜索。它们的效率取决于维度和数据结构；在高维空间中，基于树的方法可能失去优势。这是维度灾难在计算层面的表现之一，维度灾难也使局部邻域更难被样本密集覆盖。(scikit-learn.org)

降维可以降低搜索成本，并改变邻域的质量。例如，主成分分析将观测数据投影到更少的坐标维度中，但保留下来的变异未必对应与预测相关的信息。特征缩放既会影响这一投影，也会影响随后的近邻搜索。(scikit-learn.org)

统计学基础

托马斯·科弗与彼得·哈特于 1967 年发表的论文《最近邻模式分类》（Nearest Neighbor Pattern Classification）确立了一项奠基性的大样本结果。在该论文规定的分布条件下，单近邻分类器的极限错误率不超过贝叶斯错误率的两倍；贝叶斯错误率是在给定底层概率分布的情况下所能达到的最低分类错误率。这是一个渐近界，并非对每个有限数据集的保证，也不意味着固定采用 $k=1$ 就能达到贝叶斯错误率。该分析还解释了为什么在增加近邻数量的同时，必须兼顾邻域相对于样本规模的局部性。(isl.stanford.edu)