Non-Hierarchical Clustering Analysis
K-Means Clustering
K-means est un algorithme de clustering non supervisé qui :
• Regroupe un ensemble de N objets en K groupes distincts.
• Utilise uniquement les caractéristiques (vecteurs d'entrée), sans étiquettes.
• Se base sur une distance (souvent Euclidienne) entre objets et centres (centroïdes).
Étapes de l’algorithme K-means
1. Initialisation :
* Choisir un nombre k de clusters.
* Initialiser les centroïdes (généralement choisis aléatoirement).
* Définir une mesure de distance (comme la distance euclidienne).
2. Étape d’assignation:
* Assigner chaque point au cluster dont le centroïde est le plus proche.
3. Étape de mise à jour :
* Recalculer les centroïdes comme la moyenne des points assignés à chaque cluster.
4. Critères d’arrêt :
* Aucun changement dans les assignations (stabilité atteinte), ou
* Un nombre maximal d’itérations est atteint.
Cet algorithme est non supervisé (pas de labels).
Sensible aux valeurs initiales, donc souvent répété plusieurs fois avec des initialisations différentes.
Exemple d’application
The Manhattan distance matrix between différents objects is given in table.
Apply K-means starting from the two clusters (centroïds, k=2)
1- initialisattion step
Cette etape consiste à choisir deux objets comme points de départ pour les centroïdes. Ici, la méthode choisie est de prendre les
deux objets les plus éloignés selon la distance de Manhattan (qui additionne les valeurs absolues des différences de
coordonnées au lieu d’utiliser la distance euclidienne).
Dans cet exemple, les deux objets sélectionnés comme les plus éloignés sont C et G.
• We calculate the distances from each object to the two clusters.
• The remaining objects are examined one by one and located in relation to the nearest cluster (in terms of minimum
Manhattan distance)
Update:
The centroïd (mean vector) is recalculated for each cluster
Stop. No new relocation les memes centroid se repetent
How Evaluating Clustering Algorithm
pour évaluer la qualité d’un regroupement dans l’algorithme K-means :
l’inertie et la distorsion.
L’inertie, aussi appelée WCSS (Within-Cluster Sum of Squares), mesure la compacité des clusters. Elle est calculée comme la
somme des distances au carré entre chaque point et le centroïde de son cluster. Plus cette somme est petite, plus les points
sont proches du centroïde, ce qui signifie que les clusters sont compacts et bien définis.
La formule donnée pour l’inertie est :
The idea behind good clustering is having a small value of inertia, and small number of clusters.
La distorsion
C’est est une autre mesure, qui correspond à la moyenne des distances au carré entre les points et leur centroïde. Elle est
calculée en divisant l’inertie par le nombre de points dans chaque cluster, puis en faisant la moyenne sur tous les clusters.
La formule donnée pour la distorsion est :
La métrique utilisée pour ces calculs est souvent la distance euclidienne.
Silhouette Score : mesure dans quelle mesure un point est bien placé dans son cluster :
Il compare :
a(i): la cohésion → distance moyenne entre le point et les autres points de son propre cluster.
b(i) : la séparation → distance moyenne entre le point et les points du cluster le plus proche (autre que le sien).
Formule du coefficient silhouette pour un point i:
interprétation :
* s(i) proche de +1: le point est bien placé dans son cluster (bonne séparation).
* s(i) proche de 0 : le point est à la frontière entre deux clusters.
* s(i) proche de -1 : le point est mal placé, il pourrait appartenir à un autre cluster.
---
Utilisation
Le score moyen de tous les points donne une idée de la qualité globale du clustering.
Il peut aider à choisir le bon K (nombre de clusters) : on teste plusieurs K et on garde celui qui donne le meilleur score moyen.
L’indice de Dunn est défini comme le rapport entre :
* la plus petite distance entre deux clusters différents (distance inter-cluster minimale),
* et la plus grande distance entre deux points d’un même cluster (diamètre intra-cluster maximal).
Mathématiquement, on note :
Plus l’indice de Dunn est grand, mieux le clustering est considéré, car cela signifie que les clusters sont bien séparés (inter-cluster
élevé) et compacts (intra-cluster faible).
Forces de l’algorithme K-Means :
Facile à implémenter : L’algorithme est simple, basé sur des opérations élémentaires (moyenne, distance).
Rapide et efficace: Il converge généralement rapidement, surtout sur de grands ensembles de données bien séparés.
Un seul paramètre à ajuster (K): Cela facilite l’expérimentation. L’impact du choix de K est facilement visible (ex. : méthode du
coude).
Faiblesses de l’algorithme K-Means :
Sensible aux valeurs aberrantes (outliers) : Un point éloigné peut fausser le calcul des centres.
Convergence vers un minimum local: Le résultat dépend de l’initialisation des centres ; il peut ne pas être optimal globalement.
Résultat instable: Des centroïdes initiaux différents peuvent conduire à des regroupements totalement différents.
Risque de boucle infinie : Si les critères d'arrêt sont mal définis (ex. : seuil de variation trop petit), l’algorithme peut ne jamais
s’arrêter.
Une des limitations importantes de K-Means est que l’algorithme suppose que les clusters sont de forme sphérique ou arrondie.
Cela signifie qu’il fonctionne bien lorsque les données sont réparties de manière circulaire autour de centres bien définis. En
revanche, pour des données ayant des formes plus complexes, allongées ou non convexes, K-Means n’arrive pas à bien
distinguer les regroupements. Ainsi, il n’est pas adapté à des structures de données dont les clusters ont une géométrie
irrégulière.
