Analyse de Composante principale (ACP) · 2017. 5. 9. · Sommaire 1 Motivation,donnéesetnotations 2 Projection,varianceetbases 3 Calculdel’ACP 4 InterprétationGéométrique 5

Analyse de Composante principale (ACP)Fouille de données avancées (2016-2017)

UFR MIME

Université Lille 3

7 décembre 2016

Lille 3 (M2 MIASHS WA) Analyse de Composante principale (ACP) 7 décembre 2016 1 / 22

Sommaire

1 Motivation, données et notations

2 Projection, variance et bases

3 Calcul de l’ACP

4 Interprétation Géométrique

5 TP

6 Conclusion


Motivation

Comment retrouver un système des coordonnées quiQui explique les sources principales de variations

En séparant dans des bases orthogonales (pour pouvoir analyser lescomposantes individuellement)Qui ordonnes des bases par rapport leur contributions pour expliquerles variations

pour un jeu de données multi-variées.Les enjeux :

Réduire des redondances et la dimensionnalité dans les variables avecla perte d’information minimale !Explorer les liaisons entre les variables


Données et analyse

d11

N

xi X

Var 1

Var 2Var K

Chaque rang d’une matrice X est un vecteur xi et un point dansl’espace Rd


Applications réelles

Analyse croisée : d-attributs et n-échantillions(Météorologie, biologie)Économie : d-valeur d’indicateur et n-périodes temporelles(mois/années etc)Génétique : d-gènes et n-humains (d >> n)Réduction de la dimensionnalité : d-pixel et n-imagesFinance : Retrouver les portfolios qui changent ensemble (trends)


Le problème

Comment retrouver les vecteurs vk ∈ Rd , sur lesquels les projectionsde tous les points (rangs) de X “maximise la variance” ? ou unsystème de coordonnées qui garde toute information ?Quel est le sens de la première composante principale (CP) ?

On peut définir la première CP comme une solution d’un problèmed’optimisation :

max‖v‖=1

var(ProjvX ) = max‖v‖=1var(XT v) (1)

Maintenant, si on veut calculer une famille de vecteurs sur laquelle on doitmaximiser les variances et en même temps capter les variances d’une façon“complementaire” :

argmaxVV T =Id

var(Projv∈V X ) = argmaxVV T =Id

var(XV ) (2)

Le critère VV T = Id exige que les bases vi soient orthogonales.Lille 3 (M2 MIASHS WA) Analyse de Composante principale (ACP) 7 décembre 2016 6 / 22

Exemple visuelle

les points en rouge sont des projections des points de départ (en bleu)Les lignes rouges sont les erreurs de reconstruction

ACP minimises les distances orthogonaux aux points pour retrouver lameilleure ligne.


Projection et Variance

La projection d’un vecteur x sur v est un vecteur c · v dans la mêmedirection que v celui qui est orthogonale à la résidus/différence(x− c · v).deux vecteurs a,b sont orthogonales si aT b = 0.

On peut du coup calculer la projection en sachant le scalaire c.

(x− c · v)T v = 0 =⇒ c = xT v

vT v (3)

Variance d’un vecteur x :

Variance est une mesure de déviation d’une suite des valeurs autourde leur moyenne.var(x) = 1N

∑Ni=1(x̄ − xi )2 ou x̄ = 1N

∑Ni=1 xi

si on soustrait la moyenne, on peut réécrire : 1N∑N

i=1(x2i )var(x) = XT X = [x1x2...xn] ∗ [x1x2...xn]T


BasesLes bases standard :12

3

= c1 ·100

+ c2 ·010

+ c3 ·001

c =

c1c2c3

=123

Dans la notation matricielle :12

3

=1 0 00 1 00 0 1

∗123

ou

x = B ∗ c (4)ou c sont des coordonnées.


Bases

Pour le problème de l’ACP, comment retrouver des bases vi dans lescolonnes d’une matrice V ∈ Rd ,r avec leurs nouvelles coordonnées c :x1x2

x3

= | | |v1 v2 v3| | |

∗c1c2

c3

ou

x = V ∗ c (5)

On est en train de chercher un changement des bases depuis l’espace dudépart Rd vers un nouvel espace avec :

VV T = Id les vecteurs soient orthogonales,Et la variance des projections soient maximale


Maximisation de la variance de projection

Le principe de l’ACP est de trouver un axe, issu d’une combinaison linéairedes vecteurs xi ∈ X , tel que la variance du nuage autour de cet axe soitmaximale.Pour la première composante principale :

max‖v‖=1

var(projvX )

on sait que Projba = aT b

bT b ,

max‖v‖=1

var(XT v)

et on sait que var(x) = XT X ,

max‖v‖=1

(XT v)T (XT v) = max‖v‖=1

vT XXT v = max‖v‖=1

vT Av

ou A = AT est la matrice de covariance.Lille 3 (M2 MIASHS WA) Analyse de Composante principale (ACP) 7 décembre 2016 11 / 22

Maximisation de variance de projection (inertie)

Quant on calcule la projection sur un ensemble des vecteurs orthogonalesdans les colonnes de matrice V , on peut réécrire le problèmed’optimisation comme :

argmaxV ∈Rd,r :V T V =Id

trace(V T AV ) (6)

ou la fonction trace() est la somme des entrées diagonales d’une matrice.Le problème d’optimisation est résolu analytiquement en cherchent lamaximum de cette fonction. La solution est donner par une décompositionen vecteurs/valeurs propres de A, car A est une matrice symétrique. Ilimplique aussi que les meilleurs bases seront les premier r ≤ d vecteurspropres.

XXT = A = VDV T

ou V a des colonnes orthogonales et D est une matrice diagonale avec lesentrées ordonnées.


Étapes de calcul

Centrer les données X par le moyennes de chaque variable (colonnes).Calculer la matrice de covariance A = 1N X

T X ∈ Rd ,d

Décomposer en vecteurs/valeurs propres de A = VDV T

Sélectionner les composantes principales en faisant des projectionsXV ∈ Rn,r et leur reconstructions XVV T ∈ Rn,d


Transformation des données (Pre-traitement)

Centrer les données (par soustraction de la valeur moyenne devariable). C’est une rotation des données dans l’espace Rd .Réduire les données si les unités de mesure sont différentes d’unevariable à l’autre

T (xi ) =xik − x̄k

sk(7)

si on ne réduit pas le nuage : une variable à forte variance va « tirer »tout l’effet de l’ACP à ellesi on réduit le nuage : une variable qui n’est qu’un bruit va seretrouver avec une variance apparente égale à une variableinformative.


Matrice de covariance

Pour une matrice d’entrée X sa matrice de covariance est une matrice quicontient des covariances pour chaque paire des variables i , j .

Σij = cov(Xi ,Xj) = E[(Xi − µi )(Xj − µj)] (8)

ou, µi = E(Xi ) est la moyenne à travers des échantillions pour la variable i .La diagonale de cette matrice contient des variances de chaque variable.


Centrage

Figure – Centrage par les moyennes.


Première composante

Figure – Meilleure ligne (Première direction principale) avec la moindre erreurde reconstruction.


Deuxième composante

Figure – la première composante (projections sur la première direction) et ladeuxième composante.


Deuxième composante

Figure – Première et deuxième composantes avec leurs projections.


Instructions : TP

Fonctions utiles :var() cov() cor() : pour calculer les variances, covariances etcorrélationsscale(x, center = TRUE, scale = TRUE) : Pour centrer et réduire lesdonnéesprcomp() : Pour calculer les composantes principales en Reigen() : Pour calculer la decomposition eigen en RSorties de prcomp() : sdev (les variances pour chaque composante),rotation (le matrice V avec les colonnes qui sont les vecteur propres),x (les projections de X sur V)summary() : summary(objetACP) vous rends une résume de ladécomposition en ACP effectuer.pairs() : Pour plotter les nuages des points entre chaque paires devariables


Instructions : TP

Taches :Calculer le matrice de covariance pour une entrée X .Calculer le ACP d’une matrice d’entrée par la fonction prcomp.Maintenant produire les résultats d’ACP en calculant la matrice decovariance et sa décomposition avec eigen et vérifier que vous avezproduit la même résultats que la fonction prcomp.


Conclusions

Le principe de l’ACP est de trouver un axe, issu d’une combinaisonlinéaire des xi , tel que la variance du nuage autour de cet axe soitmaximale. Ceci est appliquer itérativement sur la différence entre laprojection sur l’axe principale est données de départ. La solutionanalytique existe, et un des solution efficace est de calculer le SVD dematrice de covariance.Finalement, la question de l’ACP se ramène à un problème dediagonalisation de la matrice de covariance ou corrélation.La diagonalisation de la matrice de corrélation (ou de covariance si onse place dans un modèle non réduit), nous a permis d’écrire que levecteur qui explique le plus d’inertie du nuage est le premier vecteurpropre. De même le deuxième vecteur qui explique la plus grande partde l’inertie restante est le deuxième vecteur propre, etc.Proportion de variance expliquée par le k-ième vecteur propre vaut λk


Motivation, données et notationsProjection, variance et basesCalcul de l'ACPInterprétation GéométriqueTPConclusion

0.0: 0.1: 0.2: 0.3: 0.4: 0.5: 0.6: 0.7: 0.8: 0.9: 0.10: 0.11: 0.12: 0.13: 0.14: 0.15: 0.16: 0.17: 0.18: 0.19: 0.20: 0.21: 0.22: 0.23: 0.24: 0.25: 0.26: 0.27: 0.28: 0.29: 0.30: 0.31: 0.32: 0.33: 0.34: 0.35: 0.36: 0.37: 0.38: 0.39: 0.40: 0.41: 0.42: 0.43: 0.44: 0.45: 0.46: 0.47: 0.48: 0.49: 0.50: 0.51: 0.52: 0.53: 0.54: 0.55: 0.56: 0.57: 0.58: 0.59: 0.60: 0.61: 0.62: 0.63: 0.64: 0.65: 0.66: 0.67: 0.68: 0.69: 0.70: 0.71: 0.72: 0.73: 0.74: 0.75: 0.76: 0.77: 0.78: 0.79: 0.80: 0.81: 0.82: 0.83: 0.84: 0.85: 0.86: 0.87: 0.88: 0.89: 0.90: 0.91: 0.92: 0.93: 0.94: 0.95: 0.96: 0.97: 0.98: 0.99: 0.100: 0.101: 0.102: 0.103: 0.104: 0.105: 0.106: 0.107: 0.108: 0.109: 0.110: 0.111: 0.112: 0.113: 0.114: 0.115: 0.116: 0.117: 0.118: 0.119: 0.120: 0.121: 0.122: 0.123: 0.124: 0.125: 0.126: 0.127: 0.128: 0.129: 0.130: 0.131: 0.132: 0.133: 0.134: 0.135: 0.136: 0.137: 0.138: 0.139: 0.140: 0.141: 0.142: 0.143: 0.144: 0.145: 0.146: 0.147: 0.148: 0.149: 0.150: 0.151: 0.152: 0.153: 0.154: 0.155: 0.156: 0.157: 0.158: 0.159: 0.160: 0.161: 0.162: 0.163: 0.164: 0.165: 0.166: 0.167: 0.168: 0.169: 0.170: 0.171: 0.172: 0.173: 0.174: 0.175: 0.176: 0.177: 0.178: anm0:

Documents

Analyse de Composante principale (ACP) · 2017. 5. 9. · Sommaire 1 Motivation,donnéesetnotations 2 Projection,varianceetbases 3 Calculdel’ACP 4 InterprétationGéométrique 5