在 DTW 中,距离是最短路径元素的总和还是最远元素的总和?

数据挖掘 动态时间扭曲
2022-03-14 21:37:03

标题说了算。在动态时间扭曲中,我一直听说两个距离之间的距离是最短路径元素的总和。但我也将距离视为最远角落的元素?有人可以澄清一下吗。

例子:

x = [0,1,1,2]
z = [0,2,2]

给出这个成本矩阵:

[[ 0. inf inf inf]
 [inf  0.  2.  4.]
 [inf  1.  1.  2.]
 [inf  2.  2.  2.]
 [inf  4.  2.  2.]]

这意味着距离应该是 0 + 0 + 1 + 2 + 2 = 5。但是我发现的每个 dtw 实现都返回距离为 2(即总是返回最远角的元素)。谢谢!

1个回答

该算法的工作原理令人困惑。

DTW 的灵感来自Levenshtein 编辑距离,这是一个有效计算最小距离的动态规划示例。主要思想是增量计算任意两个子序列之间的最小距离。1..i1..j

所以DTW矩阵不是成本矩阵,至少在个体位置之间的成本意义上不是。矩阵之间可能的最小距离,因此最后一个单元格已经包含完整序列的最小距离换句话说,没有什么可求和的,实际上对这些值求和是没有意义的,因为较大的子序列包含较小的子序列。m[i,j]1..i1..jm[m,n]