Header
   TUM Logo Clusteranalyse Polytop
Header_Inhalt

Header Bild
Hierarchisches Clustern

Hierarchisches Clustern

Anwendungsgebiete

Hierarchische Clusterverfahren werden angewendet, wenn das Ergebnis eine abgestufte Cluster-Struktur aufweisen soll. Die Klassifizierung von Tieren in Arten, Gattungen, etc. ist ein Beispiele hierfür.

PIC
Beispiel für eine Hierarchie im Tierreich
 

Grundlagen und Idee des Algorithmus

Hierarchische Clusterverfahren teilen die Datenmenge in eine abgestufte Folge von Clustern ein. Dazu werden sukzessive entweder zwei benachbarte Cluster verschmolzen (agglomerierendes Verfahren) oder ein Cluster in zwei verschiedene aufgesplittet (trennendes Verfahren).

PIC
Agglomerierende vs. trennende Verfahren

 

Das Ergebnis wird dabei in einem sogenannten Dendogramm dargestellt.

Dabei werden auf der x-Achse die Datenpunkte aufgetragen. Die y-Achse gibt an, bei welchem Abstand zwei Cluster verschmolzen wurden. Die Ein-Punkt-Cluster aus den Punkten 1 und 2 haben also den Abstand 10.
 
PIC
Dendogramm
 

Im Folgenden gehen wir ausschließlich auf die agglomerierende Verfahren ein, da diese in der Praxis weitaus gebräuchlicher sind.

Algorithmus des agglomerierenden hierarchischen Cluster-Verfahrens

Die Grundidee beschreibt der folgende Algorithmus:

 

1. Erzeuge für jeden Punkt aus dem Datensatz ein seperates Cluster
2. Berechne den Abstand zwischen allen Clustern
Wiederhole
   3. Verschmelze die beiden Cluster, die den geringsten Abstand zueinander haben
   4. Aktualisiere die Distanzen zwischen den Clustern
bis alle Punkte in dem gleichen Cluster liegen

Da es in der Praxis nicht sinnvoll ist, als Endergebnis ein Cluster mit allen Datenpunkten zu erhalten, sollte der Algorithmus an geeigneter Stelle abbrechen. Eine verbreitete Methode hierfür ist der Abbruch, sobald der Abstand zwischen den Cluster eine bestimmte Distanz überschreitet.

Berechnung des Abstandes zwischen zwei Clustern

Der entscheidende Schritt für den Algorithmus ist die Auswahl der zu verschmelzenden Cluster. Die zentrale Fragestellung lautet:

Wie berechne ich den Abstand zwischen zwei Clustern?

Lösungsmöglichkeiten sind:

  • kürzester Abstand zwischen den Punkten aus zwei Clustern (Single Link)
                d(A, B ) = a∈mAi,nb∈B d(a,b)
PIC
  • größter Abstand zwischen den Punkten aus zwei Clustern (Complete Link)  
                d(A, B ) = max d(a,b) a∈A,b∈B
PIC
  • durchschnittlicher Abstand zwischen den Punkten aus zwei Clustern (Average Link)
                ∑ d(a,b) d(A, B) = --a∈A,b∈B------ |A ||B |
 
PIC
  • Abstand der Zentroide der beiden Cluster
                d(A,B ) = d(a,b) mit a,b den Zentroiden von A respektive B
 
PIC
 
Wir betrachten die vier Fälle ausführlich an einem Beispiel, bestehend aus 6 zweidimensionalen Datenpunkten. Je nach Wahl des Abstandsbegriffs erhält man unterschiedliche Clusterfolgen. Dies machen wir anhand der Dendogramme und weiterer Graphiken deutlich.
Link zum Beispiel "Abstand zwischen zwei Clustern"
 

Zeit- und Speicherkomplexität des hierarchischen Clusterns

Bei den folgenden Überlegungen nehmen wir an, dass wir m Daten clustern möchten.

Zeitkomplexität

Die Berechnung aller Abstände in Schritt 2 des Algorithmus benötigt 2 O (m ). Die anschließende Schleife wird m - 1 mal durchlaufen, da bei jedem Durchlauf zwei Cluster verschmolzen werden. Im i.ten Durchlauf gibt es also m - i+ 1 Cluster. Daraus sind nun die beiden mit dem geringsten Abstand zueinander zu wählen. Im schlimmsten Fall, bei einer einfachen Suche, benötigt dies O ((m - i+ 1)2). Anschließend müssen m - i Abstände zwischen den Clustern aktualisiert werden. Der i.te Durchlauf kostet damit insgesamt O ((m - i+ 1)2) bei O(m ) Durchläufen. Dies ergibt eine Gesamtlaufzeit von 3 O(m ). Durch geeignete Suchverfahren und Datenstrukturen - speichere die Abstände in einer sortierten Liste - kann dies auf 2 O (m log m ) verbessert werden.

Speicherkomplexität

Für jeden Punkt muss das Cluster gespeichert werden, dem er zugeordnet ist. Der Speicher hierfür ist linear in der Anzahl der Datenpunkte. Außerdem werden noch die Abstände zwischen allen Clustern gespeichert. Dies benötigt O(12m2 ) unter der Annahme, dass das Abstandsmaß symmetrisch ist. Die gesamte Speicherkomplexität beträgt damit O (m2)

 

Vor- und Nachteile von hierarchischen Clusterverfahren

Die Besonderheiten des jeweiligen Algorithmus hängen, wie oben angedeutet, von der konkreten Bestimmung des Abstandes zwischen den Clustern ab. Allen hierarchischen Verfahren ist jedoch gemein, dass sie im Gegensatz zu K-Means keine Initialisierungsschwierigkeiten besitzen. Dahingegen sind hierarchische Verfahren mit einer Laufzeit von O(m3 ) in der Anzahl der Datenpunkte teuer.

Copyright 2009 - Team Clusteranalyse
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _