Business Intelligence
Visualisation de données (ACP)
Benjamin Piwowarski
22 mars 2021
$\def \argmin {\mathop{\textrm{argmin}}} \def \argmax {\mathop{\textrm{argmax}}} \def \RR {\mathbb{R}} \def \Ind#1{\mathbf{1}\left[#1\right]} \def \eqc { \stackrel{\small +}{=}} \def \px {\tilde{x}} \def \py {\tilde{x}} \def \rx {\hat{x}} \def \tr {\mathop{\mathrm{tr}}}$

Contexte et principe général

— Contexte général
  • Données : grand nombre de variables (et d'individus)
  • Objectif : synthétiser les données par réduction de dimension pour (suivant les cas)
    • Identifier les relations entre individus (notion de distance)
    • Identifier les relations entre variables (notion de corrélation)
    • Identifier les variables les plus informatives
Notes scolaires
  • Variables : maths/physique et français/anglais (2 axes)
  • Individus : jean/alan, evel/anni/pier, andr/brig, didi/mon
  • Variables informatives : Maths (ou physique) et français (ou anglais)
— Visualisation et exploration: deux grandes familles

Deux grandes familles

Source : Lebart-Morineau-Piron, Statistique exploratoire multidimensionnelle
  1. Visualisation dans un espace réduit
    1. Projections linéaires (ACP)
    2. Projections non-linéaires (MDS, LLE, t-SNE)
  2. Regroupement des individus en sous-ensembles (clustering)
— Exemple (chiffres MNIST)
Exemple de deux projections (linéaire et non linéaire pour des chiffres MNIST)
ACP (linéaire)
t-SNE (non linéaire)
— Formalisation - les données

Les échelles

Il y en a 4 qui ont des propriétés de plus en plus contraignantes :
  • L'échelle nominale (ex. sexe, nationalité, etc.)
  • L'échelle ordinale (ex. niveau de satisfaction)
  • L'échelle d'intervalle (ex. température Celcius)
    PCA
  • L'échelle de rapport (ex. hauteur, température Kelvin)
— Formalisation - les données

Données numériques

$$ X = \begin{pmatrix} x_{1,1} & ... & x_{1,p} \\ ... & x_{i,j} & ... \\ x_{n,1} & ... & x_{n,p} \end{pmatrix} = \begin{pmatrix} X_{1\bullet} \\ ...\\ X_{i\bullet} \\ ...\\ x_{n\bullet} \end{pmatrix} = \begin{pmatrix} x_{1}^T \\ ...\\ x_{i}^T \\ ...\\ X_{n}^T \end{pmatrix} = \left( X_{\bullet 1}\ldots X_{\bullet p}\right) = \left( v_{1}\ldots v_{p}\right) $$ avec
$x_i^T = X_{i\bullet}$ la $i$ème ligne (= individu)
$X_{\bullet j}$ la $j$ème colonne (= variable)

Analyse en Composantes Principales (ACP)

— Contexte général
  • Données : grand nombre de variables (et d'individus )
  • Objectif : synthétiser les données par réduction de dimension pour
    • Identifier les relations entre variables (notion de corrélation)
    • Identifier les relations entre individus (notion de distance)
    • Identifier les variables les plus informatives
— Principe général
Notations
Tableau de données $X \in \RR^{n \times p}$composé de
  • lignes = individus $x_1, \ldots, x_n$
  • colonnes = variables $v_1, \ldots v_p$
Intuition : vers un changement de base
L'idée est de trouver le sous-espace vectoriel $E_d$ de rang $d < p$ tel que la perte d'information de la projection des $x_{i}$ est minimisée sur $$\hat S_d^* =\argmin_{\hat S_d} \sum_{i=1}^{n}||x_i- \hat S_d(x_i)||^{2}$$ où $\hat S_d(x_i)$ est une projection orthogonale sur $E_d$
Projection orthogonale d'un vecteur (3D) sur un plan (2D)
— Intuition : exemple
Sur cet exemple,
  • Les indivus sont les points verts (2D)
  • Le premier axe permet de minimiser les erreurs de projection (sous-espace 1D = droite du premier axe)
  • Le second axe est perpendiculaire au premier (base)
— Préparation des données
(Rappel) Données = variable continues $X$ (matrice individus $\times$ variables)

On centre (obligatoire)

On centre les données $$X_c = X - \left( \begin{array}{ccc} \overline{X}_{\bullet 1} & \cdots & \overline{X}_{\bullet p} \\ &\cdots& \\ \overline{X}_{\bullet 1} & \cdots & \overline{X}_{\bullet p} \end{array}\right)$$ où $\overline{X}_{\bullet j}$ est la moyenne de la $j$ème colonne/variable.
Pourquoi faut-il centrer ?

On réduit (optionnel)

  • Variables réduites (on divise par l'écart type) dans le cas de variables hétérogènes (ACP normée) : attention, cela veut dire que chaque variable est aussi importante qu'une autre (ce qui peut ne pas être le cas).
  • — Projection

    Projection (linéaire) des individus

    Pour un point $x_i$ et un vecteur $m_j$ unitaire (i.e. $\|m_j\| = 1$) la projection de $x_i$ sur $m_j$ est définie par $$\hat x_i = (m_j \cdot x_i) m_j$$
    On peut généraliser à un ensemble de vecteurs orthogonaux ($m_j \cdot m_k = 0$ si $j\not=k$)
    $$\hat x_i = \sum_j (m_j \cdot x_i) m_j$$
    Sous forme matricielle, avec $M = (m_1 \cdots m_d)$, la projection de $x_i$ sur le sous-espace vectoriel engendré par $m_1, \ldots, m_d$ est :
    $$ \hat x_i = M {\color{blue} M^\top x_{i}} = \left( m_1 \cdots m_d \right) {\color{blue} \left( \begin{array}{c} m_1 \cdot x_i \\ \vdots \\ m_d \cdot x_i \end{array} \right)} $$
    La représentation $\color{blue} \tilde x_i$ de $x_i$ dans le sous-espace vectoriel est donnée par
    $$ \color{blue} \tilde x_i = M^\top x_i$$
    — Projection

    Projection (linéaire) des individus

    Projection de $\RR^p$ dans $\RR^d$
    • si $d \lt p$, réduction de dimension, reconstruction par approximation :
      $$\rx_{i} = M\px_i = MM^\top x_{i}$$
    • Si $d=p$, pas de réduction de dimension ($MM^\top=Id$), pas de perte d'information :
      $$\rx_i = MM^\top x_{i} = x_i$$
    Trouver M qui minimise l'erreur quadratique
    Le but peut maintenant être écrit :
    $$MSE(M) = \frac{1}{n} \sum_{i=1}^{n}||x_{i}-\rx_{i}||^{2}$$
    — Mimiser MSE(M)
    Essayons de résoudre ce problème...
    $$ \begin{eqnarray} MSE(M) &=& \frac{1}{n} \sum_{i=1}^{n} ||x_{i}-\rx_{i}||^{2} = \frac{1}{n} \sum_{i=1}^{n} (x_{i} - MM^\top x_{i}) \cdot (x_{i} - MM^\top x_i) \nonumber \\ &=& \frac{1}{n} \sum_{i=1}^{n} x_{i}^\top x_{i} - \frac{1}{n} \sum_{i=1}^{n} x_i^\top MM^\top x_{i} \\ \end{eqnarray}$$
    en utilisant le fait que $M^\top M=Id$
    On obtient donc
    $$\begin{eqnarray} \argmin_M MSE(M) & = & \argmax_M \sum_{i=1}^{n} x_i^\top MM^\top x_{i} = \argmax_M \tr(X M M^\top X^\top) \\ & = & \argmax_M \tr(\tilde{X}^\top \tilde{X}) \\ \end{eqnarray}$$
    où $\tilde{X}$ correspond aux individus projetés
    — Mimiser MSE(M)
    On a donc
    $$ \argmin_M MSE(M) = \argmax_M \tr(\tilde{X}^\top \tilde{X})$$
    Quel est le lien avec les "relations" entre les variables ?
    $\frac{1}{n-1} \tilde{X}^\top \tilde{X}$ est un estimateur de la matrice de covariance des données projetées
    $\tr(\tilde{X}^\top \tilde{X})$ est la somme des (estimateurs) des variances
    Conséquence
    Minimiser MSE(M)
    $\Leftrightarrow$
    maximiser la variance empirique des données projetées

    Trouver les axes de projection

    — 1er axe
    Comment trouver le 1er axe ?
    On repart de la maximisation $\argmax_M \tr\left( X MM^\top X \right)$
    On prend $M = (m_1)$ la matrice colonne où $m_1 \in \RR^p$
    On doit trouver $m_1$ qui maximise $ \tr\left( X MM^\top X \right)$
    On a
    $$ \begin{eqnarray} \tr\left( X m_1 m_1^T X^T \right) & = & \tr\left( m_1^T X^T X m_1 \right) = m_1^T X^T X m_1 \end{eqnarray}$$
    On pose $$ \Sigma = \frac{1}{n} X^T X $$ ce qui correspond à la matrice de covariance (empirique) des données
    — 1er axe

    Résolution par le langragien

    Problème = $\argmin_{m_1} MSE(m_1)= \argmin_{m_1} -m_1^\top \Sigma m_1$ avec $m_1^\top m_1=1$
    On le résoud en introduisant le lagragien$$\begin{eqnarray} \mathcal{L}(m_1,\lambda_1) &=& -m_1^\top \Sigma m_1 + \lambda_1 (m_1^\top m_1-1) \nonumber \\ \end{eqnarray}$$ dont l'optimum est atteint pour $\nabla_{m_1} \mathcal L = 0$ et $\nabla_{\lambda_1} \mathcal L = 0$ $$\begin{eqnarray} \nabla_{m_1} \mathcal{L}(m_1,\lambda_1) = -2 \Sigma m_1 + 2 \lambda_1 m_1 = 0 & ~~{\color{blue}\rightarrow}~~ & \Sigma m_1 = \lambda_1 m_1 \\ \nabla_{\lambda_1} \mathcal{L}(m_1,\lambda_1) = m_1^\top m_1-1 = 0 & {\color{blue}\rightarrow} & \| m_1 \| = 1\\ \end{eqnarray}$$
    Rappel - Valeurs propres et vecteurs propres
    Un vecteur propre $X$ associé à une valeur propre $\lambda$ doit vérifier la relation $AX = \lambda X$
    • $m_1$ et $\lambda_1$ sont respectivement des vecteurs propres et valeurs propres
    • $MSE(m_1)$ peut aussi s'écrire ainsi : $MSE(m_1)=\mathrm{constante}-\lambda_1$. Par conséquent, on cherche à maximiser la valeur propre
    • Le premier axe factoriel est issu du vecteur propre $m_1$ associé à la plus grande valeur propre $\lambda_1$ de la matrice de covariance $\Sigma$
    — 2nd axes et suivantes

    Identification du deuxième axe factoriel $m_2$

    $$ \begin{eqnarray} \min MSE(m_2) = -m_2^\top \Sigma m_2 \nonumber \\ \mbox{tel que } m_2^\top m_2=1 \mbox{ et } m_2^\top m_1=0 \nonumber \end{eqnarray}$$
    Ce qui revient à trouver la deuxième valeur propre $\lambda_2$ et son vecteur propre $m_2$ associé.
    Identification du troisième axe factoriel $m_3$ ... Même principe... etc...

    ACP en pratique

    — ACP en pratique
    À partir de données centrées $X$ que l'on centre ($X_c$)
    • Identifier les valeurs propres de $\Sigma=\frac{1}{n} X_c^\top X_c$ par décomposition en valeurs propres $$\Sigma = Q \Lambda Q^T$$ avec $m_i=Q_{\bullet i}$ le $i$ème vecteur propre associé à la valeur propre $\lambda_i$
    • Si les valeurs propres $\lambda_{i}$ sont décroissantes, et on peut obtenir la projection en dimension $d$ par $\tilde{Q} \tilde{Q}^\top$ avec $\tilde{Q}$ les $d$ premières colonnes de $Q$, i.e. $$\tilde Q = \begin{pmatrix} m_1 & \cdots & m_d \end{pmatrix}$$
    • Un individu dans l'espace projeté est donné par $\tilde x_i = \tilde Q^T x_i$
      Projeter les points pour obtenir les composantes : $$\tilde X =X_c \tilde{Q} = \begin{pmatrix} x_1^\top \tilde{Q} \\ \ldots \\ x_n^\top \tilde{Q} \end{pmatrix} $$ où chaque ligne $i$ correspond à la projection de l'individu $i$
    — Projection des variables
    Nous avons projeté les individus... mais comment faire pour les variables ?
    Pseudo-individu
    On utilise un «pseudo-individu» $e_j$ pour chaque variable $j$
    Les valeurs de $e_i$ sont 0 pour toutes les variables sauf la $j$ème qui vaut 1 ou (pour visualiser mieux) une déviation standard $\sigma_j$
    $$ e_j^\top = \begin{pmatrix} 0 & \ldots& 0 & \sigma_j & 0 & \ldots & 0\end{pmatrix}$$
    La projection de $e_i$ dans l'espace réduit donne
    $$ \tilde{Q}^\top e_j = \sigma_j \tilde{Q}^T_{j \bullet} $$
    i.e. la $j$ème ligne de la matrice $\tilde{Q}$

    Exemple

    — exemple (1 - données)
    Math Phys Fran Angl
    jean 6.0 6.0 5.0 5.5
    alan 8.0 8.0 8.0 8.0
    anni 6.0 7.0 11.0 9.5
    moni 14.5 14.5 15.5 15.0
    didi 14.0 14.0 12.0 12.5
    andr 11.0 10.0 5.5 7.0
    pier 5.5 7.0 14.0 11.5
    brig 13.0 12.5 8.5 9.5
    evel 9.0 9.5 12.5 12.0
    Données $X$
    Math Phys Fran Angl
    jean -3.67 -3.83 -5.22 -4.56
    alan -1.67 -1.83 -2.22 -2.06
    anni -3.67 -2.83 0.78 -0.56
    moni 4.83 4.67 5.28 4.94
    didi 4.33 4.17 1.78 2.44
    andr 1.33 0.17 -4.72 -3.06
    pier -4.17 -2.83 3.78 1.44
    brig 3.33 2.67 -1.72 -0.56
    evel -0.67 -0.33 2.28 1.94
    Données centrées $X_c$
    — ACP - exemple (2 - covariance)
    • Etape 1 : Matrice Variances-covariances dans l'espace des variables
      $$\Sigma=\frac{1}{n} X_c^\top X_c$$
    • MATH PHYS FRAN ANGL
      MATH 11.39 9.92 2.66 4.82
      PHYS 9.92 8.94 4.12 5.48
      FRAN 2.66 4.12 12.06 9.29
      ANGL 4.82 5.48 9.29 7.91
    Remarques
    • Si les données sont réduites, la variance de chaque variable est égale à 1.
    • On peut aussi calculer la matrice variances-covariances dans l'espace des individus : $\Sigma=\frac{1}{n} XX^\top $(cf méthodes noyau)
    • Une meilleure estimation (sans biais) de la matrice variances-covariance est $\Sigma=\frac{1}{n-1} XX^\top$
    — ACP - exemple, étape 3 : valeur et vecteurs propres
    $Q$ est égal à (valeurs propres entre parenthèses)
    $m_1$
    $\lambda_1 \approx 28.23$
    $m_2$
    $\lambda_2 \approx 12.03$
    $m_3$
    $\lambda_3 \approx 0.03$
    $m_4$
    $\lambda_4 \approx 0.01$
    MATH-0.5150.5690.1850.614
    PHYS-0.5080.371-0.450-0.634
    FRAN-0.492-0.658-0.4600.335
    ANGL-0.484-0.3250.742-0.329
    — Analyse en Composantes Principales (ACP)

    Exemple illustratif: Estimation des valeurs propres

    Facteur lambda inertie cumul
    1 28.23 0.70 0.70
    2 12.03 0.30 1.00
    3 0.03 0.00 1.00
    4 0.01 0.00 1.00
    Notion d'inertie
    L'inertie mesure le pourcentage de dispersion des points autour de l'axe factoriel (= % de la variance capturée).
    $$\mathrm{inertie}_k = \frac{\lambda_k}{\sum_{l=1}^{p} \lambda_l}$$
    Remarques
    • Les valeurs propres de $\frac{1}{n} X^\top X$ et de $\frac{1}{n} XX^\top $ sont égales $\rightarrow$ Rechercher la meilleure représentation des individus = meilleure des variables
    • Critère de choix des axes principaux: inertie cumulée $>80\%$, $\lambda_k >1$ (règle de Kaiser), coude de la courbe (éboulis), ...
    Dans l'exemple, on voit que les deux premiers axes couvrent quasiment 100% de la variance - la reconstruction sera presque parfaite
    — Analyse en Composantes Principales (ACP)

    Exemple illustratif : Etape 3 : Projection des individus et variables (biplot)

    • Deux individus proches se ressemblent
    • Deux variables très corrélées positivement sont du même côté sur un axe
    • Un individu sera proche des variables pour lesquelles il a de fortes valeurs (et inversement)
    • Plus les valeurs d'un individu pour une variable sont fortes, plus il sera éloigné de l'origine de l'axe factoriel.
    — Analyse en Composantes Principales (ACP) : exemple
    Exemple interactif : vous pouvez modifier les notes pour voir le résultat

    Extensions de l'ACP

    — Les différentes analyses factorielles
    Il existe différents types d'analyse factorielle qui sont toutes construites à partir de l'ACP et correspondent à différents cas de figure décrits ci-dessous

    Extensions à d'autres types de données

    ACP : données quantitatives, continues, a priori corrélées entre elles
    AFC : tableau de contingence (croisement de variables qualitatives)
    ACM : extension de AFC à plusieurs variables
    AFCM : Données qualitatives + quantitatives
    AFM : variables structurées en groupe
    AFMH : variables structurées en hiérarchie

    Extension non linéaire

    ACP à noyaux
    — Analyse Factorielle des Correspondances (AFC)
    Étude de la corrélation Cheveux - Yeux
    Profils-lignes $x^{'}_{ij}= \frac{x_{ij}}{x_{i.}}$ et profils-colonnes $x^{''}_{ij}= \frac{x_{ij}}{x_{.j}}$
    — Analyse Factorielle des Correspondances (AFC)
    — Analyse Factorielle des Correspondances (AFC)

    Objectif

    Analyser la liaison entre deux variables : la liaison entre deux variables est grande si les profils-lignes ou colonnes sont différents.
    • Quelles sont les lignes qui se ressemblent ? sont différentes ?
    • Existe-t-il des groupes homogènes entre les lignes ? entre les colonnes ?
    Principe général
    Une AFC est l'équivalent d'une ACP sur les profils-lignes ou profils colonnes :
    • Lignes et colonnes ont les mêmes rôles
    • Analyse de la distance entre profils
    • Inertie du nuage de points exprime l'indépendance entre les deux variables
    — Analyse Factorielle des Correspondances (AFC)
    — Analyse des Correspondances Multiples (ACM)
    Extension de l'AFC
    On peut étudier plusieurs variables
    Analyse des Correspondances Multiples (ACM)
    Une ACM est l'équivalent d'une AFC sur un tableau de Burt
    — Analyse des Correspondances Multiples (ACM)
    1. On a $p$ variables qualitatives (par exemple QCM)
      individu bac âge durée
      1 C $> 19$ 3
      2 D $m \lt 18$ 2
      ...
    2. Transformé en tableau de Burt ("Grand tableau de contingence")
    — Analyse des Correspondances Multiples (ACM)
    — ACP à noyaux
    Matrice de covariance
    Le point central est que l'ACP est basée sur l'analyse (décomposition en valeurs propres) de la matrice de variance dans l'espace des vraiables $$X_c^T X_c = \begin{pmatrix} v_1^T v_1 & \cdots & v_1^T v_p \\ & \ddots & \\ v_p^T v_1 & \cdots & v_p^T v_p \\ \end{pmatrix}$$ ... mais de manière équivalente de la matrice de variance dans l'espace des individus $$X_c X_c^T = \begin{pmatrix} x_1^T x_1 & \cdots & x_1^T x_n \\ & \ddots & \\ x_n^T x_1 & \cdots & x_n^T x_n \\ \end{pmatrix} $$ Il suffit donc de pouvoir définir le produit scalaire !
    — ACP à noyaux - exemples
    Données $X$
    Avec un noyau polynomial $$K(x,y) = (1 + \langle x, y \rangle)^d$$
    Avec un noyau Gaussien $$K(x,y) = \exp(- \frac{\langle x, y \rangle}{\sigma^2})$$
    Kernel PCA