K-Nearest Neighbors & Metric Learning: 描述 KNN 的算法流程与复杂度。

Core Concept: 找最近 k 个邻居投票；预测 O(nd)（暴力）或 O(d log n)（KD 树/近似索引），训练 O(1)。

KNN 是<strong>懒惰学习（lazy learning）</strong>的典型：没有显式训练阶段（训练复杂度 O(1)，只是存储数据），所有计算推迟到预测时。预测流程：计算查询点到所有训练样本的距离（O(nd)），取最近的 k 个，分类用多数投票（或距离加权投票），回归取均值。<strong>加速结构</strong>：① <strong>KD 树</strong>——按维度轮流划分空间，平均查询 O(log n)，但<strong>维度升高时退化为线性扫描</strong>（因为高维空间中几乎每个点都需要访问，剪枝失效）；② <strong>球树（Ball Tree）</strong>——用超球体划分，在高维下比 KD 树稍好；③ <strong>近似最近邻（ANN）</strong>——HNSW/IVF-PQ，牺牲少量精度换大幅加速，是工业级大规模检索的标准（见 M7）。

实践要点：① <strong>维度灾难</strong>——KNN 的核心弱点。高维下'最近邻'与'最远邻'的距离趋于相同（距离集中现象），使'最近'失去区分度；理论上前提是样本量需随维度指数增长。缓解手段：降维（PCA/UMAP）、度量学习（学一个任务相关的距离）、或改用树/线性模型。② <strong>K 的选择</strong>——K 小 → 低偏差高方差（对噪声敏感、决策边界复杂）；K 大 → 高偏差低方差（过度平滑）；通常用交叉验证选 K（分类取奇数避免平票）。③ <strong>距离加权</strong>——给近邻更大权重（如 1/d）可改善效果，尤其当 K 较大时。④ <strong>特征缩放是必须的</strong>——距离对量纲敏感，需标准化；否则大尺度特征会主导距离。⑤ <strong>不平衡数据</strong>——多数类会主导投票，可用距离加权或按类频率加权。