开篇题外话: 本文可以说是《百面机器学习》第2章模型评估的部分学习笔记了，外加了一些自己对距离度量方面的一些思考。
1. 距离的定义
严格意义上，距离的定义:
在一个集合中，如果每一对元素均可唯一确定一个实数，使得三条距离公理（同一性、正定性、对称性、三角不等式）成立，则该实数可称为这对元素之间的距离。[1][2]
- 同一性 (identity of indiscernibles) 就是指 $\mathrm{dist}(A,A)=0$；
- 正定性 (non-negativity or separation axiom) 就是指 $\mathrm{dist}(A,B)\ge 0$恒成立；
- 对称性 (symmetry) 就是指 $\mathrm{dist}(A,B)=\mathrm{dist}(B,A)$；
- 三角不等式 (subadditivity or triangle inequality) 就是指 $\mathrm{dist}(A,B)+\mathrm{dist}(B,C)\ge\mathrm{dist}(A,C)$。
2. 常见的距离公式
在机器学习领域，我们需要距离定性地度量两个向量之间的差异性，而距离度量通常反应在损失函数的设计上。下面对几种常见的距离函数进行解释。
2.1 曼哈顿距离 (Manhattan Distance):
$$\mathrm{dist}(A,B)=\lVert A-B\rVert_1= \sum\limits_{i}^{n}|A_i-B_i|$$
曼哈顿距离的计算，实际上就是求两个向量之差的 L1 范数 (L1 Normalization)。
2.2 欧式距离 (Euclidean Distance):
$$\mathrm{dist}(A,B)=\lVert A-B\rVert_2= \sqrt{\sum\limits_{i}^{n}(A_i-B_i)^2}$$
欧式距离的计算，实际上就是求两个向量之差的 L2 范数 (L2 Normalization)。
2.3 闵可夫斯基距离 (Minkowski distance):
$$\mathrm{dist}(A,B)=\left(\sum\limits_{i}^{n}|A_i-B_i|^p\right)^\frac{1}{p}$$
曼哈顿距离，欧氏距离都是闵可夫斯基的一种特例 ($p=1,2$)，也是最常见的。
2.4 余弦距离 (Cosine Distance):[2]
$$\mathrm{dist}(A,B)=1-\cos\theta$$
补充一下余弦定理: $c^2=a^2+b^2-2ab\cos\gamma$.
值得注意的是：
- 余弦距离并不满足三角不等式，故不是严格定义的距离；
- 欧式距离体现数值上的绝对差异，而余弦距离体现的是方向上的相对差异；
特别地，如果 $A, B$ 都是单位圆上的一点，那么:
$$\lVert A-B\rVert_2=\sqrt{2(1-\cos\theta)}=\sqrt{2*\mathrm{dist}_{余弦}(A,B)}$$
即：
$$
\begin{equation}\begin{split}
\mathrm{dist}_{余弦}(A,B)&=\frac{1}{2}\lVert A-B\rVert^2\\
&=\frac{1}{2}\mathrm{dist}_{欧式}(A,B)^2
\end{split}\end{equation}
$$
故在单位圆上，余弦距离和欧式距离有二次关系，而欧式距离满足三角不等式，那么余弦距离自然不满足三角不等式。
2.5 KL 距离 (Kullback-Leibler Divergence):
$$D_{KL}(P||Q)=-\sum\limits_{i}P(i)\ln\frac{Q(i)}{P(i)}$$
在机器学习领域，被俗称为距离，却不满足三条距离公理的不仅仅有余弦距离，还有 KL 距离 (Kullback-Leibler Divergence)，也叫相对熵，它常用于计算两个分布之间的差异，但不满足对称性和三角不等式。[2]
3. 一些思考
对于不满足三角不等式的余弦距离、KL 距离等，我们不能用 Dijkstra, Floyd 等最短路算法来高效地求最短路径，因为上述这些最短路算法在进行松弛操作的时候都依赖三角不等式 (即 $d(a,c)=\min\lbrace d(a,c), d(a,b)+d(b,c)\rbrace$)。
- 1.Wikipedia: Metric ↩
- 2.诸葛越, 百面机器学习P34-P36 ↩
