Dynamic Time Warping with Time Series

Shachia Kyaagba
Sep 7, 2018 · 4 min read

A time series is a sequence of events that is represented in order of the time the events occur. There are a plethora of natural and man made time series events that are constantly occurring in the world around us; temperatures, commodity prices, school grades, etc.

The value of time series is the fact that it can be used to assess the past and give us a possible peek into the future. There are two main operations that are performed on a time series:

  1. Analysis of a single time series.
  2. Analysis of multiple time series.
https://giphy.com/gifs/data-wfRzXJN2CxOGQ

In this blog post I will concentrate on the second operation, the analysis of multiple time series, and on one use case in particular: finding similarities between multiple time series.

In a perfect world we could easily calculate the similarity between two time series by simply calculating the euclidean distance (shortest path between two points) between points on both time serie that occur at the same time. This is a good metric for similarity if both time series are in sync and move at exactly the same speed and time (i.e. all similar events in both time series occur at exactly the same time). Things begin to fall apart very quickly when the series are out of sync. This means that the similar points on both series are being stretched farther apart by time. As such the euclidean distances are getting larger and one concludes that the series are becoming less similar.

Let’s think about it in another way. I know what my dad’s voice sounds like. When he speaks fast I’m able to recognize the voice as his. When he speaks slowly I’m still able to recognize the voice as his. If I were to plot his fast voice and slow voice as a time series and calculate the euclidean distance between them, from a euclidean distance standpoint those two time series would have very low similarity and as such would not be considered to be fundamentally the same. This would then lead to the conclusion that the two voices did not come from the same person. BUT. THEY. DID. THOUGH.

https://link.springer.com/content/pdf/10.1007/s10994-005-5828-3.pdf

Now that we have established that euclidean distance isn’t the best measure of similarity, we have to figure out another measure of time series similarity that takes time out of the equation (or standardizes it).

Dynamic Time Warping

https://gifer.com/ru/P5qm

Dynamic time warping is an algorithm used to measure similarity between two sequences which may vary in time or speed. It works as follows:

  1. Divide the two series into equal points.
  2. Calculate the euclidean distance between the first point in the first series and every point in the second series. Store the minimum distance calculated. (this is the ‘time warp’ stage)
  3. Move to the second point and repeat 2. Move step by step along points and repeat 2 till all points are exhausted.
  4. Repeat 2 and 3 but with the second series as a reference point.
  5. Add up all the minimum distances that were stored and this is a true measure of similarity between the two series.
http://www.mathcs.emory.edu/~lxiong/cs730_s13/share/slides/searching_sigkdd2012_DTW.pdf

The steps above have followed some constraints in order to optimize the solution found. Without these constraints, with every grid added there would be an exponential increase in the different ways to pick points at which to calculate distances.

http://www.mathcs.emory.edu/~lxiong/cs730_s13/share/slides/searching_sigkdd2012_DTW.pdf
http://www.mathcs.emory.edu/~lxiong/cs730_s13/share/slides/searching_sigkdd2012_DTW.pdf
http://www.mathcs.emory.edu/~lxiong/cs730_s13/share/slides/searching_sigkdd2012_DTW.pdf
http://www.mathcs.emory.edu/~lxiong/cs730_s13/share/slides/searching_sigkdd2012_DTW.pdf

You might have noticed that in finding the minimum distances along the grid (the red dots), we also created an optimum path from from the bottom left of the grid to the top right. This path is called the warping path and as with anything that follows a set of rules it has a function that defines those set of rules. This function is called the warping function. When the warping function is applied to both time series it transforms them to two new time series that are aligned in time.

Additional Resources

  1. Fast and Exact Warping of Time Series Using Adaptive Segmental Approximations by Yutau Shou, Nikos Mamoulis, David W. Cheung
  2. Dynamic Time Warping by Elena Tsiporkova

3. https://en.wikipedia.org/wiki/Dynamic_time_warping

Shachia Kyaagba

Written by

Lover of all things data

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade