K-medoids : comprendre les groupes, les médoïdes et la robustesse

Un mécanisme concret, des calculs simples et les distinctions utiles pour choisir une méthode de clustering.

K-medoids répartit les observations en k groupes représentés chacun par une observation réelle : le médoïde. Celui-ci minimise la somme des dissimilarités à l’intérieur de son groupe. L’algorithme PAM recherche une bonne configuration sans garantir l’optimum global. Un exemple permet de comprendre pourquoi ce représentant peut rester stable face à une valeur extrême, sans transformer cette propriété en garantie universelle de robustesse. [3]

In this article

1. Le médoïde : représenter un groupe par un de ses membres
2. Un exemple calculé : deux groupes sur une droite
3. PAM : initialiser, affecter, améliorer
4. Robustesse : ce qu’un exemple montre vraiment
5. Choisir k et gérer le coût de calcul

1. Le médoïde : représenter un groupe par un de ses membres

K-medoids est une méthode d’apprentissage non supervisé : elle partitionne un ensemble de n objets en k groupes, sans partir d’étiquettes de classes. Le nombre k doit être fixé avant l’exécution. Chaque groupe possède un représentant, appelé médoïde : parmi ses membres, c’est celui dont la somme des dissimilarités avec les autres membres est minimale. « Central » signifie donc ici central selon la dissimilarité choisie, et non nécessairement placé au centre visuel d’un nuage de points. [3]

La distinction essentielle est que le médoïde appartient réellement aux données. Il ne s’agit pas d’un représentant synthétique : on peut retrouver l’observation qui incarne le groupe. Les points sont habituellement affectés au médoïde le plus proche. L’objectif consiste alors à réduire la somme des dissimilarités entre chaque observation et son représentant. Il faut distinguer cet objectif de sa résolution : définir ce que serait une bonne partition ne fournit pas automatiquement une méthode capable de trouver la meilleure. [3]

2. Un exemple calculé : deux groupes sur une droite

Prenons l’exemple hypothétique des valeurs 0, 2, 3 et 10, avec k = 2 et la distance absolue : d(a, b) = |a − b|. Choisissons les médoïdes 2 et 10. L’affectation au représentant le plus proche produit les groupes {0, 2, 3} et {10}. Le coût total vaut 2 + 0 + 1 + 0 = 3. Pour vérifier le représentant du premier groupe, comparons les trois observations candidates. Le tableau applique directement la définition du médoïde ; ce n’est pas le résultat d’une exécution logicielle. [3]

Le point 2 est donc le médoïde de {0, 2, 3}, puisque son coût est le plus faible. Le groupe {10}, réduit à une observation, a pour médoïde 10 et un coût nul. Cet exemple distingue deux opérations : affecter les observations aux représentants, puis évaluer les représentants. Dans une recherche de partition, remplacer un médoïde peut aussi modifier les affectations ; il ne suffit donc pas d’évaluer chaque groupe une fois pour considérer tout le problème comme résolu. [3]

Candidat dans {0, 2, 3}	Somme des distances absolues	Coût
0	\|0 − 0\| + \|2 − 0\| + \|3 − 0\|	5 [3]
2	\|0 − 2\| + \|2 − 2\| + \|3 − 2\|	3 [3]
3	\|0 − 3\| + \|2 − 3\| + \|3 − 3\|	4 [3]

3. PAM : initialiser, affecter, améliorer

PAM, pour Partitioning Around Medoids, est un algorithme classique pour rechercher une partition en médoïdes. Sa phase BUILD sélectionne progressivement k observations comme représentants en cherchant à réduire le coût. Les observations sont ensuite associées au médoïde le plus proche. La phase SWAP cherche à améliorer la configuration par des échanges de représentants, tant que le coût diminue. Le principe est de remettre en question le choix des médoïdes plutôt que de conserver définitivement les premiers représentants sélectionnés. [3]

PAM est une heuristique gloutonne : il cherche des améliorations sans examiner exhaustivement toutes les partitions possibles. Il peut donc manquer l’optimum global. Cette distinction est importante pour interpréter le résultat : l’arrêt de la recherche n’est pas une preuve que toute autre configuration serait moins bonne. Le problème exact des k-medoids est NP-difficile ; recourir à une heuristique répond à cette difficulté de recherche, mais ne supprime pas l’incertitude sur la qualité optimale de la solution. [3]

4. Robustesse : ce qu’un exemple montre vraiment

Considérons maintenant un seul groupe hypothétique : {1, 2, 3, 100}, toujours avec la distance absolue. Les coûts des candidats 1, 2, 3 et 100 valent respectivement 102, 100, 100 et 294. Les points 2 et 3 sont donc tous deux des médoïdes. La moyenne arithmétique vaut pourtant 26,5. Ce calcul montre une différence concrète : dans cet exemple, la valeur extrême n’entraîne pas le représentant vers elle comme elle déplace la moyenne. Il montre aussi que le médoïde n’est pas nécessairement unique. [3]

Il serait toutefois excessif d’en conclure que K-medoids est insensible à toutes les anomalies. L’exemple concerne un groupe et une distance précise ; il ne démontre pas le comportement de toutes les partitions. Une limite documentée concerne les groupes de diamètres très différents : l’affectation au médoïde le plus proche peut alors mal convenir. Lorsque les formes ou les diamètres varient, des méthodes fondées sur la densité ou des modèles de mélanges gaussiens peuvent être plus adaptés. Robustesse du représentant et adéquation de la partition sont deux questions distinctes. [3]

5. Choisir k et gérer le coût de calcul

K-medoids ne détermine pas automatiquement combien de groupes il faut rechercher. La méthode de la silhouette est une possibilité pour évaluer la pertinence d’une valeur de k. En pratique, cela invite à comparer plusieurs valeurs plutôt qu’à considérer le premier découpage obtenu comme définitif. La lecture des résultats doit aussi vérifier ce que représentent les médoïdes et si la géométrie des groupes convient à une affectation au représentant le plus proche. Un faible coût ne répond pas, à lui seul, à toutes ces questions d’interprétation. [3]

Le volume de données constitue une autre contrainte : un article consacré à WOA-kMedoids souligne le coût quadratique de PAM traditionnel. Des variantes proposent d’autres compromis de recherche. CLARA applique PAM à plusieurs sous-échantillons et conserve le meilleur résultat ; CLARANS n’explore qu’une partie des échanges possibles ; BanditPAM utilise les bandits multi-bras pour sélectionner des échanges candidats. Ces mécanismes ne constituent pas une preuve qu’une variante serait toujours supérieure : il faut distinguer réduction de l’effort de recherche et qualité du regroupement obtenu. [1], [3]

Frequently asked questions

Un médoïde est-il toujours unique ?

Non. Plusieurs observations peuvent minimiser la même somme de dissimilarités. Dans l’exemple {1, 2, 3, 100} avec la distance absolue, 2 et 3 ont chacun un coût de 100. Tous deux satisfont donc la définition du médoïde. [3]

K-medoids et PAM désignent-ils exactement la même chose ?

K-medoids désigne le problème de partitionnement autour de représentants observés. PAM est un algorithme pour rechercher une solution à ce problème. D’autres approches, notamment CLARA et CLARANS, modifient la manière d’explorer les configurations. [3]

La distance choisie importe-t-elle vraiment ?

Oui : le médoïde minimise une somme de dissimilarités. Le choix de cette dissimilarité définit donc ce que signifie être central. Les exemples présentés utilisent la distance absolue ; leurs calculs ne doivent pas être transposés sans modification à une autre fonction. [3]

La silhouette dispense-t-elle de choisir k ?

Non. K-medoids exige un nombre de groupes fixé à l’avance. La silhouette aide à évaluer la pertinence d’une valeur de k ; elle constitue un outil de comparaison, pas une suppression de ce paramètre. [3]

Faut-il utiliser K-medoids pour tous les groupes de formes irrégulières ?

Non. Un représentant réel ne garantit pas une partition adaptée à toutes les géométries. Les groupes de diamètres très différents posent notamment problème. Les méthodes par densité ou les mélanges gaussiens sont des possibilités à examiner lorsque les formes ou les diamètres varient. [3]

Conclusion

La force de K-medoids est de résumer chaque groupe par une observation concrète, choisie selon une somme de dissimilarités. PAM rend cette recherche praticable grâce à des améliorations successives, sans garantir la meilleure partition possible. Pour bien interpréter un résultat, il faut garder ensemble quatre éléments : la dissimilarité utilisée, le nombre k, la géométrie des groupes et l’effort de calcul. La stabilité illustrée face à une valeur extrême est utile à comprendre, mais elle ne remplace pas cette évaluation. [3]

Source notes

Les références présentées ne permettent pas d’établir une garantie générale de robustesse aux valeurs aberrantes, ni une supériorité universelle sur K-means.

Explore next

Sources

Open a source or expand its cited passages.

Relevance scores are model estimates of how well each source addresses this question, not probabilities or fact-check ratings. Reasoned guidance is identified on hover.