Warum liefern verschiedene Starts verschiedene Cluster?

Lloyd verringert die Zielfunktion monoton, aber nur bis zu einem lokalen Minimum der nichtkonvexen Aufgabe. Verschiedene Anfangszentroide fallen in verschiedene „Fallen“ — deshalb startet man oft mehrfach neu oder initialisiert klüger (k-means++).

Ist die global optimale Zerlegung garantiert?

Nein: selbst in der Ebene ist die exakte globale Optimierung von k-Means im schlechtesten Fall NP-schwer. Die Lloyd-Iterationen sind ein schnelles heuristisches Verfahren, das auf „glatten“ Wolken gewöhnlich gut arbeitet.

Was tun, wenn ein Cluster leer wird?

Im Anwendungscode initialisiert man das Zentroid oft neu (etwa im fernsten Punkt). Hier behält ein leerer Cluster das alte Zentroid, damit die Marke mitten im Schritt nicht verloren geht; beim nächsten Zuordnen kann sich die Zusammensetzung ändern.

k-Means (Lloyd-Algorithmus)

Punkte in der Ebene, Clusterzahl k und Startzentroide. Lloyd-Schritt: Zuordnung zum nächsten Zentrum und Verschiebung des Zentroids in den Schwerpunkt. Demo — Gauß-Mischung; Summe der Quadrate innerhalb der Cluster.

Zum Modell

k-Means (Lloyd-Algorithmus) zerlegt eine endliche Punktmenge in k Gruppen und minimiert die Summe der quadrierten euklidischen Abstände zu den Zentroiden. Hier der klassische Lloyd-Algorithmus: bei festen k Zentren wechseln Zuordnungsschritt (jeder Punkt → nächstes Zentroid, Voronoi-Zellen) und Updateschritt (Zentroid ← Mittelwert seiner Punkte). In einem vollen Schritt wächst die Summe der Quadrate innerhalb der Cluster nicht: die Zuordnung ist optimal bei festen Zentren, der Mittelwert ist das Optimum bei festen Zuordnungen. Startzentroide sind k verschiedene Datenpunkte, gewählt durch Mischen mit steuerbarem Startwert; die Demo liefert eine Gauß-Mischung. Ein leerer Cluster behält das bisherige Zentroid — ein didaktischer Kniff ohne die volle k-means++-Logik.

Für wen: Datenanalyse: unüberwachtes Lernen, Voronoi-Diagramm, alternierende Minimierung.

Wichtige Begriffe

k-means
lloyd-algorithmus
zentroid
voronoi-zelle
summe der quadrate innerhalb der cluster
gauß-mischung
lokales minimum
leerer cluster

So funktioniert es

Lloyd-Algorithmus: Zuordnungsschritt — jeder Punkt zum nächsten der k Zentroide; Updateschritt — Zentroid in den Schwerpunkt seiner Punkte. Start — k zufällige Datenpunkte; Demo — Gauß-Mischung. Die Summe der Quadrate innerhalb der Cluster wächst in einem vollen Schritt nicht.

Häufige Fragen

Warum liefern verschiedene Starts verschiedene Cluster?: Lloyd verringert die Zielfunktion monoton, aber nur bis zu einem lokalen Minimum der nichtkonvexen Aufgabe. Verschiedene Anfangszentroide fallen in verschiedene „Fallen“ — deshalb startet man oft mehrfach neu oder initialisiert klüger (k-means++).
Ist die global optimale Zerlegung garantiert?: Nein: selbst in der Ebene ist die exakte globale Optimierung von k-Means im schlechtesten Fall NP-schwer. Die Lloyd-Iterationen sind ein schnelles heuristisches Verfahren, das auf „glatten“ Wolken gewöhnlich gut arbeitet.
Was tun, wenn ein Cluster leer wird?: Im Anwendungscode initialisiert man das Zentroid oft neu (etwa im fernsten Punkt). Hier behält ein leerer Cluster das alte Zentroid, damit die Marke mitten im Schritt nicht verloren geht; beim nächsten Zuordnen kann sich die Zusammensetzung ändern.

Machen Sie mit verwandten Themen in dieser Kategorie weiter — oder alle 85 in „Mathematische Visualisierung“.

Ganze Kategorie →

NeuSchule

Lineare Regression: KQ, Ridge, Lasso und R²

Simulation starten

Punkte in der Ebene und das Modell y = β₀ + β₁x: gewöhnliche kleinste Quadrate, Ridge (L₂-Strafterm nur auf die Steigung) oder Lasso (L₁-Strafterm). Die Verschiebung Δy am Punkt mit größtem |x| ist ein Ausreißer mit starker Hebelwirkung; verglichen werden SSE und R².

NeuSchule

Konvexe Hülle (Graham und QuickHull)

Simulation starten

Punkte in der Ebene: Graham-Scan mit Schrittanimation oder QuickHull; Vergleich der Knotenmengen.

NeuSchule

DBSCAN: dichtebasierte Clusteranalyse

Simulation starten

Radius ε und Schwelle minPts: Kern, Rand und Rauschen. Cluster beliebiger Form ohne vorgegebenes k; um Kerne lassen sich ε-Kreise zeigen.

NeuSchule

Delaunay-Triangulation und Voronoi-Diagramm

Simulation starten

Bowyer–Watson-Triangulation und duales Voronoi-Diagramm: ein Klick ergänzt Standorte, Ziehen verschiebt sie.

NeuSchule

Methode der kleinsten Quadrate

Simulation starten

Verrauschte Punkte und die Gerade y = ax + b, die die Summe der quadrierten vertikalen Residuen minimiert. Ändern Sie Steigung, Achsenabschnitt und Rauschen — Residuen und Summe der Fehlerquadrate werden sichtbar.

NeuHochschule / Forschung

Adaptives Filter LMS / NLMS

Simulation starten

Primärkanal p = s + v, wobei v ein unbekanntes FIR des weißen Referenzrauschens x[n] ist. Adaptives FIR mit L Abgriffen nach LMS oder NLMS: der Fehler e = p − wᵀx strebt gegen das Nutzsignal s.

k-Means (Lloyd-Algorithmus)

Zum Modell

So funktioniert es

Häufige Fragen

Ähnliche Simulationen

Lineare Regression: KQ, Ridge, Lasso und R²

Konvexe Hülle (Graham und QuickHull)

DBSCAN: dichtebasierte Clusteranalyse

Delaunay-Triangulation und Voronoi-Diagramm

Methode der kleinsten Quadrate

Adaptives Filter LMS / NLMS

k-Means (Lloyd-Algorithmus)

Zum Modell

So funktioniert es

Häufige Fragen