Methoden der Datenanalyse - Clusteranalyse

Klassifikation - Partition

Wichtig im Zusammenhang mit der Clusteranalyse ist nun auch der Begriff der „Klassifikation“. Eine Klassifikation Ω ist ein System von Teilmengen (Klassen, Gruppen, Cluster) der Menge aller Beobachtungseinheiten (Objekte). In Bezug auf die Clusteranalyse fordert man zumeist, dass eine Klassifikation disjunkt und exhaustiv ist. Ersteres meint, dass jede Beobachtung zu höchstens einer Teilmenge zugeordnet wird. Zweiteres meint, dass jede Beobachtung zu mindestens einer Teilmenge zugeordnet wird. Eine Klassifikation, die disjunktiv und exhaustiv ist, nennt man „Partition“.

Aufgabe 11 Welche Partitionen können zu den Daten in Aufgabe 10 gefunden werden?

Die Anzahl der möglichen verschiedenen Partitionen von $n$ Elementen ist durch die sogenannten BELLschen Zahlen gegeben. Diese „explodieren“ bei wachsender Anzahl von Beobachtungseinheiten.

Tabelle 3: Bell'sche Zahlen

N	0	1	2	3	4	5	6	7	8	9	10
#Partitionen	1	1	2	5	15	52	203	877	4140	21147	115975
N	20					50
#Partitionen	51724158235372					1,9*1047

Die „beste“ Partition zu finden ist nun die Aufgabe der Clusteranalyse und dies ist - in Anbetracht von Tabelle 3 - wenn nicht gerade drei bis fünf Objekte in Gruppen geteilt werden sollen, relativ schwierig. Analog zur Variablenselektion in der Regressionsanalyse gibt es aber nun Verfahren, die schrittweise durch Trennen oder Verbinden von Teilmengen eine möglichst gute Partitionen herausfinden sollen. Diese Methoden werden im folgenden Abschnitt diskutiert.

Hierarchische Verfahren

Grundbegriffe

Hierarchische Verfahren stellen Hierarchien von Partitionen auf. Bewegt man sich in eine Richtung der Hierarchie, unterscheiden sich „benachbarte“ Partitionen dadurch, dass entweder zwei Klassen miteinander „verschmolzen“ werden („Vergröberung“) oder eine Klasse in zwei aufgespalten wird („Verfeinerung“). In Abbildung 17 erhält man die Partition rechts durch Vergröberung der Partition links bzw. jene links durch Verfeinerung der rechten.

Verfeinerung und Vergröberung

Je nachdem, ob das Verfahren kontinuierlich vergröbert oder verfeinert, spricht man von agglomerativen Verfahren bzw. divisiven Verfahren. Im weiteren Verlauf dieses Abschnitts soll nur auf agglomerative Verfahren eingegangen werden.

Bei agglomerativen Verfahren beginnt man mit jener Partition, in der jede Beobach­tungseinheit eine Klasse definiert. Im weiteren Verlauf werden jeweils die beiden Klassen, die einander am ähnlichsten sind, miteinander zu einer Klasse verbunden. In jedem Schritt wird auch ein Heterogenitätsindex der erhaltenen Partition berechnet. Diese Prozedur geschieht solange, bis jene Klassifikation erreicht ist, die nur eine Klasse mit allen Werten enthält. Das Ergebnis eines agglomerativen Ver­fah­rens ist eine Liste von durchgeführten Verbindungen und ein Vektor von Heterogenitätsmaßen.

Der Anwender hat nun zur genauen Durchführung der Analyse also zwei Fragen zu beantworten:

• Frage 1: Was bedeutet „einander am ähnlichsten“ in Bezug auf Gruppen?

• Frage 2: In wieviele und welche Gruppen sollen die Daten nun aufgeteilt werden?

Methoden zur Agglomeration

Frage 1 kann auf verschiedene Arten beantwortet werden und wieder hat der Anwender die Aufgabe, die Analyse genauer zu spezifizieren. Die Standardfunktion zur hierarchischen Clusteranalyse in R bietet beispielsweise sieben verschiedene Heterogenitätsmaße die die Unähnlichkeit zwischen je zwei Klassen ausdrücken.

Single Linkage, Complete Linkage und Average Linkage

Die Distanz zweier Klassen zueinander ist definiert als die kleinste („Single Linkage“), größte („Complete Linkage“) bzw. durchschnittliche („Average Linkage“) Distanz die zwischen beliebigen Paaren von Beobachtungen vorkommt. Die Paare bestehen dabei immer aus je einer Beobachtung aus beiden Klassen.

Median und Zentroid

Die Median- und die Zentroidmethode beziehen sich ebenfalls auf den „mittleren“ Abstand zwischen zwei Objektklassen. Der Nachteil ist hier, dass in Folge einer schrittweisen Fusionierung der Klassen das Heterogenitätsmaß nicht immer not-wendigerweise höher wird. So eine Hierarchie ist jedoch schwer zu interpretieren.

Ward

Das Ward-Kriterium fusioniert jene beiden Klassen, bei denen ein minimaler Zuwachs an Varianz innerhalb der Klassen erreicht wird.

Beispiel 4 Betrachten wir nochmals die Daten aus Aufgabe 10. Ziel ist nun, eine hierarchische Clusteranalyse mit den Daten durchzuführen. Wir wählen als Abstand die L2-Distanz und als Agglomerations-Methode „Complete Linkage“. Zuerst Beginn besteht die Startpartition ${\mathcal {A}}_{1}=\{\{1\},\{2\},\{3\},\{4\}\}$. Nun wird die Distanzmatrix berechnet: $d_{12}={\sqrt {(8-6)^{2}+(9-2)^{2}+(6-3)^{2}}}={\sqrt {62}}$ Beob.-Einheit 2 3 4 1 ${\sqrt {62}}$ ${\sqrt {45}}$ ${\sqrt {66}}$ 2 ${\sqrt {13}}$ ${\sqrt {6}}$ 3 ${\sqrt {33}}$ Die Beobachtungen 2 und 4 sind jene mit dem geringsten Abstand zueinander. Diese werden zur folgenden Partition fusioniert. Damit hat die erste Vergröberung stattgefunden.${\mathcal {A}}_{1}=\{\{1\},\{2,4\},\{3\}\}$Der Heterogenitätsindex zu dieser Vergröberung ist gleich der maximal in einem Cluster vorkommenden Distanz. Daher: $h_{1}={\sqrt {6}}$ . Nach der „Complete Linkage“-Methode werden nun die neuen Abstände definiert, beispielsweise $d_{1,(2,4)}=\max \left(d_{12},d_{14}\right)$ Beob.-Einheit (2,4) 3 1 $\max({\sqrt {62}},{\sqrt {66}})={\sqrt {66}}$ ${\sqrt {45}}$ (2,4) $\max({\sqrt {13}},{\sqrt {33}})={\sqrt {33}}$ Damit findet im nächsten Schritt die Fusion zwischen Beobachtung 3 und dem Cluster bestehend aus 2 und 4 statt. Die neue Partition ist${\mathcal {A}}_{1}=\{\{1\},\{2,3,4\}\}$und der Heterogenitätsindex zu dieser Vergröberung ist $h_{2}={\sqrt {33}}$ Im letzten Schritt wird zur Partition ${\mathcal {A}}_{1}=\{\{1,2,3,4\}\}$ fusioniert und $h_{3}=\max({\sqrt {66}},{\sqrt {45}},{\sqrt {33}})={\sqrt {66}}$ .

Heterogenitätsindex und Dendrogramm

Ehe Frage 2 des vorletzen Abschnitts beantwortet werden kann, sollte das Ergebnis der Analyse graphisch aufbereitet werden. Bei hierarchischen Clusteranalysen ge­schieht dies zumeist durch das Dendrogramm. Dies ist eine Darstellung, in welcher Reihenfolge welche Fusionsschritte vollzogen worden sind und wie heterogen die gefundenen Cluster sind. Dadurch fließt auch der jeweils protokollierte Heterogenitätsindex in die Grafik ein.

Die Entscheidung, wieviele Gruppen gebildet werden sollen, ist nun dem Anwender überlassen. Wie heterogen die Mitglieder der jeweils selben Gruppe sein sollen, hängt auch von der inhaltlichen Fragestellung ab. Daher kann in Beispiel 4 darüber keine Empfehlung gegeben werden (Abbildung 18).

Fortsetzung Beispiel 4''''

Dendrogramm aus Beispiel 4

Weitere Clusteralgorithmen

Partitionierende Verfahren

Die partitionierenden Verfahren unterscheiden sich von den hierarchischen Clusterverfahren dadurch, dass hier versucht wird, eine bereits bestehende Partition durch Umgruppieren einzelner Beobachtungen bezüglich festgelegten Kriteriums zu optimieren. Man sollte hier aber eine Vorstellung bezüglich der Clusteranzahl haben, da diese jeweils zu den Standard-Inputs solcher Verfahren gehören. Die Ausgangspartition kann zum Beispiel durch ein hierarchisches Verfahren ermittelt werden, aber auch durch Gruppierung um Kristallisationskerne (potentielle Klassenschwerpunkte) oder durch Verwendung zufälliger Anfangspartitionen.

Die Vorgehensweise ist weiters wie folgt:

1. Definiere zusätzlich zur Startpartition ein Optimierungskriterium

5. Prüfe bei jeder Beobachtung, ob das Kriterium durch Zuordnung der Beobachtung in einen anderen Cluster verbessert werden kann

6. Ordne jene Beobachtung um, die die beste Verbesserung des Kriteriums erzielt

7. Wiederhole die Schritte 2 und 3 bis keine Verbesserung mehr möglich ist.

Verwendung finden oft Kriterien, die in irgendeiner Form die Streuung innerhalb der verschiedenen Gruppen minimieren (wie das schon besprochene „Ward“-Kriterium). Eine bekannte Methode stellt hierbei die (auch in R implementierte) k-Means-Methode dar.

Modellbasiertes Clustering

Im Gegensatz zu den bisherigen Verfahren, die eher auf heuristischen Über­legungen beruhen, legt man beim modellbasierten Clustering ein stochastisches Modell zugrunde. Man betrachtet die verschiedenen Gruppen als Realisierung von verschiedenen Populationen, denen jeweils eine bestimmte statistische Verteilung unterstellt wird – meist die Normalverteilung.

Bei den Modellen wird dann die Auftrittswahrscheinlichkeit gegeben eine Klassen­zu­gehörigkeit und den Verteilungsparametern berechnet und die Klassenzuordnungen werden solange geändert, bis diese Auftrittswahrscheinlichkeit maximiert wird.

Abbildung 19 zeigt anhand einer Grafik, was hier passiert. Gegeben sind die sieben Datenpunkte, die auf der X-Achse mit einem Kreuz eingetragen sind. Es sollen nun zwei Kandidaten für eine Clustergruppierung gegenübergestellt werden. Auf der linken Seite wird die – intuitive – Lösung vorgeschlagen, eine Einteilung in drei Gruppen. Legt man die Einteilung fest, kann man daraus die Dichtefunktion der zugehörigen Normalverteilung schätzen. Führt man dies für alle drei Gruppen durch, erhält man nach Multiplikation der sieben Dichtefunktionswerte ein Maß für die Plausibilität der Stichprobe gegeben die Clustereinteilung, die „Likelihood“.

Sie beträgt

$L_{1}\left(x\mid {\text{ Einteilung }}1;{\widehat {\mu _{2}}};{\widehat {\sigma _{l}}}\right)=0,80\times 0,80\times 0.29\times 0.51\times 0.4\times 0.88\times 0.88\approx 0.03$.

Eine andere Partition wurde rechts gewählt. Dort wurden zwei Gruppen unterstellt (die kleinsten drei und die größten vier Beobachtungen). Wieder kann die Likelihood dieser Stichprobe berechnet werden. Diesmal ergibt sich:

$L_{2}\left(x\mid {\text{ Einteilung }}2;{\hat {\mu }}_{\nu };{\widehat {\sigma }}_{2}\right)=0,22\times 0,28\times 0.16\times 0.16\times 0.19\times 0.20\times 0.15\approx 9*10^{-6}$.

Gewählt wird nun jene Partition, die die höchste Likelihood liefert. Für die Daten in Abbildung 19 ist die linke Gruppierung die bestmögliche.

Im multivariaten Fall (der für die Clusteranalyse relevant ist) gibt es viele Möglichkeiten, welche Annahmen über die Varianzen bzw. Kovarianzen gemacht werden (Alle Varianzen gleich oder nicht? Kovarianzen gleich Null oder nicht? usw.). Die Clusteranalyse mittels Modellannahme hat aber auch noch einen weiteren Nutzen. Es zeigt sich, dass verschiedene heuristische Verfahren implizit dieselbe Optimierung durchführen. Dadurch können diese Verfahren im Nachhinein gerechtfertigt werden.

Prinzip der modellbasierten Clusteranalyse

Clusteranalyse in R

Um die Arbeitsweise eines Clusteralgorithmus besser nachzuvollziehen zu können, soll eine Analyse nun an einem Beispiel, an dem die Daten leicht visualisiert werden können (zwei Dimensionen) gerechnet werden. Im allgemeinen werden die Daten durch mehrere Variablen charakterisiert.

Die vorliegenden Daten haben fast schon sporthistorischen Wert, geht es doch um die jeweils nationalen Bestleistungen in acht olympischen Laufbewerben (100m, 200m, 400m, 800m, 1500m, 5000m, 10000m, Marathon) aus dem Jahr 1984, protokolliert vor den olympischen Spielen in Los Angeles. Ziel der Analyse ist herauszufinden, welche Länder ähnliche Bestzeiten und über ein ähnliches Leistungsniveau im Laufsport verfügen.

Mittels Hauptachsentransformation wurden bereits zwei Komponenten extrahiert, die über 90% an Varianz erklären. Diese können als „mittleres Leistungsniveau auf alle Strecken“ bzw. als „Ausdauer vs. Schnellkraft“ bezeichnet werden. Abbildung 20 zeigt die Länder in dem zweidimensionalen Raum. Nationen, die weit links stehen, haben ein hohes mittleres Leistungsniveau. Nationen, die oben stehen, haben bezogen auf ihr mittleres Leistungsniveau eine größere Bedeutung im Ausdauerbereich.

Darstellung der Länder in beiden Dimensionen

Die R-Sequenz, um aus den Daten Abbildung 20 zu erzeugen lautet wie folgt:

• Track.FA<-read.csv("C:\\...\\Track_FA.csv",header=TRUE,dec=",",sep=";")

1. einlesen

• nam<-Track.FA[,1]
• dat<-Track.FA[,2:3]

1. Trennung von Ländernamen und Werten

• plot(dat[,1],dat[,2],type="n",xlab="Generelles Leistungsniveau",ylab="Schnellkraft vs. Ausdauer")

1. produziert einen XY-Scatterplot, allerdings ohne Punkte

• text(dat[,1], dat[,2],nam)

1. trägt anschließend an den Stellen der Punkte die Ländernamen ein

Wieviele homogene Gruppen suggeriert Abbildung 20 nun? Wir haben einerseits zwei Ausreißern (Western Samoa und Cook Islands), sowie eine Gruppe von fünf Ländern im mittleren Leistungsniveau, die eher sprintstark bzw. schwach in Ausdauer­bewerben sind (Dominikanische Republik, usw.). Die Topgruppe scheint vom Mittelfeld weniger gut trennbar.

Es wurde nun eine hierarchiche Clusteranalyse berechnet (Abbildung 21), die euklidische Distanzen und den „Complete-Linkage“-Algorithmus verwendet. Im Gegensatz zum „Single-Linkage“-Algorithmus, der zu bereits großen Gruppen immer noch einzelne Beobachtungen Schritt für Schritt dazuhängt, wachsen die Clustergrößen beim „Complete Linkage“ eher gleichmäßig.

Code-Fortsetzung:

Fortsetzung des R-Codes zur Clusteranalyse

Das erzeugte Objekt „result1“ ist vom Typ „hclust“, beinhaltet daher alle Informationen, die bei einer hierarchischen Clusteranalyse berechnet werden. Es können auf Wunsch mehrere Attribute ausgegeben werden. Wird so ein Objekt mit dem „plot“-Befehl versehen, entsteht das Dendrogramm (Abbildung 22). Die Gruppen sollen nun so gewählt werden, dass sie untereinander homogen und zueinander heterogen sind. Der hier gewählte Kompromiss ist jener, der das Dendrogramm horizontal an der Stelle $3,1<h<4,2$ schneidet und sechs Gruppen liefert. Dies wird durch die Funktion „cutree“ (Abbildung 21) erzeugt. Das Ergebnis der Gruppenzuordnung wird sodann unter „partition1“ abgespeichert.

Die beiden weiteren erstellten Partitionen wurden mit dem schon erwähnten k-Means-Algorithmus in R berechnet. Partition 2 verwendet die in Partition 1 gefundenen sechs Klassenschwerpunkte und ordnet jene Datenpunkte um, die näher zu einem anderen als dem eigenen Klassenschwerpunkt liegt. Nach einer Iteration werden die Schwerpunkte wieder neu berechnet. Das Verfahren konvergiert ziemlich schnell. Es müssen kaum Daten umgruppiert werden.

Partition 3 wählt ebenfalls die k-Means-Methode für sechs Gruppen, jedoch mit sechs zufällig gewählten Beobachtungen als Anfangsschwerpunkten. Das Verfahren wurde mehrere Male mit jeweils 1000 Iterationen durchgeführt. Die am häufigsten gefundene Gruppierung wurde hier als „partition3“ gespeichert. Die Konvergenz ist hier allerdings sehr langsam.

Die Unterschiede zwischen den drei Verfahren sind in Abbildung 23 ersichtlich. Zu beachten ist, das Partition 3 die beiden Ausreißer in eine Gruppe gibt. Unter dieser Voraussetzung wären wohl fünf Gruppen ausreichend. Am ehesten ist Einteilung 2 zu bevorzugen, da hier das Ergebnis einer hierarchischen Analyse weiter optimiert wurde und der Algorithmuss konvergiert. Jeder Datenpunkt ist dort dem Mittelpunkt seiner jeweiligen Gruppe näher als jedem anderen Mittelpunkt.

Abschließend sind die gefundenen Cluster nun noch zu charakterisieren. Tabelle 4 zeigt die Zuordnung der Länder zu den Clustern. Abbildung 24 stellt für alle acht Laufstrecken jeweils die Abweichung des Clustermittelwerts zum Gesamtmittelwert dar. Cluster 2 stellt sich als in jeder Disziplin überlegen heraus. Cluster 4 und 6 sind die beiden schwachen „Laufnationen“ am anderen Ende des Spektrums. Cluster 1 ist nach Cluster 2 die „zweite Leistungsgruppe“. Interessant sind nun Cluster 3 und 5. Cluster 3 ist in den beiden Sprintdistanzen besser als Cluster 1, in den drei längsten Distanzen jedoch nur besser als die beiden „Exoten“. Die Nationen von Cluster 5 sind bei diesen Distanzen am drittbesten, liegen aber beispielsweise auf 100m im Durchschnitt sogar hinter Western Samoa. Diese und weitere Erkenntnisse liefert also die durchgeführte Analyse.

Tabelle 4: Länderzuordnung zu den Clustern

Cluster	Länder
1	Argentina, Austria, Chile, China, Columbia, Denmark, Greece, India, Ireland, Israel, Japan, South Korea, Luxembourg, Mexico, Norway, Portugal, Romania, Taiwan, Turkey
2	Australia, Belgium, Brazil, Canada, Czechoslovakia, Finland, France, East Germany, West Germany, United Kingdom, Hungary, Italy, Kenya, Netherlands, New Zealand, Poland, Spain, Sweden, Switzerland, USA, USSR
3	Bermuda, Dominican Republic, Malaysia, Singapore, Thailand
4	Cook Islands
5	Burma, Costa Rica, Guatemala, Indonesia, North Korea, Mauritius, Papua New Guinea, Philippines
6	Western Samoa

Dendrogramm, L-Distanz (euklidisch)

 

Darstellung der drei ermittelten unterschiedlichen Partitionen

Charakteristik der sechs Cluster. Aufgetragen sind die Differenzen der Gruppenmittelwerte zum Gesamtmittelwert in der jeweiligen gemessenen Einheit.

Wiederholungsaufgaben und Zusammenfassung

1. Was ist eine Partition?

8. Was ist eine Hierarchie?

9. Wie unterscheiden sich hierarchische Verfahren von partitionierenden Verfahren?

10. Wieviele Partitionen untersuchen Sie bei einem agglomerativen Verfahren mit gegebenen Algorithmus mit 20 Beobachtungen? Wieviele gibt es insgesamt?

11. Betrachten sie nochmals die vier Datenpunkte in Aufgabe 10. Führen Sie die „Average Linkage“-Methode unter Verwendung der L₂-Distanzen durch und veranschaulichen Sie die Fusionsreihenfolge und die dazugehörigen Heterogenitätsindices anhand eines Dendrogramms.

Zusammenfassung

Die Clusteranalyse hat zum Ziel „ähnliche“ Objekte im Datensatz zu finden und diese dementsprechend in Gruppen (Cluster) zu ordnen. Diese Objekte sind Beobachtungseinheiten, von denen Messungen in mehreren Variablen vorhanden sind.

Zentrale Frage ist, wie „Abstand“ bzw. „Ähnlichkeit“ zwischen je zwei solcher Objekte definiert wird. Je nach Skalenniveau der Daten unterscheidet man zwischen Maßen, die die exakten Übereinstimmungen zählen oder Differenzen zwischen den einzelnen Komponenten der Beobachtungen messen. Zusätzlich muss jeweils ein Algorithmus gewählt werden, wie verschiedene Gruppierungen der Einheiten – Partitionen genannt – zu bewerten sind.

Die Gesamtzahl der Partitionen steigt rapide mit einem Zuwachs des Stichprobenumfangs. Daher ist es bereits bei Problemen mit moderaten Fallzahlen nicht möglich, alle möglichen Partitionen zu bewerten. Bei hierarchischen Verfahren werden verschiedene Partitionen schrittweise durch Verfeinerung bzw. Vergröberung erstellt. Hier wird nur ein sehr kleiner Bruchteil aller möglichen Partitionen bewertet. Bei partitionierenden Verfahren wird die Clusteranzahl festgelegt und dann ein Kriterium optimiert, das zumeist mit der Minimierung der Streuung der Datenpunkte innerhalb ihrer Cluster zu tun hat. Bei modellbasierten Verfahren verfolgt man einen stochastischen Ansatz.

Nachdem eine Partition gefunden ist, sind schließlich die gefundenen Gruppen auch zu charakterisieren und inhaltlich zu deuten.