K-Nearest Neighbors & Metric Learning: 解释维度灾难对 KNN 的具体影响。

Core Concept: 高维下最近邻与最远邻距离趋同，'最近'失去区分度，需要样本量指数增长。

维度灾难的三个具体表现：① <strong>距离集中</strong>——对 i.i.d. 均匀分布，随着维度 d 增大，(d_max−d_min)/d_min→0，即所有点对的距离趋于相同。此时'最近邻'与'最远邻'几乎无差别，KNN 的排序失去意义。② <strong>样本稀疏</strong>——要维持固定密度，样本量需随 d <strong>指数增长</strong>（体积 ∝ r^d）；例如要在 10 维空间中保持 1 维时同样的点密度，需要 10¹⁰ 倍样本。③ <strong>邻域不再是'局部'</strong>——高维下第 k 近邻可能距离查询点非常远（邻域跨越数据的整个范围），故'局部平均'不再局部。<strong>理论边界</strong>：Stone (1977) 证明 KNN 一致性要求 K→∞、K/n→0，但高维下满足此条件所需的 n 不可行；此外，若数据的内在维度（intrinsic dimension）低（如分布在低维流形上），KNN 仍可能有效——这提示降维的价值。

缓解手段：① <strong>降维</strong>——PCA（线性）、UMAP/t-SNE（非线性，但 t-SNE 不适合做下游特征）、自编码器；关键是降到<strong>内在维度</strong>而非任意低维。② <strong>特征选择</strong>——移除无关特征（它们只增加维度不增加信息），对 KNN 尤其有效（因为无关特征会主导距离）。③ <strong>度量学习</strong>——学习一个低维的、任务相关的距离（LMNN 用三元组约束、深度度量学习用对比损失），这等价于'有监督降维 + 距离定义'，是检索/人脸识别的标准做法。④ <strong>嵌入检索</strong>——用神经网络学到的嵌入（如 CLIP、双塔模型）替代原始特征，嵌入空间通常有更好的几何性质（各向同性、语义平滑），且维度可控（128–1024），使 ANN 检索有效——这是现代检索系统绕开维度灾难的主流方案。⑤ <strong>近似索引的局限</strong>——HNSW 等在高维下也需更多内存与查询时间，但通过图结构的导航性部分缓解了距离集中问题。