机器学习中不同的距离定义汇总（一：空间中点的距离）

本文主要参考了此博客和文末列出的参考内容

图片来源：csdn

欧几里得距离（Euclidean Distance）

n维空间中的距离：

\[ d(x,y)=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\dots+(x_n-y_n)^2} \]

2维空间中：

\[ d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2} \]

python实现：

def EuclideanDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    return np.sqrt(np.sum(np.square(x-y)))

曼哈顿距离（Manhattan Distance）

从曼哈顿街区的一点到另一点：

二维空间： $\( d(x,y)=|x_1-y_1| + |x_2-y_2| \)$

n维空间： $\( d(x,y)=\sum_{i=1}^n{|x_i-y_1|} \)$

python实现：

def ManhattanDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    return np.sum(np.abs(x-y))

闵可夫斯基距离/明氏距离（Minkowski Distance）

n维空间：

\[ d(x,y)=(\sum_{i=1}^n(x_i-y_i)^p)^{\frac{1}{p}} \]

python实现：

def MinkowskiDistance(x, y, p):
    import math
    import numpy as np
    zipped_coordinate = zip(x, y)
    return math.pow(np.sum([math.pow(np.abs(i[0]-i[1]), p) for i in zipped_coordinate]), 1/p)

切比雪夫距离（Chebyshev Distance）

公式： $\( D(x,y)=\max(|x_i-y_i|) \)$

python实现：

def ChebyshevDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    return np.max(np.abs(x-y))

标准化的欧几里得距离（Standardized Euclidean Distance）

将各个分量都“标准化”到均值、方差相等的区间：

\[ X^*=\frac{X-m}{s} \]

其中，\(X^*\)为标准化后的值，\(X\)为原值，\(m\)为分量的均值，\(s\)为分量的标准差。

所以，n维空间中标准化欧几里得距离为：

\[ d(x,y)=\sqrt{\sum_{i=1}^n(\frac{x_i-y_i}{s_i})^2} \]

python代码：

def StandardizedEuclideanDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    
    X = np.vstack([x,y])
    sigma = np.var(X, axis=0, ddof=1)
    return np.sqrt(((x - y) ** 2 /sigma).sum())

上述代码中需要避免某个分量取值一致，即该分量sigma=0

马氏距离（Mahalanobis Distance）

考虑下面这张图，椭圆表示等高线，从欧几里得的距离来算，绿黑距离大于红黑距离，但是从马氏距离，结果恰好相反：

马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性和尺度不同的性质。下图是一个二元变量数据的散点图：

当我们将坐标轴拿掉，如下图：

根据数据本身的提示信息来引入新的坐标轴：坐标的原点在这些点的中央（根据点的平均值算得）。第一个坐标轴（下图中蓝色的线）沿着数据点的“脊椎”，并向两端延伸，定义为使得数据方差最大的方向。第二个坐标轴（下图红色的线）会与第一个坐标轴垂直并向两端延伸。如果数据的维度超过了两维，那就选择使得数据方差是第二个最大的方向，以此类推。

我们需要一个比例尺度。沿着每一个坐标轴的标准差来定义一个单位长度。使用“68-95-99.7法则”更容易找到合理的单位。（大约68%的点需要在离原点一个单位长度的范围内；大约95%的点需要在离原点两个单位的长度范围内；99.7的点需要在3个单位程度范围内。）为了以示参考，如下图：

由于每个轴上的单位长度不相等，所以上图中距离原点一个单位的形成的轨迹并不是一个圆形。为了更好的呈现图表，我们将图片进行旋转。同时，并让每个轴方向上的单位长度相同：

上面就是从散点图中构建坐标系统的过程，为的是方便进行测量。说明：

沿着新坐标轴的单位向量是协方差矩阵的特征向量。注意到没有变形的椭圆，变成圆形后沿着特征向量用标准差（协方差的平方根）将距离长度分割。 坐标轴扩展的量是协方差矩阵的逆的特征值（平方根），同理的，坐标轴缩小的量是协方差矩阵的特征值。所以，点越分散，需要的将椭圆转成圆的缩小量就越多。 尽管上述的操作可以用到任何数据上，但是对于多元正态分布的数据表现更好。在其他情况下，点的平均值或许不能很好的表示数据的中心，或者数据的“脊椎”（数据的大致趋势方向）不能用变量作为概率分布测度来准确的确定。 原始坐标系的平移、旋转，以及坐标轴的伸缩一起形成了仿射变换（affine transformation）。除了最开始的平移之外，其余的变换都是基底变换，从原始的一个变为新的一个。 在新的坐标系中，多元正态分布像是标准正太分布，当将变量投影到任何一条穿过原点的坐标轴上。特别是，在每一个新的坐标轴上，它就是标准正态分布。从这点出发来看，多元正态分布彼此之实质性的差异就在于它们的维度。

单个数据点的马氏距离：

\[ D_M(x)=\sqrt{\left.(x-\mu)^{T} \Sigma^{-1}(x-\mu)\right)} \]

数据点x, y之间的马氏距离: $\( D_M(x, y)=\sqrt{\left.(x-y)^{T} \Sigma^{-1}(x-y)\right)} \)$

马氏距离是旋转变换缩放之后的欧式距离，所以马氏距离的计算公式为：

\[ \begin{aligned} &D_{M}=\left(\frac{f_{1}-\mu_{F_{1}}}{\sqrt{\lambda_{1}}}\right)^{2}+\left(\frac{f_{2}-\mu_{F_{2}}}{\sqrt{\lambda_{2}}}\right)^{2}+\ldots+\left(\frac{f_{m}-\mu_{F_{m}}}{\sqrt{\lambda_{m}}}\right)^{2}\\ \end{aligned} \]

\[ \begin{aligned} &=\left(f-\mu_{F}\right)^{T}\left(U^{T} \Sigma_{X} U\right)^{-1}\left(f-\mu_{F}\right)\\ &=\left(x-\mu_{X}\right)^{T} U U^{T} \Sigma_{X}^{-1} U U^{T}\left(x-\mu_{X}\right)\\ &=\left(x-\mu_{X}\right)^{T} \Sigma_{X}^{-1}\left(x-\mu_{X}\right) \end{aligned} \]

python实现：

def MahalanobisDistance(x, y):
    '''
    马氏居立中的(x,y)与欧几里得距离的(x,y)不同,欧几里得距离中的(x,y)指2个样本，每个样本的维数为x或y的维数；这里的(x,y)指向量是2维的，样本个数为x或y的维数，若要计算n维变量间的马氏距离则需要改变输入的参数如(x,y,z)为3维变量。
    '''
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    
    X = np.vstack([x,y])
    X_T = X.T
    sigma = np.cov(X)
    sigma_inverse = np.linalg.inv(sigma)
    
    d1=[]
    for i in range(0, X_T.shape[0]):
        for j in range(i+1, X_T.shape[0]):
            delta = X_T[i] - X_T[j]
            d = np.sqrt(np.dot(np.dot(delta,sigma_inverse),delta.T))
            d1.append(d)
        
    return d1

兰氏距离（Lance and Williams Distance）/ 堪培拉距离（Canberra Distance）

n维空间:

\[ d(x, y)=\sum_{i=1}^{n} \frac{\left|x_{i}-y_{i}\right|}{\left|x_{i}\right|+\left|y_{i}\right|} \]

python实现：

def CanberraDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    n = len(x)
    d = 0
    for i in range(len(x)):
        if x[i] == 0 and y[i] == 0:
            d += 0
        else:
            d += abs(x[i] - y[i]) / (abs(x[i]) + abs(y[i]))
    return d

余弦距离（Cosine Distance）

\[ \cos (x, y)=\frac{x \cdot y}{|x| \cdot|y|}=\frac{\sum_{i=1}^{n} x_{i} y_{i}}{\sqrt{\sum_{i=1}^{n} x_{i}^{2}} \sqrt{\sum_{i=1}^{n} y_{i}^{2}}} \]

python实现：

def CosineDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    return np.dot(x,y)/(np.linalg.norm(x)*np.linalg.norm(y))

测地距离（Geodesic Distance）

在三维网格中，Geodesic Distance 就是两顶点沿网格表面最短路径的距离。如下图所示，标注出的绿色线段长度就是顶点 vs 到顶点 vt 的 Geodesic Distance。

布雷柯蒂斯距离（Bray Curtis Distance）

布雷柯蒂斯距离（Bray Curtis Distance）主要用于生态学和环境科学，计算坐标之间的距离。该距离取值在[ 0 , 1 ] [0,1][0,1]之间，也可以用来计算样本之间的差异。n nn维空间中的布雷柯蒂斯距离为：

\[ d(x, y)=\frac{\sum_{i=1}^{n}\left|x_{i}-y_{i}\right|}{\sum_{i=1}^{n} x_{i}+\sum_{i=1}^{n} y_{i}} \]

python实现：

def BrayCurtisDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    return np.sum(np.abs(x-y))/(np.sum(x)+np.sum(y))

参考资料