Unterschied zwischen Scikit-Learn-Implementierungen von PCA und TruncatedSVD

12

Ich verstehe die Beziehung zwischen Hauptkomponentenanalyse und Singularwertzerlegung auf algebraischer / exakter Ebene. Meine Frage bezieht sich auf die Implementierung von Scikit-Learn .

In der Dokumentation heißt es: " [TruncatedSVD] ist PCA sehr ähnlich, arbeitet jedoch direkt mit Stichprobenvektoren anstatt mit einer Kovarianzmatrix. " Dies würde den algebraischen Unterschied zwischen beiden Ansätzen widerspiegeln. Später heißt es jedoch: " Dieser Schätzer [TruncatedSVD] unterstützt zwei Algorithmen: einen schnell randomisierten SVD-Löser und einen" naiven "Algorithmus, der ARPACK als Eigensolver für (X * XT) oder (XT * X) verwendet, je nachdem, welcher Wert höher ist effizient. ". In Bezug auf PCAheißt es: "Lineare Dimensionsreduktion unter Verwendung der Singularwertzerlegung der Daten, um sie zu projizieren ...". Die PCA-Implementierung unterstützt dieselben zwei Algorithmen (randomisiert und ARPACK) sowie einen weiteren, LAPACK. Wenn ich mir den Code anschaue, kann ich sehen, dass sowohl ARPACK als auch LAPACK in PCA und TruncatedSVD auf Beispieldaten X svd ausführen, wobei ARPACK in der Lage ist, mit spärlichen Matrizen umzugehen (unter Verwendung von svds).

Abgesehen von verschiedenen Attributen und Methoden und der Tatsache, dass PCA zusätzlich eine exakte vollständige Singularwertzerlegung mit LAPACK durchführen kann, scheinen PCA- und TruncatedSVD-Scikit-Learn-Implementierungen genau der gleiche Algorithmus zu sein. Erste Frage: Ist das richtig?

Zweite Frage: Obwohl LAPACK und ARPACK scipy.linalg.svd (X) und scipy.linalg.svds (X) verwenden und X die Stichprobenmatrix sind, berechnen sie die Singularwertzerlegung oder Eigenzerlegung von oder X. X T intern. Während der "zufällige" Löser das Produkt nicht berechnen muss. (Dies ist im Zusammenhang mit der numerischen Stabilität relevant, siehe Warum PCA von Daten mittels SVD der Daten? ). Ist das richtig?XTXXXT

Relevanter Code: PCA- Zeile 415. TruncatedSVD- Zeile 137.

Erpel
quelle
1
Könnten
1
Drake - Ich glaube, ich stimme dir in der ersten Frage zu. Verstehe die zweite nicht. Was meinst du mit "sie berechnen die Singularwertzerlegung oder Eigenzerlegung von XT ∗ XXT ∗ X oder X ∗ XTX ∗ XT intern" - Sie haben gerade den Code gezeigt, in dem alles mit SVD auf X ausgeführt wird? - Numerische Probleme beziehen sich darauf, zuerst die Kovarianzmatrix zu berechnen (nennen
wir
@ seanv507 In Bezug auf die 2. Frage - Ich denke, dass scipy.linalg.svd (X) die svd berechnet, indem die Eigenzerlegung von oder / und X X T durchgeführt wird . Gleiches gilt für linalg.svds (X). Zitat: "Ein schnell randomisierter SVD-Löser und ein" naiver "Algorithmus, der ARPACK als Eigensolver für (X * XT) oder (XT * X) verwendet". Siehe auch letzte Zeile in docs.scipy.org/doc/scipy/reference/generated/… . Der einzige Weg, wie ich das erste Zitat verstehen kann, ist, dass der randomisierte Algorithmus der einzige ist, der die Kovarianz / Gramm-Matrix nicht berechnetXTXXXT
Drake
1
XXtimes()Xt_times()
@ GeoMatt22 Kannst du deinen Kommentar näher erläutern? Meinen Sie damit, dass ARPACK- oder LAPACK-Ansätze nicht unter numerischen Instabilitäten leiden, weil sie die Kovarianzmatrix nicht berechnen müssen?
Drake

Antworten:

13

PCA- und TruncatedSVD-Scikit-Learn-Implementierungen scheinen genau der gleiche Algorithmus zu sein.

Nein: PCA ist (abgeschnitten) SVD für zentrierte Daten (durch mittlere Subtraktion pro Merkmal). Wenn die Daten bereits zentriert sind, machen diese beiden Klassen dasselbe.

In der Praxis TruncatedSVDist dies bei großen, spärlichen Datensätzen hilfreich, die nicht zentriert werden können, ohne dass die Speichernutzung explodiert.

  • numpy.linalg.svdund scipy.linalg.svdbeide verlassen sich auf LAPACK _GESDD, das hier beschrieben wird: http://www.netlib.org/lapack/lug/node32.html (Treiber teilen und erobern)

  • scipy.sparse.linalg.svdsstützt sich auf ARPACK, um eine Eigenwertzerlegung von XT durchzuführen. X oder X. XT (abhängig von der Form der Daten) über die Arnoldi-Iterationsmethode. Das HTML-Benutzerhandbuch von ARPACK weist eine fehlerhafte Formatierung auf, die die Berechnungsdetails verbirgt. Die Arnoldi-Iteration ist jedoch auf Wikipedia gut beschrieben: https://en.wikipedia.org/wiki/Arnoldi_iteration

Hier ist der Code für die ARPACK-basierte SVD in scipy:

https://github.com/scipy/scipy/blob/master/scipy/sparse/linalg/eigen/arpack/arpack.py#L1642 (Suche nach der Zeichenfolge für "def svds" im Falle einer Zeilenänderung im Quellcode ).

Ogrisel
quelle
2
Einer kann spärliche Daten effizient unterstützen (TruncatedSVD), der andere nicht (PCA). Deshalb haben wir 2 Klassen.
Ogrisel
1
Wenn das der Grund ist, würde ich sie SVD und SparseSVD (oder ähnliches) nennen, um Verwirrung zu vermeiden.
Drake
2
Aber die Leute wollen PCA und sie wissen möglicherweise nicht, dass PCA nur SVD für zentrierte Daten ist.
Ogrisel
5
@drake Ich bin nicht der Meinung, dass "die Verfahren unterschiedlich sind (PCA verwendet Kovarianzmatrix und SVD verwendet Datenmatrix)". PCA ist ein Name für die Art der Analyse. Man kann verschiedene Algorithmen und Implementierungen verwenden, um es auszuführen. EIG der cov-Matrix ist eine Methode, SVD der zentrierten Datenmatrix ist eine andere Methode, und dann können EIG und SVD auch mit verschiedenen Methoden durchgeführt werden. Egal - das alles ist PCA.
Amöbe sagt Reinstate Monica
1
@amoeba Danke für die Klarstellung / Korrektur der Terminologie. Was Sie sagen, ist für mich sinnvoller, da SVD und EIG algebraische Theoreme / Methoden mit einem breiteren Anwendungsbereich als PCA sind
Drake