Làm cách nào để chuyển đổi giữa thước đo tương tự và thước đo chênh lệch (khoảng cách)?

Question

Có cách nào chung để chuyển đổi giữa một phép đo tương tự và đo khoảng cách?

Hãy xem xét một biện pháp tương tự như số lượng 2-gram mà hai chuỗi có điểm chung.

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

Điều gì sẽ xảy ra nếu tôi cần phải đưa thuật toán này vào một thuật toán tối ưu dự đoán một thước đo khác biệt, như khoảng cách Levenshtein?

Đây chỉ là một ví dụ ... Tôi đang tìm một giải pháp chung, nếu có. Giống như làm thế nào để đi từ Levenshtein khoảng cách đến một biện pháp tương tự?

Tôi đánh giá cao bất kỳ hướng dẫn nào bạn có thể cung cấp.

Answer 1

similarity = 1/difference 

và xem ra cho difference = 0

Answer 2

Trong trường hợp khoảng cách levenshtein, bạn có thể tăng số điểm sim 1 cho mỗi khi trận đấu trình tự; nghĩa là, 1 cho mỗi lần bạn không cần xóa, chèn hoặc thay thế. Bằng cách đó, số liệu sẽ là thước đo tuyến tính bao nhiêu ký tự mà hai chuỗi có chung.

Answer 3

Nếu biện pháp tương tự của bạn (s) là giữa 0 và 1, bạn có thể sử dụng một trong những:

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

Answer 4

Trong một trong những dự án của tôi (dựa trên hợp tác Filtering) Tôi đã phải chuyển đổi giữa tương quan (cosin giữa các vector) là từ -1 đến 1 (gần 1 tương tự, gần với -1 là đa dạng hơn) để khoảng cách chuẩn hóa (gần 0 khoảng cách nhỏ hơn và nếu nó gần 1 khoảng cách lớn hơn)

Trong trường hợp này: khoảng cách ~ đa dạng

của tôi cho căn là: dist = 1 - (cor + 1)/2

Nếu bạn có sự tương đồng với sự đa dạng và tên miền là [0,1] trong cả hai trường hợp cách simlest là:

dist = 1 - sim

sim = 1 - dist

Answer 5

Làm 1/tương đồng là sẽ không giữ các thuộc tính của bản phân phối.

cách tốt nhất là khoảng cách (a-> b) = cao nhất tương tự - tương tự (a-> b). với độ tương tự cao nhất là khoảng cách tương tự với giá trị lớn nhất. Bạn do đó lật phân phối của bạn. sự tương đồng cao nhất trở thành 0 vv

Answer 6

Hãy d biểu thị khoảng cách, s biểu thị sự tương đồng. Để chuyển đổi đo lường khoảng cách đến biện pháp tương tự, chúng ta cần phải đầu bình thường hóa d tới [0 1], bằng cách sử dụng d_norm = d/max (d).Sau đó, các biện pháp tương tự được đưa ra bởi:

s = 1 - d_norm.

trong đó s nằm trong khoảng [0 1], với 1 biểu thị sự giống nhau cao nhất (các mục so sánh giống nhau) và 0 biểu thị sự tương tự thấp nhất (khoảng cách lớn nhất).

Answer 7

Cosine similarity là widely used cho số lượng gram hoặc véc tơ 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 

Tính tương tự của Cosine có thể được sử dụng để tính toán số liệu khoảng cách chính thức according to wikipedia. Nó tuân theo tất cả các thuộc tính của một khoảng cách mà bạn mong đợi (đối xứng, không âm, vv):

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

Cả hai số liệu dao động giữa 0 và 1.

Nếu bạn có một tokenizer sản xuất N gram từ một chuỗi bạn có thể sử dụng các số liệu như thế này:

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

tôi tìm thấy sản phẩm thanh lịch bên trong của Counter trong this SO answer