“模糊”Jaccard指数实现的性能

Question

我正在尝试计算两个集合之间的一种模糊Jaccard指数，思路是这样的：就像Jaccard指数一样，我想计算两个集合中共同项的数量与两个集合中不同项的总数量之间的比例。问题是，我想使用一个相似度函数，并设定一个阈值来判断什么算是“相同”的项，这样相似的项就可以：

1. 在并集中不被重复计算
2. 在交集中被计算。

我这里有一个可以工作的实现（用Python写的）：

def fuzzy_jaccard(set1, set2, similarity, threshold):

    intersection_size = union_size = len(set1 & set2)
    shorter_difference, longer_difference = sorted([set2 - set1, set1 - set2], key=len)

    while len(shorter_difference) > 0:          
        item1, item2 = max(
            itertools.product(longer_difference, shorter_difference),
            key=lambda (a, b): similarity(a, b)
        )
        longer_difference.remove(item1)
        shorter_difference.remove(item2)

        if similarity(item1, item2) > threshold:
            union_size += 1
            intersection_size += 1
        else:
            union_size += 2
    union_size = union_size + len(longer_difference)

    return intersection_size / union_size

这里的问题是，这个算法的复杂度是集合大小的平方，因为在itertools.product中，我要遍历每个集合中所有可能的项对（*）。现在，我觉得我必须这样做，因为我想把set1中的每个项a与set2中最合适的候选项b匹配，而这个b不能和set1中另一个项a'过于相似。

我感觉应该有一种O(n)的方式来做到这一点，但我还没有搞明白。你有什么建议吗？

还有其他问题，比如一旦找到最佳匹配后，如何重新计算每对项的相似度，但我对此不是太在意。

Answer 1

我觉得在一般情况下，可能没有什么方法能做到 O(n) 的效率，但至少在大多数情况下，你可以做到比 O(n^2) 更好。

相似性是传递的吗？我的意思是：你能否假设距离(a, c) 小于等于距离(a, b) 加上距离(b, c)？如果不能，这个回答可能对你没帮助。我把相似性当作距离来处理。

试着把数据分成小组：

选择一个半径 r。根据我的直觉，我建议把 r 设置为你计算的前 5 个相似性平均值的三分之一，或者其他什么。

你在 set1 中选择的第一个点成为你第一个小组的中心。把 set2 中的点分类为在小组内（与中心点的相似性小于等于 r）或在小组外。同时，记录那些距离小组中心在 2r 以内的点。

你可以要求小组中心点之间的距离至少为 2r；在这种情况下，有些点可能不在任何小组内。我建议它们之间的距离至少为 r。（如果你处理的维度很多，可能可以少一点。）你可以把每个点都当作小组中心，但那样你就不会节省处理时间。

当你选择一个新点时，首先要把它与小组中心点进行比较（尽管它们在同一个集合中）。这个点要么在已有的小组内，要么成为一个新的小组中心（或者如果它距离小组中心在 r 和 2r 之间，可能两者都不是）。如果它距离小组中心在 r 以内，那么就要与其他集合中距离该小组中心在 2r 以内的所有点进行比较。你可能可以忽略距离小组中心超过 2r 的点。如果在小组内找不到相似的点（可能是因为小组里没有剩下的点），那么你可能需要扫描其余所有点。希望这种情况大多只会在集合中剩下的点不多时发生。如果这个方法有效，那么在大多数情况下，你会在小组内找到最相似的点，并且知道它就是最相似的点。

这个想法可能需要一些调整。

如果涉及的维度很多，你可能会发现，对于给定的半径 r，很多点的距离在 2r 以内，而在 r 以内的点却很少。

这里还有另一种算法。如果计算你的相似性函数的时间比较长（相对于维护排序点列表所需的时间），那么你可能想要更多的索引点。如果你知道维度的数量，使用那个数量的索引点可能是有意义的。如果一个点与另一个索引点太相似，你可能会拒绝它作为候选索引点。

对于你使用的每个第一个点和你决定用作索引点的其他点，生成一个列表，列出其他集合中所有剩余点，按与索引点的距离排序。

当你把一个点 P1 与其他集合中的点进行比较时，我认为你可以跳过某些集合，原因有两个。考虑你找到的与 P1 最相似的点 P2。如果 P2 与某个索引点相似，那么你可以跳过所有与该索引点足够不相似的点。如果 P2 与某个索引点不相似，那么你可以跳过所有与该索引点足够相似的点。我认为在某些情况下，你可以对同一个索引点跳过这两种类型的点。