Zastosuj PCA na bardzo dużej rzadkiej matrycy

16

Wykonuję zadanie klasyfikacji tekstu za pomocą R i otrzymuję macierz dokumentu o rozmiarze 22490 na 120 000 (tylko 4 miliony niezerowych wpisów, mniej niż 1% wpisów). Teraz chcę zmniejszyć wymiarowość, korzystając z PCA (Principal Component Analysis). Niestety R nie jest w stanie poradzić sobie z tą ogromną matrycą, dlatego przechowuję tę rzadką macierz w pliku w „Matrix Market Format”, mając nadzieję na użycie innych technik do wykonania PCA.

Czy ktoś mógłby mi więc podpowiedzieć przydatne biblioteki (bez względu na język programowania), które z łatwością mogłyby wykonać PCA na tej wielkoskalowej matrycy, lub samodzielnie wykonać PCA na długo, innymi słowy, najpierw obliczyć macierz kowariancji i następnie obliczyć wartości własne i wektory własne dla macierzy kowariancji .

Chcę obliczyć wszystkie komputery (120 000) i wybrać tylko najlepsze N komputerów, które odpowiadają za 90% wariancji . Oczywiście w tym przypadku muszę z góry ustalić próg, aby ustawić niektóre bardzo małe wartości wariancji na 0 (w macierzy kowariancji), w przeciwnym razie macierz kowariancji nie będzie rzadka, a jej rozmiar wyniesie 120 000 x 120 000, czyli niemożliwe do obsługi za pomocą jednej maszyny. Ponadto ładunki (wektory własne) będą bardzo duże i powinny być przechowywane w formacie rzadkim.

Bardzo dziękuję za wszelką pomoc!

Uwaga: używam maszyny z 24 GB pamięci RAM i 8 rdzeniami procesora.

machine-learning

— Ensom Hodder
źródło

Jak rzadka jest matryca? Jak korzystać z wynikowego SVD? Jeśli potrzebujesz tylko jej części, prawdopodobnie możesz ją zbliżyć znacznie taniej.

— Arnold Neumaier

@ArnoldNeumaier Przepraszam, zapomniałem dodać rzadkie informacje. Zaktualizowałem post wraz z moim kompletnym pomysłem.

— Ensom Hodder

każdy z SLEPc, mahout i irlba sugerowanych do tej pory w odpowiedzi wydaje się odpowiedni dla twojego problemu.

— Arnold Neumaier

1

Dlaczego chcesz obliczyć wszystkie 120k? Wygląda na to, że chcesz tylko tych, którzy odpowiadają za 90% wariancji, co powinno być znacznie tańsze do obliczenia.

— Jed Brown

@JedBrown Hej Jed, masz całkowitą rację! Interesują mnie tylko ci, którzy odpowiadają za 90% wariancji, a także odpowiednie wektory własne (do późniejszej transformacji zestawu danych testowych). Czy możesz podać mi swoje tańsze metody ?

— Ensom Hodder

4

Sugeruję pakiet irlba - daje on praktycznie takie same wyniki jak svd, ale możesz zdefiniować mniejszą liczbę pojedynczych wartości do rozwiązania. Przykład wykorzystania rzadkich matryc do rozwiązania nagrody Netflix można znaleźć tutaj: http://bigcomputing.blogspot.de/2011/05/bryan-lewiss-vignette-on-irlba-for-svd.html

— Marc w pudełku
źródło

Dziękuję za komentarze. W rzeczywistości obejrzałem ten film i wypróbowałem wczoraj pakiet irlba , ale wydawało się, że można go użyć tylko do obliczenia kilku pojedynczych wartości. Jednak, jak stwierdzono w poście, chcę obliczyć WSZYSTKIE wartości osobliwe (120 000), aby wybrać odpowiednią liczbę komputerów PC zgodnie z wariancjami, które uwzględniają. W tym przypadku myślę, że irlba nie jest już odpowiedni.

— Ensom Hodder

Czy możesz wykorzystać wyniki SVD w sposób podobny do PCA? Nie musisz wyśrodkowywać danych PRZED wykonaniem SVD, aby wykonać PCA?

— Zach

@Zach - SVD jest głównym algorytmem stojącym za PCA (patrz prcomp - stat.ethz.ch/R-manual/R-pched/library/stats/html/prcomp.html ). Centrowanie danych jest również standardową procedurą przed poddaniem się PCA, chociaż istnieje wiele różnych opcji w zależności od pytania (np. Można zastosować różne rodzaje skalowania).

— Marc w pudełku

Ile to kosztuje, jeśli nie wyśrodkuję danych przed SVD? Mam rzadką matrycę, która pasuje do pamięci, ale centrowanie sprawiłoby, że byłaby gęsta i zbyt duża, aby zmieściła się w pamięci.

— Zach.

@Zach - To naprawdę zależy od tego, jak chcesz powiązać swoje próbki ze sobą. Jeśli nie możesz pracować z wyśrodkowanymi danymi ze względu na limity pamięci, myślę, że decyzja została podjęta za ciebie. Ogólnie, centrowanie danych powoduje, że PCA działa na macierzy kowariancji próbek, podczas gdy centrowanie i skalowanie danych powoduje, że PCA działa na macierzy korelacji. Aby uzyskać lepszy wgląd w te decyzje, możesz zadać pytanie na stronie stats.stackexchange.com lub przeszukać istniejące odpowiedzi dotyczące PCA.

— Marc w pudełku

8

Sugeruję użycie SLEPc do obliczenia częściowego SVD. Szczegółowe informacje można znaleźć w rozdziale 4 instrukcji obsługi i stronach podręcznika SVD .

— Jed Brown
źródło

1

Ponieważ chce PCA, musi wyśrodkować dane przed obliczeniem SVD. To zniszczy rzadkość. Czy istnieje jakiś sposób, że SLEPc to umożliwia?

— dranxo

3

To tylko rzadkie + niska ranga. SLEPc nie potrzebuje wpisów macierzy, tylko operator liniowy, który można zastosować jako macierz rzadką plus korektę.

— Jed Brown

2

Głosuję na Mahouta, który jest również dobry dla innych zadań NLP / TA i implementuje mapowanie / zmniejszanie.

— danas.zuokas
źródło

Tak, masz rację, Mahout jest dokładnie na mojej mapie drogowej. Ale wolę wcześniej stworzyć prototyp z pewnymi „prostymi” (jak sądzę) technikami.

— Ensom Hodder

1

Sugerowałbym zastosowanie przyrostowego rozkładu wartości osobliwych, których jest wiele w literaturze. Na przykład:

raporty techniczne Matthew Brand 1 i 2 są dość łatwe do naśladowania
Praca magisterska Chrisa Bakera , jego oprogramowanie IncPACK i jego późniejszy artykuł na temat przyrostowej metody SVD
Bunch i Nielsen opublikowali najwcześniejszy znany artykuł
Artykuły autorstwa Hall'a na temat aktualizacji problemów wartości własnych 1 i 2
Sekwencyjna analiza Karhunena-Loeve'a przeprowadzona przez Levy i wsp., Która jest w zasadzie taka sama

Wszystkie te podejścia ograniczają się do:

zacznij od małego zestawu danych
obliczyć SVD jakoś (ten krok jest trywialny dla macierzy z jedną kolumną)
powtarzaj do końca:
- dodaj nowy zestaw danych
- użyj istniejących reguł SVD i aktualizacji, aby obliczyć SVD nowego zestawu danych

W swojej aplikacji, jeśli masz pojęcie o tym, gdzie znajduje się próg wartości osobliwej na szczycie $N$ wartości będą, możesz użyć tej wartości do obliczenia obciętego SVD; jeśli wartość progowa jest wystarczająco mała, wówczas matryca, którą musisz zachować w pamięci, również będzie mała (zostaną zachowane tylko wartości w liczbie pojedynczej powyżej wartości progowej, wraz z ich wektorami w liczbie pojedynczej; nie jest nawet konieczne utrzymanie zarówno lewej, jak i prawej liczby pojedynczej wektory w algorytmie Branda).

— Geoff Oxberry
źródło

0

Nadal możesz używać R.

Revolution Rto kompilacja R, która obsługuje zestawy danych większe niż pamięć RAM. Użyj funkcji princomp.

Posiada również pełen zakres funkcji statystycznych zaprojektowanych specjalnie dla problemów w stylu dużych danych, które nie pasują do pamięci RAM, np. Regresja liniowa, regresja logistyczna, kwantyle itp.

Możesz bezpłatnie pobrać w pełni funkcjonalną wersję akademicką, zaznaczając pole „Jestem akademikiem”.

— Contango
źródło