时间序列与连续数据和分类数据的比对

Question

我有一系列的时间测量，我想对齐。我有注解器在信号中判断和标记模棱两可的事件，并希望最佳地匹配它们的时间和事件。输入是四列:一个注释器的事件开始时间和标签，另一个注释器的时间和标签。例如(作为行)：

annotator_1_times: .34, .39, .50, .68, .88

annotator_1_label:   A,   X,   Q,   L,   Z

annotator_2_times: .33, .41, .67, .90

annotator_2_label:   A,   X,   L,   X

注释器在解释相同的信号时不一定有相同数量的事件。注解器一般都有相似但不相同的标签，相似但不相同的时间。

如何做到这一点取决于某种成本函数--这将决定一段时间离开一定数量的情况有多“糟糕”，而两个标签则不同意。

在我的示例中，有一个理想的输出：

   annotator_1_times: .34, .39, .50, .68, .88

   annotator_1_label:   A,   X,   Q,   L,   Z

   annotator_2_times: .33, .41,  [], .67, .90    <-note gap inserted

   annotator_2_label:   A,   X,  [],   L,   X

然后我会做一些临时的事情：

time_mismatch_dif: .01, .02,  XX, .01, .02    <- for computing agreemt

label_mismatches_:   0,   0, ADD,   0, SUBST  <- for computing agreemt

最难的部分是知道在哪里插入缺口。

如果需要，我可以做数字对齐和单独只是标签对齐，然后以某种方式合并它们。我知道有字符对齐算法(例如在遗传学中)，而且必须有时间序列对齐算法。

欢迎任何建议。

Answer 1

您的问题非常类似于Levenshtein距离问题，您可以在那里适应相同的算法。

首先定义你的成本函数。

然后，在二次表上运行动态规划:对于每个i和j计算ans[i][j]，即第一个注释器中的第一个i事件和第二个注释器中的第一个j事件的“对齐成本”。这可以通过三种方式实现：

• 要么你把i和j对齐，然后ans[i][j]变成ans[i-1][j-1] + costAlignment(a[i],b[j])
• 要么你对齐i和'gap'，然后ans[i][j]变成ans[i-1][j] + costGap(a[i])
• 要么你对齐j和'gap'，然后ans[i][j]变成ans[i][j-1] + costGap(b[j])

您应该至少选择三个选项。