Maschinelles Lernen - Methoden Wissensbasierter Systeme - page 110

das Occam's Razor 1 genannt wird:

Bevorzuge die einfachste Hypothese,die
konsistent mit allen Beobachtungen ist.

Auf Entscheidungsbaume ubertragen kann man sich Occam's Razor wie folgt klar-
machen: Man kann sicherlich davon ausgehen, dass es sehr viel weniger kleine, kom-
pakte Entscheidungsbaume als große, komplexe gibt. Die Chance, dass irgendein
kleiner Entscheidungsbaum mit wenigen Knoten, der insgesamt sehr viele falsche
Entscheidungen trifft, zufalligerweise mit allen Beispielen konsistent ist, ist daher
sehr gering. Im Allgemeinen ist folglich ein kleiner Entscheidungsbaum, der konsi-
stent mit allen Beispielen ist, eher korrekt als ein großer, komplexer Entscheidungs-
baum.
Auf die Problematik, einen kleinsten Entscheidungsbaum zu finden, wollen wir
hier nicht eingehen; es gibt aber eine recht erfolgreiche Heuristik, kleine Entschei-
dungsbaume zu generieren. Die Idee dabei ist, das wichtigste Attribut zuerst zu
testen, wobei das wichtigste Attribut dasjenige sein soll, das am meisten zur Dif-
ferenzierung der aktuellen Beispielmenge beitragt. Im nachsten Abschnitt werden
wir ein Verfahren vorstellen, wie man die “Wichtigkeit” eines Attributs bestimmen
kann; hier geben wir zunachst ein Beispiel an.

Beispiel 5.3 (Kino 3) Wirbetrachtenwiederdiefunfzehn Trainingsbeispiele aus
dem Kinoproblem. Abbildung 5.4(a) zeigt, dass das Attribut Gruppe die Trainings-
menge so aufteilt, dass bei einem der drei moglichen Werte ( allein ) die Klassi-
fizierung von insgesamt drei Trainingsbeispielen bereits vollstandig vorgenommen
werden kann; bei den Werten Freunde und Paar sind weitere Tests notwendig.
Andererseits ist in Abbildung 5.4(b) dargestellt, dass das Attribut Kategorie
fur den ersten Test nicht gut geeignet ist, da bei allen vier moglichen Werten weitere
Tests notwendig sind und folglich kein einziges Trainingsbeispiel mit nur einem Test
klassifiziert werden kann.
Abbildung 5.4(c) zeigt, wie die fur den Wert Paar des Attributs Gruppe ubrig
gebliebene Beispielmenge E P aar =

durch Abfrage des At-
tributs Wetter weiter aufgeteilt und endgultig klassifiziert wird.
Abbildung 5.5 illustriert, wie die Beispielmenge E P aar durch Abfrage des At-
tributs Kategorie aufgeteilt wird. Beachten Sie, dass fur den Attributwert SF hier
weder positive noch negative Beispiele vorhanden sind.

{ X 2 ,X 5 ,X 10 ,X 11 ,X 15 }

Selbsttestaufgabe 5.4 (Attributauswahl) Gegeben sei der in Abbildung 5.4(c)
gegebene Teil eines Entscheidungsbaumes fur das Kinoproblem. Wir betrachten die
Beispielmenge E = { X 1 ,X 3 ,X 6 ,X 7 ,X 8 ,X 9 ,X 14 } ,diefur den Wert Freunde des

Attributs Gruppe ubrig geblieben ist.
1. Geben Sie analog zu Abbildung 5.4(c) fur jedes ubrig gebliebene Attribut a an,
wie E durch a als nachstes zu testendes Attribut aufgeteilt wurde.
2. Welches Attribut ist das wichtigste, wenn man als Grad fur die Wichtigkeit die
Anzahl der Beispiele aus E nimmt, die damit endgultig klassifiziert werden?
1 William of Occam, engl. Philosoph, ca. 1285-1349