R dtw包裝：累計成本矩陣在沿途的某些點減少？

Question

我正在探索在dtw軟件包中實現的Dynamic Time Warping的結果。在做一些理智檢查時，我發現了一個我無法理順的結果。沿着經線路徑的某些點，累計距離似乎減小。示例如下：

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是非負的距離度量之和，乘以米，其取值爲0或1

我懷疑這是dtw軟件包的實現問題，所以我在哪裏犯了一個錯誤？

另一個完整性檢查（摘自下面的參考文獻）繪製了costMatrix頂部的路徑。以下是指數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

這是由於使用像asymmetricP05 「多步」 遞歸。這種模式允許翹曲路徑由長段組成，例如，騎士的舉動。

要驗證單調性，您應該只有考慮每個「騎士的動作」的起始位置 - 不是所有通過的細胞。 index1和index2屬性確實包括中間單元（以提供更平滑的曲線），這解釋了您的觀察。爲了說服自己：（1）嘗試另一種更直觀的模式，如asymmetric; （2）注意stepsTaken屬性的長度與index1/2不同。