距离详解

1. 闵尔科夫斯基 Minkowski

定义：点$P_1(x_1,x_2,x_3,...,x_n)$和$P_2(y_1,y_2,y_3,...,y_n)$的距离如：

$distance(P_1,P_2) = \sqrt[p]{\sum\limits_{i=1}^n (x_i - y_i)^p}$

    闵尔科夫斯基距离又称为闵式距离，以俄国科学家闵尔科夫斯基命名。实际它不是一种距离，而是一类距离。

    其中，$p$是一个参量，选取不同的值，可以表示不同的距离：

p值	距离
$p = 1$	曼哈顿距离
$p = 2$	欧式距离
$p = \infty$	切比雪夫距离

    这一类距离的缺点如：

• 将各个分量的量纲（Scale），即“单位”当做了相同的值看待。

• 没有考虑各个分量的分布（期望、方差等）可能不同。

距离图示：

2. 曼哈顿距离 Manhattan

定义：点$P_1(x_1,y_1)$和$P_2(x_2,y_2)$的距离如：

$distance(P_1,P_2) = |x_2 - x_1| + |y_2 - y_1|$

    曼哈顿距离又称为出租车距离或城市区块距离，由十九世纪的赫尔曼·闵可夫斯基所创，用于标明两个点在标准坐标系上的绝对轴距综合。如上图：红线就是曼哈顿距离，蓝线和黄线是等价的曼哈顿距离，绿线是欧式距离。曼哈顿距离依赖坐标系统的转度，而不是系统在坐标轴上的平移或映射。

    补充数学性质：

性质	含义
非负性	$d(i,j) \ge 0$是一个非负的数值。
同一性	$d(i,j) = 0$对象到自身距离为0。
对称性	$d(i,j) = d(j,i)$是一个对称函数。
三角不等式	$d(i,j) \le d(i,k) + d(k,j)$从对象$i$到对象$j$的直接距离不大于途径任何其他对象的距离之和。

3. 欧几里德距离 Euclidean

定义：点$P_1(x_1,x_2,x_3,...,x_n)$和$P_2(y_1,y_2,y_3,...,y_n)$的距离如：

$distance = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 +,..., + (x_n - y_n)^2} = \sqrt{\sum\limits_{i=1}^n (x_i - y_i)^2}$

    欧几里德距离又称为欧式距离，是最常用使用的空间距离，它表示空间中两点之间的支线距离，定义中的表达式是$n$维空间的欧式距离表达式，该距离可以称为两点之间向量的自然长度。

4. 切比雪夫距离 Chebyshev

定义：点$P_1(x_1,x_2,x_3,...,x_n)$和$P_2(y_1,y_2,y_3,...,y_n)$的距离如下：

$distance(P_1,P_2) = max(|x_1 - y_1|,|x_2 - y_2|,...,|x_n - y_n|) = \max\limits_{i=1}^n|x_i - y_i|$

    它是一个$L\infty$度量，表示向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。在数学中，切比雪夫距离是由一致范数（Uniform Norm）衍生的度量，属于超凸度量（Injective Metric Space）的一种。

    它的使用意义在国际象棋中，王从一点走到另一点的最短距离，下图为所有点距离F6的切比雪夫距离：

注意：曼哈顿距离和切比雪夫距离在高维空间中不成立。

    和一点有相等切比雪夫距离的点会形成一个立方体，各面都和坐标轴垂直，而和一点有相等曼哈顿距离的点会形成一个正八面体。

5. 马氏距离 Mahalanobis

定义：

单个数据点的马氏距离如：

$distance_M(x) = \sqrt{(x - \mu)^T \sum^{-1}(x - \mu)}$

数据点x, y之间的马氏距离

$distance_M(x) = \sqrt{(x - y)^T \sum^{-1}(x - y)}$

    由印度科学家马哈拉诺比斯提出，表示数据的协方差距离。是一种有效的计算两个位置样本集相似度的方法。与欧氏距离不同的是他考虑到各种特性之间的联系并且是尺度无关的，即独立于测量尺度。如果协方差矩阵为单位矩阵，马氏距离就简化为欧式距离，如果协方差矩阵为对角阵，其也可称为正规化的马氏距离。

    马氏距离可以看做欧式距离的一种修正，修正了欧式距离中各个维度量纲不一致且相关的问题。优点：不受量纲影响，两点之间马氏距离和原始数据量纲无关，由标准化数据和中心化数据计算出的两点之间的马氏距离相同；还可以排除变量之间的相关性干扰。缺点：夸大了变化微小的变量的作用。

6. 汉明距离 Hamming

定义：

$x = x_1,x_2,x_3,...,x_n$ $y = y_1,y_2,y_3,...,y_n$

$$I(x_i,y_i) = \left\{ \begin{aligned} & 1, x_i \neq y_i \\ & 0, x_i = y_i \end{aligned} \right.$$

$distance(x,y) = \sum\limits_{i=1}^n I(x_i,y_i)$

    汉明距离是使用在数据传输差错控制编码里的，它是一个概念：标识两个（相同长度）字对应位不同的数量；对两个字符串进行异或（XOR）运算，并统计结果为1的个数，那么这个数就是汉明距离。所以信息论中，两个等长字符串的汉明距离是两个字符串相对应位置上的不同字符串的个数。

7. 杰卡德距离 Jaccard

定义：两个集合$A$、$B$

杰卡德相似系数：

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

$$\left\{ \begin{aligned} & J(A,B) =1, A = \varnothing \And B = \varnothing\\ & 0 \le J(A,B) \le 1, else \end{aligned} \right.$$

杰卡德距离：

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

    杰卡德距离是杰卡德相似系数的补集，杰卡德相似系数主要用于度量两个集合之间的相似性，定义为两个集合交集集合元素的个数比上并集集合元素的个数。

8. 编辑距离 Levenshtein

    编辑距离（Edit Distance），又称为莱文斯坦距离（Levenshtein Distance），俄罗斯科学家Vladimir Levenshtein在1965年提出，它表示两个字符串之间，由一个字符串转成另一个所需的最少编辑操作次数。许可的编辑：

• 将一个字符替换成另外一个字符

• 插入一个字符

• 删除一个字符

    它的定义略有不同：

• 常提到的编辑距离就是Levenshtein距离，该距离中去只支持上述三种操作。

• Damerau-Levenshtein距离是Levenshtein距离的变种，它允许以单一操作交换相邻两个字符（也称字符转置），如AB -> BA的距离是1（交换）而不是2（先删再插入、或两次替换）。

• LCS（最长公共子序列）距离只允许删除、加入字元。

• Jaro-Winkler距离只允许字符转置。

• 汉明距离则只允许取代字符。

9. 余弦距离 Cosine Similarity

定义：两个向量$A$，$B$

$distance_{cos} = \cos(\theta) = \frac{A \cdot B}{||A|| \cdot ||B||} = \frac{\sum_1^n(A_i \times B_i)}{\sqrt{\sum_1^n(A_i)^2} \times \sqrt{\sum_1^n(B_i)^2}}$

    余弦距离又称为余弦相似度，是通过计算两个向量的夹角余弦值来评估它们的相似度，余弦相似度将向量根据坐标值绘制到向量空间中，最常用的二维空间。其中0度的相似度是1，90度的相似度是0，180度的相似度是-1，结果的测量只与向量的方向有关，和长度无关，一般使用过程用正空间[0,1]之间。

10. 皮尔森相关系数 Pearson Correlation Coefficient

定义：两个变量$x$、$y$

$distance_r = \frac{\sum_i^n((X_i - \bar{x})(Y_i - \bar{y}))}{\sqrt{\sum_1^n(x_i - \bar{x})^2}\sqrt{\sum_1^n(y_i - \bar{y})^2}}$

    皮尔森相关系数是一种线性相关系数。是两个变量线性相关程度的统计量，皮尔森相关系数的绝对值越大则相关性越强。

11. K-L散度 Kullback-Leibler Divergence

定义：衡量两个分布$P$，$Q$之间的距离，越小越相似

$distance(P||Q) = \sum\limits_1^n P(i) \log \frac{P(i)}{Q(i)}$

    是一种量化两种概率分布P和Q之间差异的方式，又叫相对熵。在概率学和统计学上，我们经常会使用一种更简单的、近似的分布来替代观察数据或太复杂的分布。K-L散度能帮助我们度量使用一个分布来近似另一个分布时所损失的信息。