# Bisecting K-means using Dynamic Time Warping

I'm trying to cluster time series of different length and I came up to an idea to use DTW as a similarity measure, which seems to be adequate, but the thing is, I cannot use it with K-means, since it's hard to define centroids based on time series which can have different length/phase. So I was thinking about Hierarchical clustering, since it seems appropriate to combine with DTW, but it's not scalable. So my next thought is to try with bisecting k-means that seems scalable, since it is based on K-means step repetitions. My idea is next, by steps:

• Take two signals as initial centroids (maybe two signals that have smallest similarity, calculated using DTW)
• Assign all signals to two initial centroids
• Repeat the procedure on the biggest cluster

In this way I could use DTW as distance measure, that could be useful since my data may be shifted, skewed, and avoid calculating centroids. At the end I could take one signal from each cluster that is the most similar with others in cluster (some kind of centroid/medioid).

• possible duplicate of Bisecting K-mediods – Anony-Mousse Jan 10 '15 at 16:57
• Please, don't post duplicate questions. – Anony-Mousse Jan 10 '15 at 16:57
• @Anony-Mousse, they do seem like duplicates, but this one was asked first & seems better developed. We may prefer to close the other as a dup of this. – gung Jan 10 '15 at 17:24
• I really don't know why someone would down vote this question. Seems well developed and reasonable. – forecaster Jan 11 '15 at 2:27

So you are "I'm trying to cluster time series of different length and I came up to an idea to use DTW "...

Either you are

1) In a situation in which you can just make the time series the same length, see section 3 of [a]. In which case, problem solved.

2) You are in a sitation in which you cannot do this. For example, maybe your time series is a mix of one heartbeat, 2 and half heartbeats etc. Which you should clearly not make the same length. In this case you have two sub choices...

Cluster using only subsections of the time series, using u-shaplets [b] Cluster using derived (non-shape) features [c]

If I had to guess from your description only, go with u-shaplets [b], there is free code.

By the way, centroids under DTW was recently solved

[a] http://www.cs.ucr.edu/~eamonn/DTW_myths.pdf [b] http://www.cs.ucr.edu/~eamonn/ClusteringTimeSeriesUsingUnsupervised-Shapelets.pdf [c] Xiaozhe Wang, Kate A. Smith, Rob J. Hyndman: Characteristic-Based Clustering for Time Series Data. Data Min. Knowl. Discov. 13(3): 335-364 (2006) [d] Dynamic Time Warping Averaging of Time Series allows Faster and more Accurate Classification

The bisecting k-means algorithm should work with k-medoids without modifications. So go ahead, and give it a try.

It won't save you time, though. Bisecting reduces the effective $k$, so it will run k-means faster for large values of $k$, at the cost of quality.

But for k-medoids with DTW, the costly part are the distance computations. Once you have computed a full distance matrix (which takes $O(n^2)$ time and memory), regular k-medoids should be your least concern. Have you estimated how long constructing such a matrix will cost you? If you need to accelerate your process, you need to find algorithms that don't need (exact) pairwise distances, but that are compatible with DTW.

• Would you recommend some clustering algorithm that can be used with DTW? Also, is it more expensive to build the whole matrix, and then perform clustering, or to calculate the distances during clustering (like in regular k-medoids)? I'm thinking that by building a matrix I'm generating all possible distances, while I won't need a lot of them. Per example, in some cases point A will never get into cluster X during clustering, because it is too far from it, but if I build matrix I need to calculate that distance also? – Marko Jan 20 '15 at 8:33
• I'd start with a sample of 100 series and hierarchical clustering. If this doesn't work even a little bit, nothing will work. Once you have figured what works, think about scaling it up to the full data set. Don't wast time scaling a method that doesn't work anyway. DTW may be the wrong similarity measure. – Anony-Mousse Jan 20 '15 at 9:04
• Actually, I did try it on a small sample, and K-medoids with DTW gave very satisfying results for my dataset. So, regular K-medoids, no splitting, no merging. Now I've got into phase that I'm considering how to implement it. It supposed to work for Big data and I need to implement it on Hadoop (that is a constraint,even though I know that for smaller set that would be slower). In this moment it seems to me that variant without distance matrix is more appropriate for this,but my question is more general,is it more expensive to build a distance matrix or to calculate some distances repeatedly? – Marko Jan 20 '15 at 9:22
• If you have enough memory, always use a distance matrix (if you use a method that requires pairwise distances. So k-means is an exception, it does not benefit from a distance matrix.) – Anony-Mousse Jan 20 '15 at 13:20