Сходство двух наборов интервалов

Question

Какой алгоритм/решение можно использовать для обозначения сходства (перекрытие/точность/отзыв/...) двух наборов диапазонов.

я могу думать (или найти в Интернете) сотни подобных проблем, но никогда точно, но, конечно, это «колесо», должно быть, были изобретены уже ...

Допустим, что входные данные что-то вроде:

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

Выход должен быть ~ 50%

Если я, например, растровые изображения, использовать интервальные деревьев или что? Есть ли хороший функциональный или простой в написании алгоритм? Любая значимая мера сходства будет делать, и так будет любой разумный формат ввода.

спасибо.

(реалистичная длина ~ 4000 с < 50 интервалов в каждом наборе)

Answer 1

Вы можете разорвать сегменты в отдельные точки, а также пометить каждую точку как реальные/предсказаны и начало/конца.

Затем сортировать точки, просматривать отсортированный список и отслеживать перекрытия.

Вам даже не нужно отслеживать, был ли интервал изначально Real или Predicted - вам просто нужно отслеживать, есть ли один или два интервала в каждой точке.

Пример:

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

Сломался в точках и сортируются (S Старт, E для End):

[(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 означает «эти два набора не перекрываются вообще», а 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 - очень большое количество.

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) 

Примечание Это вычисление индекса Jaccard в соответствии с предложением @TimothyShields, но его выполнения и пространство зависит от числа интервалов, где его зависит от общего размера интервалов.