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

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?

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.

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 Seite$k$

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.

@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 .

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 mehrdimensionale Skalierung 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.

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 $D_{ij}$$D_{ji}$
3. zentriere es (dh subtrahiere den Mittelwert von Zeile und Spalte) um$D^c$
4. Berechne$S^c = -\frac{1}{2}D^c$
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$S^c$$S^c$$\tilde S^c$
6. Berechnen Sie die Eigenvektorzerlegung von .$\tilde S^c = V \Lambda V^\top$
7. Stellen Sie eine Vektordarstellung in einem dimensionalen metrischen Raum Ihrer Daten wieder her: .X = V Λ 1 /$n-1$$X = V\Lambda^{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$

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.

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.

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

• Numerische Ökologie (Pierre Legendre und Louis Legendre): http://www.sciencedirect.com/science/bookseries/01678892/20 oder http://tinyurl.com/cgrdfqk (Google Books) - Kapitel über "Ökologische Ähnlichkeit"
• Clusteranalyse (Brian S. Everitt, Sabine Landau, Daniel Stahl, Morven Leese): http://tinyurl.com/bld7k8h (google books) - Kapitel 'Messung der Nähe'
• Kurs 'Biostatistik-II, Multivariate Methoden' von Prof. Brian C. McCarthy an der Ohio University: http://www.ohio.edu/plantbio/staff/mccarthy/multivariate/multivariate.htm

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