Kann mich jemand auf eine k-means-Implementierung hinweisen (besser in matlab), die die Distanzmatrix als Eingabe verwenden kann? Die Standard-Matlab-Implementierung benötigt die Beobachtungsmatrix als Eingabe und es ist nicht möglich, das Ähnlichkeitsmaß benutzerdefiniert zu ändern.
clustering
matlab
k-means
Eugenio
quelle
quelle
Antworten:
Da k-means in der Lage sein muss, die Mittelwerte verschiedener Teilmengen der Punkte zu finden, die Sie gruppieren möchten, ist es nicht sinnvoll, nach einer Version von k-means zu fragen, die eine Distanzmatrix als Eingabe verwendet.
Sie könnten stattdessen k-medoids versuchen . Es gibt einige Matlab-Implementierungen .
quelle
Sie können Ihre Entfernungsmatrix in Rohdaten umwandeln und diese in das K-Means-Clustering eingeben. Die Schritte wären wie folgt:
1) Die Abstände zwischen Ihren N Punkten müssen euklidisch quadriert werden. Führen Sie eine " doppelte Zentrierung " der Matrix durch: Subtrahieren Sie den Zeilenmittelwert von jedem Element. im Ergebnis wird der Mittelwert der Spalte von jedem Element abgezogen; Addieren Sie im Ergebnis den Mittelwert der Matrix zu jedem Element. Teilen Sie durch minus 2. Die Matrix, die Sie jetzt haben, ist die SSCP-Matrix (Summe aus Quadraten und Kreuzprodukt) zwischen Ihren Punkten, wobei der Ursprung am geometrischen Mittelpunkt der Wolke aus N Punkten liegt. (Lesen Erklärung der Doppelzentrierung hier .)
2) Führen PCA (Hauptkomponentenanalyse) und auf dieser Matrix erhalten NxN Komponente Lade Matrix. Einige der letzten Spalten davon sind wahrscheinlich alle 0, - schneiden Sie sie ab. Bei dem, was Sie jetzt behalten, handelt es sich tatsächlich um Hauptkomponenten-Scores, die Koordinaten Ihrer N-Punkte auf Hauptkomponenten, die als Achsen durch Ihre Cloud verlaufen. Diese Daten können als Rohdaten behandelt werden, die für die K-Means-Eingabe geeignet sind.
PS Wenn Ihre Abstände nicht geometrisch korrekt sind, können Sie auf ein Problem stoßen: Die SSCP-Matrix ist möglicherweise nicht positiv (semidefinit). Dieses Problem kann auf verschiedene Arten, jedoch mit Genauigkeitsverlust, bewältigt werden.
quelle
X(sagen wir mal N * N) symmetrisch sein wird, so ,colMeans(X) =rowMeans(X)und wenn Sie subtrahieren Zeile oder Spalte bedeutet:Y=X-rowMeans(X),mean(Y)ist 0.You could turn your matrix of distances into raw data(Punkte 1 und 2), beziehe ich mich im Wesentlichen auf Torgersons mehrdimensionale Skalierung (MDS) , bei der die doppelte Zentrierung der erste Schritt ist. Bitte durchsuchen Sie diese Website (und auch Google) nach Informationen zu diesem Vorgang. "Doppelte Zentrierung" ist die Umwandlung von (quadratischen) Abständen in die entsprechende Skalarproduktmatrix, die über dem Ursprung definiert ist, der in den Schwerpunkt der Punktwolke eingetragen ist.Bitte beachten Sie diesen Artikel, der von einem meiner Bekannten verfasst wurde;)
http://arxiv.org/abs/1304.6899
Es handelt sich um eine verallgemeinerte k-Means-Implementierung, die eine beliebige Distanzmatrix als Eingabe verwendet. Es kann sich um eine beliebige symmetrische nichtnegative Matrix mit einer Nulldiagonale handeln. Beachten Sie, dass es für seltsame Entfernungsmatrizen möglicherweise keine vernünftigen Ergebnisse gibt. Das Programm ist in C # geschrieben.
Der Quellcode kann über den obigen Link abgerufen werden, indem Sie auf Andere Formate und dann auf Quelle herunterladen klicken. Dann erhalten Sie eine .tar.gz mit Program.cs. Alternativ kann der Quellcode auch aus dem PDF kopiert werden.
quelle
Sie können die Java Machine Learning Library verwenden. Sie haben eine K-Means-Implementierung. Einer der Konstruktoren akzeptiert drei Argumente
Sie können die DistanceMeasure-Klasse problemlos erweitern, um das gewünschte Ergebnis zu erzielen. Die Idee ist, Werte aus einer benutzerdefinierten Distanzmatrix in der Measure-Methode (Instanz x, Instanz y) dieser Klasse zurückzugeben.
Es ist garantiert, dass K-Means unter Annahme bestimmter Eigenschaften der Abstandsmetrik konvergiert. Euklidische Entfernung, Manhattan-Entfernung oder andere Standardmetriken erfüllen diese Annahmen. Da eine benutzerdefinierte Distanzmetrik diese Annahmen möglicherweise nicht erfüllt, verfügt der Konstruktor über einen dritten Parameter, der die Anzahl der Iterationen angibt, die zum Erstellen des Clusterers ausgeführt werden sollen.
quelle