• 12 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 23/12/2019

Découvrez l'apprentissage non-supervisé

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

A la fin de ce chapitre, vous serez capable de :

  • analyser un tableau de données,

  • projeter les données afin de les visualiser,

  • faire le clustering des données.

Initiez-vous à l'analyse en composantes principales

Dans cette partie, nous allons apprendre à résumer un tableau de données par l'analyse en composantes principales (ACP).

C'est quoi l'ACP ?

C'est une technique linéaire permettant de projeter des données x de dimension d en d'autres données t de dimension p<d . On parle de réduction de dimension. L'idée de l'ACP est de projeter les données sur des axes préservant la variance des données. Si on s'arrange pour que p=2 ou 3, on peut alors visualiser les données projetées.

Illustration png
Des données à la visualisation via l'ACP

Les données

Le tableau suivant comporte des données biologiques mesurées sur plusieurs sportives et sportifs. Ces paramètres biologiques sont par exemple la concentration d'hémaglobine (hg), le taux d'hématocrite (hc), la quantité de ferritine (ferr), l'indice de masse corporelle (bmi) ou la taille (ht). La description complète de ces paramètres se trouve ici.

Tableau de données biologiques
Tableau de données vu comme une matrice.

Chaque colonne du tableau représente une variable. L'hémoglobine (hg) est la 4e variable, le tableau en comportant d=11 (la dernière colonne servant juste à distinguer les sportives et les sportifs).

Une ligne du tableau représente un sportif qui est décrit par ses d variables. La ième ligne est le point xi, un vecteur de dimension d dont les éléments sont  xi=(xi,1xi,d) .

Pour n sportifs, nous aurons n vecteurs  xi ; le tableau est simplement une matrice de dimension n×d .

X=(x1,1x1,dxn,1xn,d)=(x1x2xn)Rn×d

Analyse des données

On peut mener une première analyse statistique des données en traçant les boxplots (boîtes à moustache) des variables, comme sur la figure suivante.

Boxplots des variables
Boxplots des variables

Nous pouvons faire quelques remarques :

  • Les variables n'ont pas les mêmes ordres de grandeur (rcc, wcc prennent de petites valeurs comparativement à ferr ou ssf).

  • Les variables ferr, ssf ont une grande variance alors que d'autres comme rcc ou hg varient peu en proportion.

  • ferr, ssf présentent quelques valeurs atypiques.

Cette anaylse est un peu limitée parce qu'elle ne permet pas de déterminer le lien entre différentes variables. (Quel est le lien entre la concentration d'hémaglobine hg  et le taux d'hématocrite hc ?)  Elle ne permet pas non plus de comparer en un coup d'oeil deux sportifs. Il faut donc un autre outil pour approfondir la compréhension des données : ce sera l'ACP.

L'analyse en composantes principales

Prenons l'exemple suivant : on a n points en 3D (graphique de gauche) qu'on souhaite projeter en 2D.

Illustration graphique du principe de l'ACP
Illustration graphique du principe de l'ACP

Si l'on projette sur le plan en vert (figure du milieu), les points seront confondus. A contrario, sur le plan en rouge (figure à droite), la dispersion des points sera préservée c'est-à-dire qu'on maximisera la variance des points après projection.

 Comment trouver le bon espace de projection ?

 On cherche à réaliser la projection xRdtRp,p<d 

L'espace de projection PRp sera construit de manière progressive :

  • D'abord, on va chercher le meilleur axe de projection (1D) u1 .

  • Ensuite, on détermine le meilleur plan en trouvant le deuxième axe u2 .

  • Et ainsi de suite jusqu'à obtenir P .

Préalable
Il faut centrer et réduire les données (nous reviendrons dessus) :

{xi}ni=1{~xi}ni=1avec˜xij=xiˉxjσj

avec  ˉxj  et  σj  la moyenne et la variance de la variable j .

Recherche de la première direction de projection u1Rd 

Illustration de la projection sur le premier vecteur
Illustration de la projection sur le premier vecteur

On veut :

  • un vecteur normé u12=1 ,

  • la projection orthogonale des points sur u1{ti=˜xiu1R}ni=1 soit de variance maximale. 

Le problème de maximisation de la variance est alors :

maxu1Rdu12=11nni=1t2i=maxu1Rdu12=11nni=1(˜xiu1)2

En utilisant les astuces mathématiques on a :

 

Ceci nous permet de reformuler le problème sous la forme suivante :

maxu1Rdu12=1u1Cu1

Recherche de la deuxième direction de projection u2Rd  

Comme précédemment, le deuxième vecteur doit :

  • être normé u22=1 ,

  • maximiser la variances des projections {ti=˜xiu2R}ni=1sur u2 ,

  • être orthogonal à u1 pour former une base de  R2  (voir figure).

Illustration de la construction du deuxième axe de projection
Illustration de la construction du deuxième axe de projection

et ainsi de suite pour avoir des directions de projections supplémentaires.

 Comment coder l'ACP soi-même ?

L'algorithme tient en quelques lignes :

  1. Centrer et réduire les données : {xi}ni=1{~xi}ni=1avec˜xij=xiˉxjσj

  2. Calculer C=1n˜X˜X

  3. Trouver la décomposition en valeurs propres de  C  :  U,Λeig(C) 

  4. Trier les valeurs propres   Λ par ordre décroissant et les vecteurs propres  U en conséquent

  5. Construire la matrice de projection en dimension p<d  Up=(u1,,up)Rd×p   

Utilisation de l'ACP

Revenons aux données biologiques. Pour en faire l'ACP, on a besoin de la matrice de corrélation des variables. Commençons par tracer les données par paires de variables :

Tracé par paires de variables des données biologiques
Analyse bivariée des variables

 Nous constatons que certaines variables sont linéairement dépendantes (graphiques entourés en rouge). Nous pouvons quantifier ceci en examinant la matrice de corrélation C .

Matrice de corrélation (données biologiques)
Matrice de corrélation (données biologiques)

C est symétrique, avec des 1 sur la diagonale (normal car une variable est forcément fortement correlée avec elle-même). On voit, par exemple, que les variables hg et hc ont un coefficient de corrélation de 0.95, hg et rcc ont une corrélation de 0.92 ou ssf et pcBfat une corrélation de 0.96. Comment ces informations sont exploitées par l'ACP ? Voir la partie "Visualisation des données".

Projection des données

Une fois qu'on a calculé les moyennes  ˉxRd et les écart-types des variables, puis la matrice UpRd×p, la projection en dimension p d'un point quelconque xRd en tRp,p<d  est résumée par le schéma suivant :

Procédure de projection d'un point par l'ACP
Procédure de projection d'un point par l'ACP

 Visualisation des données

Prenons p=2 ; les données projetés sont en 2D et nous pouvons les visualiser.

Visualisation des données biologiques via l'ACP
Visualisation des données biologiques via l'ACP

Comment analyser ce graphique ?

  • Chaque point tiR2 représente un athlète. Si nous colorons les points en fonction du genre, on voit apparaître deux groupes homogènes. Nous pouvons donc visuellement comparer les sportifs entre eux.

  • L'axe u1 est essentiellement déterminé par la combinaison linéaire des variables rcc,hc,hg d'un côté et ht,bmi,wt,lbm de l'autre. Nous pouvons voir, sur la matrice de corrélation, que ces variables ont des coefficients de corrélation linéaire plus forts entre elles qu'avec les autres variables.

  • L'axe u2 est lui déterminé par les variables ssf,pcBfat qui ont des corrélations négatives avec les variables liées à l'axe 1.

  • Le degré de contribution de chaque variable à l'axe de projection est lié à sa couleur et à la longueur de la flèche.

  • Les variables corrélées avec les axes 1 et 2 sont les plus importantes pour expliquer la variabilité (la variance) dans le jeu de données. Les autres variables apportent peu d'informations et peuvent être ignorées dans l'analyse des données.

Comment choisir le nombre d'axes p ?

La réponse n'est pas simple. Comme l'ACP détermine l'espace de projection en maximisant la variance des données, nous pouvons visualiser la variance expliquée par chaque axe.

Graphique des valeurs propres
Graphique des valeurs propres

Les directions de projection avec les plus grandes variances sont les plus “importantes” (principales). La première direction explique 45% de la variance des données et les trois premières directions expliquent près de 80% de la variance. Les 4 dernières directions ont peu d'influence. Au vu du graphique, on peut retenir p=3 ou p=6 (oui, ce n'est pas simple).

En résumé

  • Pourquoi faire une ACP ?

Pour analyser les liens de corrélation linéaire entre les variables, représenter les points, réduire la dimension des données.

  • Comment faire l'ACP ?

Faire la décomposition en valeurs propres de la matrice de corrélation, projeter les données sur les p premiers vecteurs propres.

Deuxième partie : Comprenez l'algorithme K-Means pour le clustering

Dans la première partie du chapitre, nous avons vu comment résumer les données en réduisant leur dimension. Dans cette partie, nous allons voir comment résumer les données par regroupement en classes homogènes : c'est le clustering. Nous allons étudier pour cela la méthode des K-Means, aussi appelée méthode des centres mobiles.

Qu’est-ce que le clustering ?

Le clustering, que l’on appelle également partitionnement, est une technique d'exploration des données qui vise à déterminer les relations de similarité entre des points.

Étant donné un ensemble de n points xi en dimension d qu'on va noter D={xiRd}ni=1 , l'idée est de regrouper ces points en classes homogènes.

Tableau de données Figure après clustering des données
Exemple

Comme le montre cette figure, le clustering permet d’obtenir des classes distinctes dans lesquelles les points seront les plus similaires possibles en se basant sur une notion de distance.

Le clustering s'utilise dans plusieurs domaines d'applications. Par exemple, il permet de réaliser la segmentation de la clientèle d'un magasin à partir des informations sur les clients et la liste de leurs achats :

Illustration
Illustration (Source : https://www.alleywatch.com/2013/08/segmentation-for-social-media-and-why-you-need-to-know-about-it/)

On peut également appliquer le clustering pour réaliser la compression des couleurs d'une image de telle sorte que l'image compressée soit la plus proche de l'image réelle. Dans l’espace des couleurs, chaque pixel RGB est approché par le code le plus similaire :

Compression des couleurs d'une image
Exemple (Source : C.M. Bishop, "Pattern Recognition and Machine Learning", Springer Verlag)

Il existe plusieurs méthodes de clustering. La plus connue est la méthode de K-Means (que l’on appelle aussi K-Moyennes ou centres mobiles).

L'algorithme K-Means cherche à regrouper les points en K classes. Chaque classe Ck est caractérisée par son centre de gravité que nous appellerons mk . Afin de mieux comprendre son principe, prenons l’exemple suivant :

Figure représentant des données à regrouper en 2 classes
Figure représentant des données à regrouper en 2 classes

La figure représente les données (les points noirs) que nous souhaitons regrouper en deux classes. Commençons par initialiser les centres des classes : ce seront les losanges bleu et rouge, qui sont positionnés aléatoirement.

Connaissant ces centres initiaux, chaque point est affecté à la classe dont le centre est le plus proche. Ceci donne la figure suivante

Figure  après affectation de chaque point à la classe dont le centre est le plus proche
Figure après affectation de chaque point à la classe dont le centre est le plus proche

Connaissant les points associés à chaque classe, on met à jour leur centre qui est calculé comme le barycentre des points de la classe. Bien évidemment, le résultat obtenu à cette première étape ne sera pas satisfaisant puisqu'on a choisi aléatoirement les centres initiaux. On va donc ré-itérer la démarche afin d'améliorer le résultat.

Mise à jour des centres de chaque classe
Mise à jour des centres de chaque classe

À la deuxième étape, nous modifions l'affectation des points aux deux classes en utilisant cette fois-ci les centres calculés à la première itération. Ceci donne la figure suivante, où l’on constate que d'autres points ont été intégrés à la classe bleue :

Recalcul des nouveaux centres des clusters
Modification de l'affectation des points aux deux classes

Partant de cette affectation, les nouveaux centres des clusters sont recalculés en fonction des points qui sont tombés dans les clusters :

Recalcul des nouveaux centres des clusters
Recalcul des nouveaux centres des clusters

On alterne ainsi l’affectation des points aux classes et l’estimation de leurs centres jusqu’à convergence. L'animation ci-dessous illustre parfaitement notre exemple :

 

La convergence est atteinte quand les centres des clusters ne changent plus.

L'algorithme

L'idée de l'algorithme de K-Means est très simple et facile à mettre en œuvre. L'algorithme nécessite en entrée les données d'apprentissage xi,i=1,,N et le nombre voulu de classes K . Après initialisation des K centres, on exécute itérativement jusqu'à convergence deux étapes :

  • Étape 1 : l'affectation des points aux classes :

i{1n}si=argmink{1K}ximk2etC={i:si=}

Pour chaque point   xi   on calcule sa distance euclidienne à tous les centres mk ; le point xi sera attribué à la classe C si sa distance à cette classe est la plus petite.

  • Étape 2 : la mise à jour du centre de chaque classe

mk=1nkiCxi

 nk  est le nombre de points de la classe Ck. Le centre mk est le barycentre des points de la classe Ck .

On peut se demander quel problème mathématique résoud cet algorithme ?

Pour formaliser ce problème, on va associer à un point xi des coefficients scalaires αi,k qui vont indiquer si ce point est affecté à la classe k (auquel cas  αi,k vaut 1 sinon il vaut 0) :

αi,k={1sixiCk0autrement

 
L'algorithme des K-Means cherche à minimiser la somme des distances des points aux centres des classes, avec la contrainte qu'un point ne peut appartenir qu'à une seule classe.  Ceci donne le problème d’optimisation suivant :

min{αi,k},{mk}J=ni=1Kk=1αi,kximk2avecαi,k{0,1}i,kxiest ou non dans la classeCketKk=1αi,k=1xi appartient à une seule classeCk

 Le critère J  va promouvoir le fait que les points d'une classe seront concentrés autour de son centre c'est-à-dire les points qui se ressemblent vont s'assembler.

À chacune des itérations, l’algorithme minimise alternativement J par rapport aux coefficients  αi,k (c'est l'étape 1), puis par rapport aux centres mk (c'est l'étape 2).

Pour l'étape 1, supposons qu'on connaît les centres ; la stratégie d'affectation d'un point quelconque xj à une classe peut se justifier mathématiquement. Pour cela, on ré-écrit le critère J en isolant les termes qui ne dépendent que de xj .

J=Kk=1αj,kxjmk2Lj+nijKk=1αi,kxjmk2

Minimiser J par rapport à αj,k,k=1,,K équivaut à minimiser que le terme  Lj c'est-à-dire à résoudre

min{αj,k}Ljavecαj,k{0,1}etKk=1αj,k=1

Dans l'autre sens, si on connaît les points de chaque cluster, c'est-à-dire les coefficients αi,k , et qu'on veut déterminer le centre m , il suffit d'isoler tous les termes relatifs à m  dans  J

J=ni=1αi,xim2L+ni=1kαikximk2

 Minimiser J par rapport à m revient à minimiser le terme en bleu L .

La courbe montre l'évolution du critère J au fil des itérations pour l'exemple illustratif vu au début du cours.
La courbe montre l'évolution du critère J au fil des itérations pour l'exemple illustratif vu au début du cours.

On constate que l'algorithme converge très rapidement, puisqu'au bout de 7 à 8 itérations le critère ne diminue plus.

 En pratique est-ce que l'algorithme des K-Means marche ? 

En pratique, cet algorithme est efficace. Néanmoins, il nécessite de faire quelques choix non-évidents. Par exemple, il faut déterminer le nombre de classes ou choisir les centres initiaux.

Prenons l’exemple ci-dessous dans lequel nous allons chercher à regrouper les points en 6 classes :

 

Nous allons choisir aléatoirement les centres initiaux et les représenter sous forme de carrés jaunes. Les 6 classes ainsi obtenues sont matérialisées par différentes couleurs. On trouve des formes géométriques correspondant aux lettres.

L'algorithme a été relancé en changeant l'initialisation :

 

Comment choisir le nombre de classes ?

Le choix du nombre de classes est un problème difficile, car le clustering est un problème d’apprentissage non-supervisé.

Il n’existe donc pas de vérité terrain nous permettant d’évaluer la pertinence des classes trouvées. On peut être guidé par l'application (exemple : on veut segmenter les utilisateurs de Velib' en K catégories), on peut tester différentes valeurs de K et retenir la meilleure solution. Retenez néanmoins qu’évaluer le résultat d'un clustering est subjectif.

Par exemple, les personnages sur cette image

Image représentant la famille Simpsons
Image représentant la famille Simpson

peuvent être regroupés ainsi :

Selont qu'ils sont de la famille Simpsons ou non... ou encore selon leur genre
Selon qu'ils sont de la famille Simpson ou non ...                 ou encore selon leur genre

Source : Les Simpsons, d'après l'oeuvre de Matt Groening.

En résumé

  • Le clustering est une approche d’exploration statistique qui vise à déterminer les similarités entre les points en les regroupant en classes ou groupes homogènes.

  • L’algorithme des K-Means, qui permet de résoudre ce type de problèmes, a la particularité d’être conceptuellement simple et rapide à mettre en œuvre. Il est basé sur la minimisation de la distance des points d’apprentissage aux centres des classes. Pour juger de son résultat, il faut préférer des classes homogènes et distinctes.

  • Il existe des critères ad-hoc permettant d’évaluer la méthode du clustering.

  • Le résultat peut changer avec l’initialisation et son évaluation reste subjective.

     

Après ce chapitre consacré à l'apprentissage non-supervisé, vous abordez dans le cours suivant votre premier problème d'apprentissage supervisé, la régression linéaire.

Exemple de certificat de réussite
Exemple de certificat de réussite