21 | 机器学习中常见距离度量及实现
文章目录
机器学习中常见距离度量及Python实现
机器学习中常见距离度量及python实现
1. 欧式距离
Euclidean距离是最简单、最易于理解的一种距离计算方法，它基于Euclidean空间中两点之间的距离计算公式。
- 二维平面上两点
a(x1, y1)与b(x2, y2)间的欧式距离
d_{12} =\sqrt [ 2 ]{ (x_1-x_2)^2+(y_1-y_2)^2 }
- 三维空间两点
a(x1, y1, z1)与b(x2, y2, z2)间的欧式距离
d_{ 12 }=\sqrt [ 2 ]{ (x_{ 1 }-x_{ 2 })^{ 2 }+(y_{ 1 }-y_{ 2 })^{ 2 }+(z_1-z_2)^2 }
- 两个n维向量
a(x11, x12, …, x1n)与b(x21, x22, …, x2n)间的欧式距离
d_{ 12 }=\sqrt [ 2 ]{ \sum _{ k=1 }^{ n }{ (x_{1k}-x_{2k} )^2} }
- 若表示成向量运算的形式
d_{ 12 }=\sqrt [ 2 ]{ (a-b)(a-b)^T}
python中实现：
import numpy as np
x = np.random.random(10)
y = np.random.random(10)
# x
array([ 0.2027935 , 0.31394456, 0.1960384 , 0.27455305, 0.73423524,
0.49304154, 0.39459916, 0.93357666, 0.25406378, 0.31207493])
# y
array([ 0.58752716, 0.41383598, 0.30174012, 0.74574908, 0.57339749,
0.32131536, 0.47729764, 0.81684854, 0.24995744, 0.47294776])
方式一：
d1=np.sqrt(np.sum(np.square(x-y)))
# 0.70208042137425797
方式二：
from scipy.spatial.distance import euclidean
euclidean(x, y)
# 0.702080421374258
AI助手2. 曼哈顿距离 Manhattan Distance
在两个十字路口之间的驾驶过程中，实际行驶的路程通常不等于两点间的直线距离，这种距离也被称为城市街区距离，缩写为city block。
- 二维平面两点
a(x1, y1)与b(x2, y2)间的曼哈顿距离
d_{ 12 }=|x_1-x_2| + |y_1-y_2|
- 两个n维向量
a(x11, x12, …, x1n)与b(x21, x22, …, x2n)间的曼哈顿距离
d_{ 12 }=\sum _{ k=1 }^{ n }{ |x_{1k}-x_{2k}| }
python中实现：
方式一：
d1=np.sum(np.abs(x-y))
方式二：
from scipy.spatial.distance import cityblock
cityblock(x, y)
AI助手3. 切比雪夫距离Chebyshev Distance
基于国际象棋的规则，国王从一个格子(x1, y1)移动到另一个格子(x2, y2)所需的最少步数的最小值即为|x2-x1|和|y2-y1|中的较大者。这个最小步数的计算公式即为切比雪夫距离。
- 二维平面两点
a(x1, y1)与b(x2, y2)间的曼哈顿距离
d_{ 12 }=max(\left| x_1 - x_2 \right|, \left| y_1-y_2 \right| )
- 两个n维向量
a(x11, x12, …, x1n)与b(x21, x22, …, x2n)间的切比雪夫距离
d_{ 12 }=\underset { i }{ max} (\left| x_{1i} - x_{2i} \right|)
以上公式等价于：
d_{ 12 }=\lim _{ k\rightarrow \infty }{ (\sum _{ i=1 }^{ n }{ (\left| x_{ 1i }-x_{ 2i } \right| ^{ k }) } )^{ \frac { 1 }{ k } } }
python中实现:
方式一：
d1=np.max(np.abs(x-y))
方式二：
from scipy.spatial.distance import chebyshev
chebyshev(x, y)
AI助手4. 闵可夫斯基距离Minkowski Distance
- 两个n维向量
a(x11, x12, …, x1n)与b(x21, x22, …, x2n)间的闵可夫斯基距离
d_{ 12 }=\sqrt [ p ]{ \sum _{ k=1 }^{ n }{ \left| x_{1k}-x_{2k} \right| ^p } }
在p取值为1时，这种距离计算方式等同于曼哈顿距离。在p取值为2时，这种距离计算方式等同于欧式距离。当p趋向于无穷大时，这种距离计算方式等同于切比雪夫距离。
闵可夫距离均存在明显的缺点：例如：
一个二维样本（身高，体重），其中身高范围是150190，体重范围是5060，具体包括样本a(180,50)、样本b(190,50)和样本c(180,60)。计算发现，样本a与样本b之间的闵氏距离与样本a与样本c之间的闵氏距离相等。然而，身高相差10厘米与体重相差10公斤是否等价？这种衡量样本间相似程度的方法存在明显的缺陷。由此可见，闵氏距离仅将各个维度的量纲视为独立单位，而忽视了各维度分布特征（如均值、方差等）的差异。
python中实现
from scipy.spatial.distance import minkowski
minkowski(x, y, 2)
AI助手5. 标准化欧式距离 Standardized Euclidean distance
针对之前提及的欧式距离的缺点，标准欧式距离是通过将各分量进行标准化处理，使其均值和方差相等，然后计算欧式距离。
- 两个n维向量
a(x11, x12, …, x1n)与b(x21, x22, …, x2n)间的标准欧式距离
d_{ 12 }=\sqrt [ 2 ]{ \sum _{ k=1 }^{ n }{ (\frac { x_{1k}-x_{2k} }{ s_k } )^2 } }
其中Sk为标准差
python中实现
X=np.vstack([x,y])
方式一：
sk=np.var(X,axis=0,ddof=1)
d1=np.sqrt(((x - y) ** 2 /sk).sum())
方式二：
from scipy.spatial.distance import pdist
d2=pdist(X,'seuclidean')
AI助手6. 马氏距离 Mahalanobis Distance
假设有M个样本向量X₁至Xₘ，其协方差矩阵被标记为S，均值则表示为向量μ。则样本向量X至均值向量μ的马氏距离计算式为：
D(X) = \sqrt{2} \cdot (X - \mu)^T S^{-1} (X - \mu)
其中，向量Xᵢ与Xⱼ之间的马氏距离定义为：
D(X_i, X_j) = \sqrt{2} \cdot (X_i - X_j)^T S^{-1} (X_i - X_j)
当协方差矩阵为单位矩阵时，所有样本向量相互独立且同分布，此时马氏距离等同于欧氏距离。若协方差矩阵为对角矩阵，则马氏距离等同于标准化距离。
因此，
在马氏距离的计算过程中，我们假设样本数据基于总体样本的分布特性。具体而言，当我们将两个样本分别放入不同的总体中进行比较时，通常会得到不同的马氏距离值。这是因为马氏距离能够反映两个样本在不同总体中的相对位置关系。
在实际计算过程中，若样本空间的维度低于样本数量，我们可以通过计算欧氏距离来替代马氏距离的计算。这是因为此时的协方差矩阵将无法进行逆运算，导致马氏距离的计算无法进行。
当满足样本空间维度低于样本数量的条件时，如果协方差矩阵仍然无法进行逆运算，这通常是因为样本点之间存在严格的线性关系（如共线性）。在这种情况下，我们仍然可以采用欧氏距离来进行计算，以避免计算上的不稳定性。
在实际应用中，样本空间维度远大于样本数量的情况较为常见，因此马氏距离的计算在大多数场景下是可行的。然而，马氏距离的计算结果对协方差矩阵的性质非常敏感，这一点与欧氏距离存在显著差异。因此，在实际应用中，我们需要特别注意协方差矩阵的性质。
**优点：**马氏距离的一个显著优点是其不受量纲的影响。具体而言，马氏距离的计算结果与原始数据的量纲无关，这使得我们可以对不同量纲的数据进行直接比较。此外，当我们将数据标准化后计算的马氏距离，与对原始数据进行中心化处理后计算的马氏距离是完全一致的。马氏距离的另一个优点是能够有效地排除变量之间的相关性干扰，从而提供更为准确的距离度量。
**缺点：**然而，马氏距离也存在一些局限性。例如，当数据中存在某些变量的变化幅度非常小时，马氏距离可能会对这些变量的变化作出过度反应，从而影响其稳定性。
python中实现
#马氏距离要求样本数要大于维数，否则无法求协方差矩阵
#此处进行转置，表示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)
#方法二：根据scipy库求解
from scipy.spatial.distance import pdist
d2=pdist(XT,'mahalanobis')
AI助手7. 余弦距离 Cosine Distance
余弦相似度在几何学中被用于表征两个向量方向之间的差异程度。在机器学习领域，该方法被采用以度量样本向量之间的差异程度。
余弦距离就是用1减去余弦相似度（余弦公式）
- 二维平面两点
a(x1, y1)与b(x2, y2)间的余弦公式
\cos { \theta } =\frac { x_{ 1 }x_{ 2 }+y_{ 1 }y_{ 2 } }{ \sqrt { x_1^2+y_1^2 } \sqrt { x_2^2+y_2^2 } }
- 两个n维向量
a(x11, x12, …, x1n)与b(x21, x22, …, x2n)间的余弦公式
\cos { \theta } =\frac { \sum _{ k=1 }^{ n }{ x_{ 1k }x_{ 2k } } }{ \sqrt { \sum _{ k=1 }^{ n }{ x_{1k}^2 } } \sqrt { \sum _{ k=1 }^{ n }{ x_{2k}^2 } } }
余弦值的取值范围是[-1,1]。通过计算两个向量之间的夹角，可以得到对应余弦值，该值可用来衡量两向量的相似程度。当夹角越小时，趋近于0度时，余弦值越接近1，表明两向量方向越趋近，相似程度越高。当两向量方向相反时，夹角余弦达到最小值-1；当余弦值为0时，两向量正交，夹角为90度。由此可知，余弦相似度仅受向量方向影响，与幅值无关。
该方法仅关注向量的方向特性，然而该方法存在一个局限性，即在向量平移操作中，若将向量x移至x+1，余弦值会发生变化。
python中实现
代码中为实现余弦相似度
方式一：
d1=np.dot(x,y)/(np.linalg.norm(x)*np.linalg.norm(y))
方式二：
from scipy.spatial.distance import pdist
d2=pdist(X,'seuclidean')
方式三：
from scipy.spatial.distance import cosine
d3 = 1 - cosine(x, y)
AI助手8. 皮尔逊相关系数（Pearson correlation）
如何实现平移不变性？这就要用到相关系数（Corr），有时候也直接叫相关性度量。
python中实现
#方法一：根据公式求解
x_=x-np.mean(x)
y_=y-np.mean(y)
d1=np.dot(x_,y_)/(np.linalg.norm(x_)*np.linalg.norm(y_))
#方法二：根据numpy库求解
X=np.vstack([x,y])
d2=np.corrcoef(X)[0][1]
#方法三：
from scipy.spatial.distance import correlation
d3 = 1 - correlation(x, y)
AI助手9. 汉明距离 Hamming distance
两个等长字符串s₁与s₂之间的汉明距离定义为将其中一个字符串转换为另一个所需进行的最小替换次数。例如，字符串“1111”与“1001”之间的汉明距离计算结果为2。
应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。
python中实现
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_)
#方法二：根据scipy库求解
X=np.vstack([x_,y_])
d2=pdist(X,'hamming')
#方法三:
from scipy.spatial.distance import hamming
hamming(x_, y_)
AI助手10. 杰卡德相似系数 Jaccard similarity coefficient
两个集合A和B的交集元素在A、B的并集中所占的比例，定义为两个集合的杰卡德相似系数，记作J(A,B)。数学表达式为：J(A,B)=\frac { \left| A\cap B \right| }{ \left| A\cup B \right| }。该系数被用作衡量两个集合之间相似程度的标准指标。
与杰卡德相似性系数相对应的概念是**杰卡德距离****(**Jaccard distance)。杰卡德距离的计算可通过以下公式实现：
J_\delta (A,B)=1-J(A,B)=1-\frac { \left| A\cap B \right| }{ \left| A\cup B \right| }
python中实现
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)
#方法二：根据scipy库求解
X=np.vstack([x_,y_])
d2=pdist(X,'jaccard')
#方法三:
from scipy.spatial.distance import jaccard
jaccard(x_, y_)
AI助手11. 布雷柯蒂斯距离 Bray Curtis Distance
Bray Curtis距离常用于生态学和环境科学领域，用于衡量坐标间的差异程度。该距离的取值范围在0到1之间，数值越小表示两者越接近。它同样适用于比较样本间的差异。
a b c d e sum
s29 11 0 7 8 0 26
s30 24 37 5 18 1 85
AI助手\frac { \left| 11-24 \right| +\left| 0-37 \right| +\left| 7-5 \right| +\left| 8-18 \right| +\left| 0-1 \right| }{ 26+85 } =0.568
python中实现
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)
#方法二：根据scipy库求解
X=np.vstack([x,y])
d2=pdist(X,'braycurtis')
#方法三:
from scipy.spatial.distance import braycurtis
braycurtis(x,y)
AI助手12. 编辑距离 Levenshtein Distance
编辑距离指标，也被称作 Levenshtein距离，两个字串之间，最少需要多少编辑操作才能将一个转换为另一个。
允许的编辑操作具体包括：可将一个字符替换为另一个字符，可进行字符插入，可执行字符删除。
例如将eeba转变成abac：
- eba（删除第一个e）
- aba（将剩下的e替换成a）
- abac（在末尾插入c）
所以eeba和abac的编辑距离就是3
它由俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
算法
算法就是简单的线性动态规划（最长上升子序列就属于线性动态规划）。
设我们要将s1变成s2
定义状态矩阵edit[len1][len2]，其中len1和len2分别表示字符串s1和s2的长度加一（其中加一的目的是为了在动态规划中处理一个字符串为空的情况）。
接着，我们用edit[i][j]表示s1的前i个字符构成的子串与s2的前j个字符构成的子串之间的编辑距离。
具体来说，该算法的工作原理是：对于每个i和j，从0开始逐步增加。在每次j的递增过程中，由于已经计算出前j-1个字符与i之间的编辑距离，因此在新增第j个字符时，只需关注新增的第j个字符即可。
**插入操作：**在s1的前i个字符之后添加一个字符ch，其中ch等于新加入的s2[j]。其编辑距离为edit[i][j-1]+1。
删除操作：删除s1[i]的字符，旨在使得s1[i-1]的前面字符能够与s2[j]的前面字符进行匹配（如果前面的几个字符能够与s2[j]的前面的几个字符有较好的匹配，那么这种操作将有助于提高匹配效果）。此外，对于s1[i-1]之前的字符与s2[j]进行匹配的情况，edit[i-1][j]中已经考虑了相关的编辑距离值。因此，删除s1[i]字符后的编辑距离值为edit[i-1][j]+1。
替换操作的计算公式为：假设s1的第i个字符与s2的第j个字符匹配，或者将s1的第i个字符替换为s2的第j个字符后进行匹配。因此，替换操作的编辑距离计算公式为edit[i-1][j-1] + f(i,j)。其中，当s1的第i个字符等于s2的第j个字符时，f(i,j)的值为0；否则，f(i,j)的值为1。
于是动态规划公式如下：
- 当i和j均为0时，edit(i, j)的值为0。
- 当i为0且j大于0时，edit(i, j)的值等于j。
- 当i大于0且j为0时，edit(i, j)的值等于i。
- 当i和j均在0到1之间时，edit(i, j)等于以下三个值的最小值：edit(i-1, j) + 1，edit(i, j-1) + 1，edit(i-1, j-1) + f(i, j)。其中，若第一个字符串的第i个字符与第二个字符串的第j个字符不相同，则f(i, j)的值为1；否则，f(i, j)的值为0。
python中实现
方式一：
按照算法编写，
缺点： 1. 需要一个x，y的矩阵，内存占用多， 2. 若两个样本相同部分很多，做了较多的无效比较。
class arithmetic():
def __init__(self):
pass
''''' 【编辑距离算法】 【levenshtein distance】 【字符串相似度算法】 '''
def levenshtein(self,left,right, gap=1):
pattern = r'.{%d}' % gap #gap决定编辑时的最小单位
left = [word for word in re.findall(pattern, left)]
right = [word for word in re.findall(pattern, right)]
# 左字符串比右字符串大时， 交换左右字符串
if len(left) > len(right):
left,right = right,left
len_left = len(left)
len_right = len(right)
# 左字符串长度为0时，直接返回右字符串的长度作为编辑距离
if len(left) == 0:
return len(right)
# 右字符串长度为0时，直接返回左字符串的长度作为编辑距离
if len(right) == 0:
return len(left)
left_length = len(left) + 1
right_length = len(right) + 1
distance_matrix = [[x + y for y in range(right_length)] for x in range(left_length)]
for i in range(1,left_length):
for j in range(1,right_length):
# 删除操作
deletion = distance_matrix[i-1][j] + 1
# 插入操作
insertion = distance_matrix[i][j-1] + 1
# 替换操作
substitution = distance_matrix[i-1][j-1]
if left[i - 1] != right[j - 1]:
substitution += 1
distance_matrix[i][j] = min(insertion,deletion,substitution)
return distance_matrix[left_length-1][right_length-1]
AI助手优化
方式二：针对算法实现方式1进行优化
class arithmetic():
def __init__(self):
pass
''''' 【编辑距离算法】 【levenshtein distance】 【字符串相似度算法】 '''
def levenshtein(self,left,right, gap=1):
pattern = r'.{%d}' % gap
left = left.upper()
left = [word for word in re.findall(pattern, left)]
right = [word for word in re.findall(pattern, right)]
# 左字符串比右字符串大时， 交换左右字符串
if len(left) > len(right):
left,right = right,left
len_left = len(left)
len_right = len(right)
# 左字符串长度为0时，直接返回右字符串的长度作为编辑距离
if len(left) == 0:
return len(right)
# 右字符串长度为0时，直接返回左字符串的长度作为编辑距离
if len(right) == 0:
return len(left)
# 先删除相同位置的相同字符
for i in range(len_left):
if left[i] == right[i]:
left[i] = ' '
right[i] = ' '
if len_left != len_right:
k = 0
for j in range(len_right - len_left , len_right):
if left[k] == right[j]:
left[k] = ' '
right[j] = ' '
k += 1
while ' ' in left:
left.remove(' ')
while ' ' in right:
right.remove(' ')
if len(left) > len(right):
left,right = right,left
len_left = len(left)
len_right = len(right)
# 左字符串长度为0时，直接返回右字符串的长度作为编辑距离
if len(left) == 0:
return len(right)
# 右字符串长度为0时，直接返回左字符串的长度作为编辑距离
if len(right) == 0:
return len(left)
left_length = len(left) + 1
right_length = len(right) + 1
# 创建一个2*right_length矩阵
distance_matrix = [[ x for x in range(right_length)] for i in range(0 , 2)]
# pprint(distance_matrix)
for i in range(1, left_length):
distance_matrix[1][0] = i
for j in range(1, right_length):
# 删除操作
deletion = distance_matrix[0][j] + 1
# # 插入操作
insertion = distance_matrix[1][j-1] + 1
# # 替换操作
substitution = distance_matrix[0][j-1]
if left[i - 1] != right[j - 1]:
substitution += 1
distance_matrix[1][j] = min(insertion,deletion,substitution)
for j in range(right_length):
distance_matrix[0][j] = distance_matrix[1][j]
# pprint(distance_matrix)
return distance_matrix[0][right_length - 1]
AI助手模块调用
方式三：
使用python-Levenshtein
import Levenshtein
Levenshtein.distance(x,y)
AI助手