L'algorithme peut commencer soit avec chaque point dans son propre cluster et les fusionner successivement (clustering agglomératif), soit 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 clusters 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 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 totale intra-cluster 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 regroupement hiérarchique sont souvent visualisés à l’aide d’un dendrogramme.