10. k-Means-Clustering

Du kennst bereits den k-Nächste-Nachbarn-Algorithmus, ein Verfahren, das mit Trainingsdaten neue Daten klassifiziert. Nun betrachten wir k-Means-Clustering, einen Algorithmus, um Datenpunkte in sogenannte Cluster zu gruppieren.

Im Bereich der KI wird oft mit großen Datenmengen gearbeitet, die auf Muster untersucht und in Gruppen eingeteilt werden. Algorithmen dieser Art sind Verfahren der Clusteranalyse. k-Means ist so ein Algorithmus, der Datenpunkte ohne vorherige Kenntnis der Gruppenzugehörigkeit in \(k\) Cluster einteilt. Das macht k-Means zu einem unüberwachten Lernalgorithmus. Seine Stärke liegt in der effizienten Strukturierung großer Datensätze und dem Entdecken versteckter Muster.

Info

Maschinelles Lernen ist ein Teilgebiet der KI, in dem Algorithmen aus Daten lernen und Vorhersagen oder Entscheidungen treffen können. Algorithmen im Bereich des maschinellen Lernens haben das Ziel, große Datenmengen zu analysieren und Muster darin zu erkennen.

10.1. Überwachtes vs. unüberwachtes Lernen

Beide Algorithmen stammen aus dem Bereich Maschinelles Lernen, welches grob in überwachtes Lernen und unüberwachtes Lernen unterteilt wird. Beim überwachten Lernen wird ein Datensatz verwendet, der Trainingsdaten mit den zugehörigen Labels enthält. Das Modell lernt aus Beispielen, bei denen die richtigen Antworten bereits bekannt sind. Diese Methode eignet sich gut für Aufgaben wie Klassifikationen (z.B. Spam-Erkennung). Der k-Nächste-Nachbarn-Algorithmus ist ein solches Verfahren.

Beim unüberwachten Lernen sind die Trainingsdaten nicht gelabelt. Stattdessen versuchen unüberwachte Algorithmen, eigenständig Muster in den Daten zu erkennen. Clustering, wie k-Means, ist ein typisches Beispiel dafür. Der Algorithmus ermittelt Gruppen (Cluster) von ähnlichen Datenpunkten und hilft, ungeordnete Daten zu strukturieren.

10.2. Einführung in das Verfahren

k-Means-Clustering gehört zum unüberwachten Lernen. Es gibt keine vordefinierten Labels, sondern nur die rohen Daten. Das Ziel von k-Means ist es, die Daten in \(k\) Cluster zu unterteilen, wobei \(k\) die Anzahl der Cluster darstellt. Der Algorithmus ermittelt Zentroiden, auch Clusterzentren genannt. Das sind die Mittelpunkte, um die sich die Cluster bilden. Means steht dabei für den Durchschnitt, da die Zentroiden als Durchschnitt der zugehörigen Datenpunkte im Cluster berechnet werden. Am Ende sind die Daten innerhalb eines Clusters homogener als zu den Daten in anderen Clustern.

In einfachen Beispielen könnten wir die Cluster auch mit dem Auge erkennen und auch ablesen, welche Zahl für \(k\) sinnvoll wäre. Bei großen Datenmengen oder nicht eindeutigen Clustern benötigen wir dann aber die Hilfe des Algorithmus.

Aufgabe 1: Wie würdest du denn die folgenden Daten in Cluster aufteilen?

Abb. 10.1 Beispiel von einfacher Verteilung von Datenpunkten

Lösung

Abb. 10.2 Ergebnis des k-Means-Clustering mit k=3

Es ist recht offensichtlich, dass die Datenpunkte in 3 Cluster aufgeteilt werden können.

Aufgabe 2: Wenn du dir das nächste Beispiel anschaust: welche Cluster-Einteilung würdest du hier vornehmen?

Abb. 10.3 Beispiel von komplexer Verteilung von Datenpunkten

Lösung

Abb. 10.4 Ergebnis des k-Means-Clustering mit k=4

Dieses Beispiel ist nicht so trivial wie das vorige. Mit bloßem Auge lassen sich die Cluster nicht ablesen.

Mit Hilfe des k-Means-Clustering können die Daten also sinnvoll unterteilt werden. Aber wie macht der Algorithmus das überhaupt? 🤔

10.3. Der k-means-Clustering Algorithmus

Try it!

Auf dieser toll programmierten Seite kann man den Algorithmus mit verschiedenen Datensammlugen graphisch nachspielen!

Der Ablauf des k-means-Clustering Algorithmus wird in folgende Schritte aufgeteilt:

Wichtig

Auswahl der Anzahl der Cluster (\(k\))
Bevor der Algorithmus gestartet werden, muss die Anzahl der Cluster \(k\) festgelegt werden. Diese Zahl bestimmt, in wie viele Gruppen die Datenpunkte aufgeteilt werden sollen.

1. Initialisierung der Zentroiden
Als nächstes werden \(k\) Datenpunkte aus den Daten oder \(k\) zufällige Punkte ausgewählt, um die anfänglichen Zentroiden (Cluster-Zentren) zu bestimmen.

2. Zuweisung der Datenpunkte und Bildung der Cluster
Jeder Datenpunkt wird dem nächstgelegenen Zentroiden zugewiesen. Dies wird durch die Distanzmaße zu allen Zentroiden bestimmt (z.B. mittels Euklidischer Distanz oder Manhattan-Distanz).

3. Aktualisierung der Zentroiden
Die Zentroiden werden neu berechnet, indem der Durchschnitt (Mean) aller Punkte innerhalb eines Clusters berechnet wird.

4. Wiederholung der Schritte 3 und 4
Die Schritte 2 und 3 werden solange wiederholt, bis sich die Zentroiden nicht mehr ändern oder eine maximale Anzahl an Iterationen erreicht ist.

Versuche mal zu überlegen, worin das Ziel des Algorithmus besteht? Denke dabei an die Beziehung der Datenpunkte innerhalb eines Clusters und Datenpunkte aus verschiedenen Clustern.

Lösung

Folgende Kriterien sind das Ziel:

• Die Ähnlichkeit der Datenpunkte innerhalb der einzelnen Cluster soll möglichst hoch sein.

• Die Ähnlichkeit der Datenpunkte zwischen den einzelnen Clustern soll möglichst gering sein.

Fazit: Die Datenpunkte innerhalb eines Cluster sollen eine höchstmögliche Homogenität haben.

Frage: Warum benötigt es in der Regel mehrere Durchgänge (Iterationen), um die Cluster vollständig zu bilden?

Lösung

Der k-means Algorithmus braucht in der Regel mehrere Durchgänge, um die Cluster korrekt zu finden. Das liegt daran, dass die Zentroiden (also die Mittelpunkte der Cluster) anfangs zufällig gewählt werden. Am Anfang sind diese Zentroiden oft nicht optimal, da sie weit von den eigentlichen Clustern entfernt liegen können.

In jeder Iteration passiert Folgendes:

1. Jeder Datenpunkt wird dem nächstgelegenen Zentroiden zugewiesen, wodurch sich Cluster bilden oder auch ändern. Es ist gut möglich, dass ein Datenpunkt nun in einem anderen Cluster landet. Damit ändert sich dann wiederum auch die Position des Zentroiden.

2. Die Zentren werden dann neu berechnet, indem der Durchschnitt der Punkte in jeder Gruppe genommen wird.

3. Dieser Prozess wiederholt sich: Die Datenpunkte werden immer wieder neu zugeordnet, und die Zentren verschieben sich dabei nach und nach.

Das Ziel ist, dass die Zentroiden eine Position erreichen, bei der sie sich gar nicht mehr oder nicht mehr groß bewegen, also eine stabile Lösung finden. Diese Stabilität wird auch Konvergenz genannt. Je nach Anfangslage der Zentroiden kann mehrere Interationen dauern, bis der Algorithmus eine stabile Gruppierung erreicht hat. Deshalb sind mehrere Iterationen nötig, um sicherzustellen, dass die Cluster gut und sinnvoll gebildet werden.

Dieses iterative Verfahren führt schließlich zu einer optimalen Gruppierung der Datenpunkte, wobei jeder Punkt in dem Cluster landet, das am besten zu seinen Eigenschaften passt.

Hilfreiche Quellen fürs weitere Verständnis

• KI Buch: Wetterdaten-Beispiel

• k-Means Clustering visualisiert

• k-Means Clustering visualisiert mit Distanzenberechnug

10.4. Reale Anwendungsbeispiele

Welche realen Anwendungsbeispiele kannst du dir vorstellen, bei denen das k-means Clustering eingesetzt werden könnte?

Überlege dabei, in welchen Bereichen es wichtig sein könnte, Daten in Gruppen aufzuteilen, ohne dass bereits vorgegeben ist, zu welcher Gruppe ein Datenpunkt gehört. Welche Situationen kennst du, in denen Menschen, Dinge oder Objekte aufgrund ihrer Ähnlichkeit in Gruppen eingeteilt werden? Es gibt hier keine richtige Antwort, nur eine Auswahl an möglichen Einsatzszenarien.

Beispiele

• Marketing: Kunden in verschiedene Segmente aufteilen. Dadurch können Unternehmen gezieltere Werbung schalten und ihre Produkte effizienter an die verschiedenen Kundengruppen anpassen.

• Bildanalyse: ähnliche Regionen in Bildern finden. Das ist besonders nützlich für die Objekterkennung. Hierbei hilft der Algorithmus, verschiedene Objekte in einem Bild zu identifizieren und zu klassifizieren.

• Biologie: Forscher nutzen den Algorithmus, um ähnliche Gene oder Spezies zu gruppieren. Dies kann helfen, neue Erkenntnisse über genetische Verbindungen und Unterschiede zu gewinnen und die Evolution besser zu verstehen.

• Textanalyse: Zum Beispiel kann der Algorithmus eingesetzt werden, um ähnliche Dokumente oder Artikel zu gruppieren, was bei der Organisation großer Textmengen hilfreich ist. In der Finanzwelt wird k-Means genutzt, um riskante von nicht riskanten Krediten zu unterscheiden, indem ähnliche Kreditprofile gruppiert werden.

10.5. Ein konkretes Beispiel: Clustering von Obstsorten

Wir möchten uns gesünder ernähren und wollen mehr Obst essen. Die WHO empfiehlt Obst mit hohen Fruchtzuckergehalt in geringen Maßen zu genießen. Obst mit einem hohen Wassergehalt führt zu einer höheren Sättigung. Nehmen wir an, wir haben Daten über Obstsorten mit Informationen wie u.a. Wassergehalt und Fruchtzuckergehalt. Wir möchten ähnliche Obstsorten in Clustern gruppieren, sodass die Obstsorten möglichst homogen sind. Anhand der Cluster können wir dann entscheiden, welches Obst wir in welchen Mengen essen können.

Wir spielen dieses Beispiel mal nach und schauen uns das Ergebnis an. Die zugeörigen Daten zu unseren Obstsorten sind:

Obst	Wassergehalt	Fruchtzuckergehalt
Apfel	85	10
Birne	83	10
Banane	75	12
Orange	87	8
Weintrauben	81	16
Erdbeere	91	5
Wassermelone	92	6
Mango	83	14

Keine übergroße Menge aber es ist schon mal nicht einfach, hier ad hoc eine konkrete Hilfestellung für unsere Obstfrage zu erhalten.

In Abb. 10.5 ist die Sammlung von Obstsorten visualisiert: 🍎 (Apfel), 🍐 (Birne), 🍌 (Banane), 🍊 (Orange), 🍇 (Weintrauben), 🍓 (Erdbeere), 🍉 (Wassermelone), 🥭 (Mango). Wir möchten diese Obstsorten nun basierend auf Wasser- und Fruchtzuckergehalt in Cluster aufteilen.

Abb. 10.5 Obstsorten visualisiert nach Wassergehalt und Fruchzuckergehalt

Aufgabe 1: Wie würdest du die Obstsorten in Cluster aufteilen? Überlege dabei, wieviele Cluster sinnvoll wären, also welchen Wert \(k\) einnehmen würde.

Ergebnis k-Means

Abb. 10.6 k-Means-Clustering der Obstsorten mit k=3

Aufgabe 2: Versuche mal, das ermittelten Cluster in eigenen Worten zusammenzufassen.

Beschreibung des Ergebnisses

Der Algorithmus hat die Obstsorten in 3 Cluster aufgeteilt, deren Datenpunkte die folgenden Merkmale aufweisen:

1. 🍌 (Banane), 🍇 (Weintrauben), 🥭 (Mango): hoher bis sehr hoher Fruchtzuckergehalt mit mittlerem Wassergehalt

2. 🍎 (Apfel), 🍐 (Birne), 🍊 (Orange): mittlerer Fruchtzuckergehalt mit hohem Wassergehalt

3. 🍓 (Erdbeere), 🍉 (Wassermelone): niedriger Fruchtzuckergehalt mit sehr hohem Wassergehalt

Hast du die Einteilung von k-Means auch so überlegt oder hattest du eine andere Vorstellung? Was hälst du denn von dieser Einteilung im Vergleich zur vorigen Lösung?

Ergebnis k-Means Variante 2

Abb. 10.7 k-Means-Clustering der Obstsorten mit k=3 Variante 2

Überlege mal einen Moment, wie der Algorithmus bei gleichen Daten zu diesen unterschiedlichen Ergebnisse kommen kann.

Tipp

Was könnte der Algorithmus zu Beginn anders gemacht haben, damit unterschiedliche Ergebnisse zustande kommen?

Tipp, wenn du noch keine Idee hast

Wie werden die Zentroiden initialisiert und wie kann dieses Verfahrensweise zu unterschiedliche Ergebnissen führen?

Lösung

Die unterschiedlichen Ergebnisse sind eine Folge davon, dass der Algorithmus mit zufälligen Startpunkten arbeitet. Je nachdem, wo die Zentroiden am Anfang liegen, teilt der Algorithmus die Punkte unterschiedlich ein. Das zeigt, dass k-Means manchmal unterschiedliche Ergebnisse liefern kann, auch wenn die Daten gleich bleiben.

• Wenn ein Start-Zentroid mitten in einer dichten Datenmenge liegt, zieht er schnell viele Punkte an.

• Liegt ein anderer Start-Zentroid weit weg, wird er vielleicht nur wenige Punkte anziehen. Der Algorithmus findet also nicht immer die ‘beste’ Lösung, sondern eine, die von den Startbedingungen abhängt

10.5.1. Initialisierung der Clusterzentren mit k‑means++

[k-means++(https://de.wikipedia.org/wiki/K-Means-Algorithmus)] ist eine verbesserte Methode zur Initialisierung der Clusterzentren beim k-means-Clustering. Es verbessert die Qualität und Effizienz des Algorithmus durch folgende Schritte:

1. Erster Startpunkt:

   • Ein Punkt wird zufällig aus den Daten gewählt.

2. Gewichtete Auswahl der weitere Startpunkte:

   • Für jeden weiteren Startpunkt wird ein Punkt basierend auf seiner Distanz zu den nächsten bereits gewählten Startpunkten ausgewählt:

     • Punkte, die weiter entfernt sind, haben eine höhere Wahrscheinlichkeit, ausgewählt zu werden.

     • Die Wahrscheinlichkeit ist proportional zum Quadrat der Distanz zum nächsten Startpunkt (\(D^2\)).

3. Wiederhole Schritt 2, bis \(k\) Startpunkte bestimmt sind.

4. Führe anschließend das normale k-means-Verfahren durch.

Vorteil: Die Startpunkte werden optimal verteilt, was zu schnellerer Konvergenz und besseren Clustering-Ergebnissen führt.

Wie funktioniert die gewichtete Auswahl genau?

Angenommen, es gibt 5 Punkte mit diesen Distanzen zu den bestehenden Zentren:

Punkt	Entfernung \(D\)	Gewicht \(D^2\)	Wahrscheinlichkeit
\(A\)	\(1\)	\(1^2 = 1\)	\(1 / (1 + 9 + 25 + 36 + 64) = 1/135 \approx 0.74\%\)
\(B\)	\(3\)	\(3^2 = 9\)	\(9 / 135 \approx 6.67\%\)
\(C\)	\(5\)	\(5^2 = 25\)	\(25 / 135 \approx 18.52\%\)
\(D\)	\(6\)	\(6^2 = 36\)	\(36 / 135 \approx 26.67\%\)
\(E\)	\(8\)	\(8^2 = 64\)	\(64 / 135 \approx 47.41\%\)

Punkt \(E\) hat die größte Wahrscheinlichkeit, gewählt zu werden, aber nicht zu 100%. Es kann jedoch auch jeder andere Punkt gewählt werden, abhängig von seiner Wahrscheinlichkeit.

10.6. Ein Beispiel zum Nachrechnen

Du weißt nun, wie der Algorithmus funktioniert und zu welchen Ergebnissen er führen kann. Am besten kannst du das nachvollziehen, indem du den Algorithmus selbst mal durchführst. Lade dir dieses Aufgabenblatt herunter und bearbeite es. Die Anweisungen findest du dem Arbeitsblatt. Viel Erfolg 💪

10.7. Die richtige Wahl für \(k\) mit der Elbow-Methode

Bisher haben wir für unsere Beispiele \(k\) so gewählt, dass es dem Verständnis passte. Doch in der Praxis stellt sich oft die Frage: Wie wähle ich die optimale Anzahl von \(k\) Clustern ?

Hier kommt die Elbow-Methode ins Spiel. Sie hilft uns, auf systematische Weise die Anzahl der Cluster zu bestimmen, die sowohl eine gute Datenaufteilung gewährleistet als auch unnötig viele Cluster vermeidet.

Die Idee der Methode ist wie folgt:

• Wir berechnen die sogenannte Trägheit (Summe der Abstände der Datenpunkte zu ihren Clusterzentren) für verschiedene Werte von \(k\).

• Die Trägheit nimmt mit steigender Clusteranzahl \(k\) ab, weil mehr Cluster zu kleineren Distanzen führen.

• Jedoch flacht die Abnahme ab, und ab einem bestimmten Punkt lohnt es sich nicht mehr, die Anzahl der Cluster weiter zu erhöhen. Dieser Punkt wird als Knickpunkt (Elbow) bezeichnet.

Abb. 10.8 Demonstration der Elbow-Methode

Die optimale Anzahl der Cluster \(k\) ist genau dort, wo dieser Knickpunkt liegt. Dies ist der Punkt, an dem die Verbesserung durch mehr Cluster stark nachlässt, und wir eine gute Balance zwischen Genauigkeit und Einfachheit erreichen.

Warum funktioniert die Elbow-Methode?

Die Methode basiert auf der Idee, dass eine kleine Anzahl von Clustern zu einer schlechten Gruppierung führt, während eine zu große Anzahl von Clustern unnötig ist und zu Overfitting führen kann. Der Knick bei Anzahl der Cluster \(= 2\) zeigt den Punkt, an dem sich der Aufwand für mehr Cluster nicht mehr lohnt.

Mit der Elbow-Methode können wir also datengetrieben und anschaulich entscheiden, wie viele Cluster sinnvoll sind, anstatt dies nur durch Intuition oder Versuch und Irrtum zu bestimmen.