Ich versuche k-means als Hausaufgabe zu implementieren. Mein Übungsblatt gibt mir folgende Bemerkung bezüglich leerer Zentren:
Wenn während der Iterationen eines der Clusterzentren keine Datenpunkte zugeordnet sind, ersetzen Sie es durch einen zufälligen Datenpunkt.
Das verwirrt mich ein bisschen, zuerst erwähnen Wikipedia oder andere Quellen, die ich lese, das überhaupt nicht. Ich lese weiter über ein Problem mit "Auswahl eines guten k für Ihre Daten" - wie soll mein Algorithmus konvergieren, wenn ich anfange neue Zentren für Cluster zu setzen, die leer waren.
Wenn ich leere Cluster ignoriere, konvergiere ich nach 30-40 Iterationen. Ist es falsch, leere Cluster zu ignorieren?
Sehen Sie sich dieses Beispiel an, wie leere Cluster passieren können: Ссылка Es bedeutet im Wesentlichen entweder 1) einen zufälligen Tremor in der Kraft oder 2) die Anzahl der Cluster k ist falsch. Sie sollten über ein paar verschiedene Werte für k iterieren und die besten auswählen. Wenn Sie während der Iteration auf einen leeren Cluster stoßen sollten, platzieren Sie einen zufälligen Datenpunkt in diesem Cluster und machen Sie weiter. Ich hoffe, das hat dir letztes Jahr bei deinen Hausaufgaben geholfen.
Die Behandlung von leeren Clustern ist nicht Teil des k-Means-Algorithmus, könnte aber zu einer besseren Cluster-Qualität führen. Wenn wir über die Konvergenz sprechen, ist sie niemals exakt, sondern nur heuristisch garantiert, und daher wird das Konvergenzkriterium um eine maximale Anzahl von Iterationen erweitert.
In Bezug auf die Strategie, dieses Problem anzugehen, würde ich sagen, dass das zufällige Zuweisen einiger Datenpunkte nicht sehr clever ist, da wir die Qualität der Cluster beeinflussen könnten, da die Entfernung zu ihrem aktuell zugewiesenen Zentrum groß oder klein ist. Eine Heuristik für diesen Fall wäre, den entferntesten Punkt vom größten Cluster zu wählen und den leeren Cluster zu verschieben, und zwar so lange, bis keine leeren Cluster mehr vorhanden sind.
Sie sollten leere Cluster nicht ignorieren, sondern sie ersetzen. k-means ist ein Algorithmus, der Ihnen nur lokale Minimums zur Verfügung stellt, und die leeren Cluster sind die lokalen Minimums, die Sie nicht wollen. Ihr Programm wird konvergieren, auch wenn Sie einen Punkt durch einen zufälligen ersetzen. Denken Sie daran, dass Sie am Anfang des Algorithmus die anfänglichen K-Punkte nach dem Zufallsprinzip auswählen. Wenn es konvergieren kann, wie können K-1 Konvergenzpunkte mit 1 Zufallspunkt nicht zusammen kommen? Nur ein paar mehr Iterationen sind erforderlich.
"Wählen Sie gute k für Ihre Daten" bezieht sich auf das Problem der Auswahl der richtigen Anzahl von Clustern. Da der k-Means-Algorithmus mit einer vorbestimmten Anzahl von Clusterzentren arbeitet, muss deren Anzahl zuerst gewählt werden. Die Wahl der falschen Zahl könnte die Aufteilung der Datenpunkte in Cluster erschweren oder die Cluster könnten klein und bedeutungslos werden.
Ich kann Ihnen keine Antwort darauf geben, ob es eine schlechte Idee ist, leere Cluster zu ignorieren. Wenn Sie dies tun, erhalten Sie möglicherweise eine geringere Anzahl von Clustern als Sie zu Beginn definiert haben. Das wird Leute verwirren, die erwarten, dass k-means auf eine bestimmte Art funktionieren, aber das ist nicht unbedingt eine schlechte Idee.
Wenn Sie leere Cluster-Zentren neu lokalisieren, konvergiert Ihr Algorithmus wahrscheinlich trotzdem, wenn dies eine begrenzte Anzahl von Malen passiert. Wenn Sie jedoch zu oft umlagern müssen, kann es passieren, dass Ihr Algorithmus nicht beendet wird.
Tags und Links k-means