计算两个列表的相似度

我有两个列表：计算两个列表的相似度

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

计算两个列表的相似度

回答

相关问题