Notre article vous guide à travers un exercice pratique pour mieux comprendre l’algorithme k-means. Plongez dans cette lecture pour élucider cette méthode de clustering et découvrir comment elle peut transformer vos données en informations claires et exploitables.

INTRODUCTION

L’entreprise MAAV réalise une étude sur ses clients afin de les regrouper en trois clusters. Son objectif est d’attribuer des bonus en fonction de leurs transferts sur la puce les mardis et vendredis. Pour le premier groupe, elle souhaite offrir un bonus de 100 %, pour le second, un bonus de 150 % et pour le troisième, un bonus de 200 %. Elle fait donc appel à vous pour cette tâche.

Vous décidez d’utiliser un échantillon des clients de l’entreprise MAAV pour effectuer votre analyse.

• Pour rappel, un échantillon est un sous-ensemble représentatif de la population. (Voir article Statistique inférentielle : Importance et exemples concrets).

DEVELOPPEMENT

Vous sélectionnez donc les clients suivants :

Votre objectif est d’utiliser l’algorithme k-means pour créer trois groupes, chacun ayant son propre bonus.

À partir de cette base de donnée, nous pouvons faire une représentation graphique dans laquelle nous placerons les points suivants : A(4 000 ; 6 000), B(2 000 ; 1 000), C(8 000 ; 300), D(3 000 ; 8 000), E(7 000 ; 9 000), F(400 ; 800), G(1 500 ; 6 500), H(9 000 ; 9 500), K(700 ; 500) et N(300 ; 300).

On obtient donc le graphique suivant :

Puisque nous voulons former trois groupes, nous allons choisir aléatoirement trois points sur le plan, comme le fait l’algorithme. Ces points sont appelés centroïdes. Soient donc les points : C1(5 000 ; 7 000), C2(8 000 ; 7 000) et C3(5 000 ; 10 000).

Représentation graphique :

Dessinons un tableau pour représenter tout cela :

D’abord, nous calculerons les distances des points A, B, C, D, E, F, G, H, K et N jusqu’aux centroïdes c1, c2 et c3 en utilisant la distance euclidienne.

Pour calculer la distance du point A au centroïde C1, on utilise la formule de la distance euclidienne :

1414,213562

Et on note le résultat dans le tableau comme suit :

Nous procédons de la même manière pour les autres centroïdes et on obtient :

Après cela, on note dans la colonne ” Cluster ” le numéro du centroïde le plus proche du point ( celui par rapport auquel la distance est la plus petite ). Par exemple le centroïde le plus proche du point A est c1, on notera donc 1.

De cette même manière, on obtient les résultats suivants :

En faisant pareil pour tous les points, on obtient le tableau suivant:

En image, voici le clustering fait par l’ordinateur :

L’on voit bien le cluster 1 en violet, le cluster 2 en bleu et le cluster 3 en orange.

Ensuite, nous mettons à jour les centroïdes. Pour minimiser les erreurs, comme mentionné dans notre article précédent, nous choisissons les centres de gravité des points formant chaque cluster comme nouveaux centroïdes.

Nous obtenons ainsi les nouveaux centroïdes : c1(1 700 ; 3 300), c2(8 500 ; 4 900) et c3(7 000 ; 9 000). Nous refaisons alors les mêmes calculs de distance.

Ensuite, nous notons dans la colonne “Nouveau Cluster” le numéro du centroïde le plus proche pour chaque point.

On obtient le clustering suivant :

Enfin, nous allons effacer les éléments de la colonne ” Cluster ” et les remplacer par ceux de la colonne ” Nouveau Cluster “. Puis nous allons tout simplement reprendre les calculs des distances afin d’obtenir de nouveaux clustering.

L’on s’arrêtera lorsque les clustering se seront stabilisés ( c’est a dire que le clustering obtenu a l’étape n+1 est le même que celui obtenu a l’étape n ).

On obtient donc :

On obtient donc les 3 clusters suivants :

Cluster 1 : B, F, K, N ( Celui des clients qui dépensent peu )  donc bonus de 100 %

Cluster 2 : C ( Celui de ceux qui dépensent fortement seulement le MARDI ou en semaine ) donc bonus de 150 %

Cluster 3 : A, D, E, G, H ( Celui de ceux qui dépensent assez les MARDI et VENDREDI ) donc bonus de 200 %

Remarquons que si nous étions tombé de façon aléatoire sur d’autres centroïdes, nous aurions eu un autre clustering. Par exemple si nous avions eu comme centroïdes de départ, les points : c1(1 000 ; 3 000), c2(1 500 ; 8 000) et c3( 8 000 ; 5 000), au bout de seulement 2 itérations, les clusters se seraient stabilisés et nous aurions eu :

CONCLUSION

Voici ainsi expliqué l’algorithme k-means. Si vous voulez mieux le comprendre, vous pouvez lire cette vidéo qui m’a servi de référence : K Means Clustering Algorithm

Une question vous trouble sans doute : les résultats diffèrent-ils en fonction des centroïdes initiaux, et donc, deux machines peuvent-elles obtenir des résultats différents ? Cela pourrait être dangereux pour la prise de décision. Ne vous inquiétez pas. Pour remédier à cela, l’algorithme effectue au moins 30 clustering différents et affiche comme résultat une moyenne des différents clustering obtenus.

On comprend donc que les centroïdes initiaux n’affectent pas notre résultat final. Cependant, une autre question se pose : “Pourquoi forcément trois clusters ? Pourquoi pas plus ? Et comment savoir si nous avons choisi le bon nombre de clusters ?”

Nous répondrons à ces questions dans notre prochain article !