Ich möchte einen massiven Datensatz gruppieren, für den ich nur die paarweisen Abstände habe. Ich habe einen k-medoids-Algorithmus implementiert, dessen Ausführung jedoch zu lange dauert. Daher möchte ich zunächst die Dimension meines Problems durch Anwendung von PCA reduzieren. Die einzige Möglichkeit, diese Methode durchzuführen, ist die Verwendung der Kovarianzmatrix, die ich in meiner Situation nicht habe.
Gibt es eine Möglichkeit, PCA anzuwenden, wenn nur die paarweisen Abstände bekannt sind?
pca
dimensionality-reduction
multidimensional-scaling
großer Baum
quelle
quelle
Antworten:
Update: Ich habe meine ursprüngliche Antwort vollständig entfernt, da sie auf einer Verwechslung zwischen euklidischen Abständen und skalaren Produkten beruhte. Dies ist eine neue Version meiner Antwort. Entschuldigung.
Wenn Sie mit paarweisen Abständen euklidische Abstände meinen, dann gibt es eine Möglichkeit, PCA durchzuführen und Hauptkomponenten zu finden. Ich beschreibe den Algorithmus in meiner Antwort auf die folgende Frage: Was ist der Unterschied zwischen Hauptkomponentenanalyse und mehrdimensionaler Skalierung?
Sehr kurz kann die Matrix der euklidischen Abstände in eine zentrierte Gram-Matrix umgewandelt werden, die direkt verwendet werden kann, um eine PCA über eine Eigenzerlegung durchzuführen. Dieses Verfahren ist als [klassische] mehrdimensionale Skalierung (MDS) bekannt .
Wenn Ihre paarweisen Abstände nicht euklidisch sind, können Sie keine PCA durchführen, aber dennoch MDS, was nicht mehr der PCA entspricht. In dieser Situation ist MDS jedoch wahrscheinlich noch besser für Ihre Zwecke.
quelle
PCA mit einer Distanzmatrix existiert und wird als Multi-Dimensional Scaling (MDS) bezeichnet. Sie können mehr auf Wikipedia oder erfahren in diesem Buch .
Sie können dies
Rmit der mds-Funktion tuncmdscale. Für ein Beispielxkönnen Sie dies überprüfenprcomp(x)undcmdscale(dist(x))das gleiche Ergebnis liefern (woprcompführt PCA unddistberechnet nur die euklidischen Abstände zwischen Elementen von x)quelle
Dies scheint ein Problem zu sein, auf das spektrale Cluster angewendet werden könnten. Da Sie die paarweise Abstandsmatrix haben, können Sie einen vollständig verbundenen Graphen definieren, in dem jeder Knoten N Verbindungen hat, entsprechend seiner Entfernung von jedem anderen Knoten im Graphen. Daraus können Sie den Laplace-Graphen berechnen (wenn dies beängstigend klingt, keine Sorge - es ist eine einfache Berechnung) und dann Eigenvektoren der kleinsten nehmenEigenwerte (hier unterscheidet es sich von PCA). Wenn Sie zum Beispiel 3 Eigenvektoren nehmen, haben Sie eine Nx3-Matrix. In diesem Raum sollten die Punkte (hoffentlich) aufgrund einer sauberen Graphentheorie gut getrennt sein, was darauf hindeutet, dass dies ein optimaler Schnitt zur Maximierung des Flusses (oder in diesem Fall der Entfernung) zwischen Clustern ist. Von dort aus können Sie ein k-means oder einen ähnlichen Algorithmus verwenden, um im 3-Raum zu gruppieren. Ich empfehle, diese großartige Anleitung zu lesen, um weitere Informationen zu erhalten:
http://arxiv.org/abs/0711.0189
quelle
Die paarweisen Abstände bilden ebenso wie die Kovarianzmatrix eine quadratische Matrix. PCA ist nur eine SVD ( http://en.wikipedia.org/wiki/Singular_value_decomposition ), die auf die Co-Varianz-Matrix angewendet wird. Sie sollten weiterhin in der Lage sein, Ihre Daten mithilfe von SVD zu verkleinern. Ich bin mir nicht ganz sicher, wie ich Ihre Ausgabe interpretieren soll, aber es ist definitiv etwas, das Sie ausprobieren sollten. Sie können Clustering-Methoden wie k-means oder hierarchisches Clustering verwenden. Schauen Sie sich auch andere Techniken zur Dimensionsreduzierung an, z. B. die mehrdimensionale Skalierung. Was versuchst du aus deinen Clustern herauszuholen?
quelle