PCA nur mit einer Distanzmatrix durchführen

12

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?

großer Baum
quelle
1
Sie haben also eine große quadratische Matrix von Abständen zwischen den Punkten, die Sie gruppieren möchten. (Übrigens, welche Entfernung? Euklidisch?) Was lässt Sie denken, dass es die Anzahl der Dimensionen ist, die diese Punkte umfassen, und nicht die Anzahl der Punkte selbst (Kardinalität), die die Clusterbildung behindert?
ttnphns
1
Die Anzahl der Punkte ist nicht "sehr groß" (wenige Tausend). Die Entfernung, die ich benutze, ist die Pearson-Korrelation zwischen diesen Punkten
bigTree
2
Aber meine Frage war: Wollen Sie wirklich die Dimensionalität (und wenn ja, warum?) Oder die Kardinalität (die Anzahl der Punkte) reduzieren ? Weil deine Frage unklar ist .
ttnphns
1
@ttnphns: Oh Mann, natürlich habe ich meinen vorherigen Kommentar einfach falsch geschrieben. Um die mögliche Verwirrung zu beseitigen, werde ich diesen Kommentar jetzt löschen und das, was ich hier gesagt habe, mit korrektem Wortlaut wiederholen: "In diesem Fall bedeutet das Verringern der Kardinalität, dass Ihre Abstandsmatrix kleiner wird (abnehmendes N ). Das Verringern der Dimensionalität bedeutet, dass sie verringert wird Rang, ohne N. zu ändern . PCA beläuft sich auf Letzteres und hilft beim ersteren Ziel nicht wirklich ". N.×N.N.N.
Amöbe sagt Reinstate Monica
1
Ich denke, dass der einfachste Weg für Sie darin besteht, eine solche (a) Clustering-Methode oder (b) eine solche Implementierung oder (c) einen so starken (ausreichend RAM) Computer zu verwenden, der 6000 Objekte aufnehmen und klassifizieren kann (ich weiß nicht, warum Ihre Medoid-Programm findet es schwierig. 6000 ist groß, aber nicht sehr groß.). Einige Methoden (wie K-Mittel) erfordern Daten zu Objekten X-Merkmalen. Sie können solche Daten aus der Objektentfernungsmatrix über ein metrisches MDS erstellen (wenn Ihr Computer / MDS-Programm wiederum 6000 Objekte zulässt).
ttnphns

Antworten:

8

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.

Amöbe sagt Reinstate Monica
quelle
Die Entfernung, die ich verwende, ist eine Korrelation (Pearson-Korrelation) und daher nicht die euklidische Entfernung. Würde das ähnlich funktionieren?
BigTree
1
@bigTree: Wenn es keine euklidische Entfernung ist, können Sie PCA auf keinen Fall ausführen. Sie können jedoch die mehrdimensionale Skalierung verwenden, bei der es sich um eine Technik zur Reduzierung der Dimensionalität handelt, bei der genau die Matrix der paarweisen Abstände verwendet wird (es kann sich um einen beliebigen Abstand handeln). Noch ein Hinweis: Unter bestimmten Annahmen über die ursprünglichen Datenpunkte (die Sie nicht haben) können Korrelationen in euklidische Abstände umgewandelt werden. Annahmen sind: (1) mit einem Mittelwert von Null, (2) mit einer festen, z. B. Einheit, Länge. Trifft dies zufällig auf Ihre Daten zu?
Amöbe sagt Reinstate Monica
Nichts davon ist wahr oder meine Daten, aber ich werde MDS versuchen, danke
bigTree
1
Kannst du nicht Kernel PCA verwenden? Ich stelle mir vor, dass nur paarweise Punktprodukte benötigt würden, aber ich weiß nicht viel über das Problem, also weiß ich nicht, ob es Sinn macht
rep_ho
4

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 tun cmdscale. Für ein Beispiel xkönnen Sie dies überprüfen prcomp(x)und cmdscale(dist(x))das gleiche Ergebnis liefern (wo prcompführt PCA und distberechnet nur die euklidischen Abstände zwischen Elementen von x)

Pop
quelle
3

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

Christopher Krapu
quelle
0

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?

Andrew Cassidy
quelle
Andrew Cassidys Antwort ist tatsächlich gültig. Wenn Ihr Abstandsmaß die Pearson-Korrelation ist, sind Sie nur ein Standardisierungsfaktor "zu weit" von einer tatsächlichen Kovarianzmatrix entfernt. Das Anwenden von SVD ist also im Grunde dasselbe wie das Ausführen von PCA.
Matthew Anthony