2

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

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

假设输入数据类似于：

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

输出应为 ~50 %

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

谢谢你。

（实际长度约为 4000，每组间隔 < 50）

4

3 回答 3

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 索引，但它的运行时间和空间取决于区间数，其中他取决于区间的总大小。

于 2016-11-04T23:58:56.520 回答
0

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

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

您甚至不需要跟踪间隔是否最初来自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)]

然后遍历数组 - 跟踪“打开”的段数并计算 and 的total open长度2 segments open。

结果是 2 segments open/ total open。

于 2016-11-04T18:08:26.997 回答
0

您可以使用Jaccard 指数来衡量相似度，也称为“联合交集”。它是一个介于 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大数字。

于 2016-11-04T18:26:06.510 回答