Die Clusteranalyse umfaßt eine Vielzahl von zum Teil sehr verschiedenen statistischen Verfahren, die das Ziel haben, eine Menge von Objekten nach einem wohldefinierten Kriterium in Gruppen (auch Klassen genannt) einzuteilen. Man gruppiert dabei die Objekte bezüglich eines Ähnlichkeitsmaßes oder Distanzmaßes so, daß sich die Objekte einer Gruppe möglichst ähnlich, die Objekte verschiedener Gruppen möglichst unähnlich sind.

Die Verfahren spielen eine große Rolle in der Medizin und Psychologie, wo es beispielsweise um die Gruppierung von Probanden in bestimmte Konstitutionstypen, Persönlichkeits- bzw. Charaktertypen oder kognitive Typen auf der Basis an den Objekten (Probanden) gemessener Merkmale geht.

Die Verfahren der Clusteranalyse unterscheiden sich vor allem hinsichtlich der Art der verwendeten Ähnlichkeitsmaße und der zu erwartenden (angestrebten) Gruppenstruktur. Hinsichtlich letzterem unterscheidet man zwischen den Clusterverfahren für eine vollständige Zerlegung der Objektmenge und den hierarchischen Clusteranalyseverfahren.

1. Clusterverfahren für eine vollständige Zerlegung

Die Menge der n zu gruppierenden Objekte O = {O₁,…, O_n} soll in m Gruppen G₁, …, G_m so aufgeteilt werden, daß jedes Objekt in genau einer Gruppe liegt, d. h. es gilt

\begin{eqnarray}G_i \cap G_j = \emptyset \,{\rm{f}\rm{\ddot{u}}\rm{r}}\,i \ne j\,{\rm{und}}\,\bigcup\limits_{i = 1}^m {G_j = \mathcal{O}.}\end{eqnarray}

Gesucht ist dabei eine im Sinne der Optimierung einer vorgegebenen Gütefunktion g(\({\mathcal{G}}\)) (Clusterkriterium) beste Zerlegung \({\mathcal{G}}\) = {G₁, …, G_m} unter allen möglichen Zerlegungen \({\mathcal{G}}\) von O in m Gruppen mit der Eigenschaft (1).

Die Verfahren unterscheiden sich in der Gütefunktion g, d. h. dem Clusterkriterium. Einige typische Kriterien sind nachfolgend aufgeführt.

a) Varianzkriterium: Minimierung der Gesamtvarianz innerhalb der Gruppen.

Angenommen, die Objekte sollen auf der Basis von p beobachtbaren mindestens intervallskalierten Merkmalen (Skalentypen) gruppiert werden. Sei \({\overrightarrow x _i = (x_{i1}, \ldots,x_{ip} )^T }\) der Vektor der am Objekt O_i beobachteten p Merkmale, i = 1, …, n. Es wird die Gruppierung \({\mathcal{G}}\) gewählt, für die folgende Funktion g minimal wird:

\begin{eqnarray}g({\mathcal{G}})=\displaystyle \sum _{j=1}^{m}\displaystyle \sum _{{O}_{t}\in {G}_{j}}||{\overrightarrow{x}}_{i}-\overline{{\overrightarrow{x}}_{{G}_{j}}}|{|}^{2},\end{eqnarray}

wobei

\begin{eqnarray}\overline{{\overrightarrow{x}}_{{G}_{j}}}=\displaystyle\frac{1}{{n}_{j}}\displaystyle \sum _{{O}_{t}\in {G}_{j}}{\overrightarrow{x}}_{i}\end{eqnarray}

(n_j = Anzahl der Objekte in G_j) und || · || der euklidische Abstand zwischen zwei p-dimensionalen reellen Vektoren ist. Bei diesem Verfahren entstehen unter bestimmten Annahmen kugelförmige Gruppen mit etwa gleichem Radius.

b) Determinantenkriterium: Anstelle der Funktion (2) wird die folgende verwendet:

\begin{eqnarray}g({\mathcal{G}})=\rm{Det}\left(\displaystyle \sum _{j=1}^{m}\displaystyle \sum _{{O}_{t}\in {G}_{j}}({\overrightarrow{x}}_{i}-\overline{{\overrightarrow{x}}_{{G}_{j}}})({\overrightarrow{x}}_{i}-\overline{{\overrightarrow{x}}_{{G}_{j}}}T)\right)\cdot \end{eqnarray}

Bei diesem Verfahren entstehen unter bestimmten Annahmen Gruppen in Form von Ellipsoiden im p-dimensionalen Merkmalsraum.

c) Kriterien für dichotome Merkmalswerte (di-chotome Variable):

Ein ganz einfaches Verfahren besteht in folgendem. Man definiert sich auf bestimmte Weise Ähnlichkeitswerte

\begin{eqnarray}{s}_{ij}= \left\{ {\begin{array}{c} {1\,{O}_{i}\,\text{und}\,{O}_{j}\,\text{sind}\,{\rm{\ddot{a}}}\text{gnlich}},\\ {0\,{O}_{i}\,\text{und}\,{O}_{j}\,\text{sind}\,\text{nicht}\,{\rm{\ddot{a}}}\text{gnlich},}\end{array} } \right.\end{eqnarray}

und beschreibt die aktuelle Gruppierung durch die Matrix

\begin{eqnarray}{\delta}_{ij}=\left\{ {\begin{array}{c} {1\,{O}_{i}\,\text{und}\,{O}_{j}\,\text{sind in einer Gruppe}},\\ {0\,{O}_{i}\,\text{und}\,{O}_{j}\,\text{sind nicht in einer Gruppe}\text{.}}\end{array} } \right.\end{eqnarray}

Die zu minimierende Funktion g beschreibt den Abstand zwischen der Ähnlichkeitsmatrix und der aktuellen Gruppierung:

\begin{eqnarray}g({\mathcal{G}})=\displaystyle \sum _{j=1}^{m}\displaystyle \sum _{i=1}^{n}{({s}_{ij}-{\delta }_{ij})}^{2}.\end{eqnarray}

Das Problem aller Clusterverfahren dieser Gruppe besteht darin, daß wegen der schnell anwachsenden Zahl von Gruppierungsmöglichkeiten die Lösung der Optimierungsaufgabe durch vollständige Berechnung von \(g({\mathcal{G}})\) für alle möglichen Gruppierungen auch bei moderner Rechentechnik ausscheiden muß. Man verwendet in der Praxis iterative Verfahren der Extremwertsuche, die im allgemeinen bei einer durch hierarchische Clusterverfahren gewonnenen Lösung starten und die optimale Lösung annähern. Allerdings ist die Güte der Approximation unbekannt.

2. Hierarchische Clusteranalyse

Ist beispielsweise m unbekannt, so muß ein Verfahren der hierarchischen Clusteranalyse angewendet werden. Typische Vertreter sind die sogenannten agglomerativen Verfahren, die alle das gleiche Konstruktionsprinzip haben:

Die Objektmenge O soll in mehreren Schritten in eine Gruppenhierarchie, d.h in eine Folge von Gruppierungen \({{\mathcal{G}}}^{(0)},{{\mathcal{G}}}^{(1)},\ldots, {{\mathcal{G}}}^{(k)}\) zerlegt werden. Dabei besteht jede Gruppe der Anfangszerlegung aus genau einem Objekt und die letzte Zerlegung enthält nur eine Gruppe mit allen Objekten, d. h. es ist

\begin{eqnarray}{{\mathcal{G}}}^{(0)}=\{\{{O}_{1}\},\{{O}_{2}\},\ldots \{{O}_{n}\}\}\end{eqnarray}

und \({{\mathcal{G}}}^{(k)}=\{O\}\).

In jedem Schritt (Agglomerationsschritt) l, l = 1, …, k, entsteht \({\mathcal{G}}\)^(l) aus \({\mathcal{G}}\)^(l−1), indem man die in wohldefinierter Weise ähnlichsten Gruppen aus \({\mathcal{G}}\)^(l-1), sagen wir G_i und G_j, durch eine Gruppe G = G_i ∪ G_j ersetzt und die übrigen beibehält.

Die Ähnlichkeit zweier Gruppen wird auf der Basis von Ähnlichkeitsmaßen s bzw. Distanzmaßen d für Objekte beschrieben.

Typische Distanzmaße für den Fall, daß alle p Merkmale mindestens intervallskaliert sind, sind z. B.

1. Average-Linkage-Verfahren: Der Abstand zwischen zwei Gruppen wird durch das Mittel aller Abstände zwischen je zwei Objekten der Gruppen definiert

   \begin{eqnarray}{D}_{ij}:=D({G}_{i},{G}_{j})=\displaystyle\frac{1}{{n}_{i}{n}_{j}}\displaystyle \sum _{{O}_{r}\in {G}_{i}}\displaystyle \sum _{{O}_{s}\in {G}_{j}}{d}_{rs}.\end{eqnarray}

2. Single-Linkage-Verfahren: Der Abstand zwischen zwei Gruppen wird durch die Objekte bestimmt, die am nächsten zusammenliegen:

   \begin{eqnarray}{D}_{ij}:=D({G}_{i},{G}_{j})=\mathop{\min }\limits_{{O}_{r}\in {G}_{i},{O}_{s}\in {G}_{j}}{d}_{rs}.\end{eqnarray}

3. Complete-Linkage-Verfahren: Der Abstand zwischen zwei Gruppen wird durch das unähnlichste Objektpaar bestimmt:

   \begin{eqnarray}{D}_{ij}:=D({G}_{i},{G}_{j})=\mathop{\max }\limits_{{O}_{r}\in {G}_{i},{O}_{s}\in {G}_{j}}{d}_{rs}.\end{eqnarray}

Die folgende Abbildung zeigt das bei diesen Verfahren entstehende typische Bild, welches man als Dendrogramm bezeichnet.

Im ersten Agglomerationsschritt werden beispielsweise die Objekte O₂ und O₅, und im dritten Schritt die Objekte O₃ und O₄ zusammengefaßt. Nach fünf Schritten sind alle Objekte in einer Gruppe.

Literatur

[1] Bock, H.: Automatische Klassifikation. Göttingen, 1974.

[2] Hartung, J.; Elpelt,B.: Multivariate Statistik. R. Oldenburg Verlag München/Wien, 1989.

[3] Metzler, H.; Krause, B.: Angewandte Statistik. Deutscher Verlag der Wissenschaften, Berlin, 1983.