Jak zrobić SVD i PCA z dużymi danymi?

Mam duży zestaw danych (około 8 GB). Chciałbym użyć uczenia maszynowego do jego analizy. Myślę więc, że powinienem użyć SVD, a następnie PCA, aby zmniejszyć wymiarowość danych w celu zwiększenia wydajności. Jednak MATLAB i Octave nie mogą załadować tak dużego zestawu danych.

Jakich narzędzi mogę użyć do wykonania SVD z tak dużą ilością danych?

Przede wszystkim redukcja wymiarów jest stosowana, gdy masz wiele współzmiennych wymiarów i chcesz zmniejszyć rozmiar problemu, obracając punkty danych do nowej ortogonalnej podstawy i przyjmując tylko osie o największej wariancji. Dzięki 8 zmiennym (kolumnom) przestrzeń jest już mało wymiarowa, więc dalsze zmniejszanie liczby zmiennych raczej nie rozwiąże problemów technicznych związanych z rozmiarem pamięci, ale może mieć duży wpływ na jakość zestawu danych. W konkretnym przypadku bardziej obiecujące jest spojrzenie na naukę onlinemetody Z grubsza mówiąc, zamiast pracować z całym zestawem danych, metody te biorą niewielką ich część (często określane jako „mini-partie”) i budują model przyrostowo. (Osobiście lubię interpretować słowo „online” jako odniesienie do jakiegoś nieskończenie długiego źródła danych z Internetu, takiego jak kanał na Twitterze, gdzie po prostu nie można załadować całego zestawu danych jednocześnie).

Ale co, jeśli naprawdę chcesz zastosować technikę zmniejszania wymiarów, taką jak PCA, do zestawu danych, który nie mieści się w pamięci? Zwykle zestaw danych jest reprezentowany jako macierz danych X o rozmiarze n x m , gdzie n jest liczbą obserwacji (wierszy), a m jest liczbą zmiennych (kolumn). Zazwyczaj problemy z pamięcią wynikają tylko z jednej z tych dwóch liczb.

Zbyt wiele obserwacji (n >> m)

Gdy masz zbyt wiele obserwacji , ale liczba zmiennych jest od małej do umiarkowanej, możesz stopniowo tworzyć macierz kowariancji . Rzeczywiście, typowy PCA polega na skonstruowaniu macierzy kowariancji o rozmiarze m x m i zastosowaniu do niej dekompozycji wartości pojedynczych. Przy m = 1000 zmiennych typu float64 macierz kowariancji ma rozmiar 1000 * 1000 * 8 ~ 8 Mb, co łatwo mieści się w pamięci i może być używane z SVD. Wystarczy więc zbudować macierz kowariancji bez ładowania całego zestawu danych do pamięci - dość wykonalne zadanie .

Alternatywnie możesz wybrać małą reprezentatywną próbkę ze swojego zestawu danych i zbliżyć macierz kowariancji . Ta matryca będzie miała takie same właściwości jak normalnie, tylko nieco mniej dokładna.

Zbyt wiele zmiennych (n << m)

Z drugiej strony, czasami, gdy masz zbyt wiele zmiennych , sama macierz kowariancji nie pasuje do pamięci. Np. Jeśli pracujesz z obrazami 640x480, każda obserwacja ma 640 * 480 = 307200 zmiennych, co skutkuje macierzą kowariancji 703 Gb! To zdecydowanie nie jest to, co chciałbyś zachować w pamięci komputera, a nawet w pamięci klastra. Musimy więc zmniejszyć wymiary bez budowania macierzy kowariancji.

Moja ulubiona metoda to losowa projekcja . Krótko mówiąc, jeśli masz zestaw danych X o rozmiarze n x m , możesz go pomnożyć przez jakąś rzadką losową macierz R o rozmiarze m x k (z k << m ) i otrzymać nową macierz X ' o znacznie mniejszym rozmiarze n x k o w przybliżeniu takich samych właściwościach jak oryginalna. Dlaczego to działa? Cóż, powinieneś wiedzieć, że PCA ma na celu znalezienie zestawu osi ortogonalnych (głównych komponentów) i rzutowanie danych na pierwsze kz nich. Okazuje się, że rzadkie wektory losowe są prawie ortogonalne, a zatem mogą być również wykorzystane jako nowa podstawa.

I oczywiście nie musisz pomnożyć całego zestawu danych X przez R - możesz przetłumaczyć każdą obserwację x na nową podstawę osobno lub w mini-partiach.

Istnieje również nieco podobny algorytm o nazwie Random SVD . Nie mam z tym żadnego doświadczenia, ale możesz znaleźć przykładowy kod z objaśnieniami tutaj .

Podsumowując, oto krótka lista kontrolna do zmniejszenia wymiarów dużych zestawów danych:

1. Jeśli nie masz tak wielu wymiarów (zmiennych), po prostu użyj algorytmów uczenia się online.
2. Jeśli jest wiele obserwacji, ale umiarkowana liczba zmiennych (macierz kowariancji pasuje do pamięci), konstruuj macierz przyrostowo i używaj normalnego SVD.
3. Jeśli liczba zmiennych jest zbyt wysoka, użyj algorytmów przyrostowych.

Nie zawracaj sobie głowy

Pierwsza zasada programowania, która dotyczy również analizy danych: wszystko działa na małym problemie testowym.

więc weź losową próbkę swoich danych, powiedzmy 100 000 wierszy. wypróbuj różne algorytmy itp., gdy wszystko będzie działać zgodnie z oczekiwaniami, możesz wypróbować większe (i większe) zestawy danych - i zobaczyć, jak zmniejsza się błąd testu, gdy dodajesz więcej danych.

ponadto nie chcesz stosować svd tylko do 8 kolumn: stosujesz go, gdy masz dużo kolumn.

PCA jest zwykle implementowane przez obliczenie SVD na macierzy kowariancji.

Obliczanie macierzy kowariancji jest żenująco równoległym zadaniem, dlatego skaluje się liniowo wraz z liczbą rekordów i jest łatwe do rozpowszechnienia na wielu komputerach!

Wystarczy przeliczyć dane, aby obliczyć średnie. Następnie drugi krok do obliczenia macierzy kowariancji. Można to zrobić z łatwością zmniejszając mapę - zasadniczo jest to to samo, co ponowne obliczenie średnich. Sumy terminów jak w kowariancji są trywialne do paralelizacji! Przy sumowaniu wielu wartości o podobnej wielkości może być konieczne zwrócenie uwagi na wartości liczbowe.

Rzeczy mają się inaczej, gdy masz ogromną liczbę zmiennych . Ale w systemie 8 GB powinieneś być w stanie uruchomić PCA na maksymalnie 20 000 wymiarów w pamięci za pomocą bibliotek BLAS. Ale wtedy możesz napotkać problem, że PCA nie jest już tak niezawodny, ponieważ ma zbyt wiele stopni swobody. Innymi słowy: łatwo się dopasowuje. Widziałem zalecenie posiadania co najmniej 10 * d * d rekordów (lub było to d ^ 3). Zatem dla 10000 wymiarów powinieneś mieć co najmniej miliard rekordów (z 10000 wymiarów ... to dużo!), Aby wynik był statystycznie wiarygodny.

Chociaż prawdopodobnie możesz znaleźć narzędzia, które pozwolą ci to zrobić na jednym komputerze, wchodzisz w zakres, w którym warto rozważyć użycie narzędzi „dużych zbiorów danych”, takich jak Spark, szczególnie jeśli uważasz, że Twój zestaw danych może się powiększać. Spark ma komponent o nazwie MLlib, który obsługuje PCA i SVD. Dokumentacja zawiera przykłady .

Zaimplementowaliśmy SVD do większego zestawu danych za pomocą PySpark. Porównaliśmy również spójność różnych pakietów. Oto link.

Poleciłbym Pythona, jeśli leniwie ocenisz plik, będziesz miał mały ślad pamięci, a numpy / scipy da ci dostęp do wszystkich narzędzi, które zrobiłby Octave / Matlab.