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

时间 2021-01-12 标签相似性度量及各种距离

工程上的很多问题，比如最经典的最小二乘法、聚类问题、分类问题、视觉中的立体匹配以及图像检索等等，都要涉及到比较两个向量或者集合或者概率分布的相似程度，而比较相似程度又可以转化为比较它们之间两两的距离，距离越近，相似程度越高。针对不同的问题，研究人员提出了不同的相似度衡量标准。首先不得不说的，就是由范数而来的几种距离度量。平时接触最多的就是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），我们要从肇嘉浜路地铁站到复旦大学附属眼耳鼻喉科医院，蓝色路线是理论上的最近路线，也就是我们从小就知道的两点之间线段最短。但是我们都知道，实际上这是不可行的，我们能选择的路线其实是红色网格线中不同路线的组合。

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

2、L2范数和欧氏距离

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

3、 L_infinity范数和切比雪夫距离

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

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}$

还有一个图做的很好，引用过来（来源http://www.cnblogs.com/daniel-D/p/3244718.html）。这个图就表达了随着p的变化，二维向量a组成的集合的变化，当p=1, 2和无穷时，就是图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$}$

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

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

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

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