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

modifier

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

modifier

Références

modifier
  1. The illustration was prepared with the Java applet, E.M. Mirkes, K-means and K-medoids: applet. University of Leicester, 2011.
  2. Stéphane Tufféry, Data Mining et statistique décisionnelle, Éditions Technip, page 244
  3. (en) Leonard Kaufman et Peter J. Rousseeuw, « Partitioning Around Medoids (Program PAM) », Wiley Series in Probability and Statistics,‎ (ISBN 978-0-470-31680-1, DOI 10.1002/9780470316801.ch2)

Bibliographie

modifier