# Dynamic Time Warping Clustering

What would be the approach to use Dynamic Time Warping (DTW) to perform clustering of time series?

I have read about DTW as a way to find similarity between two time series, while they could be shifted in time. Can I use this method as a similarity measure for clustering algorithm like k-means?

• yes, you could use similarity measure as an input to k means clustering and then determine groups in your data. – forecaster Jan 5 '15 at 15:40
• Thank you for your answer Sir. I'm guessing that for each iteration I would need to form the distance matrix for each (centroid, clustering point) couple, and recalculate centroids in standard fashion, as a mean of all series that belong to cluster? – Marko Jan 5 '15 at 15:57
• Aleksandr Blekh in the answer below has a blog post that provides a detailed example on how to do this in R. – forecaster Jan 5 '15 at 16:12
• @forecaster do not use k-means with DTW. k-means minimizes variance, not distances. Variance is squared Euclidean, but that does not mean k-means could optimize other distances. The mean doesn't, and in DTW it should be rather easy to construct counterexamples, like a sine wave offset by $\pi$: both are very similar by DTW, but their mean is constant zero - very dissimilar to both. – Anony-Mousse Jan 5 '15 at 22:30
• K-means is not an appropriate algorithm for time series clustering. Hidden markov models for discrete, longitudinal data are appropriate. There are several books out now on this topic as well as key contributions from Oded Netzer (Columbia) and Steve Scott (Google). Another approach would be the information-theoretic method developed by Andreas Brandmaier at Max Planck called permutation distribution clustering. He has also written an R module. Comparison of cluster solutions is a different issue. Marina Meila's paper, Comparing Clusterings, U of Washington Statistics Tech Report 418 is best. – DJohnson Jun 5 '15 at 20:26

Do not use k-means for timeseries.

DTW is not minimized by the mean; k-means may not converge and even if it converges it will not yield a very good result. The mean is an least-squares estimator on the coordinates. It minimizes variance, not arbitrary distances, and k-means is designed for minimizing variance, not arbitrary distances.

Assume you have two time series. Two sine waves, of the same frequency, and a rather long sampling period; but they are offset by $\pi$. Since DTW does time warping, it can align them so they perfectly match, except for the beginning and end. DTW will assign a rather small distance to these two series. However, if you compute the mean of the two series, it will be a flat 0 - they cancel out. The mean does not do dynamic time warping, and loses all the value that DTW got. On such data, k-means may fail to converge, and the results will be meaningless. K-means really should only be used with variance (= squared Euclidean), or some cases that are equivalent (like cosine, on L2 normalized data, where cosine similarity is the same as $2 -$ squared Euclidean distance)

Instead, compute a distance matrix using DTW, then run hierarchical clustering such as single-link. In contrast to k-means, the series may even have different length.

• Well, there is of course PAM (K-medoids) which works with arbitrary distances. One of the many algorithms which support arbitrary distances - k-means does not. Other choices are DBSCAN, OPTICS, CLARANS, HAC, ... – Anony-Mousse Jan 6 '15 at 19:29
• Probably. Because k-medoids uses DTW-medoid for finding the cluster center, not the L2 mean. I don't know of any real world successful clustering of time series. I believe I've seen papers, but none that really used the result. Only proof-of-concepts. – Anony-Mousse Jan 7 '15 at 20:54
• @Aleksandr Blekh gave this as one of his examples nbviewer.ipython.org/github/alexminnaar/… What is your opinion about it? – Marko Jan 8 '15 at 10:26
• Toy problems. Useless in real world. Real data has plenty of noise, which will hurt much more than smooth sine curves and the patterns presented in this data. – Anony-Mousse Jan 8 '15 at 12:43
• I think hierarchical clustering is the better choice. You won't be able to process a huge number of series anyway. – Anony-Mousse Jan 8 '15 at 15:31

Yes, you can use DTW approach for classification and clustering of time series. I've compiled the following resources, which are focused on this very topic (I've recently answered a similar question, but not on this site, so I'm copying the contents here for everybody's convenience):

• +1 excellent collection of articles and blogs. Very good references. – forecaster Jan 5 '15 at 16:02
• @forecaster: Thank you for the upvote and kind words! Glad you like the collection. It's too sad that currently I don't have time to learn forecasting and many other areas of statistics and data science more seriously, but I use every opportunity to learn something new. – Aleksandr Blekh Jan 5 '15 at 16:13
• @AleksandrBlekh Thanks very much you for your answer, I've been discussing with Anony-Mousse about this aproach, since I'm particularly interested in DTW as a similarity measure for K-means, so I could get centroids as output. What is your opinion and experience with it? As you can see Anony-Mousse gave some arguments that the results may not be so good in this case... Maybe some personal experience in a practical matter? – Marko Jan 8 '15 at 10:30
• Ok, thanks again. You have +1 from me and he gets answer accepted, since my question is more oriented towards k-means and DTW. – Marko Jan 8 '15 at 15:08
• @pera: My pleasure. Thanks for upvoting. Totally understand and agree about acceptance, no problem at all. – Aleksandr Blekh Jan 8 '15 at 16:52

A recent method DTW Barycenter Averaging (DBA) has been proposed by Petitjean et al. to average time series. In an other paper they proved empirically and theoretically how it can be used to cluster time series with k-means. An implementation is provided on GitHub by the authors (link to code).

1 F. Petitjean, G. Forestier, G. I. Webb, A. E. Nicholson, Y. Chen and E. Keogh, "Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification," 2014 IEEE International Conference on Data Mining, Shenzhen, 2014.

2 F. Petitjean, P. Gançarski, Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment, Theoretical Computer Science, Volume 414, Issue 1, 2012

Dynamic Time Warp compares the realized data points, which may or may not work. A more rigorous approach is to compare the distribution of the time series by way of a metric called telescope distance.

The cool thing about this metric is that the empirical calculation is done by fitting a series of binary classifiers such as SVM.

For a brief explanation, see this.

For clustering time series, it's been shown to outperform DTW; see Table 1 in the original paper[1].

[1] Ryabko, D., & Mary, J. (2013). A binary-classification-based metric between time-series distributions and its use in statistical and learning problems. The Journal of Machine Learning Research, 14(1), 2837-2856.

• An attempted editor notes: "Jérémie Mary (co-author) has a web page discussing the algorithm with an R implementation. – gung Apr 27 '18 at 13:12
• @gung Wow, excellent! I had correspondence with first author and he didn't mention this. – horaceT Apr 27 '18 at 16:26
• I'm actually just copying over from someone who tried to edit this into your answer, @horaceT. I don't know too much about it. – gung Apr 27 '18 at 17:12

Yes. A naive and potentially slow approach might be,

1. Create your all cluster combinations. k is for cluster count and n is for number of series. The number of items returned should be n! / k! / (n-k)!. These would be something like potential centers.
2. For each series, calculate distances via DTW for each center in each cluster groups and assign it to the minimum one.
3. For each cluster groups, calculate total distance within individual clusters.
4. Choose the minimum.