PCA auf eine sehr große dünnbesetzte Matrix anwenden

Question

Ich führe eine Textklassifizierungsaufgabe mit R durch und erhalte eine Dokument-Begriffs-Matrix mit einer Größe von 22490 mal 120.000 (nur 4 Millionen Nicht-Null-Einträge, weniger als 1% Einträge). Nun möchte ich die Dimensionalität mit Hilfe der PCA (Principal Component Analysis) reduzieren. Leider kann R mit dieser riesigen Matrix nicht umgehen, also speichere ich diese dünnbesetzte Matrix in einer Datei im "Matrix Market Format", in der Hoffnung, dass ich andere Techniken für die PCA verwenden kann.

Könnte mir also jemand Tipps für nützliche Bibliotheken (unabhängig von der Programmiersprache) geben, mit denen sich eine PCA mit dieser großen Matrix problemlos durchführen lässt, oder eine PCA per Hand, mit anderen Worten, selbst durchführen, zunächst die Kovarianzmatrix und dann die Eigenwerte und Eigenvektoren der Kovarianzmatrix zu berechnen .

Was ich möchte ist, dass Berechnen Sie alle PCs (120.000) und wählen Sie nur die besten N PCs aus, die 90% der Varianz ausmachen. . In diesem Fall muss ich natürlich a priori einen Schwellenwert festlegen, um einige sehr kleine Varianzwerte (in der Kovarianzmatrix) auf 0 zu setzen. Andernfalls wäre die Kovarianzmatrix nicht spärlich und ihre Größe würde 120.000 mal 120.000 betragen, was mit einer einzigen Maschine unmöglich zu bewältigen ist. Auch die Ladungen (Eigenvektoren) werden extrem groß sein und sollten im Sparse-Format gespeichert werden.

Vielen Dank für jede Hilfe!

Hinweis: Ich verwende einen Rechner mit 24 GB RAM und 8 Prozessorkernen.

Answer 1

Das Python-Toolkit scikit-learn hat einige PCA-Varianten, von denen RandomizedPCA kann dünnbesetzte Matrizen in jedem von der Software unterstützten Format verarbeiten scipy.sparse . scipy.io.mmread sollte in der Lage sein, das Matrix Market-Format zu analysieren (ich habe es allerdings nie ausprobiert).

Haftungsausschluss: Ich gehöre dem scikit-learn-Entwicklungsteam an.

EDITAR : die spärliche Matrixunterstützung von RandomizedPCA wurde in scikit-learn 0.14 veraltet. TruncatedSVD sollte an seiner Stelle verwendet werden. Einzelheiten finden Sie in der Dokumentation.

Answer 2

Anstelle der PCA können Sie auch die Latent-Dirichlet-Allokation (LDA) verwenden, die die Dokument-Wort-Matrix in eine Dokument-Thema- und eine Thema-Wort-Matrix zerlegt. Hier ist ein Link zu einer R-Implementierung: http://cran.r-project.org/web/packages/lda/ - Es gibt eine ganze Reihe von Implementierungen, aber wenn Sie googeln.

Bei LDA müssen Sie eine feste Anzahl von Themen (ähnlich den Hauptkomponenten) im Voraus festlegen. Eine potenziell bessere Alternative ist HDP-LDA ( http://www.gatsby.ucl.ac.uk/~ywteh/forschung/npbayes/npbayes-r21.tgz ), das die Anzahl der Themen lernt, die eine gute Repräsentation Ihres Korpus bilden.

Wenn Sie unseren Datensatz im Speicher unterbringen können (was anscheinend der Fall ist), dann sollten Sie auch kein Problem haben, den LDA-Code auszuführen.

Wie eine Reihe von Leuten im scicomp-Forum anmerkte, sollte es nicht nötig sein, alle 120k Hauptkomponenten zu berechnen. Algorithmen wie http://en.wikipedia.org/wiki/Power_iteration berechnen die größten Eigenwerte einer Matrix, und die LDA-Algorithmen konvergieren zu einer Repräsentation der Daten mit minimaler Beschreibungslänge bei der angegebenen Anzahl von Themen.

Answer 3

In R big.PCA の bigpca Paket http://cran.r-project.org/web/packages/bigpca/bigpca.pdf erfüllt die Aufgabe.

Answer 4

Textklassifizierungsaufgabe

Ich habe beschlossen fast das gleiche Problem unter Verwendung einer Technik für PCA einer dünnbesetzten Matrix . Diese Technik kann mit sehr großen spärlichen Matrizen umgehen. Das Ergebnis zeigt, dass diese einfache PCA besser ist als word2vec. Es beabsichtigt, die einfache PCA übertrifft LDA.

Answer 5

Ich nehme an, dass Sie nicht in der Lage sein werden, alle Hauptkomponenten zu berechnen. Aber Sie können trotzdem eine Version der Matrix Ihres Datensatzes mit reduzierter Dimension erhalten. Ich habe eine einfache Routine in MATLAB implementiert, die leicht in Python nachgebildet werden kann.

Berechnen Sie die Kovarianzmatrix Ihres Eingabedatensatzes und wandeln Sie sie in eine dichte Matrix um. Angenommen, S ist Ihre 120.000 * 22490 dünnbesetzte Eingabematrix, dann würde dies wie folgt aussehen:

Smul=full(S.'*S);
Sm=full(mean(S));
Sm2=120000*Sm.'*Sm;
Scov=Smul-Sm2; 

Wenden Sie die Funktion eigs auf die Kovarianzmatrix an, um die ersten N dominanten Eigenvektoren zu erhalten,

[V,D] = eigs(Scov,N);

Und erhalten Sie pcs durch Projektion der nullzentrierten Matrix auf Eigenvektoren,

Sr=(S-Sm)*V; 

Sr ist die Version von S in reduzierter Dimension.