Database Reference
In-Depth Information
I(E):=H
p
=
n
p + n
p
p + n
p
p + n
−
n
p + n
n
p + n
p + n
;
−
log
2
log
2
bit
Selbsttestaufgabe 5.7 (Informationsgehalt, Entropie)
Wie groß ist der In-
formationsgehalt der Antwort auf die Frage, ob es sich bei einem beliebigen Beispiel
aus der Trainingsmenge des Kinoproblems (Abbildung 5.3) um ein positives oder
negatives Beispiel handelt?
Bei der Attributauswahl soll nun berucksichtigt werden, welchen Informations-
gewinn man erhalt, wenn man den Wert eines Attributs kennt. Dazu stellen wir
fest, wieviel Information wir
nach
dem Test eines Attributs a noch benotigen. Je-
des Attribut a teilt die Trainingsmenge E in Teilmengen E
1
,...,E
k
auf, wobei k
die Anzahl der verschiedenen Werte w
1
,...,w
k
ist, die a annehmen kann (vgl. die
for each
-Anweisung im Algorithmus
DT
in Abbildung 5.6). Jede Teilmenge E
i
habe
p
i
positive und n
i
negative Beispiele. Wenn wir a = w
i
wissen, benotigen wir also
noch
p
i
p
i
+ n
i
n
i
p
i
+ n
i
I(E
i
)=H(
;
)
bit
an Information. Da fur ein beliebiges Beispiel aus E mit Attributwert a = w
i
die
Wahrscheinlichkeit
p
i
+ n
i
p + n
betragt, ist der mittlere Informationsgehalt der Antwort
(ob es sich um ein positives oder negatives Beispiel handelt),
nachdem
wir das
Attribut a getestet haben, die folgende
bedingte mittlere Information
:
k
I(E
|
a bekannt) =
P (a = w
i
)
·
I(E
i
)
i=1
k
p
i
+ n
i
p + n
·
p
i
+ n
i
;
n
i
p
i
p
i
+ n
i
)
bit
Der
Informationsgewinn
(
information gain
) durch das Attribut a ist nun als
Differenz zwischen der ursprunglichen Information und der Restinformation defi-
niert:
=
H(
i=1
a bekannt)
gain(a) ist also nichts anderes als die
gegenseitige Information
zwischen dem Attri-
but a und der Auspragung
positiv
/
negativ
(vgl. Gleichung (A.16) auf S. 504).
Das Lernsystem ID3 wahlt als nachstes zu testendes Attribut a dasjenige aus,
bei dem
gain(a)
maximal ist.
gain(a)=I(E)
−
I(E
|
Beispiel 5.8 (Attributauswahl und Informationsgewinn)
Fur das Kinopro-
blem haben wir fur die Wurzel des Entscheidungsbaumes (vgl. Abbildung 5.4):
gain(Gruppe)
=I(E)
−
I(E
|
Gruppe bekannt)
[
15
H(
7
;
7
)+
15
H(
5
;
5
)+
15
H(1; 0)]
≈
0.9968
−
≈
0.2964
bit
gain(Kategorie)=I(E)
−
I(E
|
Kategorie bekannt)
[
15
H(
4
;
4
)+
15
H(
2
;
2
)+
15
H(
2
;
2
)+
15
H(
3
;
3
)]
≈
0.9968
−
≈
0.0634
bit
