algorithm - 两组区间的相似度

Question

什么样的算法/解决方案可以用来表示两组范围的相似性(重叠/精度/召回/...)。

我能想到(或在网上找到)数百个类似的问题，但从来没有确切的答案，但这个“轮子”肯定已经被发明出来了......

假设输入数据是这样的:

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

输出应该是~50%

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

谢谢。

(实际长度 ~4000，每组 <50 个间隔)

Answer 1

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

假设输入区间已经排序，该算法的复杂度为 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 指数，但它的运行时间和空间取决于间隔的数量，其中他取决于间隔的总大小。