Ich habe über k-means Clustering studiert , und eine Sache, die nicht klar ist, ist, wie Sie den Wert von k wählen. Ist es nur eine Frage von Versuch und Irrtum oder steckt mehr dahinter?
cluster-analysis
k-means
Jason Baker
quelle
quelle
R
) hier beantwortet: stackoverflow.com/a/15376462/1036500Antworten:
Sie können das Bayesian Information Criterion (BIC) maximieren:
Dabei
L(X | C)
ist die Log-Wahrscheinlichkeit des DatensatzesX
nach ModellC
,p
die Anzahl der Parameter im ModellC
undn
die Anzahl der Punkte im Datensatz. Siehe "X-Mittel: Erweiterung der K- Mittel mit effizienter Schätzung der Anzahl von Clustern" von Dan Pelleg und Andrew Moore in ICML 2000.Ein anderer Ansatz besteht darin, mit einem großen Wert für
k
Zentroide zu beginnen und diese weiter zu entfernen (k zu reduzieren), bis die Beschreibungslänge nicht mehr verringert wird. Siehe "MDL-Prinzip für robuste Vektorquantisierung" von Horst Bischof, Ales Leonardis und Alexander Selb in Pattern Analysis and Applications vol. 2, p. 59-72, 1999.Schließlich können Sie mit einem Cluster beginnen und dann die Cluster weiter aufteilen, bis die jedem Cluster zugewiesenen Punkte eine Gaußsche Verteilung haben. Greg Hamerly und Charles Elkan zeigen in "Learning the k in k- means" (NIPS 2003) einige Beweise dafür, dass dies besser funktioniert als BIC und dass BIC die Komplexität des Modells nicht stark genug beeinträchtigt.
quelle
Grundsätzlich möchten Sie ein Gleichgewicht zwischen zwei Variablen finden: der Anzahl der Cluster ( k ) und der durchschnittlichen Varianz der Cluster. Sie möchten erstere minimieren und letztere minimieren. Natürlich nimmt mit zunehmender Anzahl von Clustern die durchschnittliche Varianz ab (bis zum trivialen Fall von k = n und Varianz = 0).
Wie immer in der Datenanalyse gibt es keinen echten Ansatz, der in allen Fällen besser funktioniert als alle anderen. Am Ende müssen Sie Ihr eigenes bestes Urteilsvermögen verwenden. Dazu ist es hilfreich, die Anzahl der Cluster gegen die durchschnittliche Varianz zu zeichnen (wobei davon ausgegangen wird, dass Sie den Algorithmus bereits für mehrere Werte von k ausgeführt haben ). Dann können Sie die Anzahl der Cluster am Knie der Kurve verwenden.
quelle
Ja, Sie können die beste Anzahl von Clustern mithilfe der Elbow-Methode ermitteln, aber ich fand es schwierig, den Wert von Clustern mithilfe eines Skripts aus dem Elbow-Diagramm zu ermitteln. Sie können das Ellbogen-Diagramm beobachten und den Ellbogenpunkt selbst finden, aber es war viel Arbeit, ihn aus dem Skript zu finden.
Eine andere Möglichkeit ist die Verwendung der Silhouette-Methode , um sie zu finden. Das Ergebnis von Silhouette stimmt vollständig mit dem Ergebnis der Elbow-Methode in R überein.
Hier ist was ich getan habe.
Ich hoffe es hilft!!
quelle
Kann jemand Anfänger wie ich sein, der nach einem Codebeispiel sucht. Informationen für silhouette_score ist verfügbar hier.
quelle
Schauen Sie sich dieses Papier "Lernen des k in k-Mitteln" von Greg Hamerly, Charles Elkan, an. Es verwendet einen Gaußschen Test, um die richtige Anzahl von Clustern zu bestimmen. Die Autoren behaupten auch, dass diese Methode besser ist als der BIC, der in der akzeptierten Antwort erwähnt wird.
quelle
Es gibt so etwas wie Faustregel. Es heißt, dass die Anzahl der Cluster durch berechnet werden kann
k = (n/2)^0.5
Dabei ist n die Gesamtzahl der Elemente aus Ihrer Stichprobe. Sie können die Richtigkeit dieser Informationen auf dem folgenden Dokument überprüfen:
http://www.ijarcsms.com/docs/paper/volume1/issue6/V1I6-0015.pdf
Es gibt auch eine andere Methode namens G-means, bei der Ihre Verteilung einer Gaußschen Verteilung oder Normalverteilung folgt. Es besteht darin, k zu erhöhen, bis alle Ihre k Gruppen einer Gaußschen Verteilung folgen. Es erfordert viele Statistiken, kann aber durchgeführt werden. Hier ist die Quelle:
http://papers.nips.cc/paper/2526-learning-the-k-in-k-means.pdf
Ich hoffe das hilft!
quelle
Erstellen Sie zunächst einen minimalen Spannbaum Ihrer Daten. Durch Entfernen der teuersten K-1-Kanten wird der Baum in K-Cluster aufgeteilt,
sodass Sie den MST einmal erstellen, die Clusterabstände / -metriken für verschiedene K anzeigen und das Knie der Kurve nehmen können.
Dies funktioniert nur für Single-linkage_clustering , ist aber schnell und einfach. Außerdem machen MSTs eine gute Grafik.
Siehe zum Beispiel das MST-Diagramm unter stats.stackexchange-Visualisierungssoftware für das Clustering .
quelle
Ich bin überrascht, dass niemand diesen ausgezeichneten Artikel erwähnt hat: http://www.ee.columbia.edu/~dpwe/papers/PhamDN05-kmeans.pdf
Nachdem ich einigen anderen Vorschlägen gefolgt war, stieß ich beim Lesen dieses Blogs schließlich auf diesen Artikel: https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/
Danach habe ich es in Scala implementiert, eine Implementierung, die für meine Anwendungsfälle wirklich gute Ergebnisse liefert. Hier ist Code:
quelle
Wenn Sie MATLAB verwenden, eine beliebige Version seit 2013b, können Sie die Funktion verwenden
evalclusters
, um herauszufinden, welchesk
für ein bestimmtes Dataset optimal sein sollte .Mit dieser Funktion können Sie aus 3 Clustering-Algorithmen auswählen -
kmeans
,linkage
undgmdistribution
.Außerdem können Sie unter 4 Clustering Bewertungskriterien wählen -
CalinskiHarabasz
,DaviesBouldin
,gap
undsilhouette
.quelle
Wenn Sie die Nummern der Cluster k nicht kennen, die als Parameter für k-means bereitgestellt werden sollen, gibt es vier Möglichkeiten, sie automatisch zu finden:
G-Mittelwert-Algorithmus: Er ermittelt die Anzahl der Cluster automatisch mithilfe eines statistischen Tests, um zu entscheiden, ob ein k-Mittelwert-Zentrum in zwei Teile geteilt werden soll. Dieser Algorithmus verfolgt einen hierarchischen Ansatz, um die Anzahl der Cluster zu ermitteln, basierend auf einem statistischen Test für die Hypothese, dass eine Teilmenge von Daten einer Gaußschen Verteilung folgt (kontinuierliche Funktion, die sich der exakten Binomialverteilung von Ereignissen annähert), und teilt den Cluster, wenn nicht, auf . Es beginnt mit einer kleinen Anzahl von Zentren, beispielsweise nur einem Cluster (k = 1), dann teilt der Algorithmus ihn in zwei Zentren (k = 2) auf und teilt jedes dieser beiden Zentren erneut auf (k = 4), wobei vier Zentren vorhanden sind gesamt. Wenn G-means diese vier Zentren nicht akzeptiert, lautet die Antwort der vorherige Schritt: in diesem Fall zwei Zentren (k = 2). Dies ist die Anzahl der Cluster, in die Ihr Datensatz unterteilt wird. G-means ist sehr nützlich, wenn Sie keine Schätzung der Anzahl der Cluster haben, die Sie nach dem Gruppieren Ihrer Instanzen erhalten. Beachten Sie, dass eine unbequeme Auswahl für den Parameter "k" zu falschen Ergebnissen führen kann. Die parallele Version von g-means heißtp-Mittel . G-bedeutet Quellen: Quelle 1 Quelle 2 Quelle 3
x-means : Ein neuer Algorithmus, der den Raum der Clusterpositionen und die Anzahl der Cluster effizient durchsucht, um das Bayesian Information Criterion (BIC) oder das Akaike Information Criterion (AIC) zu optimieren. Diese Version von k-means findet die Zahl k und beschleunigt auch k-means.
Online k-means oder Streaming k-means: Ermöglicht die Ausführung von k-means durch einmaliges Scannen der gesamten Daten und findet automatisch die optimale Anzahl von k. Spark implementiert es.
MeanShift-Algorithmus : Es handelt sich um eine nichtparametrische Clustering-Technik, die keine Vorkenntnisse über die Anzahl der Cluster erfordert und die Form der Cluster nicht einschränkt. Mean Shift Clustering zielt darauf ab, „Blobs“ in einer glatten Dichte von Proben zu entdecken. Es handelt sich um einen auf Schwerpunkten basierenden Algorithmus, bei dem Kandidaten für Schwerpunkte so aktualisiert werden, dass sie der Mittelwert der Punkte innerhalb einer bestimmten Region sind. Diese Kandidaten werden dann in einer Nachbearbeitungsphase gefiltert, um nahezu Duplikate zu eliminieren und den endgültigen Satz von Zentroiden zu bilden. Quellen: Quelle1 , Quelle2 , Quelle3
quelle
Ich habe die Lösung verwendet, die ich hier gefunden habe: http://efavdb.com/mean-shift/ und sie hat bei mir sehr gut funktioniert:
quelle
Meine Idee ist es, den Silhouette-Koeffizienten zu verwenden, um die optimale Clusternummer (K) zu finden. Details Erklärung ist hier .
quelle
Angenommen, Sie haben eine aufgerufene Datenmatrix
DATA
, können Sie eine Partitionierung um Medoide mit einer Schätzung der Anzahl der Cluster (durch Silhouettenanalyse) wie folgt durchführen:quelle
Eine mögliche Antwort ist die Verwendung eines meta-heuristischen Algorithmus wie des genetischen Algorithmus, um k zu finden. Das ist einfach. Sie können zufälliges K (in einem bestimmten Bereich) verwenden und die Anpassungsfunktion des genetischen Algorithmus mit einer Messung wie Silhouette bewerten und die beste K-Basis für die Anpassungsfunktion finden.
https://en.wikipedia.org/wiki/Silhouette_(clustering)
quelle
quelle
Ein anderer Ansatz ist die Verwendung von Self Organizing Maps (SOP), um die optimale Anzahl von Clustern zu finden. Die SOM (Self-Organizing Map) ist eine unbeaufsichtigte neuronale Netzwerkmethode, bei der nur die Eingabe für das Clustering zur Problemlösung verwendet werden muss. Dieser Ansatz wurde in einem Artikel über die Kundensegmentierung verwendet.
Die Referenz des Papiers ist
Abdellah Amine et al., Kundensegmentierungsmodell im E-Commerce unter Verwendung von Clustering-Techniken und LRFM-Modell: Der Fall von Online-Shops in Marokko, Weltakademie für Wissenschaft, Technik und Technologie Internationales Journal für Computer- und Informationstechnik Band 9, Nr. 8 , 2015, 1999 - 2010
quelle
Hallo, ich mache es einfach und direkt zu erklären, ich mag es, Cluster mithilfe der 'NbClust'-Bibliothek zu bestimmen.
So verwenden Sie die Funktion 'NbClust', um die richtige Anzahl von Clustern zu bestimmen: Sie können das tatsächliche Projekt in Github mit tatsächlichen Daten und Clustern überprüfen. Die Erweiterung dieses 'kmeans'-Algorithmus wird auch mit der richtigen Anzahl von' Zentren 'durchgeführt.
Github-Projektlink: https://github.com/RutvijBhutaiya/Thailand-Customer-Engagement-Facebook
quelle
Sie können die Anzahl der Cluster auswählen, indem Sie Ihre Datenpunkte visuell untersuchen. Sie werden jedoch bald feststellen, dass dieser Prozess für alle außer den einfachsten Datensätzen sehr vieldeutig ist. Dies ist nicht immer schlecht, da Sie unbeaufsichtigt lernen und der Etikettierungsprozess eine gewisse Subjektivität aufweist. Wenn Sie bereits Erfahrungen mit diesem oder einem ähnlichen Problem gesammelt haben, können Sie den richtigen Wert auswählen.
Wenn Sie einen Hinweis auf die Anzahl der zu verwendenden Cluster wünschen, können Sie die Elbow-Methode anwenden:
Berechnen Sie zunächst die Summe der quadratischen Fehler (SSE) für einige Werte von k (z. B. 2, 4, 6, 8 usw.). Die SSE ist definiert als die Summe des quadratischen Abstands zwischen jedem Mitglied des Clusters und seinem Schwerpunkt. Mathematisch:
SSE = ∑Ki = 1∑x∑cidist (x, ci) 2
Wenn Sie k gegen die SSE zeichnen, werden Sie sehen, dass der Fehler abnimmt, wenn k größer wird; Dies liegt daran, dass die Anzahl der Cluster mit zunehmender Anzahl kleiner sein sollte, sodass auch die Verzerrung geringer ist. Die Idee der Ellbogenmethode besteht darin, das k zu wählen, bei dem die SSE abrupt abnimmt. Dies erzeugt einen "Ellbogeneffekt" in der Grafik, wie Sie im folgenden Bild sehen können:
In diesem Fall ist k = 6 der Wert, den die Elbow-Methode ausgewählt hat. Berücksichtigen Sie, dass die Elbow-Methode eine Heuristik ist und als solche in Ihrem speziellen Fall möglicherweise gut funktioniert oder nicht. Manchmal gibt es mehr als einen Ellbogen oder gar keinen Ellbogen. In solchen Situationen berechnen Sie normalerweise das beste k, indem Sie bewerten, wie gut k-means im Kontext des bestimmten Clustering-Problems funktioniert, das Sie lösen möchten.
quelle
Ich habe an einem Python-Paket Kneed (Kneedle-Algorithmus) gearbeitet. Die Clusternummer wird dynamisch als der Punkt ermittelt, an dem sich die Kurve abflacht. Bei einer Reihe von x- und y-Werten gibt kneed den Kniepunkt der Funktion zurück. Der Kniepunkt ist der Punkt maximaler Krümmung. Hier ist der Beispielcode.
y = [7342,1301373073857, 6881,7109460930769, 6531,1657905495022,
6356,2255554679778, 6209,8382535595829, 6094,9052166741121, 5980,0191582610196, 5880,1869867848218, 5779,8957906367368, 5691,1879324562778, 5617,5153566271356, 5532,2613232619951, 5467,352265375117, 5395,4493783888756, 5345,3459908298091, 5290,6769823693812, 5243,5271656371888, 5207,2501206569532, 5164,9617535255456]
x = Bereich (1, len (y) +1)
vom Knieimport KneeLocator kn = KneeLocator (x, y, Kurve = 'konvex', Richtung = 'abnehmend')
drucken (kn.knee)
quelle