K-means

K moyennes.

Motivation

Identifier des groupes (clusters) dans un ensemble de données.

Analyse

L'algorithme des K-moyennes est un algorithme de ML non supervisé qui va associer à chaque point de $X$ un groupe ${1 . . K}$ .

Conception

3 points tirés au hasard se sont progressivement déplacés pour minimiser la moyenne de leur distances aux 3 groupes de valeurs

L'algorithme des K-moyennes consiste à associer des points à des groupes en fonction de leur distance à leurs barycentres (centroids) :

tirer K points au hasard
répéter jusqu'à convergence
1. affecter des points aux groupes
2. déplacer les barycentres des groupes

Affectation aux groupes

Pour déterminer le groupe (cluster) appartient (en attendant la convergence) chaque point $x^{(i)}$ (avec $i$ de 1 à $m$ ), on va chercher de quel barycentre $μ_{k}$ il est le plus proche. On affectera alors à $c^{(i)}$ l'indice du $k$ groupe trouvé (par conséquent $μ_{c^{(i)}}$ représente le barycentre auquel $x^{(i)}$ est affecté).

Mathématiquement, cette opération revient à minimiser la fonction de coût suivante (dite "fonction de distorsion") sans changer les $μ_{k}$ :

$J (c^{(1)}, \dots, c^{(m)}, μ_{1}, \dots, μ_{K}) = \frac{1}{m} \sum_{i = 1}^{m} {∥ x^{(i)} - μ_{c^{(i)}} ∥}^{2}$

Déplacement des barycentres

Déterminer pour chacun des K groupes $μ_{k}$ qui est la moyenne des points (le nouveau barycentre) affectés au groupe $k$ :

$μ_{k} := \frac{1}{| C k |} \sum_{i \in C_{k}} x^{(i)}$ où $C_{k}$ est l'ensemble de points affectés au barycentre $k$

Mathématiquement, cette opération revient à minimiser $J$ par rapport aux $μ_{k}$ .

Notes

L'algorithme K-Means ne peut que converger.
Le résultat trouvé ne sera pas forcément optimal, mais dépendra des points initialement choisis au hasard. C'est pour cela qu'il convient de réitérer l'algorithme avec des points initiaux différents et de choisir le cas qui aura donné une fonction J de coût minimale.

Exemples

Des exemples d'application de K-Means sont :

Déterminer des segments de marché : par exemple à partir d'un ensemble de ventes de tee-shirts, déterminer quelles sont les populations pour des tailles S, M et L.
Compresser une image : regrouper les couleurs d'une image en "groupes" et réduire ces couleurs à leur moyenne (permettant ainsi de passer de millions de couleurs 16 couleurs/groupes seulement par exemple).