距离度量与 KD-Tree

距离度量定义特征空间中的相似度, 直接决定 KNN/聚类/检索的结果。常用度量: 欧氏距离 $d_2(x, y) = \sqrt{\sum_i (x_i - y_i)^2}$ (L2, 各维同量纲时最自然); 曼哈顿距离 $d_1(x, y) = \sum_i |x_i - y_i|$ (L1, 对异常值更鲁棒, 高维下相对距离比 L2 稳定); 余弦相似度 $\cos \theta = \frac{x \cdot y}{\Vert x \Vert \Vert y \Vert}$ (只看方向、忽略幅度, 是文本 TF-IDF/Embedding 检索的标配); 闵可夫斯基距离 $d_p(x, y) = \left( \sum_i |x_i - y_i|^p \right)^{1/p}$ 统一三者 ($p=1$ 曼哈顿, $p=2$ 欧氏)。空间索引: KD-Tree 沿坐标中位数递归二分空间, 低维查询可到 $O(\log n)$ 量级; Ball-Tree 用超球划分, 高维下更稳。特征缩放: 量纲不同的特征以绝对数值主导距离, 必须先 z-score 标准化 (或 min-max 归一化)。

KNN、K-Means 的相似度核心, 文本/向量检索 (余弦), 推荐召回、异常检测; 面试常考“欧氏 vs 余弦怎么选”与 KD-Tree 原理。

单一度量无法覆盖所有语义——欧氏假设各维同量纲且同等重要, 文本场景用余弦消除文档长度偏差, L1 对离群点稳健, 且高维下 $L_p$ 范数随 $p$ 增大的对比能力退化 (相对距离趋同, 故高维常用余弦/曼哈顿); KD-Tree/Ball-Tree 把 KNN 朴素 $O(nd)$ 查询降到低维 $O(\log n)$ 量级, 但高维索引退化, 需要 ANN 方案。

检验攻克程度：针对「距离度量与 KD-Tree」专属刷题排雷

做单选排雷题、推导选项机制，答错自动收录进专属错题本。