python 各類距離公式實現

給個關注和轉發

所列的距離公式列表和代碼如下：

• 閔可夫斯基距離(Minkowski Distance)
• 歐氏距離(Euclidean Distance)
• 曼哈頓距離(Manhattan Distance)
• 切比雪夫距離(Chebyshev Distance)
• 夾角餘弦(Cosine)
• 漢明距離(Hamming distance)
• 傑卡德相似係數(Jaccard similarity coefficient)
• 編輯距離（Edit Distance）
• 標準化歐氏距離 (Standardized Euclidean distance )
• 馬氏距離(Mahalanobis Distance)
• 皮爾遜相關係數（Pearson correlation）
• 佈雷柯蒂斯距離(Bray Curtis Distance)

讀者可根據自己需求有選擇的學習。因使用矢量編程的方法，距離計算得到了較大的簡化。

1. 閔可夫斯基距離(Minkowski Distance)

嚴格意義上，閔氏距離不是一種距離，而是一組距離的定義。

(1)閔氏距離的定義:

兩個n維變量A(x11,x12,…,x1n)與 B(x21,x22,…,x2n)間的閔可夫斯基距離定義為：

其中p是一個變參數。

當p=1時，就是曼哈頓距離

當p=2時，就是歐氏距離

當p→∞時，就是切比雪夫距離

根據變參數的不同，閔氏距離可以表示一類的距離。

(2)閔氏距離的缺點

閔氏距離，包括曼哈頓距離、歐氏距離和切比雪夫距離都存在明顯的缺點。

舉個例子：二維樣本(身高,體重)，其中身高範圍是150\\~190，體重範圍是50~60，有三個樣本：a(180,50)，b(190,50)，c(180,60)。那麼a與b之間的閔氏距離（無論是曼哈頓距離、歐氏距離或切比雪夫距離）等於a與c之間的閔氏距離，但是身高的10cm真的等價於體重的10kg麼？因此用閔氏距離來衡量這些樣本間的相似度很有問題。

簡單說來，閔氏距離的缺點主要有兩個：

(1)將各個分量的量綱(scale)，也就是“單位”當作相同的看待了。

(2)沒有考慮各個分量的分佈（期望，方差等)可能是不同的。

python中的實現：

# -*- coding:utf-8 -*-
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
#方法一：根據公式求解,p=2
d1=np.sqrt(np.sum(np.square(x-y)))
print('d1:',d1)
#方法二：根據scipy庫求解
from scipy.spatial.distance import pdist
X=np.vstack([x,y])
d2=pdist(X,'minkowski',p=2)[0]
print('d2:',d2)

2.歐氏距離(Euclidean Distance)

歐氏距離（L2範數）是最易於理解的一種距離計算方法，源自歐氏空間中兩點間的距離公式（如圖1.9）。

(4) python實現歐式距離公式的：

# -*- coding: utf-8 -*-
from numpy import *
vector1 = mat([1,2,3])
vector2 = mat([4,5,6])
print (sqrt((vector1-vector2)*((vector1-vector2).T)))
import numpy as np
x = np.random.random(10)
y = np.random.random(10)
# solution1
dist1 = np.linalg.norm(x - y)
# solution2
dist2 = np.sqrt(np.sum(np.square(x - y)))
print('x', x)
print('y', y)
print('dist1:', dist1)
print('dist2:', dist2)
# solution3
from scipy.spatial.distance import pdist
X=np.vstack([x,y])
d2=pdist(X)[0]
print('d2:',d2)

3.曼哈頓距離(Manhattan Distance)

從名字就可以猜出這種距離的計算方法了。想象你在曼哈頓要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。實際駕駛距離就是這個“曼哈頓距離”(L1範數)。而這也是曼哈頓距離名稱的來源，曼哈頓距離也稱為城市街區距離(City Block distance)（如圖1.10）。

(3)python實現曼哈頓距離：

# -*- coding: utf-8 -*-
from numpy import *
vector1 = mat([1,2,3])
vector2 = mat([4,5,6])
print (sum(abs(vector1-vector2)))
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
#方法一：根據公式求解
d1=np.sum(np.abs(x-y))
print('d1:',d1)
#方法二：根據scipy庫求解
from scipy.spatial.distance import pdist
X=np.vstack([x,y])
d2=pdist(X,'cityblock')[0]
print('d2:',d2)

4.切比雪夫距離(Chebyshev Distance)

國際象棋玩過麼？國王走一步能夠移動到相鄰的8個方格中的任意一個（如圖1.11）。那麼國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走試試。你會發現最少步數總是max(| x2-x1| , |y2-y1| ) 步。有一種類似的一種距離度量方法叫切比雪夫距離(L∞範數)。

(3) Python實現切比雪夫距離：

# -*- coding: utf-8 -*-
from numpy import *
vector1 = mat([1,2,3])
vector2 = mat([4,7,5])
print (abs(vector1-vector2).max())
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
#方法一：根據公式求解
d1=np.max(np.abs(x-y))
print('d1:',d1)
#方法二：根據scipy庫求解
from scipy.spatial.distance import pdist
X=np.vstack([x,y])
d2=pdist(X,'chebyshev')[0]
print('d2:',d2)

5. 夾角餘弦(Cosine)

幾何中夾角餘弦可用來衡量兩個向量方向的差異，機器學習中借用這一概念來衡量樣本向量之間的差異（如圖1.12）。

(1)在二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角餘弦公式：

(2) 兩個n維樣本點A (x11,x12,…,x1n)與 B(x21,x22,…,x2n)的夾角餘弦

類似的，對於兩個n維樣本點A(x11,x12,…,x1n)與 B(x21,x22,…,x2n)，可以使用類似於夾角餘弦的概念來衡量它們間的相似程度。

夾角餘弦取值範圍為[-1,1]。夾角餘弦越大表示兩個向量的夾角越小，夾角餘弦越小表示兩向量的夾角越大。當兩個向量的方向重合時夾角餘弦取最大值1，當兩個向量的方向完全相反夾角餘弦取最小值-1。

(3)python實現夾角餘弦

# -*- coding: utf-8 -*-
import numpy as np
from scipy.spatial.distance import pdist
'''
x: [0.05627679 0.80556938 0.48002662 0.24378563 0.75763754 0.15353348
 0.54491664 0.1775408 0.50011986 0.55041845]
y: [0.50068882 0.12200178 0.79041352 0.07332715 0.017892 0.57880032
 0.56707591 0.48390753 0.631051 0.20035466]
'''
x = np.random.random(10)
y = np.random.random(10)
# solution1
dist1 = 1 - np.dot(x, y) / (np.linalg.norm(x) * np.linalg.norm(y))
# solution2
dist2 = pdist(np.vstack([x, y]), 'cosine')[0]
print('x', x)
print('y', y)
print('dist1:', dist1)
print('dist2:', dist2)

6. 漢明距離(Hamming distance)

(1)漢明距離的定義

兩個等長字符串s1與s2之間的漢明距離定義為將其中一個變為另外一個所需要作的最小替換次數。例如字符串“1111”與“1001”之間的漢明距離為2。

應用：信息編碼（為了增強容錯性，應使得編碼間的最小漢明距離儘可能大）。

(2) python實現漢明距離：

# -*- coding: utf-8 -*-
from numpy import *
matV = mat([[1,1,0,1,0,1,0,0,1],[0,1,1,0,0,0,1,1,1]])
smstr = nonzero(matV[0]-matV[1])
print(shape(smstr[0])[0])
import numpy as np
from scipy.spatial.distance import pdist
x=np.random.random(10)>0.5
y=np.random.random(10)>0.5
x=np.asarray(x,np.int32)
y=np.asarray(y,np.int32)
#方法一：根據公式求解
d1=np.mean(x!=y)
print('d1:', d1)
#方法二：根據scipy庫求解
X=np.vstack([x,y])
d2=pdist(X,'hamming')[0]
print('d2:', d2)

7. 傑卡德相似係數(Jaccard similarity coefficient)

(1) 傑卡德相似係數

兩個集合A和B的交集元素在A，B的並集中所佔的比例，稱為兩個集合的傑卡德相似係數，用符號J(A,B)表示。

傑卡德相似係數是衡量兩個集合的相似度一種指標。

(2) 傑卡德距離

與傑卡德相似係數相反的概念是傑卡德距離(Jaccard distance)。傑卡德距離可用如下公式表示：

傑卡德距離用兩個集合中不同元素佔所有元素的比例來衡量兩個集合的區分度。

(3) 傑卡德相似係數與傑卡德距離的應用

可將傑卡德相似係數用在衡量樣本的相似度上。

樣本A與樣本B是兩個n維向量，而且所有維度的取值都是0或1。例如：A(0111)和B(1011)。我們將樣本看成是一個集合，1表示集合包含該元素，0表示集合不包含該元素。

P：樣本A與B都是1的維度的個數

q：樣本A是1，樣本B是0的維度的個數

r：樣本A是0，樣本B是1的維度的個數

s：樣本A與B都是0的維度的個數

那麼樣本A與B的傑卡德相似係數可以表示為：

這裡p+q+r可理解為A與B的並集的元素個數，而p是A與B的交集的元素個數。

而樣本A與B的傑卡德距離表示為：

(4) Python實現傑卡德距離：

# -*- coding: utf-8 -*-
from numpy import *
from scipy.spatial.distance import pdist # 導入scipy距離公式
matV = mat([[1,1,0,1,0,1,0,0,1],[0,1,1,0,0,0,1,1,1]])
print ("dist.jaccard:", pdist(matV,'jaccard'))
import numpy as np
from scipy.spatial.distance import pdist
x = np.random.random(10) > 0.5
y = np.random.random(10) > 0.5
x = np.asarray(x, np.int32)
y = np.asarray(y, np.int32)
# 方法一：根據公式求解
up = np.double(np.bitwise_and((x != y), np.bitwise_or(x != 0, y != 0)).sum())
down = np.double(np.bitwise_or(x != 0, y != 0).sum())
d1 = (up / down)
print('d1:', d1)
# 方法二：根據scipy庫求解
X = np.vstack([x, y])
d2 = pdist(X, 'jaccard')[0]
print('d2:', d2)

現在，我們有能力為矩陣中對象間的相似程度(接近與遠離)提供各種度量方法，以及編碼實現。通過計算對象間的距離，我們就可以輕鬆地得到表2.8中的四個對象所屬的類別：以克、天為單位的蘋果是水果類別的一個實例; 以噸、年為單位鯊魚是大型動物的一個實例。這種區別是明顯的，但是，如果我們考察顏色這個特徵，情況可能會有所不同，蘋果和梨都有黃色這個特徵，像這種情況我們如何區分呢？

編輯距離（Edit Distance），又稱Levenshtein距離，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。一般來說，編輯距離越小，兩個串的相似度越大。

例如將kitten一字轉成sitting：（’kitten’ 和 ‘sitting’ 的編輯距離為3）

sitten （k→s）

sittin （e→i）

sitting （→g）

Python中的Levenshtein包可以方便的計算編輯距離

包的安裝： pip install python-Levenshtein

我們來使用下：

# -*- coding:utf-8 -*-
import Levenshtein
texta = '艾倫 圖靈傳'
textb = '艾倫•圖靈傳'
print Levenshtein.distance(texta,textb)

上面的程序執行結果為3，但是隻改了一個字符，為什麼會發生這樣的情況？

原因是Python將這兩個字符串看成string類型，而在 string 類型中，默認的 utf-8 編碼下，一箇中文字符是用三個字節來表示的。

解決辦法是將字符串轉換成unicode格式，即可返回正確的結果1。

# -*- coding:utf-8 -*-
import Levenshtein
texta = u'艾倫 圖靈傳'
textb = u'艾倫•圖靈傳'
print Levenshtein.distance(texta,textb)

接下來重點介紹下保重幾個方法的作用：

Levenshtein.distance(str1, str2)

計算編輯距離（也稱Levenshtein距離）。是描述由一個字串轉化成另一個字串最少的操作次數，在其中的操作包括插入、刪除、替換。算法實現：動態規劃。

Levenshtein.hamming(str1, str2)

計算漢明距離。要求str1和str2必須長度一致。是描述兩個等長字串之間對應位置上不同字符的個數。

Levenshtein.ratio(str1, str2)
 

計算萊文斯坦比。計算公式 r = (sum – ldist) / sum, 其中sum是指str1 和 str2 字串的長度總和，ldist是類編輯距離。注意這裡是類編輯距離，在類編輯距離中刪除、插入依然+1，但是替換+2。

Levenshtein.jaro(s1, s2)

計算jaro距離，Jaro Distance據說是用來判定健康記錄上兩個名字是否相同，也有說是是用於人口普查，我們先來看一下Jaro Distance的定義。

兩個給定字符串S1和S2的Jaro Distance為：

其中的m為s1, s2匹配的字符數，t是換位的數目。

兩個分別來自S1和S2的字符如果相距不超過

時，我們就認為這兩個字符串是匹配的；而這些相互匹配的字符則決定了換位的數目t，簡單來說就是不同順序的匹配字符的數目的一半即為換位的數目t。舉例來說，MARTHA與MARHTA的字符都是匹配的，但是這些匹配的字符中，T和H要換位才能把MARTHA變為MARHTA,那麼T和H就是不同的順序的匹配字符，t=2/2=1。

兩個字符串的Jaro Distance即為：

Levenshtein.jaro_winkler(s1, s2)

計算Jaro–Winkler距離，而Jaro-Winkler則給予了起始部分就相同的字符串更高的分數，他定義了一個前綴p，給予兩個字符串，如果前綴部分有長度為ι的部分相同，則Jaro-Winkler Distance為：

dj是兩個字符串的Jaro Distance

ι是前綴的相同的長度，但是規定最大為4

p則是調整分數的常數，規定不能超過25，不然可能出現dw大於1的情況，Winkler將這個常數定義為0.1

這樣，上面提及的MARTHA和MARHTA的Jaro-Winkler Distance為：

dw = 0.944 + (3 * 0.1(1 − 0.944)) = 0.961

9. 標準化歐氏距離 (Standardized Euclidean distance )

(1)標準歐氏距離的定義

標準化歐氏距離是針對簡單歐氏距離的缺點而作的一種改進方案。標準歐氏距離的思路：既然數據各維分量的分佈不一樣，好吧！那我先將各個分量都“標準化”到均值、方差相等吧。均值和方差標準化到多少呢？這裡先複習點統計學知識吧，假設樣本集X的均值(mean)為m，標準差(standard deviation)為s，那麼X的“標準化變量”表示為：

標準化後的值 = ( 標準化前的值 － 分量的均值 ) /分量的標準差

經過簡單的推導就可以得到兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的標準化歐氏距離的公式：

如果將方差的倒數看成是一個權重，這個公式可以看成是一種加權歐氏距離(Weighted Euclidean distance)。

python中的實現：

# -*- coding: utf-8 -*-
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
X=np.vstack([x,y])
#方法一：根據公式求解
sk=np.var(X,axis=0,ddof=1)
d1=np.sqrt(((x - y) ** 2 /sk).sum())
print('d1:',d1)
#方法二：根據scipy庫求解
from scipy.spatial.distance import pdist
d2=pdist(X,'seuclidean')[0]
print('d2:',d2)

10. 馬氏距離(Mahalanobis Distance)

（1）馬氏距離定義

有M個樣本向量X1~Xm，協方差矩陣記為S，均值記為向量μ，則其中樣本向量X到u的馬氏距離表示為：

而其中向量Xi與Xj之間的馬氏距離定義為：

若協方差矩陣是單位矩陣（各個樣本向量之間獨立同分布）,則公式就成了：

也就是歐氏距離了。

若協方差矩陣是對角矩陣，公式變成了標準化歐氏距離。

python 中的實現：

# -*- coding: utf-8 -*-
import numpy as np
x = np.random.random(10)
y = np.random.random(10)
# 馬氏距離要求樣本數要大於維數，否則無法求協方差矩陣
# 此處進行轉置，表示10個樣本，每個樣本2維
X = np.vstack([x, y])
XT = X.T
# 方法一：根據公式求解
S = np.cov(X) # 兩個維度之間協方差矩陣
SI = np.linalg.inv(S) # 協方差矩陣的逆矩陣
# 馬氏距離計算兩個樣本之間的距離，此處共有10個樣本，兩兩組合，共有45個距離。
n = XT.shape[0]
d1 = []
for i in range(0, n):
 for j in range(i + 1, n):
 delta = XT[i] - XT[j]
 d = np.sqrt(np.dot(np.dot(delta, SI), delta.T))
 d1.append(d)
print('d1:', d1)
# 方法二：根據scipy庫求解
from scipy.spatial.distance import pdist
d2 = pdist(XT, 'mahalanobis')
print('d2:',d2)

馬氏優缺點：

1）馬氏距離的計算是建立在總體樣本的基礎上的，這一點可以從上述協方差矩陣的解釋中可以得出，也就是說，如果拿同樣的兩個樣本，放入兩個不同的總體中，最後計算得出的兩個樣本間的馬氏距離通常是不相同的，除非這兩個總體的協方差矩陣碰巧相同；

2）在計算馬氏距離過程中，要求總體樣本數大於樣本的維數，否則得到的總體樣本協方差矩陣逆矩陣不存在，這種情況下，用歐式距離計算即可。

3）還有一種情況，滿足了條件總體樣本數大於樣本的維數，但是協方差矩陣的逆矩陣仍然不存在，比如三個樣本點（3，4），（5，6）和（7，8），這種情況是因為這三個樣本在其所處的二維空間平面內共線。這種情況下，也採用歐式距離計算。

4）在實際應用中“總體樣本數大於樣本的維數”這個條件是很容易滿足的，而所有樣本點出現3）中所描述的情況是很少出現的，所以在絕大多數情況下，馬氏距離是可以順利計算的，但是馬氏距離的計算是不穩定的，不穩定的來源是協方差矩陣，這也是馬氏距離與歐式距離的最大差異之處。

優點：它不受量綱的影響，兩點之間的馬氏距離與原始數據的測量單位無關；由標準化數據和中心化數據(即原始數據與均值之差）計算出的二點之間的馬氏距離相同。馬氏距離還可以排除變量之間的相關性的干擾。缺點：它的缺點是誇大了變化微小的變量的作用。

11. 皮爾遜相關係數（Pearson correlation）

(1) 皮爾遜相關係數的定義

前面提到的餘弦相似度只與向量方向有關，但它會受到向量的平移影響，在夾角餘弦公式中如果將 x 平移到 x+1, 餘弦值就會改變。怎樣才能實現平移不變性？這就要用到皮爾遜相關係數（Pearson correlation），有時候也直接叫相關係數。

如果將夾角餘弦公式寫成：

表示向量x和向量y之間的夾角餘弦，則皮爾遜相關係數則可表示為：

皮爾遜相關係數具有平移不變性和尺度不變性，計算出了兩個向量（維度）的相關性。

在python中的實現：

# -*- coding: utf-8 -*-
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
#方法一：根據公式求解 

x_=x-np.mean(x)
y_=y-np.mean(y)
d1=np.dot(x_,y_)/(np.linalg.norm(x_)*np.linalg.norm(y_))
print('d1:', d1)
#方法二：根據numpy庫求解
X=np.vstack([x,y])
d2=np.corrcoef(X)[0][1]
print('d2:', d2)

相關係數是衡量隨機變量X與Y相關程度的一種方法，相關係數的取值範圍是[-1,1]。相關係數的絕對值越大，則表明X與Y相關度越高。當X與Y線性相關時，相關係數取值為1（正線性相關）或-1（負線性相關）。

12. 佈雷柯蒂斯距離(Bray Curtis Distance)

Bray Curtis距離主要用於生態學和環境科學，計算座標之間的距離。該距離取值在[0,1]之間。它也可以用來計算樣本之間的差異。

樣本數據：

計算：

在python中的實現：

# -*- coding: utf-8 -*-
import numpy as np
from scipy.spatial.distance import pdist
x = np.array([11, 0, 7, 8, 0])
y = np.array([24, 37, 5, 18, 1])
# 方法一：根據公式求解
up = np.sum(np.abs(y - x))
down = np.sum(x) + np.sum(y)
d1 = (up / down)
print('d1:', d1)
# 方法二：根據scipy庫求解
X = np.vstack([x, y])
d2 = pdist(X, 'braycurtis')[0]
print('d2:', d2)

個人覺得算法可以完善的點：

去除停用詞（主要是標點符號的影響）

針對中文進行分析，按照詞比較是不是要比按照字比較效果更好？

參考：https://blog.csdn.net/guojingjuan/article/details/50396254

https://www.jb51.net/article/98449.htm

https://blog.csdn.net/mr_evanchen/article/details/77511312

http://www.cnblogs.com/denny402/p/7027954.html