Einführung in Decision Trees

I. Einführung

Die Klassifikation beschreibt das Zuordnen
von Objekten oder Daten in vordefinierte Kategorien.
Die Anwendungen reichen dabei von
der Erkennen von Spam E-Mails, Kategorisieren
von Spezies bis hin zur Astronomie und
der Detektion von Neutrinos. Ein decision tree
(zu Deutsch Entscheidungsbaum) ist eines von
mehreren Beispielen für einen automatischen
Klassifizierer, der sich unter anderem dadurch
auszeichnet, dass er einfach zu implementieren
und visualisieren ist. Im Folgendem wird die
Funktionsweise eines binären decision tree anhand
des Beispiels von Darwinfinken erläutert.
Dabei wird der CART (Classification and Regression
Trees) Algorithmus zum Erstellen und
Trainieren des Baumes verwendet.

II. Wie trainiere ich einen Decision
Tree

Angenommen Biologen finden heute auf den
Galapagos Inseln eine Vogelart, die sie nicht
eindeutig einer schon bekannten Art zuordnen
können. Was sie aber besitzen, sind Darwins
Aufzeichnungen (siehe Tabelle 1) aus seiner Expedition
von 1835. In diesen Aufzeichnungen
dokumentiert Darwin die Vögel anhand der
Schnabelgröße und der Farbe des Gefieders.
Diese Aufzeichnungen können als Trainingsdaten
für einen decision tree dienen. Trainingsdaten
zeichnen sich dadurch aus, dass diese
ein Label (in diesem Fall die Art) und Attribute
(Schnabelgröße und Farbe) besitzen. Zum
Vergleich haben die Biologen von der neu entdeckten
Art lediglich nur die Attribute, mit
denen man anschließend eine Aussage darüber
treffen kann, mit welcher Wahrscheinlichkeit
es sich um welche Art handelt. Für die Klassifikation können jetzt anhand der Attribute
True/False-Fragen gestellt werden, die die Daten
nach jeder Frage in zwei Teilmengen aufteilen. In einem

decision tree werden die Daten mit mehrerer solcher Fragen in einer hierarchischen
Reihenfolge aufgeteilt, bis am Ende keine weiteren
Teilmengen separiert werden können.
Die Abbildung 1 stellt einen decision

Tabelle 1: Trainingsdaten Darwinfinken

LabelSchnabelFarbe
Geospitza Magnirostris5braun
Geospitza Magnirostris5schwarz
Certhidea Olivacea1grün
Certhidea Olivacea1grün
Geospitza Fortis5schwarz

tree schematisch dar. Dieser besteht aus einem
Wurzelknoten (engl. root node), welcher die gesamte
Datenmenge enthält und den Startpunkt definiert.
Anschließend wird an jedem Knoten

Abbildung 1: Decision Tree mit einem root node, internal
node und leaf. Die Beschreibung der
einzelnen Komponenten kann dem Text
entnommen werden.

eine Separation der Datenmenge anhand einer
true- oder false-Frage durchgeführt. Die zwei
Teilmengen bilden dann zwei weitere Knoten,

die über die true- oder false-Äste mit den vorherigen
Knoten verbunden sind. Die nachkommenden
Knoten können wiederum zwei Äste
besitzen, die wiederum auf Knoten zeigen, was
diese Knoten zu internen Knoten (engl. internal
node) macht. Kann eine Teilmenge an einem
Knoten nicht weiter aufgeteilt werden, wird
der Knoten zu einem Blatt (engl. leaf ) und
hat somit auch kein Folgeknoten. Der nächste
Schritt ist es herauszufinden, welche Frage
an welcher Stelle zu stellen ist. Dazu führen
wir zunächst den Begriff der Reinheit (engl. purity)
einer Datenmenge ein. Eine Möglichkeit
die Reinheit zu quantisieren ist der Gini-Index
oder Gini-Koeffizient
$$L = 1 – \sum_{i}^{}p_i^2$$
der einen Zahlenwert von 0 und 1 annehmen
kann und ein Maß für die Ungleichverteilung
ist. Dabei entspricht ein Gini-Index von 0 der
größtmöglichen Reinheit. In unserem Beispiel
beschreibt \(p_i\) die Wahrscheinlichkeit ein bestimmtes
Label aus unseren Daten zu ziehen.
Unsere Testdaten haben insgesamt fünf Einträge.
Die Wahrscheinlichkeit zufällig das Label
Geospitza Magnirostris zu ziehen beträgt
\(p = 2/5\), weil dieses zwei Mal vorhanden ist.
Der Gini-Index des Wurzelknotens entspricht
damit:
$$L_{\text{root}} = 1 – [(2/5)^2 + (2/5)^2 + (1/5)^2] = 0,64$$
Ausgehend von der gestellten Frage, wird diese
Datenmenge imWurzelknoten in zwei Teilmengen
aufgeteilt, die dann jeweils einen verschiedenen
Gini-Index in den Folgeknoten besitzen.
Die möglichen Fragen, die am Wurzelknoten
gestellt werden können, ergeben sich aus den
Attributen:

  1.  Schnabel \(>=\) 5?
  2. Schnabel \(>=\) 1?
  3. Farbe \(==\) braun?
  4. Farbe \(==\) schwarz?
  5. Farbe \(==\) grün?

Die Abb. 2 und 3 stellen die unterschiedlichen Ergebnisse für die Fragen 1 und 4 dar. Beide starten am Wurzelknoten mit dem Gini-Index \(L=0,64\). Für die Frage “ Schnabel \(>=5\) “ ergibt sich ein gewichteter Gini-Index der beiden Folgeknoten von

$$L_{5} = 2/5 * 0 + 3/5 * 0,44 = 0,37 \ .$$

Für die Frage “ Farbe \(==\)schwarz ?“ ergibt sich ein gewichteter Gini-Index von

$$L_{\text{schwarz}} = 3/5 * 0,44 + 2/5 * 0,5 = 0,46 .$$

Für die Wahl, welche Frage gestellt werden muss, wird der information gain \(I\) ermittelt

$$I_{\text{Frage}} = L_{\text{root}} – L_{\text{Frage}}. $$

Um so höher $I$ ist, desto besser wird die Datenmenge bezüglich ihrer Reinheit in zwei Teilmengen aufgeteilt. In diesem Beispiel ergeben sich zwei Werte \(I_{5} = 0,37\)

Abbildung 2: Frage: Schnabel \(>=\)

und \(I_{\text{schwarz}} = 0,17\) und die Wahl für die erste Frage im decision tree fällt auf  „Schnabel \(>= 5\) ?“ (siehe Abb. 2). Für die Weiterentwicklung des Baumes werden jetzt die beiden Knoten betrachtet, die an dem false- und true-Ast entstanden sind. Zunächst erst mal der false-Ast. Dieser enthält Daten, die alle dasselbe Label (Certhidea Olivacea) besitzen. Aus den Attributen (siehe Tab. 1) entnimmt man, dass es keine mögliche Fragen gibt, die diese Datenmenge weiter in Untermengen aufteilen könnte. Dieser Knoten wird damit zu einem Blatt. Der true-Ast besitzt eine Datenmenge, die noch weiter unterteilt werden kann.

Abbildung 3: Frage: Farbe \(==\) schwarz

Ein Vergleich der Attribute der noch vorhandenen Daten ergibt, dass nur noch eine mögliche Frage gestellt werden kann. Die Schnabelgrößen haben alle den Wert \(5\), aber in der Farbe des Gefieders gibt es noch Unterschiede. Da es sich um lediglich zwei Farben (schwarz und braun) handelt, sind die Fragen „\(==\) schwarz ?“ und „\(==\) braun ?“ äquivalent und der Test nach dem information gain redundant. Wir wählen in diesem Beispiel die Frage „\( ==\) braun“ (siehe Abb. 4).  Es entstehen wieder zwei Knoten,

Abbildung 4: Frage: Farbe \(==\) braun

welche dieses Mal beide zu Blätter werden. Da keine weiteren Knoten entstehen, an denen die Daten weiter separiert werden können, ist der Baum somit komplett. Die Abb. 5 stellt den fertigen Baum dar. Vergleicht man die einzelnen Blätter, erkennt man, dass zwei Blätter einen Gini-Index von \(L=0\) und ein Blatt \(L=0,5\) besitzen. Das liegt daran, dass in unseren (bzw. Darwins) Testdaten zwei Finken unterschiedlicher Art die selben Attribute aufweisen (Schnabel = 5 und Farbe = schwarz).

Die anfangs erwähnten Biologen können jetzt mit Hilfe dieses Baumes die neu entdeckte Art mit einer gewissen Wahrscheinlichkeit oder einem gewissen Konfidenzniveau 

Abbildung 5: Fertiger Baum mit Konfidenzniveau der einzelnen Blätter

Darwins Daten zuordnen. Angenommen der entdeckte Vogel hätte eine Schnabelgröße von \(6\) und ein blaues Gefieder, dann könnte man den Vogel mit einem Konfidenzniveau von \(50\%\) der Art Geospitza Magnirostris oder Geospitza Fortis zuordnen.

III. Zusammenfassung und Ausblick

Anhand dieses Beispiels erkennt man, wie entscheidend die Trainingsdaten für die Aussagekraft sind. Allerdings treten bei zu vielen oder auch inkorrekten Trainingsdaten Artefakte auf, die besonders Behandelt werden müssen. Beim pruning beispielsweise kann die Länge eines Baumes vordefiniert werden, sodass dieser nicht zu groß wird. Das Phänomen tritt vor allem bei kontinuierlichen Attribut-Werten auf, die Gegenstand komplexerer Entscheidungsfindungsstrategien sind.