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.
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.
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):
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.
Yes. A naive and potentially slow approach might be,
n! / k! / (n-k)!. These would be something like potential centers.I used this for a small project. Here is the my repository about Time Series Clustering and my other answer about this.
