← Back to Classic ML Mind Map
📊 Classic MLID: distance-metrics

Distance Metrics & Indexing

距离度量与 KD-Tree
🎯Core Definition
Distance metrics define similarity in feature space and directly drive the results of KNN, clustering, and retrieval. Common metrics: Euclidean distance d2(x,y)=∑i(xi−yi)2d_2(x, y) = \sqrt{\sum_i (x_i - y_i)^2} (L2, most natural when all dimensions share scale); Manhattan distance d1(x,y)=∑i∣xi−yi∣d_1(x, y) = \sum_i |x_i - y_i| (L1, more robust to outliers and more stable in high dimensions); cosine similarity cos⁡θ=x⋅y∥x∥∥y∥\cos \theta = \frac{x \cdot y}{\Vert x \Vert \Vert y \Vert} (direction only, magnitude-invariant — the default for TF-IDF/embedding retrieval); Minkowski distance dp(x,y)=(∑i∣xi−yi∣p)1/pd_p(x, y) = \left( \sum_i |x_i - y_i|^p \right)^{1/p} unifies them (p=1p=1 Manhattan, p=2p=2 Euclidean).Indexing: a KD-Tree recursively bisects space at coordinate medians, giving O(log⁡n)O(\log n)-scale low-dimensional queries; a Ball-Tree partitions with hyperspheres and degrades more gracefully in higher dimensions. Feature scaling matters: variables with larger magnitudes dominate the distance unless z-scored (or min-max normalized) first.
💡Use Cases
the similarity core of KNN and K-Means, text/vector retrieval (cosine), recommendation recall, anomaly detection; interviews often ask when to choose Euclidean vs cosine and how KD-Tree works.
⚡Key Problems Solved
no single metric covers all semantics — Euclidean assumes equal, commensurable dimensions; cosine removes document-length bias in text; L1 resists outliers; and in high dimensions LpL_p norms lose contrast as pp grows (relative distances converge), which is why cosine/Manhattan are preferred there. KD-Tree/Ball-Tree cut naive O(nd)O(nd) KNN queries to O(log⁡n)O(\log n) scale in low dimensions, but degrade in high dimensions where ANN schemes are needed.
🎯Core Interview Exam Points
Fundamentals · Production Scenarios · Deep Dive
Core Def
Explain the core definition, underlying mechanism/math, and key principles of Distance Metrics & Indexing.
Use Cases
In production engineering, what are the primary use cases for Distance Metrics & Indexing and what core pain points does it solve?
🔥 High-Frequency Deep-Dive Questions
1
Write the Euclidean, Manhattan, and cosine similarity formulas; how does Minkowski distance unify them?
2
Why is cosine similarity cos⁡θ=x⋅y∥x∥∥y∥\cos \theta = \frac{x \cdot y}{\Vert x \Vert \Vert y \Vert} invariant to vector length? Why is it standard for text retrieval?
3
Euclidean vs cosine vs Manhattan — when to use each? Why is L1 more stable than L2 in high dimensions?
4
How does a KD-Tree build and query? Why does it degrade toward a linear scan in high dimensions?
5
Why is feature scaling essential for distances? How do different scales distort them? What is the standardization formula?
📖 In-depth Guide:📄 clustering-and-knn →
Updated 2026-08-12
🎯
Verify Mastery: Practice Exam Questions for "Distance Metrics & Indexing"
Take pitfall multiple-choice questions with derivation options; mistakes are automatically logged.
🚀 Start Card Practice ➔
← Previous CardKNN & K SelectionNext Card →PCA & SVD

🔗 More Classic ML Knowledge Cards

引用出处: TalentMe 450+ 工业级 AI 架构考点知识库 (Tech Vault) · 遵循 CC-BY-4.0 知识共享协议
URL: https://talentme.airsota.com/resources/tech/roadmap/mindmap/ML/card/distance-metrics
中文速览与面试要点

距离度量与 KD-Tree (Distance Metrics & Indexing)

定义: 距离度量定义特征空间中的相似度, 直接决定 KNN/聚类/检索的结果。常用度量: 欧氏距离 d_2(x, y) = _i (x_i - y_i)^2 (L2, 各维同量纲时最自然); 曼哈顿距离 d_1(x, y) = _i |x_i - y_i| (L1, 对异常值更鲁棒, 高维下相对距离比 L2 稳定); 余弦相似度 = x y x y (只看方向、忽略幅度, 是文本 TF-IDF/Embedding 检索的标配); 闵可夫斯基距离 d_p(x, y) = ( _i |x_i - y_i|^p )^1/p 统一三者 (p=1 曼哈顿, p=2 欧氏)。空间索引: KD-Tree 沿坐标中位数递归二分空间, 低维查询可到 O( 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( n) 量级, 但高维索引退化, 需要 ANN 方案。

核心要点

  • 写出欧氏、曼哈顿、余弦相似度的公式? 闵可夫斯基距离如何统一三者?
  • 为什么余弦相似度 = x y x y 对向量长度不敏感? 文本检索为什么常用?
  • 何时用欧氏、何时用余弦、何时用曼哈顿? 为什么高维下 L1 比 L2 更稳定?
  • KD-Tree 如何构建与查询? 为什么高维下退化为接近线性扫描?
  • 特征缩放为什么对距离度量必要? 不同量纲特征如何扭曲距离? 标准化的公式是什么?