K-Nearest Neighbors & Metric Learning: K 的取值如何影响偏差与方差？

Core Concept: K 小 → 低偏差高方差（对噪声敏感）；K 大 → 高偏差低方差（过度平滑）。

偏差-方差随 K 的变化：① <strong>K=1（最近邻）</strong>——决策边界完全由训练数据决定，训练误差为 0（每个点预测自己），但<strong>方差极大</strong>：训练集中任一噪声点的标签改变会直接改变其邻域内所有查询点的预测；② <strong>K 增大</strong>——预测变成更大邻域的平均，平滑了噪声（降方差），但邻域跨越决策边界时会混合不同类别的样本（升偏差）；③ <strong>K=n</strong>——所有查询点预测同一个值（训练集的多数类或均值），方差为 0 但偏差最大（完全忽略输入）。<strong>最优 K</strong> 在偏差-方差权衡的谷底，由交叉验证选择。<strong>理论联系</strong>：KNN 的收敛性保证当 n→∞、K→∞、K/n→0 时，其错误率不超过贝叶斯最优错误率的 2 倍（Cover & Hart 1967），这是 KNN 的理论基石。

实践要点：① <strong>K 的选择</strong>——常用 3–10；分类取奇数避免平票；K 应随样本量增大而适当增大（保证邻域内样本足够）。② <strong>距离加权</strong>——当 K 较大时，给近邻更大权重（如 1/d 或 1/d²）可同时保留局部性与平滑性，效果常优于等权投票；这也是'局部线性'思想的雏形。③ <strong>维度与 K 的交互</strong>——高维下需更大 K 才能获得稳定的邻域统计，但距离区分度同时下降，故高维下 KNN 本质受限。④ <strong>与核方法的联系</strong>——KNN 可视为'自适应带宽的核密度估计'（带宽由第 K 近邻距离决定）；这解释了为什么它在局部密度差异大的数据上表现不均（稠密区有效邻域小、稀疏区大）。⑤ <strong>计算代价</strong>——K 增大不改变预测复杂度（仍需求全部距离），但需维护 top-K 堆。