Dynamic Time Warping (DTW)

Anh-Thi Dinh
Machine LearningTime Series

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. 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 → 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

👉 dtaidistance
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)