Algoritmen kan enten starte med hver observasjon i sin egen klynge og deretter gradvis slå dem sammen (agglomerativ klynging), eller starte med alle observasjoner 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: hver datapunkt behandles som en egen 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 datapunktene er slått sammen til én klynge.

Koblingstyper

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

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

• Fullkobling: avstanden mellom de fjerneste to punktene i de to klyngene;

• Gjennomsnittskobling: gjennomsnittlig avstand mellom alle punktpar 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 domenekunnskap er ofte nyttig for å velge den beste metoden for dine data.

Dendrogram

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