K-Means Clustering

Objectif: Maitriser les calculs de K-Means a la main (distances, assignation, centroides).

Prenez une feuille et un stylo. Resolvez chaque partie AVANT de regarder la solution !

CONTEXTE

Vous avez 6 points a regrouper en K=2 clusters. Les coordonnees sont :

Les centroides 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 centroides.

1.1) Distance du point A au centroide $C_1$ et au centroide $C_2$

1.2) Distance du point D au centroide $C_1$ et au centroide $C_2$

1.3) Completez le tableau des distances pour les 6 points

PARTIE 2 : Assignation aux clusters

Chaque point est assigne au centroide le plus proche.

2.1) A quel cluster appartient le point A ?

2.2) A quel cluster appartient le point D ?

2.3) Listez tous les points du Cluster 1 et du Cluster 2

PARTIE 3 : Mise a jour des centroides

Apres l'assignation, on recalcule les centroides (moyenne des points de chaque cluster).

3.1) Calculez le nouveau centroide $C_1'$ (moyenne des points du Cluster 1)

3.2) Calculez le nouveau centroide $C_2'$ (moyenne des points du Cluster 2)

3.3) Les centroides ont-ils beaucoup bouge ?

PARTIE 4 : Calcul de l'inertie

L'inertie est la somme des distances au carre entre chaque point et son centroide.

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

4.1) Calculez l'inertie avec les centroides initiaux ($C_1$, $C_2$)

4.2) Calculez l'inertie avec les nouveaux centroides ($C_1'$, $C_2'$)

4.3) L'inertie a-t-elle diminue ? Pourquoi ?

PARTIE 5 : Interpretation

5.1) L'algorithme a-t-il converge apres cette iteration ?

5.2) Si on avait initialise avec $C_1 = (5, 5)$ et $C_2 = (5, 6)$, le resultat aurait-il ete different ?

5.3) Pourquoi K-Means peut donner des resultats differents selon l'initialisation ?

SOLUTION DETAILLEE

Prenez le temps de comparer avec vos reponses. Verifiez chaque etape !

RAPPEL DES DONNEES

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

Centroides 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 a gauche)
• $\textcolor{#F7E64D}{\text{Cluster 2}}$ : D, E, F (les 3 points en haut a droite)

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

PARTIE 3 : Mise a jour des centroides

3.1) Nouveau centroide $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 centroide $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) Deplacement des centroides :

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

Les centroides se sont deplaces vers le "centre de gravite" de leurs points.

PARTIE 4 : Calcul de l'inertie

4.1) Inertie avec centroides 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 centroides :

Distances aux nouveaux centroides :

• $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{ (reduction de 65\%)}}$

L'inertie a diminue car les centroides sont maintenant au centre de leurs clusters, minimisant les distances.

PARTIE 5 : Interpretation

5.1) Convergence :

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

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

5.2) Initialisation differente :

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

• Converger vers une solution differente
• Ou trouver la meme solution apres plus d'iterations

5.3) Pourquoi des resultats differents :

K-Means minimise l'inertie localement, pas globalement. Differentes initialisations peuvent mener a differents minima locaux. C'est pourquoi n_init=10 execute 10 fois avec des initialisations differentes et garde le meilleur resultat.

RESUME DES RESULTATS

Legende des couleurs :

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