Using TimeSeriesKMeans with a faster DTW approach

[nils-fl]

Hi there,

I am working with TimeSeriesKMeans and DTW as distance metric. The DTW part is quite expensive. I stumbled across the great library "dtaidistance" and its C-implementation of DTW "distance_fast". Is there a way of using that version of distance calculation inside TimeSeriesKMeans to speed up the process?
I am failing to pass any distance measure as callable to the metric parameter in TimeSeriesKMeans.

Cheers
Nils

Edit:
This is the paper about the cpp approach https://arxiv.org/pdf/2307.04904.pdf

[fkiraly]

Some recommendations, these go in different directions:

• there are two implementations of k-means in sktime, the native one (TimeSeriesKMeans), and the one from tslearn, (TimeSeriesKMeansTslearn) - have you tried both, for runtime?
• neither of these is currently supporting custom distances. I would suggest, open a feature request issue requesting both, on sktime. And, open an issue requesting the feature on tslearn, for the class that sktime interfaces from there.
• Further, using dtaidistance for any distance-based estimator in sktime would optimally add this as a pairwise (distance) transformation, using the respective extension template. I would also recommend to open a feature request issue for this.

The opening of feature request issues is quite important, as those opened by other users typically get more attention than those by devs.

Regarding how to address:

• I remember @astrogilda has worked with dtaidistance in tsbootstrap before - he is closest to sktime develpoment who I know has experience with the package
• we are also happy to guide you adding any algorithms to sktime - the general guide is here: https://www.sktime.net/en/latest/developer_guide/add_estimators.html
  • dtw is either an aligner (if it produces alignment paths), or a pairwise time series distance transformer (if it produces only distance)
• both kmeans estimators should be easy to extend with custom distances
  • the knn algorithm should be a good template for this, it is likely that it is mostly copy-paste (with bits of refactor)

[astrogilda]

Happy to help with the PR if you go the dtaidistance route!

[fkiraly]

imo optimally all the parts are carried out to make this work:

• adding dtaidistance as an aligner or distance transformer
• extending at least one of the estimators to support custom distances

It probably works with the second only, but then users would have to write their own mini-adapter to callable in the right format.

[nils-fl]

Thank you @fkiraly and @astrogilda for your rapid answer!
The steps provided by you do sound very good - I will open feature requests on both sktime and tslearn for custom distances.
And I will have a more in depth look at dtaidistance used as a pairwise distance transformation, and the knn algo as a template for custom distances.
I am happy to help, but I actually never contributed to a package before ...

PS: I check both TimeSeriesKMeans and TimeSeriesKMeansTslearn (which in principal has the n_jobs parameter), but both are relatively slow for dtw.

[fkiraly]

I am happy to help, but I actually never contributed to a package before ...

At sktime we appreciate newcomers and have regular new contributor intro sessions!
The Friday meet-ups (on discord) are typically a good place for 5-10min of screensharing and troubleshooting, and there will be longer ones due to the start of the summer work period with lots of interns and contributors joining.

There's also a streamlined contributor guide, which is hopefully helpful:
https://www.sktime.net/en/latest/developer_guide.html

Let us know if you have any questions, and looking forward to see you on discord! (link is in the dev guide at the top, or in GitHub readme)