Iterative Dichotomiser 3

Einfache Sprache

Der Iterative Dichotomiser 3 (ID3) ist ein Algorithmus der Entscheidungsbäume generieren kann. Dabei wird ein Teile-und-Beherrsche-Ansatz benutzt und es wird dabei der Informationsgewinn maximiert. Er ist der Vorgänger vom C4.5 Algorithmus.

Def. Informationsgewinn

Der Informationsgewinn errechnet sich aus der aktuellen Entropie und der durchschnittlichen Entropie wenn ein Attribut festgelegt wird.

Sei $S$ eine Menge an Trainingsdaten, $A$ die Menge der Attribute, $a\in A$ ein Attribut aus $A$, $V(a)$ ist die Menge der möglichen Attributwerte von $a$ und $S_v\subset S$, wenn $a$ auf den Wert $v$ festgelegt wird. Sei dazu eine Entropiefunktion $e$ gegeben. Dann ist der Informationsgewinn $G(S,a)$ für $S$ und $a$ definiert als

$$G(S,a)= e(S)-\sum_{v\in V(a)}\frac{|S_v|}{|S|}e(S_v)\;.$$

Def. Iterative Dichotomiser 3

Wir wählen in jedem Schritt das Attribut $a$ aus der Attributmenge so, dass ein größtmöglicher Informationsgewinn gibt. Also

$$\max_{a\in A}\{G(S,a)\}$$