K-médoïdes

K-médoïdes versus k-means. Les figures 1a-1f présentent un cas typique de la convergence de l'algorithme des k-means vers un minimum local. Le résultat de la classification par les k-means est ici en contradiction avec le partitionnement évident des données. Les figures 2a-2h présente l'algorithme des k-médoïdes avec la même configuration initiale des médoïdes (Fig. 2a) et converge vers la classification la plus évidente. Les cercles représentent les données, les étoiles à 4 branches représentent les moyennes, et les étoiles à neuf branches les médoïdes.

Le partitionnement en k-médoïdes est une méthode de partitionnement plus robuste vis-à-vis des données aberrantes (outliers) que celle des k-moyennes (k-means). La différence majeure avec les k-moyennes est que le point central d'une classe est un point du jeu de données (médoïde). En statistique, le médoïde d'une classe est défini comme le point de la classe dont la dissimilarité moyenne avec tous les autres points de la classe est minimale, c'est-à-dire qu'il s'agit du point le plus central de la classe.

Algorithme

En général, le problème des k-médoïdes est NP-difficile à résoudre exactement. Il existe donc de nombreuses solutions heuristiques.

L'algorithme PAM (Partitioning Around Medoids) est l'un des premiers algorithmes introduits pour résoudre le problème de k-médoïdes.

Voir aussi

• K-moyennes