Database Reference
In-Depth Information
5.3.5
Die induktiven Lernverfahren ID3 und C4.5
Die auf dem in Abbildung 5.6 angegebenen Verfahren
DT
basierenden Lernalgorith-
men heißen “Top-Down Induction of Decision Trees” (TDIDT). Durch den schritt-
weisen Aufbau des Entscheidungsbaumes wird die dadurch reprasentierte Klassifi-
kation schrittweise entwickelt.
Der Kern eines TDIDT-Verfahrens ist die Attributauswahl, die wir im vorigen
Abschnitt nur beispielhaft illustriert hatten. Das Verfahren
DT
in Abbildung 5.6
abstrahiert durch den Aufruf der (nicht weiter spezifizierten) Funktion
ChooseAt-
tribut(A, E)
gerade von dieser kritischen Auswahl.
Das Ziel bei der Attributauswahl ist es, den Entscheidungsbaum moglichst klein
zu halten. Ein ideales Attribut ware daher eines, das die noch verbleibenden Bei-
spiele genau in positive und negative Beispielmengen aufteilt. Gemessen an diesem
Ideal ist das Pradikat
Gruppe
in dem Kinobeispiel fur den ersten Test schon ziem-
lich gut, wahrend das Attribut
Kategorie
eher nutzlos ist (vgl. Abbildung 5.4(a)
und (b)).
Das Entscheidungsbaumlernsystem ID3 [186, 187] formalisiert diese Idee von
“ziemlich guten” und “eher nutzlosen” Attributen durch die Berucksichtigung des
Informationsgehalts
der Attribute. ID3 und seine Weiterentwicklung C4.5 sind die
etabliertesten TDIDT-Verfahren und gehoren zu den bekanntesten maschinellen
Lernsystemen uberhaupt. Verschiedene industrielle Anwendungen von ID3 sind in
[117] beschrieben.
Die mit einem Ereignis verbundene Information wird logarithmisch (ublicher-
weise zur Basis 2) aus seiner Wahrscheinlichkeit berechnet (s. Abschnitt A.7 im
Anhang). Den
mittleren Informationsgehalt
H(P ) einer Wahrscheinlichkeitsvertei-
lung P =(p
1
,..., p
n
) bezeichnet man als die
Entropie von
P :
n
H(P )=
−
p
i
log
2
p
i
(5.1)
i=1
Beim maschinellen Lernen kommt es in der Regel nur darauf an, ob das ent-
sprechende Beispiel ein positives oder ein negatives ist. Wenn wir eine Beispielmen-
ge mit k Beispielen haben, so nehmen wir an, dass die Auswahl eines beliebigen
Beispiels aus dieser Menge gemaß einer Gleichverteilung erfolgt. D.h. die Wahr-
scheinlichkeiten sind durch relative Haufigkeiten bestimmt. Die Wahrscheinlichkeit,
ein bestimmtes Beispiel e
i
aus einer Menge
auszuwahlen, ist damit
k
,
{
e
1
,..., e
k
}
und die Wahrscheinlichkeit, aus der Menge
{
e
1
,..., e
k
}
eines von l vorgegebenen
Beispielen (l
≤
k)auszuwahlen, ist
l
1
k
l
k
=
i=1
Die Wahrscheinlichkeit, aus einer Menge mit p positiven und n negativen Bei-
spielen ein positives auszuwahlen, ist also
p
p + n
. Der Informationsgehalt I(E)der
Antwort auf die Frage, ob es sich bei einem beliebigen Beispiel aus einer Trainings-
menge E mit p positiven und n negativen Beispielen um ein positives oder ein
negatives Beispiel handelt, ist daher
