Het algoritme kan ofwel beginnen met elk punt in een eigen cluster en deze vervolgens samenvoegen (agglomeratieve clustering), of beginnen met alle punten in één cluster en deze herhaaldelijk splitsen in kleinere clusters (divisieve clustering).

Aangezien agglomeratieve clustering de meest gebruikte benadering is, richten we ons hierop.

Het meest voorkomende type hiërarchische clustering is de bottom-up benadering. Het algoritme verloopt als volgt:

1. Initialisatie: elk datapunt wordt als een afzonderlijke cluster beschouwd;

2. Bereken proximiteitsmatrix: bereken de afstand tussen elk paar clusters;

3. Clusters samenvoegen: de twee dichtstbijzijnde clusters worden samengevoegd tot één cluster;

4. Proximiteitsmatrix bijwerken: herbereken de afstanden tussen de nieuwe cluster en alle overgebleven clusters;

5. Herhalen: stappen 3 en 4 worden herhaald totdat alle datapunten zijn samengevoegd tot één cluster.

Koppelingstypen

De nabijheid tussen twee clusters wordt bepaald door het koppelingstype. Veelgebruikte koppelingsmethoden in hiërarchische clustering zijn:

• Single linkage: de afstand tussen de twee dichtstbijzijnde punten in de twee clusters;

• Complete linkage: de afstand tussen de twee verst uit elkaar liggende punten in de twee clusters;

• Average linkage: de gemiddelde afstand tussen alle paren van punten in de twee clusters;

• Ward's methode: minimaliseert de toename van de totale variantie binnen clusters bij het samenvoegen van twee clusters.

De keuze van de koppelingsmethode kan invloed hebben op de vorm en structuur van de resulterende clusters. Experimenteren en domeinkennis zijn vaak nuttig bij het selecteren van de beste methode voor uw data.

Dendrogram

De resultaten van hiërarchische clustering worden vaak gevisualiseerd met behulp van een dendrogram.