An introduction to Dynamic Time Warping
This post is the first in a series about assessing similarity between time series. More specifically, we will be interested in alignment-based metrics, Here we use the term “metrics” in a pretty unformal manner, that is an equivalent of “similarity measure.” that rely on a temporal alignment of the series in order to assess their similarity.
Before entering into more details about these metrics, let us define our base objects: time series. In the following, a time series is a sequence of features: \(x = (x_0, \dots, x_{n-1})\) . All features from a time series lie in the same space \(\mathbb{R}^p\) . Below is an example univariate A time series is said univariate if all its feature vectors are monodimensional (\(p=1\) ). time series:
Here, we are computing similarity between two time series using either Euclidean distance (left) or Dynamic Time Warping (DTW, right), which is an instance of alignment-based metric that we will present in more details later in this post. In both cases, the returned similarity is the sum of distances between matched features. Here, matches are represented by gray lines and the distance associated to a match between \(i\) -th feature in time series \(x\) and \(j\) -th feature in time series \(x^\prime\) is \(d(x_i, x^\prime_j)\) . Note how DTW matches distinctive patterns of the time series, which is likely to result in a more sound similarity assessment than when using Euclidean distance that matches timestamps regardless of the feature values.
