兩組區間的相似性

什麼樣的算法/解決方案可以用來表示兩組範圍的相似性（重疊/精度/回憶/ ...）。兩組區間的相似性

我能想到的（或在網上找到）數以百計的類似的問題，但從來沒有確切的，但肯定這個「輪子」必須已發明了......

比方說，輸入的數據是一樣的東西：

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

兩組區間的相似性

回答

相關問題