Cluster (Datenanalyse)

Grundidee und Begriffe

Ein Cluster ist in Informatik und Statistik eine Gruppe von Datenobjekten mit ähnlichen Eigenschaften. Die Objekte innerhalb eines Clusters sollen sich also ähneln und sich zugleich von Objekten außerhalb des Clusters unterscheiden. Das Zuordnen von Daten zu den in einem Datensatz gefundenen Gruppen heißt Clustering; Verfahren zum Auffinden solcher Gruppen heißen Clusteranalyse.

Datenobjekte, die zu keinem Cluster gehören, werden Ausreißer (englisch „outlier“) oder Rauschen (englisch „noise“) genannt. Welche Gruppen als Cluster gelten, hängt vom jeweils verwendeten Verfahren und seinem Cluster-Modell ab.

Arten der Clusterzugehörigkeit

Bei hartem Clustering gehört jedes Datenobjekt entweder vollständig zu einem Cluster oder gar nicht. Bei weichem Clustering gehört ein Objekt zu einem bestimmten Anteil zu einem Cluster.

Beim strikt partitionierenden Clustering gehört jedes Objekt genau einem Cluster an. Eine Variante mit Ausreißern erlaubt auch, dass ein Objekt keinem Cluster angehört; bei weichem Clustering können sich seine Anteile dann zu weniger als 1 summieren. Beim überlappenden Clustering darf ein Objekt mehreren Clustern angehören; bei weichem Clustering können sich die Anteile dabei zu mehr als 1 summieren.

Hierarchische Cluster enthalten zusätzlich Untergruppen, deren Objekte einander ähnlicher sind als dem übrigen Teil der größeren Gruppe. Verfahren, die solche Strukturen finden können, sind die Hierarchische Clusteranalyse, OPTICS und BIRCH.

Cluster-Modelle und Verfahren

Clusteranalyse-Algorithmen verwenden unterschiedliche Vorstellungen davon, was ein Cluster ist. Deshalb müssen Ergebnisse verschiedener Verfahren nicht im Sinne des jeweils anderen Verfahrens ähnlich sein.

Der k-Means-Algorithmus beschreibt Cluster durch ihre Mittelpunkte und die daraus entstehenden Voronoi-Zellen. Der EM-Algorithmus beschreibt sie durch Mittelpunkt und Kovarianzmatrix. Eine Kovarianzmatrix erfasst dabei die Streuung und Beziehungen der Merkmale. DBSCAN bestimmt dagegen dichte-verbundene Mengen beliebiger Form als Cluster.

Das gewählte Modell entscheidet, welche Datenstrukturen gefunden werden können. Bei Daten, die durch eine Normalverteilung erzeugt wurden, kann der EM-Algorithmus unterschiedliche Normalverteilungen wegen der verwendeten Varianzen akkurat beschreiben. k-Means kann dieselben Cluster wegen seiner Voronoi-Zellen in ungünstige Bereiche aufteilen und sie daher nicht akkurat finden.

Es gibt zahlreiche Clusteranalyse-Algorithmen. Bei klassischen Verfahren wie k-Means, EM, hierarchischer Clusteranalyse und DBSCAN steht meist ein Cluster-Modell im Mittelpunkt. Für ein Modell existieren teils mehrere konkrete Algorithmen, die eine zumindest lokal optimale Lösung suchen. Viele neuere Verfahren besitzen dagegen kein entsprechend klar definiertes Modell mehr.

Subspace-Cluster

Ein Subspace-Cluster fällt nicht in allen Attributen oder Attributkombinationen auf. Die stärkere Ähnlichkeit seiner Objekte wird erst sichtbar, wenn die Daten geeignet projiziert werden.

Man unterscheidet achsenparallele Cluster, die auf einer Auswahl von Attributen beruhen, von beliebig orientierten Correlation-Clustern. Beispiele für Verfahren zur Suche nach Subspace-Clustern sind CLIQUE, ORCLUS, SubClu, PreDeCon, PROCLUS, HiSC, HiCO, 4C, ERiC und CASH.

Bewertung gefundener Cluster

Die Bewertung von Clustern aus verschiedenen Verfahren ist schwierig. Besonders besteht die Gefahr der Überanpassung: Ähnelt die Bewertungsmethode einem der verglichenen Verfahren zu stark, wird letztlich vor allem geprüft, welches Verfahren der Bewertungsmethode am ähnlichsten ist.

Bei der internen Bewertung werden keine zusätzlichen Informationen benutzt, sondern nur die Objekte des Datensatzes. Häufig dienen Distanzmaße als Grundlage, etwa die durchschnittliche Distanz zwischen zwei Objekten eines Clusters. Diese Bewertung bevorzugt gewöhnlich Ergebnisse, die nach demselben Modell erzeugt wurden: k-Means-Cluster haben beispielsweise natürlicherweise geringere durchschnittliche Abstände als DBSCAN-Cluster. Sie ist daher vor allem geeignet, mehrere Ergebnisse desselben Verfahrens zu vergleichen, etwa mehrere Läufe eines randomisierten k-Means-Algorithmus. Der Silhouettenkoeffizient ist ein von der Anzahl der Cluster unabhängiges internes Maß für distanzbasierte Clusterings und eignet sich besonders zum Vergleich von k-Means-Ergebnissen mit unterschiedlichen Werten von k.

Bei der externen Bewertung wird Information verwendet, die während der Clusteranalyse nicht eingesetzt wurde. Gibt es beispielsweise eine Klasseneinteilung der Daten, kann die Übereinstimmung eines Clusters mit einer Klasse bewertet werden. Geeignete Zusatzinformationen sind jedoch nicht immer vorhanden. Außerdem soll Clusteranalyse neue Strukturen entdecken; eine Bewertung anhand einer bekannten Struktur ist deshalb nur bedingt sinnvoll. Daten können zudem mehrere überlappende Strukturen enthalten. Weil die externe Bewertung an bestehende Klassen gekoppelt ist, bevorzugt sie informierte Verfahren des Maschinellen Lernens gegenüber uninformierten Verfahren der Clusteranalyse.