Czy możliwa jest nawet PCA na dużą skalę?

10

Klasycznym sposobem analizy głównych składowych (PCA) jest wykonanie macierzy danych wejściowych, których kolumny mają zerową średnią (wtedy PCA może „maksymalizować wariancję”). Można to łatwo osiągnąć poprzez centrowanie kolumn. Jednak gdy matryca wejściowa jest rzadka, matryca środkowa będzie już rzadsza i - jeśli matryca jest bardzo duża - nie będzie już pasować do pamięci. Czy istnieje algorytmiczne rozwiązanie problemu z pamięcią masową?

pca algorithms dimensionality-reduction large-data sparse Roy
źródło
5
Nawet jeśli pełna matryca danych nie mieści się w pamięci, bardzo dobrze może być tak, że albo kowariancja, albo matryca Gram mieszczą się w pamięci. Te wystarczą do wykonania PCA. O jakim rozmiarze macierzy danych wejściowych myślisz? Zobacz także stats.stackexchange.com/questions/35185 .
ameba
1
@amoeba: Patrzę na 500 000 próbek (wiersze) i 300 000 funkcji (kolumny)
Roy
Jeśli chodzi o oprogramowanie, Apache Spark ma go na Spark.apache.org/docs/latest/... na pewno wdrożenie zajmuje się danymi z braku pamięci
Tim

Odpowiedzi:

11

Tak to mozliwe.

Jeśli matryca danych nie mieści się w pamięci RAM, to jeszcze nie koniec świata: istnieją wydajne algorytmy, które mogą pracować z danymi przechowywanymi na dysku twardym. Patrz np. Randomizowany PCA, jak opisano w Halko i in., 2010, Algorytm analizy głównej składowej dużych zbiorów danych .

W sekcji 6.2 autorzy wspominają, że wypróbowali swój algorytm na 400k razy 100k macierzy danych i to

Algorytm niniejszego artykułu wymagał 12,3 godziny na przetworzenie wszystkich 150 GB tego zestawu danych przechowywanego na dysku, przy użyciu komputera przenośnego z 1,5 GB pamięci RAM [...].

Zauważ, że było to w dawnych czasach magnetycznych dysków twardych; dziś dostępne są znacznie szybsze dyski półprzewodnikowe, więc wydaje mi się, że ten sam algorytm działałby znacznie szybciej.

Zobacz także ten stary wątek, aby uzyskać więcej informacji na temat randomizowanego PCA: Najlepszy algorytm PCA dla ogromnej liczby funkcji (> 10 KB)? oraz ten obszerny przegląd z 2011 r. autorstwa Halko i wsp .: Znalezienie struktury z przypadkowością: algorytmy probabilistyczne do konstruowania przybliżonych rozkładów macierzy .

ameba
źródło