Definition - Agglomerative Verfahren

• Typen:
  • Single-Link-Clustering
  • Average-Link-Clustering
• Konstrukte:
  • Dendrogramm
• Generalisierungen:
  • Hierarchisches Clustering
• Involvierte Definitionen:
  • Metrik
  • siehe auch Divisive Verfahren
• Veranstaltung: EML
• Referenz: @thimm2024 (Abschnitt 3.2.1)

⠀

Definition: Agglomerative Verfahren

Als agglomerative Verfahren (auch bottom-up Verfahren) bezeichnen wir Methoden des hierarchischen Clusterings, die Dendrogramme von den Blättern her aufbauen.

• Die Datenpunkte werden alle einem eigenen, separaten Cluster zugewiesen.
• Anschließend werden iterativ diejenigen Cluster zusammengeführt, die einander auf Basis einer Metrik am ähnlichsten sind.

Formal:

Algorithmus: Agglomerativer Clusteringalgorithmus

Eingabe: Datensatz , Distanzmetrik
Ausgabe: Dendrogramm

leeres Dendrogramm

for do
Füge Knoten zu hinzu

while do
Finde mit und minimal
Erzeuge Knoten . Setze als Kinder von .

Setze die Wurzel von auf , wobei
return

Anmerkung

Und wenn es mehrere mit minimalem Abstand gibt?

Gibt es mehrere mit minimalem Abstand, so wird zufällig eines der Paare gewählt.