Segmentation hiérarchique ascendante

L'objectif de ce TD est de manipuler l'algorithme de segmentation hiérarchique ascendante disponible dans R.

La segmentation hiérarchique ascendante dans R

La fonction hclust()

L'algorithme de segmentation hiérarchique ascendante est disponible au travers de la fonction hclust() de R. Elle s'applique non pas à un jeu de données, mais à une matrice de distance. On peut facilement obtenir cette matrice pour un data frame à l'aide de la fonction dist() qui calcule la distance euclidienne entre chaque paire de données du data frame : 

hclust (dist (iris [,1:4]))

exécute l'algorithme de segmentation hiérarchique sur le jeu de données iris en utilisant les quatre attributs longueur et largeur des spéales et des pétales.
À l'issue de son exécution, hclust() a construit un dendrogramme.

Visualisation de la segmentation

On peut visualiser le dendrogramme à l'aide de la fonction plot(). Ainsi, supposons que vous ayez placé le résultat de hclust() dans iris.hclust. 

  plot (iris.hclust)

produit :
iris.hclust
où chaque feuille du dendrogramme est étiquetée par le numéro d'une donnée.

Découpe du dendrogramme

Plusieurs méthodes sont possibles pour découper le dendrogramme et obtenir une segmentation en K groupes, K étant fixé.

cutree

D'une segmentation hiérarchique, on peut obtenir autant de groupes (de 1 à N) que l'on veut en découpant l'arbre au nouveau adéquat. Cela se fait avec la fonction cutree comme cela : pour obtenir 3 groupes à partir de la segmentation hiérarchique précédente, on tape la commande cutree (iris.hclust, 3).

Cette commande fournit un vecteur de N entiers : l'élément i indique le groupe de la donnée i ; les groupes sont numérotés de 1 à K.

Visualisation de la découpe

La fonction rect.hclust() fait la même chose que cutree(), mais le fait visuellement. Ainsi : 

  rect.hclust (iris.hclust, 5)

met en évidence les 5 groupes (faites-le !) du dendrogramme (remarque : il faut avoir fait un plot (iris.hclust) auparavant).

On peut aussi spécifier la couleur des bordures : 

  rect.hclust (iris.hclust, 5,
               border = c ("blue", "green", "red", "pink", "black"))

et on peut aussi n'entourer que certains des groupes, par exemple le deuxième et le cinquième : 

  rect.hclust (iris.hclust, 5, which = c (2, 5))

De plus, si l'on affecte le résultat à un objet en tapant : 

  iris.hclust.5 <- rect.hclust (iris.hclust, 5, which = c (2, 5))

iris.hclust.5 est une liste contenant 5 éléments (autant que de groupes) et chaque élément de la liste contient la liste des numéros des données de ce groupe.

Comment faites-vous pour connaître la moyenne des données de chacun des 5 groupes (de la manière la plus simple qui soit) ?

Découpe à la demande

On peut aussi afficher le dendrogramme et indiquer à la souris où (les segments verticaux) on veut couper. On utilsie pour cela la fonction identify. Tapez : 

  plot (iris.hclust)
  identify (iris.hclust)

Vous pouvez alors cliquer avec le bouton gauche de la souris sur les segments verticaux au niveau desquels vous voulez découper le dendrogramme. Faites 4 découpes (par exemple). Quand vous avez terminé, cliquez avec le bouton droit (tout cela dans la fenêtre graphique).

À nouveau, vous pouvez récupérer la composition de chacun des groupes en affectant le résultat de la fonction identify à un objet : 

  plot (iris.hclust)
  iris.hclust.id <- identify (iris.hclust)

Comme avec rect.hclust(), iris.hclust.id est une liste dans laquelle chaque élément correspond à un groupe et contient la liste des nuémros des données de ce groupe.

Activité exploratoire

    1. faites une segmentation hiérarchique des iris
    2. obtenez une segmentation en 3 groupes
    3. faites un graphique représentant les iris colorés en fonction de leur groupe
    4. Comparez la segmentation à 3 groupes obtenue par segmentation hiérarchique avec celle obtenue par les centres mobiles (visuellement et via leur matrice de confusion).
    1. mêmes questions pour une segmentation en 4 groupes.
    1. on reprend le jeu de données disponibles à l'url http://www.grappa.univ-lille3.fr/~ppreux/ensg/miashs/fouilleDeDonneesII/tp/k-moyennes/jeu1.txt ; les groupes sont-ils bien trouvées par une segmentation hiérarchique ?
    2. même question pour le fichier : http://www.grappa.univ-lille3.fr/~ppreux/ensg/miashs/fouilleDeDonneesII/tp/k-moyennes/jeu2.txt
    3. et celui-là : http://www.grappa.univ-lille3.fr/~ppreux/ensg/miashs/fouilleDeDonneesII/tp/k-moyennes/jeu3.txt (même remarque pour la visualisation)
  1. on considère le jeu de données disponible à l'url http://www.grappa.univ-lille3.fr/~ppreux/ensg/miashs/fouilleDeDonneesII/tp/k-moyennes/jeu4.txt
    1. faites en une segmentation hiérarchique et découpez-là en 3 groupes
    2. visualisez le jeu de données (par un plot() tout simple)
    3. visualisez le jeu de données en colorant chaque point par une couleur différente en fonction du groupe. Qu'en pensez-vous ?
  2. on considère le jeu de données disponible à l'url http://www.grappa.univ-lille3.fr/~ppreux/ensg/miashs/fouilleDeDonneesII/tp/k-moyennes/jeu5.txt.
    1. Répondre aux mêmes questions que précédemment.
    2. Pensez-vous qu'une transformation des données permettrait de trouver les groupes attendus ?
    3. Mettez en œuvre cette idée.
  3. que se passe-t-il si on segmente des données qui ne sont pas segmentables ? Comme beaucoup d'algorithmes, les algorithmes de segmentation hiérarchique produisent un résultat, que celui-ci ait un sens ou pas, à l'expert humain (vous donc) de faire le tri.
    1. générer un jeu de 500 données en deux dimensiosn, dans l'intervalle [-1;1]x[-1;1] et le mettre dans un data.frame
    2. en faire une segmentation hiérarchique
    3. observer le résultat. Que constatez-vous ?