imported>Trustable: Kleinigkeiten verbessert

2020-07-01T21:57:47Z

Kleinigkeiten verbessert

Neue Seite

'''Top-Down Induction of Decision Trees''' oder kurz '''TDIDT''' ist ein [[nicht-inkrementelles Lernverfahren]] im Forschungsbereich des [[maschinelles Lernen|maschinellen Lernens]], das auf der Verwendung von [[Entscheidungsbaum|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 [[Pruning|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 [[Iterative Dichotomiser 3|ID3]] und [[C4.5]].

== Siehe auch ==
* [[Top-down und Bottom-up]]

== Literatur ==
* {{Literatur |Autor=J.R. Quinlan |Titel=Induction of Decision Trees |Verlag=Kluwer Academic Publishers |Ort=Boston |Sammelwerk=Machine Learning 1 |Datum=1986 |Seiten=81–106 |Online=http://classes.engr.oregonstate.edu/eecs/fall2009/cs434/decisiontree-quinlan.pdf |Format=PDF |Abruf=2010-07-10}}

[[Kategorie:Klassifikationsverfahren]]

Top-Down Induction of Decision Trees - Versionsgeschichte

imported>Trustable: Kleinigkeiten verbessert