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)间的闵可夫斯基距离定义为：

image

其中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）。

image

(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）。

image

(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）。

image.png

(1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式：

image

(2) 两个n维样本点A (x11,x12,…,x1n)与 B(x21,x22,…,x2n)的夹角余弦 类似的，对于两个n维样本点A(x11,x12,…,x1n)与 B(x21,x22,…,x2n)，可以使用类似于夹角余弦的概念来衡量它们间的相似程度。

image

夹角余弦取值范围为[-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)表示。

image.png

杰卡德相似系数是衡量两个集合的相似度一种指标。

(2) 杰卡德距离

与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。杰卡德距离可用如下公式表示：

image

杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

(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的杰卡德距离表示为：

image

(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中的四个对象所属的类别：以克、天为单位的苹果是水果类别的一个实例; 以吨、年为单位鲨鱼是大型动物的一个实例。这种区别是明显的，但是，如果我们考察颜色这个特征，情况可能会有所不同，苹果和梨都有黄色这个特征，像这种情况我们如何区分呢？

8. 编辑距离（Edit Distance）

编辑距离（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为：

image.png

其中的m为s1, s2匹配的字符数，t是换位的数目。

两个分别来自S1和S2的字符如果相距不超过

image.png

时，我们就认为这两个字符串是匹配的；而这些相互匹配的字符则决定了换位的数目t，简单来说就是不同顺序的匹配字符的数目的一半即为换位的数目t。举例来说，MARTHA与MARHTA的字符都是匹配的，但是这些匹配的字符中，T和H要换位才能把MARTHA变为MARHTA,那么T和H就是不同的顺序的匹配字符，t=2/2=1。

两个字符串的Jaro Distance即为：

image.png

Levenshtein.jaro_winkler(s1, s2)

计算Jaro–Winkler距离，而Jaro-Winkler则给予了起始部分就相同的字符串更高的分数，他定义了一个前缀p，给予两个字符串，如果前缀部分有长度为ι的部分相同，则Jaro-Winkler Distance为：

image.png

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的“标准化变量”表示为：

image

标准化后的值 = ( 标准化前的值 － 分量的均值 ) /分量的标准差

经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式：

image

如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(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的马氏距离表示为：

image

而其中向量Xi与Xj之间的马氏距离定义为：

image

若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：

image

也就是欧氏距离了。

若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。

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) 皮尔逊相关系数的定义

image

前面提到的余弦相似度只与向量方向有关，但它会受到向量的平移影响，在夹角余弦公式中如果将 x 平移到 x+1, 余弦值就会改变。怎样才能实现平移不变性？这就要用到皮尔逊相关系数（Pearson correlation），有时候也直接叫相关系数。

如果将夹角余弦公式写成：

image

表示向量x和向量y之间的夹角余弦，则皮尔逊相关系数则可表示为：

image

皮尔逊相关系数具有平移不变性和尺度不变性，计算出了两个向量（维度）的相关性。

在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]之间。它也可以用来计算样本之间的差异。

image

样本数据：

image

计算：

image

在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