Classification ascendante hiérarchique (CAH)

Apprenez à utiliser simplement une CAH en comprenant le fonctionnement de l’algorithme.

Image d'un dendrogramme

Le tout premier article qui expliquait la CAH sur lovelyanalytics.com date de 2017… il était temps pour moi de faire quelques modifications et d’enrichir un peu tout ça. Je vous propose donc une nouvelle version pour ceux qui avaient déjà lue la précédente.

La classification ascendante hiérarchique est un algorithme de machine learning de la catégorie non supervisée. Comme les k-means, elle permet d’identifier des groupes homogènes dans une population, on parle aussi de clustering. C’est une de mes méthodes préférées. Nous allons voir quels sont ses avantages et inconvénients, quand l’utiliser avec des explications simples sur son fonctionnement.

Qu’est ce qu’une CAH ?

La CAH est donc un algorithme de clustering. A partir de vos données, l’algorithme va chercher à créer des groupes d’individus homogènes, c’est à dire :

  • Des groupes dans lesquels les individus se ressemblent
  • Des groupes qui se distinguent le plus possible les uns des autres

C’est par exemple la méthode de prédilection pour faire des segmentations clients sur des volumes de données acceptables (sinon on préférera utiliser la méthode mixte qui combine CAH et k-means). C’est une méthode que j’adore parce qu’elle m’a toujours surprise par son efficacité et sa capacité à mettre en avant des groupes très cohérents d’un point de vue métier. Typiquement avec la CAH on se dit toujours « Mais c’est tellement évident » en voyant les résultats.

Quels sont les avantages et les inconvénients de la CAH ?

Illustration avantages et inconvénients CAH

Avantages :

  • Aide au choix du nombre de groupes : La plupart des méthodes de clustering demandent à l’utilisateur de choisir le nombre de groupes qu’il souhaite créer dans les paramètres de l’algorithme. Ce n’est pas le cas de la CAH qui va calculer toutes les combinaisons possibles, les représenter via un dendrogramme qui permettra au Data Scientist de choisir le nombre de clusters le plus adapté à ses données et à son objectif.
  • Hiérarchique : La classification ascendante hiérarchique est une méthode hiérarchique (oui merci c’est écrit dans son nom mais ça veut dire quoi? ) La construction des groupes se fait étape par étape (comme vous pourrez le voir juste après). Ce qui veut dire que vous pourrez d’abord faire le choix de segmenter vos données en 3 groupes par exemple. Si vous analysez le contenu de ces 3 groupes et qu’un groupe ne vous parait pas homogène, vous pourrez décider de passer à un découpage à 4 groupes sans avoir à tout recommencer. Bien sûr vous n’avez pas de garanti que le découpage supplémentaire concerne le groupe que vous avez identifié. Mais s’il ne vous parait pas homogène, il y a de grande chance qu’il soit le prochain a être découpé.
  • Facile à utiliser : La CAH construit systématiquement un dendrogramme (une sorte d’arbre) qui va résumer tous les regroupements qui ont été faits. Ce dendrogramme est vraiment très utile et facilite l’utilisation de la CAH
  • Choix de la distance : Un dernier point qui peut avoir son importance, pour décider si des individus ou des groupes sont proches ou éloignés, vous pourrez choisir votre distance. En particulier j’utilise souvent la distance de Ward pour les segmentations client qui permet d’éviter que des individus atypiques se retrouvent seuls isolés dans un groupe. Au contraire pour un sujet de détection de fraude par exemple on pourrait choisir une distance qui contribue à isoler les cas extrêmes.

Je m’arrête là pour les avantages mais je suis sûre que je pourrais en trouver d’autres tant j’apprécie cet algorithme.

Inconvénients

  • Pas adapté aux grands volumes de données : Malheureusement la CAH ne peut pas être utilisée sur des volumes de données importants, les temps de calcul explosent et cela s’explique complètement par les méthodes de calcul de l’algorithme. Il existe quand même des solutions dans ce cas, on peut coupler la CAH à un k-means et c’est ce qu’on appelle la méthode mixte.

Quand utiliser une classification ascendante hiérarchique ?

C’est un algorithme qui peut être utilisé dans pas mal de cas, en particulier, je vous recommande de l’utiliser dans les situations suivantes :

  • Utiliser une CAH pour construire une segmentation client : Pour moi c’est là que l’algorithme fonctionne le mieux, en particulier avec la distance de Ward. Avec un peu d’habitudes vous réussirez à obtenir rapidement des groupes cohérents qui ont un vrai sens métier. Ensuite je vous conseille d’appliquer un arbre de décision pour avoir des règles de construction clairs de chaque segment.
  • Utiliser une CAH pour de l’exploration de données : Les méthodes de clustering et en particulier la CAH peuvent aussi être utilisées pour faire de l’exploration. Vous avez une dataset, vous ne connaissez pas bien ces données, pourquoi ne pas le segmenter pour y voir plus clair ?

Comment fonctionne l’algorithme de classification ascendante hiérarchique ?

Regardons de plus près comment ça marche :

Comment préparer ses données avant une CAH ?

Et oui avant de vous lancer, un peu de nettoyage dans les données

Pour commencer il faut savoir que la CAH s’applique sur des données quantitatives. Si certaines données de votre dataset sont qualitative, vous pouvez faire au-préalable une ACM pour les convertir (vous utiliserez alors les axes de l’ACM comme nouvelles données).

Si vos données sont quantitatives il peut quand même être intéressant de réaliser dans un premier temps une ACP pour réduire le nombre de dimensions du problème (comme pour l’ACM, on utilisera alors les coordonnées des premiers axes de l’ACP comme nouvelles données).

Encore un dernier traitement pour les variables extrêmes. On les identifie et on les traite. Il n’y a pas de règle toute faite, vous pouvez appliquer des règles métier. Quand je n’ai pas de référence, je considère comme valeur extrême tout ce qui est supérieur à moyenne + 3*écart-type ou inférieur à moyenne – 3*écart-type (pour les distributions qui peuvent être considérées comme Gausiennes)

L’algorithme de la CAH

Les données sont prêtes, nettoyées, et le nombre de dimensions du problème a été réduit, la CAH peut être appliquée. C’est une méthode hiérarchique qui se construit étape par étape en partant du niveau le plus fin où chaque individu est seul dans son groupe jusqu’au niveau le plus agrégé où tous les individus sont dans le même groupe. Pour présenter la manière dont tout cela s’organise on construit un dendrogramme.

Comme toujours, c’est plus simple avec un exemple. Prenons 10 clients pour lesquels on connait l’ancienneté et le panier moyen. On cherche à identifier des typologies de clients.

Image exemple individus à segmenter

Etape 0 : Initialisation

On considère que chaque client est seul et isolé dans son groupe. Dans notre cas, on suppose donc qu’on a 10 groupes.

lovely analytics CAH 2

Etape itérative  :

On calcule la distance entre chaque groupe. Comme d’habitude plusieurs distances peuvent être utilisées. Pour la CAH, j’aime bien utiliser la distance de WARD qui permet de pondérer la distance en fonction du nombre d’individus appartenant au groupe. Cela permet d’éviter d’isoler les outliers (valeurs extrêmes) dans un groupe (ce qui aurait peu de sens métier en général).

On fusionne les 2 groupes les plus proches et on les relie dans le dendrogramme. Le trait qui nous permet de relier les 2 groupes dans le dendrogramme est d’autant plus long que la distance entre les groupes est élevée.

Image 1ere étape de construction d'un dendrogramme

Et on va continuer cette étape itérative encore et encore  …

Image 2e étape de construction d'un dendrogramme

… jusqu’à ce qu’il ne reste plus qu’un seul et unique groupe réunissant tous les individus.

Image 3e étape de construction d'un dendrogramme

Comment choisir le nombre de groupes d’une CAH ?

Vous obtenez finalement un dendrogramme qui présente l’emboîtement de tous les cas possibles. On arrive à l’étape cruciale du choix du nombre de groupe. Il y a 3 règles à avoir en tête :

  1. Le nombre de groupe doit être cohérent d’un point de vue métier. C’est l’interprétation des résultats qui vous permettra de vérifier que vos groupes ont du sens.
  2. Le nombre de groupe doit être exploitable : une segmentation de 8 groupes ça commence déjà à faire beaucoup pour une exploitation opérationnelle.
  3. Les groupes doivent être le plus homogènes possible (les individus d’un groupe se ressemblent et les groupes sont différents les uns des autres). Cela se traduit, sur le dendrogramme, par le fait de couper au niveau d’une branche « longue »

Dans notre cas on pourrait couper au niveau de 2 groupes ou de 3. On choisit d’en faire 3 ce qui nous donne ces résultats.

Résultats :

C’est très simple maintenant, en coupant le dendrogramme au bon niveau, vous obtenez vos clusters.

Image résultat d'une CAH

Encore un peu de travail pour comprendre et interpréter ces classes. Vous pouvez calculer les moyennes de chaque groupe ou utiliser des valeurs tests pour mettre en avant les spécificités de chaque population.

A vous de jouer !

2 commentaires sur « Classification ascendante hiérarchique (CAH) »

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s