Segmentation non hiérarchique par les k-médianes

L'objectif de ce TD est de manipuler l'algorithme des k-médianes disponible dans R.

Pour la réalisation de ce TP, on suppose que le TP sur l'algorithme des k-moyennes a été fait auparavant.

Les k-médianes en R

La fonction pam()

L'algorithme des k-médianes est disponible au travers de la fonction pam() de la bibliothèque cluster de R. Il faut donc toujours taper la commande library (cluster) avant de pouvoir utiliser les fonctions qui vont être décrites et manipulées ci-dessous.. L'utilisation en est très simple :

iris.pam.3 <- pam (iris [,1:4], 3)

exécute l'algorithme des k-médianes sur le jeu de données iris en utilisant les quatre attributs longueur et largeur des sépales et des pétales, en utilisant 3 centres.
À l'issue de son exécution, pam() a associé chaque donnée à un groupe ; les groupes sont numérotés de 1 à K.

pam() fournit une liste d'objets (on sait cela en tapant la commande help("pam.object") :

Visualisation de la segmentation

On peut visualiser le résultat de la segmentation à l'aide de couleurs. Ainsi, supposons que vous ayez segmenté en trois segments les iris et placé le résultat dans iris.pam.3.

  plot (iris$Petal.Length, iris$Petal.Width, col = iris.pam.3$clustering)

représente chacun des iris dans le plan longueur des pétales x largeur des pétales et coloré en fonction de la classe que lui a affecté pam().

On peut ajouter la position des centres sur ce graphique :

  points (iris.pam.3$medoids, pch=19)

pch=19 indique que l'on veut que les points soient représentés par des disques pleins.

La silhouette d'une segmentation

On obtient la silhouette d'une segmentation par la commande :

  iris.pam.3.si <- silhouette (iris.pam.3)

que l'on peut représenter graphiquement par la fonction plot() :

  plot (iris.pam.3.si)

On peut obtenir des statistiques sur la silhouette par la commande summary(). On récupère ainsi le « coefficient de silhouette » qui indique la pertinence de la segmentation trouvée. On peut l'obtenir par la commande :

  summary (iris.pam.3.si)$avg.width

(voir le cours pour l'interprétation.)

Trouver K optimal

Pour choisir la bonne valeur de K, on se base sur le coefficient de silhouette. Donc, on fait une boucle pour calculer les segmentations pour K variant entre 2 et 10 ou 2 et 20 ou ... (selon ce que l'on cherche et le jeu de données à étudier), et en cherchant le maximum du coefficient de silhouette.

Pour cela, on fera une boucle :

  iris.pam.silcoeff <- numeric (10)
  for (k in 2:10)
    iris.pam.silcoeff [k] <- summary (silhouette( pam (iris [,-5], k)))$avg.width

et on en fera uhn plot().

Activités exploratoires

  1. sur les iris, quel est le K optimal d'après pam() ?
    1. déterminez le nombre de groupes et les groupes dans le jeu de données disponibles à l'url http://www.grappa.univ-lille3.fr/~ppreux/ensg/miashs/fouilleDeDonneesII/tp/k-medianes/jeu12.txt et visualisez la segmentation optimale avec des couleurs
    2. mêmes questions pour ce fichier : http://www.grappa.univ-lille3.fr/~ppreux/ensg/miashs/fouilleDeDonneesII/tp/k-medianes/jeu19.txt (dans ce cas, pour la visualisation, ne prendre en compte que les deux premiers attributs)

k-médianes pour de gros jeux de données

Si le nombre de données est important (disons un gros millier pour un PC normalement constitué en 2007), pam() montre ses limites : les temps de calcul deviennent longs (problème que l'on rencontre beaucoup moins avec kmeans()). Dans ce cas, on utilise la fonction clara().

Regardez la documentation en ligne sur cette fonction et utilisez-là pour reproduire ce que l'on a fait avec pam().

Segmentation non hiérarchique floue

La fonction fanny() permet de faire une segmentation non hiérarchique floue.

Liens