余弦相似度与 Levenshtein 距离

数据挖掘 相似 公制 余弦距离
2021-10-06 09:58:33

余弦相似度与 Levenshtein 距离

我想知道它们之间有什么区别以及它们在什么情况下效果最好?

据我了解:

余弦相似度是内积空间的两个非零向量之间的相似度度量,用于度量它们之间夹角的余弦值。0°的余弦为1,在(0,π]弧度区间内的任意角度都小于1。

Levenshtein 距离是用于测量两个序列之间差异的字符串度量。非正式地,两个单词之间的 Levenshtein 距离是单字符编辑的最小数量

我的问题是

  • 什么时候会在Levenshtein 距离上使用余弦相似度
4个回答

正如其他答案中提到的,传统上余弦用于测量向量之间的相似性,而 Levenshtein 被用作字符串相似性测量,即测量字符序列之间的距离。

尽管如此,它们都可以在非传统环境中使用,并且确实具有可比性:

  • 例如,与余弦比较的向量可以包含字符或字符 n-gram 的频率,因此使其成为字符串相似性度量
  • 可以将字符序列替换为字符串序列或 n-gram 序列,从而使 Levenshtein 成为更通用的距离度量。

Cosine 和 Levenshtein 在概念上的主要区别在于,前者假设了“词袋”向量表示,即比较无序集,而后者考虑了序列中元素的顺序。

在比较单词序列的上下文中,许多组合是可能的。如果这就是您正在寻找的内容,您可能会对本文感兴趣:https ://www.aclweb.org/anthology/C08-1075/ (完全披露:我是作者之一)。

第一个是用于计算对象之间的相似性,将它们的表示视为向量。第二个是用于计算字符序列之间的相似性。

余弦相似度使用向量,可以计算集合和多集(=bags)的相似度。如果用于序列(字符、单词、句子、行……)的相似性,则比较是无序的,并且每种元素都是向量空间中的特征 = 维度。因此,单词“banana”的字母被转换为集合 [a, b, n] 或 bag {a: 3, b: 1, n: 2},其中该集合可以被认为是 bag {a: 1 , b: 1, n: 1} 和可以使用相同的计算。每个字符都被视为向量的一个维度。因此,在支持 Unicode 的情况下,向量空间可能具有 0x10FFFF ~ 110 万维,但对于两个字符串的比较,您只需要一个大小为 <= len1 + len2 的子集。这被实现为稀疏向量。为了将一些序列顺序引入应用于序列的余弦相似性,我们可以使用 2-gram 或 3-gram。这对于在大型词典中搜索相似词作为拼写纠正的候选词非常有效,例如,将搜索限制为最小相似度 0.7,或获取前 20 个相似词。

在候选者中,您可以使用速度较慢但更精确的 Levenshtein 或 LCS。

为了直接回答您的问题,我想说在处理向量时可以使用余弦相似度(例如(1,2,3)和(4,5,6)之间的距离),并且可以在以下情况下使用 Levenshtein 距离处理字符串(“aaaaa”和“aaaba”之间的“距离”)。

具体来说,它们并不真正适用于相同的上下文,也不用于相同的应用程序。如果您想测试两个不同的文本是否非常相似,使用 Levenshtein 距离可能是合理的。如果您想知道两个向量在 3 维空间中是否非常相似,使用余弦相似度可能是一个好主意。