03 Entscheidungsbäume

Klassifikationsverfahren

Entscheidungsbäume

Es wird wie beim Spiel “Wer bin ich” versucht Fragen zu stellen, um die Menge aller Optionen schnell abzugrenzen und in sortierte Bereiche zu trennen.

Dabei sind die Fragen nur sinnvoll, wenn sie die Datenmenge tatsächlich trennen. Eine Abfrage die in beiden Fällen auf unsortierte Daten hinausläuft ist nicht nützlich.

Bewertung eines Baumes

Man möchte Bäume, die möglichst wenig Fehler machen und in wenigen Schritten zum Erfolg finden. Jedoch ist es nicht sinnvoll, bis zu perfekten Ergebnissen zu trainieren. Besonders hier können falsche Messungen viel unnötige Komplexität einführen.

Ein guter Baum ist also der kleinste von allen mit der selben Fehlerrate und der mit der geringsten Fehlerrate von allen mit der selben Größe.

Definition Größe

Die Größe eines Baumes kann verschieden definiert sein. Es kann nach der Höhe oder der Anzahl an Blättern gezählt werden. Auch die Pfadlängensumme - also die Menge aller Entscheidungen im gesamten Baum - kann verwendet werden.

Klausuraufgabe

ID3-Algorithmus berechnen.
Bzw Entropie und Information Gain verschiedener Entscheidungen vergleichen.

Entscheidungsbäume sind ein Werkzeug zur Klassifikation von Objekten.
Ein Klassifikationsmodell ist in der Lage, einen solchen Entscheidungsbaum zu erstellen.

Jeder Schritt soll die Datenmenge möglichst Sortenrein trennen

Es gibt eine unbegrenzte Menge korrekter Lösungsbäume, wobei die Qualität eines Baums anhand verschiedenen Kriterien bestimmt wird (Schlimmster-Worst-Case / Summe von Knoten / etc.)

Bewertung

Entscheidungsbäume sind gut nachvollziehbar und lassen sich anschaulich darstellen. Ebenfalls ist die Berechnung einer Vorhersage mit einem trainierten Baum sehr schnell.
Bei einer getroffenen Aussage lässt sich genau nachvollziehen welche Folge von Entscheidungen zum Ergebnis geführt hat.

Jedoch neigen diese Bäume zu Überanpassung und sind bei Datensätzen mit komplexeren Entscheidungsgrenzen nicht sehr akkurat. Da die Trennebenen nur Senk- oder Waagrecht verlaufen werden diese freier geformten realen Entscheidungsgrenzen nur selten exakt abgebildet.

TODO

TODO Hyperparameter beschreiben (Maximale Baumhöhe oder Knotenzahl - Seite 154)

ID3-Algorithmus

Liefert relativ gute, simple Bäume für Datensätze mit Nominalen Merkmalen (Funktioniert nicht bei stetigen Werten). Der Algorithmus ist auch bei vielen Features effizient

Es wird zu jedem Attribut eine Abfrage erstellt wenn die aktuelle Restmenge nicht ausreichend getrennt ist. Die exakte Wahl des Wertes bei dem getrennt wird ist zwischen verschiedenen Varianten des Algorithmus unterschiedlich.
Im Standardfall wird so gewählt, dass der “Information Gain” maximal ist.

Nach der Entscheidung für ein Kriterium wird rekursiv erneut gewählt, bis jedes Kriterium abgefragt wurde oder die Menge der verbleibenden Datenpunkte hinreichend gut getrennt ist.

Informationsgehalt

Dabei ist der Informationsgehalt $I(P(A))$ über den Eintritt eines Ereignis mit Eintrittswahrscheinlichkeit $P(A)$ folgendermaßen definiert.

$$I(P(A)):=-P(A)\cdot {\log }_2(P(A))$$

Es wird keine Information gewonnen wenn ein Test bezüglich eines Ereignisses durchgeführt wird dass sicher eintritt oder nicht eintritt.

Entropie

Sie ist ein Maß für den Mittleren Informationsgehalts eines Zufallsexperiments $V$ mit den möglichen Ausgängen $A_1,A_2,\dots ,A_i$

$$H(V):=-\sum _{i=1}^{n}P(A_i)\cdot {\log }_2(P(A_i))$$

Jeder einzelne Wert ist negativ, somit wird eine große negative Summe gebildet und in einem Schritt negiert um einen positiven Wert zu erhalten. Dabei wird nicht durch die Anzahl der Werte dividiert wie es beim Arithmetischen Mittel üblich ist. Die Gewichtung erfolgt durch die Multiplikation mit der Eintrittswahrscheinlichkeit. Da die Ereignisse konkurrieren normiert sich der Wert hier immer selbst.
Ein großer Wert der Entropie deutet auf sehr ähnliche Wahrscheinlichkeiten hin.

Eintrittswahrscheinlichkeiten

In unserem Fall werden die Häufigkeiten innerhalb der gemessenen Daten als Eintrittswahrscheinlichkeit verwendet.

Beispiel: Münzwurf

$$\text{Information Gain}=-0,5\cdot {\log }_2(0,5)$$

Da beide Möglichkeiten des Münzwurfs gleich wahrscheinlich sind berechnet sich die Anwendung der Formel zur Entropie also

$$\begin{array}{ll}H(V)& =-{\sum }_{i=1}^{2}0,5\cdot {\log }_2(0,5)\\ & =-2\cdot 0,5\cdot {\log }_2(0,5)\\ & =-1\cdot {\log }_2(2^{-1})\\ & ={\log }_2(2)\\ & =1\end{array}$$

Der Münzwurf hat also einen Entropiewert von $1Sh$

Bedingte Entropie

Es soll immer die Information als nächstes geprüft werden, die den größten Einfluss auf die Qualität der Schätzung hat.
“Wie unsicher ist $V$ wenn wir $W$ kennen?”

$$H(V\mid W)=\text{Bedingte Entropie}$$ $$H(V\mid W)=\sum _{j=1}^{s}P(B_j)\cdot H(V\mid B_j)$$

Eine geringe bedingte Entropie bedeutet, dass die Daten durch das Attribut gut getrennt werden.

Information Gain

Ein Maß für die Senkung der Entropie durch eine Entscheidung.

$$IG(V,W)=H(V)-H(V\mid W)$$

Da $H(V)$ an einem Knoten immer Konstant ist bietet diejenige Entscheidung den höchsten Information Gain, bei der die Bedingte Entropie am niedrigsten ausfällt.

Klausuraufgabe

Entropie / Information Gain berechnen

Bewertung

Vorteile

Es ist sehr leicht eine Entscheidung anhand eines Baumes zu treffen. Die Berechnung ist extrem günstig und gut nachvollziehbar.
Entscheidungsbäume lassen sich außerdem sehr gut und anschaulich visualisieren.

Nachteile

Da nur Waag- und Senkrechte Trennlinien verwendet werden, lassen sich komplexere Entscheidungsgrenzen nur schlecht darstellen.
Zusätzlich neigen Entscheidungsbäume gerne zu Überanpassung.