k-means leeren cluster
Ich versuche, umzusetzen k-means als Hausaufgabe. Meine übung gibt mir folgende Bemerkung zum leeren Zentren:
Während der Iterationen, wenn einer der cluster-Zentren keine Daten Punkte die mit ihm verbunden ist, ersetzen Sie es mit einem zufälligen Datenpunkt.
Das verwirrt mich ein wenig, zuerst in der Wikipedia oder anderen Quellen, die ich gelesen habe nicht erwähnt, dass überhaupt. Ich weiter gelesen über ein problem mit der Auswahl eine gute k für Ihre Daten " - wie ist mein Algorithmus soll zu konvergieren, wenn ich starten Sie die Einstellung neue Zentren für cluster, die leer waren.
Wenn ich das ignorieren leere Cluster I konvergieren nach 30-40 Wiederholungen. Ist es falsch, zu ignorieren leere Cluster?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Umgang mit leeren Clustern ist nicht Teil des k-means-Algorithmus, jedoch könnte eine bessere Cluster-Qualität. Reden über Konvergenz, es ist nie genau, aber nur heuristisch garantiert und damit das Kriterium für Konvergenz ist erweitert, indem Sie eine maximale Anzahl von Iterationen.
Bezug auf die Strategie zur Bewältigung der auf diesem problem, würde ich sagen, dass die zufällige Zuteilung einige Daten zeigen, es ist nicht sehr klug, da wir den möglichen Auswirkungen auf die Cluster-Qualität, da die Entfernung zu der jeweils zugewiesenen center groß oder klein ist. Eine Heuristik für diesen Fall wäre zu wählen, der am weitesten entfernte Punkt von der größten cluster und bewegen, dass die leere cluster, dann tun Sie so, bis es keine leeren Cluster.
farthest point from the biggest cluster"Größte" in welcher Hinsicht?Schauen Sie sich dieses Beispiel, wie leere Cluster passieren kann: http://www.ceng.metu.edu.tr/~tcan/ceng465_f1314/Schedule/KMeansEmpty.html
Im Grunde bedeutet es entweder 1) ein zufälliges zittern in der Kraft, oder 2) die Anzahl der Cluster k ist falsch. Sie sollten die Iteration über ein paar verschiedene Werte für k und die besten auszuwählen.
Wenn Sie während Ihres Durchlaufs sollten Sie Begegnung eine leere cluster, statt einem zufälligen Datenpunkt in diesem cluster und tragen auf.
Ich hoffe, das half, sich auf Ihre Hausaufgaben im letzten Jahr.
Sollten Sie nicht ignorieren, leere Cluster, aber ersetzen Sie es. k-means ist ein Algorithmus könnte, nur bietet Sie lokale minima, und die leeren Cluster sind die lokalen minima, die Sie nicht wollen.
Ihr Programm wird zu konvergieren, auch wenn Sie ersetzen einen Punkt mit einer zufälligen one. Denken Sie daran, dass zu Beginn des Algorithmus, wählen Sie den ersten K Punkte nach dem Zufallsprinzip. wenn es konvergieren können, wie kommt es, K-1 konvergieren Punkte mit 1 random point nicht? nur ein paar mehr Iterationen benötigt werden.
"Die Auswahl an guten k für Ihre Daten" bezieht sich auf das problem der Wahl der richtigen Anzahl an Clustern. Da der k-means-Algorithmus arbeitet mit einer vorgegebenen Anzahl von cluster-Zentren, deren Anzahl ausgewählt werden, auf den ersten. Die Wahl der falschen Nummer könnte es schwer machen, zu teilen der Datenpunkte zu Clustern oder Clustern konnten sich klein und bedeutungslos.
Ich kann nicht Ihnen eine Antwort geben, ob es eine schlechte Idee ist, Sie zu ignorieren leere Cluster. Wenn Sie das tun, könnten Sie am Ende mit einer kleineren Anzahl von Clustern als Sie zu Beginn festgelegt haben. Das wird die Leute verwirren, die erwarten, dass k-means-arbeiten in einer bestimmten Weise, aber es ist nicht unbedingt eine schlechte Idee.
Wenn Sie re-suchen Sie einen leeren cluster-Zentren, Ihre Algorithmus wird wahrscheinlich konvergieren jedenfalls, wenn das passiert, dass eine begrenzte Anzahl von Zeiten. Allerdings, wenn Sie umziehen müssen, zu oft, kann es passieren, dass Ihr Algorithmus nicht terminieren.
Für "die Auswahl an guten k für Ihre Daten", Andrew Ng gibt das Beispiel eines T-shirt-Hersteller auf der Suche nach potentiellen Kunden Messungen und tun k-Mittel zu entscheiden, wenn Sie möchten, bieten S/M/L (k=3) oder 2XS/XS/S/M/L/XL/2XL (k=7). Manchmal ist die Entscheidung, getrieben von den Daten (k=7 gibt leere Cluster) und manchmal auch von wirtschaftlichen Erwägungen (die Herstellungskosten sind weniger mit nur drei Größen, oder marketing sagt Kunden wollen mehr Auswahl).
Anweisung: k-means führen kann
Beachten Sie die obige Verteilung der Datenpunkte.
überlappende Punkte bedeuten, dass der Abstand zwischen Ihnen ist del. del tendiert zu 0 das heißt, Sie können davon ausgehen, willkürliche klein genug Wert z.B. 0.01 für Sie.
dash box repräsentiert cluster zuordnen
N=6 Punkte
k=3 Clustern (farbig)
Letzte Cluster = 2
Blaue cluster ist Waise, und landet leer.