Laut Wiki ist das am häufigsten verwendete Konvergenzkriterium "Zuordnung hat sich nicht geändert". Ich habe mich gefragt, ob Radfahren auftreten kann, wenn wir ein solches Konvergenzkriterium verwenden. Ich würde mich freuen, wenn jemand auf einen Artikel verweist, der ein Beispiel für das Radfahren gibt oder beweist, dass dies unmöglich ist.
clustering
algorithms
k-means
Tomek Tarczynski
quelle
quelle
Antworten:
Dieses Papier scheint die Konvergenz in einer endlichen Anzahl von Schritten zu beweisen.
quelle
Die Mittel-Zielfunktion nimmt mit jeder Änderung der Zuordnung streng ab, was automatisch eine Konvergenz ohne Zyklus impliziert. Darüber hinaus erfüllen die in jedem Schritt der Mittel erzeugten Partitionen eine "Voronoi-Eigenschaft", indem jeder Punkt immer seinem nächsten Zentrum zugeordnet wird. Dies impliziert eine Obergrenze für die Gesamtzahl möglicher Partitionen, was eine endliche Obergrenze für die Terminationszeit für Mittel ergibt.k k k
quelle
In endlicher Präzision kann das Radfahren auftreten.
Radfahren ist häufig mit einfacher Präzision, außergewöhnlich mit doppelter Präzision.
In der Nähe eines lokalen Minimums kann sich die Zielfunktion aufgrund von Rundungsfehlern manchmal geringfügig erhöhen. Dies ist oft harmlos, da die Algorithmusfunktion wieder abnimmt und schließlich ein lokales Minimum erreicht. Gelegentlich tritt der Algorithmus jedoch auf eine zuvor besuchte Aufgabe und beginnt mit dem Radfahren.
Es ist einfach und sicher, in realen Implementierungen von Stoppkriterien nach Zyklen zu suchen.
quelle