Principe et performances

e-means est une méthode d’optimisation du problème de k‑means qui combine mini‑batchs et moyenne mobile exponentielle (EMA). Sur un large panel de jeux de données, la perte obtenue est inférieure à celle de l’algorithme de Lloyd dès 1,2 à 3 itérations, alors que Lloyd nécessite généralement 20 à 50 passes. En conditions réelles, le temps d’exécution est réduit de 10 × à 45 × sur GPU face à Flash‑KMeans, et de 8 × à 15 × sur CPU face à l’implémentation Faiss.

Mécanisme de mise à jour des centroïdes

Chaque cluster j possède une somme S_j et un compteur N_j. Au cours d’un mini‑batch de taille B, les contributions s_j et n_j sont intégrées selon la règle EMA : 

S_j ← (1‑α)·S_j + α·s_j
N_j ← (1‑α)·N_j + α·n_j
c_j = S_j / N_j
Le facteur α contrôle l’oubli des affectations anciennes. Lorsque B = n et α = 1, la règle redevient exactement celle de Lloyd, ce qui montre que Lloyd est un cas limite d’e‑means sans planification du taux d’apprentissage. L’utilisation d’EMA garantit que chaque centroïde reste dans l’enveloppe convexe des points récemment assignés, évitant les dépassements observés avec les mises à jour par descente de gradient.

Gestion des hyperparamètres et des clusters morts

e‑means ne requiert aucun réglage manuel. Deux lois d’échelle, dérivées des caractéristiques du problème (n, k, T), déterminent automatiquement la taille du batch B et le pas initial α₀. La « loi par défaut » maximise le débit, tandis que la « loi qualité » privilégie une perte plus basse au prix d’un temps de calcul légèrement supérieur. Cette automatisation a été validée sur 24 jeux de données différents, y compris des embeddings de grande dimension.

Le phénomène des « clusters morts » (centroïdes sans points assignés) est atténué par une stratégie de réanimation : un cluster actif est choisi proportionnellement à sa taille et divisé en deux, au lieu de le remplacer aléatoirement. Cette technique, inspirée de Faiss, maintient la capacité du codebook même pour des vocabulaires très larges.

Analyse scientifique des gains

Des expériences sur 200 graines aléatoires montrent que e‑means échappe plus souvent aux minima locaux que Lloyd, grâce au bruit introduit par les mini‑batchs. Le taux de convergence rapide (1,2‑3 itérations) découle de deux facteurs : (i) la mise à jour EMA qui suit les tendances récentes du paysage de perte, et (ii) le décay cosinusoïdal du taux d’apprentissage qui réduit progressivement l’amplitude des mises à jour sans impacter le temps d’exécution. Une phase de finalisation ajoute une passe supplémentaire à coût négligeable, abaissant davantage la perte finale. L’ensemble de ces mécanismes rend e‑means à la fois plus rapide et plus précis que les approches classiques, tout en restant simple à déployer grâce à des kernels parallélisés dédiés.