-1

这个问题可能更接近图像处理中的模式匹配。

有没有办法获得成本函数值，应用于不同的列表，这将返回列表间的接近度？例如，

a = [4, 7, 9]
b = [5, 8, 10]
c = [2, 3]

现在的代价函数值，可能是一个 2 元组，(a, b) 应该大于 (a, c) 和 (b, c)。这可能是一项巨大的计算任务，因为可能有更多数量的列表，并且所有排列都会破坏问题的复杂性。所以只有 2 元组的集合也可以工作。

编辑：列表名称表示动作的类型，其中的元素是相应动作发生的时间。我想做的是想出一组具有相似发生模式的动作。由于两个动作不能同时发生，它是列表内和列表间距离的组合。

提前致谢！

4

3 回答 3

0

鉴于您对迈克尔的澄清给出的答案，您可能应该查找“动态时间扭曲”。

我没有使用http://mlpy.sourceforge.net/但它的简介说它提供 DTW。（可能是敲碎坚果的锤子；取决于您的用例。）

于 2012-08-15T11:56:49.403 回答
0

你在问一个非常困难的问题。在不改变尺寸的情况下，您已经可以使用多种距离度量（欧几里得、曼哈顿等，请查看“另请参阅”部分了解更多信息）。您需要的取决于您认为衡量接近度的好方法是针对这些列表所代表的内容。

如果不知道你想用这些列表做什么，没有人可以定义一个好的答案是什么，更不用说如何有效地计算它了。

于 2012-08-15T08:37:29.903 回答
0

要比较两个字符串或列表，您可以使用Levenshtein 距离（此处的Python 实现）：

def levenshtein(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    matrix = [range(l1 + 1)] * (l2 + 1)
    for zz in range(l2 + 1):
        matrix[zz] = range(zz,zz + l1 + 1)
    for zz in range(0,l2):
        for sz in range(0,l1):
            if s1[sz] == s2[zz]:
                matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, 
                                         matrix[zz][sz+1] + 1, 
                                         matrix[zz][sz])
            else:
                matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, 
                                         matrix[zz][sz+1] + 1, 
                                         matrix[zz][sz] + 1)
    return matrix[l2][l1]

在您的清单上使用它：

>>> a = [4, 7, 9]
>>> b = [5, 8, 10]
>>> c = [2, 3]
>>> levenshtein(a,b)
3
>>> levenshtein(b,c)
3
>>> levenshtein(a,c)
3

编辑：在评论中添加解释后，您可以使用sets 而不是列表。由于集合中的每个元素都是唯一的，因此再次添加现有元素是无操作的。您可以使用集合的isdisjoint方法来检查两个集合是否不包含相同的元素，或者使用该intersection方法来查看它们有哪些共同的元素：

In [1]: a = {1,3,5}

In [2]: a.add(3)

In [3]: a
Out[3]: set([1, 3, 5])

In [4]: a.add(4)

In [5]: a
Out[5]: set([1, 3, 4, 5])

In [6]: b = {2,3,7}
In [7]: a.isdisjoint(b)
Out[7]: False

In [8]: a.intersection(b)
Out[8]: set([3])

注意：这种创建集合的语法至少需要 Python 2.7。

于 2012-08-15T08:25:45.070 回答