Clustering (k-means oder anders) mit einer minimalen Einschränkung der Clustergröße

14

Ich muss Einheiten in Cluster gruppieren, um die Summe der Quadrate innerhalb der Gruppe (WSS) zu minimieren, aber ich muss sicherstellen, dass die Cluster jeweils mindestens m Einheiten enthalten. Gibt es eine Idee, ob eine der Clustering-Funktionen von R das Clustering in k Cluster unter Einhaltung einer Mindestbeschränkung für die Clustergröße ermöglicht? kmeans () scheint keine Option für Größenbeschränkungen zu bieten.kmk

r clustering Cyrus S
quelle

Antworten:

5

Verwenden Sie EM-Clustering

Beim EM-Clustering verfeinert der Algorithmus iterativ ein anfängliches Cluster-Modell, um es an die Daten anzupassen, und bestimmt die Wahrscheinlichkeit, dass ein Datenpunkt in einem Cluster vorhanden ist. Der Algorithmus beendet den Prozess, wenn das Wahrscheinlichkeitsmodell zu den Daten passt. Die zur Bestimmung der Anpassung verwendete Funktion ist die Log-Wahrscheinlichkeit der Daten, die dem Modell gegeben sind.

Wenn während des Prozesses leere Cluster generiert werden oder wenn die Zugehörigkeit zu einem oder mehreren Clustern unter einen bestimmten Schwellenwert fällt, werden die Cluster mit geringen Populationen an neuen Punkten neu bewertet und der EM-Algorithmus wird erneut ausgeführt.

mariana weicher
quelle
Danke, Marianna. Ich würde eine Lösung vorziehen, die sich weniger stark auf (normalerweise nicht zu rechtfertigende) parametrische Modelle stützt, sich aber auf jeden Fall damit befasst.
Cyrus S
4

Dieses Problem wird in diesem Artikel angesprochen:

Bradley, PS, KP Bennett und Ayhan Demiriz. "Eingeschränktes k bedeutet Clustering." Microsoft Research, Redmond (2000) : 1-8.

Ich habe eine Implementierung des Algorithmus in Python.

Behrouz Babaki
quelle
Das ist perfekt, danke! Ich habe das rPythonPaket in R verwendet, um eine Schnittstelle zu dieser Implementierung zu erstellen, auf die ich über mein R-Skript zugegriffen habe.
Michael Ohlrogge
@MichaelOhlrogge hast du irgendwo ein Beispiel (github?) Auf der Schnittstelle, die du geschrieben hast, um das Python-Paket von R aufzurufen? Vielen Dank!
Matifou vor
Entschuldigung, ich habe mich in meinem alten Code umgesehen, konnte ihn aber nicht mehr finden.
Michael Ohlrogge vor
3

Ich denke, es wäre nur eine Frage der Ausführung der k-Mittelwerte als Teil einer if-Schleife mit einem Test für Clustergrößen, d. H. Anzahl n in Cluster k. Denken Sie auch daran, dass k-Mittelwerte für jeden Lauf mit denselben Daten unterschiedliche Ergebnisse liefern Sie sollten es wahrscheinlich sowieso als Teil einer Schleife ausführen, um das "beste" Ergebnis zu extrahieren


quelle
1
Danke, Alex. Ich sehe jedoch ein Problem damit: Was passiert, wenn die generierten Lösungen über die Schleifen hinweg niemals die Bedingung erfüllen? Dies kann passieren, wenn k means so eingestellt ist, dass es ohne Einschränkung der Clustergröße ausgeführt wird. Ich würde eine Lösung lieben, die dies vermeidet. (Die Art der Anwendung ist so, dass ich wirklich sicherstellen muss, dass die Cluster eine Mindestgröße haben.)
Cyrus S
1

Wie groß ist Ihr Datensatz? Vielleicht könnten Sie versuchen, ein hierarchisches Clustering durchzuführen und dann anhand Ihres Dendrogramms zu entscheiden, welche Cluster erhalten bleiben.

Wenn Ihre Datenmenge sehr groß ist, können Sie auch beide Clustering-Methoden kombinieren: ein anfängliches nicht hierarchisches Clustering und dann ein hierarchisches Clustering unter Verwendung der Gruppen aus der nicht hierarchischen Analyse. Ein Beispiel für diesen Ansatz finden Sie in Martínez-Pastor et al. (2005).

Manuel Ramón
quelle
Danke, Manuel. Das klingt tatsächlich nach einer sehr interessanten Möglichkeit. Ich muss darüber nachdenken, ob die hierarchische Partitionierung bestimmte Einschränkungen auferlegen würde, die verhindern würden, dass der Algorithmus die optimale Clusterpartitionierung direkt unter der Größenbeschränkung erreicht. Aber intuitiv kann ich sehen, dass dies funktionieren könnte.
Cyrus S
0

Dies kann erreicht werden, indem der Clusterzuweisungsschritt (E in EM) geändert wird, indem er als ein lineares Netzwerkoptimierungsproblem mit minimalem Kostenfluss (MCF) formuliert wird.

Ich habe ein Python-Paket geschrieben, das SimpleMinCostFlow der Operations Research-Tools von Google verwendet, eine schnelle C ++ - Implementierung. Es verfügt über eine Standard-Scikit-Lean-API.

joshlk
quelle