Cette petite modification peut considérablement améliorer la durée d'exécution de KMeans

KMeans est un algorithme de clustering populaire, mais dont la durée d'exécution est élevée. Voici comment une petite modification peut améliorer de manière significative sa durée d'exécution.

KMeans sélectionne les centroïdes initiaux de manière aléatoire. Par conséquent, il ne parvient pas toujours à converger. Cela nous oblige à répéter le clustering plusieurs fois avec une initialisation différente.

KMeans++ adopte une approche plus intelligente pour initialiser les centroïdes. Le premier centroïde est choisi au hasard. Mais le centroïde suivant est choisi en fonction de la distance par rapport au premier centroïde.

En d'autres termes, un point éloigné du premier centroïde a plus de chances d'être sélectionné comme centroïde initial. De cette manière, tous les centroïdes initiaux sont susceptibles de se trouver déjà dans des clusters différents et l'algorithme peut converger plus rapidement.

L'illustration ci-dessous montre l'initialisation des centroïdes de KMeans++ :

Notebook démonstration KMeans vs. KMeans++