01 K Means Clustering

Einstieg in das Thema

Was brauchst du als Basiswissen?

Es ist sinnvoll, wenn du "K nächste Nachbarn" verstanden hast.

Worum geht es?

In "k nächste Nachbarn" testest du, zu welchem Bereich ein neues Element gehört. Die Einteilung der Gruppen war logisch, die Kriterien transparent. Und sie waren dir bereits gegeben.

Stell dir nun vor, du musst selbst eine Einteilung finden, und zwar erst einmal unabhängig von möglichen Eigenschaften. Darum geht es nun. Du siehst also eine Punktwolke und musst - zuerst durch Ansehen, später durch Berechnen - eine Einteilung finden.

Was ist das Ziel?

Du erkennst, dass ein System auch ohne große Interaktion von außen mit Daten umgehen - also mit diesen etwas lernen - kann.

Erarbeitung

Theorie

Aufgaben zur Orientierung

Aufgabe 1
Du siehst ein Bild. Teile dieses in zwei Bereiche (Cluster) und gib die Punkte für jedes Cluster an.
Aufgabe 2
Du siehst ein Bild. Teile dieses in zwei Bereiche (Cluster) und gib die Punkte für jedes Cluster an.
Aufgabe 3
Gib eine zweite, andere Einteilung an.
Aufgabe 4
Du siehst ein Bild. Teile dieses in zwei Bereiche (Cluster) und gib die Punkte für jedes Cluster an.
Aufgabe 5
Gib eine zweite, andere Einteilung an.
Aufgabe 6
Gib eine weitere Einteilung mit drei Clustern an.
Aufgabe 7
Gib eine weitere Einteilung mit vier Clustern an.
Aufgabe 8
Vervollständige: "Die Punkte eines Clusters haben zueinander ... Abstand"

Theorie 2: Auf zum Algorithmus

Aufgaben zur Übung - eindimensional

Aufgabe 9
Wir beginnen eindimensional, also auf einer Linie. A und B sind Start. Gib alle Abstände an (AC, AD, BC, BD).
Aufgabe 10
Ordne die Punkte C und D den Clustern zu.
Aufgabe 11
Gibt es Punkte, die nicht eindeutig zugeordnet werden können?
Aufgabe 12
Was würdest du in diesem Fall tun?
Aufgabe 13
Berechne für beide Fälle den Schwerpunkt und ordne erneut zu. Ändert sich im nächsten Schritt noch einmal die Zurodnung oder bleibt die erste Wahl stabil?
Aufgabe 14
Nun gibt es die Punkte A(6), B(15), C(12), D(10), E(1) und F(1).
Aufgabe 15
Gib die erste Clusterzuordnung an.
Aufgabe 16
Gib die beiden neuen Schwerpunkte an.
Aufgabe 17
Gib an, ob Punkte das Cluster ändern.

Aufgaben zur Übung - zweidimensional

Nun soll das Ganze zweidimensional erfolgen. Nutze dazu das

Aufgabe 18
Gib bitte die Punkte A(5,4), B(6,1), C(6,4), D(1,1) E(2,5), F(5,1), G(4,2), H(1,9) ein. "Berechne" führt jeweils einen Schritt aus. Gib an, wie oft sich der Schwerpunkt erkennbar ändert.
Aufgabe 19
Haben Punkte nach dem ersten Schritt das Cluster gewechselt?
Aufgabe 20
Gib nun andere Anfangswerte, indem du die Koordinaten von A oder B mit anderen Punkten tauschst. Ist die Berechnung der Cluster abhängig von der Wahl der Anfangswerte?
Aufgabe 21
Und noch ein schönes Beispiel: A(1,2), B(4,2), C(5,6), D(3,3), E(8,2), F(5,7) Wie ist die Clusteraufteilung nach dem ersten Schritt?
Aufgabe 22
Wie viele Schritte braucht bis zur finalen Einteilung?
Aufgabe 23
Wie ist die richtige Einteilung?

Kann man auch mehrere Gruppen machen? Na klar! Bei Anzahl der Cluster kannst du dies einstellen.

Aufgabe 24
Gib die Punkte A (1,3), B (7,9), C (6,8), D (3,7), E (2,6) ein. Vermute eine sinnvolle Clustereinteilung.
Aufgabe 25
Stelle nun am unteren Rand "Anzahl der Cluster" auf 3. War deine Vermutung korrekt?
Aufgabe 26
Wie aber erkennt man, welche Art besser ist? Gib für zwei und drei Cluster jeweils den Silhouettenkoeffizient an.
Aufgabe 27
Was bedeutet dieser Koeffizient? Vermute.
Aufgabe 28
Teste nun erneut mit A(5,6), B(6,1), C(6,6), D(1,1), E(2,5), F(5,1), G(4,2), H(1,9) I(3,6) und J(7,7) Wie viele Cluster sind dies (nur nach Anschauen)?
Aufgabe 29
Teste alle Clusteraufteilungen von 2 bis 6. Welche Aufteilung ist am besten?
Aufgabe 30
Welchen Silhouettenkoeffizient hatte diese Aufteilung?
Aufgabe 31
Nimm das Beispiel der Aufgabe mit der Einteilung in zwei Bereiche (A(1,2) ... F(5,7)). Packe weitere Punkte hinzu: G(7,1), H(9,3) und I(5,8). Nach wie vielen Schritten ist die Zweiereinteilung fest?
Aufgabe 32
Nach wie vielen Schritten ist die Dreiereinteilung fest?
Aufgabe 33
Welche Einteilung ist besser?
Aufgabe 34
Vervollständige: "Je höher der Sihouettenkoeffizient, desto ..."
Aufgabe 35
Was sind die größten und kleinsten möglichen Silhouettenkoeffizienten?
Aufgabe 36
Der Algorithmus ist durcheinander geraten. Ordne die Punkte.
Aufgabe 37
Damit ergeben sich k Cluster.
Aufgabe 38
Bilde den neuen Schwerpunkt des Clusters.
Aufgabe 39
Ordne den Clustern die Punkte zu. Jeder Punkt wird dem nächstliegenden Schwerpunktz zugeordnet.
Aufgabe 40
Wiederhole die nächsten beiden Schritte, bis sich die Schwerpunkte nicht oder nur noch wenig ändern.
Aufgabe 41
Ordne erneut alle Punkte den Clustern zu.
Aufgabe 42
Wähle zufällig k Startpunkte aus den gegebenen Punkten.
Aufgabe 43
Die Schwerpunkte bekommen die Koordinaten dieser Startpunkte.

Komplexe Aufgabe ohne KI

Ohne obige Tools, aber gern mit Taschenrechner, kannst du die ersten beiden Schritte einer Zuordnung und die erste Schwerpunktberechnung durchführen. Damit kannst du zeigen, dass du das Verfahren verstanden hast.

Aufgabe 44
Dir sind folgende Punkte gegeben: A(2,2) B(7,2) C(3,6) D(5,4) E(4.5,3) F(1,4).
Aufgabe 45
Nimm A und B als Startpunkt und ordne zu.
Aufgabe 46
Berechne für beide Cluster den Schwerpunkt.
Aufgabe 47
Ordne erneut zu und gib die Cluster mit den Punkten an.

Was muss man wissen/können?

Du weißt,

  • dass man auf mathematischem Weg eine Punktwolke in Bereiche einteilen kann,
  • dass man vorgeben muss, wie viele Bereiche (Cluster) man haben möchte und
  • man sich ausrechnen lassen kann, wie gut die Einteilung passt.

Du kennst

  • den Algorithmus,
  • weißt, wie man beginnt und
  • wann man stoppt.

Was können anschließende Themen sein?

Wir haben eine "flache Einteilung" vorgenommen, ein Punkt gehört entweder zu Cluster 1 oder zu Cluster 2. Man kann aber auch eine Hierarchie erstellen (lassen). Darum geht es jetzt.

Zurück
Weiter