imported>Invisigoth67: typo

2024-09-14T16:58:58Z

typo

Neue Seite

'''Iterative Dichotomiser 3''' ('''ID3''') ist ein [[Algorithmus]], der zur Entscheidungsfindung dient. Er wird bei [[Entscheidungsbaum|Entscheidungsbäumen]] eingesetzt. Der australische Forscher [[J. Ross Quinlan]] publizierte diesen Algorithmus erstmals im Jahr [[1986]].<ref>{{Literatur |Autor=J. Ross Quinlan |Titel=Induction of Decision Trees |Sammelwerk=Machine Learning |Band=1 |Nummer=1 |Datum=1986-03 |Seiten=81-106 |DOI=10.1007/BF00116251}}</ref> ID3 war in seinen ersten Jahren sehr einflussreich. Er findet auch heute noch in einigen Produkten Verwendung. ID3 gilt als Vorgänger des [[C4.5]]-Algorithmus.

ID3 wird verwendet, wenn bei großer Datenmenge viele verschiedene Attribute von Bedeutung sind und deshalb ein Entscheidungsbaum ohne große Berechnungen generiert werden soll. Somit entstehen meist einfache Entscheidungsbäume. Es kann aber nicht garantiert werden, dass keine besseren Bäume möglich wären.

Die Basisstruktur von ID3 ist [[Iteration|iterativ]]. Es werden zu jedem noch nicht benutzten Attribut [[Entropie (Informationstheorie)|Entropien]] bezüglich der Trainingsmenge berechnet. Das Attribut mit dem höchsten Informationsgewinn (englisch: information gain) bzw. der kleinsten Entropie, wird gewählt und daraus ein neuer Baum-Knoten generiert. Das Verfahren terminiert, wenn alle Trainingsinstanzen klassifiziert wurden, d. h. wenn jedem Blattknoten eine Klassifikation zugeordnet ist.

== Algorithmus ==
Wenn alle Elemente aus <math>T</math> (Daten) zu einer Klasse gehören
: Dann
:: // Erzeuge ein Blatt //
::: Konstruiere ein Blatt mit der Klasse als Bezeichner

: Sonst
:: // Erzeuge rekursiv einen Teilbaum //
::: Wähle das „informativste“ Merkmal <math>x_i</math>
::: Beginn: Für_alle vorkommenden Werte von Merkmal <math>x_i</math>
:::: Konstruiere alle Teilbäume rekursiv mit den entsprechenden Teilmengen als Daten
::: Ende: Für_alle
::: Konstruiere einen Baumknoten mit Bezeichner <math>x_i</math> und hänge alle erzeugten Teilbäume an
: Ende Sonst

== Auswahl der Attribute (Merkmale) ==
Für die Bildung der Teilbäume wird jeweils entsprechend der [[Informationstheorie]] das informativste Attribut ausgewählt.

Sei <math>S</math> die Menge der Trainingsbeispiele mit ihrer jeweiligen Klassifizierung, <math>a \in A</math> das zu prüfende Attribut aus der Menge der verfügbaren Attribute, <math>V(a)</math> die Menge der möglichen Attributwerte von <math>a</math> und <math>S_v</math> die Untermenge von <math>S</math>, für die das Attribut <math>a</math> den Wert <math>v</math> annimmt. Der Informationsgewinn, der durch Auswahl des Attributs <math>a</math> erzielt wird, errechnet sich dann als Differenz der Entropie von <math>S</math> und der erwarteten/durchschnittlichen Entropie von <math>S</math> bei Fixierung von <math>a</math>:

<math>G(S, a) = \operatorname{Entropie}(S) - \sum_{v \in V(a)} \dfrac{|S_v|}{|S|} \operatorname{Entropie} (S_v) </math>.

Schließlich wählt man ein Attribut mit dem größtmöglichen Gewinn aus der Menge <math>\lbrace a_{next} \in A | G(S, a_{next}) = \max_{a \in A}(G(S, a)) \rbrace </math> als das nächste Attribut.

Diese Wahl führt zur Bevorzugung von Attributen mit vielen Wahlmöglichkeiten und damit zu einem breiten Baum. Um dem entgegenzuwirken, kann eine Normalisierung über die Anzahl der Wahlmöglichkeiten durchgeführt werden.

== Siehe auch ==
* [[CART (Algorithmus)|CART]]
* [[CHAID]]
* [[Top-Down Induction of Decision Trees|TDIDT]]

== Weblinks ==
* [http://ipub.com/id3-with-data-tree/ Implementierung des ID3 Algorithmus in R]

== Einzelnachweise ==
<references />

[[Kategorie:Klassifikationsverfahren]]

Iterative Dichotomiser 3 - Versionsgeschichte

imported>Invisigoth67: typo