計算兩個列表的相似度

我有兩個列表：計算兩個列表的相似度

例如， 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]

兩者都包含整數。整數背後沒有意義（例如，1與8不等於3）。

我試圖設計一個算法來計算兩個ORDERED列表之間的相似度。有序關鍵字就在這裏（所以我不能只取這兩個列表的集合並計算它們的set_difference百分比）。有時數字會重複（例如上面的3,8和9，我不能忽略重複）。

在上面的例子中，我會調用的函數會告訴我，例如，a和b約爲90％。我怎樣才能做到這一點？編輯距離是想到的東西。我知道如何使用它與字符串，但我不知道如何使用它與整數列表。謝謝！

來源

2011-07-15 aerain

考慮一個字符串，僅僅是字符的列表，就似乎是計算字符串編輯距離和計算整數列表編輯距離之間的一個非常簡單的映射。 – Chowlett

也許你正在尋找[漢明距離]（http://en.wikipedia.org/wiki/Hamming_distance）？ –

@Pat B：漢明距離要求序列具有相同的長度，並且它不能處理刪除/插入。看看OP的例子（'a'和'b'）。 – NPE

可以使用difflib模塊

比率（）
返回序列相似性的量度，在範圍內的浮子[0，1]。

其中給出：

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

來源

2011-07-15 16:04:51 kraymer

這裏唯一的問題就是那些空格也會以百分比差異結束計數 – aerain

您不想使用這種方法的更多原因：這會懲罰兩位數以上的整數，而且有時可能混淆單數和雙數（或更多）數字。 – aerain

實際上沒有（關於空格），因爲SequenceMatcher足夠智能，可以將空間檢測爲垃圾。 – kraymer

只要使用相同的算法計算字符串上的編輯距離，如果這些值沒有任何特別的含義。

來源

2011-07-15 15:49:30 jason

這聽起來像編輯（或Levenshtein）距離恰恰是工作的正確工具。

下面是一個Python實現，可以在整數的列表中：http://hetland.org/coding/python/levenshtein.py

使用的代碼，levenshtein([1,8,3,9,4,9,3,8,1,2,3], [1,8,1,3,9,4,9,3,8,1,2,3])回報1，這是編輯距離。

鑑於編輯距離和兩個陣列的長度，計算「百分比相似性」度量標準應該非常簡單。

來源

2011-07-15 15:52:12 NPE

Yup很棒。謝謝！你會怎樣劃分編輯距離來得到百分比？不確定哪個列表使用 – aerain

實際上我會推薦difflib模塊方法。我不知道它可以用來比較序列相似性。 – aerain

除非我沒有想到這一點。

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,'%')

來源

2011-07-15 16:04:45

我認爲主要問題是它不能處理刪除/插入（它認爲這個OP的例子中的兩個序列爲18％相似，而他期望〜90％）。 – NPE

@aix就在這裏 – aerain

一種方式來處理，這是利用histogram。作爲一個例子（示範與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

現在存在着的方法，利用a_c和b_c過多。

凡（貌似）簡單的相似性措施是：

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

其次：

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

和：

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

因此，你需要更具體的到找出適合您的目的的最適合的相似性度量。

來源

2011-07-15 16:25:54 eat

很久以前，我已經爲類似的任務實現了一些東西。現在，我只有a blog entry for that。很簡單：您必須計算兩個序列的pdf，然後才能找到pdf圖形表示覆蓋的公共區域。

對不起，鏈接上的圖像損壞了，我用過的外部服務器現在已經死機了。

眼下，有關問題的代碼轉換爲

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

不幸的是，它提供了一個意想不到的答案，只有0.212292609351

來源

2011-07-15 17:06:45

計算兩個列表的相似度

回答

相關問題