Initialisation

L'algorithme commence par sélectionner aléatoirement K centres de clusters initiaux, également appelés centroïdes. Ces centroïdes servent de points de départ pour chaque cluster. Une méthode courante consiste à choisir aléatoirement K points de données du jeu de données pour être les centroïdes initiaux.

Étape d'attribution

À cette étape, chaque point de données est attribué au centroïde le plus proche. La distance est généralement mesurée à l'aide de la distance euclidienne, mais d'autres mesures de distance peuvent également être utilisées. Chaque point de données est placé dans le cluster représenté par le centroïde le plus proche.

Étape de mise à jour

Une fois que tous les points de données sont attribués à des clusters, les centroïdes sont recalculés. Pour chaque cluster, le nouveau centroïde est calculé comme la moyenne de tous les points de données appartenant à ce cluster. Essentiellement, le centroïde est déplacé vers le centre de son cluster.

Itération

Les étapes 2 et 3 sont répétées de manière itérative. À chaque itération, les points de données sont réattribués aux clusters en fonction des centroïdes mis à jour, puis les centroïdes sont recalculés selon les nouvelles attributions de clusters. Ce processus itératif se poursuit jusqu'à ce qu'un critère d'arrêt soit atteint.

Convergence

L'algorithme s'arrête lorsque l'une des conditions suivantes est remplie :

• Les centroïdes ne changent pas significativement : les positions des centroïdes se stabilisent, ce qui signifie que lors des itérations suivantes, il y a peu de changement dans leur emplacement ;

• Les attributions des points de données ne changent pas : les points de données restent dans les mêmes clusters, indiquant que la structure des clusters est devenue stable ;

• Le nombre maximal d'itérations est atteint : un nombre maximal d'itérations prédéfini est atteint. Cela empêche l'algorithme de s'exécuter indéfiniment.

Après convergence, l'algorithme K-means a partitionné les données en K clusters, chaque cluster étant représenté par son centroïde. Les clusters résultants visent à être cohésifs en interne et séparés en externe selon la métrique de distance choisie et le processus d'affinement itératif.