Speed of Time Series Classification Algorithms

[muriloasouza]

Greetings,

I am working in a multiclass TSC problem (12 classes in total). My dataset contains around 4 millions of rows (4 millions of timeseries) and 48 columns (half-hourly measurements for a single day). Consider a train/test split of 0.7/0.3. And again, split that train part into train/validation with a 0.8/0.2 split.

How fast the TSC algorithms (Dictionary-based, Distance-based or Shapelet-based) would be to solve this problem? For example, currently i have developed a LSTM model from Keras library, that took around 1,5 hour to train/test.

Usually, are these TSC algorithms faster or slower than those traditional Deep Learning models we find in Keras or other DL libraries? If they are slower, any other TSC algorithm could be faster?

[fkiraly]

@muriloasouza, that's an interesting question!

We haven't done profiling or systematic experiments with datasets this large.
There is a profiling utility in sktime.utils.profiling for TSC, but experiments for this will likely take long (days, weeks to get the info for all algorithms). We also haven't systematically taking timings for smaller datasets.

I think this is an interesting development or research project, if you are interested in - just carrying out performance benchmarking for some of the more common algorithms.

Further, if you have your own models - would you consider contributing them to sktime? They are easy to add, and if they are part of a research project of yours, they might be interesting to others too.

[muriloasouza]

Hello @fkiraly, not really sure if this is the correct approach, but i tried this today:

from sktime.classification.distance_based import KNeighborsTimeSeriesClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
import time as time
import matplotlib.pyplot as plt

rede = 'kNN'

list_samples = []
list_time = []

for n_samples in range(10000, 61000, 1000):
    list_samples.append(n_samples)
    X, y = make_classification(n_samples=n_samples, n_features=48, n_informative=8, n_classes=12, random_state=42)
    
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
    
    clf = KNeighborsTimeSeriesClassifier(distance='euclidean')
    
    t_inicial = time.time()/60
    print(f'Tempo inicial {t_inicial}')
    clf.fit(X_train, y_train)
    tempo_final = time.time()/60
    print(f'Tempo final {tempo_final}')
    tempo_modelo = round(tempo_final - t_inicial, 4)
    print(f'Tempo {tempo_modelo} minutos com {n_samples} amostras com a {rede}')
    list_time.append(tempo_modelo)

plt.plot(list_samples, list_time)
plt.xlabel('Samples')
plt.ylabel('Time (minutes)')
plt.title(f'{rede} classifier')
plt.tight_layout()
plt.show()

Got this as result:

If this is the correct approach, maybe tomorrow i can try increasing the range in samples. Or another algorithm maybe.

One question regarding Deep Learning models, that we specify the number of epochs to train. Do you have any idea how this comparation can be done? How many epochs one should set when comparing to other algorithms that does not use epochs to train?

[fkiraly]

Interesting! Btw, have you seen the profiling utility? It does sth very similar to your code. Feedback would be apprecaiated.

The increase around 50.000 is probably when your computer or cluster runs out of memory, as you are using the memory-intensive strategy="brute". A memory issue has already been flagged in #5914, and is inherent to precomputation of the distance matrix. It would be particularly interesting to also check brute_incr and ball_tree.

Also, there are two other knn algorithms, from pyts and tslearn, I would be curious to see how they fare!

[fkiraly]

FYI @srggrs, this may be of interest to you.

[srggrs]

thx. At the moment I end up using the FB library FAISS, so far perform better and faster at searches and clustering using simple metrics (ie euclidean distance), though it does not have DTW and other complex distances

[fkiraly]

Interesting!

Can we somehow leverage FAISS?