用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)