Clusteranalyse

mini|Ergebnis einer Clusteranalyse mit Normalverteilungen

Unter Clusteranalyse (Clustering-Algorithmus, gelegentlich auch: Ballungsanalyse) versteht man ein Verfahren zur Entdeckung von Ähnlichkeitsstrukturen in (meist relativ großen) Datenbeständen. Die so gefundenen Gruppen von „ähnlichen“ Objekten werden als Cluster bezeichnet, die Gruppenzuordnung als Clustering. Die gefundenen Ähnlichkeitsgruppen können graphentheoretisch, hierarchisch, partitionierend oder optimierend sein. Die Clusteranalyse ist eine wichtige Disziplin des Data-Minings, des Analyseschritts des Knowledge-Discovery-in-Databases-Prozesses. Das Ziel der Clusteranalyse ist, neue Gruppen in den Daten zu identifizieren (im Gegensatz zur Klassifikation, bei der Daten bestehenden Klassen zugeordnet werden). Man spricht von einem „uninformierten Verfahren“, da es nicht auf Klassen-Vorwissen angewiesen ist. Diese neuen Gruppen können anschließend beispielsweise zur automatisierten Klassifizierung, zur Erkennung von Mustern in der Bildverarbeitung oder zur Marktsegmentierung eingesetzt werden (oder in beliebigen anderen Verfahren, die auf ein derartiges Vorwissen angewiesen sind).

Die zahlreichen Algorithmen unterscheiden sich vor allem in ihrem Ähnlichkeits- und Gruppenbegriff, ihrem Cluster-Modell, ihrem algorithmischen Vorgehen (und damit ihrer Komplexität) und der Toleranz gegenüber Störungen in den Daten. Ob das von einem solchen Algorithmus generierte „Wissen“ nützlich ist, kann jedoch in der Regel nur ein Experte beurteilen. Ein Clustering-Algorithmus kann unter Umständen vorhandenes Wissen reproduzieren (beispielsweise Personendaten in die bekannten Gruppen „männlich“ und „weiblich“ unterteilen) oder auch für den Anwendungszweck nicht hilfreiche Gruppen generieren. Die gefundenen Gruppen lassen sich oft auch nicht verbal beschreiben (anders als z. B. bei „männliche Personen“), gemeinsame Eigenschaften werden in der Regel erst durch eine nachträgliche Analyse identifiziert. Bei der Anwendung von Clusteranalyse ist es daher oft notwendig, verschiedene Verfahren und verschiedene Parameter abzufragen, die Daten vorzuverarbeiten und beispielsweise Attribute auszuwählen oder wegzulassen.

Beispiel

Angewendet auf einen Datensatz von Fahrzeugen könnte ein Clustering-Algorithmus (und eine nachträgliche Analyse der gefundenen Gruppen) beispielsweise folgende Struktur liefern:

Dabei ist Folgendes zu beachten: Der Algorithmus selbst liefert keine Interpretation („LKW“) der gefundenen Gruppen. Hierzu ist eine separate Analyse der Gruppen notwendig. Ein Mensch würde eine Fahrradrikscha als Untergruppe der Fahrräder ansehen. Für einen Clustering-Algorithmus aber sind 3 Räder oft ein signifikanter Unterschied, den sie mit einem Dreirad-Rollermobil teilen. Die Gruppen sind oft nicht „rein“, es können also beispielsweise kleine LKW in der Gruppe der PKW sein. Es treten oft zusätzliche Gruppen auf, die nicht erwartet wurden („Polizeiautos“, „Cabrios“, „rote Autos“, „Autos mit Xenon-Scheinwerfern“). Manche Gruppen werden nicht gefunden, beispielsweise „Motorräder“ oder „Liegeräder“. Welche Gruppen gefunden werden, hängt stark vom verwendeten Algorithmus sowie von den Parametern und verwendeten Objekt-Attributen ab. Oft wird auch nichts (Sinnvolles) gefunden. In diesem Beispiel wurde nur bekanntes Wissen (wieder-)gefunden – als Verfahren zur „Wissensentdeckung“ ist die Clusteranalyse hier also gescheitert.

Geschichte Historisch gesehen stammt das Verfahren aus der Taxonomie in der Biologie, wo über eine Clusterung von verwandten Arten eine Ordnung der Lebewesen ermittelt wird. Allerdings wurden dort ursprünglich keine automatischen Berechnungsverfahren eingesetzt. Inzwischen können zur Bestimmung der Verwandtschaft von Organismen unter anderem ihre Gensequenzen verglichen werden (Siehe auch: Kladistik). Später wurde das Verfahren für die Zusammenhangsanalyse in die Sozialwissenschaften eingeführt, weil es sich wegen des in den Gesellschaftswissenschaften in der Regel niedrigen Skalenniveaus der Daten in diesen Disziplinen besonders eignet.Vgl. unter anderem

Prinzip/Funktionsweise Mathematische Modellierung Die Eigenschaften der zu untersuchenden Objekte werden mathematisch als Zufallsvariablen aufgefasst. Sie werden in der Regel in Form von Vektoren als Punkte in einem Vektorraum dargestellt, deren Dimensionen die Eigenschaftsausprägungen des Objekts bilden. Bereiche, in denen sich Punkte anhäufen (Punktwolke), werden Cluster genannt. Bei Streudiagrammen dienen die Abstände der Punkte zueinander oder die Varianz innerhalb eines Clusters als sogenannte Proximitätsmaße, welche die Ähnlichkeit bzw. Unterschiedlichkeit zwischen den Objekten zum Ausdruck bringen.

Ein Cluster kann auch als eine Gruppe von Objekten definiert werden, die in Bezug auf einen berechneten Schwerpunkt eine minimale Abstandssumme haben. Dazu ist die Wahl eines Distanzmaßes erforderlich. In bestimmten Fällen sind die Abstände (bzw. umgekehrt die Ähnlichkeiten) der Objekte untereinander direkt bekannt, sodass sie nicht aus der Darstellung im Vektorraum ermittelt werden müssen.

Grundsätzliche Vorgehensweise In einer Gesamtmenge/-gruppe mit unterschiedlichen Objekten werden die Objekte, die sich ähnlich sind, zu Gruppen (Clustern) zusammengefasst.

Als Beispiel sei folgende Musikanalyse gegeben. Die Werte ergeben sich aus dem Anteil der Musikstücke, die der Nutzer pro Monat online kauft. Person 1 Person 2 Person 3 Pop 2 1 8 Rock 10 8 1 Jazz 3 3 1

In diesem Beispiel würde man die Personen intuitiv in zwei Gruppen einteilen. Gruppe 1 besteht aus Person 1&2 und Gruppe 2 besteht aus Person 3. Das würden auch die meisten Clusteralgorithmen machen. Dieses Beispiel ist lediglich aufgrund der gewählten Werte so eindeutig, spätestens mit näher zusammenliegenden Werten und mehr Variablen (hier Musikrichtungen) und Objekten (hier Personen) ist leicht vorstellbar, dass die Einteilung in Gruppen nicht mehr so trivial ist.

Etwas genauer und abstrakter ausgedrückt: Die Objekte einer heterogenen (beschrieben durch unterschiedliche Werte ihrer Variablen) Gesamtmenge werden mit Hilfe der Clusteranalyse zu Teilgruppen (Clustern/Segmenten) zusammengefasst, die in sich möglichst homogen (die Unterschiede der Variablen möglichst gering) sind. In unserem Musikbeispiel kann die Gruppe aller Musikhörer (eine sehr heterogene Gruppe) in die Gruppen der Jazzhörer, Rockhörer, Pophörer etc. (jeweils relativ homogen) unterteilt werden bzw. werden die Hörer mit ähnlichen Präferenzen zu der entsprechenden Gruppe zusammengefasst.

Eine Clusteranalyse (z. B. bei der Marktsegmentierung) erfolgt dabei in folgenden Schritten:

Schritte zur Clusterbildung: Variablenauswahl: Auswahl (und Erhebung) der für die Untersuchung geeigneten Variablen. Sofern die Variablen der Objekte/Elemente noch nicht bekannt/vorgegeben sind, müssen alle für die Untersuchung wichtigen Variablen bestimmt und anschließend ermittelt werden. Proximitätsbestimmung: Wahl eines geeigneten Proximitätsmaßes und Bestimmung der Distanz- bzw. Ähnlichkeitswerte (je nach Proximitätsmaß) zwischen den Objekten über das Proximitätsmaß. Abhängig von der Art der Variablen bzw. der Skalenart der Variablen wird eine entsprechende Distanzfunktion zur Bestimmung des Abstandes (Distanz) zweier Elemente oder eine Ähnlichkeitsfunktion zur Bestimmung der Ähnlichkeit verwendet. Die Variablen werden zunächst einzeln verglichen und aus der Distanz der einzelnen Variablen die Gesamtdistanz (oder Ähnlichkeit) berechnet. Die Funktion zur Bestimmung von Distanz oder Ähnlichkeit wird auch Proximitätsmaß genannt. Der durch ein Proximitätsmaß ermittelte Distanz- bzw. Ähnlichkeitswert nennt sich Proximität. Werden alle Objekte miteinander verglichen, ergibt sich eine Proximitätsmatrix, die jeweils zwei Objekten eine Proximität zuweist. Clusterbildung: Bestimmung und Durchführung eines/der geeigneten Clusterverfahren(s), um anschließend mit Hilfe des/dieser Verfahren(s) Gruppen/Cluster bilden zu können (die Proximitätsmatrix wird hierdurch reduziert). Im Regelfall werden hierbei mehrere Verfahren kombiniert, z. B.: Finden von Ausreißern durch das Single-Linkage-Verfahren (hierarchisches Verfahren) Bestimmung der Clusterzahl durch das Ward-Verfahren (hierarchisches Verfahren) Bestimmung der Clusterzusammensetzung durch das Austauschverfahren (partitionierendes Verfahren)

Weitere Schritte der Clusteranalyse: Bestimmung der Clusterzahl durch Betrachtung der Varianz innerhalb und zwischen den Gruppen. Hier wird bestimmt, wie viele Gruppen tatsächlich gebildet werden, denn bei der Clusterung selbst ist keine Abbruchbedingung vorgegeben. Z. B. wird bei einem agglomerativen Verfahren folglich so lange fusioniert, bis nur noch eine Gesamtgruppe vorhanden ist. Interpretation der Cluster (abhängig von den inhaltlichen Ergebnissen, z. B. durch t-Wert) Beurteilung der Güte der Clusterlösung (Bestimmung der Trennschärfe der Variablen, Gruppenstabilität)

Unterschiedliche Proximitätsmaße/Skalen Die Skalen bezeichnen den Wertebereich, den die betrachtete(n) Variable(n) des Objektes annehmen kann/können. Je nachdem, welche Art von Skala vorliegt, muss man ein passendes Proximitätsmaß verwenden. Es gibt drei Hauptkategorien von Skalen:

Binäre SkalenDie Variable kann zwei Werte annehmen, z. B. 0 oder 1, männlich oder weiblich.Verwendete Proximitätsmaße (Beispiele): Jaccard-Koeffizient (Ähnlichkeitsmaß) Lance-Williams-Maß (Distanzmaß) Nominale SkalenDie Variable kann unterschiedliche Werte annehmen, um eine qualitative Unterscheidung zu treffen, z. B., ob Pop, Rock oder Jazz bevorzugt wird.Verwendete Proximitätsmaße (Beispiele): Chi-Quadrat-Maß (Distanzmaß) Phi-Quadrat-Maß (Distanzmaß) Metrische SkalenDie Variable nimmt einen Wert auf einer vorher festgelegten Skala ein, um eine quantitative Aussage zu treffen, z. B., wie gerne eine Person Pop auf einer Skala von 1 bis 10 hört.Verwendete Proximitätsmaße (Beispiele): Pearson-Korrelationskoeffizient (Ähnlichkeitsmaß) Euklidische Metrik (Distanzmaß) Minkowski-Metrik (Distanzmaß)

Formen der Gruppenbildung (Gruppenzugehörigkeit)

Es sind drei unterschiedliche Formen der Gruppenbildung (Gruppenzugehörigkeit) möglich. Bei den überlappenden Gruppen kann ein Objekt mehreren Gruppen zugeordnet werden, bei den nicht überlappenden Gruppen hingegen wird jedes Objekt nur einer einzelnen Gruppe (Segment, Cluster) zugeordnet. In den Fuzzy-Gruppen gehört ein Element jeder Gruppe mit einem bestimmten Grad des Zutreffens an.

Man unterscheidet zwischen „harten“ und „weichen“ Clustering-Algorithmen. Harte Methoden (z. B. k-means, Spektrales Clustering, Kernbasierte Hauptkomponentenanalyse (, kurz: kernel PCA)) ordnen jeden Datenpunkt genau einem Cluster zu, wohingegen bei weichen Methoden (z. B. EM-Algorithmus mit Gaußschen Mischmodellen (, kurz: GMMs)) jedem Datenpunkt für jeden Cluster ein Grad zugeordnet wird, mit der dieser Datenpunkt in diesem Cluster zugeordnet werden kann. Weiche Methoden sind insbesondere dann nützlich, wenn die Datenpunkte relativ homogen im Raum verteilt sind und die Cluster nur als Regionen mit erhöhter Datenpunktdichte in Erscheinung treten, d. h., wenn es z. B. fließende Übergänge zwischen den Clustern oder Hintergrundrauschen gibt (harte Methoden sind in diesem Fall unbrauchbar).

Unterscheidung der Clusterverfahren Clusterverfahren lassen sich in graphentheoretische, hierarchische, partitionierende und optimierende Verfahren sowie in weitere Unterverfahren einteilen.

Partitionierende Verfahren verwenden eine gegebene Partitionierung und ordnen die Elemente durch Austauschfunktionen um, bis die verwendete Zielfunktion ein Optimum erreicht. Zusätzliche Gruppen können jedoch nicht gebildet werden, da die Anzahl der Cluster bereits am Anfang festgelegt wird (vgl. hierarchische Verfahren).