Les k-means peuvent-ils tomber dans une boucle infinie ?

Question

J'ai étudié l'algorithme k-means et je sais comment il fonctionne.

Juste par curiosité, y a-t-il une situation où cet algorithme va entrer dans une boucle infinie, par exemple si nous avons de mauvais choix pour les points centroïdes initiaux ? Je ne peux qu'imaginer une situation où k-means atteindrait un minimum local avec de mauvais choix initiaux.

Answer 1

Non. La limite supérieure de k-means est de O(n kd ) en d -espace à plusieurs dimensions.

Answer 2

Considérez également cette réponse à la même question. https://stackoverflow.com/a/60312554/15467861

Le dernier cas de figure : Que se passe-t-il si plus d'un état minimum a une perte égale ? Il s'agit d'un scénario très improbable, mais qui peut poser des problèmes si et seulement si l'algorithme est mal codé pour les ruptures d'égalité. Essentiellement, la seule façon dont cela peut causer un cycle est si un point de données a une distance égale pour deux grappes et est autorisé à changer de grappe même si la distance est égale. Il suffit de dire que les algorithmes sont généralement codés de manière à ce que les points de données ne s'échangent jamais en cas d'égalité, ou d'une autre manière déterministe, ce qui permet d'éviter complètement ce scénario.