# Algorithme des k-moyennes

written by [@marc_lelarge](https://twitter.com/marc_lelarge)

**Fonction de coût:** pour une partition $C_1, \dots, C_k$ des $n$ observations en $k$ clusters, la qualité du clustering est donnée par la fonction de coût:
\begin{eqnarray*}
\sum_{j=1}^k \sum_{i\in C_j} \|x_i-\mu_j\|^2,
\end{eqnarray*}
où $\mu_j =\frac{1}{|C_j|}\sum_{i\in C_j} x_i$.


**Algorithme des k-moyennes:**
- prendre $k$ centres de manière aléatoire
- (a) trouver la partition induite en associant chaque point à son centre le plus proche
- (b) la partition étant fixée, mettre à jour les centres grâce à la formule: $\mu_j =\frac{1}{|C_j|}\sum_{i\in C_j} x_i$
- itérer les étapes (a) et (b)

**Convergence de l'algorithme des k-moyennes:**
- la partition $(C_1,...C_k)$ étant fixée, on vérifie facilement (par ex. en calculant la dérivée) que:
\begin{eqnarray*}
\min_{\mu_1,\dots \mu_k}\sum_{j=1}^k \sum_{i\in C_j} \|x_i-\mu_j\|^2 = \sum_{j=1}^k \sum_{i\in C_j} \left\|x_i-\frac{1}{|C_j|}\sum_{\ell\in C_j} x_\ell\right\|^2
\end{eqnarray*}
Donc l'étape (b) réduit la fonction de coût.
- les centres étant fixés, l'etape (a) minimise également la fonction de coût.
- la fonction de coût ne peut donc que décroître et comme le nombre total de partitions possibles est fini, l'algorithme converge vers un minimum local de la fonction de coût.

**Quelques résultats:**

Dans une image, la couleur d'un pixel est encodée par un vecteur de taille 3: $(R,G,B)$. Dans les exemples ci-dessous, nous effectuons un clustering des couleurs de tous pixels. Ensuite nous remplaçons la couleur du pixel par la couleur du centre du cluster correspondant. Nous obtenons donc des images avec 2,4 ou 10 couleurs uniquements.

Le code est disponible sur [le repo GitHub](https://github.com/mlelarge/agreg/blob/main/k-means.ipynb).

###### tags: `public` `agreginfo`