Solved – Bisecting K-means using Dynamic Time Warping

clusteringhierarchical clusteringk-meansscalability

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?

Best Answer

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