Apprendre sans étiquettes
Ce que ce chapitre apporte
- Formuler un problème de partitionnement et dire ce qui le distingue d'une classification.
- Dérouler l'algorithme des k moyennes en séparant affectation et déplacement.
- Définir l'inertie et justifier qu'elle ne peut pas remonter.
- Choisir un nombre de groupes par la méthode du coude et par la silhouette.
- Reconnaître les trois échecs : initialisation, échelle, forme des groupes.
- Lire un dendrogramme et dire ce qu'apporte la classification hiérarchique.
- Évaluer un partitionnement en l'absence d'étiquettes.
La question change de nature
É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.
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 serveurs par salle et un autre qui les sépare par génération de matériel 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
Choisir 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.
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.
Affectation : chaque point rejoint le centre le plus proche. Les centres n'ont pas bougé.
L'inertie
L'inertie d'un partitionnement est la somme des carrés des distances de chaque point au centre de son groupe.
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.
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.
Premier échec : l'initialisation
Voici exactement les mêmes douze points, avec trois centres posés ailleurs.
Affectation : chaque point rejoint le centre le plus proche. Les centres n'ont pas bougé.
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.
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.
Deuxième échec : l'échelle
La raison tient en une ligne de calcul. Dans une distance euclidienne, deux points distants de 40 000 mégaoctets et de 12 degrés donnent , soit 40 000,002 : 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.
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.
Troisième échec : la forme des groupes
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.
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.
Tracer l'inertie en fonction de . 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 après laquelle la décroissance devient nettement plus lente : ajouter un groupe de plus n'apporte alors presque rien.
Pour chaque point, soit la distance moyenne aux points de son groupe et la distance moyenne aux points du groupe voisin le plus proche.
Sa silhouette vaut , entre et . 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.
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.
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
Partir de 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.
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.
Évaluer sans étiquettes
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.
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.
Exercices type
L'inertie peut-elle augmenter d'une étape à la suivante ?
Non, jamais, et chacun des deux gestes en donne la raison.
L'affectation remplace, pour chaque point, la distance à son ancien centre par celle au centre le plus proche. Cette seconde distance est inférieure ou égale à la première par définition.
Le déplacement place chaque centre au barycentre de son groupe, or le barycentre minimise la somme des carrés des distances aux points du groupe. Aucune autre position ne ferait mieux.
L'inertie décroît, elle est minorée par zéro, et le nombre de partages possibles est fini : l'algorithme s'arrête. Si une implémentation affiche une inertie qui remonte, elle a un bug.
Deux exécutions sur les mêmes données donnent des groupes différents. Est-ce normal ?
Oui, si les départs sont tirés au hasard, ce qui est le cas par défaut.
L'algorithme converge vers un minimum local, et il en existe plusieurs. Le chapitre en a montré deux, d'inerties 6 et 37 sur les mêmes douze points.
La parade est de relancer plusieurs fois et de garder le résultat de plus faible inertie. C'est ce que fait n_init=10 dans les bibliothèques.
Si les résultats restent très différents malgré dix relances, ce n'est plus un problème d'initialisation : c'est que les données n'ont pas de structure de groupes nette, et la conclusion à tirer est celle-là.
Faut-il standardiser avant un partitionnement ?
Presque toujours oui, parce que l'algorithme repose entièrement sur une distance.
Sans standardisation, la variable la plus étalée décide seule du partage. Une taille mémoire en octets écrase une température en degrés, quel que soit l'intérêt de l'une et de l'autre.
Le chapitre l'a mesuré : 55 % de bons regroupements sans mise à l'échelle, soit le hasard, contre 100 % avec.
L'exception est le cas où les unités sont déjà comparables et où les écarts d'étendue ont un sens métier qu'on souhaite préserver. C'est rare, et cela se justifie explicitement.
La silhouette vaut 0,71 pour k = 4 et 0,69 pour k = 5. Que conclure ?
Que l'indicateur ne tranche pas. Un écart de deux centièmes n'est pas une différence : il tiendrait à un point déplacé.
Trois suites possibles.
Regarder la stabilité : relancer sur des sous-échantillons et voir laquelle des deux valeurs donne des groupes reproductibles.
Regarder les groupes : à cinq groupes, l'un d'eux est-il un vrai groupe ou une poignée de points isolés ?
Demander au métier : quatre ou cinq segments, lequel sait-on traiter ?
Ce qu'il ne faut pas faire, c'est retenir k = 4 parce que 0,71 dépasse 0,69. Ce serait accorder à trois chiffres une précision qu'ils n'ont pas.
Pourquoi k-means échoue-t-il sur deux anneaux concentriques ?
Parce qu'affecter chaque point au centre le plus proche revient à découper le plan par des droites, à mi-chemin entre les centres.
Les groupes obtenus sont donc toujours convexes. Or l'anneau intérieur et l'anneau extérieur ne sont séparables par aucune droite : ils partagent le même centre.
L'algorithme fait ce qu'il sait faire, il coupe le plan en deux moitiés, et se trompe sur la moitié des points.
La parade est de changer d'algorithme : 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é. Reconnaître qu'un algorithme est structurellement inadapté vaut mieux que de le régler indéfiniment.
Un partitionnement affiche une excellente silhouette. Est-il bon ?
On n'en sait rien. La silhouette mesure la netteté géométrique des groupes, pas leur intérêt.
Un découpage par la variable la plus étalée du jeu peut donner une silhouette superbe et ne rien signifier. Un découpage qui sépare les serveurs par salle alors qu'on cherchait des profils d'usage aussi.
Les trois questions à poser sont, dans l'ordre : les groupes sont-ils nets, sont-ils stables sur des sous-échantillons, et quelqu'un qui connaît le métier sait-il les nommer ?
C'est la troisième qui décide, et aucune mesure automatique ne la remplace.
1.Pendant l'étape d'affectation des k moyennes…
2.L'inertie d'un partitionnement peut-elle remonter d'une étape à la suivante ?
3.Deux exécutions donnent des inerties de 6 et de 37 sur les mêmes données. Pourquoi ?
4.Sans mise à l'échelle, sur quoi porte réellement le partage ?
5.Pourquoi k-means ne sépare-t-il pas deux anneaux concentriques ?
6.Qu'apporte la classification hiérarchique que les k moyennes n'ont pas ?
La méthode
- Standardiser avant tout partitionnement fondé sur une distance.
- Relancer au moins dix fois depuis des départs différents, et garder la plus faible inertie.
- Employer k-means++ plutôt qu'un tirage uniforme des centres initiaux.
- Tracer l'inertie en fonction de k et chercher le coude, sans l'inventer s'il n'y est pas.
- Calculer la silhouette et comparer les deux indications.
- Vérifier la stabilité sur des sous-échantillons avant de retenir un découpage.
- Décrire chaque groupe par les moyennes de ses attributs et le faire lire par le métier.
- Changer d'algorithme plutôt que de régler indéfiniment, quand les groupes ne sont pas convexes.
Synthèse
- Un partitionnement cherche des groupes sans étiquettes : il n'y a pas de bonne réponse à comparer.
- Les k moyennes alternent affectation et déplacement, deux gestes qu'il faut voir séparément.
- L'inertie est la somme des carrés des distances aux centres ; elle ne peut jamais remonter.
- L'algorithme termine toujours, et converge vers un minimum local.
- Un mauvais départ coûte cher : inertie 37 contre 6 sur les mêmes douze points.
- Les parades sont de relancer et d'employer k-means++, actives par défaut dans les bibliothèques.
- Sans mise à l'échelle, la variable la plus étalée décide seule : 55 % contre 100 % de bons regroupements.
- Les groupes trouvés sont convexes : deux anneaux concentriques sont hors de portée.
- Le coude et la silhouette aident à choisir sans jamais trancher.
- La classification hiérarchique donne tous les découpages d'un coup, et coûte cher au-delà de quelques dizaines de milliers d'individus.
- Évaluer sans étiquettes demande trois questions : net, stable, et nommable par le métier.