计算两个列表的相似度

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

我想设计一个算法来计算这两个有顺序的列表之间的相似度。这里的“有顺序”很重要（所以我不能简单地把两个列表的元素放在一起，计算它们的差异百分比）。有时候数字会重复（比如上面提到的3、8和9，我不能忽略这些重复的数字）。

在上面的例子中，我希望调用的函数能告诉我，a和b的相似度大约是90%。我该怎么做呢？我想到的一个方法是编辑距离。我知道如何用它来处理字符串，但不太确定如何用在整数列表上。谢谢！

Answer 1

解决这个问题的一种方法是使用直方图。举个例子（用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

所以，你需要更具体一点，才能找到最适合你需求的相似度测量方法。

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

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