两组区间的相似度

Question

什么样的 algorithm/solution 可以用来表示两组范围的相似性 (overlap/precision/recall/...)。

我能想到（或在网上找到）数百个类似的问题，但并不确切，但这个 "wheel" 肯定已经被发明了...

假设输入数据类似于：

Real      [ ## ###  #     ] or [(1,2),(4,6),(9,10)]  
Predicted [ ## #          ] or [(1,2),(4,4)]

输出应该是~50%

例如 AND 位图，我应该使用间隔树还是什么？是否有一个很好的功能或易于编写的算法？任何有意义的相似性度量都可以，任何合理的输入格式也可以。

谢谢。

（实际长度 ~4000，每组 <50 个间隔）

Answer 1

您可以将线段拆分为单独的点，并将每个点标记为 real/predicted 和 start/end。

然后对点进行排序，遍历排序后的列表并跟踪重叠部分。

您甚至不需要跟踪间隔最初是来自 Real 还是 Predicted - 您只需要跟踪每个点是否有一个或两个间隔。

示例：

Real      [(1,2),(4,6),(9,10)]  
Predicted [(1,2),(4,4)]

分解为点并排序（S 表示开始，E 表示结束）：

[(1,S),(1,S),(2,E),(2,E),(4,S),(4,S),(4,E),(6,E),(9,S),(10,E)]

然后遍历数组 - 跟踪有多少段 "are open" 并计算 total open 和 2 segments open.

的长度

结果为2 segments open/total open.

Answer 2

你可以使用Jaccard index来衡量相似度，也称为"intersection over union."它是一个介于0和1之间的数字，其中0表示"these two sets do not overlap at all"，1表示"these two sets are identical."

在Python3中，很容易实现：

def jaccard(A, B):
    if A or B:
        return len(A & B) / len(A | B)
    else:
        return 1.0

A和B是两组值。尽管在理论上不是最优的，但以下方法可能足以满足您的需求。

real = [(1,2), (4,6), (9,10)]  
predicted = [(1,2), (4,4)]
real_set = set(x for a, b in real for x in range(a, b + 1))
predicted_set = set(x for a, b in predicted for x in range(a, b + 1))
print(jaccard(real_set, predicted_set))

这会给你 0.5。

确实存在计算线段交集和并集的更有效算法，其中没有中间转换为整数元素的枚举，但我会坚持使用这种更简单的方法，除非你有线段(a,b) 其中 b - a 是一个非常大的数字。

Answer 3

尽管您在评论中担心区间交集算法很复杂，但事实并非如此。这是我的适合通过计算交集的大小而不是其中的实际间隔来确定相似性。它有一个很好的对称性。

假定输入区间已经排序，该算法的复杂度为 O(|a| + |b|)。

def similarity(a, b):
  ia = ib = prevParity = unionLen = isectLen = 0
  while True:
    aVal = a[ia / 2][ia % 2] if ia < 2 * len(a) else None
    bVal = b[ib / 2][ib % 2] if ib < 2 * len(b) else None
    if not aVal and not bVal: break
    if not bVal or aVal < bVal or (aVal == bVal and ia % 2 == 0):
      parity = prevParity ^ 1
      val = aVal
      ia += 1
    else:
      parity = prevParity ^ 2
      val = bVal
      ib += 1
    if prevParity == 0: unionStart = val
    elif parity == 0: unionLen += val - unionStart + 1
    if parity == 3: isectStart = val
    elif prevParity == 3: isectLen += val - isectStart + 1
    prevParity = parity
  return (0.0 + unionLen - isectLen) / unionLen

print similarity(a, b)

请注意，这是按照@TimothyShields 的建议计算 Jaccard 指数，但它的运行时间和 space 取决于间隔数，其中他取决于总 size 的间隔。

两组区间的相似度

Similarity of two sets of intervals

algorithm

precision

intervals

interval-intersection