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

一尘不染

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

algorithm

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

例如：

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

因此，我基本上希望包含列表的大小以及列表中项目的分布。

有任何想法吗？

阅读 1298

2020-07-28

共1个答案

一尘不染

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

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

2020-07-28