Apprentissage non supervisé : de la structure sans étiquettes

Toutes les méthodes vues jusqu’ici avaient une réponse à prédire, et cette réponse travaillait davantage qu’il n’y paraît. Elle définit ce que le modèle estime, elle donne un sens à une erreur hors échantillon, et elle tranche chaque décision de réglage par validation croisée. Supprimez-la et les trois disparaissent d’un coup.

L’apprentissage non supervisé est ce qui reste : seulement $X$, et la question de la structure qu’il contient. Cet article couvre les trois réponses standard et reste franc du début à la fin sur ce qui les rend plus difficiles à utiliser que tout ce qui précède : il n’y a rien contre quoi les vérifier.

A. Composantes principales : la direction de variance maximale

La première composante principale est la combinaison linéaire normalisée

$$Z_1 = \phi_{11}X_1 + \dots + \phi_{p1}X_p, \qquad \sum_{j=1}^{p}\phi_{j1}^2 = 1,$$

de plus grande variance. La contrainte pèse réellement : sans elle, vous pourriez doubler chaque $\phi_{j1}$, quadrupler la variance et recommencer sans limite - aucun maximum n’existerait. Fixer la norme à un fait de la question une affaire de direction.

Il existe une seconde description équivalente qu’il vaut la peine de retenir, car c’est elle qui rend l’ACP géométrique plutôt qu’algébrique : cette même direction est la droite la plus proche des $n$ observations, au sens des distances perpendiculaires au carré. La variance totale étant fixée, ce que les projections ne captent pas subsiste comme distance à la droite - maximiser l’une et minimiser l’autre sont un seul problème.

Un exemple travaillé

Six observations sur deux variables :

$$X = \begin{bmatrix} 2&0\\ 3&1\\ 4&3\\ 5&4\\ 6&7\\ 4&2 \end{bmatrix}, \qquad S = \begin{bmatrix} 2{,}0000 & 3{,}4000 \\ 3{,}4000 & 6{,}1667 \end{bmatrix} .$$

Les valeurs propres de $S$ sont $\lambda_1 = 8{,}0708$ et $\lambda_2 = 0{,}0958$, et le premier vecteur de charges vaut $\phi_1 = (0{,}4886;\ 0{,}8725)$. Projeter les données centrées sur $\phi_1$ donne des scores de variance $8{,}0708$ - la valeur propre est la variance captée par sa composante, d’où la lecture directe de la proportion de variance expliquée :

$$\text{PVE}_1 = \frac{8{,}0708}{8{,}1667} = 0{,}9883 .$$

Une seule direction porte 98,83 % de la variation. Un éboulis les ordonne et le conseil habituel est de chercher un coude - ce qui est un jugement à l’œil, non un test. Il n’existe pas de règle objective largement acceptée pour décider combien de composantes garder, et c’est le premier endroit où la réponse manquante se fait sentir.

Les charges ne sont pas les scores. Une charge dit combien une variable contribue à une composante et appartient au jeu de données entier ; un score dit où se situe une observation le long de celle-ci. Les confondre est la façon la plus courante de mal lire une sortie d’ACP.

L’ACP n’est pas non plus invariante d’échelle. La variance porte le carré des unités : enregistrer une longueur en millimètres plutôt qu’en mètres multiplie sa variance par $10^6$ et lui offre la première composante sans autre raison que le choix de la règle. Standardisez chaque variable à écart-type un - sauf si les variables partagent déjà les mêmes unités et que leurs variances différentes sont réellement significatives, auquel cas la mise à l’échelle détruit une information véritable.

B. Les K-moyennes, et l’optimum local où elles se figent

Les K-moyennes partitionnent les observations en $K$ classes exhaustives et disjointes, en minimisant la variation intra-classe totale

$$W(C_k) = \frac{1}{|C_k|}\sum_{i,\,i' \in C_k}\ \sum_{j=1}^{p}\big(x_{ij} - x_{i'j}\big)^2 .$$

Diviser par $|C_k|$ compte : une classe de $m$ points a $m^2$ paires ordonnées, si bien qu’une somme non divisée pénaliserait les grandes classes pour leur taille et non pour leur dispersion.

Il y a $K^n$ façons d’affecter $n$ observations à $K$ classes étiquetées, et environ $K^n/K!$ partitions distinctes une fois les étiquettes ignorées : le problème exact n’est pas résolu mais approché. L’algorithme affecte au hasard, puis alterne : calculer le centroïde de chaque classe, et réaffecter chaque observation au plus proche. Il converge parce qu’aucune des deux étapes ne peut augmenter l’objectif - le centroïde minimise les écarts au carré, et déplacer un point vers un centroïde plus proche ne peut pas empirer les choses - et parce que les partitions sont en nombre fini.

Il converge. Ce n’est pas la même chose qu’avoir raison.

Prenons sept points et $K = 3$ :

$$\{\,1,\ 2,\ 3,\ 10,\ 11,\ 20,\ 21\,\}$$

La recherche exhaustive sur les $3^7 = 2187$ affectations donne l’optimum global $\{1,2,3\}, \{10,11\}, \{20,21\}$ avec $\sum_k W(C_k) = 6{,}0$.

Partez maintenant de $\{1,2,3,10,11\}, \{20\}, \{21\}$. Les centroïdes valent $5{,}4$, $20$ et $21$, et chaque point est déjà affecté au plus proche : la première passe ne change rien, l’algorithme s’arrête aussitôt et rapporte

$$\textstyle\sum_k W(C_k) = 178{,}4 ,$$

près de trente fois pire. Rien n’est cassé : converger vers un optimum local est tout ce que promet la méthode, et l’échec est silencieux.

On lance donc les K-moyennes de nombreuses fois depuis des départs différents et l’on garde le meilleur résultat. C’est une partie de la méthode, non un raffinement pour quand on a le temps. Et $K$ ne peut pas être choisi par l’objectif, qui décroît de façon monotone quand $K$ augmente et atteint zéro lorsque chaque observation forme sa propre classe.

C. Classification hiérarchique, et le saut qui décide de la réponse

La classification agglomérative supprime l’engagement sur $K$ : partez de chaque observation seule, fusionnez à répétition les deux classes les moins dissemblables, et notez la hauteur de chaque fusion. Couper horizontalement le dendrogramme obtenu donne un regroupement : un seul arbre contient une réponse pour chaque $K$.

Deux mises en garde. D’abord, les regroupements sont emboîtés par construction - si le vrai regroupement ne l’est pas, aucune coupe ne le retrouvera. Ensuite, la mauvaise lecture habituelle : seule la hauteur de fusion mesure la similarité. La position horizontale ne signifie rien, et deux feuilles adjacentes peuvent ne fusionner qu’au sommet.

Fusionner exige une dissemblance entre groupes, et ce choix est le saut : le saut maximum prend la plus grande distance entre les groupes, le minimum la plus petite, le moyen la moyenne, le centroïde la distance entre centroïdes.

Les mêmes points, deux réponses différentes

Dix points : un groupe compact de trois, un autre de trois, et quatre points régulièrement espacés faisant le pont.

Le saut minimum n’a besoin que d’une paire proche : chaque point du pont s’accroche tour à tour à l’amas grandissant et la chaîne entraîne un groupe entier - une classe traînante. Les sauts maximum et moyen regardent la plus grande distance et la moyenne, refusent de fusionner des groupes globalement éloignés, et coupent les données par le milieu. C’est le comportement général, d’où la préférence pour les sauts maximum et moyen ; le saut centroïde a un défaut propre, l’inversion, où deux classes fusionnent sous la hauteur de l’une d’elles.

Voici ces mêmes dix points ci-dessous, regroupés de quatre façons. Changez de lien et regardez les couleurs bouger : le lien minimum entraîne tout le pont dans un seul amas de sept, tandis que le maximum et le moyen refusent et coupent au milieu. Rien dans les données ne préfère l'une des réponses, et c'est là que c'est inconfortable. Le second jeu de données compte trois points et existe par honnêteté : le lien par centroïde ne produit aucune inversion sur les dix, donc les montrer en prétendant le contraire serait affirmer ce qu'ils ne montrent pas. Sur trois points, il en produit une, et les hauteurs de fusion le disent.

D. Ce qui manque réellement

Rassemblons les décisions exigées par cet article : standardiser ou non ; combien de composantes garder ; combien de classes ; quelle mesure de dissemblance ; quel saut ; où couper. Chacune change la réponse, et pas une ne se tranche depuis l’intérieur des données.

Dans le parcours supervisé, chacune aurait été une simple validation croisée contre une réponse mise de côté. L’apprentissage non supervisé n’a pas de réponse à mettre de côté, et c’est ce que James et al. appellent de petites décisions aux grandes conséquences. La conséquence pratique est une discipline plutôt qu’une technique : essayez plusieurs jeux de choix raisonnables et rapportez la structure qui apparaît sous la plupart d’entre eux - plutôt que de présenter une exécution unique comme la réponse.

Le parcours de formation Apprentissage non supervisé reprend les trois méthodes avec les dérivations complètes, et les entrées d’encyclopédie Analyse en composantes principales et Classification par K-moyennes les couvrent comme références.