Der Algorithmus kann entweder mit jedem Punkt in einem eigenen Cluster beginnen und diese sukzessive zusammenführen (agglomeratives Clustering), oder mit allen Punkten in einem Cluster starten und diese rekursiv in kleinere Cluster aufteilen (divisives Clustering).

Da das agglomerative Clustering die gebräuchlichere Methode ist, konzentrieren wir uns darauf.

Die gebräuchlichste Form des hierarchischen Clusterings ist der Bottom-up-Ansatz. Der Algorithmus verläuft wie folgt:

1. Initialisierung: Jeder Datenpunkt wird als einzelner Cluster betrachtet;

2. Berechnung der Proximitätsmatrix: Die Distanz zwischen jedem Clusterpaar wird berechnet;

3. Cluster zusammenführen: Die beiden nächstgelegenen Cluster werden zu einem Cluster zusammengeführt;

4. Aktualisierung der Proximitätsmatrix: Die Distanzen zwischen dem neuen Cluster und allen verbleibenden Clustern werden neu berechnet;

5. Wiederholung: Die Schritte 3 und 4 werden wiederholt, bis alle Datenpunkte zu einem einzigen Cluster zusammengeführt sind.

Verknüpfungstypen

Die Nähe zwischen zwei Clustern wird durch den Verknüpfungstyp definiert. Gängige Verknüpfungsmethoden im hierarchischen Clustering sind:

• Single Linkage: Die Distanz zwischen den nächstgelegenen Punkten in den beiden Clustern;

• Complete Linkage: Die Distanz zwischen den am weitesten entfernten Punkten in den beiden Clustern;

• Average Linkage: Der durchschnittliche Abstand aller Punktpaare in den beiden Clustern;

• Ward-Methode: Minimiert den Anstieg der Gesamtvarianz innerhalb der Cluster beim Zusammenführen zweier Cluster.

Die Wahl der Verknüpfungsmethode kann die Form und Struktur der resultierenden Cluster beeinflussen. Experimentieren und Domänenwissen sind oft hilfreich, um die beste Methode für Ihre Daten auszuwählen.

Dendrogramm

Die Ergebnisse der hierarchischen Clusteranalyse werden häufig mithilfe eines Dendrogramms visualisiert.