计算两个列表的相似度

Question

我有两个清单:

例如.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不是'更接近'3而不是8').

我正在尝试设计一种算法来计算两个ORDERED列表之间的相似性.Ordered是关键字就在这里(所以我不能只取两个列表的集合并计算它们的set_difference百分比).有时数字会重复(例如上面的3,8和9,我不能忽略重复).

在上面的例子中,我调用的函数会告诉我a和b的相似度约为90%.我怎样才能做到这一点？编辑距离是我想到的.我知道如何使用字符串,但我不知道如何使用它与一个整数列表.谢谢!

Answer 1

您可以使用difflib模块

ratio()
返回序列相似性的度量,作为[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

Answer 2

这听起来像编辑(或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,这是编辑距离.

给定编辑距离和两个数组的长度,计算"百分比相似度"度量应该非常简单.

Answer 3

解决这个问题的一种方法是利用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

因此，您需要更加具体地找出最适合您的目的的相似性度量。