Najszybszy algorytm PCA dla danych wielowymiarowych

11

Chciałbym wykonać PCA na zestawie danych złożonym z około 40 000 próbek, z których każda zawiera około 10 000 funkcji.

Używanie funkcji princomp Matlaba konsekwentnie zajmuje ponad pół godziny, w którym to momencie zabijam proces. Chciałbym znaleźć implementację / algorytm, który działa w mniej niż 10 minut. Jaki byłby najszybszy algorytm? Jak długo potrwa na i7 dual core / 4GB Ram?

high-dimensional data-analysis łagodny
źródło

Tak, masz rację, powinienem być bardziej precyzyjny. Zajmuje to ponad pół godziny, potem zdecydowałem się zabić proces. Muszę to zrobić co najmniej dziesięć razy, czy byłoby miło mieć coś, co działa w mniej niż 10 minut

łagodny

Jak rzadka jest twoja matryca?

Arnold Neumaier,

Procent zer w matrycy jest wyższy niż 80%

łagodny

Sprawdź także kernal-PCA.

meawoppl,

11

Przede wszystkim powinieneś określić, czy chcesz wszystkie komponenty, czy te najbardziej znaczące?

$A \in \mathbb{R}^{N \times M}$ $N$ $M$

$C \in \mathbb{R}^{M\times M}$ $O(NM^2)$ $O(M^3)$ $O(2M^2)$ $\approx 1.5$ $A$

$A$ $A$

$C$

Alexander
źródło

2

Myślę, że potrzebujesz tylko kilku (lub kilkuset) dominujących pojedynczych par wartość / wektor. Następnie najlepiej zastosować metodę iteracyjną, która będzie znacznie szybsza i zużyje znacznie mniej pamięci.

W Matlabie patrz

pomoc svds

Arnold Neumaier
źródło

Tak, wydaje się, że metody iteracyjne są znacznie szybsze, jeśli potrzebuję tylko pierwszych stu składników.

łagodny

Jeśli chodzi o svds, próbowałem umieścić moją macierz w rzadkim formacie i zmodyfikować funkcję princomp, aby wstawić svds zamiast svd, i ku mojemu zaskoczeniu zajęło to znacznie więcej czasu na matrycy 2000 * 4000 (180 s zamiast 15 s ). Dziwne ...

łagodny

1

Nie ma potrzeby przechodzenia na format rzadki. Ponadto musisz zmniejszyć liczbę pojedynczych wektorów, które chcesz obliczyć. Do obliczenia pełnego dysku svds nie nadaje się svds.

Arnold Neumaier,

2

W przypadku dominujących trybów również godne uwagi są nowsze randomizowane metody svd, jak w stanford.edu/group/mmds/slides2010/Martinsson.pdf

Nick Alger

2

Możesz sprawdzić moją odpowiedź w Cross Validated . Nie chciałem go tutaj kopiować. Zasadniczo można użyć szybkiego, randomizowanego SVD do obliczenia podstawy PCA i współczynników.

petrichor
źródło

1

Możesz wypróbować algorytm Fast PCA oparty na iteracyjnym sposobie obliczania kilku wektorów własnych. Patrz A. Sharma i KK Paliwal, Szybka analiza głównych składników za pomocą analizy stałoprzecinkowej, Pattern Recognition Letters, 28, 1151-1155, 2007 .

Matematyka
źródło

Najszybszy algorytm PCA dla danych wielowymiarowych

Odpowiedzi: