距离度量与 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 方案。

写出欧氏、曼哈顿、余弦相似度的公式? 闵可夫斯基距离如何统一三者?

为什么余弦相似度 $\cos \theta = \frac{x \cdot y}{\Vert x \Vert \Vert y \Vert}$ 对向量长度不敏感? 文本检索为什么常用?

何时用欧氏、何时用余弦、何时用曼哈顿? 为什么高维下 L1 比 L2 更稳定?

KD-Tree 如何构建与查询? 为什么高维下退化为接近线性扫描?

特征缩放为什么对距离度量必要? 不同量纲特征如何扭曲距离? 标准化的公式是什么?