兩個事件列表（持續時間）的近似匹配

Question

我有一個黑盒算法，分析時間序列和「檢測」系列中的某些事件。它返回一個事件列表，每個事件都包含一個開始時間和結束時間。事件不重疊。 我也有一個「真實」事件的列表，每個事件的開始時間和結束時間都不重疊。

我想比較兩個列表並匹配檢測到的和真實的事件，這些事件屬於特定的時間容限（真正數）。複雜的是，該算法可能檢測到的事件不是真的（False Positives），或者可能錯過那些事件（False Negatives）。

什麼是算法，從兩個列表中最佳地配對事件，並使適當的事件不成對？我很確定我不是第一個解決這個問題的人，而且這種方法存在，但我一直無法找到它，也許是因爲我不知道正確的術語。

速度要求： 該列表將包含不超過幾百個條目，並且速度不是主要因素。準確性更重要。任何在普通電腦上花費不到幾秒的時間都可以。

Answer 1

這裏是一個二次時間算法，它給出了關於以下模型的最大似然估計。讓A1 < ... <是真實的間隔並讓B1 < ... < Bn是報告的間隔。數量sub（i，j）是Ai變成Bj的對數似然。數量del（i）是Ai被刪除的對數似然值。數量ins（j）是插入Bj的對數似然值。隨處做獨立假設！我要選擇子，德爾和插件等等，對於每一個我< i「和每次J的< J」，我們有

sub(i, j') + sub(i', j) <= max {sub(i, j)  + sub(i', j') 
           ,del(i) + ins(j') + sub(i', j) 
           ,sub(i, j')  + del(i') + ins(j) 
           }. 

這確保了間隔之間的最佳匹配noncrossing，因此該我們可以使用如下的Levenshtein-like動態程序。

該動態程序作爲記憶遞歸函數score(i, j)呈現，其計算匹配A1，...，Ai與B1，...，Bj的最佳分數。調用樹的根是score(m, n)。可以修改它以在最佳解決方案中返回sub(i, j)操作的順序。

score(i, j) | i == 0 && j == 0 =  0 
      | i > 0 && j == 0 =  del(i) + score(i - 1, 0 ) 
      | i == 0 && j > 0 =  ins(j) + score(0 , j - 1) 
      | i > 0 && j > 0 = max {sub(i, j) + score(i - 1, j - 1) 
            ,del(i) + score(i - 1, j ) 
            ,ins(j) + score(i , j - 1) 
            } 

以下是sub，del和ins的一些可能的定義。我不確定他們是否會有好處;您可能希望通過比2。其他常量或使用權力來增加他們的值如果艾= [S，T]和Bj = [U，V]，然後定義

sub(i, j) = -(|u - s|^2 + |v - t|^2) 
del(i) = -(t - s)^2 
ins(j) = -(v - u)^2. 

（道歉到現存無疑學術誰在幾十年前的生物信息學文獻中發表了類似的文章）。