几何距离总汇

Question

在做分类时常常需要估算不同样本之间的相似性度量 (SimilarityMeasurement)，这时通常采用的方法就是计算样本间的 距离 (Distance)。采用什么样的方法计算距离是很讲究，甚至关系到分类的正确与否。
本文的目的就是对常用的相似性度量作一个汇总。

• 欧氏距离
• 曼哈顿距离
• 切比雪夫距离
• 闵可夫斯基距离
• 标准化欧氏距离
• 马氏距离
• 夹角余弦
• 汉明距离
• 杰卡德距离&杰卡德相似系数
• 相关系数&相关距离
• 信息熵

欧氏距离 (EuclideanDistance)

欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。

二维平面上两点 $a(x_1,y_1)$ 与 $b(x_2,y_2)$ 间的欧氏距离：

$$ d_{12}=\sqrt{(x_{1}-x_{2})^2+(y_{1}-y_{2})^2} $$

三维空间两点 $a(x_1,y_1,z_1)$ 与 $b(x_2,y_2,z_2)$ 间的欧氏距离：

$$ d_{12}=\sqrt{(x_{1}-x_{2})^2+(y_{1}-y_{2})^2+(z_{1}-z_{2})^2} $$

两个 n 维向量 $a(x_{11},x_{12},…,x_{1n)}$ 与 $b(x_{21},x_{22},…,x_{2n})$ 间的欧氏距离：

$$ d_{12}=\sqrt{\sum _{k=1} ^n (x{1k}-x_{2k})^2} $$

表示成向量运算的形式：

$$ d_{12}=\sqrt{(a-b)(a-b)^\tau} $$

曼哈顿距离 (ManhattanDistance)

出租车几何或曼哈顿距离（Manhattan Distance）是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ，是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。图中红线代表曼哈顿距离，绿色代表欧氏距离，也就是直线距离，而蓝色和黄色代表等价的曼哈顿距离。曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离，即 $d(i，j)=|x_{i}-x_{j}|+|y_{i}-y_{j}|$。对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，因此，曼哈顿距离又称为出租车距离。曼哈顿距离不是距离不变量，当坐标轴变动时，点间的距离就会不同。

二维平面两点 $a(x_1,y_1)$与$b(x_2,y_2)$ 间的曼哈顿距离

$$ d_{12}=|x_{1}-x_{2}|+|x_{1}-x_{2}| $$

两个 n 维向量 $a(x_{11},x_{12},…,x_{1n})$ 与 $b(x_{21},x_{22},…,x_{2n})$ 间的曼哈顿距离

$$ d_{12}=\sum ^n _{k=1}|x{1k}-x_{2k}| $$

切比雪夫距离 ( Chebyshev Distance )

在数学中，切比雪夫距离或是 L∞度量是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。在国际象棋中，国王走一步能够移动到相邻的 8 个方格中的任意一个。那么国王从格子 $(x_1,y_1)$ 走到格子 $(x_2,y_2)$ 最少需要多少步？你会发现最少步数总是 $max(| x_2-x_1 | , | y_2-y_1 | )$ 步。有一种类似的一种距离度量方法叫切比雪夫距离。

二维平面两点 $a(x_1,y_1)$与$b(x_2,y_2)$ 间的切比雪夫距离

$$ d_{12} = max(|x_{1}-x_{2}|,|y_{1}-y_{2}|) $$

两个 n 维向量 $a(x_{11},x_{12},…,x_{1n})$ 与 $b(x_{21},x_{22},…,x_{2n})$ 间的切比雪夫距离

$$ d_{12} = max_{i}(|x_{1i}-x_{2i}|) $$

公式的另一种等价形式：

$$ d_{12} = lin_{k\rightarrow\infty}({\sum _{i=1} ^n}|x{1i}-x_{2i}|^2)^{\frac{1}{k}} $$

闵可夫斯基距离( MinkowskiDistance )

闵氏距离不是一种距离，而是一组距离的定义。

闵氏距离的定义

两个 n 维变量 $a(x_{11},x_{12},…,x_{1n})$ 与 $b(x_{21},x_{22},…,x_{2n})$ 间的闵可夫斯基距离定义为：

$$ d_{12} = \sqrt[p]{\sum _{i=1} ^n|x{1k}-x_{2k}|^p} $$

其中 p 是一个变参数。
当 p=1 时，就是曼哈顿距离
当 p=2 时，就是欧氏距离
当 p→∞时，就是切比雪夫距离
根据变参数的不同，闵氏距离可以表示一类的距离。

闵氏距离的缺点

闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。
举个例子：二维样本（身高,体重)，其中身高范围是 150190，体重范围是 5060，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么 a 与 b 之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于 a 与 c 之间的闵氏距离，但是身高的 10cm 真的等价于体重的 10kg 么？因此用闵氏距离来衡量这些样本间的相似度很有问题。简单说来，闵氏距离的缺点主要有两个：

1. 将各个分量的量纲(scale) 也就是 单位 当作相同的看待了。
2. 没有考虑各个分量的分布（期望，方差等) 可能是不同的。

标准化欧氏距离(Standardized Euclidean distance)

标准欧氏距离的定义

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，好吧！那我先将各个分量都“标准化”到均值、方差相等吧。均值和方差标准化到多少呢？这里先复习点统计学知识吧，假设样本集 X 的均值(mean) 为 m，标准差 (standarddeviation) 为 s，那么 X 的“标准化变量”表示为：

$$ X^* = \frac{x-m}{s} $$

而且标准化变量的数学期望为 0，方差为 1。因此样本集的标准化过程 (standardization) 用公式描述就是：

标准化后的值 = ( 标准化前的值 － 分量的均值 ) /分量的标准差

经过简单的推导就可以得到两个 n 维向量 a(x₁₁,x₁₂,…,x_1n) 与 b(x₂₁,x₂₂,…,x_2n) 间的标准化欧氏距离的公式：

$$ d_{12} = \sqrt{\sum _{k=1} ^n (\frac{x{1k}-x_{2k}}{s_{k}})^p} $$

如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(WeightedEuclidean distance)。

马氏距离(MahalanobisDistance)

马氏距离定义

有 M 个样本向量 X₁<~X_m，协方差矩阵记为 S，均值记为向量μ，则其中样本向量 X 到 u 的马氏距离表示为:

$$ D(x)=\sqrt{(X-\mu)^T S^{-1}(X-\mu)} $$

而其中向量 X_i与 X_j之间的马氏距离定义为：

$$ D(X_{i},X_{j}) = \sqrt{(X_{i}-X_{j})^T S^{-1}(X_{i}-X_{j})} $$

若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：(也就是欧式距离了)

$$ D(X_{i},X_{j}) = \sqrt{(X_{i}-X_{j})^T (X_{i}-X_{j})} $$

马氏距离的优点：量纲无关，排除变量之间的相关性的干扰。

夹角余弦(Cosine)

几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。

在二维空间中向量 A(x1,y1) 与向量 B(x2,y2) 的夹角余弦公式：

$$ cosθ = \frac{x_{1}x_{2}+y_{1}y_{2}}{\sqrt{x_{1}^2 + y_{1}^2}\sqrt{x_{2}^2 + y_{2}^2}} $$

两个 n 维样本点 a(x₁₁,x₁₂,…,x_1n) 和 b(x₂₁,x₂₂,…,x_2n) 的夹角余弦
类似的，对于两个 n 维样本点 a(x₁₁,x₁₂,…,x_1n) 和 b(x₂₁,x₂₂,…,x_2n)，可以使用类似于夹角余弦的概念来衡量它们间的相似程度。

$$ cosθ = \frac{a\cdot b}{|a||b|} $$

即:

$$ cosθ = \frac{\sum _{k=1} ^n x{1k}x_{2k}}{\sqrt{\sum _{k=1} ^n x{1k}^2}\sqrt{\sum _{k=1} ^n x{2k}^2}} $$

夹角余弦取值范围为 [-1,1] ​。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值 1，当两个向量的方向完全相反夹角余弦取最小值-1。

汉明距离 (Hammingdistance)

• 汉明距离的定义
  两个等长字符串 s1 与 s2 之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为 2。
• 应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。

杰卡德相似系数 (Jaccardsimilarity coefficient)

杰卡德相似系数

两个集合 A 和 B 的交集元素在 A，B 的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号 J(A,B) 表示。

$$ J(A,B) = \frac{A\cap B}{A\cup B} $$

杰卡德相似系数是衡量两个集合的相似度一种指标。

杰卡德距离

与杰卡德相似系数相反的概念是杰卡德距离(Jaccarddistance)。杰卡德距离可用如下公式表示：

$$ J_{\delta}=1-J(A,B)=\frac{|A\cup B|-|A\cap B|}{|A\cup B|} $$

杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

杰卡德相似系数与杰卡德距离的应用

可将杰卡德相似系数用在衡量样本的相似度上。样本 A 与样本 B 是两个 n 维向量，而且所有维度的取值都是 0 或 1。例如：A(0111) 和 B(1011)。我们将样本看成是一个集合，1 表示集合包含该元素，0 表示集合不包含该元素。

• p：样本 A 与 B 都是 1 的维度的个数
  • q：样本 A 是 1，样本 B 是 0 的维度的个数
  • r：样本 A 是 0，样本 B 是 1 的维度的个数
  • s：样本 A 与 B 都是 0 的维度的个数
    那么样本 A 与 B 的杰卡德相似系数可以表示为：
    这里 p+q+r 可理解为 A 与 B 的并集的元素个数，而 p 是 A 与 B 的交集的元素个数。而样本 A 与 B 的杰卡德距离表示为：
    $$ J = \frac{p}{p+q+r} $$

相关系数( Correlation coefficient ) 与相关距离(Correlation distance)

相关系数的定义

$$ \rho_{XY} = \frac{Cov(X,Y)}{\sqrt{D(X)}\sqrt{D(Y)}} = \frac{E((X-EX)(Y-EY))}{\sqrt{D(X)}\sqrt{D(Y)}}$$

相关系数是衡量随机变量 X 与 Y 相关程度的一种方法，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明 X 与 Y 相关度越高。当 X 与 Y 线性相关时，相关系数取值为 1（正线性相关）或-1（负线性相关）。

相关距离的定义

$$ D_{xy}=1-\rho_{XY} $$

信息熵(Information Entropy)

信息熵并不属于一种相似性度量。那为什么放在这篇文章中啊？这个……，我也不知道。信息熵是衡量分布的混乱程度或分散程度的一种度量。分布越分散（或者说分布越平均)，信息熵就越大。分布越有序（或者说分布越集中），信息熵就越小。
计算给定的样本集 X 的信息熵的公式：

$$ Entropy(X)=\sum _{i=1} ^n -p{i} log_{2} p_{i} $$

参数的含义：

• n：样本集 X 的分类数
• $p_i$：X 中第 i 类元素出现的概率
  信息熵越大表明样本集 S 分类越分散，信息熵越小则表明样本集 X 分类越集中。当 S 中 n 个分类出现的概率一样大时（都是 1/n），信息熵取最大值 $log2(n)$。当 X 只有一个分类时，信息熵取最小值 0

参考资料：

[1] 吴军. 数学之美 系列 12 -余弦定理和新闻的分类.
[2] Wikipedia. Jaccard index.
[3] Wikipedia. Hamming distance
[4] 求马氏距离（Mahalanobisdistance ）matlab 版
[5] Pearson product-momentcorrelation coefficient