TP IA Cycle ENCG S4
TP : Algorithme de Clustering K-Means
Ce TP est conçu pour être complet, pédagogique et visuel. Il contient :
• Un cours théorique détaillé avec explications pas-à-pas
• Des exercices pratiques à réaliser
Partie 1 : Cours théorique
1.1 Qu’est-ce que le clustering ?
Le clustering est une technique d’apprentissage non supervisé. On cherche à regrouper des
données similaires sans connaître à l’avance les groupes.
Exemple concret : regrouper des clients selon leurs habitudes d’achat, ou des fleurs selon
leurs mesures (dataset Iris).
1.2 Principe de K-Means
K-Means est l’un des algorithmes de clustering les plus populaires et les plus simples.
Objectif : partitionner les données en K clusters (K = nombre de groupes choisi par
l’utilisateur) de manière à minimiser la variance intra-cluster.
Formule mathématique de l’objectif (fonction de coût) :
$
𝐽=# $ ∥ 𝑥 − 𝜇% ∥(
!∈#!
%&'
où :
• 𝐶% = cluster i
• 𝜇% = centroïde (moyenne) du cluster i
• ∥⋅∥= distance euclidienne
Étape par étape de l’algorithme :
1. Initialisation : choisir K centroïdes au hasard
2. Assignment : assigner chaque point au centroïde le plus proche
3. Update : recalculer chaque centroïde comme la moyenne des points assignés
4. Répéter les étapes 2 et 3 jusqu’à convergence (plus de changement ou nombre max
d’itérations atteint)
Voici une illustration claire des différentes étapes :
1
TP IA Cycle ENCG S4
[Link]
[Link]
2
TP IA Cycle ENCG S4
[Link]
Partie 2 : Exemple visuel avec données synthétiques
Imaginons 300 points répartis en 4 groupes naturels.
Données originales (clusters réels) :
[Link]
K-Means Clustering in Python :: Mubaris
3
TP IA Cycle ENCG S4
Après application de K-Means (K=4) :
[Link]
Most People Don't Really Understand K-Means — Here's the Visual Way That Finally Clicks
| by Simple ML | Artificial Intelligence in Plain English
Mauvais choix de K (ex. K=2) :
4
TP IA Cycle ENCG S4
[Link]
K-means Clustering: Algorithm, Applications, Evaluation Methods, and Drawbacks |
Towards Data Science
On voit clairement que le modèle force des regroupements qui n’ont pas de sens.
Partie 3 : Choix du bon K – Méthode du Coude (Elbow Method)
On calcule l’inertie (somme des distances au carré entre chaque point et son centroïde) pour
différents K.
On trace la courbe : elle descend fortement puis se stabilise → le « coude » indique le bon K.
Illustration de la méthode du coude :
[Link]
5
TP IA Cycle ENCG S4
[Link]
Partie 4 : Implémentation en Python
4.1 Avec scikit-learn (méthode recommandée)
import numpy as np
import [Link] as plt
import seaborn as sns
from [Link] import make_blobs
from [Link] import KMeans
# 1. Générer des données
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.60,
random_state=0)
# 2. Appliquer K-Means
kmeans = KMeans(n_clusters=4, random_state=42, n_init=10)
y_kmeans = kmeans.fit_predict(X)
# 3. Visualisation
[Link](figsize=(10, 7))
[Link](X[:, 0], X[:, 1], c=y_kmeans, cmap='viridis', s=50,
edgecolor='k')
[Link](kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1],
s=300, c='red', marker='X', edgecolor='black', linewidth=2,
label='Centroïdes')
[Link]('Résultat K-Means (K=4)')
6
TP IA Cycle ENCG S4
[Link]('Feature 1')
[Link]('Feature 2')
[Link]()
[Link](True)
[Link]()
4.2 Implémentation from scratch (très pédagogique)
def kmeans_from_scratch(X, n_clusters=3, max_iter=300, random_state=42):
[Link](random_state)
# Initialisation aléatoire des centroïdes
centroids = X[[Link]([Link][0], n_clusters, replace=False)]
for _ in range(max_iter):
# Assignment
distances = [Link](X[:, [Link]] - centroids, axis=2)
labels = [Link](distances, axis=1)
# Update
new_centroids = [Link]([X[labels == k].mean(axis=0) for k in
range(n_clusters)])
# Convergence ?
if [Link](centroids, new_centroids, atol=1e-6):
break
centroids = new_centroids
return labels, centroids
# Utilisation
labels, centroids = kmeans_from_scratch(X, n_clusters=4)
Partie 5 : TP pratique à réaliser (exercices)
Exercice 1 Appliquer K-Means sur le dataset Iris (load_iris()). → Trouver le meilleur K avec
la méthode du coude. → Visualiser les clusters en 2D
Exercice 2 Implémenter la fonction elbow_method(X, max_k=10) qui retourne la liste des
inerties et trace la courbe.
Exercice 3 Comparer K=3 et K=5 sur les données synthétiques. Que remarquez-vous ?
7
TP IA Cycle ENCG S4
Exercice 4 (challenge) Modifier la fonction from scratch pour ajouter le paramètre n_init=10
(plusieurs initialisations et garder la meilleure).