0
$\begingroup$

In Data Analysis, Dynamic Time Warping is a method to better speify the similarity between two time series: https://en.wikipedia.org/wiki/Dynamic_time_warping

What is the purpose of introducing a cost function for the cell of the matrix of the DTW measure?

As we know, we would like to identify the optimal path that allows us to go from the index <1,1> to the index <n,m> of the matrix, where n and m are the respective sizes of the two time series we are comparing.

But instead of using a cost function defined as

cost[i, j] := d(i,j) + minimum(cost[i-1, j], cost[i, j-1], cost[i-1,j-1])  

Could't we just use the raw distance measure?

Following the intuition that given a cell <i,j> the best possible successive for step for an optimal path will be one one among <i+1,j+1>, <i+1,j> or <i,j+1>, we could identify the best path simply starting from cell <1,1> and choosing the cell with the minimum distance among <2,2>,<2,1> or <1,2>, then moving to that cell and go on up until we reach <n,m>.

I do not understand why a cost measure such as the one defined above should be useful in this context, where we could just use the simple distance.

$\endgroup$

1 Answer 1

3
$\begingroup$

Here's an example that shows why that doesn't work.

Take the two time series:

$T_1 = [1, 2, 3, 4, 5]$

$T_2 = [1, -4, 3, 4, 5]$

And construct the local distance matrix:

$$ \begin{array}{cc|c:c|} &&T_1 \\ && 1 & 2 & 3 & 4 & 5 \\ \hline T_2& 1 & 0 & 1 & 2 & 3 & 4 \\ \hdashline & -4 & 5 & 6 & 7 & 8 & 9 \\ \hdashline & 3 & 2 & 1 & 0 & 1 & 2 \\ \hdashline & 4 & 3 & 2 & 1 & 0 & 1 \\ \hdashline & 5 & 4 & 3 & 2 & 1 & 0 \\ \hline \end{array} $$

Clearly, the best alignment is along the diagonal, but if we started at (1, 1) and repeatedly move to the lowest of <i+1,j+1>, <i+1,j> or <i,j+1> as you suggest, we would follow along the top then down the right side.

Following the DTW algorithm gives the following cost matrix:

$$ \begin{array}{cc|c:c|} &&T_1 \\ && 1 & 2 & 3 & 4 & 5 \\ \hline T_2& 1 & 0 & 1 & 3 & 6 & 10 \\ \hdashline & -4 & 5 & 6 & 8 & 11 & 15 \\ \hdashline & 3 & 7 & 6 & 6 & 7 & 9 \\ \hdashline & 4 & 10 & 8 & 7 & 6 & 7 \\ \hdashline & 5 & 14 & 11 & 9 & 7 & 6 \\ \hline \end{array} $$ which gives a DTW distance of 6 as expected.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.