Maschinelles Lernen - Methoden Wissensbasierter Systeme - page 109

Attribute

Bei-
spiel

Kino-
besuch?

Attr. Preis Loge Wetter Warten Bes. Kat. Land Res. Gruppe

X 1 hoch ja schlecht ja top AC int. ja Freunde ja

ee

X 2 mittel ja mittel nein mittel KO int. nein Paar ja

e

X 3 mittel nein mittel ja mittel DR int. nein Freunde nein

e

X 4 gering e ja mittel ja mittel SF int. nein allein nein

X 5 mittel e ja mittel nein mittel DR int. nein Paar ja

X 6 hoch ja schon nein top SF int. ja Freunde ja

ee

X 7 mittel e ja schlecht nein mittel KO nat. nein Freunde ja

X 8 mittel nein schlecht ja mittel AC int. nein Freunde ja

e

X 9 gering e ja schon nein mittel KO nat. nein Freunde nein

X 10 mittel ja schon nein mittel KO int. nein Paar nein

e

X 11 hoch ja mittel ja top DR int. nein Paar ja

e

X 12 mittel nein schlecht ja mittel AC nat. nein allein nein

e

X 13 hoch ja mittel ja mittel SF int. nein allein nein

ee

X 14 mittel ja schon ja top DR int. ja Freunde nein

e

X 15 mittel ja schlecht nein mittel AC int. nein Paar ja

e

Abbildung 5.3 Beispiele fur das Kinoproblem

5.3.3 Generieren von Entscheidungsbaumen

Ein Lernverfahren fur Entscheidungsbaume generiert aus einer Menge von Beispie-
len (genannt Trainingsmenge ) einen Entscheidungsbaum. Ein Beispiel besteht dabei
aus einer Menge von Attribut/Wert-Paaren zusammen mit der Klassifikation, d.h.,
ob es sich um ein positives oder um ein negatives Beispiel handelt.

Beispiel 5.2 (Kino 2) In Abbildung 5.3 sind 15 Beispiele fur das Kino-Problem
angegeben, wobei es acht positive und sieben negative Beispiele gibt.

Um aus einer Trainingsmenge einen Entscheidungsbaum zu generieren, konnte
man folgenden trivialen Ansatz wahlen: Man konstruiert einen Baum derart, dass
fur jedes Beispiel ein entsprechender Pfad von der Wurzel zu einem Knoten besteht.
Jedes Beispiel aus der Trainingsmenge wird dann durch den so generierten Entschei-
dungsbaum genau wieder so klassifiziert wie in der Trainingsmenge angegeben.
Das Problem mit diesem trivialen Ansatz ist aber, dass wir davon keine sinnvol-
le Generalisierung auf andere Falle erwarten konnen: Die gegebenen Beobachtungen
werden im Prinzip nur gespeichert, aber es wird kein Muster aus den Beispielen ex-
trahiert, von dem man erwarten konnte, dass es auf neue Situationen verallgemeinert
werden konnte (sog. overfitting ). Gerade ein solches Muster ist aber eine Moglich-
keit, eine großere Menge von Beispielen kompakt zu beschreiben. Ziel des Lernens
ist es daher, einen Entscheidungsbaum zu generieren, der nicht nur die Beispie-
le der gegebenen Trainingsmenge korrekt klassifiziert, sondern der auch moglichst
kompakt ist.
Dieser Uberlegung liegt ein generelles Prinzip des induktiven Lernens zugrunde,