imported>Saehrimnir: /* Literatur */ BKL Fix

2025-08-19T15:29:11Z

Literatur: BKL Fix

Neue Seite

Als '''Cluster''' (gelegentlich auch ''Ballungen'') bezeichnet man in der [[Informatik]] und [[Statistik]] eine ''Gruppe'' von Datenobjekten mit ähnlichen Eigenschaften. Die Zuordnung von Daten zu den in einem Datensatz gefundenen Clustern bezeichnet man als '''Clustering'''. Verfahren zum Auffinden von solchen Gruppen bezeichnet man als [[Clusteranalyse]]. Nicht zu einem Cluster gehörende Datenobjekte bezeichnet man als [[Ausreißer]] ({{enS}} ''outlier'') oder Rauschen ({{enS}} ''noise'').

Die Kernidee eines Clusters ist, dass Objekte im selben Cluster über „ähnliche“ Eigenschaften verfügen und sich dadurch von Objekten, die nicht in diesem Cluster sind, unterscheiden.

== Clusterzugehörigkeit ==
Bereits bei der Clusterzugehörigkeit gibt es unterschiedliche Formulierungen.

* Bei einem '''harten Clustering''' gehört jedes Datenobjekt ganz oder gar nicht zu einem Cluster.
* Bei einem '''weichen Clustering''' gehört jedes Datenobjekt zu einem gewissen Anteil zu einem Cluster.

Des Weiteren kann man unterscheiden:
* Bei einem '''strikt partitionierenden Clustering''' gehört jedes Datenobjekt zu genau einem Cluster.
* Bei einem '''strikt partitionierenden Clustering mit Ausreißern''' kann ein Datenobjekt auch zu keinem Cluster gehören (bei einem weichen Clustering dürfen sich die Anteile auch zu weniger als 1 summieren).
* Bei einem '''überlappenden Clustering''' kann ein Objekt auch zu mehreren Clustern gehören (bei einem weichen Clustering dürfen sich die Anteile auch zu mehr als 1 summieren).

Auch innerhalb von Clustern kann es Untergruppen geben, die einander ähnlicher sind als dem Rest der größeren Gruppe. Hat man eine derartige Struktur, so spricht man von '''hierarchischen Clustern''' bzw. einem '''hierarchischen Clustering'''. Verfahren, die hierarchische Cluster finden können, sind beispielsweise [[Hierarchische Clusteranalyse]], [[OPTICS]] und [[BIRCH]].

== Modelle von Clustern ==
[[Datei:ClusterAnalysis Mouse de.svg|mini|400px|Vergleich [[K-Means-Algorithmus|k-Means]] und [[EM-Algorithmus]] auf einem künstlichen Datensatz, visualisiert mit [[Environment for DeveLoping KDD-Applications Supported by Index-Structures|ELKI]]. Durch Verwendung von Varianzen kann EM die unterschiedlichen Normalverteilungen akkurat beschreiben, während k-Means die Daten in ungünstige Voronoi-Zellen aufteilt.]]
Verschiedene Algorithmen zur Clusteranalyse verwenden oft unterschiedliche Begriffe von Clustern. Dies führt oftmals zu Verständnisproblemen, da die Ergebnisse eines Verfahrens nicht im Sinne eines anderen Verfahrens ähnlich sein müssen.

So beschreibt der [[k-Means-Algorithmus]] Cluster durch ihre Mittelpunkte (bzw. die daraus entstehenden [[Voronoi-Diagramm|Voronoi-Zellen]]), der [[EM-Algorithmus]] Cluster durch Mittelpunkt und eine [[Kovarianzmatrix]], während [[DBSCAN]] "dichte-verbundene" Mengen beliebiger Form als Cluster berechnet.

Je nach verwendetem Clusterbegriff können unterschiedliche Strukturen gefunden oder auch nicht gefunden werden. In dem hier gezeigten Beispiel können die vorhandenen Cluster vom k-Means-Algorithmus durch dessen Cluster-Modell nicht akkurat gefunden werden. Das komplexere Modell des EM-Algorithmus hingegen eignet sich optimal, um diese Daten zu beschreiben, da sie von einer [[Normalverteilung]] erzeugt wurden.


== Subspace-Cluster ==
Als '''Subspace-Cluster''' bezeichnet man einen Cluster, der nicht in allen Attributen oder Attributkombinationen auffällig ist. Erst wenn die Daten geeignet projiziert werden, erkennt man die höhere Ähnlichkeit der Clusterobjekte im Vergleich zu den anderen.

Bei Subspace-Clustern kann man unterscheiden zwischen ''Achsenparallelen Clustern'' (basierend auf einer Attributauswahl) und beliebig orientierten ''Correlation-Clustern''.

Verfahren für Subspace-Clusterverfahren sind beispielsweise CLIQUE, ORCLUS, SubClu, PreDeCon, PROCLUS, HiSC, HiCO, 4C, ERiC und CASH.

== Berechnung von Clustern ==

{{Hauptartikel|Clusteranalyse}}

Es gibt zahlreiche Verfahren (sogenannte Clusteranalyse-Algorithmen) zur Berechnung von Clustern. Diese unterscheiden sich wesentlich darin, was für Modelle sie für Cluster verwenden. Bei vielen klassischen Verfahren wie dem [[k-Means-Algorithmus]], dem [[EM-Algorithmus]], der hierarchischen Clusteranalyse und [[DBSCAN]] steht das Cluster-Modell im Vordergrund, und es gibt zum Teil mehrere konkrete [[Algorithmus|Algorithmen]], eine (zumindest lokal) optimale Lösung für dieses Modell zu finden. Viele neuere Verfahren hingegen haben kein entsprechend klar definiertes Modell mehr.

== Bewertung von Clustern ==
Die Bewertung von gefundenen Clustern ist kein einfaches Problem, insbesondere, wenn die Cluster aus unterschiedlichen Verfahren stammen. Es besteht die Gefahr der [[Überanpassung]], wenn die Bewertungsmethode einem der verwendeten Verfahren zu ähnlich ist – das bedeutet, man untersucht letztlich, welches Verfahren der Bewertungsmethode am ähnlichsten ist.

=== Interne Bewertung ===
Von einer ''internen'' Bewertung spricht man, wenn zur Bewertung keine zusätzlichen Informationen verwendet werden, sondern lediglich die Objekte des Datensatzes zur Bewertung verwendet werden. Typischerweise verwendet man hierzu Distanzmaße, beispielsweise die durchschnittliche Distanz zweier Clusterobjekte zueinander. Die interne Bewertung bevorzugt normalerweise Clusteringergebnisse, die nach demselben Modell erstellt wurden. So haben beispielsweise von <math>k</math>-Means gefundene Cluster natürlicherweise geringere durchschnittliche Abstände als DBSCAN-Cluster.
Daher ist diese Art der Bewertung vor allem sinnvoll, wenn man unterschiedliche Ergebnisse des gleichen Verfahrens bewerten will, beispielsweise von mehreren Läufen eines randomisierten Verfahrens wie dem <math>k</math>-Means-Algorithmus. Ein von der Anzahl der Cluster unabhängiges internes Maß zur Bewertung von distanzbasierten Clusterings stellt der [[Silhouettenkoeffizient]] dar. Er eignet sich vor allem dazu, Ergebnisse von <math>k</math>-Means mit unterschiedlichen Werten von <math>k</math> zu vergleichen, da er von der Clusteranzahl <math>k</math> unabhängig ist.

=== Externe Bewertung ===
Bei der ''externen'' Bewertung wird Information hinzugenommen, die nicht während der Clusteranalyse verwendet wurde. Existiert beispielsweise eine [[Klasseneinteilung (Statistik)|Klasseneinteilung]] der Daten, so kann die Übereinstimmung des Clusters mit einer Klasse zur Bewertung verwendet werden. Die Probleme bei diesem Ansatz liegen darin, dass zum einen nicht immer eine geeignete Information zur Verfügung steht, zum anderen das Ziel der Clusteranalyse eben genau die Entdeckung von neuer Struktur ist, und die Bewertung anhand einer bekannten Struktur daher nur bedingt sinnvoll ist. Des Weiteren können in den Daten mehrere, sich überlappende Strukturen existieren.<ref>{{Literatur | Autor=I. Färber, S. Günnemann, [[Hans-Peter Kriegel|H.-P. Kriegel]], P. Kröger, E. Müller, E. Schubert, T. Seidl, A. Zimek | Titel = On Using Class-Labels in Evaluation of Clusterings | Sammelwerk = MultiClust: 1st International Workshop on Discovering, Summarizing and Using Multiple Clusterings Held in Conjunction with KDD 2010, Washington, DC | Jahr = 2010 | Online = https://www.dbs.ifi.lmu.de/~zimek/publications/MultiClustAtKDD2010/Faerberetal.pdf}}</ref> Durch die Koppelung an die bestehende Klasseneinteilung bevorzugt diese Bewertung informierte Verfahren aus dem Bereich des [[Maschinelles Lernen|Maschinellen Lernen]] gegenüber uninformierten Verfahren aus der (echten) [[Clusteranalyse]].

== Siehe auch ==
* [[Data-Mining]]
* [[Knowledge Discovery in Databases]]
* [[Multivariate Verfahren]]
* [[Klasseneinteilung (Statistik)|Klasseneinteilung]]

== Einzelnachweise ==

<references />

== Literatur ==

* {{Literatur |Autor=Martin Ester, Jörg Sander |Titel=Knowledge Discovery in Databases. Techniken und Anwendungen |Verlag=[[Springer Nature]] |Ort=Berlin |Jahr=2000 |ISBN=3540673288}}

[[Kategorie:Clusteranalyse|!Cluster]]

Cluster (Datenanalyse) - Versionsgeschichte

imported>Saehrimnir: /* Literatur */ BKL Fix