计算两个列表之间的相似度

Question

我想计算两个不同长度列表之间的相似度。

如：

listA = ['apple', 'orange', 'apple', 'apple', 'banana', 'orange'] # (length = 6) 
listB = ['apple', 'orange', 'grapefruit', 'apple'] # (length = 4) 

，你可以看到，一个项目可以在列表中出现多次，而长度的大小不同。

我已经想比较每个项目的频率，但是，这并不包括每个列表的大小（即简单地两次另一份名单应该是相似的列表，但不是完全相似）

EG2 ：

listA = ['apple', 'apple', 'orange', 'orange'] 
listB = ['apple', 'orange'] 
similarity(listA, listB) # should NOT equal 1 

所以我基本上想包含列表的大小和项目在列表中的分布。

任何想法？

Answer 1

使用collections.Counter()也许;这些都是多套，或袋子，在数据类型的说法：

from collections import Counter 

counterA = Counter(listA) 
counterB = Counter(listB) 

现在，你可以通过输入或频率比较这些：

import math 

def counter_cosine_similarity(c1, c2): 
    terms = set(c1).union(c2) 
    dotprod = sum(c1.get(k, 0) * c2.get(k, 0) for k in terms) 
    magA = math.sqrt(sum(c1.get(k, 0)**2 for k in terms)) 
    magB = math.sqrt(sum(c2.get(k, 0)**2 for k in terms)) 
    return dotprod/(magA * magB) 

：

>>> counterA 
Counter({'apple': 3, 'orange': 2, 'banana': 1}) 
>>> counterB 
Counter({'apple': 2, 'orange': 1, 'grapefruit': 1}) 
>>> counterA - counterB 
Counter({'orange': 1, 'apple': 1, 'banana': 1}) 
>>> counterB - counterA 
Counter({'grapefruit': 1}) 

可以使用计算出它们的余弦相似

其中给出：

>>> counter_cosine_similarity(counterA, counterB) 
0.8728715609439696 

值越接近1，两个列表越相似。

余弦相似度为一个你可以计算得分。如果你关心列表的长度，你可以计算另一个;如果您将该分数保持在0.0到1.0之间，那么您可以将这两个值相乘以得到-1.0和1.0之间的最终分数。

例如，采取相对长度考虑您可以使用：

def length_similarity(c1, c2): 
    lenc1 = sum(c1.itervalues()) 
    lenc2 = sum(c2.itervalues()) 
    return min(lenc1, lenc2)/float(max(lenc1, lenc2)) 

，然后组合成需要的列表作为输入的函数：

def similarity_score(l1, l2): 
    c1, c2 = Counter(l1), Counter(l2) 
    return length_similarity(c1, c2) * counter_cosine_similarity(c1, c2) 

对于你的两个例子名单，导致：

>>> similarity_score(['apple', 'orange', 'apple', 'apple', 'banana', 'orange'], ['apple', 'orange', 'grapefruit', 'apple']) 
0.5819143739626463 
>>> similarity_score(['apple', 'apple', 'orange', 'orange'], ['apple', 'orange']) 
0.4999999999999999 

您可以根据需要混合使用其他指标。

Answer 2

从理论角度：我建议你看看余弦相似 http://en.wikipedia.org/wiki/Cosine_similarity

您可能需要修改，以适应您的方案，但余弦相似的想法是伟大的。

Answer 3

我相信你所寻找的是一个数组 计数逆转的次数的问题有答案：Counting inversions in an array