【NLP基础知识】有哪些相似度计算方式(持续更新)
相异性/相似性的计算-zine
相似度计算方式
1. Euclidean Distance (L2)
用途:主要用于计算机视觉领域。
解释:计算两个点之间的直线距离。假设有两个向量
a
=
[
a
1
,
a
2
,
.
.
.
,
a
n
]
\mathbf{a} = [a_1, a_2, …, a_n]
a=[a1,a2,…,an] 和
b
=
[
b
1
,
b
2
,
.
.
.
,
b
n
]
\mathbf{b} = [b_1, b_2, …, b_n]
b=[b1,b2,…,bn],它们之间的欧几里得距离计算如下:
L2
(
a
,
b
)
=
∑
i
=
1
n
(
a
i
−
b
i
)
2
ext{L2}(\mathbf{a}, \mathbf{b}) = \sqrt{\sum_{i=1}^{n} (a_i – b_i)^2}
L2(a,b)=i=1∑n(ai−bi)2
举例:
- 向量
a
=
[
1
,
2
,
3
]
\mathbf{a} = [1, 2, 3]
b
=
[
4
,
5
,
6
]
\mathbf{b} = [4, 5, 6]
- 欧几里得距离
L2
(
a
,
b
)
=
(
1
−
4
)
2
+
(
2
−
5
)
2
+
(
3
−
6
)
2
=
27
≈
5.20
ext{L2}(\mathbf{a}, \mathbf{b}) = \sqrt{(1-4)^2 + (2-5)^2 + (3-6)^2} = \sqrt{27} \approx 5.20
L2(a,b)=(1−4)2+(2−5)2+(3−6)2
=27
≈5.20
2. Inner Product (IP)
用途:主要用于自然语言处理领域。
解释:计算两个向量的点积。假设有两个向量
a
=
[
a
1
,
a
2
,
.
.
.
,
a
n
]
\mathbf{a} = [a_1, a_2, …, a_n]
a=[a1,a2,…,an] 和
b
=
[
b
1
,
b
2
,
.
.
.
,
b
n
]
\mathbf{b} = [b_1, b_2, …, b_n]
b=[b1,b2,…,bn],它们之间的内积计算如下:
IP
(
a
,
b
)
=
∑
i
=
1
n
a
i
b
i
ext{IP}(\mathbf{a}, \mathbf{b}) = \sum_{i=1}^{n} a_i b_i
IP(a,b)=i=1∑naibi
举例:
- 向量
a
=
[
1
,
2
,
3
]
\mathbf{a} = [1, 2, 3]
b
=
[
4
,
5
,
6
]
\mathbf{b} = [4, 5, 6]
- 点积
IP
(
a
,
b
)
=
1
⋅
4
+
2
⋅
5
+
3
⋅
6
=
32
ext{IP}(\mathbf{a}, \mathbf{b}) = 1 \cdot 4 + 2 \cdot 5 + 3 \cdot 6 = 32
IP(a,b)=1⋅4+2⋅5+3⋅6=32
3. Hamming Distance
汉明距离: 两个相同长度字符串进行异或运算,结果为1的个数就是汉明距离
用途:主要用于自然语言处理领域中的二进制嵌入。
解释:计算两个相同长度的二进制字符串之间不同位置的个数。假设有两个二进制向量
a
=
[
a
1
,
a
2
,
.
.
.
,
a
n
]
\mathbf{a} = [a_1, a_2, …, a_n]
a=[a1,a2,…,an] 和
b
=
[
b
1
,
b
2
,
.
.
.
,
b
n
]
\mathbf{b} = [b_1, b_2, …, b_n]
b=[b1,b2,…,bn],汉明距离计算如下:
Hamming
(
a
,
b
)
=
∑
i
=
1
n
1
(
a
i
≠
b
i
)
ext{Hamming}(\mathbf{a}, \mathbf{b}) = \sum_{i=1}^{n} \mathbf{1}(a_i
eq b_i)
Hamming(a,b)=i=1∑n1(ai=bi)
举例:
- 向量
a
=
[
0
,
1
,
1
,
0
]
\mathbf{a} = [0, 1, 1, 0]
b
=
[
1
,
1
,
0
,
0
]
\mathbf{b} = [1, 1, 0, 0]
- 汉明距离
Hamming
(
a
,
b
)
=
2
ext{Hamming}(\mathbf{a}, \mathbf{b}) = 2
Hamming(a,b)=2
4. Jaccard Index
jaccard相似性 = 集合交集/集合并集
jaccard距离 = 1-jaccard相似性
用途:主要用于分子相似度搜索。
解释:计算两个集合的交集大小与并集大小的比值。假设有两个集合
A
A
A 和
B
B
B,它们的Jaccard指数计算如下:
Jaccard
(
A
,
B
)
=
∣
A
∩
B
∣
∣
A
∪
B
∣
ext{Jaccard}(A, B) = \frac{|A \cap B|}{|A \cup B|}
Jaccard(A,B)=∣A∪B∣∣A∩B∣
举例:
- 集合
A
=
{
1
,
2
,
3
}
A = \{1, 2, 3\}
B
=
{
2
,
3
,
4
}
B = \{2, 3, 4\}
- Jaccard指数
Jaccard
(
A
,
B
)
=
2
4
=
0.5
ext{Jaccard}(A, B) = \frac{2}{4} = 0.5
Jaccard(A,B)=42=0.5
5. Tanimoto Coefficient
用途:主要用于分子相似度搜索。
解释:类似于Jaccard指数,但通常用于浮点数或连续值的集合。假设有两个向量
a
\mathbf{a}
a 和
b
\mathbf{b}
b,Tanimoto系数计算如下:
Tanimoto
(
a
,
b
)
=
a
⋅
b
∣
a
∣
2
+
∣
b
∣
2
−
a
⋅
b
ext{Tanimoto}(\mathbf{a}, \mathbf{b}) = \frac{\mathbf{a} \cdot \mathbf{b}}{|\mathbf{a}|^2 + |\mathbf{b}|^2 – \mathbf{a} \cdot \mathbf{b}}
Tanimoto(a,b)=∣a∣2+∣b∣2−a⋅ba⋅b
举例:
- 向量
a
=
[
1
,
1
,
0
]
\mathbf{a} = [1, 1, 0]
b
=
[
0
,
1
,
1
]
\mathbf{b} = [0, 1, 1]
- Tanimoto系数
Tanimoto
(
a
,
b
)
=
1
3
≈
0.33
ext{Tanimoto}(\mathbf{a}, \mathbf{b}) = \frac{1}{3} \approx 0.33
Tanimoto(a,b)=31≈0.33
6. Superstructure and Substructure
用途:主要用于搜索分子的超结构和子结构相似性。
解释:这些指标用于化学信息学,计算一个分子是否是另一个分子的超结构或子结构。具体算法因实现而异,通常涉及子图匹配技术。
举例:
- 分子
A
A
C
6
H
6
ext{C}_6 ext{H}_6
B
B
C
6
H
5
OH
ext{C}_6 ext{H}_5 ext{OH}
- 分子
A
A
B
B
- 分子
B
B
A
A
7. Cosine Similarity
用途:主要用于自然语言处理和信息检索。
解释:计算两个向量之间的余弦角度的相似度。假设有两个向量
a
\mathbf{a}
a 和
b
\mathbf{b}
b,余弦相似度计算如下:
Cosine
(
a
,
b
)
=
a
⋅
b
∣
∣
a
∣
∣
⋅
∣
∣
b
∣
∣
ext{Cosine}(\mathbf{a}, \mathbf{b}) = \frac{\mathbf{a} \cdot \mathbf{b}}{||\mathbf{a}|| \cdot ||\mathbf{b}||}
Cosine(a,b)=∣∣a∣∣⋅∣∣b∣∣a⋅b
余弦相似性
c
o
s
θ
=
a
⋅
b
∣
∣
a
∣
∣
∣
∣
b
∣
∣
=
∑
i
=
1
n
a
i
b
i
∑
i
=
1
n
a
i
2
∑
i
=
1
n
b
i
2
cos heta =\frac{a\cdot b}{||a|| ||b||} = \frac {\sum_{i=1}^n{a_i} {b_i}} {\sqrt{\sum_{i=1}^n a_i^2} \sqrt{\sum_{i=1}^n b_i^2}}
cosθ=∣∣a∣∣∣∣b∣∣a⋅b=∑i=1nai2
∑i=1nbi2
∑i=1naibi
举例:
- 向量
a
=
[
1
,
2
,
3
]
\mathbf{a} = [1, 2, 3]
b
=
[
4
,
5
,
6
]
\mathbf{b} = [4, 5, 6]
- 余弦相似度
Cosine
(
a
,
b
)
≈
0.97
ext{Cosine}(\mathbf{a}, \mathbf{b}) \approx 0.97
Cosine(a,b)≈0.97
8. Manhattan Distance (L1)
曼哈顿距离: 又叫街区距离,类似汉明距离,区别是曼哈顿距离计算两个字符串的每个位置上对应字符之间的差值,而不是计算不陪配字符的数量。
用途:广泛用于各种数据分析和机器学习任务。
解释:计算两个点在所有坐标轴上的绝对差值之和。假设有两个向量
a
=
[
a
1
,
a
2
,
.
.
.
,
a
n
]
\mathbf{a} = [a_1, a_2, …, a_n]
a=[a1,a2,…,an] 和
b
=
[
b
1
,
b
2
,
.
.
.
,
b
n
]
\mathbf{b} = [b_1, b_2, …, b_n]
b=[b1,b2,…,bn],曼哈顿距离计算如下:
L1
(
a
,
b
)
=
∑
i
=
1
n
∣
a
i
−
b
i
∣
ext{L1}(\mathbf{a}, \mathbf{b}) = \sum_{i=1}^{n} |a_i – b_i|
L1(a,b)=i=1∑n∣ai−bi∣
举例:
- 向量
a
=
[
1
,
2
,
3
]
\mathbf{a} = [1, 2, 3]
b
=
[
4
,
5
,
6
]
\mathbf{b} = [4, 5, 6]
- 曼哈顿距离
L1
(
a
,
b
)
=
9
ext{L1}(\mathbf{a}, \mathbf{b}) = 9
L1(a,b)=9
9. Pearson Correlation Coefficient
用途:用于统计分析和机器学习中的相关性测量。
解释:衡量两个变量之间的线性相关性,取值范围为-1到1。假设有两个向量
a
\mathbf{a}
a 和
b
\mathbf{b}
b,皮尔逊相关系数计算如下:
Pearson
(
a
,
b
)
=
∑
i
=
1
n
(
a
i
−
a
ˉ
)
(
b
i
−
b
ˉ
)
∑
i
=
1
n
(
a
i
−
a
ˉ
)
2
∑
i
=
1
n
(
b
i
−
b
ˉ
)
2
ext{Pearson}(\mathbf{a}, \mathbf{b}) = \frac{\sum_{i=1}^{n} (a_i – \bar{a})(b_i – \bar{b})}{\sqrt{\sum_{i=1}^{n} (a_i – \bar{a})^2} \sqrt{\sum_{i=1}^{n} (b_i – \bar{b})^2}}
Pearson(a,b)=∑i=1n(ai−aˉ)2
∑i=1n(bi−bˉ)2
∑i=1n(ai−aˉ)(bi−bˉ)
其中
a
ˉ
\bar{a}
aˉ 和
b
ˉ
\bar{b}
bˉ 分别是
a
\mathbf{a}
a 和
b
\mathbf{b}
b 的均值。
补充公式:
p
e
a
r
s
o
n
r
=
c
o
v
(
x
,
y
)
σ
(
x
)
σ
(
y
)
=
∑
i
=
1
n
(
x
−
x
ˉ
)
(
y
−
y
ˉ
)
∑
i
=
1
n
(
x
−
x
ˉ
)
2
∑
i
=
1
n
(
y
−
y
ˉ
)
2
pearson_r =\frac{cov(x,y)}{\sigma{(x)}\sigma{(y)}} =\frac {\sum_{i=1}^n(x-\bar{x})(y-\bar{y})} {\sqrt{\sum_{i=1}^n (x-\bar{x})^2} \sqrt{\sum_{i=1}^n (y-\bar{y})^2}}
pearsonr=σ(x)σ(y)cov(x,y)=∑i=1n(x−xˉ)2
∑i=1n(y−yˉ)2
∑i=1n(x−xˉ)(y−yˉ)
举例:
- 向量
a
=
[
1
,
2
,
3
]
\mathbf{a} = [1, 2, 3]
b
=
[
4
,
5
,
6
]
\mathbf{b} = [4, 5, 6]
- 均值
a
ˉ
=
2
\bar{a} = 2
b
ˉ
=
5
\bar{b} = 5
- 皮尔逊相关系数
Pearson
(
a
,
b
)
=
1
ext{Pearson}(\mathbf{a}, \mathbf{b}) = 1
Pearson(a,b)=1
10.Spearman’s Rank Correlation
用途:用于统计分析中的秩相关性测量。
解释:衡量两个变量的秩相关性,适用于非线性相关的情况。假设有两个向量
a
\mathbf{a}
a 和
b
\mathbf{b}
b,计算如下:
Spearman
(
a
,
b
)
=
1
−
6
∑
d
i
2
n
(
n
2
−
1
)
ext{Spearman}(\mathbf{a}, \mathbf{b}) = 1 – \frac{6 \sum d_i^2}{n(n^2 – 1)}
Spearman(a,b)=1−n(n2−1)6∑di2
其中
d
i
d_i
di 是每对数据的秩差,
n
n
n 是数据对的数量。
举例:
- 向量
a
=
[
1
,
2
,
3
]
\mathbf{a} = [1, 2, 3]
b
=
[
4
,
5
,
6
]
\mathbf{b} = [4, 5, 6]
11. Edit Distance (Levenshtein Distance)
又叫莱文斯坦距离,是编辑距离的一种
用途:主要用于字符串相似性计算。
解释:计算将一个字符串变为另一个字符串所需的最少编辑操作(插入、删除、替换)的数量。
公式:
r
=
(
s
u
m
−
l
d
i
s
t
)
s
u
m
r=\frac{(sum – ldist)}{sum}
r=sum(sum−ldist)
ldist是类编辑距离,删除、插入+1,但是替换+2
举例:
- 字符串 a = “kitten” 和 b = “sitting”
- 编辑距离 = 3(kitten → sitten → sittin → sitting)
12. Bray-Curtis Dissimilarity
用途:用于生态学和其他领域中的样本比较。
解释:衡量两个样本之间的差异,计算如下:
Bray-Curtis
(
a
,
b
)
=
∑
∣
a
i
−
b
i
∣
∑
(
a
i
+
b
i
)
ext{Bray-Curtis}(\mathbf{a}, \mathbf{b}) = \frac{\sum |a_i – b_i|}{\sum (a_i + b_i)}
Bray-Curtis(a,b)=∑(ai+bi)∑∣ai−bi∣
举例:
- 向量
a
=
[
1
,
2
,
3
]
\mathbf{a} = [1, 2, 3]
b
=
[
4
,
5
,
6
]
\mathbf{b} = [4, 5, 6]
- Bray-Curtis 不相似度
Bray-Curtis
(
a
,
b
)
=
∣
1
−
4
∣
+
∣
2
−
5
∣
+
∣
3
−
6
∣
1
+
4
+
2
+
5
+
3
+
6
=
3
+
3
+
3
21
=
0.43
ext{Bray-Curtis}(\mathbf{a}, \mathbf{b}) = \frac{|1-4| + |2-5| + |3-6|}{1+4 + 2+5 + 3+6} = \frac{3 + 3 + 3}{21} = 0.43
Bray-Curtis(a,b)=1+4+2+5+3+6∣1−4∣+∣2−5∣+∣3−6∣=213+3+3=0.43
应用:
- DNA分析
- 拼字检查
- 语音辩识
- 抄袭侦测
概念
范数
- L1范数就是曼哈顿距离
- L2范数也称为欧式距离
闵氏距离
(欧几里得距离 曼哈顿距离 切比雪夫距离)
p
(
A
,
B
)
=
(
∑
i
=
1
n
∣
a
i
−
b
i
∣
P
)
1
p
p(A,B)=(\sum_{i=1}^n |a_i-b_i|^P)^{\frac{1}{p}}
p(A,B)=(i=1∑n∣ai−bi∣P)p1
p=1时为曼哈顿距离
p=2时为欧几里得距离
p
→
+
∞
p o +\infty
p→+∞切比雪夫距离
欧氏距离VS.余弦距离
欧氏距离与余弦距离的差异-CSDN
欧氏距离是超球面上的直线距离,余弦距离是超球面上的球面距离
欧式距离
- 数值受到维度的影响
- 体现的是距离上的绝对差异(
注重数值
) - 在[0,无穷)之间,无判别准则
- 复杂度
O
(
l
o
g
)
O(log)
- 对于高维稀疏向量,距离值往往很大,无法很好反映相似度
余弦相似度
- 在高维的情况下也依然保持低维完全相同时相似度为1等性质
- 体现的是方向上的相对差异(
注重维度
,相对差异) - 在[0,1]之间,有准则
- 复杂度
O
(
n
2
)
O(n^2)
- 仅考虑词语之间的方向,而不受向量模长影响,能更好反映语义相似度
调整后(调整余弦相似度)
余弦相似度对数值的不敏感导致了结果的误差,需要修正这种不合理性就出现了调整余弦相似度,即所有维度上的数值都减去一个均值
X和Y两个用户对两个内容的评分分别为(1,2)和(4,5)那么调整后为(-2,-1)和(1,2)
余弦相似度 vs 相关系数
皮尔逊系数就是cos计算之前两个向量都先进行中心化(centered)
中心化的意思是说, 对每个向量, 我先计算所有元素的平均值avg, 然后向量中每个维度的值都减去这个avg
观察皮尔逊系数的公式:分子部分:
- 每个向量的每个数字要先减掉向量各个数字的平均值, 这就是在中心化.
- 分母部分: 两个根号式子就是在做取模运算, 里面的所有的 r 也要减掉平均值, 其实也就是在做中心化.