Związek między SVD a PCA. Jak korzystać z SVD do wykonywania PCA?

351

Analiza głównego składnika (PCA) jest zwykle wyjaśniana za pomocą rozkładu własnego macierzy kowariancji. Jednakże, można także przeprowadzić za pomocą rozkładu wartości pojedyncza (SVD) macierzy danych . Jak to działa? Jaki jest związek między tymi dwoma podejściami? Jaki jest związek między SVD a PCA? $\mathbf X$

Lub innymi słowy, jak użyć SVD matrycy danych do przeprowadzenia redukcji wymiarowości?

— ameba
źródło

Napisałem to pytanie w stylu FAQ wraz z własną odpowiedzią, ponieważ jest ono często zadawane w różnych formach, ale nie ma kanonicznego wątku, a zatem zamykanie duplikatów jest trudne. Podaj meta komentarze w tym towarzyszącym meta wątku .

— ameba

stats.stackexchange.com/questions/177102/…

— kjetil b halvorsen

Oprócz doskonałej i szczegółowej odpowiedzi ameby z jej dalszymi linkami, mogę zalecić sprawdzenie tego , gdzie PCA jest rozważane obok innych technik opartych na SVD. Dyskusja przedstawia algebrę prawie identyczną z amebą, z niewielką różnicą, że mowa tam, opisująca PCA, dotyczy rozkładu svd z [lub ] zamiast - co jest po prostu wygodne, ponieważ odnosi się do PCA wykonanego przez składową macierz kowariancji.

X / \sqrt{n}

$\mathbf X/\sqrt{n}$

X / \sqrt{n - 1}

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

X

$\bf X$

— ttnphns

PCA jest szczególnym przypadkiem SVD. PCA potrzebuje znormalizowanych danych, najlepiej tej samej jednostki. Matryca to nxn w PCA.

— Orvar Korvar

@OrvarKorvar: O jakiej macierzy nxn mówisz?

— Cbhihe

Odpowiedzi:

412

Niech macierz danych będzie miała wielkość , gdzie jest liczbą próbek, a jest liczbą zmiennych. Załóżmy, że jest on wyśrodkowany , tzn. Średnie kolumnowe zostały odjęte i są teraz równe zero. $\mathbf X$ $n \times p$ $n$ $p$

Następnie macierz kowariancji jest wyrażona przez . Jest to macierz symetryczna, więc można ją przekątnie: gdzie jest macierzą wektorów własnych (każda kolumna jest wektorem własnym), a jest macierz diagonalna z wartościami własnymi w malejącej kolejności na przekątnej. Wektory własne nazywane są głównymi osiami lub głównymi kierunkami danych. Projekcje danych na głównych osiach nazywane są składowymi głównymi , znanymi również jako wyniki PC $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$ ; można je postrzegać jako nowe, przekształcone zmienne. -ty składnik główny jest przez -tej kolumnie . Współrzędne punktu danych w nowej przestrzeni PC są podawane przez ty rząd .

j

$j$

j

$j$

X V

$\mathbf {XV}$

i

$i$

i

$i$

X V

$\mathbf{XV}$

Jeśli teraz wykonamy rozkład pojedynczej wartości , otrzymamy rozkład gdzie jest macierzą jednolitą, a jest macierzą diagonalną liczby pojedyncze . Stąd łatwo można zauważyć, że co oznacza, że prawe wektory w liczbie pojedynczej są głównymi kierunkami i że wartości w liczbie pojedynczej są powiązane z wartościami własnymi macierzy kowariancji za pomocą . Główne składniki podano przez $\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$ .

Podsumowując:

Jeśli , wówczas kolumny są głównymi kierunkami / osiami. $\mathbf X = \mathbf U \mathbf S \mathbf V^\top$ $\mathbf V$
Kolumny to główne elementy („wyniki”). $\mathbf {US}$
Wartości osobliwe są powiązane z wartościami własnymi macierzy kowariancji za pomocą . Wartości własne pokazują wariancje poszczególnych komputerów. $\lambda_i = s_i^2/(n-1)$ $\lambda_i$
Standaryzowane wyniki podano w kolumnach a ładunki podano w kolumnach . Zobacz np. Tutaj i tutaj, dlaczego „ładunków” nie należy mylić z głównymi kierunkami. $\sqrt{n-1}\mathbf U$ $\mathbf V \mathbf S/\sqrt{n-1}$
Powyższe jest poprawne tylko wtedy, gdy jest wyśrodkowany. $\mathbf X$ Tylko wtedy macierz kowariancji jest równa . $\mathbf X^\top \mathbf X/(n-1)$
Powyższe jest poprawne tylko dla posiadającego próbki w wierszach i zmienne w kolumnach. Jeśli zmienne są w wierszach, a próbki w kolumnach, wówczas interpretacje wymiany i $\mathbf X$ $\mathbf U$ $\mathbf V$
Jeśli ktoś chce wykonać PCA na macierzy korelacji (zamiast macierzy kowariancji), wówczas kolumny powinny być nie tylko wyśrodkowane, ale także znormalizowane, tj. Podzielone przez ich odchylenia standardowe. $\mathbf X$
W celu zmniejszenia wymiaru danych od do , wybrać pierwsze kolumny i górnej lewej części . Ich produkt to wymagana macierz zawierająca pierwsze komputerów. $p$ $k<p$ $k$ $\mathbf U$ $k\times k$ $\mathbf S$ $\mathbf U_k \mathbf S_k$ $n \times k$ $k$
Dalsze pomnożenie pierwszych komputerów przez odpowiednie osie główne daje macierz, która ma oryginalny rozmiar ale ma niższą rangę (rangi ). Ta macierz zapewnia rekonstrukcję oryginalnych danych z pierwszych komputerów. Ma najniższy możliwy błąd rekonstrukcji, patrz moja odpowiedź tutaj . $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$
Ściśle mówiąc, ma rozmiar a ma rozmiar . Jeśli jednak to ostatnie Kolumny są dowolne (a odpowiadające im wiersze mają stałą zero); dlatego należy użyć ekonomicznego (lub cienkiego ) SVD, który zwraca o rozmiarze , porzucając niepotrzebne kolumny. W przypadku dużych macierz byłaby niepotrzebnie ogromna. To samo dotyczy przeciwnej sytuacji $\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$ .

Dalsze linki

Jaki jest intuicyjny związek między SVD a PCA - bardzo popularny i bardzo podobny wątek na math.SE.
Dlaczego PCA danych za pomocą SVD danych? - omówienie korzyści płynących z wykonywania PCA za pomocą SVD [krótka odpowiedź: stabilność liczbowa].
Analiza PCA i korespondencji w odniesieniu do Biplot - PCA w kontekście niektórych technik kongenerycznych, wszystkie oparte na SVD.
Czy jest jakaś przewaga SVD nad PCA? - pytanie, czy korzyści płynące ze stosowania SVD zamiast PCA [krótka odpowiedź: źle postawione pytanie].
Zrozumienie analizy głównych składników, wektorów własnych i wartości własnych - moja odpowiedź zawiera nietechniczne wyjaśnienie PCA. Aby zwrócić na siebie uwagę, odtwarzam tutaj jedną cyfrę:

— ameba
źródło

@Antoina, macierz kowariancji jest z definicji równa , gdzie nawiasy kątowe oznaczają średnią wartość . Jeśli wszystkie są ułożone jako wiersze w jednej macierzy , to wyrażenie jest równe . Jeśli jest wyśrodkowany, upraszcza to . Pomyśl o wariancji; jest równa . Ale jeśli (tzn. Dane są wyśrodkowane), to jest to po prostu średnia wartość .

⟨ (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$

— ameba

Przykładowy kod dla PCA autorstwa SVD: stackoverflow.com/questions/3181593/...

— optymista

Amoeba, wziąłem odpowiedzialność za dodanie jeszcze jednego linku zgodnie z podanymi przez ciebie linkami. Mam nadzieję, że uznasz to za stosowne.

— ttnphns

@amoeba tak, ale po co z tego korzystać? Czy można również użyć tego samego mianownika dla ? Problem polega na tym, że widzę formuły, w których i próbuję zrozumieć, jak ich używać?

S

$S$

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

$\lambda_i = s_i^2$

— Dims

@sera Po prostu przetransponuj swoją matrycę i pozbądź się problemu. W przeciwnym razie będziesz się mylić.

— ameba

Napisałem fragment kodu Python i Numpy, który towarzyszy odpowiedzi @ amoeba i zostawiam go tutaj na wypadek, gdyby był dla kogoś przydatny. Komentarze pochodzą głównie z odpowiedzi @ 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)

— 115202
źródło

Zacznę od PCA. Załóżmy, że masz n punktów danych składających się z d liczb (lub wymiarów) każdy. Jeśli wyśrodkujesz te dane (odejmij średni punkt danych od każdego wektora danych ), możesz ułożyć dane w stos, aby utworzyć macierz $\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)\,.$

Macierz kowariancji

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$

miary, w jakim stopniu różne współrzędne, w których podane są dane, różnią się razem. Nic więc dziwnego, że PCA - który jest zaprojektowany do przechwytywania zmienności twoich danych - może być podany w postaci macierzy kowariancji. W szczególności okazuje się , że rozkład wartości własnej $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 \,,$

gdzie to ty główny składnik lub PC, a to wartość własna i jest również równa wariancji danych wzdłuż komputera. Rozkład ten pochodzi z ogólnego twierdzenia z algebry liniowej, a niektóre prace nie muszą być wykonane, aby motywować relatino do PCA. $v_i$ $i$ $\lambda_i$ $i$ $S$ $i$

PCA z losowo generowanego zbioru danych Gaussa

SVD to ogólny sposób na zrozumienie macierzy w kategoriach przestrzeni kolumn i przestrzeni wierszy. (Jest to sposób na przepisanie dowolnej macierzy w kategoriach innych macierzy z intuicyjnym stosunkiem do przestrzeni wierszy i kolumn.) Na przykład dla macierzy możemy znaleźć wskazówki i w domenie i zakresie, aby $A = \left( \begin{array}{cc}1&2\\0&1\end{array} \right)$ $u_i$ $v_i$

SVD dla przykładu 2x2

Można je znaleźć, biorąc pod uwagę, w jaki sposób jako transformacja liniowa przekształca sferę jednostkową w swojej dziedzinie w elipsę: główne półosie elipsy wyrównują się z a są ich pierwowzorami. $A$ $\mathbb S$ $u_i$ $v_i$

W każdym razie, dla powyższej macierzy danych (tak naprawdę, po prostu ustaw ), SVD pozwala nam pisać $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\,,$

gdzie i są ortonormalnymi zestawami wektorów. Porównanie z rozkładem wartości własnych ujawnia, że „prawe wektory osobliwe” są równe komputerom osobistym, „prawe wektory osobliwe” są $\{ 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\,,$

a „wartości pojedyncze” są powiązane z macierzą danych za pośrednictwem $\sigma_i$

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

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

Jest to ogólnie to, że odpowiednie pojedyncze wektory obejmują przestrzeń kolumny . W tym konkretnym przypadku daje nam skalowane rzutowanie danych na kierunek głównego składnika. Lewe pojedyncze wektory ogólnie obejmują przestrzeń wierszy , co daje nam zestaw wektorów ortonormalnych, które obejmują dane podobnie jak komputery PC. $u_i$ $X$ $u_i$ $X$ $i$ $v_i$ $X$

W tym dłuższym artykule omówię więcej szczegółów i korzyści związanych z relacją między PCA i SVD .

— Andre P.
źródło

Dzięki za twój anser Andre. Tylko dwie małe poprawki literówek: 1. W ostatnim akapicie mylisz lewą i prawą stronę. 2. W (wielkiej) formule dla X używasz v_j zamiast v_i.

— Alon