4.2.6: Endlichkeit des ID3 auf konsistenten Trainingssets

Nehmen wir ein (endliches) konsistentes Trainingsset an, so wird in jedem Knoten des Baumes ein Attribut getestet, und die Tupel werden gemäß ihres Wertes in diesem Attribut aufgeteilt. Jedes Attribut kann in einem Ast des Baumes höchstens einmal auftreten, da sonst die Forderung, dass es zwei verschiedene Werte innerhalb der Beispielmenge des Knotens annehmen muß, nicht mehr erfüllt ist. Spätestens, wenn alle Attribute abgearbeitet sind, haben alle Tupel in diesem Endknoten des Baumes auf allen vorhersagenden Attributen identische Werte. Wegen der Konsistenz handelt es sich also um genau ein Tupel, das natürlich nur zu einer Kategorie gehört. Die Höhe des Baumes ist also durch die Anzahl der vorhersagenden Attribute beschränkt. Die tatsächliche Höhe hängt natürlich auch von der Anzahl der Kategorien und ihrer Verteilung auf die Tupel ab. Die Extremfälle sind die, in denen die Anzahl der (nicht leeren) Kategorien gleich der Anzahl der möglichen Tupel ist, bzw. die, in denen nur eine Kategorie existiert. Im ersten Fall muß der Baum maximale Höhe haben, und alle Pfade im Baum haben die volle Länge. Im zweiten Fall ist keine Kategorisierung notwendig, der Baum hat die Höhe 1 .

Dass aber neben der Anzahl der Kategorien auch deren Definition entscheidenden Einfluß auf die Größe des Baumes hat, zeigt Abbildung 4.2.6 . Hier bilden die Tupel mit gerader Quersumme die Kategorie E und die mit ungerader Quersumme die Kategorie O. Der Baum hat maximale Größe, obwohl nur zwei Kategorien vorliegen. Das liegt daran, dass die Quersumme nur bestimmt werden kann, wenn alle Attribute tatsächlich einbezogen werden. Daraus ergibt sich auch, dass es mit den vorgegebenen Attributen keinen kleineren Entscheidungsbaum geben kann. Würde man z. B. zwei Kategorien definieren, eine mit den Tupeln mit einer Quersumme im Bereich [0,2] und einer mit Tupeln mit der Quersumme 3 , ergäbe sich ein wesentlich kleinerer Baum (siehe Abbildung 49 )

Das Beispiel zeigt auch, dass die Wahl der Attribute (wenn denn eine Wahl besteht) entscheidenden Einfluß auf die Aufwendigkeit der Lösung eines Problems hat.

Abb. 48: Maximaler Entscheidungsbaum mit 2 Kategorien

Abb. 49: Entscheidungsbaum mit 2 Kategorien