Dynamic Time Warping (DTW) ^draft

The last modifications of this post were around 3 years ago, some information may be outdated!

This is a draft, the content is not complete and of poor quality!

What (idea)?

Suppose that we need to compare 2 time series (quite look-alike),

An example of 2 time series to be compared using DTW. Source of the idea.

• They're quite look-alike but if we compare point-to-point, they're clearly very different!
• With DTW, we compare:
  • hollows of series 1 with ones of series 2.
  • cambers of series 1 with ones of series 2.
• Dynamic Time Warping is used to compare the similarity or calculate the distance between two arrays or time series with different length.

Difference between DTW and Euclidian distance. Source.

How (idea)?

By using a distance matrix, we can find a good distance between 2 timeseries using DTW. Here, $8=3^2-1^2$ and we choose the smallest distance in the nearest position. Source.

More detailed of calculating the distance matrix using DTW. Ai: element ith of A; D[i-1, j-1]: The DTW between element i-1th and j-1th. Source.

When to use?

1. An example: Voice of a man. He can speak fast. He can speak slowly. However, the both voices are his. If we don't use DTW but Euclidian distance, the distance is very large $\Rightarrow$ there are 2 voices $\Rightarrow$ wrong prediction!
2. Sound Pattern Recognition: detect the same kind of sound pattern (like the above example).
3. Stock Market:

Algorithm

1. Divide 2 time series into equal points.
2. Calculate distance between 1st point in TS1 with all points in TS2 and then store the min.
3. Move to 2nd point.
4. Repeat step 2 & 3 but with 2nd point as a reference point.
5. Add up all stored distances. This is a true measure between 2 time series.

👉 Check this video fore a more explanation.

Code

👉 dtaidistance

pip install dtaidistance

from dtaidistance import dtw
s1 = [0, 0, 1, 2, 1, 0, 1, 0, 0]
s2 = [0, 1, 2, 0, 0, 0, 0, 0, 0]
distance = dtw.distance(s1, s2)

# plot
from dtaidistance import dtw_visualisation as dtwvis
import numpy as np
path = dtw.warping_path(s1, s2)
dtwvis.plot_warping(s1, s2, path, filename="warp.png")

👉 Another option: dtw-python

👉 fastdtw (an approximate Dynamic Time Warping (DTW) algorithm that provides optimal or near-optimal alignments with an O(N) time and memory complexity)

pip install fastdtw

import numpy as np
from scipy.spatial.distance import euclidean

from fastdtw import fastdtw

x = np.array([[1,1], [2,2], [3,3], [4,4], [5,5]])
y = np.array([[2,2], [3,3], [4,4]])
distance, path = fastdtw(x, y, dist=euclidean)
print(distance)