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?X

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

ameba
źródło
8
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
2
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/X/n XX/n1X
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. n × p n pXn×pnp

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 PCC C = XX / ( n - 1 ) C = V L V , V L λ i j j X V i i X Vp×pCC=XX/(n1)

C=VLV,
VLλ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 .jjXViiXV

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 przezX = U S V , U S s i C = V S UU S V/ ( n - 1 ) = V S 2X

X=USV,
USsiVλi=s 2 i /(n-1)XV=USVV=US
C=VSUUSV/(n1)=VS2n1V,
Vλi=si2/(n1)XV=USVV=US .

Podsumowując:

  1. Jeśli , wówczas kolumny są głównymi kierunkami / osiami.X=USVV
  2. Kolumny to główne elementy („wyniki”).US
  3. 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.λi=si2/(n1)λi
  4. 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.n1UVS/n1
  5. Powyższe jest poprawne tylko wtedy, gdy jest wyśrodkowany. XTylko wtedy macierz kowariancji jest równa .XX/(n1)
  6. 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 iXUV
  7. 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.X
  8. 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.pk<pkUk×kSUkSkn×kk
  9. 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 .kVkXk=UkSkVkn×pkXkk
  10. Ś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 sytuacjiUn×nVp×pn>pnpUSUn×pnpUnp.

Dalsze linki

Obracanie animacji PCA

ameba
źródło
5
@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ść .(xix¯)(xix¯)xiX(XX¯)(XX¯)/(n1)XXX/(n1)(xix¯)2x¯=0xi2
ameba
2
Przykładowy kod dla PCA autorstwa SVD: stackoverflow.com/questions/3181593/...
optymista
1
Amoeba, wziąłem odpowiedzialność za dodanie jeszcze jednego linku zgodnie z podanymi przez ciebie linkami. Mam nadzieję, że uznasz to za stosowne.
ttnphns
2
@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λi=si2
Dims
1
@sera Po prostu przetransponuj swoją matrycę i pozbądź się problemu. W przeciwnym razie będziesz się mylić.
ameba
22

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
21

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μxi

X=(x1TμTx2TμTxnTμT).

Macierz kowariancji

S=1n1i=1n(xiμ)(xiμ)T=1n1XTX

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łasnejS

S=VΛVT=i=1rλiviviT,

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.viiλiiSi

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, abyA=(1201)uivi

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.ASuivi

W każdym razie, dla powyższej macierzy danych (tak naprawdę, po prostu ustaw ), SVD pozwala nam pisaćXA=X

X=i=1rσiuivjT,

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ą{ v i } S v i{ui}{vi}Svi

ui=1(n1)λiXvi,

a „wartości pojedyncze” są powiązane z macierzą danych za pośrednictwemσi

σi2=(n1)λ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. X u i X i v i XuiXuiXiviX

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