两组区间的相似性

什么样的算法/解决方案可以用来表示两组范围的相似性（重叠/精度/回忆/ ...）。两组区间的相似性

我能想到的（或在网上找到）数以百计的类似的问题，但从来没有确切的，但肯定这个“轮子”必须已发明了......

比方说，输入的数据是一样的东西：

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

输出应该〜50％

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

谢谢。

（现实长度〜4000与<在每一组50米的间隔）

来源

2016-11-04 arctiq

迷人。几天前，对这个问题起了一点作用，这或多或少产生了_dissimilarity_。也许它会提供ides。 http://stackoverflow.com/questions/40367461/intersection-of-two-lists-of-ranges-in-python/40371246 – Gene

我见过那个。解决方案似乎过于复杂，只能让我走到一半。由于我没有输入，输出或时间限制，我希望有一种“明显正确”的实现。 – arctiq

你可能会折断段各个点，并且作为真正的/预测的标记每个点和开始/结束。

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

您甚至不需要追踪间隔最初是从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)]

然后通过阵列去 - 跟踪多少段的“是打开“并计算长度为total open和2 segments open。

结果是2 segments open/total open。

来源

2016-11-04 18:08:26

对于间隔如[（2000,3000）...]的实际案例，这会有多好？ – arctiq

重要的是间隔的数量而不是实际值。你只是去了范围的开始和结束 - 不通过整个范围... –

将加入我的解决方案代码改进此答案？或者我应该解释我最终做了什么？ – arctiq

您可以使用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是一个非常大的数字。

来源

2016-11-04 18:26:06

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

假设输入间隔已经排序，此算法为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，但它的运行时间和空间依赖于区间的数目，他的依赖于间隔的总大小。

来源

2016-11-04 23:58:56 Gene

两组区间的相似性

回答

相关问题