Top-Down Induction of Decision Trees

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 (PDF, abgerufen am 10. Juli 2010).

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Decision tree learning — This article is about decision trees in machine learning. For the use of the term in decision analysis, see Decision tree. Decision tree learning, used in statistics, data mining and machine learning, uses a decision tree as a predictive model… …   Wikipedia

  • TDIDT — 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… …   Deutsch Wikipedia

  • Entscheidungsbaum — Entscheidungsbäume sind geordnete, gerichtete Bäume, die der Darstellung von Entscheidungsregeln dienen. Sie veranschaulichen hierarchisch, aufeinanderfolgende Entscheidungen. Sie haben eine Bedeutung in zahlreichen Bereichen, in denen… …   Deutsch Wikipedia

  • Entscheidungsmodell — Entscheidungsbäume sind eine spezielle Darstellungsform von Entscheidungsregeln. Sie veranschaulichen aufeinanderfolgende, hierarchische Entscheidungen. Sie haben eine Bedeutung in der Stochastik zur Veranschaulichung bedingter… …   Deutsch Wikipedia

  • Klassifikationsbaum — Entscheidungsbäume sind eine spezielle Darstellungsform von Entscheidungsregeln. Sie veranschaulichen aufeinanderfolgende, hierarchische Entscheidungen. Sie haben eine Bedeutung in der Stochastik zur Veranschaulichung bedingter… …   Deutsch Wikipedia

  • Regression Tree — Entscheidungsbäume sind eine spezielle Darstellungsform von Entscheidungsregeln. Sie veranschaulichen aufeinanderfolgende, hierarchische Entscheidungen. Sie haben eine Bedeutung in der Stochastik zur Veranschaulichung bedingter… …   Deutsch Wikipedia

  • Wahrscheinlichkeitsbaum — Entscheidungsbäume sind eine spezielle Darstellungsform von Entscheidungsregeln. Sie veranschaulichen aufeinanderfolgende, hierarchische Entscheidungen. Sie haben eine Bedeutung in der Stochastik zur Veranschaulichung bedingter… …   Deutsch Wikipedia

  • France — /frans, frahns/; Fr. /frddahonns/, n. 1. Anatole /ann nann tawl /, (Jacques Anatole Thibault), 1844 1924, French novelist and essayist: Nobel prize 1921. 2. a republic in W Europe. 58,470,421; 212,736 sq. mi. (550,985 sq. km). Cap.: Paris. 3.… …   Universalium

  • KABBALAH — This entry is arranged according to the following outline: introduction general notes terms used for kabbalah the historical development of the kabbalah the early beginnings of mysticism and esotericism apocalyptic esotericism and merkabah… …   Encyclopedia of Judaism

  • Word-sense disambiguation — Disambiguation redirects here. For other uses, see Disambiguation (disambiguation). In computational linguistics, word sense disambiguation (WSD) is an open problem of natural language processing, which governs the process of identifying which… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”