I am exploring the results of Dynamic Time Warping as implemented in the dtw package. While doing some sanity checks I came across a result which I cannot rationalize. At some points along the warp path, the cumulative distance appears to decrease. Example below:
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))
This should not be the case, as d_phi is a sum of non-negative distance measures, multiplied by m which takes values 0 or 1.
I doubt this is an implementation problem with the dtw package, so where am I making a mistake?
Another sanity check (taken from the reference below) plots the path on top of the costMatrix. Below is plotted indices 45:55 in which we see 45, 50, 53, and 54 have decreasing cumulative cost (from above diff(d.phi)
). The first transition is 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)
If this is the actual path taken by the DP algorithm, how can the cumulative distance along this path decrease at those points?
http://cran.r-project.org/web/packages/dtw/vignettes/dtw.pdf