Clusteranalyse
Unter Clusteranalyse versteht man verschiedene automatische Verfahren der 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 Klassifikation, zur Erkennung von Mustern in der Bildverarbeitung und zum Data-Mining einsetzen.
Die zu untersuchenden Objekte werden bei der Clusteranalyse oft in Form von Vektorenen 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.
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 Berechnungsverfahre eingesetzt. Inzwischen können zur Bestimmung der Verwandtschaft von Organismus unter anderem ihre Gensequenzen verglichen werden.
Siehe auch: Kladistik
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 Distanzfunktion zur Bestimmung des Abstands zweier Elemente (, zum Beispiel die euklidische Distanz) und/oder eine Methode zur Berechnung des Mittelpunktes oder Centroiden eines Clusters (, zum Beispiel der Mittelwert) bekannt sein. Anstatt einer Distanzfunktion arbeiten einige Algorithmen auch mit einer Ähnlichkeitsfunktion.
Beim k-means Algorithmus ist eine gewünschte Anzahl von Clustern und eine Funktion zur Bestimmung des Mittelpunktes eines Clusters bekannt. Der Algorithmus läuft folgendermaßen ab:
Die bei der hierarchischen Clusterung entstehende Baumstruktur wird in der Regel mit einem Dendrogram visualisiert. 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.
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 für den Abstand zwei einzelner Elemente gegeben sein.
Für den Abstand zweier Cluster und lassen sich unter Anderem folgende Abstände verwenden:
Zwei Exterme bei der Clusterung in Netzwerken bilden die Einteilung in Zusammenhangskomponenten (Single Link) und in Cliquen.
Prinzip
Geschichte
Algorithmen
k-means-Algorithmus
Hierarchisches Clustern
Abstandsfunktionen von Clustern
Weitere Methoden: Density Linkage, Uniform-Kernel, Wong's Hybrid, EML, Flexible-Beta, McQuitty's Similarity Analysis, Median,
isodata
EM-Algorithmus
Fuzzy Clustering
kth-Nearest Neighbor
Graphentheoretische Cluster
Self-Organizing Maps
Eine andere Möglichkeit unüberwachten Lernens bieten Self-Organizing Maps.Siehe auch
Künstliche Intelligenz, Statistik, Information-Retrieval, Clusterkoeffizient