Het algoritme kan ofwel beginnen met elk punt in zijn 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 daarop.

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

1. Initialisatie: elk datapunt wordt als een afzonderlijk 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 het nieuwe cluster en alle overige clusters;

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

Koppelingssoorten

De nabijheid tussen twee clusters wordt bepaald door het type koppeling. Veelgebruikte koppelingsmethoden bij hiërarchisch clusteren 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ërarchisch clusteren worden vaak gevisualiseerd met een dendrogram.