Clustering mit unebenen Clustern (k-means)

Question

Ich habe zwei Cluster von Punkten. Bevor ich irgendeine Clustertechnik anwende, weiß ich genau, welche Punkte zu jedem Cluster gehören sollten, aber die einzige Möglichkeit, die Daten zu kennzeichnen, ist eine Clustertechnik wie k-means. Wenn die Situation, in der ich mich befinde, rätselhaft ist, konzentriere ich mich nicht auf sie, ich interessiere mich mehr für dieses potenzielle spezifische Problem mit k-means.

Sagen Sie meine Daten wie diese (einfache 2D-Punkte auf der x-y-Ebene) aussieht:

Ich möchte gibt es ein kleines Problem jedoch zwei Gruppen von Punkten erhalten. Wenn ich einen k-means Algorithmus laufen beende ich mit so etwas wie dies oben:

sollte ich hinzufügen, das nur ein skizziertes Beispiel.

Das Problem, das ich habe, ist, wenn die Cluster eine sehr ungerade Anzahl von Punkten in ihnen haben, bevor der Algorithmus ausgeführt wird, dann hat es ein signifikantes Ergebnis auf dem algorithmischen Clustering am Ende, bis die Daten verdunkelt. Natürlich ist dies nur ein Problem, wenn die Cluster vage nahe beieinander sind, aber ich frage mich, ob es eine K-Means-Variante oder einen anderen Clustering-Algorithmus gibt, der sehr gut verschiedene Populationsgrößen von Clustern behandelt. Ich habe versucht, so etwas zu finden, aber ich fürchte, ich benutze die falschen Suchbegriffe wie "ungleiche k-Mittel Cluster-Populationen" und ähnliche Phrasen bekommen nur Papiere über schnellere k-Mittel Implementierungen und Kombinationen mit anderen statistischen Analysen.

Nur um einige Bedenken auszuruhen. Ich habe k-means mehrmals ausgeführt und das Ergebnis ist immer das, was oben skizziert wurde, mit einem Clusterschwerpunkt zwischen zwei visuellen Clustern.

Wenn dies nur ein Nachteil ist k-means hat (und ich kann es so sehen) dann kann ich das akzeptieren.

Answer 1

Die Ausgabe des K-Means-Algorithmus hängt stark von den gewählten Anfangsschwerpunkten ab. Wenn Sie Schwerpunktzentren auswählen, die nahe beieinander liegen, werden die Cluster, die Sie erhalten, verzerrt.

Wenn darüber hinaus die wahren Cluster eine unsymmetrische Anzahl von Datenpunkten haben, dann ist die Wahrscheinlichkeit hoch, dass Sie die anfänglichen Zentroide aus dem gleichen Cluster auswählen, wenn Sie die anfänglichen Zentroide zufällig auswählen.

Daher würde ich vorschlagen, dass Sie versuchen, die Anfangsschwerpunkte zu wählen, die so weit wie möglich auseinander liegen. Dies sollte möglich sein, da deine Punkte 2D sind.

Sie können sogar agglomerative Clustermethoden wie Single Link oder Complete Link Algorithms untersuchen.

Das heißt, diese Algorithmen garantieren keine optimalen Ergebnisse, so dass Sie mit einigen Suboptimalitäten zufrieden sein müssen.

Hoffe, das hilft.