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).
What do you think about this approach and about the scalability? 
 A: 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

*

*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.


*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

A: 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.
