Clustering (Clusteranalyse) ist eine Kernaufgabe des maschinellen Lernens ohne vorgegebene Antworten: Ein Algorithmus gruppiert Datenpunkte so, dass Punkte innerhalb einer Gruppe einander ähnlich sind und Punkte verschiedener Gruppen sich unterscheiden. Da keine gelabelten Trainingsdaten nötig sind, gehört das Clustering zum Unsupervised Learning. Typische Eingaben sind Merkmalsvektoren aus einem Dataset.
k-Means: der Klassiker
Der bekannteste Algorithmus ist k-Means: Man wählt k Cluster-Zentren (Zentroide), weist jeden Punkt dem nächstgelegenen Zentroid zu, berechnet die Zentroide als Mittelwert ihrer Cluster neu und wiederholt das, bis sich nichts mehr ändert. Die Initialisierung erfolgt meist mit k-Means++, das die Startzentren voneinander weit entfernt platziert; da k-Means nur lokale Optima garantiert, startet man mehrfach und behält das beste Ergebnis. Die Laufzeit pro Iteration ist O(n·k) – mit n Punkten, k Clustern und I Iterationen also O(n·k·I), siehe Big-O-Notation.
Weitere Verfahren
- Hierarchisches Clustering – baut schrittweise eine Baumstruktur (Dendrogramm) auf; agglomerativ verschmilzt es ähnlichste Cluster, divisiv spaltet es sie
- DBSCAN – dichtebasiert, findet Cluster beliebiger Form und markiert Ausreißer als Rauschen; braucht die Parameter eps (Radius) und minPts
- Gaußsche Mischmodelle – modellieren Cluster als überlappende Wahrscheinlichkeitsverteilungen
Das passende k findet man empirisch, etwa mit der Elbow-Methode (Krümmung der Fehlerkurve) oder dem Silhouettenkoeffizienten als Qualitätsmaß.
Abgrenzung und Anwendungen
Clustering sucht Struktur ohne Labels – im Gegensatz zur Klassifikation, die bekannte Kategorien zuordnet, und zur Regression, die Zahlenwerte vorhersagt. Nicht zu verwechseln ist die Clusteranalyse außerdem mit einem Cluster im Rechner-Verbund: Dort arbeiten viele Server als ein System zusammen – der Begriff ist gleich, das Thema ein anderes. Typische Einsatzfelder des Clustering sind Kundensegmentierung im Marketing, Bildsegmentierung (Gruppierung ähnlicher Pixel), Empfehlungssysteme, Genexpressionsanalyse in der Bioinformatik und Anomalieerkennung.