比较数字列表相似性的算法？

Question

抱歉，如果这个问题听起来很初级，但我想找找在一个列表中相似的值。其实更具体一点，我想看看有没有办法给这些项目打分。

我知道在Python中，我可以直接用一个列表和'=='来判断它们是否完全相同，但如果它们不是完全一样的，而是有一些相似的值（或者没有相似的），那该怎么办呢？

举个例子：

#Batch one 
[1, 10, 20]
[5, 15, 10]
[70, 19, 15]
[50, 40, 20]


#Batch two 
[46, 19, 8]
[6, 14, 8]
[2, 11, 44]

假设我想根据两个批次之间的相似程度来给它们打分/排名。我本来想把所有数字加起来，然后通过总值来比较，但我觉得这样不太行，因为像[5, 6, 1000]和[600, 200, 211]看起来似乎很相似。在这个例子中，[5, 15, 10]和[6, 14, 8]应该得最高分。

我想过把每个值进行除法运算，看看百分比差异，但如果列表变得很大，变量很多，这样做似乎会很耗费资源（我可能最终会有成千上万的列表，每个列表里有超过800个变量），我觉得可能有更好的方法。

有什么建议吗？

Answer 1

这里的明显解决方案已经给出。基本上，它们是计算每组数据中每个数与平均值的差的绝对值的 p 次方（如果 p=2，这就等于计算方差）。

既然你提到了百分比……假设有两个数据集 [1,2,3] 和 [101,103,105]，你更喜欢哪个作为最终答案？如果你选择第一个，那就没关系。如果你选择第二个，那么你需要用平均值来标准化方差。

解决方案是： (平方平均 - 平均值的平方) / 平均值的平方，其中平方平均 = (a^2+b^2+c^2)/3，平均值 = (a+b+c)/3。

Answer 2

a = [1, 10, 20]
b = [5, 15, 10]
c = [70, 19, 15]
d = [50, 40, 20]

def sim(seqA, seqB):
    return sum([abs(a - b) for (a, b) in zip(seqA, seqB)])


print sim(a, a) # => 0
print sim(a, b) # => 19
print sim(a, c) # => 83
print sim(a, d) # => 79

数字越小，表示越相似。0表示完全一样。

Answer 3

你觉得用欧几里得距离怎么样？

在一个列表推导式中：

def distance(lista, listb):
    return sum( (b - a) ** 2 for a,b in zip(lista, listb) ) ** .5

或者写得更详细一点：

def distance(lista, listb):
    runsum = 0.0
    for a, b in zip(lista, listb):
        # square the distance of each
        #  then add them back into the sum
        runsum += (b - a) ** 2  

    # square root it
    return runsum **.5