Relation entre SVD et PCA. Comment utiliser SVD pour effectuer une PCA?

L'analyse en composantes principales (ACP) est généralement expliquée via une décomposition propre de la matrice de covariance. Toutefois, cela peut également être effectué via une décomposition en valeurs singulières (SVD) de la matrice de données$\mathbf X$ . Comment ça marche? Quel est le lien entre ces deux approches? Quelle est la relation entre SVD et PCA?

Ou, en d'autres termes, comment utiliser la SVD de la matrice de données pour effectuer une réduction de dimensionnalité?

Supposons que la matrice de données soit de taille , où représente le nombre d'échantillons et le nombre de variables. Supposons qu'il soit centré , c'est-à-dire que les moyennes des colonnes ont été soustraites et sont maintenant égales à zéro. n × p n $\mathbf X$$n \times p$$n$$p$

Alors la matrice de covariance est donnée par . C'est une matrice symétrique et elle peut donc être diagonalisée: où est une matrice de vecteurs propres (chaque colonne est un vecteur propre) et est une matrice diagonale avec des valeurs propres dans l'ordre décroissant sur la diagonale. Les vecteurs propres sont appelés axes principaux ou directions principales des données. Les projections des données sur les axes principaux sont appelées composantes principales , également appelées scores PC.C C = X ⊤ X / ( n - 1 ) C = V L V ⊤ , V L λ i j j X V i i X $p \times p$$\mathbf C$$\mathbf C = \mathbf X^\top \mathbf X/(n-1)$

$$\mathbf C = \mathbf V \mathbf L \mathbf V^\top,$$ $\mathbf V$$\mathbf L$$\lambda_i$; celles-ci peuvent être considérées comme de nouvelles variables transformées. La ième composante principale est donnée par la ième colonne de . Les coordonnées du ième point de données dans le nouvel espace PC sont données par la ième ligne de .$j$$j$$\mathbf {XV}$$i$$i$$\mathbf{XV}$

Si nous effectuons maintenant une décomposition en valeurs singulières de , nous obtenons une décomposition où est une matrice unitaire et est la matrice diagonale de valeurs singulières . A partir de là, on peut facilement voir que ce qui signifie que les vecteurs singuliers droits sont les directions principales et que les valeurs singulières sont liées aux valeurs propres de la matrice de covariance viaX = U S V ⊤ , $\mathbf X$

$$\mathbf X = \mathbf U \mathbf S \mathbf V^\top,$$ $\mathbf U$s i C = V S U ⊤ U S V ⊤ / ( n - 1 ) = V S$\mathbf S$$s_i$Vλi $$\mathbf C = \mathbf V \mathbf S \mathbf U^\top \mathbf U \mathbf S \mathbf V^\top /(n-1) = \mathbf V \frac{\mathbf S^2}{n-1}\mathbf V^\top,$$ $\mathbf V$X V = U S V ⊤ V = U $\lambda_i = s_i^2/(n-1)$ . Les composantes principales sont données par$\mathbf X \mathbf V = \mathbf U \mathbf S \mathbf V^\top \mathbf V = \mathbf U \mathbf S$ .

Résumer:

1. Si , les colonnes de sont des directions / axes principaux.$\mathbf X = \mathbf U \mathbf S \mathbf V^\top$$\mathbf V$
2. Les colonnes de sont des composantes principales ("scores").$\mathbf {US}$
3. Les valeurs singulières sont liées aux valeurs propres de la matrice de covariance via . Les valeurs propres montrent les variances des PC respectifs.$\lambda_i = s_i^2/(n-1)$$\lambda_i$
4. Les scores standardisés sont donnés par les colonnes de et les chargements par les colonnes de . Voir par exemple ici et ici pour savoir pourquoi les "charges" ne doivent pas être confondues avec les directions principales.$\sqrt{n-1}\mathbf U$$\mathbf V \mathbf S/\sqrt{n-1}$
5. Ce qui précède n'est correct que si est centré. $\mathbf X$Alors seulement, la matrice de covariance est-elle égale à .$\mathbf X^\top \mathbf X/(n-1)$
6. Ce qui précède n’est correct que pour ayant des échantillons en lignes et des variables en colonnes. Si les variables sont dans les lignes et les échantillons dans les colonnes, alors et échangent leurs interprétations.$\mathbf X$$\mathbf U$$\mathbf V$
7. Si l'on veut effectuer une ACP sur une matrice de corrélation (au lieu d'une matrice de covariance), alors les colonnes de doivent non seulement être centrées, mais également normalisées, c'est-à-dire divisées par leurs écarts types.$\mathbf X$
8. Afin de réduire les dimensions des données à partir de à , sélectionner premières colonnes de , et la partie supérieure gauche de . Leur produit est la matrice requise contenant les premiers PC.k < $p$$k<p$$k$$\mathbf U$$k\times k$$\mathbf S$$\mathbf U_k \mathbf S_k$$n \times k$$k$
9. En outre multiplier les premiers ordinateurs par les axes principaux correspondant rendements matrice qui a l'original taille mais est de rang inférieur (de rang ). Cette matrice fournit une reconstruction des données originales des premiers PC. C'est l'erreur de reconstruction la plus faible possible, voir ma réponse ici .V ⊤ k X k = U ⊤ k S ⊤$k$$\mathbf V_k^\top$$\mathbf X_k = \mathbf U_k^\vphantom \top \mathbf S_k^\vphantom \top \mathbf V_k^\top$$n \times p$$k$$\mathbf X_k$$k$
10. A proprement parler, est de taille et de taille . Cependant, si alors les dernières colonnes de sont arbitraires (et les lignes correspondantes de sont égales à zéro); il faut donc utiliser un SVD de taille économique (ou mince ) qui retourne de size, en supprimant les colonnes inutiles. Pour large, la matrice serait sinon inutilement énorme. Il en va de même pour une situation opposée de$\mathbf U$$n\times n$$\mathbf V$$p \times p$$n>p$$n-p$$\mathbf U$$\mathbf S$$\mathbf U$$n\times p$$n\gg p$$\mathbf U$$n\ll p$.

---

Autres liens

• Quelle est la relation intuitive entre SVD et PCA - un fil très populaire et très similaire sur math.SE.

• Pourquoi PCA de données au moyen de SVD des données? - une discussion sur les avantages de réaliser une PCA via SVD [réponse courte: stabilité numérique].

• PCA et Analyse de correspondance dans leur relation avec Biplot - PCA dans le contexte de certaines techniques congénériques , toutes basées sur la SVD.

• La SVD présente-t-elle un avantage par rapport à la PCA? - une question demandant s'il y avait des avantages à utiliser SVD au lieu de PCA [réponse courte: question mal posée].

• Donner un sens à l'analyse en composantes principales, aux vecteurs propres et aux valeurs propres - ma réponse donne une explication non technique de l'ACP. Pour attirer l'attention, je reproduis une figure ici:

J'ai écrit un extrait de Python & Numpy qui accompagne la réponse de @ amoeba et je le laisse ici au cas où il serait utile à quelqu'un. Les commentaires sont principalement tirés de la réponse de @ amoeba.

import numpy as np
from numpy import linalg as la
np.random.seed(42)


def flip_signs(A, B):
    """
    utility function for resolving the sign ambiguity in SVD
    http://stats.stackexchange.com/q/34396/115202
    """
    signs = np.sign(A) * np.sign(B)
    return A, B * signs


# Let the data matrix X be of n x p size,
# where n is the number of samples and p is the number of variables
n, p = 5, 3
X = np.random.rand(n, p)
# Let us assume that it is centered
X -= np.mean(X, axis=0)

# the p x p covariance matrix
C = np.cov(X, rowvar=False)
print "C = \n", C
# C is a symmetric matrix and so it can be diagonalized:
l, principal_axes = la.eig(C)
# sort results wrt. eigenvalues
idx = l.argsort()[::-1]
l, principal_axes = l[idx], principal_axes[:, idx]
# the eigenvalues in decreasing order
print "l = \n", l
# a matrix of eigenvectors (each column is an eigenvector)
print "V = \n", principal_axes
# projections of X on the principal axes are called principal components
principal_components = X.dot(principal_axes)
print "Y = \n", principal_components

# we now perform singular value decomposition of X
# "economy size" (or "thin") SVD
U, s, Vt = la.svd(X, full_matrices=False)
V = Vt.T
S = np.diag(s)

# 1) then columns of V are principal directions/axes.
assert np.allclose(*flip_signs(V, principal_axes))

# 2) columns of US are principal components
assert np.allclose(*flip_signs(U.dot(S), principal_components))

# 3) singular values are related to the eigenvalues of covariance matrix
assert np.allclose((s ** 2) / (n - 1), l)

# 8) dimensionality reduction
k = 2
PC_k = principal_components[:, 0:k]
US_k = U[:, 0:k].dot(S[0:k, 0:k])
assert np.allclose(*flip_signs(PC_k, US_k))

# 10) we used "economy size" (or "thin") SVD
assert U.shape == (n, p)
assert S.shape == (p, p)
assert V.shape == (p, p)

Permettez-moi de commencer par PCA. Supposons que vous avez n points de données composés de d nombres (ou dimensions) chacun. Si vous centrez ces données (soustrayez le point de données moyen de chaque vecteur de données ), vous pouvez empiler les données pour créer une matrice.$\mu$$x_i$

$$X = \left( \begin{array}{ccccc} && x_1^T - \mu^T && \\ \hline && x_2^T - \mu^T && \\ \hline && \vdots && \\ \hline && x_n^T - \mu^T && \end{array} \right)\,.$$

La matrice de covariance

$$S = \frac{1}{n-1} \sum_{i=1}^n (x_i-\mu)(x_i-\mu)^T = \frac{1}{n-1} X^T X$$

mesures dans quelle mesure les différentes coordonnées dans lesquelles vos données sont données varient ensemble. Il n’est donc peut-être pas surprenant que l’ACP - conçue pour capturer la variation de vos données - puisse être donnée en termes de matrice de covariance. En particulier, la décomposition en valeurs propres de s’avère être$S$

$$S = V \Lambda V^T = \sum_{i = 1}^r \lambda_i v_i v_i^T \,,$$

où est la ième composante principale , ou PC, et est la ième valeur propre de et est égale à la variance des données le long du ième PC. Cette décomposition découle d'un théorème général en algèbre linéaire, et un travail doit être effectué pour motiver le relatino à l'APC.$v_i$$i$$\lambda_i$$i$$S$$i$

SVD est un moyen général de comprendre une matrice en termes d’espace colonne et rangée. (C'est un moyen de réécrire n'importe quelle matrice en termes d'autres matrices avec une relation intuitive à l'espace des lignes et des colonnes.) Par exemple, pour la matrice nous pouvons trouver les directions et dans le domaine et la plage$A = \left( \begin{array}{cc}1&2\\0&1\end{array} \right)$$u_i$$v_i$

Vous pouvez les trouver en considérant comment tant que transformation linéaire, transforme une sphère unité dans son domaine en une ellipse: les demi-axes principaux de l'ellipse alignés sur le et le sont leurs pré-images.$A$$\mathbb S$$u_i$$v_i$

Dans tous les cas, pour la matrice de données ci-dessus (en réalité, définissez simplement ), SVD nous permet d’écrire$X$$A = X$

$$X = \sum_{i=1}^r \sigma_i u_i v_j^T\,,$$

où et sont des ensembles de vecteurs orthonormés.Une comparaison avec la décomposition en valeurs propres de révèle que les "vecteurs singuliers droits" sont égaux aux PC, les "vecteurs singuliers droits" sont{ v i } S v $\{ u_i \}$$\{ v_i \}$$S$$v_i$

$$u_i = \frac{1}{\sqrt{(n-1)\lambda_i}} Xv_i\,,$$

et les "valeurs singulières" sont liées à la matrice de données via$\sigma_i$

$$\sigma_i^2 = (n-1) \lambda_i\,.$$

Il est un fait général que les vecteurs singuliers couvrent l'espace des colonnes de . Dans ce cas particulier, nous donne une projection échelonnée des données sur la direction de la ième composante principale. Les vecteurs singuliers de gauche couvrent en général l’espace de rangée de , ce qui nous donne un ensemble de vecteurs orthonormés qui recouvrent les données de la même manière que les ordinateurs personnels. x u i x i v i$u_i$$X$$u_i$$X$$i$$v_i$$X$

Je vais dans quelques détails plus et avantages de la relation entre PCA et SVD dans cet article plus long .