Wikipedia · einfach zusammengefasst · Stand
Clusteranalyse
Unter Clusteranalyse (Clustering-Algorithmus, gelegentlich auch: Ballungsanalyse) versteht man ein Verfahren zur Entdeckung von Ähnlichkeitsstrukturen in …
Inhalt6 Abschnitte
Begriff, Ziel und Bedeutung
Die Clusteranalyse, auch Clustering-Algorithmus oder gelegentlich Ballungsanalyse genannt, ist ein Verfahren zur Entdeckung von Ähnlichkeitsstrukturen in meist großen Datenbeständen. Gruppen ähnlicher Objekte heißen Cluster; ihre Zuordnung zu Gruppen heißt Clustering. Anders als bei der Klassifikation werden die Daten nicht bereits bekannten Klassen zugeordnet. Stattdessen sollen neue Gruppen erkannt werden. Deshalb gilt die Clusteranalyse als „uninformiertes Verfahren“, das kein Vorwissen über Klassen benötigt.
Clusteranalyse ist eine wichtige Disziplin des Data-Minings im Knowledge-Discovery-in-Databases-Prozess. Ihre Ergebnisse können unter anderem zur späteren automatisierten Klassifizierung, zur Mustererkennung in der Bildverarbeitung oder zur Marktsegmentierung dienen.
Ob ein Ergebnis tatsächlich nützlich ist, kann meist nur ein Experte beurteilen. Ein Algorithmus kann lediglich schon bekanntes Wissen reproduzieren, unerwartete oder für den Zweck ungeeignete Gruppen bilden oder gar keine sinnvolle Struktur finden. Außerdem benennt und erklärt er seine Cluster nicht selbst. Gemeinsame Eigenschaften müssen nachträglich untersucht werden. Deshalb werden in der Praxis häufig verschiedene Algorithmen und Parameter ausprobiert sowie Daten vorverarbeitet, etwa durch Auswahl oder Weglassen bestimmter Attribute.
Mathematisches Modell und Arbeitsablauf
Die Eigenschaften der untersuchten Objekte werden mathematisch als Zufallsvariablen aufgefasst. Meist wird jedes Objekt als Vektor und damit als Punkt in einem Vektorraum dargestellt; dessen Dimensionen entsprechen den Eigenschaftsausprägungen. Häufen sich Punkte in bestimmten Bereichen zu Punktwolken, können diese Bereiche als Cluster verstanden werden.
Ein Proximitätsmaß beschreibt die Ähnlichkeit oder Unterschiedlichkeit zweier Objekte. Dazu dienen beispielsweise Abstände zwischen Punkten oder die Varianz innerhalb eines Clusters. Ein Cluster kann auch als Objektgruppe definiert werden, deren Abstandssumme zu einem berechneten Schwerpunkt minimal ist. Dafür muss ein geeignetes Distanzmaß gewählt werden. Sind Abstände oder Ähnlichkeiten direkt bekannt, müssen sie nicht erst aus einem Vektorraum berechnet werden.
Das Ziel besteht darin, eine heterogene Gesamtmenge in Teilgruppen zu zerlegen, die in sich möglichst homogen sind. Der typische Ablauf umfasst:
• Variablenauswahl: Für die Fragestellung geeignete Eigenschaften werden bestimmt und erhoben.
• Proximitätsbestimmung: Ein passendes Distanz- oder Ähnlichkeitsmaß wird gewählt. Zunächst werden einzelne Variablen verglichen; daraus entsteht eine Gesamtdistanz oder Gesamtähnlichkeit. Der berechnete Wert heißt Proximität. Der Vergleich aller Objektpaare ergibt eine Proximitätsmatrix.
• Clusterbildung: Ein oder mehrere Clusterverfahren werden ausgewählt und angewendet. Häufig werden Verfahren kombiniert, etwa Single Linkage zum Finden von Ausreißern, die Ward-Methode zur Bestimmung der Clusterzahl und ein Austauschverfahren zur Festlegung der Clusterzusammensetzung.
• Nachbearbeitung: Die Zahl der Cluster wird beispielsweise anhand der Varianz innerhalb und zwischen den Gruppen festgelegt. Anschließend werden die Cluster interpretiert und hinsichtlich Trennschärfe der Variablen und Gruppenstabilität beurteilt.
Das geeignete Proximitätsmaß hängt vom Skalenniveau ab. Binäre Variablen besitzen zwei Werte, etwa 0 und 1; mögliche Maße sind der Jaccard-Koeffizient als Ähnlichkeitsmaß und das Lance-Williams-Maß als Distanzmaß. Nominale Variablen unterscheiden qualitative Kategorien wie Pop, Rock und Jazz; Beispiele sind Chi-Quadrat- und Phi-Quadrat-Maß. Metrische Variablen liefern quantitative Werte auf einer Skala; hierfür eignen sich unter anderem Pearson-Korrelationskoeffizient, euklidische Metrik und Minkowski-Metrik.
Gruppenzugehörigkeit und grundlegende Verfahrensarten
Gruppen können nicht überlappend, überlappend oder unscharf sein. Bei nicht überlappenden Gruppen gehört jedes Objekt genau einem Cluster an. Bei überlappenden Gruppen darf es mehreren Clustern angehören. In Fuzzy-Gruppen besitzt es für jede Gruppe einen bestimmten Zugehörigkeitsgrad.
Entsprechend unterscheidet man harte und weiche Algorithmen. Harte Verfahren wie k-Means, spektrales Clustering und kernel PCA ordnen jeden Datenpunkt genau einem Cluster zu. Weiche Verfahren wie der EM-Algorithmus mit Gaußschen Mischmodellen weisen einem Punkt für jedes Cluster einen Grad oder eine Wahrscheinlichkeit zu. Sie sind besonders geeignet, wenn Cluster nur als Regionen erhöhter Punktdichte erscheinen, fließend ineinander übergehen oder von Hintergrundrauschen begleitet werden.
Clusterverfahren werden unter anderem als graphentheoretisch, hierarchisch, partitionierend oder optimierend eingeordnet; der Artikel kennzeichnet diese Klassifikation allerdings als überarbeitungsbedürftig. Partitionierende Verfahren beginnen mit einer festgelegten Zahl von Gruppen und ordnen Elemente durch Austausch um, bis eine Zielfunktion ein Optimum erreicht. Hierarchische Verfahren bauen dagegen schrittweise eine verschachtelte Gruppenstruktur auf. Daneben nennt der Artikel überwachte und nicht überwachte sowie modellbasierte Algorithmen, die eine bestimmte Verteilung der Daten voraussetzen, etwa ein Gaussian Mixture Model.
Partitionierende und hierarchische Verfahren
Bei partitionierenden Verfahren muss die Clusterzahl k zunächst festgelegt werden. Danach werden k Clusterzentren bestimmt und iterativ verschoben, bis sich die Zuordnung der Beobachtungen nicht mehr ändert; dabei wird eine Fehlerfunktion minimiert. Ein Vorteil ist, dass Objekte während dieses Vorgangs ihr Cluster wechseln können.
• k-Means minimiert die Summe der quadrierten euklidischen Abstände zum jeweils nächsten Zentrum. Ein Zentrum wird als Mittelwert aller Objekte seines Clusters aktualisiert. Das Verfahren nimmt ungefähr gleich große Cluster an und trennt dichtebasierte Formen nicht gut.
• k-Means++ wählt anfängliche Zentren zufällig so aus, dass sie ungefähr gleichmäßig im Objektraum verteilt sind, und beschleunigt dadurch den Algorithmus.
• k-Median minimiert Manhattan-Distanzen und aktualisiert Zentren über den Median. Dadurch wirken sich Ausreißer weniger stark aus.
• k-Medoids beziehungsweise Partitioning Around Medoids (PAM) verwendet tatsächliche Objekte als Zentren. Benötigt werden nur die Distanzen zwischen Objekten, nicht deren Koordinaten.
• Fuzzy-c-Means berechnet Zugehörigkeitsgrade, häufig aus [0,1]. Je größer der Abstand zum Zentrum, desto kleiner ist der Grad und desto geringer der Einfluss auf dessen Verschiebung.
• EM-Clustering modelliert k multivariate Normalverteilungen und schätzt mit dem EM-Algorithmus iterativ deren unbekannte Parameter μᵢ und Σᵢ für i = 1,…,k. Jedes Objekt gehört jedem Cluster mit einer gewissen Wahrscheinlichkeit an. Normalverteilte Cluster lassen sich gut erkennen, nicht konvexe Cluster dagegen nicht.
• Affinity-Propagation ist ein deterministischer Message-Passing-Algorithmus, der Clusterzentren automatisch findet. Er berechnet Responsibility und Availability sowie deren Summe; ein Dämpfungsfaktor soll numerische Instabilitäten vermeiden. Die gefundene Clusterzahl hängt jedoch von Dämpfung und Selbstähnlichkeit ab und muss nicht optimal sein.
Hierarchische Verfahren erzeugen eine Hierarchie zwischen den Extremen „ein Cluster mit allen Objekten“ und „für jedes Objekt ein eigenes Cluster“. Divisive Top-down-Verfahren beginnen mit einem Gesamtcluster und teilen ihn immer weiter. DIANA spaltet jeweils den Cluster mit dem größten Durchmesser: Ausgangspunkt des Splitterclusters ist das Objekt mit der größten mittleren Distanz zu den übrigen Objekten.
Agglomerative Bottom-up-Verfahren beginnen mit Einzelobjekten und vereinigen Cluster schrittweise. Bei Single Linkage werden die Cluster zusammengeführt, deren nächste Objekte die kleinste Distanz besitzen. Der Single-Link-Effekt kann jedoch dazu führen, dass große Cluster erst sehr spät getrennt erscheinen. Die Ward-Methode fusioniert die Cluster mit dem kleinsten Zuwachs der totalen Varianz. Einmal gebildete hierarchische Cluster können nicht mehr verändert und einzelne Objekte nicht ausgetauscht werden.
Dichte-, Gitter- und kombinierte Verfahren
Dichtebasierte Verfahren verstehen Cluster als dichte Punktgebiete in einem d-dimensionalen Raum, die durch Bereiche geringerer Dichte getrennt sind. Bei DBSCAN sind Objekte Kernobjekte, wenn in einem Abstand ε mindestens k weitere Objekte liegen. Kernobjekte mit einem Abstand kleiner als ε gehören zum selben Cluster. Nahe Nicht-Kern-Objekte werden als Randobjekte aufgenommen; alle übrigen gelten als Rauschobjekte. Da DBSCAN nur einen Dichte-Schwellwert verwendet, kann es benachbarte Cluster nicht immer gut trennen. OPTICS erweitert DBSCAN für verschieden dichte Cluster und verringert die Bedeutung der Wahl von ε. Maximum-Margin-Clustering sucht leere Bereiche zwischen Clustern und leitet daraus Grenzen ab; die Technik ist eng mit Support-Vektor-Maschinen verbunden.
Gitterbasierte Verfahren teilen den Datenraum unabhängig von den Daten in endlich viele Zellen. In wenigen Dimensionen ist ihre asymptotische Komplexität gering, weil die Laufzeit von der Zahl der Zellen abhängt. Mit jeder zusätzlichen Dimension wächst diese Zahl jedoch exponentiell. STING teilt den Raum rekursiv in rechteckige Zellen, berechnet statistische Informationen auf der untersten Ebene vor und ermittelt relevante Zellen top-down. CLIQUE sucht zunächst dicht besetzte d-dimensionale Zellen und verbindet sie anschließend mit einer Greedy-Strategie zu möglichst großen Regionen. Gitter können auch k-Means approximieren oder DBSCAN beschleunigen, etwa bei GriDBSCAN.
Kombinierte Verfahren nutzen die Stärken mehrerer Ansätze. Beispielsweise kann zunächst hierarchisch eine geeignete Clusterzahl bestimmt und das Ergebnis danach mit k-Means verbessert werden. Beim spektralen Clustering werden Objekte als Graphknoten und Distanzen oder Unähnlichkeiten als gewichtete Kanten dargestellt. Besitzt der Graph k Zusammenhangskomponenten, hat die Laplace-Matrix den Eigenwert Null mit Vielfachheit k. Untersucht werden deshalb die k kleinsten Eigenwerte und der zugehörige k-dimensionale Eigenraum; dort kann anschließend etwa k-Means eingesetzt werden.
Multiview-Clustering verarbeitet mehrere Distanz- oder Ähnlichkeitsmatrizen, etwa bei Webseiten eine Matrix gemeinsamer Wörter und eine zweite der Verlinkungen. Die Ergebnisse eines Schritts dienen jeweils dem nächsten, bis die Zuordnung stabil bleibt. BIRCH führt für sehr große Datensätze ein Preclustering durch und clustert anschließend die entstandenen Gruppen weiter; darauf basiert das in SPSS verwendete Two-Step Clustering.
Biclustering, Co-Clustering oder Two-Mode Clustering gruppiert gleichzeitig Zeilen und Spalten einer Matrix. Solche Verfahren wurden besonders für die Bioinformatik entwickelt, werden aber auch als Bidimensional Clustering oder Subspace Clustering in anderen Gebieten eingesetzt.
Beispiele, Grenzen und Bewertung
In einem Musikbeispiel werden monatliche Kaufanteile betrachtet: Person 1 hat für Pop, Rock und Jazz die Werte 2, 10 und 3; Person 2 die Werte 1, 8 und 3; Person 3 die Werte 8, 1 und 1. Wegen ihrer ähnlichen Präferenzen bilden Person 1 und 2 intuitiv eine Gruppe, Person 3 eine zweite. Bei näher zusammenliegenden Werten, mehr Musikrichtungen und mehr Personen wäre die Einteilung deutlich weniger eindeutig.
Das Fahrzeugbeispiel zeigt typische Grenzen. Ein Algorithmus liefert Gruppen, aber keine Bezeichnungen wie „LKW“ oder „PKW“. Eine Fahrradrikscha könnte wegen ihrer drei Räder eher mit einem dreirädrigen Rollermobil als mit Fahrrädern gruppiert werden. Kleine LKW könnten im PKW-Cluster landen; unerwartete Gruppen wie rote Autos oder Polizeiautos könnten entstehen, während Motorräder unentdeckt bleiben. Das Ergebnis hängt stark von Algorithmus, Parametern und ausgewählten Attributen ab. Wird nur bekanntes Wissen wiedergefunden, ist das Ziel der Wissensentdeckung nicht erreicht.
Jede Clusterlösung muss evaluiert werden. Die passende Metrik richtet sich nach Daten, Fragestellung und Verfahren. Interne Metriken bewerten nur den Datensatz und seine innere Struktur. Externe Metriken beziehen zusätzliche Informationen wie Experten-Labels ein. Relative Metriken vergleichen die Ergebnisse zweier Clusteralgorithmen.
Der 1987 von Peter J. Rousseeuw vorgestellte Silhouettenkoeffizient ist eine häufig verwendete interne Kennzahl. Er gibt für jeden Datenpunkt an, wie gut dessen Zuordnung zur gewählten Gruppe im Vergleich zu den anderen Gruppen ist. Seine Laufzeitkomplexität beträgt O(n²), weshalb er für große Datenbestände zu langsam sein kann.
Der Rand-Index ist eine externe Metrik zum Vergleich gefundener Cluster mit einer Ground-Truth, also einer als korrekt angenommenen Zuordnung. Er entspricht der Korrektklassifikationsrate für die Aussage, ob ein Objektpaar A und B gemeinsam in einem Cluster auftritt. Als weitere externe Metriken nennt der Artikel den Matthews-Korrelationskoeffizienten und Mutual Information, erläutert sie jedoch nicht näher.
