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

Question

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

13

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

例如：

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

如您所见，列表中的单个项目可能会出现多次，并且长度各不相同。

我已经考虑过比较每个项目的频率，但这并不能涵盖每个列表的大小（一个仅是另一个列表两倍的列表应该是相似的，但不是完全相似的）。

例如2：

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

我基本上想涵盖列表的大小和列表中项目的分布。

有任何想法吗？

- kmace

5

那些是列表，而不是集合。 - Martijn Pieters

通过“相似性”，您的意思是创建一个包含列表A和列表B中出现的元素的第三个列表吗？因此，在您的例子中，结果将是['apple'，'orange']？ - Konsol Labapen

相似性指的是它们有多么相似的度量。因此，比较两个完全相同的集合（或列表）会给您一个评分为1，而两个完全不同的集合则会给您0。但是这些集合在大小上不同，并且可能包含重复元素。 - kmace

3个回答

1

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

你可能需要进行修改以适应你的方案，但余弦相似度的概念非常棒。

- Vigneshwaren

1

我相信你想要做的是计算数组中逆序对的数量。问题的答案在这里: 计算数组中逆序对的数量。

- Computernerd

抱歉，我不确定我是否理解您的意思。如何将比较两个集合转换为在归并排序实现中计算逆序数？ - kmace

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martijn Pieters · Accepted Answer

可以考虑使用 collections.Counter()，它们是多重集合或称为袋的数据类型：

from collections import Counter

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

现在你可以按条目或频率进行比较：

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

您可以使用以下方法计算它们的余弦相似度：

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)

得出的结果是：

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

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