KNN 与 K 选择

K 近邻 (KNN) 是惰性学习 (lazy learning) 的非参数算法: 训练阶段仅存储数据 (零训练开销), 预测时在训练集中找与输入最近的 $K$ 个样本——分类用多数投票, 回归用均值。常用距离加权投票提升鲁棒性: 权重 $w_i = \tfrac{1}{d(x, x_i)}$ 或 $w_i = \tfrac{1}{d(x, x_i)^2}$, 距离越近的邻居话语权越大; 决策边界由训练点的 Voronoi 区域决定。K 过小 → 高方差过拟合 (预测被 1 个近邻左右), K 过大 → 高偏差欠拟合 (混入远类样本), 常用交叉验证选 K。维度灾难: 高维下样本稀疏, 任意两点距离趋同, 相对距离 $d_{\max} - d_{\min}$ 塌缩, 近邻几乎等距、判别退化为随机, 需降维或特征选择缓解。

小样本、低维数据的分类/回归基线, 推荐与检索的召回层、可解释的在线预测; 面试常考“为什么高维下 KNN 失效”与复杂度分析。

无需训练、非参数可拟合任意决策面、天然支持增量与逐样本解释; 但把全部计算推迟到预测时——朴素预测 $O(nd)$, 低维下用 KD-Tree/Ball-Tree 可降至 $O(\log n)$ 量级, 高维则退化为线性扫描; 且对特征量纲敏感, 必须先 z-score 标准化, 否则大数值特征主导距离。

KNN 的分类与回归流程是什么? 为什么叫惰性学习? 训练阶段到底做了什么?

K 太小与太大分别造成什么误差? 如何选 K? 距离加权投票 $w_i = 1/d(x, x_i)$ 如何改进?

什么是维度灾难? 高维下为什么近邻退化 (相对距离趋同)? 有哪些缓解手段?

KNN 与 K-Means 的区别是什么? 朴素预测复杂度 $O(nd)$ 与 KD-Tree 加速后的复杂度?

为什么 KNN 对特征缩放敏感? 需要哪种预处理? 分类与回归的输出分别是什么?