Ich habe einige Punkte in und möchte die Punkte so gruppieren, dass:
Jeder Cluster enthält eine gleiche Anzahl von Elementen von . (Angenommen, die Anzahl der Cluster teilt .)
Jeder Cluster ist in gewissem Sinne "räumlich kohäsiv", wie die Cluster aus Mitteln.
Es ist leicht, sich eine Menge Clustering-Verfahren vorzustellen, die die eine oder andere dieser Anforderungen erfüllen, aber kennt jemand einen Weg, um beide gleichzeitig zu erreichen?
machine-learning
clustering
k-means
unsupervised-learning
Nicht Durrett
quelle
quelle
Antworten:
Ich schlage einen zweistufigen Ansatz vor:
Erhalten Sie eine gute erste Einschätzung der Cluster-Zentren, z. B. mit harten oder unscharfen K-Mitteln.
Verwenden Sie die Zuweisung "Globaler nächster Nachbar", um Punkte mit Clusterzentren zu verknüpfen: Berechnen Sie eine Abstandsmatrix zwischen jedem Punkt und jedem Clusterzentrum (Sie können das Problem ein wenig verkleinern, indem Sie nur angemessene Abstände berechnen), replizieren Sie jedes Clusterzentrum X-mal und lösen Sie die lineare Zuweisungsproblem . Sie erhalten für jedes Clusterzentrum genau X Übereinstimmungen mit Datenpunkten, sodass der Abstand zwischen Datenpunkten und Clusterzentren global minimiert wird.
Beachten Sie, dass Sie Cluster-Zentren nach Schritt 2 aktualisieren und Schritt 2 wiederholen können, um grundsätzlich K-means mit einer festen Anzahl von Punkten pro Cluster auszuführen. Trotzdem ist es eine gute Idee, zuerst eine erste Vermutung anzustellen.
quelle
Probieren Sie diese k-means Variante:
Initialisierung :
k
Zentren aus dem Datensatz nach dem Zufallsprinzip oder noch besser mithilfe der Strategie kmeans ++Am Ende sollten Sie eine Partitionierung haben, die Ihren Anforderungen von + -1 der gleichen Anzahl von Objekten pro Cluster entspricht. (Stellen Sie sicher, dass die letzten Cluster auch die richtige Anzahl haben. Die ersten
m
Cluster solltenceil
Objekte haben, der Rest genaufloor
Objekte.)Iterationsschritt :
Voraussetzungen: Eine Liste für jeden Cluster mit "Tauschvorschlägen" (Objekte, die sich lieber in einem anderen Cluster befinden würden).
Schritt E : Berechnen Sie die aktualisierten Cluster-Zentren wie in regulären k-Mitteln
M- Schritt: Durchlaufen aller Punkte (entweder nur einer oder alle in einem Stapel)
Berechnen Sie das nächstgelegene Clusterzentrum für Objekte / alle Clusterzentren, die näher an den aktuellen Clustern liegen. Wenn es sich um einen anderen Cluster handelt:
Die Clustergrößen bleiben unveränderlich (+ - der Decken- / Bodendifferenz), ein Objekt wird nur von einem Cluster zu einem anderen verschoben, solange dies zu einer Verbesserung der Schätzung führt. Es sollte daher irgendwann konvergieren wie k-means. Es könnte allerdings etwas langsamer sein (dh mehr Iterationen).
Ich weiß nicht, ob dies bereits veröffentlicht oder implementiert wurde. Es ist genau das, was ich versuchen würde (wenn ich k-means versuchen würde. Es gibt viel bessere Clustering-Algorithmen.)
Ein guter Ausgangspunkt könnte die Implementierung von k-means in ELKI sein , die anscheinend bereits drei verschiedene Initialisierungen unterstützt (einschließlich k-means ++), und die Autoren sagten, dass sie auch unterschiedliche Iterationsstrategien haben möchten, um alle verschiedenen allgemeinen abzudecken modulare Varianten (z. B. Lloyd, MacQueen, ...).
quelle
Dies ist ein Optimierungsproblem. Wir haben eine Open-Source-Java-Bibliothek, die dieses Problem löst (Clustering, bei dem die Menge pro Cluster zwischen festgelegten Bereichen liegen muss). Die Gesamtpunktzahl sollte jedoch maximal einige Tausend betragen - nicht mehr als 5000 oder vielleicht 10000.
Die Bibliothek ist hier:
https://github.com/PGWelch/territorium/tree/master/territorium.core
Die Bibliothek selbst ist für Probleme mit geografischen / GIS-Typen eingerichtet. Sie sehen also Verweise auf X und Y, Breiten- und Längengrade, Kunden, Entfernung und Zeit usw. Sie können die "geografischen" Elemente jedoch einfach ignorieren und als reine Elemente verwenden Clusterer.
Sie stellen eine Reihe von anfänglich leeren Eingabe-Clustern mit jeweils einer minimalen und einer maximalen Zielmenge bereit. Der Clusterer weist Ihren Eingabe-Clustern mithilfe eines heuristischen Optimierungsalgorithmus (Swaps, Moves usw.) Punkte zu. Bei der Optimierung wird zum einen die Priorität festgelegt, dass jeder Cluster innerhalb seines minimalen und maximalen Mengenbereichs bleibt. Zum anderen werden die Abstände zwischen allen Punkten im Cluster und dem zentralen Punkt des Clusters minimiert, sodass ein Cluster räumlich zusammenhängend ist.
Über diese Schnittstelle geben Sie dem Löser eine metrische Funktion (dh Distanzfunktion) zwischen Punkten:
https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/TravelMatrix.java
Die Metrik ist so strukturiert, dass sie sowohl eine Entfernung als auch eine "Zeit" zurückgibt, da sie für reisebasierte geografische Probleme entwickelt wurde. Bei beliebigen Clustering-Problemen setzen Sie "Zeit" einfach auf Null und die Entfernung auf die tatsächliche Metrik, die Sie zwischen den beiden verwenden Punkte.
Sie würden Ihr Problem in dieser Klasse einrichten:
https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Problem.java
Ihre Punkte lauten "Kunden" und ihre Anzahl "1". Stellen Sie in der Kundenklasse sicher, dass Sie costPerUnitTime = 0 und costPerUnitDistance = 1 festlegen, vorausgesetzt, Sie geben Ihre metrische Entfernung in das von der TravelMatrix zurückgegebene Feld "Entfernung" ein.
https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Customer.java
Ein Beispiel zum Ausführen des Solvers finden Sie hier:
https://github.com/PGWelch/territorium/blob/master/territorium.core/src/test/java/com/opendoorlogistics/territorium/TestSolver.java
quelle
Ich schlage den kürzlich erschienenen Artikel Diskriminatives Clustering durch Regularisierte Informationsmaximierung (und darin enthaltene Referenzen) vor. Im Besonderen geht es in Abschnitt 2 um das Klassengleichgewicht und die Clusterannahme.
quelle
Vor kurzem brauchte ich das selbst für einen nicht sehr großen Datensatz. Obwohl meine Antwort eine relativ lange Laufzeit hat, wird sie garantiert zu einem lokalen Optimum konvergieren.
quelle