3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ possible duplicate of Bisecting K-mediods $\endgroup$
    – Has QUIT--Anony-Mousse
    Jan 10, 2015 at 16:57
  • $\begingroup$ Please, don't post duplicate questions. $\endgroup$
    – Has QUIT--Anony-Mousse
    Jan 10, 2015 at 16:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – gung - Reinstate Monica
    Jan 10, 2015 at 17:24
  • 2
    $\begingroup$ I really don't know why someone would down vote this question. Seems well developed and reasonable. $\endgroup$
    – forecaster
    Jan 11, 2015 at 2:27

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Kobe-Wan Kenobi
    Jan 20, 2015 at 8:33
  • $\begingroup$ 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. $\endgroup$
    – Has QUIT--Anony-Mousse
    Jan 20, 2015 at 9:04
  • $\begingroup$ 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? $\endgroup$
    – Kobe-Wan Kenobi
    Jan 20, 2015 at 9:22
  • $\begingroup$ 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.) $\endgroup$
    – Has QUIT--Anony-Mousse
    Jan 20, 2015 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.