k-Means für Depots verständlich erklärt

Kundenstandorte sollen auf Depots aufgeteilt werden: das Standardbeispiel für k-Means. Die zugehörige Demo ist eine von mehreren zum Thema Clustering und zeigt dieses eine Verfahren an einem Beispiel, das Schritt für Schritt tückischer wird. Diese Seite erklärt es zuerst ohne Formeln und danach für Fachleute mit Formeln, Messwerten und Grenzen.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Kunden und Depots: wer bedient wen?

Stellen Sie sich Kundenstandorte auf einer Karte vor. Sie sollen auf mehrere Depots aufgeteilt werden, und jedes Depot bedient die Kunden, die ihm am nächsten liegen. Gesucht ist die Aufteilung, bei der die Entfernungen zwischen Kunde und Depot insgesamt möglichst klein sind. Dabei werden die Entfernungen quadriert: Ein weiter Weg zählt also überproportional.

Genau das rechnet k-Means. Das „k“ steht für die Zahl der Depots, die man vorgibt. Das Verfahren heißt auch Lloyd's Algorithmus und ist eine Heuristik: ein Rechenweg, der gute Lösungen findet, ohne zu beweisen, dass keine bessere existiert.

Zwei Schritte, die sich wiederholen

Zuerst werden k Startpunkte für die Depots gewählt. Dann wechseln sich zwei Schritte ab. Zuweisung: Jeder Kunde wird dem nächstgelegenen Depot zugeordnet. Verschiebung: Jedes Depot wandert in den Schwerpunkt, also in den Mittelwert der Orte seiner Kunden. Danach sind manche Kunden dem Depot eines Nachbarn näher, und die Zuweisung beginnt von vorn.

Die Demo zeigt jede dieser Runden als Animation und daneben, wie sich die Summe der quadrierten Entfernungen entwickelt. So sieht man, wie schnell das Verfahren zur Ruhe kommt.

Warum hört es immer auf?

Jeder der beiden Schritte macht die Aufteilung besser oder lässt sie gleich, nie schlechter. Außerdem gibt es nur endlich viele mögliche Aufteilungen. Eine Aufteilung kann sich also nicht wiederholen, ohne dass das Verfahren endet. Das Ende ist garantiert.

Aufgehört ist nicht dasselbe wie am besten

Die Garantie gilt nur für das Ende, nicht für das beste Ergebnis. Wo das Verfahren landet, hängt von den Startpunkten ab. Bei klar getrennten, gleich großen Kundengruppen landet praktisch jeder Start beim selben Ergebnis. Bei ungleichen, engen Gruppen scheitert ein zufälliger Start reproduzierbar: Er kann zwei Startpunkte in dieselbe Gruppe legen und eine andere Gruppe ohne eigenes Depot lassen. Das Verfahren bleibt dann in einer stabilen, aber schlechteren Aufteilung hängen.

k-Means++ wählt die weiteren Startpunkte bevorzugt weit von den bisherigen entfernt. Dadurch landet nach der Demo öfter genau ein Startpunkt in jeder Gruppe. Das beste Ergebnis lässt sich nicht einfach nachrechnen: Es gilt als sehr aufwendig zu berechnen, die Demo hat deshalb keinen exakten Löser für k-Means.

Ausreißer: der Mittelwert lässt sich verziehen

Ein einzelner Kunde weit abseits zieht den Mittelwert so stark an, dass ein Depot mitten ins Leere rutschen kann. Die Alternative heißt k-Medoids: Das Depot muss dann an einem echten Kundenstandort liegen, und zwar am zentralsten. Ausreißer ziehen so ein Zentrum weniger leicht fort. Der Preis: Gemessen an der k-Means-Zielfunktion fällt das Ergebnis auf sauberen Daten etwas schlechter aus, und der Rechenaufwand je Runde ist höher. Ganz immun ist auch der Medoid nicht, vor allem wenn die Ausreißer eine eigene Gruppe bilden.

Wo liegt der Haken?

Die Zahl der Depots muss vorab feststehen. Das Verfahren unterstellt außerdem kugelförmige, gleich gestreute Gruppen und weist jeden Kunden genau einem Depot zu. Bei Gruppen anderer Form, zum Beispiel zwei ineinandergreifenden Halbmonden, scheitern der Mittelwert und der Medoid beide. Weitere Demos zum Thema Clustering behandeln diese Schwächen mit anderen Verfahren.

Wie ernst ist das Modell zu nehmen?

Die Kundenpunkte sind künstlich erzeugt und liegen in der Ebene. Die Demo zeigt, wie das Verfahren sich verhält, wenn das Beispiel tückischer wird, nicht welche Standorte für einen echten Betrieb richtig wären.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Vehikel: Kundenstandorte werden auf \(k\) Depots aufgeteilt, jedes Depot bedient die ihm nächstgelegenen Kunden. Die Summe der quadrierten Entfernungen zu minimieren ist exakt die k-Means-Zielfunktion (Inertia).
• Szenario: zufällige Kundenpunktwolken in der Ebene. Drei Regler bestimmen, wie tückisch die Landschaft ist: Zahl der Depots \(k\), Streuung beziehungsweise Überlappung der Gruppen und Größen-Ungleichgewicht (bei 0 sind alle Gruppen gleich groß und gleich dicht, bei 1 ist eine Gruppe groß und diffus, die übrigen klein und dicht). Dazu kommen 0 bis 10 Ausreißer.
• Verfahren: Lloyd's Algorithmus mit Zufalls-Start oder k-Means++, Zentrum wahlweise Mittelwert oder Medoid. Die Obergrenze liegt bei 50 Iterationen je Lauf; die Konvergenz erfolgt typischerweise nach 5 bis 15 Iterationen.
• Prüfung: Ein exaktes globales Optimum ist für k-Means NP-schwer, es gibt also keinen zweiten, exakten Löser. Stattdessen drei Prüfungen: Monotonie der Inertia über viele Zufallsinstanzen, eine handgerechnete Kleinstinstanz und der Kreuzvergleich mit scikit-learn von identischen Startzentren aus. Nur für k-Medoids gibt es einen exakten Vergleich (p-Median per MILP).

Zielfunktion und Lloyd-Schritte

Gegeben \(n\) Punkte \(x_1, \dots, x_n\) in der Ebene und \(k\) Zentren \(c_1, \dots, c_k\) ist die Inertia (Summe der quadrierten Abstände innerhalb der Cluster, englisch WCSS) zu minimieren:

\[\min_{c_1,\dots,c_k} \sum_{i=1}^n \min_{j \in \{1,\dots,k\}} \lVert x_i - c_j \rVert^2\]

Die innere Minimierung ist die Zuweisung jedes Punkts zum nächsten Zentrum (Voronoi-Partition bei festen Zentren). Im Update-Schritt wandert jedes Zentrum in den Mittelwert der Punktmenge \(S_j\), die ihm zugewiesen ist:

\[c_j \leftarrow \frac{1}{|S_j|} \sum_{x_i \in S_j} x_i\]

Der Mittelwert minimiert nachweislich die Summe der quadrierten Abstände innerhalb der Gruppe (Ableitung nach \(c_j\) gleich null setzen). Beide Schritte können die Zielfunktion nur verkleinern oder gleich lassen. Da es nur endlich viele Partitionen gibt, terminiert das Verfahren, aber nur in einem lokalen Optimum, dem Ergebnis der Startkonfiguration.

k-Means++ und k-Medoids

Beim k-Means++-Seeding wird der erste Startpunkt gleichverteilt gewählt, jeder weitere Punkt \(x\) mit einer Wahrscheinlichkeit proportional zu \(D(x)^2\), wobei \(D(x)\) der Abstand zum nächstgelegenen bereits gewählten Zentrum ist:

\[P(x) = \frac{D(x)^2}{\sum_{x'} D(x')^2}\]

Dieses Seeding garantiert in Erwartung eine \(O(\log k)\)-Approximation des globalen Optimums; Zufalls-Start hat keine solche Garantie. Ersetzt man im Update den Mittelwert durch den zentralsten echten Datenpunkt, erhält man k-Medoids, das p-Median-Problem:

\[\min_{S \subseteq X,\ |S| = k} \sum_{i=1}^n \min_{c \in S} \lVert x_i - c \rVert\]

Der Medoid minimiert die Summe der nicht quadrierten Abstände; ein Ausreißer dominiert sie weniger leicht. Das Update prüft alle Punktpaare im Cluster, \(O(|S_j|^2)\) statt \(O(|S_j|)\). Die Demo rechnet die Voronoi-Iteration, die wie Lloyd nur zu einem lokalen Optimum konvergiert.

Befunde

Die Zahlen stammen aus der Messreihe der Demo (die Zahlen zu Medoid und Ausreißern sind in deren Tests belegt). Die Preset-Instanz ist die Voreinstellung der Demo: 120 Punkte, 3 Gruppen, Streuung 0,25, 5 Ausreißer, Zufalls-Seed 3. Verteilungen laufen über 40 feste Netze ab Zufalls-Seed 100000. Die Werte sind das beste von 10 Läufen, die Zentren-Verschiebung steht in Karteneinheiten. Abweichende Bedingungen stehen in der jeweiligen Zeile.

Frage	Befund
Ist Konvergenz ein Optimum? (Handinstanz: vier Punkte, zwei klar getrennte Paare)	Mit Startzentren in der Mitte jedes Paares konvergiert das Verfahren sofort zur optimalen Partition (Inertia 1,0). Liegen beide Startzentren im selben Paar, konvergiert es stabil, aber zu einer nachweislich schlechteren Partition (Inertia 100,0).
Ausreißer ziehen den Mittelwert (Preset-Instanz mit 5 Ausreißern)	Der Mittelwert gibt ein Zentrum an die Ausreißer ab und verschmilzt zwei echte Gruppen: Zentren im Mittel 4,87 gegenüber der Lösung ohne Ausreißer verschoben, 33,3 % der echten Punkte falsch zugeordnet. Der Medoid bleibt in den echten Gruppen (Verschiebung 0,00, 0 % falsch). Jedes Verfahren gewinnt in seinem eigenen Maß: Summe der Abstände 176,3 (Medoid) gegen 273,6 (Mittelwert), Inertia 1 004,5 gegen 873,7.
Mehrere Ausreißer (40 Netze mit 1 / 3 / 5 / 10 Ausreißern)	Mittlere Verschiebung der Zentren: Mittelwert 0,106 / 0,578 / 0,836 / 3,573, Medoid 0,011 / 0,050 / 0,075 / 2,056. Falsch zugeordnete echte Punkte im Mittel: Mittelwert 0,1 / 1,8 / 2,7 / 21,8 %, Medoid 0,1 / 0,1 / 0,1 / 12,6 %. Bei 10 Ausreißern (8 % der Punkte) ordnet auch der Medoid 12,6 % falsch zu (schlechtestes Netz 34,2 %).
Was kostet der Medoid? (40 Netze ohne Ausreißer)	Die Medoid-Lösung hat im Mittel die 1,031-fache Inertia des Mittelwerts (höchstens 1,081, in allen 40 Netzen größer); der Mittelwert hat nur die 0,9955-fache Summe der Abstände des Medoids. Beide brauchen im Mittel 1,4 Iterationen.
Medoid-Heuristik gegen den exakten p-Median (40 Netze mit 60 Punkten)	Ein Lauf mit k-Means++-Start liegt im Mittel beim 1,024-fachen (3 Gruppen) bzw. 1,081-fachen (5 Gruppen) des Optimums, mit Zufalls-Start bei 1,117 bzw. 1,097. Das beste von 40 Läufen trifft das Optimum in 40 bzw. 39 von 40 Netzen.
Was nicht wie erwartet ausfiel	„k-Means++ ist immer besser“ gilt mit Ausreißern nicht: In der Preset-Instanz mit dem Medoid liegt die mittlere Summe der Abstände bei Zufalls-Start bei 198,7, bei k-Means++ bei 254,6, denn k-Means++ wählt die weit entfernten Ausreißer bevorzugt als Startpunkte. „Der Medoid rettet nicht-konvexe Formen“ gilt nicht: Halbmonde (k = 2) haben Fehlzuordnung 25,4 % (Mittelwert) gegen 23,9 % (Medoid), beide scheitern.

Grenzen

• Heuristik ohne Optimalitätsgarantie: Konvergenz ist ausdrücklich nur der Nachweis eines lokalen Optimums. Für k-Means gibt es keinen exakten Löser zum Vergleich (NP-schwer, bereits für \(k = 2\) bei unbeschränkter Dimension und in der Ebene für beliebiges \(k\)).
• Annahmen des Verfahrens: \(k\) muss vorab feststehen, die Gruppen werden als kugelförmig und gleich gestreut unterstellt, die Zuweisung ist hart. Halbmonde zeigen, dass auch der Medoid nicht-konvexe Formen nicht rettet. Dichte-, mischungs- und graphbasierte Verfahren behandeln diese Schwächen.
• Der Medoid ist nicht immun: Bei Ausreißern, die eine eigene Gruppe bilden, kann auch er zu ihnen abwandern. Die Voronoi-Iteration ist kein PAM; ein Einzellauf liegt deshalb im Mittel 2 bis 12 % über dem Optimum, erst mehrere Starts nähern sich ihm.
• Aussagen mit Voraussetzungen: Die Befunde zu Ausreißern gelten für die genannten Netze (Preset-Instanz, 40 feste Netze) und für das beste von 10 Läufen.
• Simulation in der Ebene: Die Kundenpunkte sind erzeugt, keine Praxisdaten. Der Medoid-Update ist mit \(O(|S_j|^2)\) teurer; der exakte p-Median ist nur auf Abruf bis 80 Punkte gerechnet.

Quellen

• Arthur und Vassilvitskii (2007): k-Means++-Seeding mit der \(O(\log k)\)-Approximationsgarantie.
• Aloise et al. (2009): NP-Härte der Euklidischen Summe-der-Quadrate-Clusterung, bereits für \(k = 2\), wenn die Dimension nicht beschränkt ist.
• Mahajan, Nimbhorkar und Varadarajan: Das planare k-Means-Problem ist NP-schwer.
• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/kmeans-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise stammen aus der README der Demo.