Chapitre 10 — K-Means et algorithme de Lloyd

🎯 Objectifs d'apprentissage

Définir l'inertie intra-cluster et l'objectif de K-Means.
Décrire les 4 étapes de l'algorithme de Lloyd.
Calculer la mise à jour d'un centroïde.
Connaître les avantages et limites de K-Means.

10.1 — Le problème à résoudre

La méthode K-Means (K-moyennes) est une méthode de partitionnement qui cherche à séparer un jeu de données $D$ en $K$ clusters fixes. On suppose que les objets sont représentés dans un espace euclidien. main_5.pdf, p. 10

💡 Intuition

Placez $K$ drapeaux (centroïdes) au hasard au milieu d'une foule. Chaque personne se range sous le drapeau le plus proche. Puis, chaque porteur de drapeau se déplace au centre exact de son groupe. On répète jusqu'à ce que plus personne ne change de drapeau.

10.2 — Objectif : inertie intra-cluster

📘 Définition à connaître

L'objectif de K-Means est de trouver une partition $(C 1, C 2, \dots, C K)$ de l'ensemble des observations qui minimise la variance intra-cluster globale, souvent appelée inertie :

\underset{C_{1}, \dots, C_{K}}{argmin} \sum_{k = 1}^{K} \sum_{\vec{x} \in C_{k}} {‖ \vec{x} - {\vec{μ}}_{k} ‖}_{2}^{2}

où $μ⃗ k$ est le centroïde (centre de gravité) du cluster $C k$ .

main_5.pdf, p. 10

⚠️ Remarque — problème NP-difficile

Résoudre ce problème de manière exacte n'est pas possible (NP-hard). On utilise donc une heuristique qui détermine un optimum local : l'algorithme de Lloyd.

10.3 — Algorithme de Lloyd

📘 Algorithme — 4 étapes

Entrée : $n$ observations $D = {x i} i=1,\dots,n$ dans $ℝ p$ et un nombre $K$ de clusters.

Initialisation : choisir $K$ observations $p 1, \dots, p K$ parmi les $n$ pour servir de centroïdes initiaux.
Affectation : affecter chaque observation $x i$ au centroïde dont elle est la plus proche : $k_{i} = \underset{k = 1, \dots, K}{argmin} {‖ x_{i} - p_{k} ‖}_{2}^{2}$
Mise à jour : recalculer les centroïdes de chaque cluster $C k$ : $p_{k} = \frac{1}{| C_{k} |} \sum_{x_{i} \in C_{k}} x_{i}$
Convergence : répéter les étapes 2 et 3 jusqu'à ce que les affectations ne changent plus.

main_5.pdf, p. 11

10.4 — Exemple guidé

✏️ Exemple guidé — Calcul de centroïdes et d'inertie

Soient 3 points dans $ℝ²$ : $x 1 = (1, 2) T$ , $x 2 = (3, 4) T$ , $x 3 = (8, 10) T$ .

Affectation courante : cluster $C 1 = {x 1, x 2}$ , cluster $C 2 = {x 3}$ .

Recalcul du centroïde $μ 1$ :

{\vec{μ}}_{1} = \frac{x_{1} + x_{2}}{2} = \frac{(1, 2) + (3, 4)}{2} = (2, 3)

Recalcul du centroïde $μ 2$ :

{\vec{μ}}_{2} = x_{3} = (8, 10)

Calcul de l'inertie intra-cluster totale :

Distance $x 1$ à $μ 1$ : $(1-2)² + (2-3)² = 1 + 1 = 2$
Distance $x 2$ à $μ 1$ : $(3-2)² + (4-3)² = 1 + 1 = 2$
Distance $x 3$ à $μ 2$ : $0$
Inertie intra-cluster = 2 + 2 + 0 = 4,0

Interprétation : l'inertie mesure la variabilité résiduelle interne des groupes. Plus elle est faible, plus les clusters sont compacts.

10.5 — Avantages et limites

Avantages	Inconvénients
Simple à implémenter et à comprendre Relativement efficace : $θ(tKn)$ , où $t$ = nb d'itérations Tend à réduire la variance intra-cluster	Nécessite de spécifier $K$ à l'avance Utilisable seulement quand la notion de moyenne existe (pas sur données nominales) Peut rester bloqué sur un optimum local Sensible au bruit et aux anomalies Sensible à l'initialisation Ne permet pas de définir des classes aux formes non convexes

main_5.pdf, p. 13

⚠️ Attention — données nominales

K-Means ne peut pas être appliqué directement à des données catégorielles nominales, car la notion de moyenne vectorielle n'a pas de sens sur ces données. Il faut d'abord vectoriser (par exemple par one-hot encoding) si l'on veut les traiter.

📌 À retenir

Objectif : minimiser l'inertie intra-cluster $\sum k \sum x \in C k ‖x - μ k ‖²$ .
Problème NP-difficile → heuristique de Lloyd.
Algorithme de Lloyd : initialisation → affectation → mise à jour → convergence.
Centroïde : $μ k = (1/|C k |) \sum x i \in C k x i$ .
Nécessite de fixer $K$ à l'avance ; sensible à l'initialisation.

🎯 À l'examen

Citez les 4 étapes de l'algorithme de Lloyd.
Définissez mathématiquement l'objectif d'inertie intra-cluster.
Pour les points $x 1 = (0, 0)$ et $x 2 = (4, 4)$ dans le même cluster, calculez le centroïde et l'inertie.
Pourquoi K-Means ne fonctionne-t-il pas sur des données nominales ?