K-Means Clustering

K-Means-Clustering ist ein grundlegender und weit verbreiteter Algorithmus im Bereich des unüberwachten Lernens, der darauf ausgelegt ist, verborgene Strukturen in unbeschrifteten Daten aufzudecken. Sein primäres Ziel besteht darin, einen Datensatz in klar abgegrenzte Untergruppen, sogenannte Cluster, aufzuteilen, sodass Datenpunkte innerhalb derselben Gruppe möglichst ähnlich und Datenpunkte aus unterschiedlichen Gruppen möglichst verschieden sind. Als grundlegender Bestandteil des Data Minings und der explorativen Analyse ermöglicht K-Means Datenwissenschaftlern, komplexe Informationen automatisch in überschaubare Kategorien zu organisieren, ohne vordefinierte Bezeichnungen oder menschliche Überwachung zu benötigen.

Funktionsweise des Algorithmus#

Die Arbeitsweise von K-Means ist iterativ und basiert auf Distanzmaßen, um die optimale Gruppierung der Trainingsdaten zu bestimmen. Der Algorithmus organisiert die Elemente in K Cluster, wobei jedes Element dem Cluster mit dem nächstgelegenen Mittelwert beziehungsweise Schwerpunkt zugeordnet wird. Dieser Prozess minimiert die Varianz innerhalb jeder Gruppe. Der Ablauf umfasst im Allgemeinen die folgenden Schritte:

1. Initialisierung: Der Algorithmus wählt K Ausgangspunkte als Schwerpunkte aus. Diese können zufällig oder mithilfe optimierter Verfahren wie k-means++ ausgewählt werden, um die Konvergenz zu beschleunigen.

2. Zuordnung: Jeder Datenpunkt im Datensatz wird anhand eines bestimmten Distanzmaßes dem nächstgelegenen Schwerpunkt zugeordnet, meist der euklidischen Distanz.

3. Aktualisierung: Die Schwerpunkte werden neu berechnet, indem der Durchschnitt (Mittelwert) aller Datenpunkte gebildet wird, die diesem Cluster zugeordnet sind.

4. Iteration: Die Schritte 2 und 3 werden wiederholt, bis sich die Schwerpunkte nicht mehr wesentlich bewegen oder die maximale Anzahl an Iterationen erreicht ist.

Die Bestimmung der richtigen Anzahl an Clustern (K) ist ein entscheidender Aspekt bei der Verwendung dieses Algorithmus. In der Praxis werden häufig Verfahren wie die Ellenbogenmethode verwendet oder der Silhouettenkoeffizient analysiert, um zu bewerten, wie klar die resultierenden Cluster voneinander getrennt sind.

Praktische Anwendungen in der KI#

K-Means-Clustering ist äußerst vielseitig und wird in verschiedenen Branchen zur Vereinfachung und Datenvorverarbeitung eingesetzt.

• Bildkomprimierung und Farbquantisierung: Im Bereich des maschinellen Sehens (CV) trägt K-Means dazu bei, die Dateigröße von Bildern zu reduzieren, indem Pixelfarben gruppiert werden. Durch die Zusammenfassung Tausender Farben zu einer kleineren Auswahl dominanter Farben führt der Algorithmus effektiv eine Dimensionsreduktion durch und bewahrt dabei die visuelle Struktur des Bildes. Diese Technik wird häufig vor dem Training fortschrittlicher Modelle zur Objekterkennung eingesetzt, um Eingabedaten zu normalisieren.
• Kundensegmentierung: Unternehmen nutzen Clustering, um Kunden anhand ihrer Kaufhistorie, demografischer Merkmale oder ihres Website-Verhaltens zu gruppieren. Dies ermöglicht gezielte Marketingstrategien und ist ein zentraler Bestandteil von KI-Lösungen im Einzelhandel. Durch die Identifizierung besonders wertvoller Käufer oder von Kunden mit Abwanderungsrisiko können Unternehmen ihre Kommunikation gezielt anpassen.
• Anomalieerkennung: Indem Systeme die Struktur von Clustern „normaler“ Daten erlernen, können sie Ausreißer erkennen, die weit von jedem Schwerpunkt entfernt liegen. Dies ist für die Betrugserkennung im Finanzwesen und die Anomalieerkennung in der Netzwerksicherheit wertvoll, da dadurch verdächtige Aktivitäten erkannt werden können, die von Standardmustern abweichen.
• Generierung von Anchor Boxes: Historisch verwendeten Objekterkennungsmodelle wie ältere YOLO-Versionen K-Means, um optimale Anchor Boxes aus Trainingsdatensätzen zu berechnen. Während moderne Modelle wie YOLO26 fortschrittliche anchor-freie Verfahren nutzen, bleibt das Verständnis von K-Means für die Entwicklung von Erkennungsarchitekturen relevant.

Implementierungsbeispiel#

Während Deep-Learning-Frameworks wie die Ultralytics Platform komplexe Trainingspipelines verarbeiten, wird K-Means häufig zur Analyse von Datensatzstatistiken eingesetzt. Das folgende Python-Snippet zeigt, wie sich 2D-Koordinaten, die Objektmittelpunkte simulieren, mithilfe der beliebten Bibliothek Scikit-learn clustern lassen.

import numpy as np
from sklearn.cluster import KMeans

# Simulated coordinates of detected objects (e.g., from YOLO26 inference)
points = np.array([[10, 10], [12, 11], [100, 100], [102, 101], [10, 12], [101, 102]])

# Initialize K-Means to find 2 distinct groups (clusters)
kmeans = KMeans(n_clusters=2, random_state=0, n_init="auto").fit(points)

# Output the cluster labels (0 or 1) for each point
print(f"Cluster Labels: {kmeans.labels_}")
# Output: [1 1 0 0 1 0] -> Points near (10,10) are Cluster 1, near (100,100) are Cluster 0

Vergleich mit verwandten Algorithmen#

Es ist wichtig, K-Means von anderen Algorithmen mit ähnlichen Namen oder Funktionen zu unterscheiden, damit für ein Projekt das richtige Werkzeug ausgewählt wird.

• K-Means im Vergleich zu K-nächste Nachbarn (KNN): Diese beiden Verfahren werden aufgrund des „K“ in ihren Namen häufig verwechselt. K-Means ist ein unüberwachter Algorithmus zum Clustering unbeschrifteter Daten. Im Gegensatz dazu ist K-nächste Nachbarn (KNN) ein überwachter Lernalgorithmus, der für Bildklassifizierung und Regression eingesetzt wird und sich auf beschriftete Daten stützt, um Vorhersagen anhand der Mehrheitsklasse der Nachbarn zu treffen.
• K-Means im Vergleich zu DBSCAN: Beide Verfahren gruppieren Daten, K-Means geht jedoch von kugelförmigen Clustern aus und erfordert, dass die Anzahl der Cluster im Voraus festgelegt wird. DBSCAN gruppiert Daten anhand ihrer Dichte, kann Cluster beliebiger Formen erkennen und kommt besser mit Rauschen zurecht. Dadurch ist DBSCAN für komplexe räumliche Daten in Datensätzen mit unregelmäßigen Strukturen überlegen, wenn die Anzahl der Cluster unbekannt ist.