Ich habe dies zuvor bei StackOverflow gefragt, aber es scheint, als wäre es hier angemessener, da es auf SO keine Antworten gab. Es ist eine Art Schnittstelle zwischen Statistik und Programmierung.
Ich muss Code schreiben, um PCA (Principal Component Analysis) durchzuführen. Ich habe die bekannten Algorithmen durchgesehen und diese implementiert , was, soweit ich das beurteilen kann, dem NIPALS-Algorithmus entspricht. Es funktioniert gut, um die ersten 2-3 Hauptkomponenten zu finden, scheint dann aber sehr langsam zu konvergieren (in der Größenordnung von Hunderten bis Tausenden von Iterationen). Hier sind die Details von dem, was ich brauche:
Der Algorithmus muss effizient sein, wenn eine große Anzahl von Merkmalen (in der Größenordnung von 10.000 bis 20.000) und Stichprobengrößen in der Größenordnung von wenigen Hundert verarbeitet werden.
Es muss ohne eine anständige lineare Algebra / Matrix-Bibliothek einigermaßen implementierbar sein, da die Zielsprache D ist, für die es noch keine gibt, und selbst wenn dies der Fall ist, würde ich es vorziehen, es nicht als Abhängigkeit zum betreffenden Projekt hinzuzufügen .
Nebenbei bemerkt, scheint R im selben Datensatz alle Hauptkomponenten sehr schnell zu finden, verwendet jedoch eine Singularwertzerlegung, die ich nicht selbst codieren möchte.
Antworten:
Ich habe die randomisierte SVD implementiert, wie in "Halko, N., Martinsson, PG, Shkolnisky, Y. & Tygert, M. (2010) angegeben. Ein Algorithmus für die Hauptkomponentenanalyse großer Datensätze. Arxiv preprint arXiv: 1007.5510, 0526. Abgerufen am 1. April 2011 von http://arxiv.org/abs/1007.5510 . " Wenn Sie eine abgeschnittene SVD erhalten möchten, arbeitet diese sehr viel schneller als die svd-Variationen in MATLAB. Sie können es hier bekommen:
Erstellen Sie zum Testen einfach ein Bild in demselben Ordner (Sie können die Matrix auch als große Matrix selbst erstellen).
Wenn ich es auf meinem Desktop für ein Image der Größe 635 * 483 ausführe, erhalte ich
Wie Sie sehen, ist es bei niedrigen Werten von
k
mehr als 10-mal schneller als bei Verwendung von Matlab SVD. Übrigens benötigen Sie möglicherweise die folgende einfache Funktion für die Testfunktion:Ich habe die PCA-Methode nicht hinzugefügt, da die Implementierung mit SVD unkompliziert ist. Sie können diesen Link überprüfen , um ihre Beziehung zu sehen.
quelle
Sie könnten versuchen, mit ein paar Optionen.
1- Bestrafte Matrixzersetzung . Sie wenden einige Strafbedingungen auf die u und v an, um eine gewisse Sparsamkeit zu erzielen. Schneller Algorithmus, der für Genomdaten verwendet wurde
Siehe Whitten Tibshirani. Sie haben auch ein R-Päckchen. "Eine bestrafte Matrixzerlegung mit Anwendungen für spärliche Hauptkomponenten und kanonische Korrelationsanalyse."
2- Randomisierte SVD . Da SVD ein Master-Algorithmus ist, kann eine sehr schnelle Approximation wünschenswert sein, insbesondere für die explorative Analyse. Mit randomisierter SVD können Sie PCA für große Datasets durchführen.
Siehe Martinsson, Rokhlin und Tygert "Ein randomisierter Algorithmus zur Zerlegung von Matrizen". Tygert hat Code für eine sehr schnelle Implementierung von PCA.
Unten sehen Sie eine einfache Implementierung der randomisierten SVD in R.
quelle
Es hört sich so an, als ob Sie den Lanczos-Algorithmus verwenden möchten . Andernfalls können Sie sich an Golub & Van Loan wenden. Ich habe einmal einen SVD-Algorithmus (aus allen Sprachen in SML) aus ihrem Text codiert, und er hat einigermaßen gut funktioniert.
quelle
Ich würde vorschlagen, Kernel-PCA zu testen, dessen zeitliche / räumliche Komplexität von der Anzahl der Beispiele (N) und nicht von der Anzahl der Features (P) abhängt. Kernel-PCA arbeitet grundsätzlich mit der NxN-Kernelmatrix (Matrix der Ähnlichkeiten zwischen den Datenpunkten) und nicht mit der PxP-Kovarianzmatrix, die für große P schwer zu handhaben ist. Ein weiterer Vorteil von Kernel-PCA ist, dass es nichtlineare Projektionen lernen kann auch, wenn Sie es mit einem geeigneten Kernel verwenden. Siehe dieses Papier über Kernel-PCA .
quelle
Ich erinnere mich, dass es möglich ist, PCA durchzuführen, indem man die Eigenzerlegung von X ^ TX anstelle von XX ^ T berechnet und dann transformiert, um die PCs zu erhalten. Ich kann mich jedoch nicht an die Details erinnern, aber es ist in Jolliffes (ausgezeichnetem) Buch und ich werde es nachschlagen, wenn ich das nächste Mal bei der Arbeit bin. Ich würde die linearen Algebra-Routinen von zB Numerical Methods in C transliterieren, anstatt irgendeinen anderen Algorithmus zu verwenden.
quelle
Es gibt auch die Bootstrap-Methode von Fisher et al. , Die für mehrere hundert Proben mit hohen Abmessungen ausgelegt ist.
Die Hauptidee der Methode lautet: "Resampling ist eine Transformation mit geringer Dimension". Wenn Sie also nur wenige (mehrere Hundert) hochdimensionale Proben haben, können Sie nicht mehr Hauptkomponenten als die Anzahl Ihrer Proben erhalten. Es ist daher sinnvoll, die Stichproben als sparsame Grundlage zu betrachten, die Daten auf den linearen Unterraum zu projizieren, der von diesen Vektoren überspannt wird, und die PCA innerhalb dieses kleineren Unterraums zu berechnen. Sie enthalten auch weitere Informationen zum Umgang mit dem Fall, dass möglicherweise nicht alle Proben im Speicher abgelegt sind.
quelle
Siehe Sam Roweis 'Artikel, EM-Algorithmen für PCA und SPCA .
quelle