2
$\begingroup$

I am trying to do K-means clustering on my data which has time series length of 3700 and for (latitude,longitude) points of around 6000 in length. However, timeseries clustering using tslearn package even with joblib capabilities is painstaking slow. I m trying to cluster using dynamic time wrapping method. Can anyone suggest better method to cluster my data. I have tried all the packages in python without any leads. Please let me know if any implementation of time-series clustering available with dtw metric which works in parallel.

$\endgroup$

2 Answers 2

3
$\begingroup$

A good answer has already been given, but here's an alternative method. It is a very simple summary of a paper by Rob Hyndman

  1. Let each time series be $X_i = (X_{i,1}, X_{i,2}, \ldots )$. They do not need to be of equal length or be sampled at the same time points.
  2. Obtain summary statistics of each $X_i$; $\theta_i$ for each time series. Relatively simple models like bin smoothers, splines or low order polynomials might be effective. You could also experiment with moments of $X_i$. You will need to fit the same type of model/calculate same summaries for each time series for this method to work. The linked paper gives many more details.
  3. Perform clustering on $\theta_i$ using e.g. $k$-means.

In my experience, I have founds this to be much faster than DTW. In a recent example, I clustered ~10s of thousands time series in ~15 minutes using a method based on this approach. The 15 minutes included model selection (number of bins in a bin smoother) as well as simultaneously choosing $k$ for $k$-means. Timing will depend on your machine and chosen language, but DTW could have taken a week or so for my example.

$\endgroup$
2
  • $\begingroup$ Dear @jcken, First of all, thank you for your response. Coming from a climate research background I am poor at programming things from scratch. If you can point me to a repository (preferably python) through which I can implement this, It would be a great help. I am working on finding time series clusters for rainfall and identifying major clusters on which I have to further carry out my analysis. Thank you. $\endgroup$ Dec 5, 2022 at 10:28
  • $\begingroup$ Unfortunately, I'm not a python programmer. I would however imagine that scikit-learn has all, or at least most, of the functionality you need for modelling and clustering. Programming is a bit off-topic on CV, I'd take your questions about the programmatic implementation of your methods to stack overflow $\endgroup$
    – jcken
    Dec 5, 2022 at 10:38
1
$\begingroup$
  1. Instead of DTW, use cDTW, with a constraint of about 5%. That will give a ~20 times speed up

  2. If the data is oversampled (as most data is) you can downsample it before using DTW. Since the time is quadratic in length, if you downsample by say 1 in 3, that would be about nine times faster.

  3. You can combine ideas '1' and '2' to get about 200 times faster...

PS, DTW is not a metric, it is a measure

https://www.cs.unm.edu/~mueen/DTW.pdf

$\endgroup$
1
  • $\begingroup$ Dear @Eamonn, I followed your work and humbled by your response. Thanks much for your quick reply and help. 1. I will definitely try that (github.com/halachkin/cdtw): Please confirm that this link is the same cDTW that you are speaking about. I am a climate researcher with elementary programming skills. 2. I am trying to cluster my rainfall time series (1 day time resolution) undersampling meaning may be I can take monthly averages and then use cDTW? I appreciate your help. this greatly helps my research work. PS: Tq for the powerpoint presentation $\endgroup$ Dec 5, 2022 at 10:15

Your Answer

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

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