盘一盘机器学习中的那些距离

在机器学习的很多算法，尤其是与聚类相关的算法中你会碰到各种各样的距离，欧式距离、马氏距离、切比雪夫距离等会让初学者头疼，如果只看书的话，大多书上就一行公式带过，看完还是迷迷糊糊，今天本文就来盘一盘机器学习中的各种距离。

闵可夫斯基距离

闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述，欧式距离、曼哈顿距离、切比雪夫距离都是由闵可夫斯基距离而来，先来看看书上给的定义^[1]

初次看到这个公式的我和你们一样，除了感觉是个有点类似于p范数的东西之外毫无感觉，但是要知道这个p是一个可以变化的参数，所以根据不同的p我们可以得到不同的距离，最常用的就是欧式距离、曼哈顿距离与切比雪夫距离。

欧式距离

当p=2时就是常见的欧式距离，我们在中学就会接触到，在二维时两点之间的欧式距离如下

那么推广到高维也是一样的，没什么好说的，所以欧式距离的计算公式就是

在Python中可以使用numpy直接计算欧式距离

import numpy as np
a = np.array([1,2,3])
b = np.array([4,5,6])
np.linalg.norm(a - b) #直接计算
np.sqrt(np.sum(np.square(a - b))) #使用公式

曼哈顿距离

当p=1时就是曼哈顿距离，从公式来看就是在计算绝对轴距之和

这样瞪这个公式可能没什么感觉，那么为什么叫曼哈顿距离？其实呢就是在曼哈顿街区要从一个十字路口开车到另一个十字路口，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是曼哈顿距离。我们来看二维的形式^[2]

图中的红线就是二维形式下的曼哈顿距离，绿线就是刚刚说过的欧式距离，而蓝线和黄线则是等价的曼哈顿距离，实际上和红线计算的结果相同，所以这就直观的想清楚了我们在开头说的绝对轴距之和，推广到高维计算思想也是类似的！在Python中计算曼哈顿距离也不难

import numpy as np
a = np.array([1,2,3])
b = np.array([4,5,6])
np.sum(np.abs(a - b))

切比雪夫距离

当p=∞时闵可夫斯基距离就转换为切比雪夫距离

书上的解释为取各个坐标数值差的绝对值的最大值，其实切比雪夫距离是是向量空间中的一种度量，可以用这样一种形象的方法思考，在国际象棋中，国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？这个距离的度量就是切比雪夫距离。

大家可以自己走一下试试，看看是否无论怎么走，最短的距离永远是max(|x2-x1|,|y2-y1|)那么早起给出原公式的证明，因为好几位读者问过，其实就是利用夹逼定理简单放缩下就行，懒得敲公式了

在Python中可以使用numpy直接计算切比雪夫距离

import numpy as np
a = np.array([1,2,3])
b = np.array([4,5,6])
print(np.abs(a-b).max())
print(np.linalg.norm(a-b,ord=np.inf))

马氏距离

在前文忘记说明，距离就是用来衡量相似度的，什么是一个好的距离，也就是我们希望算出来两个样本的距离越小，相似度越高！

而在上面的几种距离的定义中，有一个很严重的问题就是忽略了量纲的影响^{[3] ，比如我有}三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b的闵可夫斯基距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c的闵可夫斯基距离。但身高的10cm并不能和体重的10kg划等号！

当然量纲的影响可以通过标准化来解决，但是解决了量纲因素之后，样本的分布也会影响分类

比如上图有两个正态分布的总体，它们的均值分别为a和b，但方差不一样，则图中的A点离哪个总体更近？或者说A有更大的概率属于谁？显然，A离左边的更近，A属于左边总体的概率更大，尽管A与a的欧式距离远一些！

所以，在一个方差较小的维度下很小的差别就有可能成为离群点^{[4] 。就像下图一样，A与B相对于原点的距离是相同的。但是由于样本总体沿着横轴分布，所以B点更有可能是这个样本中的点，而A则更有可能是离群点。}

（图源自知乎）

OK，就算现在我们处理了样本之间的量纲与方差因素，但是如果样本之间存在一定的相关性，样本点一定与欧氏距离近的样本点同类的概率更大吗？我们看下图

可以看到样本基本服从f(x) = x的线性分布，A与B相对于原点的距离依旧相等，显然A更像是一个离群点，因此光靠闵可夫斯基距离及衍生出来的几种距离是不够的，我们还需要解决样本之间的相关性！

因此这时候，马氏距离就出来说，只要我们先将坐标轴旋转至主成分方向解决相关性，然后再将坐标轴按照特征值进行压缩就可以了，是不是有点主成分分析PCA的意思在里面，所以计算样本数据的马氏距离就是坐标旋转+坐标压缩

由于篇幅原因，有关马氏距离的计算与推导本文就不再展开，有机会我会单独写一篇，因为为了小白也能看懂需要补充很多高等代数的知识。但是要注意到这个公式里面出现了协方差矩阵，所以当协方差矩阵为单位阵时马氏距离就转换为欧式距离，什么是协方差矩阵为单位阵？不就是样本之间的各个分量之间没有相关性并且方差为1嘛！并且对公式敏感的读者应该要发现上面马氏距离的公式与正态分布概率密度函数的指数部分有一定的相似，所以它们之间存在一定的函数关系，感兴趣的可以继续研究！

最后，在Python中计算两个样本的马氏距离可以使用scipy直接计算

import numpy as np
from scipy.spatial.distance import pdist
a=np.random.random(10)
b=np.random.random(10)
#马氏距离要求样本数要大于维数，否则无法求协方差矩阵
X=np.vstack([a,b])
XT=X.T  #此处进行转置，表示10个样本，每个样本2维

pdist(XT,'mahalanobis')

当然最好可以自己用公式来一步步计算，而不是像我一样化身调包侠！到这里我们就盘完了机器学习中的几种距离，如果看完的话应该要了解何时使用什么距离！当然还有些其他的比如夹角余弦、汉明距离等就不再介绍了，拜拜～

闵可夫斯基距离

欧式距离

曼哈顿距离

切比雪夫距离

马氏距离

更多相关文章

随机推荐