Das gleiche gilt auch für die Konstruktion der Hierarchie......
Bei der Ermittlung einer Hierarchie startet man i.d.R. mit x Klassen (die jeweils ein Element beinhalten), vereinigt in jedem Iterationsschritt je zwei Klassen und hat am Schluss nur noch eine Klasse, die alle Elemente umfasst.
In jedem Iterationsschritt gehst Du dabei wie folgt vor:
1. neue Distanzmatrix ermitteln
- Heterogenitätsmaß?
I) single-linkage => Distanz(neu) = min(Distanz(alt)) zwischen je zwei Klassen
II) complete-linkage => Distanz(neu) = max(Distanz(alt)) zwischen je zwei Klassen
2. die globale minimale Distanz in der neuen Distanzmatrix ermitteln
3. die beiden jeweils betroffenen Klassen vereinigen
Bsp. (Klausur SS05 - Block II - Aufgabe 1)
a)
Hier muss zunächst die Distanzmatrix ermittelt werden (auf Distanzmaß achten, hier euklidischer Abstand!):
A___B______C_____D
0___0,37___0,27___0,195
____0______0,62___0,191
___________0______0,43
__________________0
b)
Basis: K^0 = {K^0(1),K^0(2,K^0(3),K^0(4)} = {{A},{B},{C},{D}}
=> Klassen mit jeweils einem Element
Jetzt bis zur Ermittlung der Klasse, die alle Elemente umfasst, die Iterationsschritte durchführen:
Erste Iteration:
1. Distanzmatrix aufstellen => D(0) = D (haben wir in Aufgabeteil a) ermittelt)
2. globale minimale Distanz in der Distanzmatrix ermitteln => 0,191 (Klassen {B},{D})
3. beide Klasse vereinigen: {B},{D} => {B,D}
=> neue Hierarchiebene: K^1 = {K^1(1), K^1(2), K^1(3)} = {{A},{B,D},{C}}
Nächste Iteration:
1. neue Distanzmatrix (Heterogenitätsmaß: single-linkage) aufstellen:
A___BD_____C
0___0,195___0,27
____0_______0,43
____________0
2. globale minimale Distanz in der Distanzmatrix ermitteln => 0,195 (Klassen {A},{B,D})
3. beide Klassen vereinigen: {A},{B,D} => {A,B,D}
=> neue Hierarchiebene: K^2 = {K^2(1), K^2(2)} = {{A,B,D},{C}}
Nächste Iteration:
1. neue Distanzmatrix (Heterogenitätsmaß: single-linkage) aufstellen:
=> kann hier entfallen, da nur noch zwei Klassen übrig!
2. globale minimale Distanz in der Distanzmatrix ermitteln => 0,195 (Klassen {A},{B,D})
=> kann hier entfallen, da nur noch zwei Klassen übrig!
3. beide Klassen vereinigen: {A,B,D},{C} => {A,B,C,D}
=> neue Hierarchiebene: K^3 = {K^3(1)} = {A,B,C,D}
Ermittlung beendet, das es nur noch eine Klassen gibt, die alle Elementen umfasst!
Die folgenden Klassen wurden somit generiert:
K(1) = K^0(1) = K^1(1) = {A}
K(2) = K^0(2) = {B}
K(3) = K^0(3) = K^1(3) =K^2(2) = {C}
K(4) = K^0(4) = {D}
K(5) = K^1(2) = {B,D}
K(6) = K^2(1) = {A,B,D}
K(7) = K^3(1) = {A,B,C,D}