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

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

Le type le plus courant de clustering 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é : calculer 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é : recalculer les 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 groupes est définie par le type de liaison. Les méthodes de liaison couramment utilisées dans le regroupement hiérarchique sont :

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

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

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

• Méthode de Ward : minimise l’augmentation de la variance intra-groupe totale lors de la fusion de deux groupes.

Le choix de la méthode de liaison peut influencer la forme et la structure des groupes 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 regroupement hiérarchique sont souvent visualisés à l’aide d’un dendrogramme.