Hierarchisch agglomerative Clusterverfahren

Beschreibung des Verfahrens

Wir gehen von einer Distanzmatrix der I Beobachtungen aus... . Die Klassifikationsmethoden unterscheiden sich untereinander durch spezifische Rechenregeln für die Abstände zwischen disjunkten Klassen von Beobachtungen. Nach jedem Fusionsschritt, der zur Bildung einer neuen Klasse führt, sind die Abstände zwischen der neuen und den anderen Klassen verfahrensspezifisch zu modifizieren. Das geschieht unter Bezugnahme auf die Abstände der an der Fusion beteiligten Klassen und der jeweils gerade betrachteten Klasse. Betrachten wir exemplarisch einen Fusionsschritt, bestehend aus den drei Etappen:

  1. Suche des minimalen Wertes in der Distanzmatrix. Es sei die minimale Distanz und A, B das zugehörige Klassenpaar (bei mehrdeutigem Minimum kann A, B durch das erste der Paare mit minimaler Distanz festgelegt werden), d.h.
  2. Fusion der Klassen A und B zur neuen Klasse R.
  3. Berechnung der Abstände der neuen Klasse R zu allen übrigen Klassen Q gemäß der allgemeinen Rekursionsformel

Parameterwerte der allgemeinen Rekursionsformel

Methode
single linkage (nearest neighbor)
1/2
1/2
0
-1/2
complete linkage
(furthest neighbor)
1/2
1/2
0
1/2
simple average linkage
1/2
1/2
0
0
average linkage
(UPGMA = unweighed pair group average)
0
0
median
1/2
1/2
-1/4
0
centroid
0
Ward
0

Die Rekursionsformel gibt dabei schon die für die Implementierung vorteilhafte Auflösung der Distanzformel. Die Ausgangsform der Distanzformel ist in den detailierten Beschreibungen angegeben.

Implementierung

  1. CCluster.NextStep() führt die nächste Fusion durch (wird von timer gestartet, progress bar wird weiter gesetzt)
  2. die zwei am nächsten liegenden Cluster suchen
  3. je nach Clustermethode Unterfunktion aufrufen

Variablen <-> Formel

Variablenname in CCluster Namen in Formel
fDistAQ, analog für BQ und AB d(A,Q)
nObjInA, analog für B |A|
fWeightA siehe Spalten der Tabelle Parameterwerte

Literatur

Vgl. Mucha S.96,

Kaufman 90,44

 

 

siehe auch:

  • keine Verweise

  •  

    Autor: E.Haimerl
    letzte Änderung am 13 Februar, 2004