K-Means Clustering

Objectif: Maîtriser les calculs de K-Means à la main (distances, assignation, centroïdes).

Prenez une feuille et un stylo. Résolvez chaque partie AVANT de regarder la solution !

CONTEXTE

Vous avez 6 points à regrouper en K=2 clusters. Les coordonnées sont :

Les centroïdes initiaux sont :

• $C_1 = (1, 1)$ (Cluster 1)
• $C_2 = (9, 9)$ (Cluster 2)

Distance euclidienne : $d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$

PARTIE 1 : Calcul des distances

Calculez la distance de chaque point aux deux centroïdes.

1.1) Distance du point A au centroïde $C_1$ et au centroïde $C_2$ 1.2) Distance du point D au centroïde $C_1$ et au centroïde $C_2$ 1.3) Complétez le tableau des distances pour les 6 points

PARTIE 2 : Assignation aux clusters

Chaque point est assigné au centroïde le plus proche.

2.1) À quel cluster appartient le point A ? 2.2) À quel cluster appartient le point D ? 2.3) Listez tous les points du Cluster 1 et du Cluster 2

PARTIE 3 : Mise à jour des centroïdes

Après l'assignation, on recalcule les centroïdes (moyenne des points de chaque cluster).

3.1) Calculez le nouveau centroïde $C_1'$ (moyenne des points du Cluster 1) 3.2) Calculez le nouveau centroïde $C_2'$ (moyenne des points du Cluster 2) 3.3) Les centroïdes ont-ils beaucoup bougé ?

PARTIE 4 : Calcul de l'inertie

L'inertie est la somme des distances au carré entre chaque point et son centroïde.

$$\text{Inertie} = \sum_{i} d(P_i, C_{\text{assigne}})^2$$

4.1) Calculez l'inertie avec les centroïdes initiaux ($C_1$, $C_2$) 4.2) Calculez l'inertie avec les nouveaux centroïdes ($C_1'$, $C_2'$) 4.3) L'inertie a-t-elle diminué ? Pourquoi ?

PARTIE 5 : Interprétation

5.1) L'algorithme a-t-il convergé après cette itération ? 5.2) Si on avait initialise avec $C_1 = (5, 5)$ et $C_2 = (5, 6)$, le résultat aurait-il été différent ? 5.3) Pourquoi K-Means peut donner des résultats différents selon l'initialisation ?

SOLUTION DÉTAILLÉE

Prenez le temps de comparer avec vos réponses. Vérifiez chaque étape !

RAPPEL DES DONNÉES

Points : A(1,2), B(2,1), C(2,3), D(8,7), E(9,8), F(8,9)

Centroïdes initiaux : $\textcolor{#9B7AC4}{C_1 = (1, 1)}$, $\textcolor{#F7E64D}{C_2 = (9, 9)}$

PARTIE 1 : Calcul des distances

1.1) Point A(1, 2) :

$$d(A, C_1) = \sqrt{(1-1)^2 + (2-1)^2} = \sqrt{0 + 1} = \textcolor{#27ae60}{\mathbf{1.00}}$$

$$d(A, C_2) = \sqrt{(1-9)^2 + (2-9)^2} = \sqrt{64 + 49} = \textcolor{#e74c3c}{\mathbf{10.63}}$$

1.2) Point D(8, 7) :

$$d(D, C_1) = \sqrt{(8-1)^2 + (7-1)^2} = \sqrt{49 + 36} = \textcolor{#e74c3c}{\mathbf{9.22}}$$

$$d(D, C_2) = \sqrt{(8-9)^2 + (7-9)^2} = \sqrt{1 + 4} = \textcolor{#27ae60}{\mathbf{2.24}}$$

1.3) Tableau complet des distances :

PARTIE 2 : Assignation aux clusters

2.1) Point A : $d(A, C_1) = 1.00 < d(A, C_2) = 10.63$ → $\textcolor{#9B7AC4}{\text{Cluster 1}}$

2.2) Point D : $d(D, C_1) = 9.22 > d(D, C_2) = 2.24$ → $\textcolor{#F7E64D}{\text{Cluster 2}}$

2.3) Composition des clusters :

• $\textcolor{#9B7AC4}{\text{Cluster 1}}$ : A, B, C (les 3 points en bas à gauche)
• $\textcolor{#F7E64D}{\text{Cluster 2}}$ : D, E, F (les 3 points en haut à droite)

$\boxed{\text{Cluster 1} = \{A, B, C\} \quad \text{Cluster 2} = \{D, E, F\}}$

PARTIE 3 : Mise à jour des centroïdes

3.1) Nouveau centroïde $C_1'$ :

Points du Cluster 1 : A(1,2), B(2,1), C(2,3)

$$C_1' = \left( \frac{1+2+2}{3}, \frac{2+1+3}{3} \right) = \left( \frac{5}{3}, \frac{6}{3} \right)$$

$\boxed{C_1' = \textcolor{#9B7AC4}{(1.67, 2.00)}}$

3.2) Nouveau centroïde $C_2'$ :

Points du Cluster 2 : D(8,7), E(9,8), F(8,9)

$$C_2' = \left( \frac{8+9+8}{3}, \frac{7+8+9}{3} \right) = \left( \frac{25}{3}, \frac{24}{3} \right)$$

$\boxed{C_2' = \textcolor{#F7E64D}{(8.33, 8.00)}}$

3.3) Déplacement des centroïdes :

• $C_1$ : $(1, 1) \to (1.67, 2.00)$ → déplacement de $\sqrt{0.67^2 + 1^2} = 1.20$
• $C_2$ : $(9, 9) \to (8.33, 8.00)$ → déplacement de $\sqrt{0.67^2 + 1^2} = 1.20$

Les centroïdes se sont déplacés vers le "centre de gravite" de leurs points.

PARTIE 4 : Calcul de l'inertie

4.1) Inertie avec centroïdes initiaux :

$$\text{Inertie}_{init} = d(A,C_1)^2 + d(B,C_1)^2 + d(C,C_1)^2 + d(D,C_2)^2 + d(E,C_2)^2 + d(F,C_2)^2$$

$$= 1^2 + 1^2 + 2.24^2 + 2.24^2 + 1.41^2 + 1^2$$

$$= 1 + 1 + 5 + 5 + 2 + 1 = \textcolor{#e67e22}{\mathbf{15}}$$

4.2) Inertie avec nouveaux centroïdes :

Distances aux nouveaux centroïdes :

• $d(A, C_1') = \sqrt{(1-1.67)^2 + (2-2)^2} = 0.67$
• $d(B, C_1') = \sqrt{(2-1.67)^2 + (1-2)^2} = 1.05$
• $d(C, C_1') = \sqrt{(2-1.67)^2 + (3-2)^2} = 1.05$
• $d(D, C_2') = \sqrt{(8-8.33)^2 + (7-8)^2} = 1.05$
• $d(E, C_2') = \sqrt{(9-8.33)^2 + (8-8)^2} = 0.67$
• $d(F, C_2') = \sqrt{(8-8.33)^2 + (9-8)^2} = 1.05$

$$\text{Inertie}_{new} = 0.67^2 + 1.05^2 + 1.05^2 + 1.05^2 + 0.67^2 + 1.05^2$$

$$= 0.45 + 1.10 + 1.10 + 1.10 + 0.45 + 1.10 = \textcolor{#27ae60}{\mathbf{5.30}}$$

4.3) Comparaison :

$\boxed{\text{Inertie} : 15 \to 5.30 \text{ (réduction de 65\%)}}$

L'inertie a diminué car les centroïdes sont maintenant au centre de leurs clusters, minimisant les distances.

PARTIE 5 : Interprétation

5.1) Convergence :

Non, l'algorithme n'a pas encore converge. Il faudrait refaire une itération :

• Recalculer les distances avec $C_1'$ et $C_2'$
• Vérifier si les assignations changent
• Si aucun point ne change de cluster → convergence

5.2) Initialisation différente :

Avec $C_1 = (5, 5)$ et $C_2 = (5, 6)$, les deux centroïdes sont proches. L'algorithme pourrait :

• Converger vers une solution différente
• Ou trouver la même solution après plus d'itérations

5.3) Pourquoi des résultats différents :

K-Means minimise l'inertie localement, pas globalement. Différentes initialisations peuvent mener à différents minima locaux. C'est pourquoi n_init=10 exécute 10 fois avec des initialisations différentes et garde le meilleur résultat.

RÉSUMÉ DES RÉSULTATS

Légende des couleurs :

• $\textcolor{#9B7AC4}{Violet}$ : Cluster 1 et son centroïde
• $\textcolor{#F7E64D}{Jaune}$ : Cluster 2 et son centroïde
• $\textcolor{#27ae60}{Vert}$ : Distance gagnante (plus proche)
• $\textcolor{#e74c3c}{Rouge}$ : Distance perdante (plus loin)
• $\textcolor{#e67e22}{Orange}$ : Inertie initiale