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?
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.
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.
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.
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.
 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.
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.
For each series, calculate distances via DTW for each center in each cluster groups and assign it to the minimum one.
For each cluster groups, calculate total distance within individual clusters.
I used this for a small project. Here is the my repository about Time Series Clustering and my other answer about this.
Not the answer you're looking for? Browse other questions tagged time-series clustering or ask your own question.
How to compare and cluster sets of daily time series?
Which clustering techniques can be used with Dynamic Time Warping (other than Hierarchical clustering)?
Can someone please explain dynamic time warping for determining time series similarity?
Does it make sense to use dynamic time warping when clustering time series that all have the same length and sampling interval?
What are some fast alternatives to dynamic time warping?