Definition - Divisive Verfahren

• Generalisierungen:
  • Hierarchisches Clustering
• Involvierte Definitionen:
  • Metrik
  • siehe auch Agglomerative Verfahren
• Veranstaltung: EML
• Referenz: @thimm2024 (Abschnitt 3.2.1)

⠀

Definition: Divisive Verfahren

Als divisive Verfahren (auch top-down Verfahren) bezeichnen wir Methoden des hierarchischen Clusterings, die Dendrogramme von der Wurzel her aufbauen.

• Die Datenpunkte werden alle einem gemeinsamen Cluster zugewiesen.
• Anschließend werden die Knoten iterativ in zwei (oder mehr) Kind-Cluster aufgeteilt, so lange, bis alle Datenpunkte in Blätter aufgeteilt wurden.

Formal:

Algorithmus: Divisive Analysis Clustering (DIANA)

Eingabe: Datensatz , Distanzmetrik
Ausgabe: Dendrogramm

leeres Dendrogramm
Setze Wurzel von auf
while Es existiert Blattknoten von mit do:



while True do

if then


else
break
Setze und als neue Kinder von in
return

Anmerkung

Welche Distanzmetriken?

Der DIANA-Algorithmus kann die selben Distanzmetriken nutzen wie der allgemeine agglomerative Algorithmus.

Siehe hierzu auch:

• Single-Link-Clustering
• Average-Link-Clustering