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}

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}

\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}

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}

\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}

\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.

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}

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.