Come posso convertire tra una misura di somiglianza e una misura di differenza (distanza)?

Question

Esiste un modo generale per convertire tra una misura di somiglianza e una misura di distanza?

Considerare una misura di somiglianza come il numero di 2 grammi che due stringhe hanno in comune.

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

Cosa succede se ho bisogno di alimentare l'accaduto a un algoritmo di ottimizzazione che prevede una misura della differenza, come Levenshtein distanza?

Questo è solo un esempio ... Sto cercando una soluzione generale, se ne esiste una. Ti piace come andare dalla distanza di Levenshtein ad una misura di somiglianza?

Apprezzo tutte le indicazioni che potresti offrire.

Answer 1

similarity = 1/difference 

e guardare fuori per difference = 0

Answer 2

Nel caso di Levenshtein distanza, si potrebbe aumentare il punteggio sim di 1 per ogni volta che la partita sequenze; cioè, 1 per ogni volta che non hai bisogno di una cancellazione, inserimento o sostituzione. In questo modo la metrica sarebbe una misura lineare del numero di caratteri che le due stringhe hanno in comune.

Answer 3

Se la misura di similarità (s) è compreso tra 0 e 1, è possibile utilizzare uno di questi:

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

Answer 4

In uno dei miei progetti (sulla base di filtraggio collaborativo) ho dovuto per la conversione tra correlazione (coseno tra i vettori) che era da -1 a 1 (più vicino 1 è più simile, più vicino a -1 è più vario) a distanza normalizzata (vicino a 0 la distanza è minore e se è vicina a 1 la distanza è maggiore)

In questo caso: distance ~ diversity

Il mio per mula era: dist = 1 - (cor + 1)/2

Se si dispone di somiglianza con la diversità e il dominio è [0,1] in entrambi i casi il modo simlest è:

dist = 1 - sim

sim = 1 - dist

Answer 5

facendo 1/somiglianza è non manterrà le proprietà della distribuzione.

il modo migliore è distanza (a-> b) = somiglianza più alta - somiglianza (a-> b). con somiglianza più alta è la distanza di somiglianza con il valore più grande. Quindi capovolgi la tua distribuzione. la somiglianza più alto diventa 0 ecc

Answer 6

Let d denota distanza, s denota somiglianza. Per convertire misura di distanza di misura di similarità, abbiamo bisogno di normalizzare prima d a [0 1], utilizzando d_norm = d/max (d).Poi la misura di similarità è dato da:

s = 1 - d_norm.

dove s è nell'intervallo [0 1], con 1 indica la somiglianza più alta (gli elementi in confronto sono identici) e 0 indica la somiglianza più bassa (maggiore distanza).

Answer 7

Cosine similarity è widely used per conteggio n-grammi o vettori 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 

coseno di similitudine può essere utilizzato per calcolare una distanza metrica formale according to wikipedia. Esso obbedisce tutte le proprietà di una distanza che ci si aspetterebbe (simmetria, non negatività, ecc):

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

Entrambe queste metriche variare tra 0 e 1.

Se si dispone di un tokenizer che produce N- grammi da una stringa si potrebbe utilizzare questi parametri in questo modo:

>>> 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 

ho trovato l'elegante prodotto interno di Counter in this SO answer