Le partitionnement : les k moyennes

La coopérative de Vérelles, qui collecte le blé de ses adhérents, veut adapter son conseil, l'azote surtout, à des groupes de parcelles au profil voisin. Personne ne sait combien il y en a, ni lesquels : aucune colonne du tableau ne les donne. Jusqu'ici, chaque exemple s'accompagnait de la réponse attendue ; le premier chapitre a nommé le cas où elle n'existe pas, l'apprentissage non supervisé. Le partitionnement groupe des données sans étiquettes, et l'algorithme des k moyennes en est le représentant le plus employé. Une difficulté nouvelle apparaît : il n'y a plus de bonne réponse à laquelle se comparer, donc plus de mesure d'erreur au sens des chapitres précédents. Combien de groupes la coopérative doit-elle retenir, et comment savoir s'ils veulent dire quelque chose ? Ce chapitre présente l'algorithme, ses trois façons d'échouer, et la question qu'il ne sait pas trancher tout seul.

La question change de nature

Partitionnement

Étant donné un ensemble d'individus décrits par des attributs, un partitionnement les répartit en groupes tels que les individus d'un même groupe se ressemblent davantage entre eux qu'avec ceux des autres groupes.

Aucune étiquette n'est fournie, et aucune n'est produite : les groupes sont numérotés, pas nommés.

Il n'y a pas de bonne réponse

En apprentissage supervisé, on compare une prédiction à une vérité connue. Ici, il n'y a rien à comparer.
Deux partitionnements différents du même jeu peuvent être également défendables, et le seul juge est le sens métier des groupes obtenus. Un algorithme qui sépare les parcelles par sol et un autre qui les sépare par conduite, intensive ou économe en azote, ont tous deux raison, et la question de savoir lequel sert est extérieure aux données.
C'est pourquoi les mesures présentées plus bas ne mesurent pas la justesse d'un partitionnement, seulement sa cohérence géométrique. Elles peuvent parfaitement récompenser un découpage sans aucun intérêt.

L'algorithme des k moyennes

La boucle, en deux gestes

Choisir $k$ positions de départ, appelées centres.

Puis répéter :

Affectation : chaque point rejoint le centre le plus proche.
Déplacement : chaque centre se place au barycentre des points qu'il vient de recevoir.

S'arrêter quand plus aucune affectation ne change.

Deux gestes, et il faut les voir séparément. On les décrit ensemble et l'on ne comprend alors ni l'un ni l'autre.
Pendant l'affectation, les centres ne bougent pas : ce sont les points qui changent de couleur. Pendant le déplacement, les couleurs ne changent pas : ce sont les croix qui glissent.
La figure ci-dessous les sépare. Avancer d'un cran à la fois est le seul moyen de voir que la convergence n'est pas un mystère : chacun des deux gestes fait baisser la même quantité, et une quantité qui baisse toujours et reste positive finit par s'arrêter.

étape 4 / 4inertie 6

Affectation : chaque point rejoint le centre le plus proche. Les centres n'ont pas bougé.

Douze points, trois centres posés un peu au hasard. Avancer d'une étape à la fois montre l'alternance : les croix glissent, puis les points changent de couleur, et l'inertie tombe de 323 à 6. La dernière étape ne change plus rien : c'est ainsi que l'algorithme sait qu'il a fini. Inertie finale 6, en 4 demi-étapes, après convergence.

L'inertie

Inertie

L'inertie d'un partitionnement est la somme des carrés des distances de chaque point au centre de son groupe.

I = \sum_{i} \lVert x_i - c_{g(i)} \rVert^2

Pourquoi elle ne peut jamais remonter. Chacun des deux gestes la fait baisser, ou la laisse égale, et pour deux raisons différentes.
L'affectation déplace chaque point vers le centre le plus proche. Sa contribution à la somme ne peut donc que diminuer, puisqu'on remplace une distance par une distance plus petite ou égale.
Le déplacement place chaque centre au barycentre de son groupe. Or le barycentre est, par construction, le point qui minimise la somme des carrés des distances aux points du groupe. La contribution de chaque groupe ne peut donc que diminuer.
L'inertie décroît, elle est positive, et il n'existe qu'un nombre fini de partages possibles : l'algorithme termine. C'est une démonstration complète, et elle tient en trois phrases.

Terminer n'est pas trouver le meilleur partage

L'inertie décroît jusqu'à un minimum local. Rien ne garantit que ce soit le plus petit possible, et la section suivante montre un cas où l'écart est d'un facteur six.
Trouver le partage d'inertie minimale est d'ailleurs un problème NP-difficile. On ne cherche donc pas l'optimum : on relance l'algorithme plusieurs fois depuis des départs différents et l'on garde le meilleur résultat obtenu.

Vérification rapideon peut se reprendre

1.La coopérative sait, pour chaque parcelle passée, si la rouille l'a touchée, et veut prévoir cette mention pour l'an prochain. De quoi s'agit-il ?

2.Pendant l'étape d'affectation des k moyennes…

3.L'inertie d'un partitionnement peut-elle remonter d'une étape à la suivante ?

Premier échec : l'initialisation

Voici exactement les mêmes douze points, avec trois centres posés ailleurs.

étape 2 / 2inertie 37

Affectation : chaque point rejoint le centre le plus proche. Les centres n'ont pas bougé.

Les mêmes points, avec deux centres posés dans le groupe de droite et un seul pour les deux autres. L'algorithme converge, et il converge sur un partage bien pire : le groupe isolé est coupé en deux, les deux groupes voisins sont fusionnés, et rien ne l'en fera sortir. Inertie finale 37, en 2 demi-étapes, après convergence.

À manipuler

Dans la première figure, faire avancer le curseur d'une position à la fois et noter l'inertie affichée : elle part de 323 et tombe à 6, sans jamais remonter. Faire de même dans la seconde, puis comparer les deux arrivées : 37 contre 6, sur les mêmes douze points. Constater que l'inertie a baissé à chaque position dans les deux cas : la descente est garantie, le point d'arrivée ne l'est pas.

Le prix d'un mauvais départ

Bon départ : trois groupes de quatre points, inertie finale 6,00.

Mauvais départ : des groupes de 2, 2 et 8 points, inertie finale 37,00.

Six fois pire, sur les mêmes données et avec le même algorithme. Et l'algorithme n'a rien fait de mal : il a bien fait décroître l'inertie jusqu'à ce qu'aucun geste ne l'améliore plus. Il est simplement arrivé dans un creux dont il ne peut pas sortir, parce que ni l'affectation ni le déplacement ne savent remonter.

Les deux parades, et elles se combinent.

Relancer plusieurs fois. Dix départs tirés au hasard, on garde celui d'inertie minimale. C'est bon marché et cela suffit dans la plupart des cas. Toute implémentation sérieuse le fait par défaut.
Mieux choisir le départ. La méthode dite k-means++ tire le premier centre au hasard, puis chaque centre suivant avec une probabilité proportionnelle au carré de sa distance au centre le plus proche déjà choisi. Les centres se répartissent donc d'emblée, et la probabilité de poser deux centres dans le même amas s'effondre.
Les deux ensemble sont le réglage par défaut des bibliothèques, et il ne faut pas le désactiver sans raison.

Vérification rapideon peut se reprendre

Deux exécutions donnent des inerties de 6 et de 37 sur les mêmes données. Pourquoi ?

Deuxième échec : l'échelle

main.py

Sortie

>_ Prêt à exécuter…

Sans mise à l'échelle, le partitionnement mesure la mauvaise chose

Cinquante-cinq pour cent, c'est le niveau du hasard : l'algorithme n'a rien trouvé. Après standardisation, il retrouve la structure en entier.
La raison tient en une ligne de calcul. Dans une distance euclidienne, deux parcelles dont les distances au silo diffèrent de 10 000 m et les rendements de 11 q/ha sont séparées de

\sqrt{10000^2 + 11^2}

, soit 10 000,006 : le second terme ne compte littéralement pour rien. La variable la plus étalée décide seule du partage, quel que soit son intérêt.
Cette distance est celle du chapitre de géométrie, à ceci près qu'elle s'y applique à des longueurs comparables. Employée sur des attributs qui n'ont ni la même unité ni le même ordre de grandeur, elle cesse de mesurer ce qu'on croit.
La mise à l'échelle n'est donc pas une commodité de présentation : c'est une condition pour que l'algorithme mesure ce qu'on croit lui demander. Elle vaut pour tout ce qui calcule une distance.

Vérification rapideon peut se reprendre

Sans mise à l'échelle, sur quoi porte réellement le partage ?

Troisième échec : la forme des groupes

Ce que la méthode suppose sans le dire. Affecter chaque point au centre le plus proche revient à découper le plan en régions délimitées par des droites, chacune à mi-chemin entre deux centres.
Les groupes trouvés sont donc nécessairement convexes et de taille comparable. C'est une hypothèse, et elle n'est pas toujours vraie.
Deux anneaux concentriques la mettent en défaut de la façon la plus nette : aucun découpage par des droites ne peut séparer un anneau intérieur d'un anneau extérieur. L'algorithme coupera le plan en deux moitiés, et se trompera sur la moitié des points.

main.py

Sortie

>_ Prêt à exécuter…

Choisir le nombre de groupes

C'est la seule décision que l'algorithme ne prend pas, et il n'existe pas de réponse automatique. Deux indicateurs aident, et aucun ne tranche.

Le coude

Tracer l'inertie en fonction de $k$ . Elle décroît nécessairement, puisque plus de groupes signifie des points plus près de leur centre, jusqu'à zéro quand chaque point est son propre groupe.

Le coude est la valeur de $k$ après laquelle la décroissance devient nettement plus lente : ajouter un groupe de plus n'apporte alors presque rien.

La silhouette

Pour chaque point, soit $a$ la distance moyenne aux points de son groupe et $b$ la distance moyenne aux points du groupe voisin le plus proche.

Sa silhouette vaut $\dfrac{b - a}{\max(a, b)}$ , entre $-1$ et $1$ . Elle est proche de 1 si le point est bien dans son groupe, négative s'il aurait dû aller ailleurs.

La silhouette du partitionnement est la moyenne de celles de ses points.

main.py

Sortie

>_ Prêt à exécuter…

Ce que les deux indicateurs disent ici.

Le coude. L'inertie tombe de 615 à 263 en passant à deux groupes, puis de 263 à 22 en passant à trois : une chute de 92 %. De trois à quatre, elle ne baisse plus que de 19 %, puis 23 %, puis 22 %. La décroissance devient régulière et sans intérêt : on ne fait plus que découper des groupes déjà homogènes. Le coude est donc à trois.
La silhouette. Elle vaut 0,61 pour deux groupes, culmine à 0,84 pour trois, et redescend ensuite : 0,71, puis 0,57, puis 0,40. Le maximum désigne la même valeur.
Les deux concordent, ce qui est le cas favorable. Quand ils divergent, aucun n'a raison contre l'autre : c'est le signe que la structure n'est pas nette, et la décision redevient une question métier.

Le coude n'est pas toujours là

Sur des données réelles, la courbe d'inertie est souvent lisse, sans angle visible. Chercher un coude qui n'existe pas conduit à en inventer un.
Dans ce cas, la silhouette est plus robuste, et surtout la réponse peut venir d'ailleurs : combien de segments l'entreprise sait-elle traiter, combien d'équipes existe-t-il, combien de catégories la suite du processus accepte-t-elle ? Un partitionnement en dix-sept groupes est mathématiquement défendable et opérationnellement inutile.

La classification hiérarchique

Le principe ascendant

Partir de $n$ groupes d'un individu chacun. Fusionner à chaque étape les deux groupes les plus proches, jusqu'à n'en avoir qu'un.

L'arbre des fusions s'appelle un dendrogramme. Sa hauteur à chaque nœud est la distance à laquelle la fusion a eu lieu.

Ce qu'elle apporte que les k moyennes n'ont pas.

Elle ne demande pas $k$ à l'avance. On construit l'arbre entier, puis on choisit la hauteur de coupe, ce qui donne tous les découpages d'un coup.
Elle montre la structure emboîtée. Un dendrogramme dit non seulement quels groupes existent, mais lesquels se ressemblent le plus, et à quelle distance ils se séparent. Deux longues branches signalent des groupes vraiment distincts ; des fusions à hauteur presque égale signalent qu'il n'y a pas de découpage naturel.
Elle est déterministe. Pas d'initialisation, donc pas de résultat qui change d'une exécution à l'autre.
Le prix est le coût : il faut calculer et maintenir les distances entre tous les groupes, ce qui devient prohibitif au-delà de quelques dizaines de milliers d'individus, là où les k moyennes tiennent des millions.

main.py

Sortie

>_ Prêt à exécuter…

Vérification rapideon peut se reprendre

Qu'apporte la classification hiérarchique que les k moyennes n'ont pas ?

Évaluer sans étiquettes

Trois questions, dans cet ordre, et la dernière décide

Les groupes sont-ils géométriquement nets ? C'est ce que mesurent l'inertie et la silhouette. C'est nécessaire et très insuffisant.
Sont-ils stables ? Relancer sur un sous-échantillon de 80 % des individus, plusieurs fois, et regarder si les mêmes groupes reviennent. Un partitionnement qui change à chaque tirage ne décrit rien de réel.
Veulent-ils dire quelque chose ? Décrire chaque groupe par les moyennes de ses attributs et le faire lire par quelqu'un qui connaît le métier. Si personne ne sait nommer les groupes, ils n'existent pas.
Aucune mesure automatique ne remplace la troisième question, et c'est ce qui distingue le partitionnement de tout ce que ce module verra ensuite.

Ce que ferait scikit-learn. Les vingt lignes écrites plus haut correspondent à quelques appels dans la bibliothèque de référence, qu'il vaut mieux reconnaître.

from sklearn.cluster import KMeans, AgglomerativeClustering
from sklearn.metrics import silhouette_score
from sklearn.preprocessing import StandardScaler

Z = StandardScaler().fit_transform(X)
km = KMeans(n_clusters=3, n_init=10, init="k-means++").fit(Z)
print(km.inertia_, silhouette_score(Z, km.labels_))

Les valeurs par défaut valent la peine d'être lues : n_init=10 relance dix fois, et init="k-means++" choisit les départs. Ce sont exactement les deux parades de la section sur l'initialisation, et elles sont actives sans qu'on les demande.

Mettre en pratique

L'inertie est le seul nombre que les k moyennes cherchent à réduire. La calculer à la main sur six points suffit à comprendre ce que l'algorithme fait, et ce qu'il ne fait pas.

Calculer une inertie

1.
Six points valent 1, 2, 3, 10, 11 et 12. Avec un seul groupe, quel est le centre ?
2.
Quelle est l'inertie de ce groupe unique, c'est-à-dire la somme des carrés des écarts au centre ?
3.
Avec deux groupes de centres 2 et 11, quelle est l'inertie totale ?
4.
Par quel facteur le passage à deux groupes réduit-il l'inertie ?

Pourquoi l'inertie ne peut pas remonter. Chaque étape d'affectation place chaque point auprès du centre le plus proche, ce qui ne peut que réduire sa contribution. Chaque étape de déplacement place le centre à la moyenne de son groupe, qui est par définition le point qui minimise la somme des carrés des écarts.
Les deux étapes réduisent donc l'inertie ou la laissent égale, jamais ne l'augmentent. C'est ce qui garantit la convergence, et c'est aussi ce qui explique qu'elle ne garantit rien sur la QUALITÉ du résultat : l'algorithme descend, sans savoir vers quel creux.

La coopérative a lancé les k moyennes sur ses parcelles, pour k de 1 à 6. Combien de groupes retenir pour adapter son conseil ?

Chaque parcelle est décrite par son rendement et son apport d'azote, standardisés. Pour chaque valeur de k, l'algorithme a été relancé dix fois, et le meilleur partage gardé.

k	Inertie	Silhouette
1	900	non définie
2	520	0,48
3	150	0,66
4	128	0,52
5	110	0,45
6	96	0,41

À k = 3, les trois groupes ont pour moyennes :

Groupe	Parcelles	Rendement (q/ha)	Azote (kg/ha)
A	112	64	148
B	96	65	108
C	52	53	122

Par où commencer ? Calculer, pour chaque passage de k à k + 1, la part d'inertie gagnée : c'est elle, et non l'inertie elle-même, qui montre le coude.

Vérification rapideon peut se reprendre

Pourquoi comparer les chutes d'inertie plutôt que les inerties elles-mêmes ?

Le corrigé

Calculer les chutes d'inertie. De 1 à 2 groupes, l'inertie perd 42 % ; de 2 à 3, 71 % ; puis 15 %, 14 % et 13 %.
Repérer le coude. La chute s'effondre après k = 3 : un quatrième groupe ne rapporte plus que 15 % quand le troisième en rapportait 71.
Confirmer par la silhouette. Elle culmine à 0,66 pour trois groupes et redescend ensuite : les deux indicateurs désignent la même valeur.
Vérifier que les groupes se nomment. Le groupe A rend 64 q/ha avec 148 kg/ha d'azote ; le groupe B rend autant, 65 q/ha, avec 40 kg de moins ; le groupe C rend 53 q/ha malgré 122 kg/ha. Le service agronomique sait quoi dire à chacun : réduire l'azote en A, ne rien changer en B, chercher la cause en C. Trois groupes, qui veulent dire quelque chose.

Pourquoi les k moyennes échouent-elles sur deux anneaux concentriques, et que faire ?

Par où commencer ? Se demander quelle forme a la frontière entre deux centres, quelle que soit leur position.

Le corrigé

Tracer la frontière entre deux centres. Affecter chaque point au centre le plus proche revient à couper le plan par la médiatrice des deux centres : une droite.
En déduire la forme des groupes. Avec plus de centres, les frontières restent des morceaux de droites : les groupes obtenus sont toujours convexes.
Confronter aux anneaux. L'anneau intérieur et l'anneau extérieur ont le même centre, et aucune droite ne les sépare : l'algorithme coupe le plan en deux moitiés et se trompe sur la moitié des points.
Changer d'outil plutôt que de réglage. Le partitionnement spectral, qui travaille sur un graphe de voisinage, ou une méthode fondée sur la densité séparent ces anneaux sans difficulté.
Vérifier. Relancer les k moyennes depuis d'autres départs ne change rien : toutes leurs solutions sont convexes. Une limite de structure ne se règle pas.

Une enseigne de bricolage partitionne ses 80 magasins pour adapter son assortiment. Combien de groupes retenir ?

Chaque magasin est décrit par son chiffre d'affaires au mètre carré, la part du jardin dans ses ventes et son panier moyen, standardisés. Pour chaque valeur de k, l'algorithme a été relancé dix fois, et le meilleur partage gardé.

k	Inertie	Silhouette
1	320	non définie
2	190	0,71
3	150	0,52
4	92	0,58
5	84	0,49
6	78	0,44

À k = 2, les deux groupes séparent les magasins de plus de 5 000 m² des autres. À k = 4, les directeurs régionaux reconnaissent des magasins de centre-ville, de périphérie, de bourg rural et de littoral saisonnier ; sur dix relances avec 80 % des magasins tirés au hasard, ces quatre groupes reviennent neuf fois.

Par où commencer ? Calculer, pour chaque passage de k à k + 1, la part d'inertie gagnée, puis la confronter à la silhouette.

Le corrigé

Calculer les chutes d'inertie. 41 %, 21 %, 39 %, 9 % et 7 %.
Repérer le coude. Le quatrième groupe rapporte encore 39 %, le cinquième 9 % : le coude est à k = 4.
Lire la silhouette. Elle culmine à 0,71 pour deux groupes. Les deux indicateurs divergent, signe que la structure n'est pas nette : la décision redevient une question de métier.
Juger le sens et la stabilité. Les deux groupes de k = 2 ne font que retrouver la surface des magasins, que l'enseigne connaît déjà ; les quatre de k = 4 se nomment, et reviennent neuf fois sur dix.
Conclure, et vérifier ce que mesure la silhouette. Quatre groupes. Une silhouette maximale mesure la netteté géométrique, pas l'intérêt : ici, la coupure la plus nette est celle qui n'apprend rien.

La question change de nature

L'algorithme des k moyennes

L'inertie

Premier échec : l'initialisation

Deuxième échec : l'échelle

Troisième échec : la forme des groupes

Choisir le nombre de groupes

La classification hiérarchique

Évaluer sans étiquettes

Mettre en pratique

Dans la bibliothèque d'exercices

Premier échec : l'initialisation

Deuxième échec : l'échelle

Troisième échec : la forme des groupes