Führen Sie K-Means-Clustering (oder ein Clustern seiner nahen Verwandten) nur mit einer Distanzmatrix durch, nicht mit Daten zu Punkten nach Merkmalen

22

Ich möchte K-Means-Clustering für Objekte ausführen, die ich habe, aber die Objekte werden nicht als Punkte im Raum beschrieben, dh nach objects x featuresDatensatz. Ich kann jedoch den Abstand zwischen zwei beliebigen Objekten berechnen (er basiert auf einer Ähnlichkeitsfunktion). Also verfüge ich über die Distanzmatrix objects x objects.

Ich habe K-means bereits implementiert, aber das geschah mit der Eingabe von Punktedatensätzen. und mit der Distanzmatrixeingabe ist mir nicht klar, wie ich die Cluster aktualisieren kann, um die Cluster- "Zentren" ohne Punktdarstellung zu sein. Wie würde das normalerweise gemacht werden? Gibt es dafür Versionen von K-Mitteln oder Methoden in der Nähe?

Maus
quelle
Was meinst du da nicht als Punkte beschrieben?
neugierig

Antworten:

24

Offensichtlich k-Mittel - Bedürfnisse in der Lage sein zu berechnen Mittel .

Es gibt jedoch eine bekannte Variante, die als k-Medoide oder PAM (Partitioning Around Medoids) bezeichnet wird, bei der das Medoid das vorhandene Objekt ist, das für den Cluster am zentralsten ist. K-medoids benötigt nur die paarweisen Abstände.

Anony-Mousse
quelle
21

Sie beschreiben genau die Problemeinstellung von Kernel- Mitteln; Wenn Sie einen Datenpunkt nicht als euklidischen Vektor darstellen können, aber das innere Produkt zwischen zwei Datenpunkten immer noch berechnen (oder definieren) können, können Sie den Algorithmus kernelisieren . Die folgende Webseite enthält eine kurze Beschreibung des Algorithmus:k

Kernel bedeutet Seitek

Dieser Kernel-Trick ist eine sehr beliebte und grundlegende Idee in der Statistik und im maschinellen Lernen.

Wiki-Seite zum Kernel-Trick

Bei Interesse ist das Buch Lernen mit Kernen von Bernhard Schölkopf und Alexander J. Smola eine sehr schöne Einführung.

Diese Notiz von Max Welling scheint sehr nett zu sein; Wenn Sie R verwenden, können Sie sich auch dieses R-Paket ansehen .

MDS ist zwar eine Möglichkeit, Ihr Problem zu lösen, greift das zu lösende Problem jedoch nicht direkt an. während kernel k-means es tut.

d_ijk_stra
quelle
Ich wollte mehr Links einbinden, konnte es aber aufgrund des schlechten Rufs nicht. Dieser Hinweis von Max Welling Note scheint sehr nett; Wenn Sie R verwenden, können Sie sich auch dieses R-Paket
ansehen
(+1) Willkommen auf der Seite. Ich habe die Links in Ihrem Kommentar zum Hauptteil des Beitrags sowie einen zum Schölkopf- und Smola-Text hinzugefügt.
Kardinal
9

@gung ist absolut korrekt und empfiehlt Ihnen die multidimensionale Skalierung (MDS) als vorläufiges Tool zum Erstellen von points X dimensions Daten außerhalb der Entfernungsmatrix. Ich möchte nur ein paar Striche hinzufügen. K-bedeutet Clustering impliziert euklidische Abstände . MDS gibt Ihnen Koordinaten von Punkten in Dimensionen und garantiert Ihnen so euklidische Abstände. Verwenden Sie das metrische MDB und fordern Sie eine möglichst große Anzahl von Dimensionen an, da Ihr Ziel darin besteht, Fehler bei der Rekonstruktion der Daten zu minimieren und diese nicht in 2D oder 3D abzubilden.

Was ist, wenn Sie keine MDS-Software zur Hand haben, aber einige Matrixfunktionen wie Eigenwertzerlegung oder Singulärwertzerlegung haben? Dann können Sie ein einfaches metrisches MDS selbst erstellen - Torgerson MDS, auch bekannt als Principal Coordinates Analysis (PCoA). Es handelt sich um eine etwas "verdrehte" Hauptkomponentenanalyse. Ich werde es hier nicht beschreiben, obwohl es recht einfach ist. Sie können an vielen Stellen darüber lesen, zB hier .

Schließlich ist es möglich, "K-Mittel für Distanzmatrix-Eingabe" direkt zu programmieren - ohne Funktionen aufzurufen oder zu schreiben, die PCoA oder ein anderes metrisches MDS ausführen. Wir wissen, dass (a) die Summe der quadratischen Abweichungen vom Schwerpunkt gleich der Summe der paarweisen quadratischen euklidischen Abstände geteilt durch die Anzahl der Punkte ist; und (b) wissen, wie Entfernungen zwischen Cluster-Schwerpunkten aus der Entfernungsmatrix berechnet werden ; (c) und wir wissen weiter, wie Quadratsummen in K-Mitteln zusammenhängen. Alles zusammen macht das Schreiben des gewünschten Algorithmus zu einem unkomplizierten und nicht zu einem komplexen Unterfangen. Man sollte sich jedoch daran erinnern, dass das K-Mittel nur für euklidische Entfernungen / euklidischen Raum gilt. Verwenden Sie K-Medoide oder andere Methoden für nicht-euklidische Abstände.

Eine ähnliche Frage .

ttnphns
quelle
7

Ich weiß mit Sicherheit nicht, wie es "normal" gemacht wird, und vor allem weiß ich nicht viel über Clusteranalyse. Kennen Sie sich jedoch mit mehrdimensionaler Skalierung aus ? ( Hier ist eine weitere Referenz, das Wiki , und Sie können den Lebenslauf unter dem Tag für die suchen .) Bei der mehrdimensionalen Skalierung wird eine Matrix von paarweisen Abständen verwendet, die sich nach Ihrer Situation anhört. Aus dem MDB können Sie die Positionen der Objekte im niedrigsten Raum abrufen, um sie angemessen darzustellen. Ich würde vermuten, dass Sie diese Orte verwenden könnten, um eine nachfolgende Cluster-Analyse wie k-means durchzuführen. Alternativ benötigen Sie die Zertifizierungsstelle möglicherweise nicht mehr, sobald Sie die Ausgabe erhalten haben.

Ich weiß nicht, ob Sie R verwenden, aber hier ist die Aufgabenansicht für Psychometrics, die einen Abschnitt zu MDS in R enthält. Hoffe, dass dies hilft.

gung - Wiedereinsetzung von Monica
quelle
4

Optimale Clusterbewahrung Die Einbettung von nichtmetrischen Näherungsdaten sollte zu Ihrem Fall passen. Der Artikel zeigt, wie Sie eine metrische Vektordarstellung Ihrer Objekte erhalten können, wenn nur eine Matrix der paarweisen Unähnlichkeitsfunktion gegeben ist, sodass die Clusterzuweisungen für eine Reihe von Cluster-Algorithmen, einschließlich Mittelwerten , erhalten bleiben.k

In Ihrem Fall müssen Sie im Grunde Folgendes tun:

  1. Haben Sie Ihre Unähnlichkeitsmatrix mit null Unähnlichkeit.D
  2. Falls es noch nicht symmetrisch ist, symmetrieren Sie durch Mitteln von und . D j iDijDji
  3. zentriere es (dh subtrahiere den Mittelwert von Zeile und Spalte) umDc
  4. BerechneSc=12Dc
  5. Führen Sie eine spektrale Verschiebung: subtrahieren Sie die ‚s kleinsten Eigen von ‘ s Spektrum zu gewährleisten , ist es positiv semidefinite wird. Tun Sie dies, um .S c ˜ S cScScS~c
  6. Berechnen Sie die Eigenvektorzerlegung von .S~c=VΛV
  7. Stellen Sie eine Vektordarstellung in einem dimensionalen metrischen Raum Ihrer Daten wieder her: .X = V Λ 1 / 2n1X=VΛ1/2

Dies setzt voraus, dass nicht zu groß ist. Wenn dies der Fall ist, erhalten Sie durch das Ausführen von PCA eine aussagekräftigere Darstellung der Daten. (Das Papier beschreibt auch, wie das geht).n

blubb
quelle
Die beschriebenen Schritte sind nichts weniger als die Hauptkoordinatenanalyse, die ich in meiner Antwort erwähne.
TTNPHNS
Bitte veranschaulichen Sie Ihren Schritt 5. Das Subtrahieren des letzten (negativen) Eigenwerts / der letzten) Eigenwerte von S-Matrixelementen scheint nicht dazu beizutragen, S positiv semidefinit zu machen.
TTNPHNS
@ttnphns: Grundsätzlich handelt es sich um PCA, aber es ist nicht erforderlich, dass die Entfernungen metrisch sind. Die Beschreibung von Schritt 5 war unglücklich, danke, dass Sie ihn entdeckt haben. Ist es jetzt klar?
Blubb
Das Subtrahieren der Summe der negativen Eigenwerte von allen Eigenwerten und dann der S-Matrix für die Wiederherstellung entspricht dem Subtrahieren dieser Summe von den diagonalen Elementen von S. Dies macht S positiv (halb) definit, aber ...
ttnphns
... aber dieser Weg ist sehr schlecht in dem Sinne, dass die resultierenden euklidischen Daten X euklidische Abstände D_new erzeugen, die sehr weit von den ursprünglichen Unähnlichkeiten D entfernt sind. Ich würde also Ihren Schritt 5 nicht empfehlen. Es scheint viel besser, einfach negativ zu setzen Eigenwerte auf 0 setzen und mit Schritt 7 fortfahren. Oder etwas feinerer Ansatz: Negative Eigenwerte auf 0 setzen, positive Eigenwerte neu skalieren, damit sie als Summe original sind (= Kurve (S)), und dann mit Schritt 7 fortfahren mir.
TTNPHNS
2

Ihre Daten können auch als Netzwerk angezeigt werden, und Sie können einen der vielen verfügbaren Netzwerk-Clustering-Algorithmen verwenden. Dazu müssten Sie wahrscheinlich einen Schwellenwert auf die Kantengewichte anwenden und Abstände in Ähnlichkeiten umwandeln. Dies ist keine statistische Methode, aber die Clusteranalyse ist anfangs ein unterbestimmtes Problem, und als explorative Tools bieten Netzwerk-Cluster-Algorithmen eine sehr gute Leistung.

micans
quelle
2

Ich weiß nicht, warum dies in der Literatur so ungewöhnlich ist, aber die von @gung und @ttnphns vorgeschlagene Lösung (zuerst die paarweisen Abstände mit Hilfe der Hauptkoordinatenanalyse in einen euklidischen Raum projizieren, z. B. durch dieses Paket, wenn Sie R verwenden, und dann) (K-bedeutet auf übliche Weise) ist einfach und erfordert keine speziellen Algorithmen. Ich persönlich habe es hier in ein Optimierungsframework eingebettet und es hat ziemlich gut funktioniert.

Francesco Napolitano
quelle
1

In Bezug auf Clustering und MDS würde ich die folgenden Ressourcen vorschlagen:

Diese Referenzen decken auch die Themen Ähnlichkeits- und Abstandsfunktionen (Näherungsmaße) für binäre und kontinuierliche Daten gut ab.

user1137731
quelle