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 den mest använda metoden, kommer vi att fokusera på den.

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 par av kluster;

3. Slå ihop kluster: de två närmaste klustren slås ihop till ett enda 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 ihop till ett enda kluster.

Länkningstyper

Närheten mellan två kluster definieras av länkningstypen. Vanliga länkmetoder som används i hierarkisk klustring är:

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

• Fullständig länkning: avståndet mellan de två mest avlägsna 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änkmetod kan påverka formen och strukturen hos de resulterande klustren. Experimentering och domänkunskap är ofta användbara för att välja den bästa metoden för dina data.

Dendrogram

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