Database Reference
In-Depth Information
3. Falls die Attributmenge leer ist, es aber noch sowohl positive als auch negative
Beispiele gibt, tritt folgendes Problem auf: In der ursprunglichen Trainings-
menge gibt es Beispiele mit genau denselben Attributwerten, aber unterschied-
licher Klassifikation. Dies kann bedeuten, dass einige Beispiele der Trainings-
menge falsch sind; es konnte aber auch der Fall sein, dass noch zusatzliche
Attribute eingefuhrt werden mussten, um die Beispiele zu unterscheiden und
damit die Situation vollstandiger beschreiben zu konnen. Im Folgenden wer-
den wir vereinfachend annehmen, dass in einem solchen Fall der Algorithmus
mit einer Fehlermeldung abbricht.
4. Falls es noch sowohl positive als auch negative Beispiele in E und eine nicht
leere Attributmenge A gibt, wahlen wir das beste Attribut a
A gemaß sei-
ner “Wichtigkeit” aus. Die Beispiele in E werden gemaß den moglichen At-
tributwerten von
a
aufgeteilt, um rekursiv einen Entscheidungsbaum fur das
entsprechende Teilproblem zu generieren. Abbildung 5.4(c) zeigt, wie das At-
tribut
Wetter
dazu benutzt wird, eine der noch verbliebenen Beispielmengen
weiter aufzuteilen.
∈
Der vollstandige Lernalgorithmus
DT
zum Generieren von Entscheidungsbaumen
ist in Abbildung 5.6 angegeben.
function
DT
(E, A,
default
)
Eingabe:
E
Menge von Beispielen
A
Menge von Attributen
default
Default-Klassifikation
Ausgabe:
Entscheidungsbaum
if
E
= ∅
then return
default
else if
alle Elemente in E haben die gleiche Klassifikation c
∈{
ja
,
nein
}
then return
c
else if
A =
∅
then
Fehler “gleiche Beispiele mit unterschiedlicher
Klassifikation”
else
a
:=
ChooseAttribute
(A, E)
T := neuer Entscheidungsbaum
mit Wurzelmarkierung a
for each
Attributwert w
i
von
a
do
E
i
:=
a(e)=w
i
}
T
i
:=
DT
(E
i
,A
{
e
∈
E
|
,
MajorityVal
(E))
hange an den Wurzelknoten von T
eine neue Kante mit Markierung w
i
und Unterbaum T
i
an
\{
a
}
end
return
T
Abbildung 5.6
Verfahren
DT
zur Generierung von Entscheidungsbaumen
