计算两个列表的相似度

Question

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

比如：

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

你可以看到，列表中的一个项目可以出现多次，而且它们的长度也不一样。

我已经考虑过比较每个项目的出现频率，但这并没有考虑到每个列表的大小（一个列表如果只是另一个列表的两倍，那么它们应该是相似的，但并不是完全相似）。

再比如：

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

所以我基本上想要考虑列表的大小，以及列表中项目的分布情况。

有没有什么好的想法呢？

Answer 1

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

你可能需要根据自己的情况做一些调整，但余弦相似度的概念非常不错。

Answer 2

我觉得你想要做的是计算一个数组中的逆序对数量。这个问题的答案在这里：计算数组中的逆序对

Answer 3

可以使用 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

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