Clusteranalyse [von E cluster = Haufen, Klumpen],Ecluster analysis, Sammelbezeichnung für eine große Anzahl verschiedener Techniken der Explorativen Datenanalyse (EDA). Eine generelle Fragestellung in fast allen Bereichen der Datenanalyse besteht dabei in dem Finden und Einteilen der beobachteten Daten in bedeutungsvolle Strukturen. Z.B. müssen Tierarten erst in verschiedene Untergruppen eingeteilt werden, bevor eine sinnvolle Beschreibung der Unterschiede zwischen den Arten möglich ist. Allen Clusteranalysemethoden gemein ist die Zielsetzung, ähnliche Objekte zusammen zu gruppieren, wobei die Objekte innerhalb einer Klasse möglichst homogen und die Klassen untereinander möglichst heterogen sind. Alle Clusteranalysestudien lassen sich in fünf Schritte einteilen: 1) Auswahl der zu clusternden Daten, 2) Bestimmung der Merkmale mit denen die einzelnen Entitäten beschrieben werden, 3) Berechnung der Ähnlichkeiten zwischen den einzelnen Entitäten, 4) Verwendung einer Clusteranalysemethode zur Generierung von Gruppen mit ähnlichen Entitäten, 5) Validierung der gefundenen Clusterung. – Die Verfahren der Clusteranalyse unterscheiden sich hinsichtlich ihrer a-priori gemachten Annahmen über Ähnlichkeit und Disjunktivität der Klassen sowie deren Anzahl. Bei allen Clusterverfahren ist jedoch zu beachten, daß sie selten eine ausgeprägte statistische Basis besitzen. Die Verfahren sind meist heuristischer Natur und beeinflußt von der jeweiligen Forschungsrichtung, in der sie sich entwickelt haben. Ebenso gilt, daß verschiedene Clustermethoden verschiedene Lösungen aus den gleichen Datensätzen generieren können; obwohl Clusteranalysemethoden nach Struktur in Daten suchen, wird auch gleichzeitig Struktur aufgeprägt, und zwar über die Art und Weise, wie gesucht wird. Somit wird zwar jede Clustermethodik die Entitäten in Gruppen einteilen, diese können jedoch drastisch verschieden sein. Die Schwierigkeit besteht nun darin, zu wissen, wann die gefundene Gruppeneinteilung wirklich ist und wann sie nur durch die Methode aufgeprägt wird. – Es können drei Verfahrensfamilien unterschieden werden: Hierarchische Clusterung, k-means Clusterung und graphentheoretische Clusterverfahren. Graphentheoretische Verfahren eignen sich für Distanzdaten, deren Cluster schlecht durch Mittelpunkte charakterisiert werden können. Die hierarchische Clusterung und die k-means Clusterung werden nun eingehender betrachtet. Die hierarchischen Verfahren gehen im allgemeinen von Ähnlichkeits- oder Distanzdaten aus. Dabei existieren eine Fülle von Distanz- oder Ähnlichkeitsmaßen, z.B. die euklidische Distanz der Merkmalspunkte im n-dimensionalen Raum oder die Hamming-Distanz für binäre Muster. Ausgehend von solchen Maßen wird ein Inhomogenitätsmaß für die Cluster definiert, z.B. die maximale Distanz von Entitäten in einer Gruppe oder die Größe der Varianz innerhalb eines Clusters. Bei den hierarchischen Verfahren werden dann sukzessive Objektklassen zusammengefaßt oder partitioniert ( siehe Abb. 1 ), so daß das jeweilige Inhomogenitätsmaß von allen Klassen nicht überschritten wird (schwarze Linie in der Abbildung). Bei der k-means Clusteranalyse wird mit einer zufälligen Initialisierung von k Clustern begonnen. Die jeweiligen Cluster werden über die nächste Nachbarschaft der Objekte zu k Zentren (Prototypen) bestimmt ( siehe Abb. 2 ). Die Zentren oder die Zugehörigkeit eines Objekts zu einem Cluster werden nun mit dem Ziel geändert, daß die Variabilität innerhalb der Clusters minimal ist und der Unterschied zwischen den Clustern maximal wird. Das Ändern der Zentren wird in Abb. 2 dargestellt. Durch das Bewegen der Zentren ändern sich die Zugehörigkeiten der Datenpunkte zu den Clustern (weiß, grau und schwarz markiert). – Die Clusteranalyse ist im Ergebnis ein datenreduzierendes Verfahren; am deutlichsten wird dies bei der k-means Clusteranalyse, in dem statt eines n-dimensionalen Datenvektors ein Skalar, die Angabe des Clusters, zu dem das betreffende Muster gehört, verwendet wird. Die Clusteranalyse wird in der Mustererkennung häufig zur Musterraumdiskretisierung verwendet, man spricht dabei auch von Vektorquantisierung. Ebenso können die von einer k-means Clusteranalyse gefundenen Zentren zur Initialisierung von Radial-Basis-Funktions-Netzen verwendet werden. Für die Clusteranalyse existieren auch Ansätze aus dem Bereich "neurocomputing", wie z.B. die self-organizing feature map von Kohonen.

Lit.:Aldenderfer, M.S., Blashfield, R.K.: Cluster Analysis, Sage Publications, 1984. Backer, E: Computer-Assisted Reasoning in Cluster Analysis, Prentice Hall, 1995. Bacher, J: Clusteranalyse, Oldenbourg, 1996.

Clusteranalyse

Abb. 1: Hierarchische Clusteranalyse. Sukzessives Partitionieren (bzw. Zusammenfassen) von Objektklassen.

Clusteranalyse

Abb. 2: k-means Clusterung. Die Repräsentanten (Zentren, Prototypen) bewegen sich in die Datenwolken und ändern die Klassenzugehörigkeit der Datenpunkte (a-c).