K-Means-Clustering

Das K-Means-Clustering teilt Beobachtungen in eine feste Anzahl von Clustern ein, indem es die gesamte Summe der quadrierten Abstände innerhalb der Cluster zu den Cluster-Schwerpunkten minimiert.

Definition

K-Means-Clustering ist eine Partitionierungsmethode, die eine vorgegebene Anzahl von Clusterzentren platziert und jede Beobachtung ihrem nächsten Zentrum zuweist, um die gesamte quadrierte euklidische Distanz von Beobachtungen zu ihren zugewiesenen Zentren zu minimieren.

Scope

Dieses Thema behandelt die Zielsetzung der Summe der Quadrate innerhalb der Cluster, den iterativen Zuweisungs- und Aktualisierungsalgorithmus, der zwischen der Zuweisung von Punkten zum nächsten Schwerpunkt und der Neuberechnung der Schwerpunkte wechselt, die Abhängigkeit von der Initialisierung und die daraus resultierenden lokalen Optima, die Wahl der Anzahl der Cluster sowie die Annahmen und Einschränkungen der Methode.

Core questions

• Wie können Beobachtungen partitioniert werden, um die Streuung innerhalb der Cluster zu minimieren?
• Warum konvergiert der Algorithmus nur zu einem lokalen Optimum und wie wird dies gemildert?
• Wie wird die Anzahl der Cluster gewählt?
• Welche Clusterformen und -skalen nimmt die Methode implizit an?

Key theories

Minimierung der Summe der Quadrate innerhalb der Cluster

K-Means sucht die Partition und den Satz von Schwerpunkten, die den gesamten quadrierten Abstand von Punkten zu ihren Clusterzentren minimieren, ein Ziel, für das die alternierende Zuweisungs- und Aktualisierungsiteration das Kriterium monoton verringert.

Empfindlichkeit gegenüber lokalen Optima

Da die Zielfunktion nicht konvex ist, konvergiert der Algorithmus zu einem lokalen Minimum, das von den anfänglichen Zentren abhängt, was mehrere Neustarts und eine sorgfältige Initialisierung motiviert.

Clinical relevance

K-Means ist eine schnelle, skalierbare Standardmethode zur Partitionierung großer Datensätze und wird in der Vektorquantisierung, der Bildfarbreduktion, der Kundensegmentierung und als Initialisierung für komplexere Modelle eingesetzt.

History

Die Idee der schwerpunktbasierten Partitionierung wurde 1967 von MacQueen formalisiert, der K-Means benannte und auf Lloyds früherem Quantisierungsalgorithmus aufbaute. Aufgrund seiner Einfachheit und Geschwindigkeit wurde es zu einer der am weitesten verbreiteten Clustering-Methoden.

Debates

Implizite Annahmen von K-Means

Die Minimierung der quadrierten euklidischen Distanz begünstigt annähernd kugelförmige, gleich große Cluster, sodass K-Means irreführend sein kann, wenn Cluster länglich, ungleich groß oder nicht-konvex sind, was modellbasierte oder dichte-basierte Alternativen motiviert.

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

Warum liefert K-Means bei verschiedenen Durchläufen unterschiedliche Ergebnisse?

Die Zielfunktion ist nicht konvex, daher konvergiert der Algorithmus zu einem lokalen Optimum, das von den zufälligen Initialzentren abhängt; es ist gängige Praxis, ihn mehrmals auszuführen und das beste Ergebnis zu behalten.

Wie wähle ich die Anzahl der Cluster k?

Gängige Heuristiken umfassen den „Ellenbogen“ in der Summe der Quadrate innerhalb der Cluster, die Gap-Statistik und die durchschnittliche Silhouettenbreite, obwohl keine davon definitiv ist und Domänenwissen oft die Wahl leitet.