Prépa Code Connexion Inscription

L'algorithme des k-moyennes (k-means) regroupe un nuage de points en k clusters. A chaque iteration :

1. Chaque point est affecte au cluster dont le centre est le plus proche (distance euclidienne).
2. Chaque centre est deplace au barycentre (moyenne) des points qui lui sont affectes.

Ecrire une fonction kmeans_etape(points, centres) qui effectue une seule iteration et renvoie la nouvelle liste de centres obtenus.

• points est une liste de tuples (x, y).
• centres est une liste de tuples (x, y) (les centres initiaux).
• La sortie est une liste [[x, y], ...] de listes (et non de tuples) de meme longueur que centres, dans le meme ordre.

Cas particulier : si un cluster se retrouve vide (aucun point ne lui est affecte), son centre conserve les memes coordonnees (converties en liste [x, y]).

En cas d'egalite de distance entre un point et plusieurs centres, affecter le point au centre d'indice le plus petit.