Tính tương tự của hai danh sách

Question

Tôi có hai danh sách:

ví dụ: a = [1,8,3,9,4,9,3,8,1,2,3] và b = [1,8,1,3,9,4,9,3,8, 1,2,3]

Cả hai đều chứa int. Không có ý nghĩa đằng sau các int (ví dụ 1 không phải là 'gần hơn' đến 3 hơn là 8).

Tôi đang cố gắng đưa ra một thuật toán để tính toán sự giống nhau giữa hai danh sách ORDERED. Đặt hàng là từ khóa ngay tại đây (vì vậy tôi không thể chỉ lấy tập hợp của cả hai danh sách và tính toán tỷ lệ phần trăm set_difference của chúng). Đôi khi các số lặp lại (ví dụ 3, 8 và 9 ở trên, và tôi không thể bỏ qua các lần lặp lại).

Trong ví dụ trên, hàm tôi gọi sẽ cho tôi biết rằng a và b là ~ 90% tương tự chẳng hạn. Làm thế nào tôi có thể làm điều đó? Khoảng cách chỉnh sửa là thứ gì đó đến trong tâm trí bạn. Tôi biết làm thế nào để sử dụng nó với chuỗi nhưng tôi không chắc chắn làm thế nào để sử dụng nó với một danh sách các ints. Cảm ơn!

Answer 1

Bạn có thể sử dụng các mô-đun difflib

tỷ lệ()
Return một biện pháp tương tự của chuỗi như một phao trong khoảng [0, 1].

Mà cho:

>>> s1=[1,8,3,9,4,9,3,8,1,2,3] 
>>> s2=[1,8,1,3,9,4,9,3,8,1,2,3] 
>>> sm=difflib.SequenceMatcher(None,s1,s2) 
>>> sm.ratio() 
0.9565217391304348 

Answer 2

Chỉ cần sử dụng cùng một thuật toán để tính khoảng cách chỉnh sửa trên chuỗi nếu giá trị không có bất kỳ ý nghĩa cụ thể nào.

Answer 3

Có vẻ như khoảng cách chỉnh sửa (hoặc Levenshtein) chính xác là công cụ thích hợp cho công việc.

Đây là một thực hiện Python có thể được sử dụng trên danh sách các số nguyên: http://hetland.org/coding/python/levenshtein.py

Sử dụng mã, levenshtein([1,8,3,9,4,9,3,8,1,2,3], [1,8,1,3,9,4,9,3,8,1,2,3]) lợi nhuận 1, đó là chỉnh sửa từ xa.

Với khoảng cách chỉnh sửa và độ dài của hai mảng, việc tính toán số liệu "phần trăm tương tự" nên khá tầm thường.

Answer 4

Trừ khi im thiếu điểm.

from __future__ import division 

def similar(x,y): 
    si = 0 
    for a,b in zip(x, y): 
     if a == b: 
      si += 1 
    return (si/len(x)) * 100 


if __name__ in '__main__': 
    a = [1,8,3,9,4,9,3,8,1,2,3] 
    b = [1,8,1,3,9,4,9,3,8,1,2,3] 
    result = similar(a,b) 
    if result is not None: 
     print "%s%s Similar!" % (result,'%') 

Answer 5

Một cách để giải quyết vấn đề này là sử dụng histogram. Như một ví dụ (trình diễn với numpy):

In []: a= array([1,8,3,9,4,9,3,8,1,2,3]) 
In []: b= array([1,8,1,3,9,4,9,3,8,1,2,3]) 

In []: a_c, _= histogram(a, arange(9)+ 1) 
In []: a_c 
Out[]: array([2, 1, 3, 1, 0, 0, 0, 4]) 

In []: b_c, _= histogram(b, arange(9)+ 1) 
In []: b_c 
Out[]: array([3, 1, 3, 1, 0, 0, 0, 4]) 

In []: (a_c- b_c).sum() 
Out[]: -1 

Hiện nay tồn tại rất nhiều cách để khai thác a_c và b_c.

Trường hợp (dường như) biện pháp tương tự đơn giản nhất là:

In []: 1- abs(-1/ 9.) 
Out[]: 0.8888888888888888 

Tiếp nối bởi:

In []: norm(a_c)/ norm(b_c) 
Out[]: 0.92796072713833688 

và:

In []: a_n= (a_c/ norm(a_c))[:, None] 
In []: 1- norm(b_c- dot(dot(a_n, a_n.T), b_c))/ norm(b_c) 
Out[]: 0.84445724579043624 

Vì vậy, bạn cần phải được nhiều cụ thể hơn để tìm ra biện pháp tương tự phù hợp nhất cho mục đích của bạn.

Answer 6

Tôi đã triển khai một cái gì đó cho một tác vụ tương tự một thời gian dài trước đây. Bây giờ, tôi chỉ có a blog entry for that. Thật đơn giản: bạn phải tính toán cả hai trình tự của cả hai chuỗi sau đó nó sẽ tìm thấy khu vực chung được trình bày bằng biểu diễn đồ họa của pdf.

Xin lỗi vì các hình ảnh bị hỏng trên liên kết, máy chủ bên ngoài mà tôi đã sử dụng lúc đó đã chết.

Ngay bây giờ, đối với vấn đề của bạn mã dịch để

def overlap(pdf1, pdf2): 
    s = 0 
    for k in pdf1: 
     if pdf2.has_key(k): 
      s += min(pdf1[k], pdf2[k]) 
    return s 

def pdf(l): 
    d = {} 
    s = 0.0 
    for i in l: 
     s += i 
     if d.has_key(i): 
      d[i] += 1 
     else: 
      d[i] = 1 
    for k in d: 
     d[k] /= s 
    return d 

def solve(): 
    a = [1, 8, 3, 9, 4, 9, 3, 8, 1, 2, 3] 
    b = [1, 8, 1, 3, 9, 4, 9, 3, 8, 1, 2, 3] 
    pdf_a = pdf(a) 
    pdf_b = pdf(b) 
    print pdf_a 
    print pdf_b 
    print overlap(pdf_a, pdf_b) 
    print overlap(pdf_b, pdf_a) 

if __name__ == '__main__': 
    solve() 

Thật không may, nó mang lại cho một câu trả lời bất ngờ, chỉ 0.212292609351