Pourquoi des départs différents donnent-ils des classes différentes ?

Lloyd fait décroître de façon monotone la fonction objectif, mais seulement jusqu’à un minimum local d’un problème non convexe. Des centroïdes initiaux différents tombent dans des « pièges » différents — d’où plusieurs redémarrages, ou une initialisation plus soignée (k-means++).

La partition globalement optimale est-elle garantie ?

Non : même dans le plan, l’optimisation globale exacte des k-moyennes est NP-difficile dans le pire cas. Les itérations de Lloyd sont une heuristique rapide, en général efficace sur des nuages « réguliers ».

Que faire si une classe se vide ?

En pratique, on réinitialise souvent le centroïde (par exemple au point le plus lointain). Ici, une classe vide garde l’ancien centroïde, pour ne pas perdre l’étiquette au milieu d’un pas ; à l’affectation suivante, la composition peut changer.

k-moyennes (algorithme de Lloyd)

Points du plan, nombre de classes k et centroïdes de départ. Un pas de Lloyd : affectation au centre le plus proche et déplacement du centroïde au barycentre. Démonstration : mélange de gaussiennes ; somme des carrés intra-classes.

À propos du modèle

Les k-moyennes (algorithme de Lloyd) partagent un ensemble fini de points en k groupes en minimisant la somme des carrés des distances euclidiennes aux centroïdes. Ici, l’algorithme classique de Lloyd : à k centres fixés, on alterne un pas d’affectation (chaque point → centroïde le plus proche, cellules de Voronoï) et un pas de mise à jour (centroïde ← moyenne de ses points). Sur un pas complet, la somme des carrés intra-classes ne croît pas : l’affectation est optimale à centres fixés, la moyenne est l’optimum à étiquettes fixées. Les centroïdes de départ sont k points de données distincts, choisis par permutation aléatoire à graine contrôlée ; la démonstration donne un mélange de gaussiennes. Une classe vide conserve l’ancien centroïde — choix pédagogique, sans la logique complète de k-means++.

Public : Analyse de données : apprentissage non supervisé, diagramme de Voronoï, minimisation alternée.

Notions clés

k-moyennes
algorithme de Lloyd
centroïde
cellule de Voronoï
somme des carrés intra-classes
mélange de gaussiennes
minimum local
classe vide

Comment ça marche

Algorithme de Lloyd : pas d’affectation — chaque point vers le plus proche des k centroïdes ; pas de mise à jour — centroïde au barycentre de ses points. Départ : k points de données au hasard ; démonstration : mélange de gaussiennes. La somme des carrés intra-classes ne croît pas sur un pas complet.

Questions fréquentes

Pourquoi des départs différents donnent-ils des classes différentes ?: Lloyd fait décroître de façon monotone la fonction objectif, mais seulement jusqu’à un minimum local d’un problème non convexe. Des centroïdes initiaux différents tombent dans des « pièges » différents — d’où plusieurs redémarrages, ou une initialisation plus soignée (k-means++).
La partition globalement optimale est-elle garantie ?: Non : même dans le plan, l’optimisation globale exacte des k-moyennes est NP-difficile dans le pire cas. Les itérations de Lloyd sont une heuristique rapide, en général efficace sur des nuages « réguliers ».
Que faire si une classe se vide ?: En pratique, on réinitialise souvent le centroïde (par exemple au point le plus lointain). Ici, une classe vide garde l’ancien centroïde, pour ne pas perdre l’étiquette au milieu d’un pas ; à l’affectation suivante, la composition peut changer.

Poursuivez avec des thèmes proches de cette catégorie — ou les 85 de «Visualisation mathématique».

Toute la catégorie →

NouveauCollège–lycée

Régression linéaire : MCO, ridge, lasso et R²

Lancer la simulation

Points du plan et modèle y = β₀ + β₁x : moindres carrés ordinaires (MCO), ridge (pénalité L₂ sur la pente) ou lasso (pénalité L₁). Le décalage Δy du point de plus grand |x| est une valeur aberrante à fort levier ; on compare SSE et R².

NouveauCollège–lycée

Enveloppe convexe (Graham et QuickHull)

Lancer la simulation

Points du plan : parcours de Graham avec animation pas à pas, ou QuickHull ; comparaison des ensembles de sommets.

NouveauCollège–lycée

DBSCAN : clustering par densité

Lancer la simulation

Rayon ε et seuil minPts : cœur, frontière et bruit. Classes de forme quelconque sans k imposé ; autour des points cœur, on peut afficher les cercles de rayon ε.

NouveauCollège–lycée

Triangulation de Delaunay et diagramme de Voronoï

Lancer la simulation

Triangulation de Bowyer–Watson et diagramme de Voronoï dual : un clic ajoute des sites, un glissement les déplace.

NouveauCollège–lycée

Méthode des moindres carrés

Lancer la simulation

Points bruités et droite y = ax + b qui minimise la somme des carrés des résidus verticaux. On fait varier la pente, l’ordonnée à l’origine et le bruit : résidus et somme des carrés des erreurs.

NouveauUniversité

Filtre adaptatif LMS / NLMS

Lancer la simulation

Voie primaire p = s + v, où v est un RIF inconnu du bruit blanc de référence x[n]. RIF adaptatif à L coefficients, LMS ou NLMS : l’erreur e = p − wᵀx tend vers le signal utile s.

k-moyennes (algorithme de Lloyd)

À propos du modèle

Comment ça marche

Questions fréquentes

Simulations voisines

Régression linéaire : MCO, ridge, lasso et R²

Enveloppe convexe (Graham et QuickHull)

DBSCAN : clustering par densité

Triangulation de Delaunay et diagramme de Voronoï

Méthode des moindres carrés

Filtre adaptatif LMS / NLMS

k-moyennes (algorithme de Lloyd)

À propos du modèle

Comment ça marche

Questions fréquentes