Classification Hiérarchique

Un ensemble de techniques de classification non supervisée (ou "clustering").

Une hiérarchie de clusters

Etant donné un ensemble d'observations, une hiérarchie sur cet ensemble est une collection de groupes d'observations (clusters) tels que :

    * L'ensemble complet des données est un cluster.

    * Chacune des observations est un cluster (singleton).

    * Etant donnés deux clusters de la hiérarchie, ou bien ils n'ont aucune observation en commun, ou bien l'un est incklus dans l'autre (pas de chevauchement).

Pour des raisons pratiques, il est commode d'imposer également que chaque cluster (excepté les singletons) est partitionné en exactement deux clusters de la hiérarchie.

-----

Une telle structure peut se représenter par un "dendogramme" (ou "arbre") :

    * Le cluster contenant toutes les observations s'appelle la "Racine" de l'arbre.

    * Au bas de l'arbre, les singletons (clusters ne contenant qu'une seule observation) s'appellent des "Feuilles".

    * Chaque cluster dans l'arbre s'appelle un "Nœud".

    * Chaque cluster (à l'exception des singletons) a habituellement deux "Enfants".

    * Une ligne joingant un nœud à l'un de ses enfants s'appelle une "Branche".

Tous les chemins menant d'un nœud au feuilles qui en dépendant n'ont pas nécessairement le même nombre de branches.

Hiérarchie et Typologie

 Ce qui intéresse l'analyste n'est pas la hiérarchie, mais une typologie, c'est à dire une partition de l'ensemble des données en clusters qui sont :

    * Compacts,

    * Bien séparés les uns des autres,

    * Et facilement interprétables.

Une hiérarchie permet de construire beaucoup de typologies : toute section supérieure de l'arbre définit un ensemble de clusters partitionnant l'ensemble des données  (nœuds rouges dans l'image inférieure de l'illustration ci-dessus).

-----

La construction de typologies à partir de hiérarchies doit résoudre deux problèmes :

    1) Construire la hiérarchie

        Etant donné un cluster, quelle est la meilleure manière de le scinder en deux "enfants" ? Ou bien, à l'inverse, comment choisir deux clusters dans le but de les fusionner en un unique cluster parent ? Ces deux questions donnent naissance, respectivement, aux Hiérarchies Descendantes et Ascendantes.
 

    2) Choisir une typologie dans la hiérarchie

         Etant donnée un hiérarchie, quelle section supérieure de l'arbre doit être retenue comme typologie finale ?

Classification Hiérarchique Ascendante

 Le Classification Hiérarchique Ascendante (ou "par agrégation") procède par fusions successives de clusters déjà existants. A chaque étape, les deux clusters qui vont fusionner sont ceux dont la "distance" est la plus faible. La question est donc de trouver une bonne définition de ce que l'on entend par la "distance" entre deux groups de points. Il existe de nombreuses définitions d'une telle distance, la plus utilisée étant la distance de Ward, que nous décrivons ci-dessous.

La Classification Ascendante Hiérarchique (ou "CAH") considère initialement toutes les observations comme étant des clusters ne contenant qu'une seule observation (singleton), et leur distance est alors le plus souvent définie comme étant leur distance euclidienne. La première étape consiste donc à réunir dans un cluster à deux observations les deux observations les plus proches.

Puis la CAH continue, fusionnant à chaque étape les deux clusters les plus proches au sens de la distance choisie.

Le processus s'arrête quand les deux clusters restant fusionnent dans l'unique cluster contenant toutes les observations.

-----

Nous décrivons la règle la plus communément utilisée pour tracer l'arbre de la hiérarchie ainsi obtenue. Cette règle est telle que les typologies qui ont le plus de chance d'être significatives sont obtenues simplement en traçant une ligne horizontale en travers du dendogramme, et en retenant dans la typologie les clusters terminaux qui sont juste au-dessus de vette ligne. En changeant la hauteur de la ligne, on change le nombre de clusters retenus, et on dispose ainsi d'un moyen simple pour faire varier la granularité de la typologie finale.

Cette possibilité n'existe pas dans K-means, où la nombre de clusters doit être fixé à l'avance.

 Classification Hiérarchique Descendante

La Classification Hiérarchique Descendante (ou "par division") procède de façon inverse. Elle considère l'enemble des données comme un gros cluster unique, et le scinde en deux clusters "descendants". La scission s'opère de façon à ce que la distance entre les deux descendants soit la plus grande possible, de façon à créer deux clusters bien séparés. Cette procédure est ensuite appliquée à chacun des descendants (procédure récursive) jusqu'à ce qu'il ne reste plus que des clusters ne contenant qu'une seule observation (singletons).

La même représentation en dendogramme, et la même procédure de définition d'une typologie à partir d'un dendogramme utilisées par l'approche "Ascendante" sont utilisables avec par approche "Descendante".

Ascendante ou Descendante ?

A première vue, les approches Ascendante et Descendante semblent être comme des images symétriques l'une de l'autre. Mais il n'en est pas ainsi pour deux raison :

1. L'approche "Ascendante" requiert que la table des distances entre clusters courants soit maintenue à jour après chaque fusion, puis que la fusion suivante soit décidée en cherchant la distance la plus petite dans cette table mise à jour. Bien que longue, cette procédure reste d'une durée raisonnable.
   Les choses sont très différentes pour l'approche "Descendante". A chaque étape, un cluster est désigné pour être scindé en deux. Si l'on veut respecter strictement le critère de maximisation de la distance entre descendants, on doit considérer toutes les partitions possibles du cluster en deux descendants, et retenir la meilleure. Cette procédure est exagérément longue, même pour des clusters de taille modeste. Nous devons donc abandonner l'idée de trouver la partition optimale, et nous satisfaire de trouver une "bonne" partition.
    
2. Cependant, l'approche "Descendante" est séduisante parce qu'elle fournit habituellement des typologies dont l'interprétation est plus claire que celle produites par les méthodes ascendantes. La raison en est que :
      * Une faible distance ne peut pas s'interpréter de façon non ambiguë comme désignant des clusters dont la fusion produise un cluster "naturel",
      * Alors que la scission d'un cluster an deux clusters ayant une grande distance entre eux produit en général deux clusters bien séparés. En fait, on pourrait avancer l'idée selon laquelle l'œil humain, un outil remarquable de Classification Automatique pour des données bidimensionnelles, procède de façon Descendante et non Ascendante.
   

-----

En pratique, les difficultés calculatoires rencontrées par l'approche Descendante font que la méthode Ascendante est de loin la plus répandue des deux.

Arbres de segmentation

Il est difficile, cependant, de renoncer complètement à l'approche Descendante, en raison de ses bons résultats et de son interprétabilité. Une autre façon de contourner la problème du temps de calcul est de conserver le schéma Descendant général, mais de considérer les scissions sur la base des valeurs prises par les observations sur une seule variable, alors que les critères classiques (comme la distance de Ward) exigent la prise en compte simultanée de toutes les variables.

Pour chaque cluster, les variables sont passées en revue une par une et pour chaque variable, on considère les scissions définies par une valeur seuil de la variable. On retient, pour cette variable, la valeur seuil optimale selon un certain critère défini à l'avance (il existe de nombreux tels critères). On retient enfin la variable (et le seuil associé) conduisant à la meilleure scission.

Cette technique s'appelle Arbres de Segmentation.

-----

Ce schéma n'est pas sans rappeler celui des Arbres de Décision, la différence étant que :

    * Les Arbres de Décision essayent de minimiser un taux de mauvaise classification selon les modalités d'une variable nominale (classification supervisée).

    * Alors que les Arbres de Segmentation ne font pas référence à une variable particulière, et essayent simplement d'identifier une bonne typologie (classification non supervisée).

__________________________________________________________

Dans ce Tutoriel, nous décrivons la plus connue des techniques de Classification Hiérarchique : la Classification Hiérarchique Ascendante. Elle est conceptuellement simple, et conduit habituellement à des résultats satisfaisants.

Cependant, comme c'est souvent le cas avec les heuristiques, les logiciels laissent l'utilisateur choisir parmi de nombreuses options (distance entre observations, distances entre clusters, granularité de la typologie), qu'il est donc important de bien comprendre.

CLASSIFICATION HIERARCHIQUE ASCENDANTE

 ___________________________________________

Voir aussi :