python - 计算两个无序集合之间的 "distance"

Question

假设有两个集合(无序，无重复元素):

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

我怎样才能标准化这个值并根据什么？

Answer 1

对于这个问题，这个答案当然已经过时了，但希望 future 的任何访问者都能看到。

使用 Jaccard distance ，两个集合之间的对称差异的基数(集合的大小)除以它们的并集的基数。换句话说，union 减去 intersection 全部除以 union。

这假设元素可以以离散的方式进行比较，即它们是否相等。一个理想的属性是 Jaccard 距离是 metric .