机器学习中常见的相似度衡量方法及代码实现
- 欧式距离（Euclidean Distance）
- 曼哈顿距离(Manhattan Distance)
- 切比雪夫距离(Chebyshev Distance)
- 明可夫斯基距离(Minkowski Distance)
- 余弦距离(Cosine)
- 杰卡德相似系数(Jaccard Similarity Coefficient) & 杰卡德距离(Jaccard Distance)
- 汉明距离(Hamming Distance)
在数据挖掘和机器学习中，经常会碰到相似性度量，本文总结常见的几种方法，并用Python和Numpy实现。部分图片和代码来自这篇文章FIVE MOST POPULAR SIMILARITY MEASURES IMPLEMENTATION IN PYTHON
欧式距离（Euclidean Distance）
数学表达式
多维空间的两点$a(x_{1,1},…x_{1,n})$, $b(y_{2,1}… y_{2,n})$之间的欧式距离：\(d_{1,2}=\sqrt{\sum_{k=1}^{n}\left(x_{1 k}-x_{2 k}\right)^{2}}\)
二维空间的两点$a(x_1, y_1)$, $b(x_2, y_2)$之间的欧式距离：\(d_{1,2}=\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}}\)
Python代码实现
from math import *
def euclidean_distance(x, y):
return sqrt(sum(pow(a - b, 2) for a, b in zip(x, y)))
print(euclidean_distance([0, 3, 4, 5], [7, 6, 3, -1]))
9.746794344808963
Numpy代码实现
import numpy as np
def euclidean_distance_numpy(x, y):
return np.linalg.norm(x - y)
# return np.sqrt(np.sum(np.square(x-y)))
print(euclidean_distance_numpy(np.array([0, 3, 4, 5]), np.array([7, 6, 3, -1])))
9.746794344808963
曼哈顿距离(Manhattan Distance)
曼哈顿距离又名城市街区距离
数学表达式
多维空间的两点$a(x_{1,1},…x_{1,n})$, $b(y_{2,1}… y_{2,n})$之间的曼哈顿距离：\(d_{1,2}=\sum_{k=1}^{n}\left|x_{1 k}-x_{2 k}\right|\)
二维空间的两点$a(x_1, y_1)$, $b(x_2, y_2)$之间的曼哈顿距离： \(d_{1,2}=\left|x_{1}-x_{2}\right|+\left|y_{1}-y_{2}\right|\)
Python代码实现
from math import*
def manhattan_distance(x,y):
return sum(abs(a-b) for a,b in zip(x,y))
print(manhattan_distance([10,20,10],[10,20,20]))
10
Numpy代码实现
import numpy as np
def manhattan_distance_numpy(x,y):
return np.linalg.norm(x-y, ord=1)
# return np.sum(np.abs(x-y))
print(manhattan_distance_numpy(np.array([10,20,10]),np.array([10,20,20])))
10.0
切比雪夫距离(Chebyshev Distance)
玩过国际象棋的都知道，国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子 $(x_1, y_1)$走到格子 $(x_2, y_2)$ 最少需要多少步？你会发现最少步数总是$\max \left(\left|x_{1}-x_{2}\right|,\left|y_{1}-y_{2}\right|\right)$ 步 。有一种类似的一种距离度量方法叫切比雪夫距离。
数学表达式
多维空间的两点$a(x_{1,1},…x_{1,n})$, $b(y_{2,1}… y_{2,n})$之间的切比雪夫距离：\(d_{1,2}=\max _{i}\left(\left|x_{1 i}-x_{2 i}\right|\right)\)
等价于 \(d_{1,2}=\lim _{k \rightarrow \infty}\left(\sum_{i=1}^{n}\left|x_{1 i}-x_{2 i}\right|^{k}\right)^{\frac{1}{k}}\)
二维空间的两点$a(x_1, y_1)$, $b(x_2, y_2)$之间的切比雪夫距离： \(d_{1,2}=\max \left(\left|x_{1}-x_{2}\right|,\left|y_{1}-y_{2}\right|\right)\)
Python代码实现
from math import*
def chebyshev_distance(x,y):
return max(abs(a - b) for a, b in zip(x, y))
print(chebyshev_distance([1, 2, 3], [4, 7, 5]))
5
Numpy代码实现
import numpy as np
def chebyshev_distance_numpy(x,y):
return np.linalg.norm(x-y, ord=np.inf)
# return np.abs(x-y).max()
print(chebyshev_distance_numpy(np.array([1, 2, 3]), np.array([4, 7, 5])))
5.0
明可夫斯基距离(Minkowski Distance)
简称为明氏距离。 闵氏距离不是一种距离，而是一组距离的定义。
数学表达式
多维空间的两点$a(x_{1,1},…x_{1,n})$, $b(y_{2,1}… y_{2,n})$之间的明可夫距离距离：\(d_{1,2}=\sqrt[p]{\sum_{k=1}^{n}\left|x_{1 k}-x_{2 k}\right|^{p}}\)
其中p是一个变参数。
当p=1时，就是曼哈顿距离
当p=2时，就是欧式距离
当p→∞时，就是切比雪夫距离
根据变参数的不同，闵氏距离可以表示一类的距离。
局限性
明氏距离，包括曼哈顿距离、欧式距离和切比雪夫距离都存在明显的缺点。
举个例子：二维样本(身高,体重)，其中身高范围是150 ~ 190，体重范围是50 ~ 60，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b之间的明氏距离（无论是曼哈顿距离、欧式距离或切比雪夫距离）等于a与c之间的闵氏距离，但是身高的10cm真的等价于体重的10kg么？因此用明氏距离来衡量这些样本间的相似度很有问题。
简单说来，明氏距离的缺点主要有两个：(1)将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布（期望，方差等)可能是不同的。
Python代码实现
from math import*
from decimal import Decimal
def nth_root(value, n_root):
root_value = 1/float(n_root)
return round (Decimal(value) ** Decimal(root_value),3)
def minkowski_distance(x,y,p_value):
return nth_root(sum(pow(abs(a-b),p_value) for a,b in zip(x, y)),p_value)
print(minkowski_distance([0,3,4,5],[7,6,3,-1],3))
8.373
Numpy代码实现
利用np.linalg.norm函数
余弦距离(Cosine)
数学表达式
多维空间的两点$a(x_{1,1},…x_{1,n})$, $b(y_{2,1}… y_{2,n})$之间的余弦距离：\(\cos \theta=\frac{a \cdot b}{|a||b|}\)
等价于
\(\cos \theta=\frac{\sum_{k=1}^{n} x_{1 k} x_{2 k}}{\sqrt{\sum_{k=1}^{n} x_{1 k}^{2}} \sqrt{\sum_{k=1}^{n} x_{2 k}^{2}}}\)
二维空间的两点$a(x_1, y_1)$, $b(x_2, y_2)$之间的余弦距离：\(\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}}}\)
Python代码实现
from math import*
def square_rooted(x):
return round(sqrt(sum([a*a for a in x])),3)
def cosine_similarity(x,y):
numerator = sum(a*b for a,b in zip(x,y))
denominator = square_rooted(x)*square_rooted(y)
return round(numerator/float(denominator),3)
print(cosine_similarity([3, 45, 7, 2], [2, 54, 13, 15]))
0.972
Numpy代码实现
import numpy as np
def cosine_similarity_numpy(x, y):
return np.dot(x, y)/(np.linalg.norm(x)*np.linalg.norm(y))
print(cosine_similarity_numpy(np.array([3, 45, 7, 2]), np.array([2, 54, 13, 15])))
0.9722842517123499
杰卡德相似系数(Jaccard Similarity Coefficient) & 杰卡德距离(Jaccard Distance)
两个集合A和B的交集元素在A，B的并集中所占的比例，称为两个集合的杰卡德相似系数。
杰卡德相似系数是衡量两个集合的相似度一种指标。
数学表达式
杰卡德相似系数: \(J(A, B)=\frac{|A \cap B|}{|A \cup B|}\)
杰卡德距离: \(J_{\delta}(A, B)=1-J(A, B)=\frac{|A \cup B|-|A \cap B|}{|A \cup B|}\)
杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。
Python代码实现
from math import*
def jaccard_similarity(x,y):
intersection_cardinality = len(set.intersection(*[set(x), set(y)]))
union_cardinality = len(set.union(*[set(x), set(y)]))
return intersection_cardinality/float(union_cardinality)
print(jaccard_similarity([0,1,2,5,6],[0,2,3,5,7,9]))
0.375
Numpy代码实现
import numpy as np
import scipy.spatial.distance as dist
# x, y长度相同，不然会报错
def jaccard_similarity_numpy(x, y):
matv = np.array([x, y])
return dist.pdist(matv, 'jaccard')
print(jaccard_similarity_numpy(np.array([0,1,2,5,6,3]),np.array([0,2,3,5,7,9])))
[0.8]
汉明距离(Hamming Distance)
两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。
Numpy代码实现
import numpy as np
def hamming_distance_numpy(x, y):
smstr = np.nonzero(x - y)
return np.shape(smstr[0])[0]
print(hamming_distance_numpy(np.array([1,1,0,1,0,1,0,0,1]), np.array([0,1,1,0,0,0,1,1,1])))