Как преобразовать меру сходства в меру разницы (расстояния)?

Question

Есть ли общий способ пересчета между мерой сходства и мерой расстояния?

Рассмотрим меру сходства, например, число 2 граммов, которые имеют две общие строки.

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

Что, если мне нужно передать это алгоритму оптимизации, который ожидает меру разницы, такую ​​как расстояние Левенштейна?

Это всего лишь пример ... Я ищу общее решение, если оно существует. Например, как пройти расстояние Левенштейна до степени сходства?

Я ценю любые рекомендации, которые вы можете предложить.

Answer 1

Пусть d обозначает расстояние, s обозначает сходство. Чтобы преобразовать меру расстояния в меру подобия, нам нужно сначала нормализовать d до [0 1], используя d_norm = d / max ( d ). Тогда мера подобия определяется как:

с = 1 - d_norm .

, где s находится в диапазоне [0 1], где 1 обозначает наибольшее сходство (сравниваемые элементы идентичны), а 0 обозначает наименьшее сходство (наибольшее расстояние).

Answer 2

Выполнение 1 / подобия не сохранит свойства распределения.

лучший способ - расстояние (a-> b) = наибольшее сходство - сходство (a-> b).с наибольшим сходством, являющимся расстоянием сходства с наибольшим значением.Следовательно, вы переворачиваете свое распределение.наибольшее сходство становится 0 и т. д.

Answer 3

Если ваши меры сходства находятся между 0 и 1, вы можете использовать один из них:

1-s
sqrt(1-s)
-log(s)
(1/s)-1

Answer 4

similarity = 1/difference

и следите за difference = 0

Answer 5

Косинусное сходство широко используется для подсчета n-грамм или векторов 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-грамм из строки, вы можете использовать эти метрики, например:

>>> 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 ответ

Answer 6

В одном из моих проектов (на основе коллаборативной фильтрации) мне пришлось конвертировать корреляцию (косинус между векторами), которая была от -1 до 1 (чем ближе 1, тем больше сходство, чем ближе к -1, то больше различий), чтобы нормализовать расстояние (близко к 0 расстояние меньше, а если близко к 1, расстояние больше)

В этом случае: расстояние ~ разнообразие

Моя формула была: dist = 1 - (cor + 1)/2

Если у вас есть сходство с разнесением, и домен равен [0,1], в обоих случаях самый простой способ:

dist = 1 - sim

sim = 1 - dist

Answer 7

В случае расстояния Левенштейна, вы можете увеличивать счет сима на 1 для каждого совпадения последовательностей;то есть 1 за каждый раз, когда вам не нужно удаление, вставка или замена.Таким образом, метрика будет линейной мерой того, сколько символов имеют две строки.