Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add Dynamic Time Warping (DTW) distance #310

Open
candalfigomoro opened this issue Oct 21, 2019 · 7 comments
Open

Add Dynamic Time Warping (DTW) distance #310

candalfigomoro opened this issue Oct 21, 2019 · 7 comments

Comments

@candalfigomoro
Copy link
Contributor

I think Dynamic Time Warping (DTW) distance would be a nice addition when we deal with time series.

While searching for UMAP + DTW on Google I found this implementation: https://gist.github.com/kylemcdonald/76b6f18fb4026e01196282b59bd31e7e

I didn't try it (I don't know if it correctly works), but I think it could be useful to add DTW to built-in distances in UMAP.

@lmcinnes
Copy link
Owner

I agree that DTW would be a useful metric to have. It is not trivial to implement; Kyle had a good solution that works around the issues with getting a pure numba implementation working. It is defintiely on my TODO list, but admittedly is currently not that high. If you feel like you could write a decent DTW routine that is numba compilable I would be very happy to accept a PR.

@candalfigomoro
Copy link
Contributor Author

candalfigomoro commented Oct 21, 2019

@lmcinnes Do you see any particular issue in kyle's implementation (apart from the comment about the dtw function naming)?

@candalfigomoro
Copy link
Contributor Author

An "issue" I can see is that DTW could be used with multiple distances (not just euclidean distance), so it's like DTW should be a sort of wrapper for other distances.

@lmcinnes
Copy link
Owner

I believe this is something you can work around with some numba fanciness. In particular it is possible for distance functions to take (optional) parameters. Since numba supports passing numba jitted functions as parameters you could, in principle, pass in the underlying distance function as an optional parameter.

An added bonus may be looking at using numba stencil operators for some of the cumulative distance computations.

@sleighsoft
Copy link
Collaborator

sleighsoft commented Oct 28, 2019

optimize_fn = numba.njit(

This is how you could dynamically wrap functions to be numba compatible.

@msseibel
Copy link

Here is a differentiable implementation of DTW soft-DTW.
It is implemented in numba.

@mblondel
Copy link

Our code implements a differentiable divergence between time series, based on soft-DTW, as described in this paper. Our divergence is defined as D(X, Y) := SDTW(X, Y) - 0.5 * SDTW(X, X) - 0.5 * SDTW(Y, Y). Let me know if you have any question with using the code.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants