4.2 Entscheidungsbäume

Ein Entscheidungsbaum ist eine grafische Darstellung der möglichen Ergebnisse bzw. Auswirkungen einer Reihe zusammenhängender Entscheidungen bzw. Bedingungen. Mithilfe der visuellen Darstellung wird veranschaulicht, wie Entscheidungen zustande kommen.

In der Abbildung 4.2 ist ein einfacher, beispielhafter Entscheidungsbaum dargestellt, in dem es um die Frage geht, ob ein Obstbaum Früchte tragen wird. Jeder Knoten des Baumes, in der Abbildung grau unterlegt, beschreibt ein Attribut, das zur Entscheidung beiträgt. Es gibt das Alter des Baumes, die Baum-Sorte und den Boden, auf dem der Baum steht. Jede Kante des Baumes repräsentiert einen möglichen Wert des darüber liegenden Attributs, z. B. Alt und Jung für das Alter des Baums. Die endgültigen Entscheidungen werden gelb unterlegt und sind die Blätter des Baumes.

Beispielhafter Entscheidungsbaum

Abbildung 4.2: Beispielhafter Entscheidungsbaum

Ein Pfad von der Wurzel des Baumes bis zu einem Blatt entspricht einer Entscheidungsregel bzw. einer Entscheidung, ob ein Baum Früchte tragen wird (“Ja”) oder nicht (“Nein”). Ein Beispiel wäre:

WENN Alter=Alt UND Sorte=veredelt DANN tragen=Ja

Die Abbildung 4.3 veranschaulicht den Zusammenhang zwischen einem Entscheidungsbaum und den zugrunde liegenden Datensätzen. Es handelt sich hier um ein in der Literatur oft verwendetes Beispiel, bei dem aufgrund von Wetterinformationen die Entscheidung getroffen wird, ob Golf gespielt wird oder nicht.

Beispiel Golf spielen

Abbildung 4.3: Beispiel Golf spielen

Die Wurzel des Baumes bildet das Attribut Aussicht, d. h. alle resultierenden Entscheidungen basieren im ersten Schritt auf diesem Attribut und seinen drei Ausprägungen Sonnig, Bedeckt oder Regnerisch. Bei 5 der gegebenen Datensätze war das Wetter sonnig (Datensätze 1, 2, 8, 9, 11). Bei 4 Datensätzen war es bedeckt (Datensätze 3, 7, 12, 13), und für diese Datensätze kann schon eindeutig entschieden werden, dass gespielt wird. Die anderen Attribute müssen also für bedecktes Wetter gar nicht mehr betrachtet werden. Die entsprechende Regel lautet:

WENN Aussicht=Bedeckt DANN Spielen=Ja

Entscheidungsbäume bereiten Entscheidungsregeln visuell auf. Das Verständnis eines Entscheidungsbaums ist dadurch recht einfach, weil die Darstellung intuitiv ist. Schwieriger ist, einen Entscheidungsbaum auf Basis von Beispieldaten zu erstellen. Wie soll der Entscheidungsbaum zu der Abbildung 4.4 aussehen? Welches der vier Attribute steht oben? Welche folgen danach? Diese Fragen lassen sich nicht so leicht beantworten.

Datensatz Kreditrisiko

Abbildung 4.4: Datensatz Kreditrisiko

Die prinzipielle Vorgehensweise beim Erstellen eines Entscheidungsbaumes beschreibt der Algorithmus ID3:

\begin{algorithm}
\caption{ID3 Algorithmus}
\begin{algorithmic}
  \INPUT Beispieldaten $ B $
  \OUTPUT Entscheidungsbaum $ EB $
  \IF{ alle Beispieldaten gehören zur gleichen Klasse $k$ }
    \RETURN Blattknoten mit Beschriftung der Klasse $k$;
  \ELSE
    \STATE wähle ein Attribut $A$ aus $B$ aus;
    \STATE Setze $A$ als Wurzel für den aktuellen Baum ein;
    \STATE Lösche $A$ aus $B$;
    \FORALL{ Attributwert $a_i$ des Attributs $A$ }
      \STATE Erzeuge Kante im Baum mit Beschriftung $a_i$;
      \STATE Erstelle mit $ID3$ rekursiv den untergeordneten Baum $EB_i$ für alle Beispieldaten $B_i$;
    \ENDFOR
  \ENDIF
\end{algorithmic}
\end{algorithm}

Der spezifizierte Algorithmus macht deutlich, dass ein Attribut nach dem anderen im Baum abgetragen wird bis keine Entscheidung mehr nötig ist, weil alle verbleibenden Datensätze der gleichen Klasse angehören. Allerdings ist immer noch unklar, welches Attribut für die Wurzel und für alle weiteren Ebenen ausgewählt werden sollte. Die Attributauswahl ist aber sehr wichtig, weil eine gute Wahl für einen kleinen, übersichtlichen Baum sorgen kann, während eine schlechte Wahl zu einem großen, unübersichtlichen Baum führen kann. Ein einfacher Ansatz zur Attributauswahl setzt jedes Attribut als Wurzel und errechnet die Fehlerrate jeder Ausprägung :

Ein weiterer, komplexerer und in der Praxis häufig verwendeter Ansatz ist der sogenannte Information-Gain, also Informations-Gewinn, den man durch die Kenntnis eines Attributs und seiner Ausprägungen erzielt. Zunächst wird dazu der Informationsgehalt eines Attributs berechnet, wobei der Begriff Informationsgehalt interpretiert wird als Unordnung, die in den Daten herrscht. Je größer die Unordnung (bzw. die Entropie), desto größer der Informationsgehalt. Gehören alle Beispieldatensätze der gleichen Klasse an, so ist der Informationsgehalt der Daten gleich 0.

Dabei sind die möglichen Werte des Attributs und die relative Häufigkeiten (interpretiert als die Wahrscheinlichkeit) für das Eintreffen von in der Trainingsmenge. Im zweiten Schritt wird der Informationsgehalt der resultierenden Unterbäume erechnet:

Schließlich errechnet sich der Informationsgewinn durch das Attribut als

Wie wirkt sich der Informationsgewinn nun aus? In der Abbildung 4.5 ist ein Entscheidungsbaum für die Kreditrisikodaten dargestellt, dessen Wurzel Kreditwürdigkeit wenig Informationsgewinn (0,266) erzielt. Entsprechend ist der Baum recht umfangreich.

Entscheidungsbaum Kreditrisiko (1)

Abbildung 4.5: Entscheidungsbaum Kreditrisiko (1)

Zum Vergleich ist in der Abbildung 4.6 das Attribut Einkommen als Wurzel gewählt worden, mit einem Informationsgewinn von 0,967. Dieser Baum ist deutlich kleiner und übersichtlicher.

Entscheidungsbaum Kreditrisiko (2)

Abbildung 4.6: Entscheidungsbaum Kreditrisiko (2)

Es kann vorkommen, dass ein Entscheidungsbaum die Trainingsdaten ausnahmslos exakt klassifiziert, dass die Klassifikation auf den Testdaten aber schlecht funktioniert. Der Baum hat quasi die Trainingsdaten auswendig gelernt. Man nennt dieses Problem Overfitting. Selbstverständlich möchte man Overfitting verhindern, weil dadurch auch neue Daten nicht korrekt klassifiziert werden. Aber wie und was ist dafür zu tun?

Ein verbreiteter Lösungsansatz ist das Verkürzen eines Entscheidungsbaums, so dass jeder Unterbaum eine minimale Anzahl an Datensätzen enthalten muss. Dadurch werden manche Unterbäume durch ein Blatt ersetzt. Man bezeichnet diesen Ansatz mit Pruning, bei dem aufgegeben wird, dass JEDER Datensatz der Trainingsdaten korrekt vorhergesagt wird. Dies ist oft sowieso nicht möglich, weil es widersprüchliche Daten geben kann: Zwei Datensätze haben die gleichen Werte, nur die zugehörigen Klassen sind unterschiedlich.

Ein durch Pruning gekürzter Baum erzielt oft bessere Ergebnisse als ein kompletter Entscheidungsbaum, denn durch das Abschneiden von Teilbäumen beim Pruning ist der Entscheidungsbaum verallgemeinert und verhindert damit Overfitting.