Unter Clusteranalyse versteht man verschiedene automatische Verfahren der [wiki:Datenanalyse] zur Ermittlung von Gruppen (Cluster) zusammengehöriger Objekte aus einer Grundmenge von numerisch beschriebenen Objekten. Die Objekte können beispielsweise Datensätze von Messwerten oder Bildpunkte sein, in denen geordnete Ansammlungen oder Hierarchien gefunden werden sollen.
Verfahren der Clusteranalyse lassen sich zur automatischen [wiki:Klassifikation], zur Erkennung von Mustern in der Bildverarbeitung und zum [wiki:Data-Mining] einsetzen.
Prinzip
Die zu untersuchenden Objekte werden bei der Clusteranalyse oft in Form von Vektoren als Punkte in einem Vektorraum zusammengefasst. Die Anzahl der Komponenten der Datenvektoren bildet die Dimension des Vektorraumes. Ein Cluster ist eine Anhäufung von Punkten mit geringerem Abstand zu Punkten des gleichen Clusters als zu Nachbarn anderer Cluster bzw. eine Gruppen von Punkten, die untereinander oder in Bezug auf einen berechneten Schwerpunkt eine minimale Abstandssumme haben. Dazu ist die Wahl eines Distanzmaßes erforderlich. In anderen Fällen sind die Abstände (bzw. umgekehrt die Ähnlichkeiten) der Objekte untereinander direkt bekannt und müssen nicht aus der Darstellung im Vektorraum ermittelt werden.
Geschichte
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 Organismus unter anderem ihre Gensequenzen verglichen werden.
Siehe auch: [wiki:Kladistik]
Algorithmen
Daten-clustering Algorithmen können hierarchisch oder partitionierend sein, wobei man erstere noch in agglomerierende (bottom-up) oder unterteilende (top-down) Algorithmen unterteilt. Weiterhin unterscheidet man zwischen überwachten (supervised) und nicht-überwachten (unsupervised) Algorithmen.
Je nach Algorithmus muss eine [wiki:Distanzfunktion] zur Bestimmung des Abstands zweier Elemente (<math>d(a,b)</math>, zum Beispiel die [wiki:Euklidische Distanz]) und/oder eine Methode zur Berechnung des Mittelpunktes oder Centroiden eines Clusters (<math>\bar a</math>, zum Beispiel der [wiki:Mittelwert]) bekannt sein. Anstatt einer Distanzfunktion arbeiten einige Algorithmen auch mit einer Ähnlichkeitsfunktion.
Hierarchisches Clustern
Grundsätzlich lassen sich anhäufende Verfahren (agglomerative clustering) und teilende Verfahren (divisive clustering) unterscheiden. Bei den anhäufenden Verfahren, die in der Praxis häufiger eingesetzt werden, werden schrittweise einzelne Objekte zu Clustern und diese zu größeren Gruppen zusammengefasst, während bei den teilenden Verfahren größere Gruppen schrittweise immer feiner unterteilt werden. Die bei der hierarchischen Clusterung entstehende Baumstruktur wird in der Regel mit einem Dendrogram visualisiert.
Beim anhäufenden Clustern wird zunächst jedes Objekt als ein eigener Cluster mit einem Element aufgefasst. Nun werden in jedem Schritt die jeweils einander nächsten Cluster zu einem Cluster zusammengefasst. Das Verfahren kann beendet werden, wenn alle Cluster eine bestimmte Distanz zueinander überschreiten oder wenn eine genügend kleine Zahl von Clustern ermittelt worden ist. Aus verschiedenen Methoden zur Bestimmung des Abstands zweier Cluster ergeben sich verschiedene Verfahren. Dabei muss eine Distanzfunktion <math>d</math> für den Abstand zwei einzelner Elemente gegeben sein.
Abstandsfunktionen von Clustern
Für den Abstand zweier Cluster <math>A</math> und <math>B</math> lassen sich unter Anderem folgende Abstände verwenden:
- Der minimale Abstand zweier Elemente aus den beiden Clustern (single linkage clustering)
<math>min_{a\in A, b\in B}\{d(a,b)\} </math> - Der maximale Abstand zweier Elemente aus den beiden Clustern (complete linkage clustering)
<math>max_{a\in A, b\in B}\{d(a,b)\}</math> - Der durchschnittliche Abstand aller Elementpaare aus den beiden Clustern (average linkage clustering)
<math>\frac{1}{|A||B|}\sum_{a\in A, b\in B} d(a,b)</math> - Die durchschnittliche Abstand aller Elementpaare aus der Vereinigung von A und B(average group linkage)
<math>\frac{1}{|C|}\sum_{x,y\in C, C=A \cup B} d(a,b)</math> - Der Abstand der [wiki:Mittelwert] der beiden Cluster (centroid method)
<math>d(\bar a, \bar b)</math> - Die Zunahme der Varianz beim Vereinigen von A und B (Ward's method)
<math>\frac{d(\bar a, \bar b)}{1/|A|+1/|B|}</math>
Weitere Methoden: Density Linkage, Uniform-Kernel, Wong's Hybrid, EML, Flexible-Beta, McQuitty's Similarity Analysis, Median,
isodata
k-means-Algorithmus
Beim k-means Algorithmus ist eine gewünschte Anzahl <math>k</math> von Clustern und eine Funktion zur Bestimmung des Mittelpunktes eines Clusters bekannt. Der Algorithmus läuft folgendermaßen ab:
- (Initialisierung) (Zufällige) Auswahl von k Clusterzentren
- (Zuordnung) Jedes Objekt wird dem ihm am nächsten liegenden Clusterzentrum zugeordnet
- (Neuberechnung) Es werden für jedes Cluster die Clusterzentren neu berechnet
- (Wiederholung) Falls sich nun die Zuordnung der Objekte ändert, weiter mit Schritt 2, ansonsten Abbruch
EM-Algorithmus
Die Idee des EM Algorithmus basiert auf dem Clustern nach k-means. Grundvoraussetzung ist hier, dass alle Objekte als Vektoren der Dimension n dargestellt werden können. "n" kann beliebig gewählt werden. Weiterhin muß eine Funktion bekannt sein, nach der der Mittelwert zweier solcher Vektoren berechnet werden kann. Wie bei k-means wird zu Beginn des Clustervorgangs eine beliebige, domänenspezifische Anzahl von Clustern vorgegeben, in die die Objekte eingeteilt werden sollen. Jeder dieser Cluster hat einen Mittelpunkt: Einen Vektor der Dimension n.
Der Clusteralgorithmus selbst durchläuft zwei Schritte:
1) Estimation
Bestimme für jedes Objekt nach einer Wahrscheinlichkeitsverteilung Deiner Wahl (beliebt ist hier z.B. die Normalverteilung), mit welcher Wahrscheinlichkeit es zu jedem der Cluster gehört und speichere diese Wahrscheinlichkeiten für alle Objekte und Cluster.
2) Maximisation
Bestimme anhand der ermittelten Zuordnungswahrscheinlichkeiten die Parameter neu, die die Cluster bestimmen (z.B. die Mittelwertvektoren).
Die Iteration wird abgebrochen, wenn entweder die Änderung der Likelyhood der Daten gegeben die Cluster unter einen vorgegebenen Schwellwert sinkt, oder die ebenfalls vorgegebene maximale Anzahl von Iterationen erreicht ist.
Im Gegensatz zu k-means wird damit eine "weiche" Clusterzuordnung erreicht: Mit einer gewissen Wahrscheinlichkeit gehört jedes Objekt zu jedem Cluster. Jedes Objekt beeinflußt so die Parameter jedes Clusters entsprechend dieser Wahrscheinlichkeit. Der Erfolg des Algorithmus hängt stark von der gewählten Wahrscheinlichkeitsverteilung ab.
Literatur: A. Dempster, N. Laird, and D. Rubin. Maximum likelehood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society B 39, 1977.
Fuzzy Clustering
kth-Nearest Neighbor
Graphentheoretische Cluster
Zwei Exterme bei der Clusterung in Netzwerken bilden die Einteilung in [wiki:Zusammenhangskomponente] (Single Link) und in [wiki:Clique (Graphentheorie)].
Self-Organizing Maps
Eine andere Möglichkeit unüberwachten Lernens bieten [wiki:Self-Organizing Maps].
Siehe auch
[wiki:Künstliche Intelligenz], [wiki:Statistik], [wiki:Information-Retrieval], [wiki:Clusterkoeffizient]
Weblinks
- [url:http://www.fuzzy-clustering.de/|http://www.fuzzy-clustering.de/][wiki:En:data clustering]
Dieser Artikel basiert auf einem gleichnamigen Artikel der freien Enzyklopädie [url:http://de.wikipedia.org/wiki/Wikipedia:Hauptseite|Wikipedia] und steht unter der Doppellizenz [url:http://www.gnu.org/licenses/gpl-3.0.html|GNU-Lizenz für freie Dokumentation] und [url:http://creativecommons.org/licenses/by-sa/3.0/|CC-BY-SA 3.0 Unported]. In dem Artikel von Wikipedia ist eine Liste der Autoren verfügbar.
