K-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^[2]). 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.

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^[1].

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^[3] (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