• 15 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 12/11/2019

Effectuez une classification hiérarchique

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Nous allons voir un autre type de partitionnement : la classification hiérarchique.

Regardez ces données : combien de clusters y voyez-vous ?

Certains diront 5, d'autres 4, ou encore 3. En effet, il y a 5 groupes bien distincts, mais deux d'entre eux sont très rapprochés : on peut donc considérer qu'ils ne forment qu'un seul cluster et répondre 4. Ces deux clusters très proches sont également relativement proches d'un troisième : si on les regroupe, on considère donc qu'il y a 3 clusters.

En fait, il n'y a pas vraiment de bonne réponse : tout dépend du contexte et des objectifs poursuivis.

On comprend ici l'aspect hiérarchique : ceux qui auront répondu 3 ont eu une vue très générale, alors que ceux qui ont répondu 5 ont préféré avoir une analyse plus fine, plus en profondeur. C'est donc le niveau de profondeur qui détermine une hiérarchie : avec une analyse générale, on voit 3 clusters, mais si l'on creuse un peu plus, on peut diviser l'un de ces 3 clusters en 2 sous-clusters. En allant un peu plus loin, on peut encore diviser l'un de ces 2 sous-clusters en 2 autres. Cette notion de "sous-clusters" est résumable par un arbre :

La notion de profondeur est visible ici à travers l'axe vertical. En effet, on peut "couper" l'arbre plus ou moins haut. Si on le coupe peu profondément, on trouve 3 clusters. Si l'on descend un peu plus bas, on en trouve 5.

Classification hiérarchique ascendante et descendante

Il y a deux approches pour créer une partition hiérarchique :

  • L'approche ascendante, aussi appelée clustering agglomératif : on considère tout d'abord que chaque point est un cluster. Il y a donc autant de clusters que de points. Ensuite, on cherche les deux clusters les plus proches, et on les agglomère en un seul cluster. On répète cette étape jusqu'à ce que tous les points soient regroupés en un seul grand cluster.

  • L'approche descendante, aussi appelée clustering divisif : c'est l'inverse. On part d'un grand cluster contenant tous les points, puis on le divise successivement jusqu'à obtenir autant de clusters que de points.

On obtient donc une arborescence qui a un cluster tout en haut, et qui se divise petit à petit jusqu'à avoir autant de clusters que de points. On appelle cette arborescence un dendrogramme.

Voici le dendrogramme des données ci-dessus :

 

Méthode des liens et méthode de Ward

Que ce soit avec l'approche ascendante ou descendante, on a besoin de mesurer la distance entre 2 clusters.

La distance entre 2 points, c'est assez intuitif. Mais comme un cluster est composé de plusieurs points, il y a différentes manières de considérer une distance entre 2 clusters. On les appelle les méthodes de lien (linkage methods), car ce sont elles qui permettent de lier les clusters lorsque l'on construit petit à petit l'arborescence.

On a :

  • Le lien simple (simple linkage) : on considère que la distance entre 2 clusters est la distance entre leurs 2 points les plus proches. Cela est équivalent à dire "deux clusters sont proches si au moins deux de leurs points sont proches".

  • Le lien complet (complete linkage) : on considère que la distance entre 2 clusters est la distance entre leurs 2 points les plus éloignés. Cela équivaut donc à dire "deux clusters sont proches si tous leurs points sont proches".

  • Le lien moyen : on considère que la distance entre 2 clusters est la moyenne de toutes les distances entre les points d'un cluster et les points de l'autre cluster. Pour la calculer, on énumère toutes les paires de points possibles d'un cluster à l'autre, puis on calcule la distance de chaque paire, puis on calcule la moyenne.

  • Le lien centroïdal : on considère que la distance entre 2 clusters est la distance entre les centroïdes de ceux-ci.

Les méthodes de lien permettent de garantir que les clusters sont bien séparés, car on prend en compte la distance entre les clusters. Cependant, elles ne garantissent pas que les clusters sont resserrés sur eux-mêmes (c'est la notion d'inertie intraclasse). Pour résoudre cela, il existe la méthode de Ward qui, à chaque itération, c'est-à-dire à chaque fois que 2 clusters sont regroupés en 1, cherche à minimiser l'augmentation d'inertie intraclasse due au regroupement des 2 clusters. Par défaut, on préfère en général utiliser la méthode de Ward.

Avantages et inconvénients

Contrairement au k-means, la classification hiérarchique ne nécessite pas de déterminer un nombre de classes au préalable. En effet, en jouant sur la profondeur de l'arbre, on peut explorer différentes possibilités et choisir le nombre de classes qui nous convient le mieux.

Ce choix peut se faire en regardant les inerties intraclasse et interclasse, ou en utilisant d'autres critères. Nous pouvons choisir un nombre de classes en observant le dendrogramme.

Cependant, il y a des chances pour que l'algorithme de classification hiérarchique mette du temps avant de vous fournir son résultat. En effet, à chaque itération (c'est-à-dire à chaque fois que l'on divise un cluster en 2 pour l'approche descendante, ou que l'on regroupe 2 clusters pour l'approche ascendante), il faut recalculer les distances de toutes les paires de points possibles entre les 2 clusters en question !

Cela nécessite beaucoup de temps et beaucoup d'espace mémoire. On dit que cet algorithme a une forte complexité algorithmique en temps et en espace, c'est-à-dire que vous manquerez peut-être de temps ou d'espace mémoire, même avec un jeu de données de taille moyenne. Le clustering hiérarchique est donc plus adapté aux petits échantillons.

Oui, mais tu nous disais que le clustering pouvait justement servir à réduire les dimensions du jeu de données (en regroupant des lignes) si celui-ci est trop gros. Si l'on ne peut pas utiliser la classification hiérarchique sur un gros échantillon, à quoi cela sert-il ?

Effectivement. Mais il y a une petite astuce qui permet de combiner les avantages d'un algorithme rapide, mais qui offre peu de flexibilité comme le k-means, avec le confort d'une classification hiérarchique. Si par exemple vous avez un échantillon contenant 10 000 individus, vous pouvez commencer par les regrouper en 50 clusters, en extraire les 50 centroïdes, puis appliquer un clustering hiérarchique sur ces 50 centroïdes. Avec le dendrogramme, vous pourrez ainsi choisir le nombre de clusters (compris entre 1 et 50) qui vous convient !

Exemple de certificat de réussite
Exemple de certificat de réussite