K-means sur des séries temporelles

J’ai récemment été amené à travailler sur un projet qui avait pour but d’étudier des données remontées par des capteurs. Il s’agissait d’un projet d’IoT et j’ai eu besoin de faire du clustering sur les valeurs remontées par les capteurs, qui sont en fait des séries temporelles. J’ai donc décidé d’appliquer un algorithme de clustering classique comme le k-means (algorithme des k-moyennes). Mais très vite la question de distance et d’aggrégation entre séries s’est posée. Quelle distance utilisée pour déterminer l’écart entre deux séries temporelles ?

Dans cet article, nous verrons quelles sont les possibilités en terme de distances entre séries temporelles. Et nous ferons un exemple d’application du k-means avec la bibliothèque Python tslearn.

Différents types de distances entre deux séries

La p-norme

Il s’agit de la plus simple des distances qu’on puisse imaginer. Étant données les séries temporelle \(S = \sum_i^n{s_i}\) et \(T = \sum_i^n{t_i}\), la distance définie par la p-norme est la suivante :
\[D(S, T) = (\sum_i^n{(s_i - t_i)^p})^{1/p} \]

Quand p=1 il s'agit d'une distance de Manhattan et quand p=2 il s'agit d'une distance euclidienne.

Le défaut de cette distance est qu'elle n'est pertinente que si les valeurs \(t_i\) et \(s_i\) sont alignées (synchronisées).

Dynamic Time Warping (DTW)

Il s'agit d'une distance qui prend en compte le décalage temporel entre les deux séries. Ainsi, plutôt que de comparer les \(s_i\) aux \(t_i\) (uniquement les mêmes indices), le DTW compare \(s_i\) à une suite de \(t_j\) où \(j \in ]i-w, i+w[\) \(w\) [1]. Les deux séries à comparer n'ont donc pas besoin d'être synchronisées ni même de la même taille.

On peut calculer le DTW grâce à la formule suivante récursive :

Soient deux séries \(S = s_1, s_2, ..., s_m\) et \(T = t_1, t_2, ..., t_n\).
Soit \(D(i,j)\) la distance entre les séries \(s_1, s_2, ..., s_i\) et \(t_1, t_2, ..., t_j\) avec \(1 \le i \le m\) et \(1 \le j \le n\) :
\(D(i, j) = \begin{cases} |s_1-t_1 |, si \ i=j=1; \\ |s_i-t_j| + \min{(D(i-1, j), D(i-1, j-1), D(i, j-1))}, sinon \\ \end{cases} \)
On a donc au final : \(DTW(S, T) = D(m, n)\)

Quelle distance choisir ?

Nous nous arrêterons à ces deux distances pour cet article. Cependant, il en existe beaucoup d'autres (on peut même en créer s'il y a un besoin particulier).

Il est évident que le DTW est bien plus robiste que la p-norme. Cependant, le DTW peut être beaucoup plus coûteuse en temps de calcul. En effet, la distance p-normée a une complexité en \( \mathcal{O}(n)\) tandis que le DTW est en \( \mathcal{O}(n*m)\) ce qui peut vite devenir gênant pour de très longues séries. Pour pallier ce problème, on peut utiliser une fenêtre pour le calcul du DTW. Il s'agit d'une constante \(\Delta\) qui correspond à la longueur de l'intervalle mentionné en [1]. Cela ramène la complexité à \(\mathcal{O}(\Delta*n)\).

K-means avec tslearn

Dans cette section, je vous propose un exemple de clustering de séries temporelles que l'on va réaliser grâce à la bibliothèque tslearn. Cette bibliothèque propose une collection de modèles de machine learning applicables aux séries temporelles. Il est basé sur Scikit-Learn, Scipy et Numpy.

Vous pouvez voir les détails de l'algorithme k-means dans cet article. Pour les séries temporelles, l'algorithme reste le même sauf qu'il faut adapter la distance. Pour notre exemple, nous utiliserons le DTW.

import numpy as np
import matplotlib.pyplot as plt

# On génère des séries temporelles
a = np.random.rand(100)
b = 2*a + 0.2
a = 2*a
c = np.random.rand(100)
d = 1.1*c + 1

plt.plot(np.arange(100),a, c='blue')
plt.plot(np.arange(100),b, c='green')
plt.plot(np.arange(100),c, c='red')
plt.plot(np.arange(100),d, c='orange')
Séries temporelle générées
Séries temporelles à clusteriser

On va vérifier qu'on retrouve bien les clusters générés (a et b => cluster 0 et c et d => cluster 1) en appliquant k-means à nos séries.

from tslearn.clustering import TimeSeriesKMeans

# On choisit la distance DTW et on fixe 'k' à 2
model = TimeSeriesKMeans(n_clusters=2, metric="dtw")
prediction = model.fit_predict([a, b, c, d])

print(prediction)
array([0, 0, 1, 1])

On retrouve bien nos clusters!

Évidemment, dans la vraie vie les clusters ne sont pas si facile à déterminer. Mais vous avez compris le principe... Dans la pratique, il est important de passer le temps nécessaire sur l'exploration de vos séries notamment grâce à des éléments visuels. La bibliothèque tslearn facilite énormément la vie lorsqu'on travaille avec des séries temporelles.

Conclusion

Dans cet article, nous nous sommes intéressés au clustering des séries temporelles. Nous avons par la même occasion découvert le package tslearn avec un exemple d'application du k-means pour les séries temporelles.

J'espère que cet article vous a plu. N'hésitez pas à laisser des commentaires :-).

La source Apprentissage non supervisé de séries temporelles à l'aide des k-means et d'une nouvelle méthode d'agrégation de séries Methods for variable-length time series
Laisser un commentaire

Votre adresse email ne sera pas publiée.

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Voulez-vous en savoir plus sur la Data Science ?

Inscrivez-vous alors à notre newsletter et vous receverez gratuitement nos derniers articles et actualités ! 
S'INSCRIRE MAINTENANT 
close-link