Plus précisément, on a discuté de la façon dont, lors de l'étape de réassignation des centroïdes dans le KMeans traditionnel, tous les points de données doivent être disponibles en mémoire pour calculer la moyenne.
Mais sur de grands datasets, garder tous les points en mémoire peut devenir problématique.
MiniBatchKMeans est une implémentation mini-batch de KMeans qui résout ce problème en conservant les informations suivantes pour chaque centroïde, tout au long des itérations sur les mini-batches :
Un "vecteur-somme" pour stocker la somme des vecteurs des points assignés au centroïde
Une variable "count" pour stocker le nombre de vecteurs de points assignés au centroïde.
Après avoir itéré sur tous les mini-batches, on effectue une division scalaire entre le vecteur-somme et le count pour obtenir le vecteur moyen :
Ce vecteur moyen nous donne précisément la nouvelle position du centroïde, comme si tous les points de données étaient présents en mémoire.
Cela résout les problèmes de bottleneck mémoire de KMeans.
En fait, l'approche mini-batch peut aussi offrir un gain de run-time, car si la vectorisation apporte en général des améliorations spectaculaires de performance quand les données sont volumineuses, ses bénéfices finissent par diminuer au-delà d'un certain seuil.
Le gain de performance lié à la vectorisation augmente d'abord, puis diminue progressivement avec la taille du dataset
Ainsi, en chargeant moins d'instances à la fois en mémoire, on peut obtenir un meilleur run-time d'entraînement.
Une autre limitation de KMeans
Cela dit, il existe une autre limitation majeure, commune à KMeans et MiniBatchKMeans, qu'on n'a pas abordée hier.
Pour rappel, KMeans s'entraîne ainsi :
Étape 1 : Initialiser les centroïdes
Étape 2 : Trouver le centroïde le plus proche pour chaque point
Étape 3 : Réassigner les centroïdes
Étape 4 : Répéter jusqu'à convergence
Mais dans cette implémentation, même l'étape 2 présente un bottleneck de run-time, car elle repose sur une recherche brute-force et exhaustive.
Autrement dit, elle calcule la distance de chaque point de données par rapport à chaque centroïde.
Résultat : cette étape n'est pas optimisée, et l'entraînement comme la prédiction prennent beaucoup de temps.
C'est particulièrement problématique sur de grands datasets.
Pour accélérer KMeans, l'une des implémentations que je préfère, notamment sur de grands datasets, c'est Faiss, développé par Facebook AI Research.
Concrètement, Faiss propose une recherche du plus proche voisin bien plus rapide grâce à des algorithmes de recherche approchée du plus proche voisin (approximate nearest-neighbor search).
Il utilise un "Inverted Index", une structure de données optimisée pour stocker et indexer les points de données.
Cela rend le clustering extrêmement efficace, en particulier sur de grands datasets, comme le montre l'image ci-dessous :
Comme on peut le voir, sur un dataset de 500k points (1024 dimensions), Faiss est environ 20x plus rapide que le KMeans de Sklearn. Un gain de vitesse impressionnant.
De plus, Faiss peut aussi tourner sur GPU, ce qui peut encore améliorer les performances de run-time de ton clustering.
👉 Pour démarrer avec Faiss : GitHub
👉 À toi : quelles autres limitations connais-tu dans l'algorithme KMeans ?
Envie d'aller plus loin ? DataXp t'attend : formations et parcours pour progresser en data science, machine learning et IA.
