Definition - K-Means-Clustering

• Typen:
  • K-Median Clustering
  • K-Medoid-Clustering
• Konstrukte:
  • Inertia
  • K-Means++
• Generalisierungen:
  • Clusteranalyse
  • Heuristischer Algorithmus
• Eigenschaften:
  • Bestimmung der Clusterzahl mittels Elbow Methode
  • Gegenüberstellung partitionierender Clusteringmethoden
  • Wie KNN ist auch K-Means sensibel gegenüber verschieden skalierten Merkmalen und profitiert stark von der z-Transformation.
  • K-Means ist nicht deterministisch und stark abhängig von der initialen Wahl der Zentroiden.
  • Nur Anwendbar, wenn der Mittelwert definiert ist.
  • Konvergiert zu einem lokalen Minimum der Inertia
  • Konvergiert in einer endlichen Anzahl von Schritten.
  • Laufzeitkomplexität pro Iteration beträgt
• Involvierte Definitionen:
  • Ungelabelter Datensatz
  • Heuristischer Algorithmus
  • Euklidische Norm
  • K-Means++
  • siehe auch KNN-Klassifikator / KNN-Regressor
• Veranstaltung: EML
• Referenz: @thimm2024 (Abschnitt 3.1.1, Algorithmus 1)

⠀

Definition: K-Means-Clustering

Sei ein ungelabelter Datensatz mit .

Als K-Means-Clustering bezeichnen wir einen Algorithmus der Clusteranalyse, der einen Datensatz iterativ so in Teilmengen partitioniert, dass die Summe der euklidischen Distanzen der Datenpunkte zu dem Mittelpunkt des ihnen zugewiesenen Clusters minimal ist.

Die zwei gängigsten (heuristischen) Algorithmen sind der Lloyd- und der MacQueen-Algorithmus.

Algorithmus: Lloyd-Algorithmus

Sei ein ungelabelter Datensatz.

Der Lloyd-Algorithmus (auch naiver K-Means-Algorithmus) ist ein gängiger heuristischer Algorithmus zur Durchführung des K-Means-Clusterings.

Grob zusammengefasst:

0. Der Lloyd-Algorithmus wird mit einer gegebenen Menge von Clustermittelpunkten (auch Zentroiden) initialisiert.

1. Jedem wird derjenige Zentroid zugewiesen, der ihm (nach der euklidischen Norm) am nächsten ist.

2. Anschließend aktualisieren wir die Zentroiden , indem wir jeweils durch den Mittelpunkt derjenigen Datenpunkte ersetzen, die dem Cluster von zugewiesenen wurden.

3. Weiter mit 1, bis die Werte der konvergiert sind (heißt: bis sie sich nicht mehr verändern).

Algorithmus: Lloyd-Algorithmus

Eingabe: Datensatz , Clusteranzahl
Ausgabe: Zentroiden des finalen Clusterings

Wähle initiale Zentroiden (bspw. random, k-means++, …)
while nicht konvergiert do
for do

for do


return

Anmerkung

Nachteile des K-Means-Clusterings

• Wie KNN ist auch K-Means sensibel gegenüber verschieden skalierten Merkmalen und profitiert stark von der z-Transformation.
• K-Means ist nicht deterministisch und stark abhängig von der initialen Wahl der Zentroiden.
• Nur Anwendbar, wenn der Mittelwert definiert ist.

K-Means-Clustering mit scikit-learn

In Python erhalten wir ein K-Means-Clustering mit Lloyds-Algorithmus, zufälliger Clusterinitialisierung und durch:

X=((12,7),(10,8),(10,7.5),(15,5),(16,9),(18,8))
 
from sklearn.cluster import KMeans
kmeans = KMeans(algorithm= "lloyd", init="random", n_clusters=3).fit(X) 
 
kmeans.predict([(5,10)])

Herleitung

Für den Lloyd-Algorithmus gibt es eine sehr schöne analytische Herleitung.

Als Erinnerung: zur Evaluation des Clusterings nutzen wir das Trägheitsmaß

Der Algorithmus lässt sich in zwei Teilschritte schneiden:

1. Punkte zu Cluster zuweisen wählen
   • (das entspricht der Funktion )
2. Cluster-Zentren wählen
   • (das entspricht den )

Für beide Teilschritte können wir uns nun überlegen, wie wir minimieren können.

1. Punkte zu Cluster zuweisen wählen

Möchten wir bezüglich der Funktion minimieren, so geht das einfach, indem wir den Abstand minimieren - und das können wir machen, indem wir aus allen dasjenige auswählen, das am nächsten ist.

2. Cluster-Zentren wählen

Möchten wir bezüglich minimieren, ist das schon wesentlich komplizierter. Hierzu können wir die erste partielle Ableitung der -Funktion bezüglich der bilden und diese anschließend nullstellen.

Ob wir ein Minimum oder Maximum erhalten, können wir anschließend mit der zweiten Ableitung prüfen.

Wir erhalten mit der Kettenregel:

Stellen wir nun noch null, erhalten wir

was genau dem Lloyd-Algorithmus entspricht.

Bilden wir nun noch zur Prüfung die zweite Ableitung, erhalten wir

Nach der Unterscheidung von Maximum und Minimum über die zweite Ableitung folgt, dass es sich bei der Nullstelle tatsächlich um ein Minimum handelt - was zu zeigen war.