Beziehung zwischen SVD und PCA. Wie verwende ich SVD, um PCA durchzuführen?

352

Die Hauptkomponentenanalyse (PCA) wird üblicherweise durch eine Eigenzerlegung der Kovarianzmatrix erklärt. Sie kann aber auch über die Singular Value Decomposition (SVD) der Datenmatrix . Wie funktioniert es? Welche Verbindung besteht zwischen diesen beiden Ansätzen? Wie ist die Beziehung zwischen SVD und PCA? $\mathbf X$

Oder mit anderen Worten, wie kann die SVD der Datenmatrix verwendet werden, um eine Dimensionsreduktion durchzuführen?

pca dimensionality-reduction matrix svd Amöbe
quelle

Ich habe diese Frage im FAQ-Stil zusammen mit meiner eigenen Antwort geschrieben, da sie häufig in verschiedenen Formen gestellt wird, es aber keinen kanonischen Thread gibt und es daher schwierig ist, Duplikate zu schließen. Bitte geben Sie Metakommentare in diesem begleitenden Meta-Thread an .

Amöbe

stats.stackexchange.com/questions/177102/…

kjetil b halvorsen

Zusätzlich zu einer ausgezeichneten und detaillierten Antwort von Amoeba mit ihren weiteren Links kann ich empfehlen, dies zu überprüfen , wobei PCA als Seite an Seite mit einigen anderen SVD-basierten Techniken betrachtet wird. In der dortigen Diskussion wird die Algebra fast identisch mit der Amöbe dargestellt, mit dem kleinen Unterschied, dass in der dortigen Rede zur Beschreibung der PCA die DVD-Zerlegung von [oder ] behandelt wird. statt - was einfach praktisch ist, da es sich um die PCA handelt, die über die Neuzusammenstellung der Kovarianzmatrix erfolgt.

X / \sqrt{n}

$\mathbf X/\sqrt{n}$

X / \sqrt{n - 1}

$\mathbf X/\sqrt{n-1}$

X

$\bf X$

TTNPHNS

PCA ist ein Sonderfall der SVD. PCA benötigt die Daten normalisiert, idealerweise dieselbe Einheit. Die Matrix ist in PCA nxn.

Orvar Korvar

@OrvarKorvar: Über welche nxn Matrix sprichst du?

Cbhihe

Antworten:

412

Die Datenmatrix sei groß, wobei die Anzahl der Abtastwerte und die Anzahl der Variablen ist. Nehmen wir an, es ist zentriert , dh die Spaltenmittel wurden abgezogen und sind jetzt gleich Null. $\mathbf X$ $n \times p$ $n$ $p$

Dann ist die Kovarianzmatrix gegeben durch . Es ist eine symmetrische Matrix und kann daher diagonalisiert werden: wobei eine Matrix von Eigenvektoren ist (jede Spalte ist ein Eigenvektor) und ist eine Diagonalmatrix mit Eigenwerten in absteigender Reihenfolge auf der Diagonale. Die Eigenvektoren werden als Hauptachsen oder Hauptrichtungen der Daten bezeichnet. Projektionen der Daten auf den Hauptachsen werden als Hauptkomponenten bezeichnet , die auch als PC-Scores bezeichnet werden $p \times p$ $\mathbf C$ $\mathbf C = \mathbf X^\top \mathbf X/(n-1)$

C = V L V^{⊤},

$\mathbf C = \mathbf V \mathbf L \mathbf V^\top,$

V

$\mathbf V$

L

$\mathbf L$

λ_{i}

$\lambda_i$ ; Diese können als neue, transformierte Variablen angesehen werden. Die te Hauptkomponente ist durch die te Spalte von . Die Koordinaten des ten Datenpunktes im neuen PC-Raum sind durch die te Zeile von .

j

$j$

j

$j$

X V

$\mathbf {XV}$

i

$i$

i

$i$

X V

$\mathbf{XV}$

Wenn wir nun eine Singularwertzerlegung von , erhalten wir eine Zerlegung von wobei eine Einheitsmatrix und die Diagonalmatrix von ist singuläre Werte . Von hier aus kann man leicht sehen, dass was bedeutet, dass rechte Singularvektoren Hauptrichtungen sind und dass Singularwerte mit den Eigenwerten der Kovarianzmatrix über . Hauptbestandteile sind gegeben durch $\mathbf X$

X = U S V^{⊤},

$\mathbf X = \mathbf U \mathbf S \mathbf V^\top,$

U

$\mathbf U$

S

$\mathbf S$

s_{i}

$s_i$

C = V S U^{⊤} U S V^{⊤} / (n - 1) = V \frac{S^{2}}{n - 1} V^{⊤},

$\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,$

V

$\mathbf V$

λ_{i} = s_{i}^{2} / (n - 1)

$\lambda_i = s_i^2/(n-1)$

X V = U S V^{⊤} V = U S

$\mathbf X \mathbf V = \mathbf U \mathbf S \mathbf V^\top \mathbf V = \mathbf U \mathbf S$ .

Zusammenfassen:

Wenn , dann sind die Spalten von Hauptrichtungen / -achsen. $\mathbf X = \mathbf U \mathbf S \mathbf V^\top$ $\mathbf V$
Spalten von sind Hauptbestandteile ("Scores"). $\mathbf {US}$
Singularwerte werden über mit den Eigenwerten der Kovarianzmatrix in Beziehung gesetzt . Eigenwerte zeigen Abweichungen der jeweiligen PCs an. $\lambda_i = s_i^2/(n-1)$ $\lambda_i$
Standardisierte Ergebnisse werden durch Spalten mit und Ladungen durch Spalten mit . Sehen Sie zB hier und hier, warum "Ladungen" nicht mit Hauptrichtungen verwechselt werden sollten. $\sqrt{n-1}\mathbf U$ $\mathbf V \mathbf S/\sqrt{n-1}$
Das obige ist nur korrekt, wenn zentriert ist. $\mathbf X$ Nur dann ist die Kovarianzmatrix gleich . $\mathbf X^\top \mathbf X/(n-1)$
Das Obige gilt nur für mit Stichproben in Zeilen und Variablen in Spalten. Befinden sich Variablen in Zeilen und Samples in Spalten, tauschen und Interpretationen aus. $\mathbf X$ $\mathbf U$ $\mathbf V$
Wenn man PCA auf einer Korrelationsmatrix (anstelle einer Kovarianzmatrix) durchführen möchte, sollten Spalten von nicht nur zentriert, sondern auch standardisiert, dh durch ihre Standardabweichungen dividiert werden. $\mathbf X$
Um die Dimensionalität der Daten von auf zu verringern , wählen Sie erste Spalten von und oberer linker Teil von . Ihr Produkt ist die erforderliche Matrix, die die ersten PCs enthält. $p$ $k<p$ $k$ $\mathbf U$ $k\times k$ $\mathbf S$ $\mathbf U_k \mathbf S_k$ $n \times k$ $k$
Weiteres Multiplizieren der ersten PCs mit den entsprechenden Hauptachsen ergibt Matrix mit dem ursprünglichen size ist aber von niedrigerem Rang (von Rang ). Diese Matrix liefert eine Rekonstruktion der Originaldaten von den ersten PCs. Es hat den geringstmöglichen Rekonstruktionsfehler, siehe meine Antwort hier . $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$
Streng genommen ist von Größe und ist von Größe. Wenn jedoch dann sind die letzten Spalten von beliebig (und die entsprechenden Zeilen von sind konstant Null); man sollte daher eine SVD mit Economy-Größe (oder Thin- Größe ) verwenden, die der Größe zurückgibt und die nutzlosen Spalten löscht. Für großes die Matrix sonst unnötig groß. Gleiches gilt für eine gegenteilige Situation von $\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$ .

Weiterführende Links

Was ist die intuitive Beziehung zwischen SVD und PCA - ein sehr beliebter und sehr ähnlicher Thread zu math.SE.
Warum PCA von Daten mittels SVD der Daten? - eine Diskussion über die Vorteile der Durchführung von PCA mittels SVD [kurze Antwort: numerische Stabilität].
PCA - und Korrespondenzanalyse in ihrer Beziehung zu Biplot - PCA im Kontext einiger allgemeiner Techniken, die alle auf SVD basieren.
Gibt es einen Vorteil von SVD gegenüber PCA? - eine Frage, in der gefragt wird, ob die Verwendung von SVD anstelle von PCA Vorteile bringt [kurze Antwort: schlecht gestellte Frage].
Die Analyse von Hauptkomponenten, Eigenvektoren und Eigenwerten verstehen - meine Antwort mit einer nicht-technischen Erklärung der PCA. Um die Aufmerksamkeit auf sich zu ziehen, reproduziere ich hier eine Figur:

Amöbe
quelle

@Antoine, Kovarianzmatrix ist per Definition gleich , wobei spitze Klammern den Durchschnittswert bezeichnen . Wenn alle als Zeilen in einer Matrix gestapelt sind , ist dieser Ausdruck gleich . Wenn zentriert ist, vereinfacht sich dies zu . Denken Sie an Varianz; es ist gleich . Aber wenn (dh die Daten sind zentriert), dann ist es einfach der Durchschnittswert von .

⟨ (x_{i} - \bar{x}) (x_{i} - \bar{x})^{⊤} ⟩

$\langle (\mathbf x_i - \bar{\mathbf x})(\mathbf x_i - \bar{\mathbf x})^\top \rangle$

x_{i}

$\mathbf x_i$

X

$\mathbf X$

(X - \bar{X}) (X - \bar{X})^{⊤} / (n - 1)

$(\mathbf X - \bar{\mathbf X})(\mathbf X - \bar{\mathbf X})^\top/(n-1)$

X

$\mathbf X$

X X^{⊤} / (n - 1)

$\mathbf X \mathbf X^\top/(n-1)$

⟨ (x_{i} - \bar{x})^{2} ⟩

$\langle (x_i-\bar x)^2 \rangle$

\bar{x} = 0

$\bar x=0$

x_{i}^{2}

$x_i^2$

Amöbe

Ein Codebeispiel für PCA von SVD: stackoverflow.com/questions/3181593/…

Optimist

Amoeba, ich habe die Verantwortung übernommen, einen weiteren Link gemäß den von Ihnen angegebenen Links hinzuzufügen. Ich hoffe, Sie finden es angemessen.

TTNPHNS

@amoeba ja, aber warum es benutzen? Ist es auch möglich, den gleichen Nenner für ? Das Problem ist, dass ich Formeln mit sehe und versuche zu verstehen, wie ich sie verwende.

S

$S$

λ_{i} = s_{i}^{2}

$\lambda_i = s_i^2$

Dims

@sera Vertausche einfach deine Matrix und befreie dich von deinem Problem. Sie werden sonst nur verwirrt.

Amöbe

Ich habe ein Python & Numpy-Snippet geschrieben, das die Antwort von @ amoeba begleitet, und ich lasse es hier, falls es für jemanden nützlich ist. Die Kommentare stammen größtenteils aus der Antwort von @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)

user115202
quelle

Lassen Sie mich mit PCA beginnen. Angenommen, Sie haben n Datenpunkte, die jeweils aus d Zahlen (oder Dimensionen) bestehen. Wenn Sie diese Daten zentrieren (subtrahieren Sie den mittleren Datenpunkt von jedem Datenvektor ), können Sie die Daten stapeln, um eine Matrix zu erstellen $\mu$ $x_i$

X = (\begin{array}{ccccc} x_{1}^{T} - μ^{T} \\ x_{2}^{T} - μ^{T} \\ ⋮ \\ x_{n}^{T} - μ^{T} \end{array}) .

$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)\,.$

Die Kovarianzmatrix

S = \frac{1}{n - 1} \sum_{i = 1}^{n} (x_{i} - μ) (x_{i} - μ)^{T} = \frac{1}{n - 1} X^{T} X

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

misst, in welchem Maße die verschiedenen Koordinaten, in denen Ihre Daten angegeben sind, voneinander abweichen. Daher ist es vielleicht nicht verwunderlich, dass PCA - mit dem die Variation Ihrer Daten erfasst werden soll - in Form der Kovarianzmatrix angegeben werden kann. Insbesondere stellt sich die Eigenwertzerlegung von als heraus $S$

S = V Λ V^{T} = \sum_{i = 1}^{r} λ_{i} v_{i} v_{i}^{T},

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

wobei die te Hauptkomponente oder PC ist und der te Eigenwert von und auch gleich der Varianz der Daten entlang des ten PC ist. Diese Zersetzung kommt aus einem allgemeinen Satz in der linearen Algebra, und einige Arbeit nicht getan werden , haben die relatino zu PCA zu motivieren. $v_i$ $i$ $\lambda_i$ $i$ $S$ $i$

PCA eines zufällig generierten Gaußschen Datensatzes

SVD ist eine allgemeine Methode, um eine Matrix in Bezug auf ihren Spalten- und Zeilenraum zu verstehen. (Es ist eine Möglichkeit, eine Matrix in Bezug auf andere Matrizen mit einer intuitiven Beziehung zum Zeilen- und Spaltenraum neu zu schreiben.) Zum Beispiel für die Matrix Wir können die Richtungen und in der Domäne und im Bereich finden, so dass $A = \left( \begin{array}{cc}1&2\\0&1\end{array} \right)$ $u_i$ $v_i$

SVD für ein 2x2 Beispiel

Sie können diese finden, indem Sie sich überlegen, wie als lineare Transformation eine Einheitskugel in ihrer Domäne in eine Ellipse verwandelt : Die der Ellipse richten sich nach dem und dem sind ihre Vorbilder. $A$ $\mathbb S$ $u_i$ $v_i$

In jedem Fall lässt uns SVD für die obige Datenmatrix (setzen Sie einfach ) schreiben $X$ $A = X$

X = \sum_{i = 1}^{r} σ_{i} u_{i} v_{j}^{T},

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

wobei und orthonormale Sätze von Vektoren sind. Ein Vergleich mit der Eigenwertzerlegung von zeigt, dass die "rechten Singularvektoren" gleich den PCs sind, die "rechten Singularvektoren" sind $\{ u_i \}$ $\{ v_i \}$ $S$ $v_i$

u_{i} = \frac{1}{\sqrt{(n - 1) λ_{i}}} X v_{i},

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

und die "singulären Werte" beziehen sich auf die Datenmatrix über $\sigma_i$

σ_{i}^{2} = (n - 1) λ_{i} .

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

Es ist eine allgemeine Tatsache, dass die rechten Singularvektoren den Spaltenraum von überspannen . In diesem speziellen Fall eine skalierte Projektion der Daten auf die Richtung der ten Hauptkomponente. Die linken singulären Vektoren überspannen im Allgemeinen den Zeilenraum von , was uns einen Satz orthonormaler Vektoren gibt, die die Daten ähnlich wie bei PCs überspannen. $u_i$ $X$ $u_i$ $X$ $i$ $v_i$ $X$

In diesem längeren Artikel gehe ich auf einige Details und Vorteile der Beziehung zwischen PCA und SVD ein .

Andre P
quelle

Danke für deinen anser Andre. Nur zwei kleine Tippfehlerkorrekturen: 1. Im letzten Absatz sind Sie links und rechts verwirrend. 2. In der (Groß-) Formel für X verwenden Sie v_j anstelle von v_i.

Alon,