2組の間隔の類似性

Question

2種類の範囲の類似性（重複/精度/再呼び出し/ ...）を示すために使用できるアルゴリズム/ソリューションの種類。

を：

私は考える（またはオンライン見つける。）同様の問題の何百も決して正確な、しかし確実に、この「ホイール」が既に発明されている必要がありますすることができます...

は、入力されたデータのようなものであることを言うことができます

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

出力は50％

私は一例であり、ビットマップのために、区間木または何を使用すべき〜すべきですか？ 便利な機能やシンプルなアルゴリズムがありますか？意味のある類似性の尺度があれば、合理的な入力形式も同様になります。

ありがとうございます。

（現実的な長〜4000各セットの< 50回の間隔で）

Answer 1

あなたは個々の点にセグメントを壊し、そして本物の/予測とスタート/エンドとして各ポイントにタグを付けることができます。

次にポイントをソートし、ソートされたリストに行き、重複を追跡します。

間隔が最初にRealまたはPredictedであったかどうかを追跡する必要はなく、各点に1つまたは2つの間隔があるかどうかを追跡するだけで済みます。

例：

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です。

Answer 2

類似性を測定するのに、Jaccard indexを使用することができます。これは、「交差を越える交差」とも呼ばれます。 0と1の間の数値です.0は「これらの2つのセットがまったく重ならない」ことを意味し、1は「これら2つのセットが同一」を意味します。 Pythonの3では

、それが実現するのは簡単です：

def jaccard(A, B): 
    if A or B: 
     return len(A & B)/len(A | B) 
    else: 
     return 1.0 

AとBは、2組の値です。理論的には最適ではありませんが、次のアプローチでは、十分に速いニーズがあります。

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は非常に大きな数値です。

Answer 3

コメントには、区間交差アルゴリズムが複雑であるとの心配がありますが、実際はそうではありません。ここでは、実際の間隔ではなく、交差のサイズを計算することによって類似性を判断するようになっています。素晴らしい対称性を持っています。

入力間隔がすでにソートされていると仮定すると、このアルゴリズムは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によって提案されているように、これはジャカードインデックスを計算するが、その実行時と空間が彼の間隔の合計サイズに依存する間隔の数に依存します。