Kann k-means in eine Endlosschleife geraten?

Question

Ich habe den k-means-Algorithmus studiert und weiß, wie er funktioniert.

Nur neugierig, gibt es irgendeine Situation, dass dieser Algorithmus in eine Endlosschleife gehen wird, sagen wir, wenn wir einige bestimmte schlechte Entscheidungen für anfängliche Schwerpunktpunkte haben? Ich könnte mir nur eine Situation vorstellen, in der k-means ein lokales Minimum mit schlechten Anfangspunkten erreicht.

Answer 1

Nein. k-means hat eine obere Grenze von O(n kd ) en d -dimensionalen Raum.

Answer 2

Beachten Sie auch diese Antwort auf dieselbe Frage. https://stackoverflow.com/a/60312554/15467861

Der letzte Grenzfall: Was ist, wenn mehr als ein Mindestzustand den gleichen Verlust aufweist? Dies ist ein höchst unwahrscheinliches Szenario, kann aber nur dann Probleme verursachen, wenn der Algorithmus für Gleichstandsbrecher schlecht kodiert ist. Im Grunde genommen kann dies nur dann zu einem Zyklus führen, wenn ein Datenpunkt den gleichen Abstand zu zwei Clustern hat und selbst bei gleichem Abstand das Cluster wechseln darf, in dem er sich gerade befindet. Es genügt zu sagen, dass die Algorithmen in der Regel so kodiert sind, dass die Datenpunkte bei einem Gleichstand nicht wechseln oder auf andere deterministische Weise, wodurch dieses Szenario vollständig vermieden wird.