algorithm - 两个事件列表的近似匹配(带持续时间)

Question

我有一个黑盒算法，可以分析时间序列并“检测”该序列中的某些事件。它返回一个事件列表，每个事件都包含开始时间和结束时间。事件不重叠。我还有一个“真实”事件的列表，同样包含每个事件的开始时间和结束时间，不重叠。

我想比较这两个列表并匹配检测到的事件和落在特定时间容差内的真实事件(真阳性)。复杂的是，该算法可能会检测到实际上不存在的事件(误报)，或者可能会错过存在的事件(误报)。

什么算法可以对两个列表中的事件进行最佳配对，并使适当的事件不配对？我很确定我不是第一个解决这个问题的人，而且确实存在这样的方法，但我一直没能找到它，可能是因为我不知道正确的术语。

速度要求:列表将包含不超过几百个条目，速度不是主要因素。准确性更为重要。在普通计算机上花费不到几秒钟的时间就可以了。

Answer 1

这是一个二次时间算法，它给出了关于以下模型的最大似然估计。设 A1 < ... < Am 为真实间隔，设 B1 < ... < Bn 为报告间隔。数量 sub(i, j) 是 Ai 变成 Bj 的对数似然。数量 del(i) 是删除 Ai 的对数似然。量 ins(j) 是插入 Bj 的对数似然。处处做独立假设!我将选择 sub、del 和 ins，这样对于每个 i < 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)
                               }.

这确保区间之间的最佳匹配是非交叉的，因此我们可以使用以下 Levenshtein - 像动态程序。

动态程序呈现为内存递归函数 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 以外的幂。如果 Ai = [s, t] 和 Bj = [u, v]，则定义

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

(向几十年前在生物信息学文献中发表过类似内容的现存学者致歉。)