algorithm - 时间序列与连续和分类数据对齐

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 distance 非常相似问题，您可以在那里采用相同的算法。

首先定义成本函数。

然后，在二次表上运行动态规划:对于每个 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])

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