Urszula Herman-Iżycka
Przemysław Strzelczak
19. marca 2004
Do tych właśnie celów wymyślono drzewa decyzyjne, które na stałe wpisały się w poczet elementów uczenia maszynowego. Na podstawie dostarczonego zbioru faktów i reguł maszyna uczy się jak sklasyfikować nowe przypadki. Zbiór faktów na podstawie, których będziemy wnioskować nazywamy Training Set, natomiast nowe przypadki, które będziemy chcieli zaklasyfikować to Test Set. Klasyfikacja polega na stwierdzeniu w jakiej kategorii umieścić nowy przypadek, zwykle jest to podział binarny na true lub false itp. Training Set jest zbiorem rekordów o tej samej strukturze, na którą składają się pary typu atrybut/wartość atrybutu. Ponadto każdy rekord jest przyporządkowany do odpowiedniej kategorii. Na podstawie wartości tych atrybutów i Training Set próbujemy sklasyfikować nowe przypadki, w których mamy dane jedynie atrybuty i ich wartości.
Oto przykład wzięty z giełdy:
ATTRIBUTE | POSSIBLE VALUES ============+======================= age | old, midlife, new ------------+----------------------- competition | no, yes ------------+----------------------- type | software, hardware ------------+----------------------- AGE | COMPETITION | TYPE | PROFIT ========================================= old | yes | swr | down --------+-------------+---------+-------- old | no | swr | down --------+-------------+---------+-------- old | no | hwr | down --------+-------------+---------+-------- mid | yes | swr | down --------+-------------+---------+-------- mid | yes | hwr | down --------+-------------+---------+-------- mid | no | hwr | up --------+-------------+---------+-------- mid | no | swr | up --------+-------------+---------+-------- new | yes | swr | up --------+-------------+---------+-------- new | no | hwr | up --------+-------------+---------+-------- new | no | swr | up --------+-------------+---------+--------
A także przykład golfowy, z którego będziemy często korzystać. Na podstawie warunków atmosferycznych określamy czy będziemy grać w golfa czy nie.
ATTRIBUTE | POSSIBLE VALUES ============+======================= outlook | sunny, overcast, rain ------------+----------------------- temperature | continuous ------------+----------------------- humidity | continuous ------------+----------------------- windy | true, false ============+======================= OUTLOOK | TEMPERATURE | HUMIDITY | WINDY | PLAY ===================================================== sunny | 85 | 85 | false | Don't Play sunny | 80 | 90 | true | Don't Play overcast| 83 | 78 | false | Play rain | 70 | 96 | false | Play rain | 68 | 80 | false | Play rain | 65 | 70 | true | Don't Play overcast| 64 | 65 | true | Play sunny | 72 | 95 | false | Don't Play sunny | 69 | 70 | false | Play rain | 75 | 80 | false | Play sunny | 75 | 70 | true | Play overcast| 72 | 90 | true | Play overcast| 81 | 75 | false | Play rain | 71 | 80 | true | Don't Play
Drzewo decyzyjne jest odpowiednio zbudowanym drzewem o następujących własnościach:
Ponadto dobrze zbudowane drzewo decyzyjne (tzn. takie, które szybko potrafi zwrócić kategorię) ma odpowiednio rozmieszczone atrybuty w węzłach:
Drzewo decyzyjne w przykładzie giełdowym:
Age
/ | \
/ | \
new/ |mid \old
/ | \
Up Competition Down
/ \
/ \
no/ \yes
/ \
Up Down
Natomiast w przykładzie golfowym drzewo decyzyjne wygląda tak: (wierząc autorowi artykułu :-)
Outlook
/ | \
/ | \
overcast / |sunny \rain
/ | \
Play Humidity Windy
/ | | \
/ | | \
<=75 / >75| true| \false
/ | | \
Play Don'tPlay Don'tPlay Play
Aby przystąpić do budowy drzewa potrzebujemy jeszcze kilku definicji, a przede wszystkim określić jak wybrać spośród atrybutów ten, który zawiera ,,najwięcej informacji''.
Mając zadany rozkład prawdopodobieństwa P=(p1, p2, ..., pn) określamy Informację, jaką przechowuje ten rozkład (Entropię P) jako:
Im bardziej jednorodny rozkład prawdopodobieństwa, tym większa jest jego informacja:
Podzielmy zbiór rekordów T na rozłączne klasy C1, C2, ..., Ck według wartości ich atrybutu kategorii. Informację potrzebną, by stwierdzić do której klasy należy element ze zbioru oznaczmy przez
gdzie P jest rozkładem prawdopodobieństwa podziału (C1, C2, ..., Ck) zadanym następująco
W przykładzie z giełdą mamy:
gdyż mamy dwie klasy (Up, Down) i w naszym Training Set dokładnie 5 entek spośród 10 miało kategorię Up i dokładnie 5- Down.
Podzielmy zbiór T na podstawie wartości atrybutu X na podzbiory T1, T2, .., Tn. Informacja potrzebna, by stwierdzić do jakiej klasy należy element z T jest średnią ważoną informacji potrzebnych, by stwierdzić do jakiej klasy należy element Ti:
W golfowym przykładzie obliczenia są następujące:
Różnicę pomiędzy informacją potrzebną, by stwierdzić do jakiej klasy należy element T, a informacją potrzebną, po tym jak poznaliśmy wartość atrybutu X definiujemy jako:
W przykładzie golfowym:
Widzimy więc, że Outlook daje większy zysk informacji niż Windy.
Budując drzewo decyzyjne będziemy się opierać na wartościach Gain
wyliczonych dla każdego atrybutu i umieszczać w korzeniu poddrzewa ten
atrybut spośród tych, które jeszcze nie zostały umieszczone w drzewie a który
ma największą wartość Gain. Dzięki temu zbudujemy małe drzewo decyzyjne,
które będzie w stanie sklasyfikować odpowiednio nowe rekordy w kilku krokach.
Gain daje lepsze wyniki w przypadku, gdy atrybut ma dużą liczbę rożnych wartości. Na przykład dla atrybutu D, który ma rozkład prawdopodobieństwa (0,1) Info(D,T)=0 zaś Gain(D,T) jest maksymalne i równe Info(T). Problem możemy zaobserwować w naszym przykładzie golfowym, Gain(Outlook,T) ma dużo większą wartość niż Gain(Windy,T), gdyż Outlook przyjmuje trzy wartości a Windy tylko dwie. Aby to zrównoważyć wprowadzono Gain Ratio:
gdzie SplitInfo(D,T) definiujemy następująco (zakładając że T1..Tm jest podziałem T indukowanym przez D):
W przykładzie golfowym mamy:
Rekurencyjny algorytm budowy drzewa, który jako danych wejściowych potrzebuje:
function ID3 (R: a set of non-categorical attributes,
C: the categorical attribute,
S: a training set) returns a decision tree;
begin
If S is empty, return a single node with value Failure;
If S consists of records all with the same value for
the categorical attribute,
return a single node with that value;
If R is empty, then return a single node with as value
the most frequent of the values of the categorical attribute
that are found in records of S; [note that then there
will be errors, that is, records that will be improperly
classified];
Let D be the attribute with largest Gain(D,S)
among attributes in R;
Let {dj| j=1,2, .., m} be the values of attribute D;
Let {Sj| j=1,2, .., m} be the subsets of S consisting
respectively of records with value dj for attribute D;
Return a tree with root labeled D and arcs labeled
d1, d2, .., dm going respectively to the trees
ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm);
end ID3;
do 
.
oraz na te, które mają wartość 
.
.
Dzięki temu zabiegowi otrzymujemy większą generalizację oceny nowych przypadków, a o to przecież nam chodziło.
Poniżej zaprezentuję efekty testów dla znajomych przykładów.
Play, Don't Play. outlook: sunny, overcast, rain. temperature: continuous. humidity: continuous. windy: true, false.
sunny, 85, 85, false, Don't Play sunny, 80, 90, true, Don't Play overcast, 83, 78, false, Play rain, 70, 96, false, Play rain, 68, 80, false, Play rain, 65, 70, true, Don't Play overcast, 64, 65, true, Play sunny, 72, 95, false, Don't Play sunny, 69, 70, false, Play rain, 75, 80, false, Play sunny, 75, 70, true, Play overcast, 72, 90, true, Play overcast, 81, 75, false, Play rain, 71, 80, true, Don't Play
C4.5 [release 8] decision tree generator Wed Mar 17 20:18:34 2004
----------------------------------------
Options:
File stem <golf>
Read 14 cases (4 attributes) from golf.data
Decision Tree:
outlook = overcast: Play (4.0)
outlook = sunny:
| humidity <= 75 : Play (2.0)
| humidity > 75 : Don't Play (3.0)
outlook = rain:
| windy = true: Don't Play (2.0)
| windy = false: Play (3.0)
Tree saved
Evaluation on training data (14 items):
Before Pruning After Pruning
---------------- ---------------------------
Size Errors Size Errors Estimate
8 0( 0.0%) 8 0( 0.0%) (38.5%) <<
C4.5 [release 8] rule generator Wed Mar 17 20:18:44 2004
-------------------------------
Options:
File stem <golf>
Read 14 cases (4 attributes) from golf
------------------
Processing tree 0
Final rules from tree 0:
Rule 2:
outlook = overcast
-> class Play [70.7%]<br>
Rule 4:
outlook = rain
windy = false
-> class Play [63.0%]
Rule 1:
outlook = sunny
humidity > 75
-> class Don't Play [63.0%]
Rule 3:
outlook = rain
windy = true
-> class Don't Play [50.0%]
Default class: Play
Evaluation on training data (14 items):
Rule Size Error Used Wrong Advantage
---- ---- ----- ---- ----- ---------
2 1 29.3% 4 0 (0.0%) 0 (0|0) Play
4 2 37.0% 3 0 (0.0%) 0 (0|0) Play
1 2 37.0% 3 0 (0.0%) 3 (3|0) Don't Play
3 2 50.0% 2 0 (0.0%) 2 (2|0) Don't Play
Tested 14, errors 0 (0.0%) <<
(a) (b) <-classified as
---- ----
9 (a): class Play
5 (b): class Don't Play
C4.5 [release 8] decision tree interpreter Thu Mar 18 20:59:20 2004
------------------------------------------
outlook: sunny
humidity: 23
Decision:
Play CF = 1.00 [ 0.50 - 1.00 ]
bare, bear. pos1: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition. pos2: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition. pos3: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition. pos4: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition. pos5: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition.
none, article, noun, verb, adverb, bare none, none, none, none, article, bare none, none, possessive, noun, verb, bare none, article, noun, noun, verb, bare verb, adverb, adverb, preposition, article, bare none, none, none, verb, adverb, bare none, none, none ,none, none, bare none, none, none, none, article, bear pronoun, verb, verb, preposition, article, bear none, none, pronoun, verb, article, bear none, none, adverb, noun, modal, bear none, none, adverb, noun, modal, bear none, pronoun, modal, pronoun, preposition, bear pronoun, verb, verb, pronoun, modal, bear none, none, none, verb, preposition, bear none, none, none, pronoun, modal, bear
C4.5 [release 8] decision tree generator Wed Mar 17 20:25:26 2004
----------------------------------------
Options:
File stem <bare>
Read 16 cases (5 attributes) from bare.data
Decision Tree:
pos5 = none: bare (1.0)
pos5 = verb: bare (2.0)
pos5 = noun: bear (0.0)
pos5 = adjective: bear (0.0)
pos5 = adverb: bare (2.0)
pos5 = article: bear (5.0/2.0)
pos5 = connective: bear (0.0)
pos5 = number: bear (0.0)
pos5 = possessive: bear (0.0)
pos5 = pronoun: bear (0.0)
pos5 = interjection: bear (0.0)
pos5 = modal: bear (4.0)
pos5 = preposition: bear (2.0)
Tree saved
Evaluation on training data (16 items):
Before Pruning After Pruning
---------------- ---------------------------
Size Errors Size Errors Estimate
14 2(12.5%) 14 2(12.5%) (51.0%) <<
Jak widać program po czasowniku zawsze będzie mówił, że chodziło o misia, zaś po czasowniku modalnym stwierdzi, że mieliśmy na myśli tolerowanie czegoś.
This document was generated using the LaTeX2HTML translator Version 2002 (1.62)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 -local_icons -html_version 3.2,latin2,unicode c4_5Main.tex
The translation was initiated by Przemyslaw Strzelczak on 2004-03-19