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

Koska agglomeroiva 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 havaintopiste käsitellään omana klusterinaan;

2. Laske läheisyysmatriisi: laske etäisyys jokaisen klusteriparin välillä;

3. Yhdistä klusterit: kaksi lähintä klusteria yhdistetään yhdeksi klusteriksi;

4. Päivitä läheisyysmatriisi: laske uudelleen etäisyydet uuden klusterin ja kaikkien jäljellä olevien klusterien välillä;

5. Toista: vaiheet 3 ja 4 toistetaan, kunnes kaikki havaintopisteet on yhdistetty yhdeksi klusteriksi.

Linkage-tyypit

Kahden klusterin välinen läheisyys määritellään linkage-tyypin avulla. Yleisiä linkage-menetelmiä hierarkkisessa klusteroinnissa 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 pisteparien keskimääräinen etäisyys kahden klusterin välillä;

• Wardin menetelmä: minimoi klusterin sisäisen varianssin kasvun yhdistettäessä kahta klusteria.

Linkage-menetelmän valinta voi vaikuttaa muodostuvien klustereiden muotoon ja rakenteeseen. Kokeilu ja sovellusalueen tuntemus auttavat usein parhaan menetelmän valinnassa aineistolle.

Dendrogrammi

Hierarkkisen klusteroinnin tulokset esitetään usein dendrogrammin avulla.