Programming

Dynamic Time Warping Explained

The Intuition behind Dynamic Time Warping & Python Implementation on Stock Data

Image from Unsplash taken by Agê Barros

This article will cover the intuition and mathematics behind Dynamic Time Warping. Upon building a solid understanding for the reader, the article will proceed to apply DTW in the stock market for finding stocks that have similar performances with other very high-performing stocks. If this is interesting for you, keep reading as the table of contents outlines the structure of the article below.

Table of Contents

• What is Dynamic Time Warping (DTW)
  - Algorithm
  - Implementation
  - Library Implementation
• Problem Statement
  - Data
  - Benchmark Portfolio
  - Identify Similar Stocks
  - Visualize
• Concluding Statements
• Resources

What is Dynamic Time Warping (DTW)?

Dynamic time warping (DTW) was introduced in 1968 by Vintsyuk, T.K. in his paper discussing Speech discrimination by dynamic programming [3]. The algorithm is commonly used in time series analysis. Intuitively, the algorithm tells you two key things about the data you’re working with.

1. Which point(s) in the first time series corresponds with the point(s) in the other time series (as seen in Figure 1)
2. How similar are the two-time series

Figure 1: Two time series being compared to each other, the left is done through Euclidean distance (1 to 1 matching), the right is done through DTW (1 to many matching). (Image provided by author)

Now the naive way to see how similar two-time series are would be to take the Euclidean distance between each corresponding pair of points, as seen on the left-hand side of Figure 1. Dynamic time warping however takes into account the time at which each point was generated, thus you are able to map 1 point in the upper time series to many points in the lower time series because that is the number of points each time series generated in that time step.

As you can see, the beauty of this algorithm is that the two-time series you are comparing don’t necessarily need to start at the same time or move at the same time. You will still be able to identify the…