K-Means ist ein bekannter Algorithmus des Unsupervised Learning. Die Daten benötigen keine Klassenlabels. Stattdessen versucht der Algorithmus, natürliche Gruppen oder Cluster zu entdecken.
Grundidee
Bei K = 3 werden drei Clusterzentren initialisiert. Jeder Datenpunkt wird dem nächsten Zentrum zugeordnet. Anschließend wird für jeden Cluster der Mittelwert seiner Punkte als neuer Centroid berechnet.
Dieser Vorgang wird wiederholt, bis sich die Zuordnungen kaum oder gar nicht mehr verändern.
Schritte
- K wählen.
- K Centroids initialisieren.
- Distanzen berechnen.
- Punkte dem nächsten Centroid zuordnen.
- Centroids als Mittelwert neu berechnen.
- Bis zur Konvergenz wiederholen.
Centroid
Ein Centroid ist der Mittelwert der Positionen aller Punkte eines Clusters und muss selbst kein realer Datenpunkt sein.
Euklidische Distanz
Typischerweise wird folgende Distanz verwendet:
d = sqrt((x2 - x1)^2 + (y2 - y1)^2)
K auswählen
Elbow Method
Mehrere K-Werte werden getestet und der Fehler innerhalb der Cluster wird verglichen. Der Punkt, an dem zusätzliche Cluster nur noch wenig Verbesserung liefern, kann ein sinnvoller K-Wert sein.
Silhouette Score
Der Silhouette Score bewertet, wie gut Punkte zu ihrem eigenen Cluster im Vergleich zu anderen Clustern passen.
Feature Scaling
Da K-Means auf Distanzen basiert, können Features mit großem Wertebereich dominieren. Standardization oder Min-Max Scaling sind deshalb häufig erforderlich.
Initialisierung
Schlechte Startzentren können zu schwächeren lokalen Lösungen führen. K-Means++ ist eine verbreitete Methode für bessere Startpunkte.
Die JavaScript-Implementierung im bereitgestellten Projekt verwendet die ersten K Datenpunkte als initiale Zentren. Das ist didaktisch einfach, in produktiven Systemen sind robustere Initialisierungen meist sinnvoller.
Anwendungen
- Kundensegmentierung
- Nutzersegmentierung
- Marketinganalyse
- Bildkompression
- Explorative Datenanalyse
Vorteile
- Einfach
- Relativ effizient
- Gut für Segmentierungsprobleme
- Hilfreich zur ersten Strukturerkennung
Grenzen
- K muss vorgegeben werden
- Ausreißer können Zentroiden verschieben
- Initialisierung beeinflusst das Ergebnis
- Kompakte Cluster funktionieren besser als komplexe Formen
- Für rein kategoriale Daten ist Standard-K-Means ungeeignet
Implementierungslogik
choose K centroids
repeat:
assign every point to nearest centroid
recompute each centroid as cluster mean
until assignments stop changing
Die mitgelieferte Implementierung berechnet Distanzen, weist die Punkte Clustern zu und berechnet die Zentroiden iterativ neu.
K-Means vs. KNN
KNN ist meist supervised und nutzt gelabelte Nachbarn zur Vorhersage.
K-Means ist unsupervised und entdeckt Cluster ohne Labels.
Fazit
K-Means ist ein grundlegender Clustering-Algorithmus. Gute Ergebnisse hängen besonders von K, Skalierung, Initialisierung, Ausreißern und der tatsächlichen Struktur der Daten ab.