2.3.4.1: Formale Beschreibung des ID3-Algorithmus

Nach dieser eher formlosen Beschreibung soll nun eine formalere und ausführlichere Beschreibung gegeben werden, zunächst für die Konstruktion des Entscheidungsbaums:

Algorithmus 3: ID3 im Detail

Auswahlkriterium

In Schritt 2 muss ein Attribut A_i:D->R_i ausgewählt werden, das zur Selektion verwendet werden soll. Für jedes Attribut, das in Frage kommt, wird der Wert

E

(Ai,Kj,rm)

=

kRi

| A-1i({k} )Kj,rm| |Kj,rm|

I

(k,Kj,rm)

I

(k,K)

=

rR0

-qk,rln

( qk,r)

qk,r=

|A-10 ({r}) A-1i({k} )K| | A-1i({k} )K|

Es wird das Attribut zur Selektion gewählt, bei dem der Wert E(A_i,K_j,rm) minimal ist, bei dem die Kindknoten also bezüglich der gesuchten Kategorie möglichst wenig durchmischt sind.

Abbildung 52: Entropiewerte, nach denen die Attribute bei der Konstruktion eines ID3 Baums selektiert werden.

Abbildung 53: ID3-Entscheidungsbaum

Die Auswahl dieser Optimierungsheuristik ist folgendermaßen motiviert: Betrachtet man die Beispiele eines Knotens als Informationsquelle über die Zugehörigkeit zu den Zielkategorien, dann gibt Formel (63 ) eine Abschätzung des Informationsgehalts bzw. der Entropie eines Kindknotens an, d.h. des mittleren Informationsgewinns, den das Inspizieren eines Beispiels aus der Menge bringt. Stammen fast alle Beispiele der Knotenmenge aus einer Kategorie, ist der zu erwartende Informationsgewinn gering. Stammen sie sogar alle aus einer Kategorie, ist entweder q_k,r=0 oder q_k,r=1 und damit ln(q_k,r) =ln(1)=0 . In beiden Fällen ist das Produkt -q_k,rln(q_k,r) und damit I(k,K) gleich 0. In den anderen Fällen ist der Wert positiv, weil das Argument des Logarithmus zwischen 0 und 1 liegt und der Logarithmus daher negativ ist. Formel (63 ) gibt also den mittleren erwarteten Informationsgehalt der Kindknoten bei einer Aufteilung nach Attribut A_i an. Je kleiner der ist, desto größer ist der Informationsgewinn durch die Wahl von A_i .