Preuve de convergence des k-moyennes

Pour une mission, on m'a demandé de fournir une preuve que k-means converge en un nombre fini d'étapes.

Voici ce que j'ai écrit:

$C$

$$E(C)=\sum_{\mathbf{x}}\min_{i=1}^{k}\left\Vert \mathbf{x}-\mathbf{c}_{i}\right\Vert ^{2}$$ $E(C)$

L'étape 2 fait référence à l'étape qui étiquette chaque point de données par son centre de cluster le plus proche, et l'étape 3 est l'étape où les centres sont mis à jour en prenant une moyenne.

Cela ne suffit pas pour prouver la convergence en un nombre fini d'étapes. L'énergie peut continuer à diminuer, mais cela n'exclut pas la possibilité que les points centraux puissent sauter sans trop changer l'énergie. En d'autres termes, il pourrait y avoir plusieurs minima d'énergie et l'algorithme peut sauter entre eux, non?

Premièrement, il existe au plus façons de partitionner N points de données en k grappes; chacune de ces partitions peut être appelée un "clustering". Il s'agit d'un nombre important mais fini. Pour chaque itération de l'algorithme, nous produisons un nouveau cluster basé uniquement sur l'ancien cluster. Remarquerez que$k^N$$N$$k$

1. si l'ancien clustering est le même que le nouveau, alors le clustering suivant sera à nouveau le même.
2. Si le nouveau clustering est différent de l'ancien, alors le plus récent a un coût inférieur

Puisque l'algorithme itère une fonction dont le domaine est un ensemble fini, l'itération doit finalement entrer dans un cycle. Le cycle ne peut pas avoir une longueur supérieure à car sinon en (2) vous auriez un clustering qui a un coût inférieur à lui-même ce qui est impossible. Par conséquent, le cycle doit avoir une longueur exactement 1 . Par conséquent, k-means converge en un nombre fini d'itérations.$1$$1$

Pour ajouter quelque chose: La convergence ou non de l'algorithme dépend également de votre critère d'arrêt. Si vous arrêtez l'algorithme une fois que les affectations de cluster ne changent plus, vous pouvez en fait prouver que l'algorithme ne converge pas nécessairement (à condition que l'affectation de cluster ne dispose pas d'un briseur de lien déterministe dans le cas où plusieurs centroïdes ont la même distance).

Ici, vous avez 8 points de données (points) et deux centroïdes (croix rouges). Maintenant, les points de données vertes ont la même distance au centre de gravité gauche et droit. Il en va de même pour les points de données bleus. Supposons que la fonction d'affectation n'est pas déterministe dans ce cas. De plus, nous supposons qu'à l'itération 1, les points verts sont affectés au cluster de gauche et les points bleus sont affectés au cluster de droite. Ensuite, nous mettons à jour les centroïdes. Il s'avère qu'ils restent en fait au même endroit. (C'est un calcul facile. Pour le centroïde gauche, vous faites la moyenne des coordonnées des deux points noirs gauches et des deux points verts -> (0, 0,5). Idem pour le centroïde droit).

Ensuite, à l'itération 2, la situation est à nouveau la même, mais nous supposons maintenant que notre fonction d'affectation non déterministe (en cas d'égalité) attribue les points verts au cluster droit et les points bleus au cluster gauche. Encore une fois, les centroïdes ne changeront pas.

L'itération 3 est à nouveau la même que l'itération 1. Ainsi, nous avons un cas où les affectations de cluster changent continuellement et l'algorithme (avec ce critère d'arrêt) ne converge pas.

$\leq$$\lt$