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, and we choose the smallest distance in the nearest position. Source.
More detailed of calculating the distance matrix using DTW.
D[i-1, j-1]: The DTW between element
When to use? #
- 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 there are 2 voices wrong prediction!
- Sound Pattern Recognition: detect the same kind of sound pattern (like the above example).
- Stock Market:
- Divide 2 time series into equal points.
- Calculate distance between 1st point in TS1 with all points in TS2 and then store the min.
- Move to 2nd point.
- Repeat step 2 & 3 but with 2nd point as a reference point.
- Add up all stored distances. This is a true measure between 2 time series.
👉 Check this video fore a more explanation.
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)
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)