CAH : Classification ascendante hiérarchique

La CAH (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 les avantages et les inconvénients de la CAH, quand l’utiliser avec des explications simples sur son fonctionnement.

Qu’est ce qu’une CAH ?

La Classification Ascendante Hiérarchique est donc un algorithme de clustering. C’est à dire qu’à partir de vos données, l’algorithme va chercher à créer des groupes d’individus homogènes :

• 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. En revanche si les données sont volumineuses, on préférera utiliser la méthode mixte qui combine CAH et k-means. C’est une méthode que j’adore : 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. En principe avec la CAH on se dit « Mais c’est tellement évident » en voyant les résultats.

Quels sont les avantages et les inconvénients de la 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. Ce n’est pas le cas de la CAH qui va calculer toutes les combinaisons possibles. Elle les représente ensuite 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. 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 : C’est 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. Elle permet d’éviter que des individus atypiques se retrouvent seuls isolés dans un groupe.

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. 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, je vous le recommande 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 ?

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. Dans ce cas vous utiliserez 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).

Pour conclure 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.

En règle générale, c’est plus simple avec un exemple. Prenons donc 10 clients pour lesquels on connait l’ancienneté et le panier moyen. On cherche alors à identifier des typologies de clients.

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.

Etape itérative  :

On calcule ensuite 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.

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

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

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 :

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

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 !

Vous voulez en savoir plus ? Je vous conseille ce cours sur la CAH si vous voulez approfondir le sujet avec plus de formules mathématiques.