Algoritmen kan antingen börja med varje punkt i sitt eget kluster och successivt slå ihop dem (agglomerativ klustring), eller börja med alla punkter i ett kluster och rekursivt dela upp dem i mindre kluster (divisiv klustring).

Eftersom agglomerativ klustring är det vanligaste tillvägagångssättet fokuserar vi på det.

Den vanligaste typen av hierarkisk klustring är bottom-up-metoden. Algoritmen är följande:

1. Initialisering: varje datapunkt behandlas som ett enskilt kluster;

2. Beräkna närhetsmatris: beräkna avståndet mellan varje klusterpar;

3. Sammanfoga kluster: de två närmaste klustren slås samman till ett kluster;

4. Uppdatera närhetsmatris: beräkna om avstånden mellan det nya klustret och alla återstående kluster;

5. Upprepa: steg 3 och 4 upprepas tills alla datapunkter har slagits samman till ett enda kluster.

Länkningsmetoder

Närheten mellan två kluster definieras av länkningsmetoden. Vanliga länkningsmetoder som används vid hierarkisk klustring är:

• Enkel länkning: avståndet mellan de närmaste två punkterna i de två klustren;

• Fullständig länkning: avståndet mellan de mest avlägsna två punkterna i de två klustren;

• Genomsnittlig länkning: det genomsnittliga avståndet mellan alla punktpar i de två klustren;

• Wards metod: minimerar ökningen av den totala inomkluster-variansen vid sammanslagning av två kluster.

Valet av länkningsmetod kan påverka formen och strukturen hos de resulterande klustren. Experimentering och domänkunskap är ofta till hjälp vid val av bästa metod för dina data.

Dendrogram

Resultaten av hierarkisk klustring visualiseras ofta med hjälp av ett dendrogram.