我有两个列表：
例如， 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的关系更近）。
我正在尝试设计一种算法来计算两个有序列表之间的相似度。有序是此处的关键字（因此我不能只取两个列表的集合并计算它们的set_difference百分比）。有时数字会重复出现（如上面的3、8和9），我不能忽略这些重复项。
在上面的示例中，我要调用的函数将告诉我，例如a和b大约相似90％。我该怎么做呢？编辑距离是我想到的一种方法。我知道如何在字符串中使用它，但我不确定如何在整数列表中使用它。谢谢！
你可以使用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
听起来编辑距离（或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，它是编辑距离。
给定编辑距离和两个数组的长度，计算“相似度百分比”指标应该非常简单。
应对这个问题的一种方法是利用直方图。以下是一个示例（使用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
如果这些值没有特定的含义，那么可以使用相同的算法计算字符串的编辑距离。
我很久以前为类似的任务实现了一些东西。现在，我只有一个博客条目。它很简单：你需要计算两个序列的概率密度函数，然后找到由概率密度函数图形表示的公共区域。
链接上的图片无法显示，我当时使用的外部服务器已经失效了。
现在，针对您的问题，代码转换为：
def overlap(pdf1, pdf2):
s = 0
for k in pdf1:
if pdf2.has_key(k):
s += min(pdf1[k], pdf2[k])
return s
def pdf(l):
d = {}
s = 0.0
for i in l:
s += i
if d.has_key(i):
d[i] += 1
else:
d[i] = 1
for k in d:
d[k] /= s
return d
def solve():
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]
pdf_a = pdf(a)
pdf_b = pdf(b)
print pdf_a
print pdf_b
print overlap(pdf_a, pdf_b)
print overlap(pdf_b, pdf_a)
if __name__ == '__main__':
solve()
不幸的是，它给出了一个意外的答案，只有0.212292609351
s1=[1,2,3,4,5,6,7,8,9,10]
s2=[2,1,3,4,5,6,7,8,9,9]
尽管有3个不同的元素而不是2个，它仍然返回0.8。
一个解决方法可能是:
def find_percentage_agreement(s1, s2):
assert len(s1)==len(s2), "Lists must have the same shape"
nb_agreements = 0 # initialize counter to 0
for idx, value in enumerate(s1):
if s2[idx] == value:
nb_agreements += 1
percentage_agreement = nb_agreements/len(s1)
return percentage_agreement
哪个会返回预期结果：
>>> s1=[1,2,3,4,5,6,7,8,9,10]
>>> s2=[2,1,3,4,5,6,7,8,9,9]
>>> find_percentage_agreement(s1, s2)
0.7
除非我误解了重点。
from __future__ import division
def similar(x,y):
si = 0
for a,b in zip(x, y):
if a == b:
si += 1
return (si/len(x)) * 100
if __name__ in '__main__':
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]
result = similar(a,b)
if result is not None:
print "%s%s Similar!" % (result,'%')
a和b）。 - NPE