R dtw包: cumulative cost matrix decreases at some points along the path?

Question

我正在探索 dtw 包中实现的动态时间扭曲的结果。在进行一些健全性检查时，我发现了一个我无法合理解释的结果。在扭曲路径上的某些点，累积距离似乎会减小。下面的例子:

mat= structure(c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.01,0.01,0.02,0.03,0.04,0.06,0.09,0.11,0.13,0.16,0.18,0.2,0.22,0.24,0.24,0.22,0.22,0.22,0.22,0.21,0.2,0.19,0.2,0.23,0.29,0.34,0.41,0.51,0.62,0.73,0.82,0.9,0.95,1,1,1,0.92,0.92,0.89,0.89,0.84,0.79,0.7,0.53,0.37,0.23,0.17,0.13,0.11,0.09,0.08,0.07,0.07,0.07,0.07,0.07,0.07,0.08,0.08,0.08,0.09,0.1,0.13,0.15,0.19,0.22,0.27,0.29,0.34,0.35,0.36,0.35,0.38,0.37,0.37,0.32,0.3,0.26,0.24,0.21,0.19,0.17,0.15,0.14,0.12,0.1,0.09,0.09,0.08,0.08,0.07,0.07,0.07,0.07,0.06,0.06,0.06,0.05,0.05,0.05,0.05,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.03,0.04,0.04,0.04,0.03,0.03,0.03,0.04,0.04,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.01,0.01,0.01,0.02,0.02,0.03,0.04,0.05,0.06,0.07,0.08,0.1,0.12,0.12,0.13,0.14,0.15,0.17,0.19,0.2,0.21,0.22,0.24,0.23,0.24,0.26,0.3,0.32,0.33,0.35,0.39,0.44,0.49,0.55,0.61,0.67,0.71,0.76,0.83,0.9,0.97,1,0.99,0.86,0.68,0.5,0.41,0.33,0.28,0.23,0.2,0.17,0.15,0.13,0.12,0.1,0.1,0.1,0.11,0.11,0.11,0.11,0.11,0.11,0.11,0.13,0.15,0.17,0.18,0.2,0.21,0.24,0.25,0.28,0.29,0.32,0.35,0.36,0.34,0.32,0.3,0.3,0.28,0.26,0.23,0.22,0.19,0.17,0.15,0.14,0.12,0.1,0.09,0.09,0.08,0.08,0.07,0.07,0.07,0.06,0.06,0.05,0.05,0.05,0.05,0.05,0.05,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04,0.04),.Dim=c(149L,2L))
tw = dtw(mat[,1], mat[,2], keep.internals = T, step.pattern = asymmetricP05)

.

d.phi = tw$costMatrix[ cbind(tw$index1, tw$index2) ]

which(diff(d.phi) < 0)
# 45  50  53  54  61  70  72  73  80  81 101 115 117 120 124 125 129 139 184 189 191 193

plot(diff(d.phi))

事实并非如此，因为 d_phi 是非负距离测量值的总和，乘以 m(取值为 0 或 1)。

我怀疑这是 dtw 包的实现问题，那么我在哪里犯了错误？

另一个健全性检查(取自下面的引用文献)在成本矩阵顶部绘制了路径。下面绘制了索引 45:55，其中我们看到 45、50、53 和 54 的累积成本不断减少(来自上面的 diff(d.phi))。第一个转换是 diff(d.phi)[45]。

i = 45:55
i1 = tw$index1[i]
i2 = tw$index2[i]
r= range(c(i1,i2))
s = r[1]:r[2]

ccm <- tw$costMatrix[s,s]
image(x=1:nrow(ccm),y=1:ncol(ccm),ccm)
text(row(ccm),col(ccm),label=round(ccm,3))
lines(i1-r[1]+1,i2-r[1]+1)

如果这是DP算法所采取的实际路径，那么沿着这条路径的累积距离在那些点处如何减少？

http://cran.r-project.org/web/packages/dtw/vignettes/dtw.pdf

Answer 1

这是由于使用了“多步”递归，例如asymmetryP05。这种图案允许扭曲路径由长段组成，例如骑士的 Action 。

为了验证单调性，您应该仅考虑每个“骑士 Action ”的起始位置 - 而不是所有经过的单元格。 index1 和 index2 属性确实包含中间单元格(以提供更平滑的曲线)，这解释了您的观察结果。

要说服自己:(1) 尝试另一种更直观的模式，例如不对称； (2) 请注意 stepsTaken 属性的长度与 index1/2 不同。