Clustering des k-moyennes : le point de départ décide du résultat

L'algorithme des k-moyennes est le premier algorithme de clustering que l'on étudie, mais il possède une propriété que personne ne mentionne : son résultat dépend de son point de départ. Tournez la molette ci-dessous. Observez les mêmes points, divisés en autant de groupes, converger vers une solution différente.

Exemple résolu — Clustering des k-moyennes : le point de départ décide du résultat

Somme des carrés intra-cluster	1,0989
Itérations avant convergence	2
Écart entre les résultats	430,8%
Résultats différents	3 sur 24
Ce départ est donc	le meilleur trouvé

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Clustering des k-moyennes : le point de départ décide du résultat

Les k-moyennes cherchent k groupes en répétant deux étapes jusqu'à ce que plus rien ne bouge. Attribuez chaque point au centre le plus proche. Déplacez ensuite chaque centre vers la moyenne des points qu'il a captés. L'algorithme cherche à minimiser la somme des carrés intra-groupe, c'est-à-dire la distance totale au carré entre chaque point et son propre centre. Chacune de ces deux étapes ne peut que réduire cette valeur. Vous avez là la preuve complète que l'algorithme finit par s'arrêter.

Ce que signifie chaque symbole

k: le nombre de groupes que vous avez demandé, une information que rien dans les données ne vous indique
WCSS: la distance totale au carré entre chaque point et son propre centre

Suppose: Qu'un groupe forme un amas sphérique de taille à peu près égale à celle des autres, car la distance euclidienne au carré par rapport à une moyenne ne sait rien exprimer d'autre. Face à des groupes étirés, imbriqués ou très inégaux, les k-moyennes ne se trompent pas. Ce ne sont tout simplement pas les formes qu'elles cherchent.

Chacune de ces exécutions a convergé 🖖

Laissez les trois amas et k = 3 tels quels, puis parcourez les positions de départ de 1 à 24 à l'aide de la molette. Vingt-deux de ces départs se stabilisent à 1,0989. Les numéros 17 et 21 s'arrêtent à 5,8172 et 5,8331, un résultat 5,3 fois moins bon. Ils fusionnent deux des amas et coupent le troisième en deux. Rien ne s'est mal passé lors de ces deux exécutions. La convergence de l'algorithme de Lloyd est garantie : la somme des carrés intra-cluster diminue à chaque étape et ne peut pas diminuer indéfiniment. Il doit donc s'arrêter. Sur 1 536 exécutions couvrant tous les ensembles, tous les k et les deux initialisations, aucune n'a échoué. En revanche, rien ne garantit qu'il s'arrête sur une solution pertinente. L'affirmation « l'algorithme a convergé » relève donc de l'arithmétique plutôt que de vos données. Si vous n'avez exécuté les k-moyennes qu'une seule fois, vous n'avez aucun moyen de savoir laquelle de ces deux réponses vous avez entre les mains.

k-means++ réduit les dégâts de moitié sans rien promettre 🖖

Basculez Initialisation sur k-means++ et la dispersion sur cet ensemble est réduite à néant : les vingt-quatre départs trouvent 1,0989. C'est la solution vers laquelle tout le monde se tourne. Elle fonctionne en espaçant les centres initiaux au lieu de les placer au hasard. Mais l'amélioration est d'ordre statistique, non garantie, et il est utile de savoir dans quelle mesure. Sur 112 combinaisons d'ensembles de points, de tailles d'échantillons et de k, k-means++ a trouvé un optimum strictement meilleur qu'un départ aléatoire dans 38 d'entre elles. L'aléatoire a fait mieux dans 17 cas, et les deux ont fait jeu égal dans 57 cas. L'écart moyen sur vingt-quatre départs a chuté de 55,5 % à 31,7 %. L'erreur d'une exécution malchanceuse est donc approximativement divisée par deux. Cependant, dans un cas sur six, vous auriez obtenu de meilleurs résultats en lançant des fléchettes. Réglez l'anneau sur 90 points et k = 5 pour observer l'un de ces cas : l'aléatoire atteint 0,9884 et k-means++ s'arrête à 1,0213.

Une réponse stable, équilibrée et assurée à une question sans réponse 🖖

Chargez le dernier préréglage. Les points forment un réseau régulier sans l'ombre d'un cluster, et les k-moyennes les divisent en quatre groupes de 25 exactement. Observez maintenant ce que vos diagnostics indiquent à propos de ce résultat. Il a convergé, en onze itérations. Il est stable : les vingt-quatre positions de départ aboutissent à la même réponse, relancer l'algorithme ne vous avertit donc d'aucune anomalie. Les clusters sont parfaitement équilibrés, ce qui correspond généralement à l'aspect d'un bon clustering. Trois signaux distincts pointent dans la même direction, pourtant il n'y a rien à trouver. C'est l'aspect du clustering qui ne possède aucune solution technique. L'algorithme des k-moyennes répond à la question « où iraient k centres » et il a toujours une réponse à offrir, que la question « combien de groupes y a-t-il dans ces données » en possède une ou non.

Problème entièrement résolu

Vous ignorez le nombre de groupes présents dans vos données, vous prévoyez donc de le lire dans le coude de la courbe des scores. Tentez cette lecture sur les quatre nuages de points et comptez vos succès. Le panneau inférieur vous donne le meilleur score pour chaque k de 1 à 8, avec la baisse par rapport au k précédent tracée en arrière-plan.

Ouvrez ce problème dans l'outil
1. D'abord, pourquoi un coude plutôt qu'un minimum ? Réglez le nuage de points sur Trois amas et lisez la courbe : 10,3978 à k = 1, puis 5,6145, 1,0989, 0,9241, 0,8052, 0,6875, 0,6077, 0,5366. Elle ne remonte jamais. C'est impossible. Toute partition en k groupes peut en devenir une à k + 1 groupes si l'on divise l'un d'eux, et cette division ne peut que rapprocher les points de leur propre centre. Poussez k jusqu'au nombre de points et chaque point devient son propre groupe avec un score d'exactement 0.
  
  $WCSS (k) = \sum_{j = 1}^{k} \sum_{x \in C_{j}} ∥ x - μ_{j} ∥^{2}, WCSS (k + 1) \leq WCSS (k) three blobs : 10.3978, 5.6145, 1.0989, 0.9241, 0.8052, 0.6875, 0.6077, 0.5366$
2. La courbe n'offre donc aucun minimum à trouver. La lecture doit plutôt porter sur les baisses. Sur les amas, elles s'élèvent à 46,0 %, puis 80,4 %, puis 15,9 %, 12,9 %, 14,6 %, 11,6 %, 11,7 %. La chute après k = 3 est un cinquième de celle qui y mène, soit un effondrement d'un facteur 5,06. Or, les données ont été structurées exactement pour k = 3. La méthode fonctionne ici. C'est d'ailleurs le cas d'école que l'on montre à tout le monde.
  
  $drop (k) = 1 - \frac{WCSS ( k + 1 )}{WCSS ( k )}, elbow = ar g max_{k} \frac{drop ( k - 1 )}{drop ( k )} three blobs : 46 . 0%, 80 . 4%, 15 . 9%, 12 . 9%, 14 . 6%, 11 . 6%, 11 . 7% \Rightarrow k = 3, \times 5.06$
3. Passons à la Grille, qui ne contient aucun groupe. Ses baisses sont de 41,6 %, 34,1 %, 36,8 %, 16,4 %, 16,9 %, 12,8 %, 15,7 %. On observe un effondrement d'un facteur 2,25 après k = 4. C'est très exactement la forme que l'on vous a appris à repérer. La méthode du coude renvoie ainsi « quatre groupes » pour un ensemble qui n'en possède aucun.
  
  $lattice : 41 . 6%, 34 . 1%, 36 . 8%, 16 . 4%, 16 . 9%, 12 . 8%, 15 . 7% \Rightarrow k = 4, \times 2.25$
4. Vient ensuite l'Anneau, où existent véritablement deux groupes. Ses baisses s'enchaînent ainsi : 37,2 %, 32,8 %, 38,5 %, 33,4 %, 43,1 %, 25,3 %, 15,3 %. Il n'y a aucune tendance générale, puis deux chutes finales. L'effondrement le plus marqué se situe après k = 6. La lecture donne six. La réponse est deux.
  
  $ring : 37 . 2%, 32 . 8%, 38 . 5%, 33 . 4%, 43 . 1%, 25 . 3%, 15 . 3% \Rightarrow k = 6, \times 1.70$
5. Enfin Inégal, formé de trois groupes de tailles différentes : 43,8 %, 48,4 %, 35,4 %, 24,7 %, 16,1 %, 14,4 %, 21,8 %. C'est un déclin fluide sans aucun effondrement. La chute la plus forte représente un facteur 1,53, ce qui ne constitue pas une cassure. La lecture ne vous donne rien, sur des données qui abritent pourtant bien trois groupes.
  
  $uneven : 43 . 8%, 48 . 4%, 35 . 4%, 24 . 7%, 16 . 1%, 14 . 4%, 21 . 8% \Rightarrow k = 5, \times 1.53$
Réponse

Une réussite sur quatre : le résultat est correct sur les amas, quatre groupes sont inventés sur la grille, six sont proposés pour les deux de l'anneau, et c'est le silence sur l'ensemble inégal. Cette dynamique n'a rien d'aléatoire. Le coude est net précisément lorsque les groupes sont ronds, de taille similaire et bien séparés. Bref, lorsque vous auriez pu les compter à l'œil nu. Il s'efface sur chaque ensemble où vous aviez réellement besoin d'aide. C'est une chose à savoir avant d'utiliser cette courbe pour justifier un chiffre auprès de quelqu'un. C'est aussi pour cela que le coude se range à côté du score de silhouette, de la statistique d'écart et des critères d'information, et non au-dessus d'eux. Aucun de ces outils ne figure sur cette page. Chacun pose différemment la même question, celle à laquelle la courbe des scores ne peut répondre : non pas « où se placeraient k centres », qui trouve toujours une réponse, mais « y a-t-il seulement des groupes ici ».

$set three blobs lattice ring uneven elbow says 3465 truth 3023 sharpness \times 5.06 \times 2.25 \times 1.70 \times 1.53$

Parcours

Ajustement d'une droite aux données

Références (3)

The algorithm itself. Written in 1957 for quantising a signal into levels, circulated as a Bell Labs memorandum, and not published for twenty-five years: S. P. Lloyd, “Least squares quantization in PCM.” IEEE Transactions on Information Theory 28(2), 129–137, 1982.
The initialisation the second insight block measures — and the source of the bound that makes it worth using, which is a guarantee about the EXPECTED score rather than about any single run: D. Arthur and S. Vassilvitskii, “k-means++: The Advantages of Careful Seeding.” In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’07), 1027–1035. SIAM, 2007.
Where the elbow reading comes from, and it was proposed with more caution than it is usually repeated with: R. L. Thorndike, “Who belongs in the family?” Psychometrika 18(4), 267–276, 1953.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.