L'algorithme peut soit commencer avec chaque point dans son propre cluster et les fusionner successivement (regroupement agglomératif), soit commencer avec tous les points dans un seul cluster et les diviser récursivement en clusters plus petits (regroupement divisif).

Puisque le regroupement agglomératif est l'approche la plus couramment utilisée, nous nous concentrerons sur celle-ci.

Le type le plus courant de regroupement hiérarchique est l'approche ascendante. L'algorithme est le suivant :

1. Initialisation : chaque point de données est considéré comme un cluster unique ;

2. Calcul de la matrice de proximité : calcul de la distance entre chaque paire de clusters ;

3. Fusion des clusters : les deux clusters les plus proches sont fusionnés en un seul cluster ;

4. Mise à jour de la matrice de proximité : recalcul des distances entre le nouveau cluster et tous les clusters restants ;

5. Répétition : les étapes 3 et 4 sont répétées jusqu'à ce que tous les points de données soient fusionnés en un seul cluster.

Types de liaison

La proximité entre deux clusters est définie par le type de liaison. Les méthodes de liaison courantes utilisées dans le regroupement hiérarchique sont :

• Liaison simple : la distance entre les deux points les plus proches dans les deux clusters ;

• Liaison complète : la distance entre les deux points les plus éloignés dans les deux clusters ;

• Liaison moyenne : la distance moyenne entre toutes les paires de points dans les deux clusters ;

• Méthode de Ward : minimise l'augmentation de la variance intra-cluster totale lors de la fusion de deux clusters.

Le choix de la méthode de liaison peut influencer la forme et la structure des clusters obtenus. L'expérimentation et la connaissance du domaine sont souvent utiles pour sélectionner la méthode la plus adaptée à vos données.

Dendrogramme

Les résultats du clustering hiérarchique sont souvent visualisés à l'aide d'un dendrogramme.