Nous avons vu dans cet article pourquoi partitionner un jeu de données temporelles. Ici nous allons voir un exemple d’implémentation de partitionnement, tel que nous l’avons mis en place sur nos données lors de tests.

Partitionnement par k-moyennes

Le partitionnement par k-moyennes, ou k-means clustering en anglais, est un algorithme de partitionnement assez répandu. Il a le gros avantage d’être rapide à calculer si tant est qu’on puisse se satisfaire d’un résultat approché. En effet, il fonctionne de manière incrémentale. Donc plus on réalise d’itérations sur les données, plus on obtient un résultat proche du résultat optimal.

Principe

Le partitionnement par k-moyennes prend en paramètre un nombre de clusters fixe, défini à l’avance. L’objectif du processus est de calculer un point appelé « centroïde » par cluster. Ce centroïde représente un vecteur moyen pour l’ensemble des données du cluster. À son initialisation, l’algorithme génère un centroïde par cluster de manière aléatoire. Puis à chaque itération, il met à jour les centroïdes de la manière suivante. Pour l’ensemble des données, l’algorithme calcule une distance entre chaque point de donnée et chaque centroïde. Chaque point de donnée est associé au centroïde le plus proche par rapport à cette distance. Enfin, chaque centroïde devient le point moyen parmi tous les points dans le cluster associé.

Il existe plusieurs fonctions de distance pouvant être utilisée dans l’algorithme. La distance euclidienne est un exemple classique de fonction de distance. Elle a l’avantage de pouvoir être facilement visualisée en deux ou trois dimensions.

MiniBatch K-Means: une variante adaptée pour les gros volumes

Il existe plusieurs variantes de l’algorithme de k-moyennes avec différents objectifs. Par exemple, une méthode appelée k-médianes utilise des points médians plutôt que des points moyens comme centroïdes de cluster. Cela permet potentiellement d’obtenir un partitionnement un peu plus optimal. Cependant, cela rend également l’algorithme plus complexe et donc plus long à exécuter.

Dans l’objectif de pouvoir faire tourner l’algorithme de partitionnement sur de très grands volumes de données, nous nous sommes plutôt intéressés à une variante de k-moyennes conçue pour être extrêmement rapide au détriment d’un petit peu d’optimalité. Cette variante s’appelle « Mini-batch k-means » en anglais, ou littéralement « k-moyennes par mini-lot ». Elle consiste à exécuter l’algorithme des k-moyennes sur des sous-ensembles du jeu de données. En pratique, avec un petit nombre de clusters à déterminer l’écart de qualité entre k-moyenne et sa variante par lot est de l’ordre de 2%. Tout en réduisant le temps de calcul de manière significative.

Sur quelles données calculer la distance ?

Un problème auquel nous nous sommes heurtés au moment de partitionner notre ensemble de données était de choisir sur quelles variables exécuter l’algorithme de partitionnement. En effet, nous travaillons sur des données sous la forme de séries temporelles. Bien qu’il soit possible de calculer la distance entre deux séries temporelles sur une même période (point par point), cela donne un résultat très influencé par l’amplitude des courbes. Or nos séries de données possèdent des amplitudes (volume d’impressions, de clics, de conversions…) très hétérogènes. Nous souhaitions baser le partitionnement davantage sur la « forme » des courbes des séries temporelles.

En réfléchissant à la manière de procéder, nous avons finalement développé de manière empirique une fonction calculant un score de « régularité » pour chaque série. Associé au volume quotidien moyen, cela nous a permis d’obtenir un couple de valeur définissant chaque série temporelle. Nous avons ensuite exécuté l’algorithme de partitionnement sur ces couples de valeurs. Partitionner avec des valeurs agrégées plutôt que l’ensemble des points des séries de données permet des temps de calcul plus courts, et potentiellement d’utiliser des séries n’ayant pas un axe temporel commun. Mais surtout, utiliser des couples de valeurs nous a permis de visualiser ces points en deux dimensions et ainsi aidés à prendre des décisions.

Mise en pratique avec Python

Nous travaillons en python pour développer notre outil de détection d’anomalies utilisant le Deep Learning. En python, il existe de nombreuses bibliothèques de machine learning et d’analyse de données très bien fournies. L’une d’entre elles, scikit-learn, implémente de nombreux algorithmes de partitionnement et est très bien documentée. Nous avons utilisé le module « MiniBatchKMeans » de scikit-learn, dont la documentation présente un exemple de résultat de partitionnement de données par k-moyennes et sa variante:

https://scikit-learn.org/stable/_images/sphx_glr_plot_mini_batch_kmeans_0011.png

On peut voir que sur un exemple avec un grand nombre de points de données, la variante « par mini-lot » de l’algorithme de partitionnement par k-moyennes s’exécute plus rapidement. 30 millisecondes environ contre 50 pour k-moyennes. Cependant, la différence de résultat entre les deux algorithmes, mise en valeur à droite, est faible. Seuls quelques points se retrouvent dans un cluster différent en fonction de la variante utilisée.

septembre 1, 2020 8:00
Partagez sur :

Besoin d’être conseillé ?

Nous sommes là pour vous répondre. N’hésitez pas à nous donner votre numéro de téléphone pour que nous puissions vous rappeler dans les plus brefs délais.