两组区间的相似度

Question

有什么算法/解决方案可以用来指示两组范围的相似性（重叠/精度/召回率/...）。

我可以想到（或在网上找到）数百个类似的问题，但从未找到完全相同的，但肯定已经发明了这个“轮子”...

假设输入数据如下：

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

输出应该约为50％。

例如，如果我要使用位图AND操作，应该使用区间树还是其他什么？是否有一种好的功能性或简单编写的算法？任何有意义的相似度度量都可以，任何合理的输入格式也可以。

谢谢。

（实际长度约为4000，每个集合中不超过50个间隔）

- user7048002

---

很有趣。几天前，我玩了一下这个问题，它更或多或少地产生了“差异性”。也许它会提供灵感。https://dev59.com/9pzha4cB1Zd3GeqPASA8#40371246 - Gene

我看过那个。那些解决方案看起来不合理复杂，并且只让我完成了一半。由于我没有输入、输出或时间限制，我希望有一种“显然正确”的实现方式。 - user7048002

Answer 1

你可以将段落分解为单独的点，并将每个点标记为真实/预测和开始/结束。

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

你甚至不需要跟踪间隔最初是来自“真实”还是“预测” - 你只需要跟踪每个点是否有一个或两个间隔即可。

例如：

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)]

然后遍历数组 - 跟踪有多少个“打开的”段，并计算总共打开和2个段打开的长度。

结果是2个段打开/总共打开。

- Alex Libov

---

那对于类似于[(2000,3000)...]这样的区间，它能够良好地工作吗？ - user7048002

重要的是间隔的数量而不是实际值。您只需遍历范围的起始和结束位置 - 而不是整个范围... - Alex Libov

将我的解决方案代码添加到这个答案中会有所改善吗？还是我应该只是解释一下我最终做了什么？ - user7048002

你可以添加这段代码。它可能会对未来的某个人有所帮助。 - Alex Libov

Answer 2

尽管您在评论中表达了对间隔交集算法的担忧，但它并不复杂。这是我自己改编的算法，通过计算交集的大小来确定相似性，而不是实际的间隔。它具有良好的对称性。

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

- Gene

Answer 3

你可以使用Jaccard index来测量相似度，也被称为“交集比联合”。它是一个介于0和1之间的数字，其中0表示“这两个集合根本没有重叠”，1表示“这两个集合完全相同”。

在Python 3中，实现起来很容易：

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是一个非常大的数字，否则我建议坚持这种更简单的方法。

- Timothy Shields