常见距离算法

机器学习中有很多的距离计算公式，用于计算数据和数据之间的距离，进而计算相似度或者其他。

1. 欧式距离(Euclidean Distance)

​ 欧式距离是最常见的距离度量方法。小学、初中、高中接触到的两个点在空间中的距离一般都是指欧式距离。

举例：

X=[[1,1],[2,2],[3,3],[4,4]];
经计算得:(2-1,3-1,4-1,3-2,4-2,4-3)
d = 1.4142    2.8284    4.2426    1.4142    2.8284    1.4142

python求该距离：

testData=[1, 1]
testData2=[4, 4]
dist = np.linalg.norm(np.array(testData2) - np.array(testData))
print(dist)
print(round(dist, 2))
'''
4.242640687119285
4.24
'''

2. 曼哈顿距离(Manhattan Distance)

​ 在曼哈顿街区要从一个十字路口开车到另一个十字路口，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance)。

举例子：(2-1,3-1,4-1,3-2,4-2,4-3)

X=[[1,1],[2,2],[3,3],[4,4]];
经计算得:
d =   2     4     6     2     4     2

python计算：

testData=[1, 1]
testData2=[4, 4.5]

op3=np.sum(np.abs(np.array(testData)-np.array(testData2)))
op4=np.linalg.norm(np.array(testData)-np.array(testData2),ord=1)
print(op3)
print(op4)
'''
6.5
6.5
'''

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

​ 国际象棋中，国王可以直行、横行、斜行，所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？这个距离就叫切比雪夫距离。

举例：

X=[[1,1],[2,2],[3,3],[4,4]];
经计算得:
d =   1     2     3     1     2     1

python计算：

import numpy as np

vector1 = np.array([1, 1])
vector2 = np.array([4, 4])
op5 = np.abs(vector1 - vector2).max()
op6 = np.linalg.norm(vector1 - vector2, ord=np.inf)
print(op5)
print(op6)
'''
3
3.0
'''

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

​ 该距离不是一种距离，而是一组距离的定义，是对多个距离度量工时的概括性的表述。

两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：

其中，P是一个可变参数

p=1是曼哈顿距离

P=2是欧式距离

P->无穷大时是切比学府距离

根据p的不同，闵氏距离可以表示某一类/种的距离。

小结： 上面四个距离存在的缺点：

(1). 二维样本身高和体重单位不是，一个是cm、一个是kg，实际上10cm不等于10kg，但是上面计算是没有考虑的。

(2). 未考虑各个分量的分布（期望，方差等）可能是不同的

5. 标准化欧式距离(Stangardized Euclidean Distance)

标准化欧式距离是针对欧式距离的缺点做的改进。 先将各个分量"标准化"到均值、方差等。

Sk表示各个维度的标准差

如果将方差的倒数看成一个权重，也可称之为加权欧氏距离(Weighted Euclidean distance)。

举例:

X=[[1,1],[2,2],[3,3],[4,4]];（假设两个分量的标准差分别为0.5和1）
经计算得:
d =   2.2361    4.4721    6.7082    2.2361    4.4721    2.2361

6. 余弦距离(Cosine Diatance)

几何中，夹角余弦可用来衡量两个向量方向的差异；机器学习中，借用这一概念来衡量样本向量之间的差异。

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

• 两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦为：

也就是：

​ 夹角余弦取值范围为[-1,1]。余弦越大表示两个向量的夹角越小，余弦越小表示两向量的夹角越大。当两个向量的方向重合时余弦取最大值1，当两个向量的方向完全相反余弦取最小值-1。

举例：

X=[[1,1],[1,2],[2,5],[1,-4]]
经计算得:
d =   0.9487    0.9191   -0.5145    0.9965   -0.7593   -0.8107

python 计算：

import numpy as np

vector1 = np.array([1, 1])
vector2 = np.array([1, 2])
op7 = np.dot(vector1, vector2) / (np.linalg.norm(vector1) * (np.linalg.norm(vector2)))
print(op7)
'''
0.9486832980505138
'''

此算法也可以用来计算相似度，余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，这就叫"余弦相似性"。

7. 汉明距离(Hamming Distance)

两个等长字符串s1与s2的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。

python 计算：

import numpy as np

v1=np.array([1,1,0,1,0,1,0,0,1])
v2=np.array([0,1,1,0,0,0,1,1,1])
smstr=np.nonzero(v1-v2)
print(smstr) # 不为0 的元素的下标
sm= np.shape(smstr[0])[0]
print( sm )

汉明重量：

​ 是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。因此，如果向量空间中的元素a和b之间的汉明距离等于它们汉明重量的差a-b。

​ 应用：汉明重量分析在包括信息论、编码理论、密码学等领域都有应用。比如在信息编码过程中，为了增强容错性，应使得编码间的最小汉明距离尽可能大。但是，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离等算法。

举例：

X=[[0,1,1],[1,1,2],[1,5,2]]
注：以下计算方式中，把2个向量之间的汉明距离定义为2个向量不同的分量所占的百分比。

经计算得:
d =   0.6667    1.0000    0.3333

8. 杰卡德距离(Jaccard Distance)

​ 通过交并集进行计算。两个集合的交集在并集中所占的比例，称为杰卡德相似系数。

杰卡德距离(Jaccard Distance)：与杰卡德相似系数相反，用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度：

举例：

X=[[1,1,0][1,-1,0],[-1,1,0]]
注：以下计算中，把杰卡德距离定义为不同的维度的个数占“非全零维度”的比例
经计算得:
d =   0.5000    0.5000    1.0000

总结：

1. 欧式距离：通过距离平方值进行计算
2. 曼哈顿距离：通过距离的绝对值求和进行计算
3. 切比雪夫距离：维度的最大值进行计算
4. 闵可夫斯基距离：一个距离的统称

p=1是曼哈顿距离
P=2是欧式距离
P->无穷大时是切比雪夫距离

上面几个距离将单位同等看待，计算过程不是很科学

5. 标准化欧式距离：计算过程中添加了标准差
6. 余弦距离：通过cos思想完成
7. 汉明距离：一个字符串变成另一个字符串需要经过几个字母进行计算
8. 杰卡德距离：通过交集并集计算