De nombreux algorithmes ML de Sklearn supportent l'apprentissage incrémental, c'est-à-dire un entraînement par mini-batches.
Ça les rend très utiles quand toutes les données ne tiennent pas en mémoire.
Voici les algorithmes concernés, pour référence :
Si tu regardes bien, KMeans figure dans cette liste.
C'est un algorithme de clustering populaire, et c'est une bonne chose de pouvoir l'utiliser sur de grands datasets si besoin.
Mais quand j'ai découvert que KMeans pouvait être implémenté en mini-batch, je me suis demandé comment ça pouvait concrètement fonctionner.
En y réfléchissant quelques instants, j'ai eu une idée que je veux partager avec toi aujourd'hui.
C'est parti !
Le vrai problème du KMeans classique
Avant de comprendre l'implémentation en mini-batch, il faut identifier le problème du KMeans habituel.
Pour rappel, KMeans fonctionne comme suit :
Étape 1) Initialiser les centroïdes.
Étape 2) Trouver le centroïde le plus proche pour chaque point.
Étape 3) Recalculer chaque centroïde comme la moyenne des points qui lui sont assignés.
Étape 4) Répéter jusqu'à convergence.
Dans cette implémentation, le principal goulot d'étranglement mémoire vient de l'étape 3.
C'est là qu'on calcule la moyenne de tous les points assignés à un centroïde pour le déplacer.
Classiquement, tous les points assignés à un centroïde doivent donc être disponibles en mémoire pour calculer cette moyenne.
Mais dans notre cas, tous les points ne tiennent pas en mémoire en même temps. L'averaging direct n'est donc pas faisable.
Voici pourtant comment on peut résoudre ça intelligemment.
Note : je n'ai pas vérifié l'implémentation exacte de MiniBatchKMeans dans Sklearn. La doc n'en dit pas grand-chose non plus.
Ce que je vais te présenter, c'est la solution à laquelle je suis arrivé en réfléchissant au problème.
Si elle recoupe parfaitement ce que fait Sklearn, tant mieux !
Sinon, pas de problème, car cette solution est parfaitement viable.
MiniBatchKMeans
On commence par choisir k, le nombre de centroïdes.
Ensuite, il faut leur donner une position initiale : on tire m points aléatoires (avec m << n) pour initialiser les centroïdes.
Rappelle-toi maintenant le problème identifié : tous les points doivent être en mémoire pour calculer la moyenne.
Pour y remédier, il faut un moyen de garder une trace des points assignés à chaque centroïde au fur et à mesure qu'on charge et traite chaque mini-batch.
On ne peut pas maintenir une liste grandissante de points assignés à chaque centroïde : ça finirait par occuper autant de mémoire que le dataset entier.
Voici comment remplir cet objectif intelligemment.
On exploite la propriété mathématique suivante qui relie somme et moyenne :
Comment ?
Dans un KMeans classique, on moyenne tous les points assignés à un centroïde pour déterminer sa nouvelle position.
Mais comme on ne peut pas garder tous ces points en mémoire, voilà ce qu'on fait dans le cadre du KMeans en mini-batch.
Pour chaque centroïde :
On maintient un vecteur-somme, qui accumule la somme des vecteurs de tous les points qui lui ont été assignés jusqu'ici. Au départ, c'est un vecteur nul.
Une variable count, qui compte le nombre de points assignés à ce centroïde. Au départ, count vaut zéro.
À chaque itération sur les mini-batches :
Le vecteur-somme de chaque centroïde continue d'accumuler la somme des points qui lui sont assignés.
Le count de chaque centroïde continue de comptabiliser le nombre de ces points.
Une fois tous les mini-batches parcourus, on effectue une division scalaire entre le vecteur-somme et le count pour obtenir le vecteur moyen :
Cette moyenne nous donne précisément la nouvelle position du centroïde, comme si tous les points avaient été disponibles en mémoire.
On répète jusqu'à convergence.
Et avant de démarrer l'itération suivante du MiniBatchKMeans, on réinitialise le vecteur-somme à zéro et le count à zéro.
C'est tout ce qu'il faut pour implémenter une version mini-batch de KMeans.
Simple, non ?
Il est assez évident que les étapes décrites ci-dessus impliquent essentiellement des calculs matriciels et vectoriels, qui peuvent être chargés rapidement sur un GPU pour accélérer l'exécution.
On peut donc facilement implémenter une version tensor de KMeans.
Ce qui l'est moins, c'est comment convertir, par exemple, un arbre de décision ou une random forest en calculs tensoriels pour les faire tourner sur GPU.
Si tu veux en savoir plus, on en a parlé ici :
Par ailleurs, même si on a parlé de KMeans dans ce deep dive, cet algorithme a de nombreuses limites qui le rendent inadapté dans beaucoup de situations.
Connaître d'autres algorithmes de clustering et savoir quand les utiliser est donc essentiel.
On a couvert deux grandes familles d'algorithmes de clustering, les approches density-based et distribution-based, dans ces deep dives :
👉 Quels autres algorithmes ML classiques pourraient, selon toi, être implémentés en mini-batch mais ne le sont pas encore dans Sklearn ?
Envie d'aller plus loin ? DataXp t'attend : formations et parcours pour progresser en data science, machine learning et IA.
