Sktime: [BUG] KNN with DTW

[manu-torres]

Describe the bug

KNeighborsClassifier(n_neighbors = 1, metric = "euclidean")) always gives exactly the same result than KNeighborsTimeSeriesClassifier(n_neighbors = 1, metric = "dtw")

To Reproduce

Go to the example jupyter notebook 02_classification_univariate, section "K-nearest-neighbours classifier for time series".

The last two code cells before the "Other clasiffiers" section show the difference between using regular euclidean distance and dynamic time warping for a K Neighbors Classifier. When executing those two cells both models always give the same score. The results only change when repeating the train test split, but both models still have the same score with the same samples.

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report
from sktime.datasets import load_basic_motions
from sklearn.pipeline import make_pipeline
from sktime.transformers.series_as_features.reduce import Tabularizer
X, y = load_basic_motions(return_X_y = True)
x_train, x_test, y_train, y_test = train_test_split(X.iloc[:, [0]], y)

#sklearn version
from sklearn.neighbors import KNeighborsClassifier

knn = make_pipeline(
        Tabularizer(),
        KNeighborsClassifier(n_neighbors = 1,
                             metric = "euclidean"))

knn.fit(x_train, y_train)
print("sklearn model performance (euclidean distance): " + str(knn.score(x_test, y_test)))
print(classification_report(y_test, knn.predict(x_test)))

#sktime adaptation (with the metric changed)
from sktime.classification.distance_based import KNeighborsTimeSeriesClassifier

knn = KNeighborsTimeSeriesClassifier(n_neighbors = 1,
                           metric = "dtw")

knn.fit(x_train, y_train)
print("sktime model performance (with dynamic time warping): " + str(knn.score(x_test, y_test)))
print(classification_report(y_test, knn.predict(x_test)))

Expected behavior

The sktime version with dwt should have better performance, or at least not exactly the same.

Additional context

I was following the tutorial at PyData Amsterdam 2020 and all the output from my local installation mirrored the one in the video. However, those two cells of code had a strange behaviour. In the video it seemed that the sklearn classifier had a score of 0.65 while the sktime implementation had a 1. Of course different results are to be expected when running the code since there is randomness involved, but it is still odd.

I thought I just made a mistake somewhere while copying the code, or maybe there was a problem with my installation (version 0.4.1), so I went to the notebook hosted on Binder and saw the same behaviour there.

Versions

Local installation version of sktime: 0.4.1

Also experienced the issue on the Binder notebook, with version 0.4.2

[mloning]

Thanks @manu-torres for raising the issue! I can confirm that the code gives the same results. @jasonlines or @ABostrom are you able to comment on this?

[Abelarm]

If you want I can try to solve this,
do you have already any clue about what could be the error?

[mloning]

I'm not sure where it comes from. But KNN currently doesn't pass our default estimator tests. I think it's worth looking at the tslearn's KNN version and this package https://github.com/wannesm/dtaidistance to perhaps re-implement parts of it or write an interface to tslearn.

[Abelarm]

Ok I was not able to find the error of the code so I did the other way around. I tried to set up a super fast working version

First I try the dtw distance you suggested me with the KNeighborsClassifier from sklearn:

from dtaidistance.dtw import distance_fast as dtw

knn_sk_dtw = make_pipeline(
    Tabularizer(),
    KNeighborsClassifier(n_neighbors=1,
                         metric=dtw))

knn_sk_dtw.fit(x_train, y_train)
print("sklearn model performance (with external dynamic time warping): " + str(knn_sk_dtw.score(x_test, y_test)))
print(classification_report(y_test, knn_sk_dtw.predict(x_test))) 

obtaining: sklearn model performance (with external dynamic time warping): 1.0
So we know it works.! :+1:

Then I used this distance inside the class KNeighborsTimeSeriesClassifier itself even tho I had to hack a little bit to make it work (doesn't support the inputs in the form [n_samples,1]):

if metric == "dtw":
    from dtaidistance.dtw import distance_fast as dtw

    def hacked_dtw(*args, **kwargs):
        new_args = [np.squeeze(args[0]), np.squeeze(args[1])]
        return dtw(*new_args, **kwargs)

    metric = hacked_dtw

obtaining: sktime model performance (with dynamic time warping): 1.0

Note: this is not a final solution but just an hack to see where the problem laid, and it seems it is inside the dtw calculation function.

now how do you think we should proceed?

[mloning]

@Abelarm thanks for looking into this! It would be great to get this fixed! Here are my thoughts but I'm happy for you to take the lead.

We have a few options:

1. replace our KNN with an interface to tslearn's KNN,
2. fix our KNN using distances from the dtaidistance package,
3. fix our KNN and distance functions.

3 seems to involve most work. The dtaidistance package seems to be well maintained but I'm not sure how compatible it is with scikit-learn. tslearn also has its own distance implementations. It may be worth to compare their functions against ours and see if they have all the distances that we have. What do you think?

[Abelarm]

1) the distance supported are {‘dtw’, ‘softdtw’, ‘euclidean’, ‘sqeuclidean’, ‘cityblock’, ‘sax’} plus the one from scipy doc

2) This seems the easiest way to do it, after reading better the documentation I found the function dtw_ndim which supports multivariate and time series in the form [n_samples, 1] (so no need to hack or nothing)
this bug can be solved by changing the line 33 from:

- from sktime.distances.elastic_cython import dtw_distance
+  from dtaidistance.dtw_ndim import distance_fast as dtw_distance

keeping the integration with sklearn as it is

3) That is the best one if you are sure about your c code, which I thinks is always hard.

Personally I would go with: 2 or 1 in order of preference.

Ps: are all the other distances tested?

[mloning]

As far as I'm aware the distances were tested against Java implementations in TSML but don't think we have unit tests for them.

I'm happy for you to work on 2, that would have been also my preferred option. If we can ensure compatibility with tslearn distances that would be even better. Are the tslean distances compatible with distances from dtaidistance (do they have the same function signature)?

It also seems like we have a number of additional distances (see sktime/distances/elastic.py), I'm not sure where they are used and would be hesitant to remove them without being certain that we don't break anything.

[Abelarm]

Ok let's start over:

the tslearn option cannot be pursued because it breaks too many test cases
So we need to go with the dtaidistance BUT:

dtaidistance has two classes for the case of univariate dtw and multivariate dtw_ndim.

Now the class KNeighborsTimeSeriesClassifier always pass the X,Y in the form of [n_samples, n] even in the case of n=1, so if we use dtw_ndimwith the shape [n_samples, 1] it behaves in the same way as the already implemented function.

The only way to have a correct result is to use the trick I showed previously, (that in the case of univariate time series, it removes the dimension 1)

if metric == "dtw":
    from dtaidistance.dtw import distance_fast as dtw

    def hacked_dtw(*args, **kwargs):
        new_args = [np.squeeze(args[0]), np.squeeze(args[1])]
        return dtw(*new_args, **kwargs)

    metric = hacked_dtw

but this is not a viable solution. The problem is way harder...

ps: you can also delete this

[mloning]

Which test cases does it break? We could exclude it from some of them. Or perhaps option 3 isn't too bad after all.

[Abelarm]

Most of the test where the dtw distance is involved...
173 failed, 1941 passed, 1654 warnings

[mloning]

I agree that this is a larger project to work on and requires some more in-depth investigation on how to best fix this. Let me know if you're still interested.

@jasonlines will add some unit tests for our distance function some time soon.

But refactoring our TimeSeriesKNN class still seems like a good idea if you want to work on this @Abelarm?

[Abelarm]

Yeah I can refactor it, but exactly what you had in mind?

[mloning]

The basic idea is to extend scikit-learn to be able to use our data input formats (nested pandas/3d numpy arrays) and distance functions but use as much code from scikit-learn as possible. Our current solution is a bit hacky and hence fragile. So we need to go through scikit-learn's KNN class and see where and how to best make changes to adapt it to our interface.

[TonyBagnall]

hi, I have rolled this into this issue just to tidy up a bit and make sure we address all related issues together,
https://github.com/alan-turing-institute/sktime/issues/596