Dynamic Time Warping and Time Series Clustering

Introduction

Working with a set of time series measuring related observations requires a different set of tools compared to analyzing or forecasting a single time series.

If you want to cluster time series into groups with similar behaviors, one option is feature extraction: statistical summaries that characterize some feature of the time series, such as min, max, or spectral density. The feasts R package and the Python package tsfresh provide tools to make this easier.

Why not cluster on the time series directly? Standard methods don’t work as well, and can produce clusters that fail to capture visual similarities in shape and size.

Dynamic time warping is method that aligns with intuitive notions of time series similarity. To show how it works, I’ll walk through

1. how standard distance metrics fail to create useful time series clusters

2. dynamic time warping distance as a method for similarity

Distance Metrics

To cluster, we need to measure the distance between every member of the group.¹ Typically we think of Euclidean distance: the length of a straight line between two points.

This distance pops up all the time in data science, usually in Mean Squared Error (MSE) or it’s counterpart Root Mean Squared Error (RMSE). These metrics are used to measure regression error in machine learning and assess the accuracy of a time series forecast.

To evaluate the fit of the forecast to the actual data, you can calculate the Euclidean distance between the corresponding points in the time series and the forecasts. The smaller the distance, the better the forecast: the more similar the two series are.

A straight line between two points isn’t always the possible. In a city grid, we are constrained by the blocks. In this situation, the distance between two points is called the Manhattan distance.

Time series also need a special distance metric. The most common is called Dynamic Time Warping.

##           red    blue
## blue  9.83149        
## green 9.78531 9.82103

Dynamic Time Warping

To capture our intuition about the similarity of red and blue, we need a new metric. This metric can’t simply measure the point-to-point distance between the series. As we saw, blue is shifted to the left of red, even though the shape is really similar. We need to warp time to account for this shift!

In the visualizations below², you can see how dynamic time warping stretches (warps) time to match up nearby points.

When comparing red to green below, there is a lot more warping going on to match up points (as measured by the light gray concentric lines between the series), so the time series are more dissimilar.

The dissimilarity between red and green is reflected when we calculate the dynamic time warping distance.

##            red     blue
## blue  28.26073         
## green 33.82476 31.50148