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.
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:
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.[1]
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.
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.
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:
Weitere Schritte der Clusteranalyse:
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:
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 (kernel principal component analysis, kurz: kernel PCA)) ordnen jeden Datenpunkt genau einem Cluster zu, wohingegen bei weichen Methoden (z. B. EM-Algorithmus mit Gaußschen Mischmodellen (gaussian mixture models, 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).
Clusterverfahren lassen sich in graphentheoretische, hierarchische, partitionierende und optimierende Verfahren sowie in weitere Unterverfahren einteilen.
Zu beachten ist, dass man noch diverse weitere Verfahren und Algorithmen unterscheiden kann, unter anderem überwachte (supervised) und nicht-überwachte (unsupervised) Algorithmen oder modellbasierte Algorithmen, bei denen eine Annahme über die zugrundeliegende Verteilung der Daten gemacht wird (z. B. Gaussian mixture model).
Es sind eine Vielzahl von Clustering-Verfahren in den unterschiedlichsten Anwendungsgebieten entwickelt worden. Man kann folgende Verfahrenstypen unterscheiden:
Die ersten beiden Verfahrenstypen sind die klassischen Clusterverfahren, während die anderen Verfahren eher neueren Datums sind.
Die Gemeinsamkeit der partitionierenden Verfahren ist, dass zunächst die Zahl der Cluster k {\displaystyle k} festgelegt werden muss (Nachteil). Dann werden k {\displaystyle k} Clusterzentren bestimmt und diese iterativ so lange verschoben, bis sich die Zuordnung der Beobachtungen zu den k {\displaystyle k} Clusterzentren nicht mehr verändert, wobei eine vorgegebene Fehlerfunktion minimiert wird. Ein Vorteil ist, dass Objekte während der Verschiebung der Clusterzentren ihre Clusterzugehörigkeit wechseln können.
Als hierarchische Clusteranalyse bezeichnet man eine bestimmte Familie von distanzbasierten Verfahren zur Clusteranalyse. Cluster bestehen hierbei aus Objekten, die zueinander eine geringere Distanz (oder umgekehrt: höhere Ähnlichkeit) aufweisen als zu den Objekten anderer Cluster. Dabei wird eine Hierarchie von Clustern aufgebaut: auf der einen Seite ein Cluster, der alle Objekte enthält, und auf der anderen Seite so viele Cluster, wie man Objekte hat, d. h., jedes Cluster enthält genau ein Objekt. Man unterscheidet zwei wichtige Typen von Verfahren:
Für beide Verfahren gilt: einmal gebildete Cluster können nicht mehr verändert oder einzelne Objekte getauscht werden. Es wird die Struktur entweder stets nur verfeinert („divisiv“) oder nur verallgemeinert („agglomerativ“), sodass eine strikte Cluster-Hierarchie entsteht. An der entstandenen Hierarchie kann man nicht mehr erkennen, wie sie berechnet wurde.
Bei dichtebasiertem Clustering werden Cluster als Objekte in einem d-dimensionalen Raum betrachtet, die dicht beieinander liegen, getrennt durch Gebiete mit geringerer Dichte.
Bei gitterbasierten Clusterverfahren wird der Datenraum unabhängig von den Daten in endlich viele Zellen aufgeteilt. Der größte Vorteil dieses Ansatzes ist die geringe asymptotische Komplexität im Niedrigdimensionalen, da die Laufzeit von der Anzahl der Gitterzellen abhängt. Mit steigender Anzahl der Dimensionen wächst jedoch die Zahl der Gitterzellen exponentiell. Vertreter sind STING und CLIQUE. Zudem können Gitter zur Beschleunigung anderer Algorithmen eingesetzt werden, bspw. zur Approximation von k-means oder zur Berechnung von DBSCAN (GriDBSCAN).
In der Praxis werden oft auch Kombinationen von Verfahren benutzt. Ein Beispiel ist es erst eine hierarchische Clusteranalyse durchzuführen, um eine geeignete Clusterzahl zu bestimmen, und danach noch ein k-Means Clustering, um das Resultat des Clusterings zu verbessern. Oft lässt sich in speziellen Situation zusätzliche Information ausnutzen, sodass z. B. die Dimension oder die Anzahl der zu clusternden Objekte reduziert wird.
Biclustering, Co-Clustering oder Two-Mode Clustering ist eine Technik, die das gleichzeitige Clustering von Zeilen und Spalten einer Matrix ermöglicht. Zahlreiche Biclustering-Algorithmen wurden für die Bioinformatik entwickelt, darunter: Block Clustering, CTWC (Coupled Two-Way Clustering), ITWC (Interrelated Two-Way Clustering), δ-Bicluster, δ-pCluster, δ-Pattern, FLOC, OPC, Plaid Model, OPSMs (Order-preserving Submatrices), Gibbs, SAMBA (Statistical-Algorithmic Method for Bicluster Analysis), Robust Biclustering Algorithm (RoBA), Crossing Minimization, cMonkey, PRMs, DCC, LEB (Localize and Extract Biclusters), QUBIC (QUalitative BIClustering), BCCA (Bi-Correlation Clustering Algorithm) und FABIA (Factor Analysis for Bicluster Acquisition). Auch in anderen Anwendungsgebieten werden Biclustering-Algorithmen vorgeschlagen und eingesetzt. Dort sind sie unter den Bezeichnungen Co-Clustering, Bidimensional Clustering sowie Subspace Clustering zu finden.
Die Ergebnisse eines jeden Cluster-Verfahrens müssen wie bei allen Verfahren des maschinellen Lernens einer Evaluation unterzogen werden. Die Güte einer fertig berechneten Einteilung der Datenpunkte in Gruppen kann anhand verschiedener Metriken eingeschätzt werden. Die Auswahl einer geeigneten Metrik muss immer im Hinblick auf die verwendeten Daten, die vorgegebene Fragestellung sowie die gewählte Clustering-Methode erfolgen.
Es wird zwischen internen, externen und relativen Metriken unterschieden.[21] Interne Metriken bewerten die Cluster rein anhand des vorliegenden Datensatzes und dem internen Zusammenhang der Daten. Externe Metriken ziehen zusätzlich externe Daten (z. B. Experten Label) hinzu. Relative Metriken vergleichen die Ergebnisse zweier Cluster-Algorithmen.
Internen Validitätsmetriken haben den Vorteil, dass kein Wissen über die korrekte Zuordnung vorhanden sein muss, um das Ergebnis zu bewerten.
Zu den in der Praxis häufig verwendeten Evaluations-Kennzahlen gehört der 1987 von Peter J.Rousseeuw vorgestellte Silhouettenkoeffizient. Dieser berechnet pro Datenpunkt einen Wert, der angibt wie gut die Zuordnung zur gewählten Gruppe im Vergleich zu allen deren Gruppen erfolgt ist.[22] Mit einer Laufzeitkomplexität von O(n²) ist der Silhouettenkoeffizient aber langsamer als viele Clusterverfahren, und kann so nicht auf großen Daten verwendet werden.
Der Rand-Index kann zur Bewertung der Übereinstimmung gefundener Cluster mit einer Ground-Truth herangezogen werden (z. B. können Clusterzugehörtigkeiten explizit in der Laplace-Matrix oder der Adjazenzmatrix festgehalten werden). Beim Rand-Index handelt es sich um die Korrektklassifikationsrate für die Klassifikation „das Paar A und B tritt gemeinsam im Cluster auf“.
Lokasi Pengunjung: 18.116.27.63