Algoritmen kan enten starte med hver observasjon i sin egen klynge og deretter gradvis slå dem sammen (agglomerativ klyngeanalyse), eller starte med alle observasjoner i én klynge og deretter dele dem opp i mindre klynger (divisiv klyngeanalyse).

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

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

1. Initialisering: hver datapunkt behandles som en egen klynge;

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

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

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

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

Koblingstyper

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

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

• Fullkobling: avstanden mellom de to fjerneste 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 når to klynger slås sammen.

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

Dendrogram

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