13

有没有一种通用的方法可以在相似度度量和距离度量之间进行转换?

考虑一个相似性度量,例如两个字符串共有的 2-gram 的数量。

2-grams('beta', 'delta') = 1
2-grams('apple', 'dappled') = 4

如果我需要将其提供给期望差异度量的优化算法,例如 Levenshtein 距离,该怎么办?

这只是一个例子......我正在寻找一个通用的解决方案,如果存在的话。就像如何从 Levenshtein 距离到相似度的度量?

感谢您提供的任何指导。

4

9 回答 9

13

d表示距离,s表示相似度。要将距离度量转换为相似度度量,我们需要首先使用d_norm = d /max( d ) 将d归一化为 [0 1] 。然后相似性度量由下式给出:

s = 1 - d_norm

其中s在 [0 1] 范围内,1 表示最高相似度(比较的项目相同),0 表示最低相似度(最大距离)。

于 2015-03-12T20:47:18.113 回答
5

如果您的相似性度量在 0 和 1 之间,您可以使用以下之一:

1-s
sqrt(1-s)
-log(s)
(1/s)-1
于 2011-12-15T20:54:06.853 回答
5

做 1/similarity 不会保留分布的属性。

最好的方法是距离(a->b)=最高相似度-相似度(a->b)。最高相似度是具有最大值的相似度。因此,您翻转了您的分配。最高相似度变为 0 等

于 2014-04-14T08:32:58.203 回答
3

是的,有一种最通用的方法可以在相似度距离之间进行转换:严格单调递减函数f(x)

也就是说,with f(x)you can make similarity = f(distance)or distance = f(similarity)。它在两个方向都有效。这样的功能有效,因为相似性和距离之间的关系是当另一个增加时,一个减小。

例子:

这些是一些众所周知的严格单调递减候选,它们适用于非负相似性或距离:

  • f(x) = 1 / (a + x)
  • f(x) = exp(- x^a)
  • f(x) = arccot(ax)

您可以选择参数a>0(例如,a=1

编辑 2021-08

一个非常实用的方法是使用属于 统计软件 R的函数sim2diss。该函数提供了多达 13 种方法来计算相似性中的差异性。可悲的是,根本没有解释这些方法:您必须查看代码:-\

于 2020-06-10T09:58:53.157 回答
1
similarity = 1/difference

并注意difference = 0

于 2010-10-31T19:35:14.990 回答
0

在我的一个项目中(基于协作过滤),我必须在从 -1 到 1(越接近 1 越相似,越接近 -1 越多样化)的相关性(向量之间的余弦)之间转换为归一化距离(接近0距离更小,如果接近1距离更大)

在这种情况下:距离〜多样性

我的公式是:dist = 1 - (cor + 1)/2

如果您与多样性有相似性,并且在这两种情况下域都是 [0,1],那么最简单的方法是:

dist = 1 - sim

sim = 1 - dist

于 2011-12-15T21:06:54.730 回答
0

在 Levenshtein 距离的情况下,每次序列匹配时,您可以将 sim 分数增加 1;也就是说,每次您不需要删除、插入或替换时都为 1。这样,度量将是两个字符串共有多少个字符的线性度量。

于 2011-08-05T13:33:32.753 回答
0

根据scikit 学习

内核是相似性的度量,即如果对象 a 和 b 被认为比对象 a 和 c“更相似”,则 s(a, b) > s(a, c)。核也必须是半正定的。

有许多方法可以在距离度量和相似性度量之间进行转换,例如内核。令 D 为距离,S 为核:

  • S = np.exp(-D * gamma),其中选择 gamma 的一种启发式方法是 1 / num_features
  • S = 1. / (D / np.max(D))
于 2021-03-30T00:19:34.923 回答
0

余弦相似度广泛 用于 n-gram 计数或 TFIDF 向量。

from math import pi, acos
def similarity(x, y):
    return sum(x[k] * y[k] for k in x if k in y) / sum(v**2 for v in x.values())**.5 / sum(v**2 for v in y.values())**.5

根据维基百科,余弦相似度可用于计算正式的距离度量。它遵循您期望的距离的所有属性(对称性、非负性等):

def distance_metric(x, y):
    return 1 - 2 * acos(similarity(x, y)) / pi

这两个指标的范围都在 0 和 1 之间。

如果您有一个从字符串生成 N-gram 的标记器,您可以使用以下指标:

>>> import Tokenizer
>>> tokenizer = Tokenizer(ngrams=2, lower=True, nonwords_set=set(['hello', 'and']))

>>> from Collections import Counter
>>> list(tokenizer('Hello World again and again?'))
['world', 'again', 'again', 'world again', 'again again']
>>> Counter(tokenizer('Hello World again and again?'))
Counter({'again': 2, 'world': 1, 'again again': 1, 'world again': 1})
>>> x = _
>>> Counter(tokenizer('Hi world once again.'))
Counter({'again': 1, 'world once': 1, 'hi': 1, 'once again': 1, 'world': 1, 'hi world': 1, 'once': 1})
>>> y = _
>>> sum(x[k]*y[k] for k in x if k in y) / sum(v**2 for v in x.values())**.5 / sum(v**2 for v in y.values())**.5
0.42857142857142855
>>> distance_metric(x, y)
0.28196592805724774

Counter我在这个 SO 答案中找到了优雅的内积

于 2016-05-13T23:41:46.117 回答