Agglomerative Clusterverfahren
Author: Hans Lohninger
Agglomerative Clusterverfahren basieren auf folgendem Prinzip: Zwei Objekte, die sich am nächsten sind, werden ausgewählt und in einer neuen Gruppe (Cluster) zusammengelegt; nun wiederholt man diesen Prozess, bis alle Objekte und Cluster zu einem einzigen zusammengelegt sind. Während dieses Prozesses ist es notwendig, die Abstände der zusammengelegten Objekte aufzuzeichnen, um danach ein Dendrogramm konstruieren zu können. Die Art der Gruppierung kann von den Parametern der Lance-Williams-Gleichung beeinflusst werden:
dqi' = s dpi + t dqi + u dpq
+ v |dpi-dqp|
mit
s,t,u, und v als den Systemparametern, dpi, dqi, dpq als den Abständen zwischen den Clustern (oder Objekten) und dqi' als die neue Distanz zwischen dem neuen Cluster q und allen anderen Objekten i; dqi' ersetzt dqi während des Zusammenlegungsprozesses.
Unten finden Sie die Parameter der am meisten genutzten Gruppierungstechniken:
Art der Gruppierung |
s |
t |
u |
v |
Kommentar |
Einzelverknüpfung |
0.5 |
0.5 |
0 |
-0.5 |
beschränkt |
Komplettverknüpfung |
0.5 |
0.5 |
0 |
0.5 |
erweitert |
Durchschnittsverknüpfung |
0.5 |
0.5 |
0 |
0 |
Kompromiss |
mittlere |
0.5 |
0.5 |
-0.25 |
0 |
nicht monoton |
Zentroid-Verfahren (1) |
np/n |
nq/n |
-npnq/n2 |
0 |
nicht monoton |
Methode nach Ward (1) |
(np+ni)/(n-ni) |
(nq+ni)/(n-ni) |
-ni/(n-ni) |
0 |
"beste" Näherung |
flexible Strategie |
a |
a |
1-2a |
0 |
Parameter a bestimmt Verhalten |
n ... Anzahl der Objekte
np ... Anzahl der Objekte in Cluster p
nq ... Anzahl der Objekte in Cluster q
ni ... Anzahl der Objekte in Cluster i |
Nicht jedes der oben erwähnten Clustervefahren ist für jeden Datensatz gleich gut geeignet. Da die unterschiedlichen Verfahren unterschiedliche Tendenzen aufweisen, entweder die Bildung von Clustern oder aber die Unterscheidung von Clustern zu bevorzugen. Im Folgenden ein Beispiel das die Ergebnisse der drei wichtigsten Clusterverfahren zeigt:
|