# Dynamic Time Warping (DTW)

Anh-Thi Dinh

## What (idea)?

Suppose that we need to compare 2 time series (quite look-alike),
• 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.

## 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 → there are 2 voices → wrong prediction!
1. Sound Pattern Recognition: detect the same kind of sound pattern (like the above example).
1. Stock Market:

## Algorithm

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

## Code

``1pip install dtaidistance``
``````1from dtaidistance import dtw
2s1 = [0, 0, 1, 2, 1, 0, 1, 0, 0]
3s2 = [0, 1, 2, 0, 0, 0, 0, 0, 0]
4distance = dtw.distance(s1, s2)
5
6# plot
7from dtaidistance import dtw_visualisation as dtwvis
8import numpy as np
9path = dtw.warping_path(s1, s2)
10dtwvis.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)
``1pip install fastdtw``
``````1import numpy as np
2from scipy.spatial.distance import euclidean
3
4from fastdtw import fastdtw
5
6x = np.array([[1,1], [2,2], [3,3], [4,4], [5,5]])
7y = np.array([[2,2], [3,3], [4,4]])
8distance, path = fastdtw(x, y, dist=euclidean)
9print(distance)``````