k-moyennes (k-means)

Vue d'ensemble

Tu as une nuée de points sans aucune étiquette — des clients décrits par deux chiffres, des pixels d'une image, des relevés de mesure — et une seule intuition : « il doit y avoir des groupes là-dedans ». Les k-moyennes (en anglais k-means) sont l'algorithme phare pour faire émerger ces groupes tout seuls. C'est de l'apprentissage non supervisé : personne ne t'a dit à l'avance qui va avec qui, l'algorithme doit le découvrir.

L'idée tient en une phrase que l'on répète : chaque point rejoint le centre le plus proche, puis chaque centre se replace au milieu de sa troupe. On recommence jusqu'à ce que plus rien ne bouge.

Au programme (BO 2021, informatique commune, 2e année). Apprentissage non supervisé et partitionnement. Algorithme des k-moyennes : initialisation des centres, phase d'affectation au plus proche centre (distance euclidienne), phase de mise à jour par le barycentre, itération jusqu'à stabilisation. Notion de convergence vers un minimum local et dépendance à l'initialisation. À bien distinguer de l'algorithme des k plus proches voisins (k-NN), qui est supervisé.

Prérequis

k plus proches voisins — surtout le calcul de la distance euclidienne $d (p, q) = (x_{p} - x_{q})^{2} + (y_{p} - y_{q})^{2}$ entre deux points du plan.
Tableaux 2D / images — manipuler des listes de coordonnées et parcourir des collections de points.
Complexité temporelle — savoir compter les opérations d'une double boucle pour donner un $O (\dots)$ .

🎯 Accompagnement Majorant

Le clustering piège tout le monde à l'oral. On confond affectation et mise à jour, minimum local et global, supervisé et non supervisé. Nos mentors alumni X · Centrale · Mines t'entraînent à dérouler l'algorithme au tableau sans jamais te tromper d'étape.

Trouver un mentor →

Partitionner sans étiquettes

En apprentissage supervisé (comme le k-NN), on connaît déjà la classe de chaque exemple d'entraînement : « ce point est un chat, celui-là un chien ». En apprentissage non supervisé, on n'a que des points nus, sans réponse. L'objectif change complètement : on ne cherche pas à prédire une étiquette connue, mais à faire apparaître une structure cachée.

Définition 1.1 — Partitionnement (clustering)

Le partitionnement consiste à répartir un ensemble de $n$ points non étiquetés en $k$ groupes appelés clusters, de sorte que les points d'un même groupe se ressemblent (soient proches) et que deux groupes différents soient bien séparés. C'est une tâche d'apprentissage non supervisé.

Définition 1.2 — Centroïde (barycentre)

Le centroïde d'un groupe de points est son barycentre : le point dont chaque coordonnée est la moyenne des coordonnées correspondantes des points du groupe. Pour un groupe de points $(x_{1}, y_{1}), \dots, (x_{m}, y_{m})$ dans le plan :

$g = (\frac{x _{1} + \dots + x _{m}}{m}, \frac{y _{1} + \dots + y _{m}}{m})$ .

📝 Le centroïde n'est pas forcément l'un des points du groupe : c'est un point « moyen », souvent situé au milieu du nuage, qui peut n'appartenir à aucune donnée réelle.

L'algorithme des k-moyennes

Définition 2.1 — Algorithme des k-moyennes

On fixe le nombre de groupes $k$ . L'algorithme :

Initialisation : choisir $k$ centres de départ (par exemple $k$ points tirés au hasard).
Répéter jusqu'à stabilisation :
- Affectation : associer chaque point au centre le plus proche (distance euclidienne).
- Mise à jour : remplacer chaque centre par le barycentre des points qui lui sont affectés.

On s'arrête quand les groupes (donc les centres) ne changent plus d'une itération à l'autre.

La brique de base : la distance

Tout repose sur « qui est le plus proche ». On mesure avec la distance euclidienne. Un point est un couple (x, y).

import math

def distance(p, q):
    return math.sqrt((p[0] - q[0])**2 + (p[1] - q[1])**2)

🔍 Décryptage ligne par ligne

import mathon importe math pour disposer de math.sqrt, la racine carrée.

def distance(p, q):on définit une fonction qui prend deux points p et q, chacun étant un couple (x, y).

p[0] - q[0]écart des abscisses ; p[1] - q[1] fait de même pour les ordonnées.

(...)**2on élève chaque écart au carré (pour supprimer les signes et pénaliser les grands écarts), puis on somme les deux carrés.

math.sqrt(...)racine carrée de la somme : c'est exactement la longueur du segment entre p et q, par le théorème de Pythagore.

📐 Pour seulement comparer des distances (savoir laquelle est la plus petite), on peut se passer de la racine et comparer les carrés des distances : cela ne change jamais le classement et évite un calcul. La racine ne sert que si l'on veut la vraie valeur.

Une itération complète

On code les deux phases pour $k = 2$ centres c1 et c2. La phase d'affectation range chaque point dans g1 ou g2 ; la phase de mise à jour recalcule les barycentres.

def barycentre(groupe):
    n = len(groupe)
    sx = sum(p[0] for p in groupe)
    sy = sum(p[1] for p in groupe)
    return (sx / n, sy / n)

def une_iteration(points, c1, c2):
    g1, g2 = [], []
    for p in points:                     # phase d'AFFECTATION
        if distance(p, c1) <= distance(p, c2):
            g1.append(p)
        else:
            g2.append(p)
    return barycentre(g1), barycentre(g2)  # phase de MISE A JOUR

🔍 Décryptage ligne par ligne

def barycentre(groupe):calcule le centroïde d'une liste de points.

n = len(groupe)nombre de points du groupe : ce sera le dénominateur de la moyenne.

sx = sum(p[0] for p in groupe)somme de toutes les abscisses ; sy fait pareil pour les ordonnées.

return (sx / n, sy / n)on divise chaque somme par n : on obtient le couple des deux moyennes, soit le barycentre.

g1, g2 = [], []deux listes vides qui vont recevoir les points de chaque groupe.

for p in points:on examine chaque point du nuage, un par un.

if distance(p, c1) <= distance(p, c2):si p est au moins aussi proche de c1 que de c2, il rejoint g1. Le <= tranche les égalités en faveur de g1.

g1.append(p) / g2.append(p)on range p dans le bon groupe.

return barycentre(g1), barycentre(g2)une fois tous les points affectés, on renvoie les deux nouveaux centres : c'est la mise à jour.

⚠ L'ordre est sacré : on affecte tous les points d'abord, puis on déplace les centres. Recalculer un centre au milieu de la boucle d'affectation (avant d'avoir fini de ranger tous les points) donne un autre algorithme, pas les k-moyennes classiques.

Déroulé pas à pas sur un exemple

Prenons 6 points du plan et $k = 2$ . On lance l'algorithme avec deux centres de départ mal choisis (deux points proches, en bas à gauche) pour bien voir les centres se déplacer :

Points : $(1; 1), (1, 5; 2), (3; 4), (5; 7), (3, 5; 5), (4, 5; 5)$ . Centres initiaux : $c_{1} = (1; 1)$ et $c_{2} = (1, 5; 2)$ .

Trois itérations des k-moyennes (affectation puis nouveaux barycentres). L'algorithme se stabilise à l'itération 3.
Itér.	c1 (avant)	c2 (avant)	Groupe 1	Groupe 2	Nouveau c1	Nouveau c2
1	(1 ; 1)	(1,5 ; 2)	{(1;1)}	{(1,5;2),(3;4),(5;7),(3,5;5),(4,5;5)}	(1 ; 1)	(3,5 ; 4,6)
2	(1 ; 1)	(3,5 ; 4,6)	{(1;1),(1,5;2)}	{(3;4),(5;7),(3,5;5),(4,5;5)}	(1,25 ; 1,5)	(4 ; 5,25)
3	(1,25 ; 1,5)	(4 ; 5,25)	{(1;1),(1,5;2)}	{(3;4),(5;7),(3,5;5),(4,5;5)}	(1,25 ; 1,5) ✓	(4 ; 5,25) ✓

À l'itération 3, les groupes sont identiques à ceux de l'itération 2, donc les barycentres ne bougent plus : les centres renvoyés sont égaux à ceux d'entrée. C'est le critère d'arrêt : plus aucun point ne change de groupe. On lit le résultat final : un petit cluster en bas à gauche ${(1; 1), (1, 5; 2)}$ et un gros cluster en haut à droite.

📝 Dès l'itération 1, le point

(1, 5; 2)

était affecté à

c_{2}

parce que ce centre partait juste dessus. Mais une fois

c_{2}

remonté vers le nuage du haut, ce point s'est retrouvé plus près de

c_{1}

et a changé de camp. C'est ce va-et-vient qui fait « travailler » l'algorithme jusqu'à l'équilibre.

Convergence et minimum local

Pourquoi l'algorithme finit-il toujours par s'arrêter ? On mesure la qualité d'un partitionnement par son inertie intra-classe : la somme, sur tous les points, du carré de la distance de chaque point au centre de son groupe. Plus elle est petite, plus les groupes sont compacts.

$I = groupes j \sum p \in groupe j \sum d (p, c_{j})^{2}$ .

Propriété — Décroissance de l'inertie

À chaque itération, la phase d'affectation ne peut que faire baisser (ou laisser égale) l'inertie, car on réaffecte chaque point à un centre au moins aussi proche ; et la phase de mise à jour aussi, car le barycentre est le point qui minimise la somme des carrés des distances aux points de son groupe. L'inertie $I$ décroît donc à chaque étape. Comme il n'existe qu'un nombre fini de partitions possibles des $n$ points en $k$ groupes, cette suite décroissante finit par se stabiliser : l'algorithme converge en un nombre fini d'itérations.

⚠ Converger ne veut pas dire trouver la meilleure solution ! L'algorithme s'arrête sur un minimum local de l'inertie, qui dépend des centres de départ. Deux initialisations différentes peuvent donner deux partitionnements finaux différents, et un seul est peut-être le minimum global.

📐 Parade en pratique : relancer les k-moyennes plusieurs fois avec des initialisations aléatoires distinctes, puis garder le partitionnement d'inertie

I

la plus faible. On approche ainsi le minimum global sans garantie absolue.

🎯 Accompagnement Majorant

« Minimum local vs global » est LA question de colle. Savoir expliquer pourquoi l'inertie décroît, et pourquoi ça ne suffit pas à garantir l'optimum, fait la différence. Nos mentors alumni X · Centrale · Mines te font verbaliser l'argument proprement.

Trouver un mentor →

Choix de k et coût

Comment choisir k ?

Le nombre de groupes $k$ est un paramètre d'entrée : c'est toi qui le fixes, l'algorithme ne le devine pas. Parfois le contexte l'impose (segmenter une clientèle en 3 profils). Sinon, une heuristique classique — la méthode du coude — consiste à tracer l'inertie finale en fonction de $k$ : elle diminue toujours quand $k$ augmente, mais on repère le « coude » à partir duquel gagner un groupe de plus ne fait presque plus baisser l'inertie. Ce $k$ est un bon compromis.

💡 Cas extrême : avec

k = n

(autant de centres que de points), chaque point est son propre groupe et l'inertie vaut 0. C'est parfait numériquement mais totalement inutile — d'où l'intérêt d'un

k

raisonnable.

Complexité d'une itération

À chaque itération, la phase coûteuse est l'affectation : pour chacun des $n$ points, on calcule sa distance à chacun des $k$ centres pour trouver le plus proche. Cela fait $n \times k$ calculs de distance.

Une itération est donc en $O (n \times k)$ calculs de distance (chaque calcul étant lui-même en $O (1)$ en dimension fixée). La mise à jour, elle, parcourt une fois les $n$ points pour cumuler les barycentres, soit $O (n)$ : elle est négligeable devant l'affectation. Sur $t$ itérations, le coût total est $O (t \times n \times k)$ .

📝 On ne connaît pas

t

à l'avance : c'est le nombre d'itérations avant stabilisation, qui dépend des données et de l'initialisation. En pratique il reste petit.

Ne pas confondre k-moyennes et k-NN

Les deux commencent par « k » et parlent de distance euclidienne : d'où la confusion. Mais ce sont deux mondes différents.

Comparaison k-moyennes vs k plus proches voisins.
Critère	k-moyennes (k-means)	k plus proches voisins (k-NN)
Type d'apprentissage	Non supervisé	Supervisé
Données	Points SANS étiquette	Points AVEC étiquette connue
Ce que « k » désigne	Nombre de groupes à former	Nombre de voisins à consulter
But	Partitionner : découvrir des groupes	Classer un nouveau point selon ses voisins
Ce qu'on calcule	Des centres (barycentres) qui bougent	Aucun centre : on regarde les k voisins les plus proches
Itératif ?	Oui, jusqu'à stabilisation	Non : une requête = un vote des voisins

⚠ Phrase-test : « on cherche k centres » → k-moyennes (non supervisé). « on regarde les k voisins d'un point à classer » → k-NN (supervisé). Si les données ont déjà des étiquettes, ce n'est PAS du clustering.

Exercices corrigés

Exo 1Un barycentreFacile

Un groupe contient les points $(2; 0), (4; 2), (6; 4)$ . Donne son centroïde (barycentre).

Voir la correction détaillée

Le barycentre a pour abscisse la moyenne des abscisses :

\frac{2 + 4 + 6}{3} = \frac{12}{3} = 4

Pour l'ordonnée :

\frac{0 + 2 + 4}{3} = \frac{6}{3} = 2

Centroïde :

(4; 2)

. Remarque : ici il tombe pile sur le point

(4; 2)

, mais c'est un hasard — en général le barycentre n'est pas un point du groupe.

Exo 2Une affectationIntermédiaire

On a deux centres $c_{1} = (0; 0)$ et $c_{2} = (6; 5)$ , et les points $(0; 0), (1; 1), (6; 5), (7; 6)$ . Effectue la phase d'affectation, puis calcule les deux nouveaux centres.

Voir la correction détaillée

Point

(0; 0)

: distance à

c_{1}

nulle → groupe 1. Point

(1; 1)

: distance à

c_{1} = 2 \approx 1, 41

, à

c_{2} = 25 + 16 \approx 6, 40

→ groupe 1.

Point

(6; 5)

: distance à

c_{2}

nulle → groupe 2. Point

(7; 6)

: distance à

c_{1} \approx 9, 22

, à

c_{2} = 1 + 1 \approx 1, 41

→ groupe 2.

Groupe 1 =

{(0; 0), (1; 1)}

, barycentre

(\frac{0 + 1}{2}; \frac{0 + 1}{2}) = (0, 5; 0, 5)

Groupe 2 =

{(6; 5), (7; 6)}

, barycentre

(\frac{6 + 7}{2}; \frac{5 + 6}{2}) = (6, 5; 5, 5)

. Nouveaux centres :

(0, 5; 0, 5)

(6, 5; 5, 5)

Exo 3Sensibilité à l'initialisationDifficile

On dispose des points $(0; 0), (1; 0), (10; 0), (11; 0)$ alignés, et $k = 2$ . (a) Avec les centres initiaux $(0; 0)$ et $(1; 0)$ , vers quel partitionnement converge-t-on ? (b) Même question avec les centres initiaux $(0; 0)$ et $(11; 0)$ . (c) Que conclus-tu ?

Voir la correction détaillée

(a) Affectation initiale :

(0; 0) \to c_{1}

;

(1; 0)

est à distance nulle de

c_{2}

→

c_{2}

;

(10; 0)

(11; 0)

sont plus proches de

c_{2} = (1; 0)

que de

c_{1} = (0; 0)

→

c_{2}

. Groupe 1 =

{(0; 0)}

→ centre

(0; 0)

. Groupe 2 =

{(1; 0), (10; 0), (11; 0)}

→ centre

(\frac{1 + 10 + 11}{3}; 0) = (\frac{22}{3}; 0) \approx (7, 33; 0)

Itération suivante :

(0; 0), (1; 0)

sont maintenant plus proches de

c_{1} = (0; 0)

que de

c_{2} \approx (7, 33; 0)

;

(10; 0), (11; 0)

plus proches de

c_{2}

. Groupes

{(0; 0), (1; 0)}

{(10; 0), (11; 0)}

, centres

(0, 5; 0)

(10, 5; 0)

, stables ensuite. Partition finale :

{0, 1} ∣ {10, 11}

(b) Avec

c_{1} = (0; 0), c_{2} = (11; 0)

(0; 0), (1; 0)

vont à

c_{1}

;

(10; 0), (11; 0)

c_{2}

. Barycentres

(0, 5; 0)

(10, 5; 0)

, déjà stables. Même partition

{0, 1} ∣ {10, 11}

(c) Ici les deux initialisations donnent le même (bon) résultat car les groupes sont très séparés. Mais rien ne le garantit en général : sur des données moins nettes, une mauvaise initialisation peut figer un point « isolé » comme un cluster à lui seul et coincer l'algorithme sur un minimum local. D'où la pratique de relancer plusieurs fois et garder l'inertie minimale.

Récap final — Ce qu'il faut absolument retenir

Les k-moyennes : un aller-retour affectation / mise à jour jusqu'à ce que plus rien ne bouge. Vérifie que tu maîtrises chaque point.

Sais-tu dire pourquoi les k-moyennes relèvent de l'apprentissage non supervisé (points sans étiquette) ?
Sais-tu énoncer les deux phases répétées : affectation au centre le plus proche, puis mise à jour par le barycentre ?
Sais-tu calculer un barycentre (moyenne coordonnée par coordonnée) sans hésiter ?
Sais-tu dérouler l'algorithme à la main sur un petit nuage 2D avec $k = 2$ ?
Sais-tu quel est le critère d'arrêt (les groupes ne changent plus) ?
Sais-tu expliquer que l'inertie décroît et que l'algorithme converge vers un minimum local dépendant de l'initialisation ?
Sais-tu donner la complexité d'une itération, $O (n \times k)$ calculs de distance, et dire d'où vient le $n \times k$ ?
Sais-tu distinguer k-moyennes (k centres, non supervisé) de k-NN (k voisins, supervisé) ?

Vue d'ensemble

Prérequis

Partitionner sans étiquettes

L'algorithme des k-moyennes

La brique de base : la distance

Une itération complète

Déroulé pas à pas sur un exemple

Convergence et minimum local

Choix de k et coût

Comment choisir k ?

Complexité d'une itération

Ne pas confondre k-moyennes et k-NN

Exercices corrigés

Récap final — Ce qu'il faut absolument retenir

Débloque la fiche complète

Quiz — k-moyennes

Fiches associées

Recherche par dichotomie

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Tu veux aller plus loin sur ce chapitre ?