常见的距离测度

在对向量进行相似度计算的时候经常需要纠结的是用什么测度来衡量相似度。经常听到的距离测度无非是欧氏距离、曼哈顿距离、切比雪夫距离、闵科夫斯基距离、海明距离、编辑距离、余弦距离、杰卡德距离这么几个，稍微生僻点的再加上什么标准化欧氏距离、卡方距离、马哈拉诺比斯距离、巴塔恰里雅距离、皮尔逊距离。前面说的那些距离大都是一回事，掌握了初中左右的知识基本都能理解，而后面说的这些距离就相对复杂很多了，得有离散统计线性代数这类的扎实功底才能吃透。。。这里就稍微介绍下概念上距离测度的定义，以及简单的距离测度。

距离测度的定义

感觉实距离测度本没有标准的定义，只是人们用多了，也就有了这么个定义。

所谓距离测度(Similarity Measure)就是指一个函数d(x,y)，用空间中的两个点x,y作为参数，输出一个实数值，这个值能够反应这两个点的距离关系。这个函数一般要满足下面的准则：

1、d(x,y)\geq 0（非负性）

2、x=y当且仅当d(x,y)=0（自反性）

3、d(x,y)=d(y,x)（对称性）

4、d(x,y)\geq d(x,z)+d(z,y)(三角不等式)

前三个都很好理解，只是为什么一定要满足三角不等式呢？我想应该是为了保证距离一定得是所有同类路径中最短的那条轨迹。

闵可夫斯基距离类

在n维空间中，两个n维向量x=(x_1,x_2,x_3,...,x_n),y=(y_1,y_2,y_3,...,y_n)之间的闵可夫斯基距离(Minkowski Distance)定义为：

闵科夫斯基距离实际上就是Lp norm里的距离(p根据需要确定)。可以很容易的证明当p>=1的时候，这个距离都是满足距离测度的定义的。不过当p<0时，他就不满足三角不等式了，也就不算是标准的距离测度了。

当p=1时，闵科夫斯基距离就变曼哈顿距离成了：

曼哈顿距离，又叫出租车距离，直观的理解就是向量在各个维度上差的绝对值之和。

当p=2时，就是我们最常见的欧氏距离了：

当p\to\infty时，闵科夫斯基距离就变成了切比雪夫距离：

也就是向量在各个维度上差的绝对值的最大值。

可以很容易证明，当p\geq 1时，闵科夫斯基距离是满足距离测度的所有要求的。

海明距离

海明距离的定义也很简单，对于两个向量，他们之间的海明距离就是定义为这两个向量中不同分量的个数。仔细想想这个距离定义好像很没有用，不过事实上他通常应用在布尔向量(比如00101和01111的海明距离就是2)或者相似度要求比较高的场景中。

他的特点在于计算速度巨快，通过计算机基础的异或操作就能比较布尔向量的距离，因此在数据量巨大、追求效率的场景中用处还是非常广的。

编辑距离

编辑距离也是很简单的，主要用于两个字符串之间的距离计算。定义就是将一个字符串用最少的删除、插入操作变成另一个字符串所需要的操作个数。比如x=abcde,y=acfdeg，他们的编辑距离就是3。具体的实现方法就用dp做就好了，复杂度就是两个字符串长度之积。他的值跟这两个字符串的LCS还有一定的关系，即编辑距离等于x和y的长度之和减去他们LCS长度的两倍。

当然，有些定义的编辑距离还会支持“替换”或者“交换”之类的操作，其实意思也都差不多了。

余弦距离

余弦距离就是字面上的意思了，也就是求两个向量夹角的余弦值。具体的计算方法也就是用两个向量的内积除以两个向量的l_2\ \ norm：

余弦距离在某些情况下特别管用，谁用谁知道。

杰卡德距离

Jaccard距离实际上就是1-Jaccard相似度，即：

在文档相似度处理时，杰卡德距离和杰卡德相似度都常常被提及。

上面这些距离测度其实都很好理解，在这里归纳一下主要是为了以后遇到类似距离计算的问题时能够多几种思考的角度。