Tragen Sie PCA auf eine sehr große, dünnflüssige Matrix auf

16

Ich führe eine Textklassifizierungsaufgabe mit R durch und erhalte eine Dokumentterm-Matrix mit einer Größe von 22490 mal 120.000 (nur 4 Millionen Einträge ungleich Null, weniger als 1% Einträge). Jetzt möchte ich die Dimensionalität mit PCA (Principal Component Analysis) reduzieren. Leider kann R diese riesige Matrix nicht verarbeiten, daher speichere ich diese spärliche Matrix in einer Datei im "Matrix Market Format", in der Hoffnung, einige andere Techniken zur Durchführung von PCA zu verwenden.

Könnte mir jemand einige Hinweise für nützliche Bibliotheken (unabhängig von der Programmiersprache) geben, die PCA mit dieser großen Matrix mühelos ausführen können, oder selbst eine Langhand-PCA erstellen, dh zuerst die Kovarianzmatrix berechnen und Berechnen Sie dann die Eigenwerte und Eigenvektoren für die Kovarianzmatrix .

Was ich möchte, ist, alle PCs (120.000) zu berechnen und nur die Top-N-PCs auszuwählen, die 90% Abweichung ausmachen . In diesem Fall muss ich natürlich von vornherein einen Schwellenwert angeben, um einige sehr kleine Varianzwerte auf 0 zu setzen (in der Kovarianzmatrix). Andernfalls ist die Kovarianzmatrix nicht spärlich und würde eine Größe von 120.000 mal 120.000 haben unmöglich mit einer einzigen Maschine zu handhaben. Außerdem sind die Ladungen (Eigenvektoren) extrem groß und sollten in einem spärlichen Format gespeichert werden.

Vielen Dank für jede Hilfe!

Hinweis: Ich verwende einen Computer mit 24 GB RAM und 8 CPU-Kernen.

machine-learning Ensom Hodder
quelle
Wie dünn ist die Matrix? Wie benutzt man die resultierende SVD? Wenn Sie nur einen Teil davon benötigen, könnten Sie es wahrscheinlich viel billiger schätzen.
Arnold Neumaier
@ArnoldNeumaier Entschuldigung, ich habe vergessen, die spärlichen Informationen hinzuzufügen. Ich habe den Beitrag zusammen mit meiner vollständigen Idee aktualisiert.
Ensom Hodder
Jedes der in den bisherigen Antworten vorgeschlagenen SLEPc-, Mahout- und Iirlba-Elemente scheint für Ihr Problem geeignet zu sein.
Arnold Neumaier
1
Warum möchten Sie alle 120k berechnen ? Es hört sich so an, als wollten Sie nur diejenigen, die 90% der Varianz ausmachen, was in der Berechnung viel billiger sein sollte.
Jed Brown
@JedBrown Hey Jed, du hast vollkommen recht! Ich interessiere mich nur für diejenigen, die eine Varianz von 90% ausmachen, und auch für entsprechende Eigenvektoren (für die anschließende Transformation des Testdatensatzes). Könnten Sie mir bitte Ihre billigeren Methoden mitteilen ?
Ensom Hodder

Antworten:

4

Ich schlage das irlba-Paket vor - es liefert praktisch die gleichen Ergebnisse wie svd, aber Sie können eine kleinere Anzahl singulärer Werte definieren, für die eine Lösung gefunden werden soll. Ein Beispiel für die Lösung des Netflix-Preises mithilfe von Sparse-Matrizen finden Sie hier: http://bigcomputing.blogspot.de/2011/05/bryan-lewiss-vignette-on-irlba-for-svd.html

Marc in der Kiste
quelle
Danke für deine Kommentare. Tatsächlich hatte ich mir dieses Video gestern angesehen und auch das Paket irlba ausprobiert , aber anscheinend konnte es nur zur Berechnung einiger singulärer Werte verwendet werden. Wie in der Post angegeben, möchte ich jedoch ALLE Singular-Werte (120.000) berechnen , um die geeignete Anzahl von PCs entsprechend den Abweichungen zu wählen, die sie berücksichtigen. In diesem Fall ist irlba wohl nicht mehr geeignet.
Ensom Hodder
Können Sie die SVD-Ergebnisse auf ähnliche Weise wie PCA verwenden? Müssen Sie die Daten nicht VOR der SVD zentrieren, um eine PCA durchzuführen?
Zach
@Zach - SVD ist der Hauptalgorithmus hinter PCA (siehe prcomp - stat.ethz.ch/R-manual/R-patched/library/stats/html/prcomp.html ). Das Zentrieren von Daten ist ebenfalls ein Standardverfahren, bevor PCA angewendet wird, obwohl es je nach Ihrer Frage eine Vielzahl von Optionen gibt (z. B. können auch verschiedene Arten der Skalierung angewendet werden).
Marc in der Box
Wie groß ist der Deal, wenn ich die Daten nicht vor SVD zentriere? Ich habe eine spärliche Matrix, die in den Speicher passt, aber durch die Zentrierung würde sie dicht und zu groß, um in den Speicher zu passen.
Zach
@Zach - Es hängt wirklich davon ab, wie Sie Ihre Samples miteinander in Beziehung setzen möchten. Wenn Sie aufgrund von Speicherbeschränkungen nicht mit zentrierten Daten arbeiten können, wurde die Entscheidung vermutlich für Sie getroffen. Im Allgemeinen arbeitet die PCA beim Zentrieren von Daten mit einer Kovarianzmatrix der Abtastwerte, während die PCA beim Zentrieren und Skalieren von Daten mit einer Korrelationsmatrix arbeitet. Wenn Sie mehr über diese Entscheidungen erfahren möchten , können Sie unter stats.stackexchange.com eine Frage stellen oder die vorhandenen Antworten zu PCA durchsuchen.
Marc in der Box
8

Ich schlage vor, SLEPc zu verwenden, um eine partielle SVD zu berechnen. Weitere Informationen finden Sie in Kapitel 4 des Benutzerhandbuchs und in den Manpages zu SVD .

Jed Brown
quelle
1
Da er eine PCA möchte, muss er die Daten zentrieren, bevor er die SVD berechnet. Dies wird die Sparsamkeit zerstören. Gibt es eine Möglichkeit, wie SLEPc dies bewerkstelligt?
Dranxo
3
Das ist nur spärlich + niedriger Rang. SLEPc benötigt keine Matrixeinträge, nur einen linearen Operator, der als dünne Matrix plus Korrektur angewendet werden kann.
Jed Brown
2

Ich stimme für Mahout, das auch für andere NLP / TA-Aufgaben gut ist und map / reduction implementiert.

danas.zuokas
quelle
Ja, Sie haben recht, Mahout ist genau in meiner Straßenkarte. Aber ich bevorzuge es, einen Prototyp mit einigen "einfachen" (ich nehme an) Techniken im Voraus zu erstellen.
Ensom Hodder
1

Ich würde vorschlagen, eine inkrementelle Singulärwertzerlegung zu verwenden, von der es in der Literatur viele gibt. Zum Beispiel:

Alle diese Ansätze reduzieren sich auf Folgendes:

  • Beginnen Sie mit einem kleinen Datensatz
  • berechnen Sie eine SVD irgendwie (dieser Schritt ist für eine einzelne Spaltenmatrix trivial)
  • wiederhole bis fertig:
    • Neuen Datensatz hinzufügen
    • Verwenden Sie vorhandene SVD- und Aktualisierungsregeln, um die SVD des neuen Datensatzes zu berechnen

N

Geoff Oxberry
quelle
0

Sie können immer noch R verwenden.

Revolution Rist ein Build von R, der Datensätze verarbeitet, die größer als RAM sind. Nutzen Sie die Funktion princomp.

Es verfügt auch über eine Reihe von Statistikfunktionen, die speziell für Probleme mit Big Data-Stilen entwickelt wurden, die nicht in den Arbeitsspeicher passen, z. B. lineare Regression, logistische Regression, Quantile usw.

Sie können die Vollversion von Academic kostenlos herunterladen, indem Sie das Kästchen "Ich bin ein Akademiker" ankreuzen.

Contango
quelle