Link

$K$-means

Distortion:

$$J(\mu ,Z)\stackrel{\scriptscriptstyle\mathrm{def}}{=}\sum _{i=1}^n\sum _{k=1}^K{Z}_{ik}\Vert x_i-{\mu }_k{\Vert }^2$$

L’algorithme K-means consiste en une minimisation alternée entre $\mu$ et $Z$ :

1. Choix d’une matrice $\mu$ de manière aléatoire
2. Etape 1: Minimisation de $J$ par rapport à $Z$ (revient à assigner chaque point $x_i$ au cluster le plus proche)
3. Etape 2: Minimisation de $J$ par rapport à $\mu$ : ${\mu }_k=\frac{\sum _i{Z}_{ik}{x}_i}{\sum _i{Z}_{ik}}$
4. Etape 3: Revenir à l’étape 1 jusqu’à convergence.

1) Montrer que l’étape 2 de l’algorithme correspond à l’annulation du gradient de $J$ par rapport à chacun des ${\mu }_k$ avec $Z$ fixé.

Donc