02 Hierarchisches Clustering

Einstieg in das Thema

Was brauchst du als Basiswissen?

Du kennst k-means-clustering.

Worum geht es?

K-means-clustering zerlegt deine Daten Bereiche, die hoffentlich einen Sinn ergeben. Jeder Punkt war in einem Cluster, in einem Bereich.

Aber auch Bereiche können hierarchisch angeordnet sein. Cluster ergeben wieder Cluster. Eine Meise ist ein Tier, aber auch ein Vogel, aber kein Zugvogel.

Was ist das Ziel?

Du siehst, dass man Daten auch hierarchisch ändern kann, ohne sie genau zu kennen. Und du kennst das Vorgehen dazu.

Erarbeitung

Theorie

Aufgaben

Gegeben ist dir eine Punktwolke.

Aufgabe 1

Gib an, welche Punkte ein Cluster bilden können.

Aufgabe 2

Welche der Cluster könnte man zu einem neuen Cluster zusammenfügen?

Schau dir nun das zweite Bild an. Wieder hast du Punkte gegeben.

Aufgabe 3

Welche Punkte können nun auf den ersten Blick Cluster bilden?

Aufgabe 4

Nun kommt die zweite Runde. Welche Cluster könnten wieder Cluster bilden?

Aufgabe 5

Findest du noch eine dritte Runde?

Nun arbeitet der Algorithmus aber nicht mit mehreren Punkten oder Clustern gleichzeitig, sondern nimmt immer nur zwei(!) Elemente. Ob ein abgegrenzter Bereich entstanden ist, müssen wir selbst entscheiden. Was uns bei dieser Entscheidung hilft, schauen wir uns später an. Jetzt geht es ums Rechnen.

Für folgende Aufgabe sind die Koordinaten der Punkte gegeben:

        A(1,1)
        B(2,5)
        C(4,5)

Aufgabe 6

Suche das Paar mit dem kleinsten Abstand. Gib diesen an.

Aufgabe 7

Nun bilden diese beiden Punkte ein Cluster. Es soll der Abstand des dritten Punktes zum Cluster ermittelt werden. Berechne zuerst den Abstand des dritten Punktes zu den Punkten des Clusters.

Aufgabe 8

Bilde den Mittelwert der beiden Abstände.

Es kommt ein Punkt hinzu:

        A(1,1)
        B(2,5)
        C(4,5)
        D(5,6)

Aufgabe 9

Welche beide Punkte haben zueinander wohl den kleinsten Abstand? Berechne diesen.

Aufgabe 10

Nun sind vier Punkte dabei. Es kann nun sein, dass die anderen beiden ein Cluster bilden oder dass einer der beiden Punkte besser zum bereits existierenden Cluster passt. Berechne zuerst den Abstand der beiden einzelnen Punkte.

Aufgabe 11

Berechne weiterhin den Abstand des Clusters zum nächstliegenden Punkt (Beachte, es wird der Abstand zu beiden Punkten des Clusters gebildet und gemittelt).

Aufgabe 12

Welche Entscheidung hast du getroffen?

Du hast nun Punkte oder Cluster mit vielen Punkten. Willst du den Abstand von Punkt zu Cluster, dann musst du den Abstand zu jedem Punkt des Clusters berechnen, addieren und durch die Zahl der berechneten Abstände teilen (also den Mittelwert bilden).

Möchtest du den Abstand von zwei Clustern mit vielen Punkten berechnen, musst du alle möglichen Abstände (jeder zu jedem) berechnen und dann wieder mitteln.

Aufgabe 13

Mache das nun für den letzten Schritt. Welchen Abstand hast du ermittelt?

Du kannst deine Ergebnisse nun prüfen. Trage die Punkte (sinnigerweise auf dem jeweils Zehnfachen) ein und lasse dir die (zehnfachen) Abstände anzeigen, indem du mit der Maus über die waagerechten Linien fährst.

Aufgabe 14

Bist du zur gleichen Entscheidung gekommen wie das Applet? Oder hast du etwas anders gemacht?

Probiere das Applet auch ruhig mit weiteren Punkten aus und schaue, ob du die Entscheidung nachvollziehen kannst. Gönne dir gern 10min oder mehr zum Spielen. Der Baumgraph sieht nur nicht immer gut aus, weil Linien sich überdecken.

Im Baum kann man leider nicht ohne Weiters erkennen, ob drei oder vier Punkte nahe beieinander liegen und damit eine Einheit bilden. Wir nähern uns mit ein paar Überlegungen. Nimm zum Forschen das Applet von oben.

Aufgabe 15

Was passiert mit dem Abstand, wenn man im Baum immer weiter nach oben geht?

Aufgabe 16

Was passiert mit dem Abstand, wenn man im Baum weiter nach oben geht, wenn Punkte nahe beieinander liegen?

Aufgabe 17

Und was passiert mit dem Abstand, wenn plötzlich Punkte oder Cluster weitab liegen?

Aufgabe 18

Wie kann man auf diese Art entscheiden, ob man zusammengehörige Punkte gefunden hat?

Nun sollst du deine These testen. Dazu gibt es ein erweitertes Applet. In diesem Kannst du auch mehrere Werte - immer durch Komma getrennt - eingeben. Achtung, ein Beispiel wird immer geladen, aber du kannst das überschreiben und den Baum - das Dendrogramm - zeichnen lassen.

Übernimm folgende Punkte in das Applet und lass das Dendrogramm neu zeichnen.

        A,1,3
        B,8,2
        C,7,2
        D,7,5
        E,8,6
        F,9,1
        G,2,3
        H,1,8
        I,7,7
        J,2,7
        K,1,2
        L,6,9
        M,7,10
        N,8,10

Aufgabe 19

Welche Punkte liegen wohl nahe beieinander und bilden Cluster?

Aufgabe 20

Welche Cluster können neue Cluster bilden, liegen also beieinander? Beachte, dass auch mehr als zwei Cluster ein neues Cluster bilden können.

Nun sollen auch praktische Beispiele kommen. Für die folgende Aufgabe hast du Autos, Gewicht in Tonnen, Leistung in Stufen von 1 bis 10, und die Geschwindigkeit in 100km/h.

        A, 0.8, 2, 1.1
        B, 1.0, 3, 1.2
        C, 1.1, 3, 1.0
        D, 1.2, 4, 1.3
        E, 1.5, 6, 1.8
        F, 1.6, 6, 1.7
        G, 1.8, 8, 2.0
        H, 2.0, 9, 2.2
        I, 2.2, 10, 2.3
        J, 3.0, 7, 1.9
        K, 6.0, 4, 1.2
        L, 8.0, 3, 1.0
        M, 10.0, 2, 0.9
        N, 12.0, 2, 0.8
        O, 7.5, 3, 1.1

Aufgabe 21

Übernimm die Daten ins Applet. Welche Fahrzeuge bilden Gruppen? Also welche Fahrzeuge würden in "k means clustering" zusammengefasst werden?

Aufgabe 22

A ist ein Kleinwagen. Welche Fahrzeuge könnten auch Kleinwagen sein?

Aufgabe 23

D ist kein Kleinwagen. Wie könnte man die Fahrzeugklasse, zu der er gehört, auch nennen?

Aufgabe 24

Würdest du auf Basis der Abstände sagen, dass das Cluster mit K Ähnlichkeiten hat zum Cluster mit M?

Aufgabe 25

M ist ein großer LKW. Was könnte K sein?

Dir sind sicher schon die Einstellmöglichkeiten für die gewichte aufgefallen. Unser Autobeispiel hat Werte, die so nicht im Prospekt stehen. Dort steht 1400kg Leergewicht statt 1,4t. Ersetze nun alle Massen, also die ersten Zahlen, durch ihr Tausendfaches.

        A, 800, 2, 1.1
        B, 1000, 3, 1.2
        C, 1100, 3, 1.0
        D, 1200, 4, 1.3
        E, 1500, 6, 1.8
        F, 1600, 6, 1.7
        G, 1800, 8, 2.0
        H, 2000, 9, 2.2
        I, 2200, 10, 2.3
        J, 3000, 7, 1.9
        K, 6000, 4, 1.2
        L, 8000, 3, 1.0
        M, 10000, 2, 0.9
        N, 12000, 2, 0.8
        O, 7500, 3, 1.1

Aufgabe 26

Hat sich der Baum geändert?

Aufgabe 27

Schreibe zwei Fahrzeuge auf, die bei den Angaben in Tonnen Ähnlichkeiten zu A hatten. Welches Fahrzeug gehört nach dem zeichnen nicht mehr dazu?

Aufgabe 28

Schreibe zwei Fahrzeuge auf, die bei den Angaben in Tonnen Ähnlichkeiten zu E hatten. Welches Fahrzeug gehört nach dem zeichnen nicht mehr dazu?

Aufgabe 29

Was könnte Ursache des Problems sein?

Aufgabe 30

Schreibe in das Feld "Gewichte" für den ersten Wert 0.001.

Aufgabe 31

Formuliere eine allgemeine Regel zum Umgang mit den Daten. (Hinweis: Vielleicht ist dir ein ähnliches Problem im vorherigen Kapitel schon begegnet.)

Zusammenfassung

Was muss man wissen/können?

Du weißt,

dass man Daten auch vertikal Clustern kann,
dass das die Möglichkeit eröffnet, Cluster von Clustern zu finden und
dass das Finden der Cluster eine Betrachtung der Veränderung der Abstände notwendig macht.

Was können anschließende Themen sein?

Abstände waren für dich einfach Entferungen, die man auch mit dem Pythagoras berechnen kann. "Abstände" sind aber ein großes Thema. Geht es zum Beispiel nur um Merkmale, die vorhanden sind oder eben auch nicht, dann ist ein anderer "Abstand" auch praktikabler (und einfacher).