K-Means Clustering

Théorie

Apprentissage non supervisé

Contrairement à la classification (supervisé), le clustering n'utilise PAS de labels prédéfinies.

Objectif: Trouver des groupes "naturels" dans les données.

K-Means:

K = nombre de clusters désiré (à définir)
Chaque cluster a un "centroïde" (centre)
Les points sont assignés au centroïde le plus proche

Algorithme:

Initialiser K centroïdes aléatoirement
Assigner chaque point au centroïde le plus proche
Recalculer les centroïdes (moyenne des points)
Répéter 2-3 jusqu'à convergence

Applications: segmentation clients, compression d'images, détection d'anomalies...

Théorie

Schéma: Fonctionnement de K-Means

Supervisé vs Non-supervisé:

SUPERVISÉ	NON-SUPERVISÉ
Données avec labels	Données SANS labels
"Apprends à reconnaître chiens et chats"	"Trouve des groupes par toi-même"

flowchart LR subgraph Supervise["SUPERVISÉ: on connaît les classes"] S1["Chien"] S2["Chat"] S3["Chien"] S4["Chat"] end subgraph NonSupervise["NON-SUPERVISÉ: classes inconnues"] N1(("?")) N2(("?")) N3(("?")) N4(("?")) end class S1 ml-node-main class S3 ml-node-main class S2 ml-node-brand class S4 ml-node-brand class N1 ml-node-secondary class N2 ml-node-secondary class N3 ml-node-secondary class N4 ml-node-secondary

Algorithme K-Means étape par étape:

flowchart LR subgraph E1["ÉTAPE 1: Initialisation"] I1["Placer K centroïdes
aléatoirement"] end subgraph E2["ÉTAPE 2: Assignation"] A1["Chaque point →
centroïde le plus proche"] end subgraph E3["ÉTAPE 3: Mise à jour"] U1["Recalculer centroïdes
= moyenne des points"] end subgraph E4["ÉTAPE 4: Répéter"] R1["Jusqu'a convergence"] end E1 --> E2 --> E3 --> E4 E4 -.->|"pas stable"| E2

Comment un point est assigné:

Le point est assigné au centroïde le plus proche (distance minimale).

Exemple concret avec code couleur - Assignation d'un point:

Nouveau point: $\textcolor{#3498db}{x = 4.5}$, $\textcolor{#e67e22}{y = 3.2}$

Centroïdes des clusters:

$\textcolor{#9B7AC4}{Centroide\ A}$: $(\textcolor{#9B7AC4}{2.0}, \textcolor{#9B7AC4}{1.5})$
$\textcolor{#F7E64D}{Centroide\ B}$: $(\textcolor{#F7E64D}{5.0}, \textcolor{#F7E64D}{3.0})$

Étape 1 - Calcul des distances (Euclidienne):

$d_A = \sqrt{(\textcolor{#3498db}{4.5} - \textcolor{#9B7AC4}{2.0})^2 + (\textcolor{#e67e22}{3.2} - \textcolor{#9B7AC4}{1.5})^2} = \sqrt{6.25 + 2.89} = \textcolor{#e74c3c}{\mathbf{3.02}}$

$d_B = \sqrt{(\textcolor{#3498db}{4.5} - \textcolor{#F7E64D}{5.0})^2 + (\textcolor{#e67e22}{3.2} - \textcolor{#F7E64D}{3.0})^2} = \sqrt{0.25 + 0.04} = \textcolor{#27ae60}{\mathbf{0.54}}$

Étape 2 - Comparaison:

$\textcolor{#27ae60}{d_B = 0.54} < \textcolor{#e74c3c}{d_A = 3.02}$

Résultat: Le point est assigné au $\textcolor{#27ae60}{\mathbf{Cluster\ B}}$ (distance minimale)

Légende des couleurs:

$\textcolor{#3498db}{Bleu}$: coordonnée X du point ($\textcolor{#3498db}{4.5}$)
$\textcolor{#e67e22}{Orange}$: coordonnée Y du point ($\textcolor{#e67e22}{3.2}$)
$\textcolor{#9B7AC4}{Violet}$: Centroïde A (trop loin)
$\textcolor{#F7E64D}{Jaune}$: Centroïde B (plus proche)
$\textcolor{#27ae60}{Vert}$: Distance gagnante / Cluster assigne
$\textcolor{#e74c3c}{Rouge}$: Distance perdante

Résumé du processus:

flowchart TD Init["1. Initialise
K centroïdes"] Assign["2. Assigne
les points"] Update["3. Recalcule
centroïdes"] Check{"Convergence?
(stable?)"} Done["FINI!
K clusters"] Init --> Assign Assign --> Update Update --> Check Check -->|Non| Assign Check -->|Oui| Done class Init ml-node-secondary class Done ml-node-accent

Avancé Exercice manuel: À vous de calculer!

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 :

Point	x	y
A	1	2
B	2	1
C	2	3
D	8	7
E	9	8
F	8	9

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 ?

Avancé Solution de l'exercice manuel

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 :

Point	Coords	Distance à C1	Distance à C2	Plus proche
A	(1, 2)	1.00	10.63	C1
B	(2, 1)	1.00	10.63	C1
C	(2, 3)	2.24	9.22	C1
D	(8, 7)	9.22	2.24	C2
E	(9, 8)	10.63	1.41	C2
F	(8, 9)	10.63	1.00	C2

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

Étape	Cluster 1	Cluster 2	Inertie
Initial	C1 = (1, 1)	C2 = (9, 9)	15.0
Après 1 iter	C1' = (1.67, 2)	C2' = (8.33, 8)	5.3

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

Code

Explorer les données

# =============================================================================
# ETAPE 1 : EXPLORATION DES DONNEES POUR LE CLUSTERING
# =============================================================================
# En clustering non supervise, nous n'avons PAS de labels !
# L'objectif est de decouvrir des structures cachees dans les donnees.

print("=" * 70)
print("EXPLORATION DU DATASET POUR CLUSTERING")
print("=" * 70)
print()
print("RAPPEL : En clustering, nous n'avons PAS de labels predefinies.")
print("L'algorithme doit trouver les groupes par lui-meme !")
print()

# --- 1.1 Apercu des donnees ---
print("1. APERCU DES DONNEES")
print("-" * 40)
print("Chaque ligne represente un point dans un espace 2D (x, y).")
print("Nous ne savons pas a quel groupe appartient chaque point.")
print()
display(df.head(10), title="Apercu du dataset (pas de label !)")

# --- 1.2 Dimensions ---
n_points = len(df)
n_features = len(df.columns)
print()
print("2. DIMENSIONS DU DATASET")
print("-" * 40)
print(f"   Nombre de points   : {n_points}")
print(f"   Nombre de features : {n_features}")
print()
print(f"   Interpretation : Nous avons {n_points} points a regrouper")
print(f"   dans un espace a {n_features} dimensions.")

# --- 1.3 Statistiques descriptives ---
print()
print("3. STATISTIQUES DESCRIPTIVES")
print("-" * 40)
print("   Ces statistiques nous aident a comprendre l'etendue des donnees :")
print()
display(df.describe().round(3), title="Statistiques")

# --- 1.4 Analyse de l'etendue ---
print()
print("4. ANALYSE DE L'ETENDUE DES DONNEES")
print("-" * 40)

x_min, x_max = df['x'].min(), df['x'].max()
y_min, y_max = df['y'].min(), df['y'].max()
x_range = x_max - x_min
y_range = y_max - y_min

print(f"   Coordonnee X : de {x_min:.2f} a {x_max:.2f} (etendue : {x_range:.2f})")
print(f"   Coordonnee Y : de {y_min:.2f} a {y_max:.2f} (etendue : {y_range:.2f})")
print()

# Verification de l'echelle
if abs(x_range - y_range) / max(x_range, y_range) < 0.3:
    print("   ✓ Les echelles X et Y sont similaires.")
    print("     → Pas besoin de normalisation pour K-Means.")
else:
    print("   ⚠ Les echelles X et Y sont differentes.")
    print("     → Envisagez une normalisation avant K-Means.")

# --- 1.5 Detecter des patterns potentiels ---
print()
print("5. INDICES DE STRUCTURE DANS LES DONNEES")
print("-" * 40)

# Verifier si les donnees ont une distribution uniforme ou structuree
x_std = df['x'].std()
y_std = df['y'].std()

print(f"   Ecart-type X : {x_std:.3f}")
print(f"   Ecart-type Y : {y_std:.3f}")
print()
print("   Si l'ecart-type est grand par rapport a l'etendue,")
print("   les donnees sont probablement dispersees (plusieurs clusters).")
print()

# Correlation entre X et Y
correlation = df['x'].corr(df['y'])
print(f"   Correlation X-Y : {correlation:.3f}")
if abs(correlation) < 0.3:
    print("   → Faible correlation : les clusters peuvent etre dans toutes les directions.")
else:
    print("   → Correlation notable : les clusters pourraient suivre une diagonale.")

print()
print("=" * 70)
print("CONCLUSION : Visualisons les donnees pour voir les groupes naturels !")
print("=" * 70)

Ctrl+Entrée

Cliquez sur « Exécuter » pour voir le résultat.