Clustering-Algorithmen

Clustering-Algorithmen unterteilen Daten in Gruppen ähnlicher Elemente und offenbaren so natürliche Strukturen, ohne dass Labels verwendet werden.

Definition

Clustering ist die unüberwachte Partitionierung eines Datensatzes in Gruppen, sodass Punkte innerhalb einer Gruppe einander ähnlicher sind als Punkte in anderen Gruppen, wobei die Ähnlichkeit durch ein für die Anwendung gewähltes Distanz- oder Dichtekriterium definiert wird.

Scope

Dieses Thema behandelt die Hauptfamilien des Clustering: zentroidbasierte Methoden wie k-Means, hierarchisch-agglomeratives Clustering, das einen Baum verschachtelter Gruppen aufbaut, dichte-basierte Methoden, die beliebig geformte Cluster finden, sowie die Wahl von Distanzmaßen und der Anzahl der Cluster. Es wird erörtert, was ein gutes Clustering ausmacht und warum das Problem von Natur aus mehrdeutig ist.

Core questions

• Was macht eine Menge von Punkten zu einem Cluster?
• Wie minimiert k-Means iterativ die Varianz innerhalb der Cluster?
• Wie wird die Anzahl der Cluster gewählt?
• Wann übertreffen hierarchische oder dichte-basierte Methoden die zentroidbasierten Methoden?

Key theories

k-Means und Lloyds Algorithmus

k-Means minimiert die gesamte quadrierte Distanz zu Clusterzentren, indem es die Zuordnung von Punkten zu den nächsten Zentren und die Neuberechnung der Zentren abwechselt, ein Verfahren, das zu einem lokalen Optimum konvergiert.

Hierarchisches Clustering

Agglomeratives Clustering fusioniert wiederholt die nächstgelegenen Gruppen, um ein Dendrogramm zu erstellen, das Clusterings in jeder Granularität liefert und die Notwendigkeit vermeidet, die Anzahl der Cluster im Voraus festzulegen.

Mischmodell-Clustering

Die Behandlung von Clustern als Komponenten einer probabilistischen Mischung ermöglicht weiche Zuordnungen und Cluster unterschiedlicher Form und Größe, wodurch Clustering mit der Dichteschätzung latenter Variablen verbunden wird.

Clinical relevance

Clustering ist die Grundlage für Marktsegmentierung, Dokumenten- und Bildorganisation, Genexpressionsgruppierung und Anomalieerkennung und ein primäres Werkzeug der explorativen Datenanalyse. Da Clusterings von der gewählten Distanz und der Anzahl der Gruppen abhängen, müssen die Ergebnisse mit Vorsicht interpretiert werden, anstatt sie als einzigartige Grundwahrheit zu behandeln.

History

Das k-Means-Verfahren geht auf Lloyds Quantisierungsarbeit von 1957 zurück, die 1982 veröffentlicht wurde, sowie auf MacQueens unabhängige Formulierung. Hierarchisches Clustering entstand in der numerischen Taxonomie, und dichte-basierte Methoden wie DBSCAN erweiterten das Clustering auf beliebig geformte Gruppen, wodurch sie zusammen das Standard-Toolkit der unüberwachten Gruppierung bilden.

Key figures

• Stuart Lloyd
• James MacQueen
• Trevor Hastie

Seminal works

• lloyd1982
• hastie2009
• bishop2006

Frequently asked questions

Warum erfordert k-Means die Wahl der Clusteranzahl?

k-Means optimiert die Platzierung einer festen Anzahl von Zentren, sodass diese Anzahl ein Eingabeparameter ist. Die Wahl basiert auf Heuristiken wie der Elbow-Methode, Silhouetten-Scores oder Domänenwissen, da das Hinzufügen weiterer Cluster die Distanz innerhalb der Cluster immer reduziert.

Können verschiedene Clustering-Methoden unterschiedliche Ergebnisse liefern?

Ja. Da es keine einzelne Definition eines Clusters gibt, können zentroidbasierte, hierarchische und dichte-basierte Methoden unterschiedliche Partitionen derselben Daten erzeugen, die jeweils unter ihrem eigenen Kriterium gültig sind. Die richtige Wahl hängt von den erwarteten Clusterformen und dem Ziel ab.