Top-Down Induction of Decision Trees - LinkFang.de





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

Literatur

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

Kategorien: Klassifikationsverfahren

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Top-Down Induction of Decision Trees (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.