Clustering time series data using dynamic time warping

Question

I would like to cluster/group the curves in the attached picture with Python. The data is already normalized and my approach would be to use dtw (dynamic time warping) to calculate the distance and with that feature use a clustering algorithm (like kmeans or DBSCAN) to classify them.

Do I pick out one trajectory as a starting curve to compare the other curves to, or do I calculate an 'average' curve of all curves and use that as the starting curve to compare to?

Moreover I am not completely sure how to interpret the dtw distance. Please have a look at the code below:

from dtaidistance import dtw
import numpy as np    
y=np.random.randint(0,10,10)   
y1=y+2  
dist=dtw.distance(y,y1)

The shape of the two curves should be exactly the same just shifted on the y-axis, but the dtw still calculates a distance greater than 0. Is this because of the fact the two curves are not normalized and then would be aligned exactly over each other? I always had the impression dtw measures the similarity of the shape of two curves and therefore is susceptible to shifting or stretching. I am just worried that if a curve has a different shape, but is near the compared curve, the dtw distance will be way smaller than the dtw distance of two exact same, but shifted curves.

Answer 1

Dynamic time warping (DTW) is for temporal alignments. You are comparing non-temporal alignment by adding a constant between the two time series.

Here is an example of temporal alignment by shifting 1 time unit between the two time series. The result is a DTW distance of 1.

from dtaidistance import dtw
import numpy as np    

y = np.random.randint(0,10,10)   
y1 = y[1:]
dist = dtw.distance(y, y1)

Answer 2

I'll work from the bottom up:

I am not completely sure how to interpret the dtw distance.

Dynamic Time Warping measures the distance between series of data points where the order of data points in each series is informative. In your case your data points are pressure measurements and your informative sorting order is the position at the time of measurement.

For a dummy example, lets say you had two rounds of pressure measurements, sorted them by the position they were collected at and stored it as two python lists:

pressures_a = [10, 2, 1, 5, 60, 1]
pressures_b = [10, 3, 60]

Under the hood, Dynamic Time Warping is asking "what's the smallest euclidean distance between these two lists?" I'll skip the algorithm to find that answer, and focus on the information that makes it into the result:

>>> imaginary_DTW_function(pressures_a, pressures_b, loss="abs")

Best pair-up cost:
  |10 - 10| =  0
  | 2 -  3| =  1
  | 1 -  3| =  2
  | 5 -  3| =  2
  |60 - 60| =  0
  | 1 - 60| = 59

DTW Distance: 64

Notice how the final result stretches pressures_b's 3 to avoid having to pair small numbers with 60, but there's no way to avoid that huge cost at the end: Everything has to match with something, preserving order, allowing any part of the series to "stretch".

The "DTW distance" you get back is the sum of the "loss" for the best alignment. In my fake DTW function I used the absolute distance (a.k.a. L1, cityblock, 1D, etc). Dynamic Time Warping implementations by default use the euclidean distance.

The shape of the two curves (y, y1) should be exactly the same just shifted on the y-axis, but the dtw still calculates a distance greater than 0. Is this because of the fact the two curves are not normalized and then would be aligned exactly over each other?

Regarding your example with y and y1: The distance between the matching elements between the two is by design sqrt((x - (x+1))^2) (which is 1). You have 10 of these elements so the DTW is 10*.

You can run scaled or unscaled data through Dynamic Time Warping and get very different results (but both informative) results. The magnitude of the distance you receive depend on your units.

I would like to cluster/group the curves in the attached picture with Python. The data is already normalized and my approach would be to use dtw (dynamic time warping) to calculate the distance and with that feature use a clustering algorithm (like kmeans or DBSCAN) to classify them.

Do I pick out one trajectory as a starting curve to compare the other curves to, or do I calculate an 'average' curve of all curves and use that as the starting curve to compare to?

This is a great blog post if you want to get more intuition on Dynamic Time Warping, but you'll find the important bit to clustering if you skip to the "Properties" section. TLDR, Dynamic Time Warping is not a true metric (though in some datasets you can test if it does behave like a true metric!). Picking or making a single trajectory to compare to can be catastrophic/uninformative.

If you think DTW distance is a useful comparison given your domain knowledge, I would start with one of these:

1. Build the full DTW distance matrix for this dataset, and pass the distance to DBSCAN (metric='precomputed' doc here).

2. There are some libraries that perform K-means clustering using Dynamic Time Warping as the metric. (e.g. tslearn TimeSeriesKMeans).

You can always get fancier for DTW-based clustering, or try non-DTW approaches, but if this distance is a reasonable pick for your problem and you want to get the feel for DTW clustering results I'd try these approaches.

*(On average, and if we don't wake up the statistical methods people)