Univerzitet u Beogradu Elektrotehnički fakultet
Student: Darko Tamburić 3026/2013 Profesor: dr. Veljko Milutinović 1
Uvod C4.5 je DM algoritam za izgradnju stabla odlučivanja Stablo odlučivanja: Ciljani atribut Trening skup Čvor je atribut Diskretne vrednosti
Glavna pitanja Koji atribut uzeti za podelu Kada zaustaviti izgradju stabla
Darko Tamburić -
[email protected]
1/15
Postojeća rešenja CART Binarno grananje po vrednosti atributa Poboljšana mera homogenosti čvora
ID3 Samo diskretne vrednosti atributa Svi atributi moraju imati vrednosti Nije moguće skratiti stablo
Darko Tamburić -
[email protected]
2/15
Rad algoritma Entropija Gain Trening skup
C4.5 Ciljani atribut Darko Tamburić -
[email protected]
3/15
Kako birati čvor? Entropija kao mera neuređenosti skupa S c mogućih vrednosti ciljanog atributa pi - verovatnoća pojavljivanja i vrednosti u skupu S, pi = |Si| / |S| c
Entropy( S ) pi log2 ( pi ) i 1
Dobit prilikom podele na osnovu vrednosti atributa Fi
S – početni skup pre podele SV – skup dobijen podelom tako da ima vrednost v atributa Fi | Sv | Gain(S , Fi ) Entropy(S ) Entropy(Sv ) vValues( Fi ) | S |
Za podelu skupa S izabrati atribut Fi koji ima najveću dobit Darko Tamburić -
[email protected]
4/15
Primer (1) R.b.
Izgled vremena
Temperatura
Vlažnost vazduha
Vetrovito
Igrati tenis
1
sunčano
visoka
visoka
nije
ne
2
sunčano
visoka
visoka
jeste
ne
3
oblačno
visoka
visoka
nije
da
4
kišovito
umerena
visoka
nije
da
5
kišovito
niska
normalna
nije
da
6
kišovito
niska
normalna
jeste
ne
7
oblačno
niska
normalna
jeste
da
8
sunčano
umerena
visoka
nije
ne
9
sunčano
niska
normalna
nije
da
10
kišovito
umerena
normalna
nije
da
11
sunčano
umerena
normalna
jeste
da
12
oblačno
umerena
visoka
jeste
da
13
oblačno
visoka
normalna
nije
da
14
kišovito
umerena
visoka
jeste
ne
S={1,2,3,4,5,6,7,8,9,10,11,12,13,14} Entropy ( S )
9 9 5 5 log 2 log 2 0.9403 14 14 14 14 Darko Tamburić -
[email protected]
5/15
Primer (2) Izgled vremena Sunčano Oblačno Kišovito Da Ne Da Ne Da Ne 9,11 1,2,8 3,7,12,13 4,5,10 6,14 2 2 3 3 Entropy ( Suncano ) log 2 log 2 0.9710 5 5 5 5 4 4 0 0 Entropy (Oblacno ) log 2 log 2 0 4 4 4 4 3 3 2 2 Entropy ( Kisovito ) log 2 log 2 0.9710 5 5 5 5 5 Entropy( Suncano) 14 4 Gain( S , Izgled _ vrem ena) Entropy( S ) Entropy(Oblacno) 0.2467 14 Gain( S , Tem peratura) 0.0292 5 Entropy( Kisovito) Gain( S ,Vlaznost _ vazduha) 0.1518 14 Gain( S ,Vetrovito) 0.0481
Darko Tamburić -
[email protected]
6/15
Primer (3) Gain( S1, Tem peratura ) 0.5710 Gain( S1, Vlaznost _ vazduha) 0.9710 Gain( S1, Vetrovito) 0.0200
Sunčano Oblačno
Kišovito
DA (3,7,12,13)
Gain( S 2, Tem peratura ) 0.0200 Gain( S 2, Vlaznost _ vazduha) 0.0118 Gain( S 2, Vetrovito) 0.9710
Sunčano Oblačno
Kišovito
DA Visoka
Normalna
Jeste
Nije
NE
DA
NE
DA
(1,2,8)
(9,11)
(6,14)
(4,5,10)
Darko Tamburić -
[email protected]
7/15
Pravila odlučivanja Sunčano Oblačno
Kišovito
DA Visoka NE
Normalna DA
Jeste
Nije
NE
DA
If Izgled_vremena=Oblačno then Igrati tenis := DA If Izgled_vremena=Sunčano and Vlažnost_vazduha=Visoka then Igrati tenis := NE If Izgled_vremena=Sunčano and Vlažnost_vazduha=Normalna then Igrati tenis := DA If Izgled_vremena=Kišovito and Vetrovito=Jeste then Igrati tenis := NE If Izgled_vremena=Kišovito and Vetrovito=Nije then Igrati tenis := DA Darko Tamburić -
[email protected]
8/15
Nepoznate vrednosti atributa Postaviti ‘?’ Torka ne utiče na sračunavanje entropije i gain-a
Postaviti najčešću vrednost iz te kolone R.b.
Izgled vremena
Temperatura
1
sunčano
visoka
visoka
nije
ne
visoka
visoka
jeste
ne
visoka
nije
da
2
Vlažnost vazduha Vetrovito
Igrati tenis
3
oblačno
4
kišovito
umerena
R.b.
Izgled vremena
Temperatura
1
sunčano
visoka
visoka
nije
ne
2
?
visoka
visoka
jeste
ne
3
oblačno
?
visoka
nije
da
4
kišovito
umerena
visoka
?
da
visoka
da
Vlažnost vazduha Vetrovito
Darko Tamburić -
[email protected]
Igrati tenis
9/15
Zaustavljanje izgradnje stabla Ista vrednost ciljanog atributa Odsecanje stabla(Pruning) broj torki u skupu je ispod definisanog minimuma stablo postalo preduboko ne može se poboljšati dobitak
Darko Tamburić -
[email protected]
10/15
Implementacija (pseudocode) Proveriti početne uslove Za svaki atribut a Naći normalizovan information gain za podelu na osnovu atributa a
Neka a_best bude atribut sa najvećim normalizovanim information gain-om Napravi se čvor koji se deli na osnovu a_best atributa Rekurzivno primeniti algoritam na podskupove nastale na osnovu podele zbog a_best atributa Darko Tamburić -
[email protected]
11/15
Primena Opis 1.Košarka,Evropsko,2005 2.Odbojka,Evropsko,2005 3.Vaterpolo,Evropsko,2006 4.Odbojka,Evropsko,2011 5.Rukomet,Evropsko,2012 6.Rukomet,Evropsko,2012 Rukomet,Svetsko,2013
Pol Protiv prošlog šampiona Broj igrača Medalja? M Nisu igrali 5 Ne(9) M Izgubili 6 Da(3) M Pobedili 7 Da(1) Ž Nisu igrali 6 Da(1) Ž Izgubili 7 Ne(4) M Nisu igrali 7 Da(2) Ž
Pobedili
5
NE
6
7
?
7
DA
Darko Tamburić -
[email protected]
M
Ž
DA
NE
12/15
Zaključak Dubinsko izgrađivanje stabla Brza klasifikacija novih podataka Jednostavna implementacija Poboljšanja u C5 algoritmu: Troši se manje memorije Stablo odlučivanja je manje Veća brzina izgradnje stabla Odstranjivanje nepotrebnih atributa Darko Tamburić -
[email protected]
13/15
Literatura 1. D. Larose, “Discovering knowledge in data”, John Wiley & Sons, New Jersey, 2005, pp. 116-122 2. J.R.Quinlan,”C4.5:Programs for machine learning”, Morgan Kaufman, San Francisco, 1993, pp. 27-42 3. I.H.Witten and E.Frank, ”Data Mining-Practical Machine Learning Tools and Techniques”, Morgan Kaufman, San Francisco, 2005, pp. 189-199 4. -, http://en.wikipedia.org/wiki/C4.5_algorithm , Wikipedia-the free encyclopedia, 19.12.2013
Darko Tamburić -
[email protected]
14/15
Hvala na pažnji!
Darko Tamburić
[email protected] 15/15
