用Numpy实现常见距离度量

2020 年 4 月 19 日
AI

设 $x$ 和 $y$ 为两个向量，求它们之间的距离。

这里用Numpy实现，设 $x$ 和 $y$ 为ndarray <numpy.ndarray>，它们的shape都是(N,)

$d$ 为所求的距离，是个浮点数（float）。

import numpy as np

1.欧氏距离(Euclidean distance)

欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

$d(\mathbf{x}, \mathbf{y}) = \sqrt{ \sum_i (x_i - y_i)^2 } \\$

def euclidean(x, y):

    return np.sqrt(np.sum((x - y)**2))

2.曼哈顿距离(Manhattan distance)

想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(City Block distance)。

$d(\mathbf{x}, \mathbf{y}) = \sum_i |x_i - y_i| \\$

def manhattan(x, y):

    return np.sum(np.abs(x - y))

3.切比雪夫距离(Chebyshev distance)

在数学中，切比雪夫距离（Chebyshev distance）或是L∞度量，是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。以数学的观点来看，切比雪夫距离是由一致范数（uniform norm）（或称为上确界范数）所衍生的度量，也是超凸度量（injective metric space）的一种。

$d(\mathbf{x}, \mathbf{y}) = \max_i |x_i - y_i| \\$

def chebyshev(x, y):

    return np.max(np.abs(x - y))

4.闵可夫斯基距离(Minkowski distance)

闵氏空间指狭义相对论中由一个时间维和三个空间维组成的时空，为俄裔德国数学家闵可夫斯基(H.Minkowski,1864-1909)最先表述。他的平坦空间（即假设没有重力，曲率为零的空间）的概念以及表示为特殊距离量的几何学是与狭义相对论的要求相一致的。闵可夫斯基空间不同于牛顿力学的平坦空间。

$d(\mathbf{x}, \mathbf{y}) = \left( \sum_i |x_i - y_i|^p \right)^{1/p} \\$

def minkowski(x, y, p):

    return np.sum(np.abs(x - y) ** p) ** (1 / p)

5.汉明距离(Hamming distance)

汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量，我们以 $d(x,y)$ 表示两个字 $x$ , $y$ 之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。

$d(\mathbf{x}, \mathbf{y}) = \frac{1}{N} \sum_i \mathbb{1}_{x_i \neq y_i} \\$

def hamming(x, y):

    return np.sum(x != y) / len(x)