Sktime: Implement ShapeDTW for TSC

[TonyBagnall]

Is your feature request related to a problem? Please describe.
A recently proposed distance based approach to TSC is called ShapeDTW

https://www.sciencedirect.com/science/article/pii/S0031320317303710

Describe the solution you'd like
ShapeDTW is basically a composition of a transformer and DTW. The transformer convert a univariate series into a multivariate one, and the form of DTW employed is DTW_D. This requires
1) implement transformer
2) implement multivariate dependent DTW
this should then slot into the existing structure, we can just wrap the published classifier as a pipeline
Additional context
Vincent Nicholson is doing this as part of his MSc project.

[vincent-nich12]

Yes I'm looking to deploy this algorithm as part of my MSC project

[mloning]

Welcome @Multivin12 and thanks for contributing to sktime!

A few tips for contributing:

• general contributing guideline/workflow
• you should probably inherit from BaseSeriesAsFeaturesTransformer, the RandomIntervalSegmenter may serve you as a template/starting point
• input and output data type should be a nested pandas data frame, for a quick intro check out our classification tutorial notebook
• the advanced installation instructions will also be useful for running tests, we use pytest, you can simply run pytest or make tests in the root dir, please also add some unit tests that check the methods
• please make sure you comply with a PEP8 style, you can pip install flake8 and run flake8 sktime/ in the root dir to see if everything works
• opening a draft PR early is probably a good idea, I'm happy to review the code

[vincent-nich12]

Hello so just a quick question, I saw that DTW does support multivariate classification but TimeSeriesNeighbours does not. So I was wondering would it be a good approach to add Shape DTW as a distance metric to TimeSeriesNeighbours?

[jasonlines]

hi @Multivin12. Sorry I haven't had a chance to dig into this too much as I'm snowed under with marking at the minute. If it doesn't create a lot of repeated work then perhaps ShapeDTW as a metric would be a good idea (i.e. if it doesn't have to transform anything multiple times, each time a series is used in a NN classification). If you do have to repeat some kind of transformation each time you use a series though then I expect it would make things very slow (for example, if you had to transform each training case every time you compare to a test series then this would be a lot of work!)

Alternatively, are you sure that the kNN in sktime doesn't support multivariate data? It's been a while since I implemented/tested any of that and my head is a bit fuzzy about what was actually implemented or not (I'm getting old!) but the comments suggest that it does support multivariate TSC. Eg in https://github.com/alan-turing-institute/sktime/blob/master/sktime/classification/distance_based/_time_series_neighbors.py line 237 lists the paramaters where it says:

X : sktime-format pandas dataframe with shape([n_cases,n_dimensions])

Given this explicitly states n_dimensions then it suggests that this is an option - it is very possible that this was included as a future feature however, and classification was restricted to univariate for now (I remember the data checks were a pain for even 1d series so I may have only got that far in the first push) but it might be worth double-checking if you can already use multivariate data for distance measures. After all, it would be a bit confusing why the measures can handle multivariate data if the classifier can't! (but again, I might just have a bad memory and may not have gotten that far). I'll be able to dig into the code more over the next week or two if need be though, but hopefully that's enough to go on for now

[vincent-nich12]

Hello @jasonlines and thanks for your response! I did try and put multivariate data into k-NN (once I updated my fork because it was out of date) but I did get this error message -

ValueError: X must be univariate with X.shape[1] == 1, but found: X.shape[1] == 2. For multivariate problems please consider compositor classes. Estimator-specific multivariate approaches are not implemented yet.

So I think what i'm going to do is implement ShapeDTW as a new metric for kNN as that will support univariate data (classifying multivariate TS is out the scope of my MSc project). And yes I wouldn't have to repeat transformations only issue is that ShapeDTW has a lot of parameters but I can probably pass them through like 'mpdist' does.

[mloning]

The value error is simply due to the input check, it may in fact work with multivariate data, I didn't try it out when I implemented the checks (note that KNN needs some refactoring, see #257, anyway). If you want to remove the input check and try it out with multivariate data and it works, feel free to open a PR. Happy to help if you have more questions!

[vincent-nich12]

Okay I will try that thank you!

[goastler]

@Multivin12 if you end up going down the transformer route to convert univariate to multivariate as @jasonlines mentioned you can cache the result in the transformer. Use the index of the panda dataframe row as a key and maintain a map (dict) of row# -> transformed instance.

I built a cached transformer once upon a time for Proximity Forest so you can try that / use it as a starting point for your shape DTW work: https://github.com/alan-turing-institute/sktime/blob/57944d5b03b31c7f0d5b8746b1df6642bbe42b6d/sktime/classification/distance_based/_proximity_forest.py#L49

Note that it would more elegant for the KNNs to accept multivariate data, but if this is a no go then this should do

[TonyBagnall]

hi vincent, I think in the first instance implement shapeDTW as a fixed composition of the shape transform and KNeighborsTimeSeriesClassifier, assuming it can be adapted to work with multivariate. This may be what you are suggesting already! Key thing is to avoid doing the transform in the distance function, as that is unnecessary

[vincent-nich12]

Oh okay thank you all for your help! @TonyBagnall so just so I understand would that mean writing ShapeDTW as its own class that comprises of the Shape transform and kNeighboursTimeSeriesClassifier? I was thinking that if I wrote shape_dtw as a metric then it would be doing the transform inside the distance function (or doing something hacky inside KNeighboursTimeSeriesClassifier but I want to avoid that). Not only that ShapeDTW has a lot of parameters so I was thinking it might be more logical to put it into a class. I guess the idea I had was that the class would transform the data then this transformed data will be fed into kNeighboursTimeSeriesClassifier (so the transformations would only ever be done once).

[mloning]

Closed by #287