Algoritmi voi joko aloittaa jokainen piste omassa klusterissaan ja yhdistää niitä vähitellen (agglo­meraatiivinen klusterointi), tai aloittaa kaikki pisteet yhdessä klusterissa ja jakaa niitä toistuvasti pienempiin klustereihin (divisiivinen klusterointi).

Koska agglo­meraatiivinen klusterointi on yleisimmin käytetty lähestymistapa, keskitymme siihen.

Yleisin hierarkkisen klusteroinnin tyyppi on alhaalta ylöspäin -lähestymistapa. Algoritmi etenee seuraavasti:

1. Alustus: jokainen datapiste käsitellään omana klusterinaan;

2. Läheisyysmatriisin laskeminen: lasketaan etäisyys jokaisen klusteriparin välillä;

3. Klusterien yhdistäminen: kaksi lähintä klusteria yhdistetään yhdeksi klusteriksi;

4. Läheisyysmatriisin päivitys: lasketaan uudelleen etäisyydet uuden klusterin ja kaikkien jäljellä olevien klusterien välillä;

5. Toisto: vaiheet 3 ja 4 toistetaan, kunnes kaikki datapisteet on yhdistetty yhdeksi klusteriksi.

Linkage-tyypit

Kahden klusterin välinen läheisyys määritellään linkage-tyypin perusteella. Yleisiä hierarkkisessa klusteroinnissa käytettyjä linkage-menetelmiä ovat:

• Single linkage: etäisyys kahden klusterin lähimpien pisteiden välillä;

• Complete linkage: etäisyys kahden klusterin kauimpien pisteiden välillä;

• Average linkage: kaikkien kahden klusterin pisteparien keskimääräinen etäisyys;

• Wardin menetelmä: minimoi kahden klusterin yhdistämisestä aiheutuvan kokonaisklusterin sisäisen varianssin kasvun.

Linkage-menetelmän valinta voi vaikuttaa muodostuvien klustereiden muotoon ja rakenteeseen. Kokeilu ja asiantuntemus ovat usein hyödyllisiä parhaan menetelmän valinnassa aineistolle.

Dendrogrammi

Hierarkkisen klusteroinnin tulokset esitetään usein dendrogrammin avulla.