2

假设两组（无序，无重复元素）：

A = set(["z", "x", "c"])
B = set(["x", "z", "d", "e"])

这些集合有两个共同的元素：“z”和“x”，以及一些特定于集合的元素：c、d、e。

你怎么能给每组一个分数，就像字符串距离一样，而

  • 不考虑元素的顺序和
  • 对每个孤立集施加无重复约束

?

正如您在示例中看到的，每组的大小可以不同。

该算法的非关键要求是：

  • 如果可能，插入 > 删除（缺少元素的集合意味着成本高于具有太多元素的集合），或者只是 INS = DEL
  • 交换：0（无成本，因为排序对距离没有影响）

现在我一直在计算一个设定的距离分数：

score_A = len(common(a,b)) / len(a)    # common(...) calculates intersection
score_B = len(common(a,b)) / len(b)

quadratic_score = sqrt(score_A * score_B)

你会如何建议解决这个问题或改进我的解决方案？

有没有允许指定成本的算法？

现在我要为集合修改定义一个简单的代数：

def calculate_distance( a, b, insertion_cost=1, deletion_cost=1 ):
    """
    Virtually, a programmer-friendly set-minus.

    @return     the distance from A to B, mind that this is not
                a commutative operation.
    """
    score = 0
    for e in a:
        if e not in b: # implies deletion from A
            score += deletion_cost

    for e in b:
        if e not in a: # implies insertion into A
            score += insertion_cost

    return score

我怎样才能规范这个值和反对什么？

4

3 回答 3

3

集合交集的大小超过较大集合的大小如何？所以：

float(len(A.intersection(B)))/max(len(A),len(B))

它会给你一个在 0.0 到 1.0 范围内缩放的数字，这通常是可取的。1.0 代表完全平等，0.0 代表没有共同点。

于 2012-07-03T18:02:41.573 回答
3

对于这个问题，这个答案当然已经过时了，但希望任何未来的访问者都能接受。

使用Jaccard 距离，即两个集合之间的对称差的基数（集合的大小）除以其并集的基数。换句话说，并集减去交集都除以并集。

这假定可以以离散方式比较元素，即它们是否相等。一个理想的属性是 Jaccard 距离是一个度量。

于 2013-08-20T21:35:53.093 回答
2

与此类似的问题

假设 OP 要求的是“距离”，我认为根据距离函数的一般要求，当两组相同时，最好将其设为0

对称和三角不等式也很好

对称是直观的，三角不等式意味着 d(A,C) ≤ d(A,B) + d(B,C)

我建议类似：

C = A.intersection(B)
Distance = sqrt(len(A-C)*2 + len(B-C)*2)

但是我还不知道如何证明三角不等式

要规范化 OP 的更新函数结果，只需执行score = score / (len(a) + len(b))

这将给你 1 时a不相交b，而 0 时a == b

于 2012-07-03T19:19:29.190 回答