Cyclisme dans l'algorithme k-means

9

Selon wiki, le critère de convergence le plus utilisé est "l'assignation n'a pas changé". Je me demandais si le cyclisme peut se produire si nous utilisons un tel critère de convergence? Je serais heureux si quelqu'un faisait référence à un article qui donne un exemple de cyclisme ou prouve que c'est impossible.

clustering algorithms k-means Tomek Tarczynski
la source
2
Permettez-moi de souligner (car cela est souvent négligé) que les preuves de convergence ont besoin d'une distance euclidienne (au carré) , de sorte que la fonction distance et la fonction moyenne optimisent le même critère. Si vous utilisez une distance différente (en fait, vous ne devez pas utiliser une distance, mais la "moindre somme de carrés"), vous risquez de perdre la convergence des k-moyennes.
A QUIT - Anony-Mousse

Réponses:

7

Cet article semble prouver la convergence en un nombre fini d'étapes.

Simon Byrne
la source
1
Exactement ce que je cherchais!
Tomek Tarczynski
4

kkk

Suresh Venkatasubramanian
la source
Merci, il est intuitif que la fonction objectif diminue, mais je n'étais pas sûr qu'elle diminue strictement. Je voulais m'assurer qu'il n'y a pas de cas patologique comme dans la programmation linéaire
Tomek Tarczynski
Eh bien oui et non. Bien qu'il converge, cela peut prendre un temps exponentiel, tout comme le fait le simplexe. De plus, pour les deux problèmes, vous pouvez montrer que les variantes "lissées" convergent en temps polynomial
Suresh Venkatasubramanian
2

En précision finie , des cycles peuvent apparaître.

Le cyclisme est fréquent en simple précision, exceptionnel en double précision.

Lorsqu'elle est proche d'un minimum local, la fonction objectif peut parfois légèrement augmenter en raison d'erreurs d'arrondi. Ceci est souvent inoffensif car la fonction d'algorithme diminue à nouveau et atteint finalement un minimum local. Mais parfois, l'algorithme marche sur une affectation précédemment visitée et commence à faire du vélo.

Il est facile et sûr de surveiller les cycles dans les implémentations de critères d'arrêt du monde réel.

François Pays
la source