Header
   TUM Logo Clusteranalyse Polytop
Header_Inhalt

Header Bild
Hierarchisches Clustern

Verschiedene Abstandsbegriffe bei Clustern

Der entscheidende Schritt für den hierarchischen agglomerierenden 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)
  • größter Abstand zwischen den Punkten aus zwei Clustern (Complete Link)
  • durchschnittlicher Abstand zwischen den Punkten aus zwei Clustern (Average Link)
  • Abstand der Zentroide der beiden Cluster
Wir betrachten die vier Fälle ausführlich an einem Beispiel, bestehend aus 6 zweidimensionalen Datenpunkten. Die Koordinaten der Punkte finden sich in Tabelle 1, Abbildung 1 zeigt den Beispieldatensatz und Tabelle 2 enthält die paarweisen Abstände von je zwei Punkten, wobei wir den euklidischen Abstand zugrunde legen.

Agnes

Abbildung 1: Datensatz aus 6 2-dimensionalen Datenpunkten


Punkt x-Koordinate y-Koordinate
p1 40 53
p2 22 38
p3 35 32
p4 26 19
p5 8 41
p6 45 30

Tabelle 1: Koordinaten der 6 Punkte

 
  p1 p2 p3 p4 p5 p6
p1 0 24 22 37 34 23
p2 24 0 15 20 14 25
p3 22 15 0 15 28 11
p4 37 20 15 0 29 22
p5 34 14 28 29 0 39
p6 23 25 11 22 39 0

Tabelle 2: Euklidische Abstände zwischen den einzelnen Punkten



Kürzester Abstand zwischen den Punkten aus zwei Cluster (Single Link)

Für diese Methode wird der Abstand von allen Punkten des einen Clusters zu allen Punkten des anderen Clusters berechnet. Der kleinste Abstand zwischen zwei Punkten aus den verschiedenen Clustern wird dann als Abstand der Cluster gewählt. Der Abstand zwischen den Clustern A und B bestimmt sich damit durch die Formel:

d(A, B ) = a∈mAi,nb∈B d(a,b)
PIC
Abbildung 2: kürzester Abstand
 

Wenden wir nun diese Methode auf unser Beispiel an. 

PIC

Abbildung 3: Beispiel für die kürzester Abstand-Methode
 

Der Algorithmus initialisiert jeden Punkt als seperates Cluster und sucht nun die beiden Cluster bzw. Punkte mit dem minimalen Abständen zueinander. Ein Blick in Tabelle 2 zeigt uns, dass dies die Punkte 3 und 6 sind. Also verschmilzt der Algorithmus diese beiden zu einem Cluster. Interessant ist erstmals der dritte Schritt in Abbildung 7. Die Abstände der verschiedenen Cluster sind gegeben durch.

dist({1},{2,5}) = min{dist({1},{2}),dist({1},{5})} = min{24,34} = 24
dist({1},{3,6}) = min{dist({1},{3}),dist({1},{6})} = min{22,23} = 22
dist({1},{4}) = min{dist({1},{4})} = min{37} = 37
dist({2,5},{3,6}) = min{dist({2},{3}),dist({2},{6}),dist({5},{3}),dist({5},{6})}
= min{15,25,28,39} = 15
dist({2,5},{4}) = min{dist({2},{4}),dist({5},{4})} = min{20,29} = 20
dist({4},{3,6}) = min{dist({4},{3}),dist({4},{6})} = min{15,22} = 15
Die Cluster {2,5} und {3,6} bzw. {4} mit {3,6} haben demnach minimalen Abstand zueinander und könnten miteinander verschmolzen werden. Genauere Rechnung zeigt, dass zuerst das Cluster aus 2 und 5 mit dem aus den Punkten 3 und 6 verschmolzen werden muss.

Die Hierarchie der Cluster ist durch das folgende Dendogramm gegeben.

Dendogramm

Abbildung 4: Dendogramm für die kürzester Abstand-Methode

Vorteil: Erkennt auch nicht elliptische Formen gut

Nachteil: Anfällig für Rauschen und Ausreißer



Größter Abstand zwischen den Punkten aus zwei Clustern (Complete Link)

Es werden wieder alle Abstände zwischen den Punkten aus den verschiedenen Clustern berechnet. Diesmal wird jedoch der größte Abstand zwischen zwei Punkten als Abstand der Cluster gewählt.

d(A, B ) = max d(a,b) a∈A,b∈B
 
PIC
Abbildung 5: größter Abstand

Diese Methode angewendet auf unser Beispiel liefert: 

PIC
Abbildung 6: Beispiel für die größter Abstand-Methode

Auch hier sehen wir uns die dritte Verschmelzung zweier Cluster genauer an. Die Abstände sind, ähnlich wie oben, gegeben durch:

dist({1},{2,5}) = max{dist({1},{2}),dist({1},{5})} = max{24,34} = 34
dist({1},{3,6}) = max{dist({1},{3}),dist({1},{6})} = max{22,23} = 23
dist({1},{4}) = max{dist({1},{4})} = max{37} = 37
dist({2,5},{3,6}) = max{dist({2},{3}),dist({2},{6}),dist({5},{3}),dist({5},{6})}
= max{15,25,28,39} = 39
dist({2,5},{4}) = max{dist({2},{4}),dist({5},{4})} = max{20,29} = 29
dist({4},{3,6}) = max{dist({4},{3}),dist({4},{6})} = max{15,22} = 22

Die Wahl der zu verschmelzenden Cluster ist eindeutig. Der Punkt 4 wird dem Cluster aus den Punkten 3 und 6 hinzugefügt. Auch hier das Dendogramm zum Vergleich. 

Dendogramm

Abbildung 7: Dendogramm für die größter Abstand-Methode

Vorteil: Kaum anfällig gegenüber Rauschen und Ausreißern
Nachteil: Begünstigt kugelförmige Cluster, kann große Cluster zerstören



Durschschnittlicher Abstand zwischen den Punkten aus zwei Clustern (Average Link)

Nach der Berechnung aller Abstände zwischen den Punkten zweier Cluster wird der Mittelwert über alle Abstände gebildet.

∑ d(a,b) d(A, B) = --a∈A,b∈B------ |A ||B |
 
PIC
Abbildung 8: durchschnittlicher Abstand
 
 
Im Beispiel ergibt sich deshalb folgende Struktur: 

PIC

Abbildung 9: Beispiel für die durchschnittlicher Abstand-Methode
 

Auch hier sehen wir uns wieder den dritten Schritt an. Die Abstände sind gegeben durch:

dist({1},{2,5}) = avg{dist({1},{2}),dist({1},{5})} = avg{24,34} = 24-+-34 1* 2 = 29
dist({1},{3,6}) = avg{dist({1},{3}),dist({1},{6})} = avg{22,23} = 22-+-23 1* 2 = 22,5
dist({1},{4}) = avg{dist({1},{4})} = avg{37} = 37
dist({2,5},{3,6}) = avg{dist({2},{3}),dist({2},{6}),dist({5},{3}),dist({5},{6})}
= avg{15,25,28,39} = 15+ 22 + 28 + 39 ---------------- 2* 2 = 26
dist({2,5},{4}) = avg{dist({2},{4}),dist({5},{4})} = avg{20,29} = 20-+-29 2* 1 = 24,5
dist({4},{3,6}) = avg{dist({4},{3}),dist({4},{6})} = avg{15,22} = 15-+-22 1* 2 = 18,5

Der kleinste Abstand ergibt sich also zwischen dem Punkt 4 und dem Cluster aus den Punkten 3 und 6. 

Dendogramm

Abbildung 10: Dendogramm für die durchschnittlicher Abstand-Methode


Abstand der Zentroide der beiden Cluster

Hier werden in jeder Phase des Algorithmuses zunächst die Zentroide jedes Clusters bestimmt (für Zentroide vgl. K-Means - LINK!). Anschließend ergibt sich der Abstand zwischen zwei Clustern als der Abstand ihrer Zentroide.

d(A,B ) = d(a,b) mit a,b den Zentroiden von A respektive B
 
PIC
Abbildung 11: Abstand der Zentroide

In der folgenden Grafik, die die Anwendung des Algorithmuses zeigt, sind die Zentroide der jeweiligen Cluster durch Kreuze gekennzeichnet. 

PIC

Abbildung 12: Beispiel für die Zentroid-Methode

 

Sehen wir uns auch hier den dritten Schritt an. Zunächst müssen wir die Koordinaten der Zentroide berechnen:

Zentroid{2,5} = (22+-8- 2,38+-41- 2) = (15,39,5)
Zentroid{3,6} = (35+-45- 2,32+-30- 2) = (40,31)

Die Abstände der Cluster ergeben sich nun als die Abstände ihrer Zentroide:

dist({1},{2,5}) = dist({1},Zentroid{2,5}) = ∘ --------2-------------2- (40- 15) + (53 - 39,5) = 28
dist({1},{3,6}) = dist({1},Zentroid{3,6}) = ∘ ---------------------- (40- 40)2 + (53 - 31)2 = 22
dist({1},{4}) = dist({1},{4}) = ---------------------- ∘ (40 - 26)2 + (53 - 19)2 = 38
dist({2,5},{3,6}) = dist(Zentroid{2,5},Zentroid{3,6}) = ∘ ---------2------------2- (15 - 40) + (39,5- 31) = 26
dist({2,5},{4}) = dist(Zentroid{2,5},{4}) = ∘ ------------------------ (15- 26)2 + (39,5 - 19)2 = 23
dist({4},{3,6}) = dist({4},Zentroid{3,6}) = ∘ (26--40)2-+-(19---31)2- = 18

Es wird also als nächstes der Punkt 4 dem Cluster aus 3 und 6 hinzugefügt. 

Dendogramm

Abbildung 13: Dendogramm für die Zentroid-Methode
 

Nachteil: Der Abstand zwischen den Zwischen den Clustern kann im Laufe des Verfahrens abnehmen.

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