Top-Down Induction of Decision Trees

Top-Down Induction of Decision Trees oder kurz TDIDT ist ein nicht-inkrementelles Lernverfahren im Forschungsbereich des maschinellen Lernens, das auf der Verwendung von Entscheidungsbäumen basiert.

Als Ausgangspunkt dient eine Lernmenge L von Beispielen und eine Menge T der verfügbaren Tests. Die Funktion F stelle eine Abbruchbedingung für einen Knoten dar. Weiterhin wird eine Methode M benötigt, die eine Auswahl eines Tests t aus T ermöglicht.

Beginnend vom Wurzelknoten wird nun jeder Folgeknoten rekursiv untersucht, ob die Abbruchbedingung F an diesem Knoten erfüllt ist. Ist dies der Fall, wird der Knoten als Blatt definiert und mit der Ausgabe von F beschriftet. Konnte der Knoten nicht als Blatt identifiziert werden, so wird mittels M ein Test t aus T gewählt, und damit der Knoten beschriftet. Für die in diesem Zweig folgenden Knoten wird t aus der Menge T entfernt. Durch die Bedingungen von t werden entsprechende Folgeknoten mit verbindenden Kanten aus dem aktuellen gebildet. Die Menge der Beispiele L teilt sich durch die Bedingungen von t ebenfalls in disjunkte Teilmengen auf die Folgeknoten auf. Bei der Rekursion durch alle Knoten verändern sich also die Lernmenge L und die Menge der verfügbaren Tests T, bis schließlich diese Mengen (i. B. L) leer sind. Alle Beispiele aus L wurden damit einem Blatt zugeordnet.

Es muss natürlich das Ziel sein, einen möglichst effizienten, also einen möglichst kleinen, Entscheidungsbaum zu erhalten. Dies kann von vornherein erreicht werden, indem die Methode M jeweils einen Test auswählt, der die zur Verfügung stehenden Beispiele L in möglichst gleich große Teilmengen aufspaltet. Während der Konstruktion kann durch die Abbruchbedingungen F ein möglichst früher Abbruch angestrebt werden. Im Nachhinein können Techniken, wie Baumbeschneiden, angewendet werden, die den Baum verkleinern.

Als ein nicht-inkrementelles Lernverfahren muss TDIDT bei einer Änderung der Beispiele L durch neue Beobachtungen (also neue Beispiele) oder Änderung des Verhaltens untereinander komplett neu aufgebaut werden.

Häufig verwendete TDIDT-Verfahren sind ID3 und C4.5.

Siehe auch

• Top-down und Bottom-up

Literatur

• J.R. Quinlan: Induction of Decision Trees. In: Machine Learning 1. Kluwer Academic Publishers, Boston 1986, S. 81–106 (oregonstate.edu [PDF; abgerufen am 10. Juli 2010]).