Quelle est l'explication intuitive de la façon dont l'ACP passe d'un problème géométrique (avec des distances) à un problème d'algèbre linéaire (avec des vecteurs propres)?

54

J'ai beaucoup lu sur la PCA, y compris divers tutoriels et questions (comme celle-ci , celle-ci , celle-ci et celle-ci ).

Le problème géométrique que PCA essaie d’optimiser m’est clair: PCA essaie de trouver le premier composant principal en minimisant l’erreur de reconstruction (projection), ce qui maximise simultanément la variance des données projetées.

entrez la description de l'image ici

Lorsque j'ai lu cela pour la première fois, j'ai immédiatement pensé à quelque chose comme une régression linéaire; vous pouvez peut-être résoudre le problème en utilisant une descente de pente si nécessaire.

Cependant, mon esprit a été stupéfait quand j'ai lu que le problème d'optimisation est résolu en utilisant l'algèbre linéaire et en recherchant des vecteurs propres et des valeurs propres. Je ne comprends tout simplement pas comment cet usage de l’algèbre linéaire entre en jeu.

Ma question est donc la suivante: comment l’ACP peut-elle passer d’un problème d’optimisation géométrique à un problème d’algèbre linéaire? Quelqu'un peut-il fournir une explication intuitive?

Je ne cherche pas une réponse comme celle-ci qui indique: "Lorsque vous résolvez le problème mathématique de l'ACP, cela revient à trouver les valeurs propres et les vecteurs propres de la matrice de covariance." Veuillez expliquer pourquoi les vecteurs propres sont les composantes principales et pourquoi les valeurs propres sont la variance des données projetées sur celles-ci.

Je suis un ingénieur en logiciel et pas un mathématicien, d'ailleurs.

Remarque: la figure ci-dessus a été prise et modifiée à partir de ce tutoriel de la PCA .

stackoverflowuser2010
la source
2
Dans le long fil derrière votre premier lien, il y a la réponse de @ amoeba avec animation, ce qui explique l'essentiel. PCA est la rotation des axes de données (colonnes) jusqu'à ce qu'ils soient décorrélés en tant que vecteurs de données (variables). Cette matrice de rotation est trouvée via une composition eigend ou une décomposition en valeurs singulières et est appelée matrice de vecteurs propres.
Heures
2
De plus, même si vous n'êtes pas mathématicien (je ne suis pas trop), vous avez probablement entendu parler de l'algèbre linéaire et la géométrie euclidienne sont des domaines intimement liés des mathématiques; ils sont même étudiés ensemble en tant que discipline appelée géométrie analytique.
ttnphns
1
optimization problemOui, je crois que le problème de la PCA pourrait être résolu via des approches d'optimisation (itératives, convergentes). Mais comme il a une solution de forme fermée via maths, pourquoi ne pas utiliser cette solution plus simple et efficace?
ttnphns
Vous demandez à provide an intuitive explanation. Je me demande pourquoi la réponse intuitive et claire de l'amibe, à laquelle je suis lié, ne vous convient pas. Vous demandez _why_ eigenvectors come out to be the principal components...pourquoi? Par définition! Les vecteurs propres sont les directions principales d'un nuage de données.
ttnphns
6
@ttnphns: Je pense en fait que la question est raisonnable. Voici comment je le comprends. PCA veut trouver la direction de la variance maximale de la projection. Cette direction est appelée (par définition) la première direction principale. D'autre part, un vecteur propre de la matrice de covariance est (par définition) un tel vecteur w que C w = λ w . Alors, pourquoi la première direction principale est-elle donnée par le vecteur propre ayant la plus grande valeur propre? Quelle est l'intuition ici? Ce n'est certainement pas par définition. J'y ai réfléchi et je sais comment le prouver, mais c'est difficile à expliquer de manière intuitive. CwCw=λw
amibe dit de réintégrer Monica

Réponses:

54

Déclaration du problème

Le problème géométrique que PCA essaie d’optimiser m’est clair: PCA essaie de trouver le premier composant principal en minimisant l’erreur de reconstruction (projection), ce qui maximise simultanément la variance des données projetées.

C'est vrai. J'explique le lien entre ces deux formulations dans ma réponse ici (sans math) ou ici (avec des maths).

Cww=1wCw

(Juste au cas où cela ne serait pas clair: si est la matrice de données centrée, alors la projection est donnée par et sa variance est .)XXw1n1(Xw)Xw=w(1n1XX)w=wCw

Par ailleurs, un vecteur propre de est, par définition, tout vecteur tel que .CvCv=λv

Il s'avère que la première direction principale est donnée par le vecteur propre ayant la plus grande valeur propre. C'est une déclaration non triviale et surprenante.


Preuves

Si l’on ouvre un livre ou un tutoriel sur la PCA, on peut y trouver la preuve suivante, presque une ligne, de la déclaration ci-dessus. Nous voulons maximiser sous la contrainte que ; cela peut être fait en introduisant un multiplicateur de Lagrange et en maximisant ; en différenciant, on obtient , qui est l’équation du vecteur propre. On voit que doit en fait être la plus grande valeur propre en substituant cette solution à la fonction objective, ce qui donnewCww=ww=1wCwλ(ww1)Cwλw=0λwCwλ(ww1)=wCw=λww=λλ . En raison du fait que cette fonction objectif doit être maximisée, doit être la plus grande valeur propre, QED.λ

Cela a tendance à ne pas être très intuitif pour la plupart des gens.

Une meilleure preuve (voir par exemple cette réponse soignée de @ cardinal ) dit que, puisque est une matrice symétrique, elle est diagonale dans sa base de vecteur propre. (Ceci est en fait appelé théorème spectral .) On peut donc choisir une base orthogonale, à savoir celle donnée par les vecteurs propres, où est diagonal et a des valeurs propres sur la diagonale. Dans cette base, simplifie en , ou en d'autres termes, la variance est donnée par la somme pondérée des valeurs propres. Il est presque immédiat que pour maximiser cette expression, il suffit de prendreCC wC w Σ λ i w 2 i w = ( 1 , 0 , 0 , ... , 0 ) λ 1 wC wCλiwCwλiwi2w=(1,0,0,,0), c’est-à-dire le premier vecteur propre, générant une variance (s’écarter de cette solution et "échanger" des parties de la plus grande valeur propre pour les parties de valeurs plus petites ne fera que réduire la variance globale). Notez que la valeur de ne dépend pas de la base! Passer à la base de vecteur propre équivaut à une rotation. En 2D, on peut donc imaginer simplement faire tourner un morceau de papier avec le diagramme de dispersion; évidemment cela ne peut changer aucun écart.λ1wCw

Je pense que cet argument est très intuitif et très utile, mais il repose sur le théorème spectral. Je pense donc que la vraie question est la suivante: quelle est l’intuition qui se cache derrière le théorème spectral?


Théorème spectral

Prenez une matrice symétrique . Prenons son vecteur propre avec la plus grande valeur propre . Faites de ce vecteur propre le premier vecteur de base et choisissez d'autres vecteurs de base de manière aléatoire (de sorte qu'ils soient tous orthonormés). À quoi ressemblera dans cette base?Cw1λ1C

Il aura dans le coin supérieur gauche, parce que dans cette base et doit être égal à .λ1w1=(1,0,00)Cw1=(C11,C21,Cp1)λ1w1=(λ1,0,00)

Par le même argument, il y aura des zéros dans la première colonne sous le .λ1

Mais comme il est symétrique, il aura aussi des zéros dans la première ligne après . Donc ça va ressembler à ça:λ1

C=(λ10000),

où espace vide signifie qu'il y a un bloc d'éléments. Parce que la matrice est symétrique, ce bloc sera également symétrique. Nous pouvons donc lui appliquer exactement le même argument, en utilisant efficacement le deuxième vecteur propre en tant que deuxième vecteur de base, et en obtenant et sur la diagonale. Cela peut continuer jusqu'à ce que soit diagonal. C'est essentiellement le théorème spectral. (Notez comment cela fonctionne uniquement parce que est symétrique.)λ1λ2CC


Voici une reformulation plus abstraite du même argument.

Nous savons que , le premier vecteur propre définit donc un sous-espace à une dimension dans lequel agit comme une multiplication scalaire. Prenons maintenant tout vecteur orthogonal à . Ensuite, il est presque immédiat que soit également orthogonal à . En effet:Cw1=λ1w1Cvw1Cvw1

w1Cv=(w1Cv)=vCw1=vCw1=λ1vw1=λ10=0.

Cela signifie que agit sur tout le sous-espace restant orthogonal à sorte qu'il reste séparé de . C'est la propriété cruciale des matrices symétriques. Ainsi, nous pouvons y trouver le plus grand vecteur propre, , et procéder de la même manière, en construisant finalement une base orthonormée de vecteurs propres.Cw1w1w2

l'amibe dit de réintégrer Monica
la source
"Multiplicateur de Lagrange" est vraiment clair pour moi. Cependant, pourriez-vous me dire pourquoi nous avons besoin d'une contrainte de longueur d'unité? Merci
Haitao Du
2
@ hxd1011 Il y a déjà exactement cette question ici, mais brièvement: c'est parce que sinon vous pouvez multiplier par n'importe quel nombre et augmentera du carré de ce nombre. Le problème devient alors mal défini: le maximum de cette expression est infini. En fait, la variance de la projection sur la direction de est que si est l'unité de longueur. wwCwwwCww
amibe dit de réintégrer Monica
Je suppose que pourrait être un peu plus familier à la plupart des lecteurs; Je l'ai remplacé ici. Merci. n1
amibe dit de réintégrer Monica
@ amoeba: Merci pour la réponse. Je suis dérouté par certaines de vos notes. Vous utilisez w pour indiquer le vecteur de longueur unitaire qui se révèle être le premier vecteur propre (composante principale). Lorsque je lance PCA dans R (par exemple prcomp(iris[,1:4], center=T, scale=T)), je vois des vecteurs propres de longueur unité avec un groupe de flotteurs comme (0.521, -0.269, 0.580, 0.564). Cependant, dans votre réponse sous "Preuves", vous écrivez Il est presque immédiat que pour maximiser cette expression, il suffit de prendre w = (1,0,0,…, 0), c’est-à-dire le premier vecteur propre . Pourquoi le vecteur propre de votre preuve a-t-il l'air si bien formé?
stackoverflowuser2010
1
Bonjour @ user58865, merci pour le coup de pouce: j'ai tout simplement oublié de répondre pour la première fois. Le mince est, est un scalaire - c'est juste un nombre. Tout nombre est "symétrique" :) et est égal à sa transposition. Est-ce que ça fait du sens? w1Cv
Amibe dit de réintégrer Monica
5

Eckart et Young ont publié un résultat datant de 1936 ( https://ccrma.stanford.edu/~dattorro/eckart%26young.1936.pdf ), qui indique ce qui suit:

1rdkukvkT=argminX^ϵM(r)||XX^||F2

où M (r) est l'ensemble des matrices de rang-r, ce qui signifie fondamentalement que les premières composantes de la SVD de X donnent la meilleure approximation de X sur la matrice de bas rang et que le meilleur est défini en termes de la norme de Frobenius au carré - la somme du carré éléments d'une matrice.

Il s’agit d’un résultat général pour les matrices et, à première vue, n’a rien à voir avec les ensembles de données ou la réduction de la dimensionnalité.

Cependant, si vous ne pensez pas à tant que matrice mais aux colonnes de la matrice représentant des vecteurs de points de données, est l'approximation avec l'erreur de représentation minimale en termes de différences d'erreur au carré.XXX^

Cagdas Ozgenc
la source
4

Ceci est mon point de vue sur l'algèbre linéaire derrière PCA. En algèbre linéaire, l'un des théorèmes clés est le . Si S est une matrice symétrique n par n avec des coefficients réels, S a n vecteurs propres, toutes les valeurs propres étant réelles. Cela signifie que nous pouvons écrire avec D une matrice diagonale avec des entrées positives. C'est et il n'y a aucun mal à supposer que . A est la matrice de changement de base. C'est-à-dire que si notre base d'origine était , alors par rapport à la base donnée parSpectral TheoremS=ADA1D=diag(λ1,λ2,,λn)λ1λ2λnx1,x2,,xnA(x1),A(x2),A(xn), l'action de S est diagonale. Cela signifie également que le peut être considéré comme une base orthogonale avec Si notre matrice de covariance était pour n observations de n variables, nous aurions terminé. La base fournie par est la base de la PCA. Cela découle des faits de l'algèbre linéaire. En substance, il est vrai qu’une base PCA est une base de vecteurs propres et qu’il existe au plus n vecteurs propres d’une matrice carrée de taille n. Bien sûr, la plupart des matrices de données ne sont pas carrées. Si X est une matrice de données avec n observations de p variables, alors X est de taille n par p. Je supposerai que (plus d'observations que de variables) et queA(xi)||A(xi)||=λiA(xi)
n>prk(X)=p(toutes les variables sont linéairement indépendantes). Aucune hypothèse n'est nécessaire, mais cela aidera avec l'intuition. L'algèbre linéaire a une généralisation du théorème spectral appelée décomposition en valeurs singulières. Pour un tel X, il est indiqué que avec U, V matrices orthonormales (carrées) de taille n et p et une matrice diagonale réelle avec uniquement des valeurs non négatives. entrées sur la diagonale. De nouveau, nous pouvons réorganiser la base de V pour que en termes de matrice, cela signifie que si et si . LeX=UΣVtΣ=(sij)s11s22spp>0 i p s i i = 0 i > n v i Σ V tX(vi)=siiuiipsii=0i>nvidonner la décomposition PCA. Plus précisément est la décomposition PCA. Pourquoi? Encore une fois, l'algèbre linéaire dit qu'il ne peut y avoir que des vecteurs propres. La SVD donne de nouvelles variables (données par les colonnes de V) qui sont orthogonales et ont une norme décroissante. ΣVt

Aginensky
la source
4

"qui maximise simultanément la variance des données projetées." Avez-vous entendu parler du quotient de Rayleigh ? Peut-être que c'est une façon de voir cela. À savoir le quotient de Rayleigh de la matrice de covariance vous donne la variance des données projetées. (et la page wiki explique pourquoi les vecteurs propres maximisent le quotient de Rayleigh)

seanv507
la source
1

@amoeba donne une formalisation soignée et une preuve de:

Nous pouvons le formaliser comme suit: étant donné la matrice de covariance C, nous cherchons un vecteur w de longueur unitaire, w‖ = 1, tel que w T Cw soit maximal.

Mais je pense qu’il existe une preuve intuitive pour:

Il s'avère que la première direction principale est donnée par le vecteur propre ayant la plus grande valeur propre. C'est une déclaration non triviale et surprenante.

On peut interpréter w T Cw comme un produit scalaire entre le vecteur w et Cw, obtenu en passant par la transformation C:

w T Cw = ‖w‖ * Cw‖ * cos (w, Cw)

Puisque w a une longueur fixe, pour maximiser w T Cw, il faut:

  1. maximiser ‖Cw‖
  2. maximiser cos (w, Cw)

Il s'avère que si nous prenons w comme vecteur propre de C avec la plus grande valeur propre, nous pouvons archiver les deux simultanément:

  1. ‖Cw‖ est max (si w dévie de ce vecteur propre, décomposez-le le long de vecteurs propres orthogonaux, vous devriez voir une diminution de ‖Cw‖.)
  2. w et Cw dans la même direction, cos (w, Cw) = 1, max

Puisque les vecteurs propres sont orthogonaux, ils forment avec les autres vecteurs propres de C un ensemble de composantes principales de X.


preuve de 1

décomposite w en vecteur propre orthogonal primaire et secondaire v1 et v2 , supposons que leur longueur est respectivement v1 et v2. nous voulons prouver

1 w) 2 > ((λ 1 v1) 2 + (λ 2 v2) 2 )

depuis λ 1 > λ 2 , on a

((λ 1 v1) 2 + (λ 2 v2) 2 )

<((λ 1 v1) 2 + (λ 1 v2) 2 )

= (λ 1 ) 2 * (v1 2 + v2 2 )

= (λ 1 ) 2 * w 2

Ciel
la source