Was sind Entscheidungsbäume?
Entscheidungsbäume ...
... stellen einen Klassifikator dar, der unbekannte Daten klassifiziert.
... werden von Expert*innen erstellt oder aus Trainingsdaten gelernt.
Beispiel
Der folgende Entscheidungsbaum zeigt, wie eine Bank bei einer Kreditvergabe entscheiden könnte.
4-6 Dimension
Bsp. Vektor
Semantik
Innere Knoten stellen Entscheidungen dar.
im inneren Knoten stehen Attribute
Kanten stellen Ausgang der Entscheidung dar.
An Kanten stellen alle möglichen Attributwerte/ Dimensionsausprägungen
Blätter entsprechen der Klassifikation
Hinweis —> Es muss nicht zwingend ein binärer Baum (2 Kanten je Knoten) sein!
Welche Algorithmen werden zur Entwicklung von Entscheidungsbäumen genutzt?
Entscheidungsbäume werden aus Trainingsdaten gelernt.
Hierzu wurden viele Algorithmen vorgestell.
Beispiele:
CART (Breiman et al. 1984))
ID3 (Quinlan 1986)
C4.5 (Quinlan 1993)
Was ist ID3?
Iterative Dichotomiser 3
Lernen von Entscheidungsbäumen
Entropie-basierte Auswahl von Features
Greedy-Algorithmus (gierig, keine Entscheidung ist umkehrbar)
kann auch aus qualitative Daten arbeiten
Der ID3-Algorithmus beantwortet die folgende Frage:
Welches Feature des Trainingsdatensatzes steht in der Wurzel des Entscheidungsbaums?
bzw.
Welches Attribut steht in der Wurzel eines Teilbaums?
ID3 ist iterativ
Das gleiche Vorgehen zur Auswahl des Features des Wurzelknotens kann mit den verbleibenden Features in weiteren Iterationen rekursiv wiederholt werden.
Wie lautet der Ablauf von ID3? (Code)
Was ist eine Partition?
Gegeben sei ein Datensatz T von Personen mit den Features Größe, Gewicht, Geschlecht, Geburtsdatum, Haarfarbe, Name, Vorname.
In den Featurevektoren sind im Feature Haarfarbe die Werte schwarz, braun, blond, rot vorhanden.
Wird das Feature Haarfarbe zur Partitionierung ausgewählt, so entstehen die vier Partitionen Tschwarz, Tbraun, Tblond sowie Trot . Der jeweiligen Partition gehören die Featurevektoren an, die im Attribut Haarfarbe den entsprechenden Wert enthalten
Was ist Informationsgewinn und was wird zu dessen Berechnung benötigt?
Zum Verständnis des Begriffs Informationsgewinn müssen zunächst die Konzepte der Entropiereduktion, der Entropie sowie des Informationsgehalts geklärt werden, die aufeinander aufbauen.
Der Informationsgewinn G (engl. Information Gain) beschreibt den Gewinn an Information, der durch Auswahl des Features (Attributs) a zur Partittionierung entsteht.
Der Begriff liegt in der Informationstheorie nach Shannon begründet und ist gleichbedeutend mit der Reduktion von Entropie H.
Um also den Gewinn an Information zu berechnen, muss die Reduktion von Entropie berechnet werden
Was ist die Entropiereduktion und wie wird sie berechnet?
H(T) = Trainingsdatensatz
∑v = alle Values die das Attribut annehmen kann
Tv = Partitionen
Entropiereduktion bedeutet Unordnung maximal beseitigen
Was ist die Entropie?
Die Entropie ist ein Maß für die Unsicherheit oder Unordnung. (Wie unvorhersagbar ist das Ergebnis Label —> unterschiedliche Wahrscheinlichkeiten)
Je höher die Entropie, desto unsicherer, ungeordneter oder unvorhersehbarer ist ein System.
Shannon hat die Entropie im Kontext der Informationstheorie definiert als den mittleren Informationsgehalt bzw. die Informationsdichte einer Nachricht.
Informationsgehalt
Bestimmung des Informationsgehalts des Ereignisses, bei einem fairen Münzwurf Kopf zu werfen
Es gibt die beiden Zeichen kopf und zahl mit den Auftrittswahrscheinlichkeiten
Wie berechnet man die Entropie?
Die Entropie war definiert als der mittlere Informationsgehalt einer Nachricht.
Zur Berechnung der Entropie wird daher über alle möglichen Informationsgehalte gemittelt. Konkret wird das gewichtete Mittel berechnet und die Auftrittswahrscheinlichkeit als Gewicht angenommen.
Summe Auftrittswahrscheinlichkeiten * Informationsgehalt
Wie berechnet sich der Informationsgewinn bzw. die Entropiereduktion?
= Gewicht (wie groß ist die Partition im Verhältnis zu T)
= Auftrittswahrscheinlichkeit * Gewicht
Wie wird der Informationsgewinn maximiert?
Bei (positivem) Informationsgewinn bzw. positiver Entropiereduktion wird das System durch Auswahl des Attributs a und der entsprechenden Partitionierung demnach vorhersehbarer und geordneter als ohne diese Partitionierung.
Nun wird aus allen Featrues (Attributen) dasjenige ausgewählt, dass den größtmöglichen Informationsgewinn bietet, das System also bestmöglich ordnet oder vorhersagbar macht.
Das entspricht natürlich genau der Idee des Entscheidungsbaums: Beginnend an der Wurzel und dann an jedem inneren Knoten eine best- / schnellstmögliche Klassifikation.
Der Datensatz enthält 14 Featurevektoren mit den Features outlook, temprature, humidity und wind sowie dem Label play_tennis.
Der Datensatz beschreibt, ob unter Berücksichtigung der Vorhersage, der Temperatur, der Luftfeuchtigkeit und des Windes Tennis gespielt wird. Dabei ist play_tennis das Label und somit das Ziel der Klassifikation.
ZSpielen = {Yes, No}
Da die Auftrittswahrscheinlichkeiten hier nicht bekannt sind, können bzw. müssen näherungsweise die relativen Häufigkeiten verwendet werden.
Somit ergibt sich die Entropie zu
Was passiert wenn eine Partition nicht rein ist?
Ist eine Partiton Tv nicht rein, enthält also nicht nur Featurevektoren einer Klasse,
wird der Knoten ein innerer Knoten.
bildet der Knoten die Wurzel eines neuen Teilbaums.
wird im Teilbaum nicht mehr der gesamte Datensatz betrachtet, sondern nur noch die Partition Tv (Filter werden zusammengenommen)
werden im Teilbaum nur noch die Features betrachet, die von der Wurzel bis zu diesem Knoten noch nicht betrachtet wurden.
Was ist die max-depth?
—> Tiefe des Baums beschränkbar
—> Risiko falsche/ uneindeutige Zuordnung zu treffen
—> ergibt sich aus Business und Data Understanding ob sinnvoll oder nicht
Last changed10 months ago
