常见相似性度量及各种距离

青旅半醒 2022-05-16 01:15 364阅读 0赞

工程上的很多问题，比如最经典的最小二乘法、聚类问题、分类问题、视觉中的立体匹配以及图像检索等等，都要涉及到比较两个向量或者集合或者概率分布的相似程度，而比较相似程度又可以转化为比较它们之间两两的距离，距离越近，相似程度越高。针对不同的问题，研究人员提出了不同的相似度衡量标准。首先不得不说的，就是由范数而来的几种距离度量。平时接触最多的就是L0，L1，L2和L\_infinity范数：L0范数即向量中非零元素的个数；L1范数即向量各元素绝对值之和；L2范数最常见，是向量各元素平方和的平方根，又叫Euclidean范数；L\_infinity范数是指向量中绝对值最大的那个元素的绝对值，在CV的多视角几何中有着比较广泛的应用，有篇paper推荐：Multiple-View Geometry under the L\_infinity-Norm，发表在TPAMI上，作者是计算机视觉经典书籍MVG的作者Richard Hartley。这几种范数，除了L0范数，都可以对应一种空间上的距离表达。

### **1、L1范数和曼哈顿距离** ###

用L1范数来表达距离，就是曼哈顿距离（Manhattan Distance），这也是我们日常生活中最常接触的一种距离表达。比如就像这个地图上显示的（图1），我们要从肇嘉浜路地铁站到复旦大学附属眼耳鼻喉科医院，蓝色路线是理论上的最近路线，也就是我们从小就知道的两点之间线段最短。但是我们都知道，实际上这是不可行的，我们能选择的路线其实是红色网格线中不同路线的组合。

![70][]

所以，如果近似地将这个地图放入到我们熟知的直角坐标系中（图2），以肇嘉浜路地铁站作为坐标原点，那么从肇嘉浜路地铁站到复旦大学附属眼耳鼻喉科医院的距离，实际上是医院的横纵坐标之和。如果把医院的坐标看成是一个二维向量(X,Y)，那么横纵坐标之和就是向量元素的绝对值之和，也就是L1范数的定义。那么这个将横纵坐标相加得到的距离，就是曼哈顿距离。因为我们都知道，曼哈顿的街道几乎是严格的横平竖直（图3），规划非常整齐，所以用曼哈顿距离来定义这个L1范数的距离度量是再合适不过了。

![70 1][]

![70 2][]

### 2、L2范数和欧氏距离 ###

用L2范数来表达距离，就是欧几里德距离（Euclidean Distance），又叫欧式距离，这是我们从小学一开始就建立的距离概念，也就是空间中两点连线的距离。很显然，之前那个例子中，图1蓝色的路线表示的就是L2距离。这在现实中几乎是不可能的，但是在工程领域，L2距离的应用非常广泛，在衡量距离的时候，大多数人的第一反应都是L2距离。当然L2距离的缺陷也很显著，接下来在介绍马氏距离的时候会提到。

### 3、 L\_infinity范数和切比雪夫距离 ###

用L\_infinity来表达距离，就是切比雪夫距离（Chebyshev Distance）。 在二维空间的一个例子就是国际象棋，图4来自百度百科。。。每个格子里的数字就代表了该格子到国王所处位置（f6）的切比雪夫距离。比如说，从国王（f6）到图中的红框位置（d2）至少需要走几步呢，这个切比雪夫距离就代表了至少需要的步数。

![70 3][]

![70 4][]

### 4、p范数和闵可夫斯基距离 ###

以上的各种范数和距离还可以归纳到一起，总结成一个很好的形式（感觉数学和物理很多时候都是在对之前的研究进行总结，很多看起来不一样的东西都可以归结成一个统一的形式，比如TBBT中Sheldon研究的弦理论，就是为了把基本粒子和四种相互作用力统一起来），那就是p范数和闵可夫斯基距离（Minkowski Distance）。公式显示不出来，p范数的定义只好粘一个图片了。可以看到，当p取不同值的时候，p范数就变成了不同的范数： p=1，L1范数；p=2，L2范数；p趋向无穷，就是L\_infinity范数。

![\\left( \\sum\_\{i=1\}^\{n\}\\left | x\_i-y\_i \\right |^p \\right)^\{1/p\}][left_ _sum_i_1_n_left _ x_i-y_i _right _p _right_1_p]

还有一个图做的很好，引用过来（来源http://www.cnblogs.com/daniel-D/p/3244718.html）。这个图就表达了随着p的变化，二维向量**a**组成的集合的变化，当p=1, 2和无穷时，就是图5所示的样子。

![70 5][]

### 5、马氏距离 ###

以上这一类，都是由范数而来的距离度量。之前提到L2距离的缺陷，其实也是闵可夫斯基距离的缺陷，那就是没有考虑向量各维度之间的关系，比如量纲的问题。举个例子：统计一群人的身高、体重和鞋码，其中身高的单位是米（m），体重单位是千克（kg），而鞋码的单位是厘米（cm）。可以想象，身高数据基本在1.5~1.9m的范围内，体重数据在40~80kg左右，鞋码基本上是20~30cm，三个维度数据相差的还是比较大的。如果更夸张一点，体重单位用克的话，那么体重和身高数据相差的就更大了。这样一来，在用闵式距离计算的时候，数值较大的维度会对距离影响较大，导致各维度对距离的贡献不均衡，那么距离衡量就可能出现偏差。如果还是想利用L2距离的话，就要考虑使用标准化的L2距离，也就是将各个维度都减去均值，除以标准差，使之变成0均值，1标准差，这样一来就消除了量纲的影响。可是再进一步，如果每个维度之间有所关联，并不是完全独立的呢？比如还是身高、体重和鞋码。一般来讲，身高高的人体重和鞋码也会比较大，这样三个数据维度之间就是有联系的。为了体现这种联系，我们在计算距离的时候就要考虑数据维度之间的统计特性，不能像闵式距离一样，假设各维度是统计独立的。所以，就有了马氏距离。

先上个公式。公式中的x和μ就是要比较的两个向量，Σ是协方差矩阵。可见，马氏距离跟欧式距离相差了一个协方差矩阵，这个协方差矩阵就引入了各维度之间的统计关系：矩阵元素λij代表了第i个维度和第j个维度之间的协方差，也就是相关性，对角元素就是各维度的方差。

![D\_M(x)= \\sqrt\{\\(x-\\mu \\)^T \\Sigma ^\{-1\} \\(x-\\mu\\)\}][D_M_x_ _sqrt_x-_mu _T _Sigma _-1_ _x-_mu]

注:到这个Σ用的是逆。可以想象，如果Σ非对角元素都是零，就表示各维度之间没有关联，是统计独立的；再如果Σ对角元均为1，那么Σ就是一个单位阵，就说明各维度之间量纲的关系没有考虑，这个距离就是L2距离，公式上也就转化成了L2距离；如果Σ对角元不相等，Σ是一个一般的对角阵，也就是不同维度除了一个不同的值，那么就说明这个距离是标准化的欧式距离。

所以综上，闵式距离是L2距离在范数层面上的一般化，马氏距离算是考虑了统计关系后，L2距离在统计意义上的一般化。

### 6、其他相似性度量和距离 ###

接下来还有几种距离，余弦相似度比较简单，与之相关的是皮尔逊相似系数；汉明距离我记得是在信息论中学到过，学信道编码的时候会用到；还有一个接触的不多，叫做巴氏距离，师兄用到过。关于这些距离推荐http://www.cnblogs.com/daniel-D/p/3244718.html。这里没有巴氏距离，巴氏距离的话看https://www.cnblogs.com/wt869054461/p/5777782.html。

[70]: /images/20220516/c2964e500e1946089fa63fb6169e4a52.png
[70 1]: /images/20220516/041a1658faa64cdbbf8b4d556089c3f6.png
[70 2]: /images/20220516/861912aad121461da9a424c03724934f.png
[70 3]: /images/20220516/ec2333638ef94db99d2b7b4e091c1306.png
[left _ a _right _1_left _ a _right _2_left _ a _right _propto _1]: https://private.codecogs.com/gif.latex?%5Cleft%20%5C%7C%20a%20%5Cright%20%5C%7C_1%3D%5Cleft%20%5C%7C%20a%20%5Cright%20%5C%7C_2%3D%5Cleft%20%5C%7C%20a%20%5Cright%20%5C%7C_%5Cpropto%20%3D1
[70 4]: /images/20220516/1b097fa468ec4c1c9191c0edad5c66ab.png
[left_ _sum_i_1_n_left _ x_i-y_i _right _p _right_1_p]: https://private.codecogs.com/gif.latex?%5Cleft%28%20%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%5Cleft%20%7C%20x_i-y_i%20%5Cright%20%7C%5Ep%20%5Cright%29%5E%7B1/p%7D
[70 5]: /images/20220516/92a1ee7b4abc4b61b6220d01ba78b8f6.png
[D_M_x_ _sqrt_x-_mu _T _Sigma _-1_ _x-_mu]: https://private.codecogs.com/gif.latex?D_M%28x%29%3D%20%5Csqrt%7B%5C%28x-%5Cmu%20%5C%29%5ET%20%5CSigma%20%5E%7B-1%7D%20%5C%28x-%5Cmu%5C%29%7D