k means algorithm

algorithme k-means

Il s'agit d'une implémentation Python de l'algorithme k-means comprenant la méthode du coude et la méthode de la silhouette pour sélectionner le K optimal.

K-means est un algorithme de clustering populaire utilisé pour partitionner les données en K clusters. Il fonctionne en attribuant de manière itérative chaque point de données au centroïde de cluster le plus proche, puis en recalculant le centroïde de chaque cluster en fonction des points de données qui lui sont attribués. Le processus est répété jusqu'à convergence.

Algorithme

• Sélectionnez au hasard K centroïdes de cluster initiaux à partir des points de données.
• Attribuez chaque point de données au centre de gravité du cluster le plus proche.
• Recalculez le centroïde de chaque cluster en fonction des points de données qui lui sont attribués.
• Répétez les étapes 2 et 3 jusqu'à convergence (c'est-à-dire lorsque les affectations de cluster ne changent plus).

Fonction objectif

L'objectif de k-means est de minimiser la somme des carrés des distances entre chaque point de données et le centroïde de cluster qui lui est attribué. La fonction objectif peut s’écrire : $$J = sum_{j=1}^K sum_{i=1}^N||x_i^j - mu_j||^2$$ où $x_i^j$ est le i-th point de données du cluster j , μj est le centroïde du cluster j et N est le nombre total de points de données.

Méthode du coude

La méthode Elbow est une heuristique utilisée pour déterminer le nombre optimal de clusters dans le clustering K-Means. La méthode trace la somme des carrés des distances entre chaque observation et son centroïde attribué en fonction du nombre de clusters. Le point « coude » sur le tracé indique le nombre de grappes pour lesquelles l'ajout de grappes supplémentaires n'entraîne pas de réduction significative de la somme des carrés des distances.

La méthode Elbow peut être résumée par les étapes suivantes :

• Exécutez le clustering K-Means pour une plage de valeurs k
• Calculer la somme des distances au carré pour chaque valeur k
• Tracer la somme des carrés des distances en fonction de k
• Identifiez le point "coude" sur le tracé

Méthode des silhouettes

La méthode Silhouette est une autre heuristique utilisée pour déterminer le nombre optimal de clusters dans le clustering K-Means. La méthode mesure la qualité de l'affectation des clusters de chaque observation en calculant son coefficient de silhouette. Le coefficient de silhouette varie de -1 à 1, où une valeur de 1 indique que l'observation est bien regroupée et une valeur de -1 indique que l'observation est mal classée. La formule de calcul du coefficient de silhouette pour un point de données i est : $$s(i) = frac{(b(i) - a(i))}{max(a(i), b(i))}$$ où a(i) est la distance moyenne entre i et tous les autres points de données de son cluster, et b(i) est la distance moyenne minimale entre i et tous les autres clusters (c'est-à-dire le cluster avec le centre de gravité le plus proche). Le coefficient de silhouette pour l'ensemble du clustering est la moyenne des coefficients de silhouette pour tous les points de données.

La méthode Silhouette peut être résumée par les étapes suivantes :

• Exécutez le clustering K-Means pour une plage de valeurs k
• Pour chaque observation, calculez le coefficient de silhouette
• Calculer le coefficient de silhouette moyen pour chaque valeur k
• Tracez le coefficient de silhouette moyen en fonction de k
• Identifiez la valeur k avec le coefficient de silhouette moyen le plus élevé