Jak wykonać PCA dla danych o bardzo dużych wymiarach?

12

Aby przeprowadzić analizę głównego składnika (PCA), należy odjąć średnie z każdej kolumny od danych, obliczyć macierz współczynnika korelacji, a następnie znaleźć wektory własne i wartości własne. Cóż, raczej to zrobiłem, aby zaimplementować go w Pythonie, z wyjątkiem tego, że działa tylko z małymi macierzami, ponieważ metoda znajdowania macierzy współczynnika korelacji (corrcoef) nie pozwala mi na użycie tablicy o wysokiej wymiarowości. Ponieważ muszę go używać do obrazów, moja obecna implementacja naprawdę mi nie pomaga.

Czytałem, że można po prostu wziąć macierz danych i obliczyć zamiast , ale to nie działa dla mnie. Nie jestem do końca pewien, czy rozumiem, co to znaczy, poza tym, że ma to być macierz zamiast (w moim przypadku ). Czytałem o tych z samouczków na temat własnych twarzy, ale żaden z nich nie wyjaśnił tego w taki sposób, że naprawdę mogłem to zrozumieć. $D$ $DD^\top/n$ $D^\top D/n$ $n \times n$ $p\times p$ $p\gg n$

Krótko mówiąc, czy istnieje prosty algorytmiczny opis tej metody, abym mógł ją zastosować?

pca python ameba
źródło

To, co czytasz, jest poprawne. Macierz

nazywa matryca gram. Jego wektory własne są (skalowane) głównymi składnikami. Jego wartości własne są dokładnie identyczne, aż do współczynnika

, z wartościami własnymi macierzy kowariancji

.

D D^{⊤}

$DD^\top$

1 / n

$1/n$

D^{⊤} D / n

$D^\top D/n$

ameba

10

Najłatwiejszym sposobem wykonania standardowego PCA jest wyśrodkowanie kolumn macierzy danych (zakładając, że kolumny odpowiadają różnym zmiennym) poprzez odjęcie średnich kolumn, a następnie wykonanie SVD. Lewe wektory w liczbie pojedynczej, pomnożone przez odpowiednią wartość w liczbie pojedynczej, odpowiadają (szacowanym) głównym składnikom. Odpowiednie wektory w liczbie pojedynczej odpowiadają (szacunkowym) kierunkom składowych głównych - są one takie same jak wektory własne podane przez PCA. Wartości w liczbie pojedynczej odpowiadają odchyleniom standardowym głównych składników (pomnożonemu przez współczynnik pierwiastka n, gdzie n jest liczbą wierszy w macierzy danych) - tak samo jak pierwiastek kwadratowy wartości własnych podanych przez PCA.

Jeśli chcesz wykonać PCA na macierzy korelacji, musisz zastosować standaryzację kolumn macierzy danych przed zastosowaniem SVD. Sprowadza się to do odjęcia średnich (centrowanie), a następnie podzielenia przez odchylenia standardowe (skalowanie).

To będzie najbardziej wydajne podejście, jeśli chcesz mieć pełną PCA. Za pomocą algebry możesz zweryfikować, że daje to tę samą odpowiedź, co rozkład widmowy macierzy kowariancji próbki.

Istnieją również wydajne metody obliczania częściowego SVD, gdy potrzebujesz tylko kilku komputerów. Niektóre z nich są wariantami iteracji mocy. Algorytm Lanczosa jest przykładem, który jest także związany z cząstkowych najmniejszych kwadratów. Jeśli twoja matryca jest ogromna, możesz być lepiej z przybliżoną metodą. W takim przypadku istnieją również statystyczne powody, dla których należy zalegalizować PCA.

vqv
źródło

Popraw mnie, jeśli się mylę, ale myślę, że algorytm Lanczosa wykonuje skład eigend, a nie SVD.

ameba

1

Zainteresowany czytelnik może poszukać dalszych informacji na temat wykonywania PCA przez SVD: Związek między SVD i PCA. Jak używać SVD do wykonywania PCA?

ameba

10

To, co teraz robisz, jest bliskie, ale musisz upewnić się, że pomnożysz wektory własne z (data . data.T) / lineslewej strony data.T, aby uzyskać wektory własne (data.T . data) / lines. Czasami nazywa się to „transpozycją”.

$A$ $A$ $A^T A$

$A$ $m \times n$ $n >> m$ $A^T A$ $n \times n$ $A^T A$ $m \times m$ $A A^T$ $A^T A$ $A A^T$

$v$ $A A^T$ $\lambda$

$AA^T v = \lambda v$
$A^T(A A^T v) = A^T(\lambda v)$
$(A^T A)(A^T v) = \lambda (A^T v)$

$v$ $A A^T$ $A^T v$ $A^T A$ $A$ $A^T A$ $v$ $AA^T$ $A^T$ $A^T v$ $A^T A$

raegtin
źródło

1

To brzmi jak „sztuczka jądra” zastosowana do PCA. en.wikipedia.org/wiki/Kernel_PCA Jest to bardzo dobry sposób obsługi niektórych dużych matryc.

Gilead

A A^{⊤}

$AA^\top$

8

Wygląda na to, że chcesz algorytmu NIPALS do wykonywania PCA. Jest to bardzo popularny algorytm wśród statystyk. Ma wiele zalet:

Obliczeniowo tańszy niż SVD lub metody dekompozycji wartości własnych, jeśli tylko kilka pierwszych składników jest wymaganych.
Ma ogólnie skromniejsze wymagania dotyczące przechowywania, ponieważ macierz kowariancji nigdy nie jest tworzona. Jest to bardzo ważna właściwość w przypadku bardzo dużych zestawów danych.
Potrafi obsłużyć brakujące dane w zestawie danych (choć nie stanowi to problemu w twoim przypadku, ponieważ masz do czynienia z obrazami).

Opis
http://en.wikipedia.org/wiki/Non-linear_iterative_partial_least_squares

Algorytm
Oto prosty i doskonały opis algorytmu (w sekcji 1.2)
http://stats4.eng.mcmaster.ca/w/mediafiles/mediawiki/f/f7/Section-Extra-Class-1.pdf

Pamiętaj, aby najpierw zrobić średnią skalę środkową przed wykonaniem PCA, ponieważ jest wrażliwa na skalę.

Gilead
źródło

4

Aby dodać odpowiedź Gileada, są one obliczeniowo tańszymi algorytmami dla skróconych PCA. NIPALS jest rzeczywiście bardzo popularny, ale odniosłem duży sukces dzięki przybliżonym metodom, które wykonują szereg dopasowań na danych częściowych (co często nazywane jest PCA przez losową projekcję). Zostało to omówione w wątku metaoptymalizacji .

Jak wspomniałeś w Pythonie, pozwól mi zauważyć , że algorytm jest zaimplementowany w scikit-learn : klasie PCA . W szczególności jest stosowany w przykładzie demonstrującym powierzchnie własne .

Gael Varoquaux
źródło

Jak wykonać PCA dla danych o bardzo dużych wymiarach?

Odpowiedzi: