Algoritmen kan enten starte med hvert punkt i sin egen klynge og deretter gradvis slå dem sammen (agglomerativ klynging), eller starte med alle punkter i én klynge og deretter dele dem opp i mindre klynger (divisiv klynging).

Siden agglomerativ klynging er den mest brukte tilnærmingen, vil vi fokusere på denne.

Den vanligste typen hierarkisk klynging er bottom-up-tilnærmingen. Algoritmen er som følger:

1. Initialisering: hvert datapunkt behandles som en enkelt klynge;

2. Beregn nærhetsmatrise: beregn avstanden mellom hvert par av klynger;

3. Slå sammen klynger: de to nærmeste klyngene slås sammen til én klynge;

4. Oppdater nærhetsmatrise: beregn avstandene på nytt mellom den nye klyngen og alle gjenværende klynger;

5. Gjenta: trinn 3 og 4 gjentas til alle datapunkter er slått sammen til én klynge.

Koblingstyper

Nærheten mellom to klynger defineres av koblingstype. Vanlige koblingsmetoder brukt i hierarkisk klyngeanalyse er:

• Enkeltkobling: avstanden mellom de nærmeste to punktene i de to klyngene;

• Fullstendig kobling: avstanden mellom de fjerneste to punktene i de to klyngene;

• Gjennomsnittskobling: gjennomsnittlig avstand mellom alle par av punkter i de to klyngene;

• Wards metode: minimerer økningen i total varians innenfor klyngene ved sammenslåing av to klynger.

Valg av koblingsmetode kan påvirke formen og strukturen til de resulterende klyngene. Eksperimentering og domeneekspertise er ofte nyttig for å velge den beste metoden for dine data.

Dendrogram

Resultatene av hierarkisk klyngeanalyse visualiseres ofte ved hjelp av et dendrogram.