Le clustering k-means est une méthode courante pour regrouper des données en k groupes. On l'utilise notamment pour structurer des collections de vecteurs, préparer des jeux de données et construire des dictionnaires de codes pour des modèles d'IA. Mais dès que les volumes montent à plusieurs millions de points, le coût des itérations devient vite un sujet concret : temps de calcul, capacité GPU et coût d'exploitation.
L'algorithme de Lloyd est robuste et facile à expliquer. Il n'est pas toujours le meilleur compromis, surtout quand le nombre de passages sur le jeu de données fait exploser le temps d'exécution. e-means, développé chez Meta FAIR, propose une autre façon de faire : des mises à jour par mini-lots, une moyenne mobile exponentielle (EMA) et des réglages basés sur des lois d'échelle. Les résultats rapportés annoncent une baisse du temps de calcul, et une perte souvent plus faible que Lloyd à nombre d'époques comparable. Voyons ce que change la méthode, comment elle fonctionne et quand elle vaut la peine d'être testée en production.
Que cherche à résoudre e-means ?
K-means consiste à répartir un ensemble de points en k groupes. Chaque point est affecté au centroïde le plus proche, et l'objectif est de minimiser la distance quadratique moyenne entre les points et leur centroïde. Concrètement, on répète deux étapes : affecter les points aux groupes, puis recalculer les centroïdes à partir des affectations.
Lloyd applique ces étapes sur tout le jeu de données. À chaque itération, il relit tous les points, recalcule les statistiques des groupes, puis met à jour les centroïdes. C'est une approche simple et très utile comme référence, mais chaque itération coûte un passage complet sur les données. Quand les volumes deviennent énormes, réduire le nombre de passages peut faire une vraie différence.
e-means vise précisément ce point : au lieu de recalculer sur l'ensemble, il utilise des mini-lots. L'idée n'est pas d'attendre la fin d'un passage complet pour mettre à jour les centroïdes. L'algorithme ajuste progressivement les statistiques de chaque cluster. L'objectif est d'obtenir une qualité de clustering correcte avec moins d'époques - ici, une époque correspond à un traitement du jeu de données dans le processus d'entraînement.
Les travaux rapportent des gains : à 25 époques, e-means obtient une perte de test inférieure à Lloyd en 1,2 à 3 époques, selon les configurations. Côté vitesse, les auteurs mesurent en temps réel une réduction de 10 à 45 fois sur GPU par rapport à Flash-KMeans, et de 8 à 15 fois sur CPU par rapport à Faiss.
À prendre avec prudence : ces chiffres ne veulent pas dire que tous les cas seront accélérés pareil. Tout dépend des données, du nombre de clusters, du matériel et surtout de l'implémentation. Mais le message reste clair : mettre à jour par mini-lots ne dégrade pas forcément la qualité, à condition que la méthode soit pensée et réglée pour ce régime.
Il y a aussi une question de contexte. e-means suppose un jeu de données fixe. Ce n'est pas la même chose que l'apprentissage d'un codebook dans un VQ-VAE, où la distribution des vecteurs évolue pendant l'entraînement. Les mécanismes peuvent être utiles dans ce genre de situation, mais les résultats discutés ici concernent le clustering d'un ensemble statique.
Pourquoi e-means peut-il être plus rapide et plus précis ?
Le gain de vitesse vient d'abord du nombre de passages nécessaires. Dans les expériences publiées, e-means atteint une perte de test inférieure à Lloyd en quelques époques, plutôt qu'en 25. Quand les mises à jour consomment moins de passes, le temps réel baisse souvent - à condition que l'implémentation évite d'autres goulots d'étranglement.
Autrement dit : l'architecture logicielle compte autant que l'idée algorithmique. Les noyaux GPU d'e-means fusionnent notamment l'affectation des points au centroïde le plus proche. Cette fusion réduit des opérations intermédiaires et aide à convertir des économies d'itérations en économies de temps. Sinon, on peut gagner moins que prévu, parce que transferts mémoire, lancements de noyaux ou lectures répétées mangent une partie de l'avantage.
Le bruit des mini-lots peut aider à éviter certaines impasses
Le fait d'obtenir une meilleure perte à convergence peut surprendre. Lloyd améliore la perte à chaque mise à jour : ça donne l'impression d'une trajectoire « propre » vers une bonne solution. Mais une baisse monotone ne garantit pas forcément que l'algorithme trouve une bonne configuration globale. K-means est sensible aux minima locaux et à l'initialisation. Même si l'objectif baisse à chaque étape, on peut rester coincé dans une solution médiocre.
Les mini-lots introduisent plus de bruit dans les mises à jour. Selon les auteurs, sur des jeux de données synthétiques, cette variabilité rend e-means moins susceptible de tomber dans certaines configurations pathologiques observées avec Lloyd. Le bruit ici sert d'exploration : il ne garantit pas qu'on s'en sort toujours, mais il peut réduire la fréquence des mauvais scénarios.
C'est un compromis qu'on retrouve souvent en optimisation : une trajectoire plus régulière exploite la solution courante, tandis qu'une trajectoire plus bruitée explore davantage (et peut aussi osciller si elle est mal réglée). e-means cherche justement à exploiter cette exploration, avec une décroissance progressive du taux de mise à jour.
La perte ne suffit pas pour évaluer un codebook
En production, regarder uniquement la perte moyenne ne suffit pas. Il faut aussi vérifier la distribution des tailles de clusters, le nombre de clusters inactifs et la stabilité par rapport aux initialisations. Ces points comptent particulièrement quand les centroïdes servent de dictionnaire de codes ou alimentent une étape en aval d'un système d'IA.
Un cluster inutilisé réduit la capacité effective du codebook. Même si la perte globale semble correcte, perdre une part significative des centroïdes peut dégrader la représentation réelle. La qualité doit donc se mesurer à la fois globalement et sur la répartition des affectations.
Comment sont réglés les paramètres et les clusters inactifs ?
Un objectif d'e-means est de ne pas laisser les praticiens gérer une longue liste d'hyperparamètres. La méthode estime automatiquement la taille des mini-lots et le pas initial à partir des caractéristiques du problème : nombre de points n, nombre de clusters k et budget d'entraînement T.
Les auteurs ajustent des lois d'échelle sur plusieurs configurations, puis testent la capacité à généraliser à d'autres jeux de données et à des tailles pas vues pendant l'ajustement. Les erreurs de regret médianes rapportées restent faibles sur les configurations testées. En pratique, ça veut dire : les règles proposées approchent les meilleurs réglages trouvés par recherche dans une grille, sans exiger cette recherche à chaque nouveau jeu de données.
Deux variantes de loi sont proposées pour la taille des mini-lots. La loi par défaut privilégie le débit ; la loi « qualité » consacre davantage de calcul pour viser un meilleur clustering. Le choix met en lumière un compromis souvent implicite dans les pipelines : si « se tromper » coûte cher en aval, ralentir un peu peut être rationnel. Si le pipeline tourne à grande échelle et que la qualité obtenue suffit déjà, la loi par défaut peut faire plus de sens.
La décroissance du pas d'apprentissage
Le pas α ne reste pas constant. Il décroît via un calendrier cosinus : on part de α₀ et on descend jusqu'à environ 0,1 α₀. L'idée est simple : au début, on veut des mises à jour plus franches, puis on réduit l'amplitude quand les centroïdes commencent à se stabiliser.
La logique ressemble à un taux d'apprentissage en entraînement, mais ici les paramètres répondent aux besoins du clustering. L'avantage annoncé : un réglage qui s'adapte au problème plutôt que de supposer qu'une valeur fixe conviendra à tous les volumes et à tous les k.
Réactiver les clusters plutôt que les laisser mourir
Avec des méthodes par mini-lots, certains centroïdes peuvent se retrouver sans affectation (ou presque). On appelle souvent ça des clusters morts. Un réflexe courant consiste à remplacer ces centroïdes par des points tirés au hasard dans le mini-lot courant.
e-means prend une autre voie : diviser un cluster actif plutôt que rééchantillonner au hasard. Concrètement, on sélectionne un cluster actif avec une probabilité proportionnelle à sa taille, puis on le scinde pour réactiver un centroïde.
Dans une ablation sur un million de vecteurs, avec 16 384 clusters et cinq époques, cette stratégie réduit le nombre de clusters morts par rapport au rééchantillonnage aléatoire ou à l'absence de réactivation. Sur DEEP, les auteurs rapportent 47 clusters morts avec la division proportionnelle, contre 2 343 avec le rééchantillonnage et 4 313 sans réactivation. Sur SIFT, les nombres sont 10, 750 et 2 080.
Ce point ramène à une idée plus générale : la stratégie de reprise compte autant que la détection. Remplacer un centroïde par un point « au hasard » peut le ramener dans une zone peu utile. Diviser un groupe trop grand peut au contraire redistribuer correctement de la capacité, même si ce n'est pas garanti de façon universelle. Mais au moins, la division suit une structure cohérente avec les affectations observées.
Dans quels cas e-means est-il pertinent en production ?
e-means vaut la peine d'être évalué quand vous avez un jeu de données statique et volumineux, que le coût des passages complets est élevé, et que votre implémentation peut exploiter le matériel disponible. Les cas d'usage typiques : regrouper des embeddings, réduire des collections de descripteurs, construire des codebooks pour des systèmes de représentation.
Ce n'est pas « juste » adopter un nouvel algorithme. Le but est de réduire le coût ou le délai d'une étape sans dégrader ce qui dépend du clustering. Pour une équipe produit, ça peut vouloir dire : réentraînements plus fréquents, infrastructure de calcul moins sollicitée, ou capacité à traiter des volumes qui étaient trop coûteux jusqu'ici. Mais il faut mesurer le bénéfice sur le pipeline complet : e-means ne compensera pas un système dominé par le stockage, les transferts ou une étape aval.
Une méthode à comparer sur votre propre charge
Les résultats publiés couvrent 24 jeux de données et configurations, avec des embeddings et des données synthétiques. Une autre campagne compare 234 configurations sur 16 jeux de données allant de 100 000 à 100 millions de points. Cette diversité aide, mais elle ne remplace pas un test sur vos distributions et vos contraintes.
La façon la plus fiable de décider : comparez e-means à votre référence actuelle avec un protocole stable (mêmes données, même k, même matériel, même budget de calcul, plusieurs graines). Mesurez au minimum la perte de test, le temps mur, la mémoire utilisée, le nombre de clusters inactifs et la variabilité entre exécutions. Une accélération obtenue au prix d'une instabilité opérationnelle peut coûter plus cher à maintenir que ce qu'elle fait gagner.
Et attention à un point souvent oublié : séparer les performances de l'algorithme de celles du code. Les gains GPU annoncés reposent sur des noyaux spécialisés. Si votre environnement n'a pas ces optimisations, les résultats peuvent être moins spectaculaires. Le bon comparatif, c'est entre implémentations adaptées à chaque méthode, pas entre une version optimisée et un code de référence qui ne l'est pas.
Quand rester sur Lloyd ?
Lloyd reste un choix raisonnable quand le jeu de données est modeste, que le budget de calcul est limité, ou quand vous avez besoin de simplicité et de reproductibilité plus que de vitesse. Il sert aussi de point de comparaison stable.
Le remplacer a du sens seulement si le gain mesuré améliore réellement le coût, le délai ou la qualité du produit.
À l'inverse, quand n et k deviennent importants et que l'affectation au centroïde le plus proche domine le temps de calcul, e-means peut devenir un bon levier. Vérifiez quand même deux choses : que vos données sont bien statiques, et que vos critères de qualité métier sont correctement représentés dans l'évaluation.
Conclusion
e-means reprend l'idée de k-means sans changer l'objectif : former des groupes autour de centroïdes. Ce qui bouge, c'est l'ensemble du système : mini-lots, moyenne mobile exponentielle, paramètres estimés automatiquement, réactivation des clusters inactifs et noyaux optimisés. Dans les expériences rapportées, cette combinaison réduit fortement le temps de calcul tout en atteignant une perte plus faible que Lloyd pour plusieurs configurations.
Si je devais résumer : ce n'est pas une promesse de gain universel, mais une piste sérieuse pour le clustering de grands jeux de données statiques. Testez avec vos données, votre matériel et plusieurs graines, puis comparez qualité, temps, mémoire et stabilité. C'est ce bilan « bout en bout » qui dira si l'innovation algorithmique devient, vraiment, un avantage opérationnel.
Comment e-means met-il à jour les centroïdes ?
Pour chaque cluster, on peut suivre deux quantités : la somme des points affectés et le nombre de points concernés. Le centroïde est ensuite le rapport entre ces deux valeurs. Les variantes de k-means diffèrent surtout sur la manière dont on met à jour ces sommes et ces comptes au fil du temps.
De Lloyd à la moyenne mobile exponentielle
Avec Lloyd, les statistiques sont recalculées à partir de zéro à chaque itération. Le résultat correspond à la moyenne exacte des points affectés pendant la passe. La précision a un coût : il faut traiter tout le jeu de données à chaque mise à jour.
MacQueen, lui, accumule les observations au fil du temps sans repartir de zéro. Un point peut donc continuer à contribuer au centroïde même si l'affectation a été calculée à partir d'une version plus ancienne de celui-ci. Cette mémoire « persistante » peut devenir un problème si les centroïdes bougent beaucoup.
e-means utilise une moyenne mobile exponentielle (EMA). À chaque mini-lot, la somme et le compte du cluster sont combinés avec les nouvelles observations. Les statistiques anciennes gardent un rôle, mais elles perdent progressivement du poids. Résultat : les centroïdes suivent mieux les affectations récentes, sans exiger un recalcul complet sur l'ensemble des données à chaque étape.
En version simplifiée : les statistiques précédentes sont pondérées par 1 − α, celles du mini-lot par α, puis on recalcule le centroïde à partir de la nouvelle somme et du nouveau compte. Le paramètre α détermine la priorité donnée aux observations récentes. Un α élevé rend les mises à jour plus réactives, mais peut les rendre moins stables ; un α plus faible amortit davantage, au risque d'avancer trop lentement.
Pourquoi préférer une EMA à une mise à jour par gradient ?
Des travaux antérieurs avaient montré que des mises à jour par mini-lots fondées sur une descente de gradient pouvaient dépasser Lloyd. Dans les expériences rapportées pour e-means, les auteurs observent toutefois une instabilité quand le taux d'apprentissage est trop agressif. L'EMA répond à une contrainte pratique : obtenir des mises à jour efficaces sans envoyer les centroïdes hors de contrôle.
L'intuition avancée est géométrique. Avec une mise à jour EMA, le centroïde reste dans l'enveloppe convexe des points associés. Une mise à jour par gradient peut au contraire le faire sortir de cette zone. Ce n'est pas, à lui seul, une garantie de meilleure qualité dans tous les cas, mais ça aide à expliquer pourquoi l'EMA ressort comme plus stable dans les résultats présentés.
Il existe aussi un lien avec Lloyd. Si le mini-lot contient tout le jeu de données et si α = 1, une mise à jour e-means se réduit à une mise à jour de Lloyd. Lloyd est donc un cas limite de cette famille de méthodes. En revanche, les réglages expérimentaux indiquent que ce cas limite n'est pas le meilleur compromis pour les configurations étudiées.