Outil de Clustering K-Means

Pseudocode

Deux étapes qui alternent jusqu'à ce que plus rien ne bouge: affecter chaque point au centroïde le plus proche, puis déplacer chaque centroïde vers la moyenne des points qui lui ont été affectés.

KMoyennes(points, k):
    initialiser k centroides (aleatoire, ou k-means++)

    repeter jusqu a ce que les affectations ne changent plus:
        // Etape d affectation
        pour chaque point p:
            groupe[p] = argmin sur c de distance(p, c)

        // Etape de mise a jour
        pour chaque centroide c:
            c = moyenne des points avec groupe[p] == c

    renvoyer groupes et centroides

Chaque étape réduit la somme des carrés intra-groupes ou la laisse inchangée, et il n'existe qu'un nombre fini d'affectations possibles, l'algorithme termine donc toujours. Ce qu'il ne garantit pas, c'est de terminer à l'optimum global: il converge vers un minimum local qui dépend entièrement de l'initialisation, et c'est la limite pratique qu'il faut gérer.

Exemple détaillé, étape par étape

Regroupe quatre points en deux groupes en partant délibérément d'une mauvaise initialisation, les deux centroïdes étant placés dans le même groupe réel.

Graphe d'exemple: Points en (1,1), (2,1), (8,8) et (9,8). Centroïdes initiaux placés en (1,1) et (2,1), donc tous deux dans le groupe inférieur gauche.

1. Itération 1, affectation. Le point (1,1) rejoint le premier centroïde. Les trois autres, (2,1), (8,8) et (9,8), sont plus proches du second. La partition est nettement mauvaise: un groupe d'un point et un groupe de trois.
2. Itération 1, mise à jour. Le premier centroïde reste en (1,1). Le second se déplace vers la moyenne de (2,1), (8,8) et (9,8), soit (6,33, 5,67). La somme des carrés intra-groupes vaut 61,333.
3. Itération 2, affectation. Le second centroïde ayant migré vers le haut à droite, le point (2,1) est désormais plus proche du premier. La partition devient (1,1) et (2,1) contre (8,8) et (9,8), soit la bonne.
4. Itération 2, mise à jour. Les centroïdes se déplacent vers (1,5, 1) et (8,5, 8). La somme des carrés intra-groupes chute de 61,333 à 1,0.
5. Itération 3, convergence. Les affectations ne changent plus et les centroïdes non plus. L'algorithme s'arrête.

La convergence intervient en deux itérations et la somme des carrés intra-groupes chute de 61,333 à 1,0. Note que l'algorithme s'est remis d'une initialisation délibérément mauvaise, les deux centroïdes se trouvant dans le même groupe réel. Ce n'est pas garanti: sur d'autres données, une telle initialisation peut te bloquer dans un minimum local. C'est pourquoi k-means++ choisit des centroïdes initiaux bien écartés et pourquoi il vaut la peine de lancer l'algorithme plusieurs fois avec des initialisations différentes.

Complexité et son origine

Temps: O(n · k · i · d) · Espace: O(n + k·d)

Chaque itération affecte n points en les comparant à k centroïdes en d dimensions, soit O(n fois k fois d), et l'étape de mise à jour reparcourt les points au même coût. Avec i itérations, le total est O(n fois k fois i fois d). En pratique i reste petit, de l'ordre de quelques dizaines, même si le pire cas peut croître de façon superpolynomiale. L'espace tient à l'affectation de groupe par point plus les k centroïdes. Trouver le regroupement optimal au sens de la somme des carrés est NP-difficile même pour k égal à 2, l'algorithme de Lloyd universellement employé est donc une heuristique: rapide et efficace en pratique, sans garantie d'optimalité.

Quand utiliser Clustering Logistique K-Means, et quand l'éviter

Choisis selon la forme attendue des groupes et selon que tu connais k à l'avance.

Pièges fréquents

• Initialiser au hasard sans k-means++. Une mauvaise initialisation peut converger vers un minimum local nettement moins bon. K-means++ choisit les centres initiaux avec une probabilité proportionnelle au carré de la distance aux centres déjà retenus, ce qui les écarte et améliore beaucoup le résultat attendu pour un surcoût négligeable.
• Ne pas normaliser les variables. K-moyennes utilise la distance euclidienne, une variable mesurée en milliers domine donc une variable comprise entre 0 et 1. Si les échelles diffèrent, normalise avant de regrouper, sinon les groupes ne refléteront que la variable de plus grande amplitude.
• Choisir k d après la seule somme des carrés. La somme des carrés intra-groupes décroît toujours quand k augmente, jusqu'à atteindre zéro lorsque k égale le nombre de points. Utilise la méthode du coude, la silhouette ou la statistique du gap, pas le minimum absolu.
• L appliquer à des groupes non sphériques. K-moyennes partitionne l'espace en cellules de Voronoï, il ne peut donc produire que des frontières convexes. Sur des groupes en croissant ou imbriqués il échoue par construction, quel que soit le nombre d'exécutions. DBSCAN ou le regroupement spectral sont alors les alternatives.
• Ne l exécuter qu une seule fois. Le résultat dépendant de l'initialisation, une exécution unique ne dit pas si tu es tombé dans un minimum local. Lance plusieurs exécutions avec des graines différentes et retiens celle de plus faible somme des carrés.

Questions fréquentes

Qu'est-ce que le regroupement k-moyennes?

K-moyennes partitionne un ensemble de points en k groupes en alternant deux étapes: affecter chaque point au centroïde le plus proche, puis déplacer chaque centroïde vers la moyenne de ses points affectés. Cela se répète jusqu'à ce que les affectations cessent de changer, en minimisant la somme des distances au carré à l'intérieur de chaque groupe.

Quelle est la complexité temporelle de k-moyennes?

O(n fois k fois i fois d), où n est le nombre de points, k celui des groupes, i celui des itérations et d la dimension. En pratique i reste de l'ordre de quelques dizaines. Trouver le regroupement optimal au sens de la somme des carrés est NP-difficile même pour k égal à 2, l'algorithme standard est donc une heuristique sans garantie d'optimalité.

K-moyennes converge-t-il toujours?

Oui, il termine toujours, car chaque étape réduit ou maintient la somme des carrés intra-groupes et il n'existe qu'un nombre fini d'affectations possibles. Mais il converge vers un minimum local, pas nécessairement global, et lequel il atteint dépend entièrement de l'initialisation.

Pourquoi l'initialisation compte-t-elle en k-moyennes?

Parce que l'algorithme ne peut qu'améliorer localement à partir de son point de départ. Des centres initiaux mal placés peuvent le bloquer sur une partition nettement moins bonne que l'optimale. K-means++ atténue cela en choisissant des centres initiaux bien écartés, et lancer plusieurs exécutions avec des graines différentes en retenant la meilleure est la pratique courante.

Comment choisit-on la valeur de k?

Il n'y a pas de réponse unique. La méthode du coude trace la somme des carrés en fonction de k et cherche le point où l'amélioration s'aplatit. Le coefficient de silhouette mesure la qualité de séparation des groupes. La statistique du gap compare à des données aléatoires de référence. Souvent, la connaissance du domaine l'emporte sur les trois.