Apprentissage non supervisé/Méthode des k-moyennes

La méthode des k-moyennes (k-means en anglais) est une méthode de partitionnement des données. Elle permet de regrouper en k partitions (clusters en anglais) les données qui se ressemblent. Pour rappel, nous sommes en contexte non supervisé, c'est-à-dire que nous ne connaissons pas la vérité terrain sur les données.

Définition formelle

Considérons un ensemble de points (x₁, x₂, …, x_n). La méthode des k-moyennes consiste à partitionner les n points en k ensembles S = {S₁, S₂, …, S_k} (k ≤ n) en minimisant la distance entre les points à l'intérieur de chaque partition :

$\underset{𝐒}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\sum _{i=1}^k\sum _{{𝐱}_j\in S_i}{\Vert {𝐱}_j-{\mathit{\mu }}_i\Vert }^2$

où μ_i est le barycentre des points dans S_i.