Clusteranalysen

Idee der Clusteranalysen

Clusteranalysen kommen ohne Trainingsdaten aus, sie gehören zu den nicht-überwachten Methoden. Im Gegensatz zur Klassifikation gibt es keine vorgegebenen Kategorien, stattdessen versucht der Algorithmus den Datensatz so aufzuteilen, dass sich die Fälle innerhalb eines Clusters möglichst ähneln und zwischen den Clustern möglichst unterscheiden. Eine Vielzahl von Verfahren kann hierfür benutzt werden.

Clusteranalysen gehören natürlich auch zum Repertoire der klassischen Analysemethoden.

Idee der hierarchischen Clusteranalyse

Für kleinere Datensätze kann ein hierarchischer Clusteralgorithmus verwendet werden, der Schritt für Schritt aus den Fällen Cluster formt. Zunächst wird jeder Fall als ein Cluster angesehen. In jedem Schritt werden diejenigen Cluster verschmolzen, die nach einem vorgegebenen Maß am nächsten zueinander liegen. Sowohl das Distanzmaß als auch eine Berechnungsregel für den Abstand zweier Cluster (Fusionsalgorithmus) müssen dabei vorgegeben werden. Als Distanzmaß wird häufig der euklidische Abstand verwendet. Gängige Fusionsalgorithmen benutzen die Distanz der Mittelpunkte als Clusterabstand oder die geringste oder größte Distanz zwischen je zwei Fällen der Cluster. Eine Sonderposition nimmt der Ward-Algorithmus ein, der jeweils die Clusterfusion durchführt, die zur geringsten Zunahme der Gesamtvarianz innerhalb der Cluster führt.

Clusterlösungen, die mit unterschiedlichen Fusionsalgorithmen erzeugt wurden, können sich stark in der Form der Cluster im Variablenraum unterscheiden. Das Ward-Verfahren führt typischerweise zu sphärischen Clustern ähnlicher Größe. Ist hingegen der geringste Abstand zweier Fälle das Maß für den Clusterabstand, können in Größe und Form sehr ungleiche Cluster entstehen.

Idee der partitionierenden Clusteranalyse

Der gängigste Algorithmus zur partitionierenden Clusteranalyse ist der k-Means-Algorithmus, der auch für größere Datenmengen geeignet ist. Er versucht, die Fälle möglichst optimal auf eine vorgegebene Anzahl von Clustern aufzuteilen. Dabei werden die Fälle iterativ dem Cluster zugeordnet, zu dessen Zentrum sie den geringsten Abstand haben. Die Clusterzentren ergeben sich wiederum aus den Mittelwerten der Clusterfälle aus der vorherigen Iteration. Neben der Clusteranzahl müssen für die erste Iteration auch Anfangswerte für die Clusterzentren vorliegen. Beispielsweise können diese zufällig bestimmt werden oder es können Fälle gewählt werden, die einen möglichst großen Abstand zueinander haben. Außerdem kann das Ergebnis einer vorgeschalteten hierarchischen Analyse verwendet werden .

Ähnlich wie der Ward-Algorithmus einer hierarchischen Clusteranalyse resultiert der k-Means-Algorithmus typischerweise in sphärischen Clustern ähnlicher Größe. Wenn das der erwarteten oder wahren Partitionierung der Daten entspricht, hat dies den Vorteil, dass das Clusterzentrum die Fälle des Clusters sehr gut repräsentiert. Sollen die Fälle nicht eindeutig einem Cluster zugeordnet werden, sondern anteilig, können Fuzzy-Clustermethoden verwendet werden. Die meisten Algorithmen bestimmen den Anteil, mit dem ein Fall einem Cluster zugeordnet wird, anhand des Abstandes zu dessen Zentrum. Ein Fall, der sehr nahe bei einem Clusterzentrum liegt, wird mit großer Wahrscheinlichkeit zu diesem Cluster gehören, wohingegen ein Fall, der genau zwischen zwei Zentren liegt, zu beiden Clustern mit gleichem Anteil gehört. Auch in die Berechnung der Clusterzentren fließen die Fälle jeweils mit diesem Anteil ein.

Idee der dichtebasierten Clusteranalyse

Dichtebasierte Ansätze wie der etablierte DBSCAN-Algorithmus identifizieren zusammenhängende Gebiete im Variablenraum als Cluster. Voraussetzung ist ein Dichtekriterium, das aus einem Abstand und einer Mindestanzahl an Fällen besteht. Ein Fall ist dicht, wenn innerhalb des Abstandes die Mindestzahl an Fällen liegt. Ein Cluster ergibt sich aus benachbarten dichten Fällen.

In diesem Verfahren werden Fälle, die in keins der Cluster passen, automatisch erkannt. Dies ist besonders dann relevant, wenn Ausreißer oder Rauschen in den Daten zu erwarten ist. Die resultierenden Cluster können eine beliebige Form im Variablenraum haben. Das kann von Vorteil sein, hat aber den Nachteil, dass das Ergebnis schwieriger zu interpretieren ist. Im Allgemeinen müssen die Mittelpunkte der Cluster keine guten Repräsentanten der Clusterfälle sein.

Abweichungen identifizieren: Clusteralgorithmen

Was sich zunächst einfach anhört, kann in hochdimensionalen Daten sehr schwierig sein: die Fälle zu identifizieren, die sich von allen anderen Fällen unterscheiden. Ein mit dem DBSCAN-Algorithmus verwandtes Verfahren (Local-Outlier-Factor) nutzt ein Dichtekriterium, um Fälle zu erkennen, die in besonders dünn besiedelten Regionen des Variablenraumes sind. Auch mit anderen Clusterverfahren können ungewöhnliche Fälle erkannt werden.

Abweichungen Identifizieren: Klassifikationsverfahren

Verschiedene Klassifikationsverfahren können so eingesetzt werden, dass sie lediglich ein Modell für die Daten an sich bauen. Beispiele sind die One-Class-SVM und das Replicator-Neural-Network. Mit dieser Beschreibung der Daten kann für neue Fälle geprüft werden, wie gut sie zu den Trainingsdaten passen.

Wenn die Abweichungen typischerweise in den Ausprägungen nur weniger Variablen zu erwarten sind, kann die eigentliche Analyse mit dem sogenannten Feature Bagging kombiniert werden. Dabei wird die Analyse mehrfach auf verschiedenen Teilmengen der Variablen durchgeführt.