VII EKSPLORACJA DANYCH

Drzewa decyzyjne …

VII EKSPLORACJA DANYCH

Drzewa decyzyjne …

VII EKSPLORACJA DANYCH

Drzewa decyzyjne …

VII EKSPLORACJA DANYCH

Drzewa decyzyjne …

VII EKSPLORACJA DANYCH

Drzewa decyzyjne …

VII EKSPLORACJA DANYCH

Jak drzewa decyzyjne wybierają atrybut
dzielący:

Drzewa decyzyjne starają się stworzyć zbiór liści,
które są najczystsze, tzn. takie które zawierają
jak najwięcej rekordów należących do tej samej
klasy. W ten sposób drzewa decyzyjne
zapewniają przypisanie do klasy z największą
miarą ufności.

Metod określania jednorodności będącej miarą
czystości liści jest wiele, a dwie
najpopularniejsze to:

Algorytm drzew klasyfikacyjnych i regresyjnych

CART

Algorytm C4.5

VII EKSPLORACJA DANYCH

Algorytm drzew klasyfikacyjnych CART

Φ

(s│t) = 2 P

L

P

P



(s│t)

gdzie:



(s│t) =

Σ

│

P(j│t

L

) – P(j│t

P

)

│

VII EKSPLORACJA DANYCH

Algorytm drzew klasyfikacyjnych CART

P

L

=

liczba rekordów w t

L

liczba rekordów w zbiorze uczącym

P

P

=

liczba rekordów w t

P

liczba rekordów w zbiorze uczącym

Φ

(s│t) = 2 P

L

P

P



(s│t)

VII EKSPLORACJA DANYCH

Algorytm drzew klasyfikacyjnych CART



(s│t) =

Σ

│

P(j│t

L

) – P(j│t

P

)

│

P(j│t

L

) =

liczba rekordów należących do klasy j w t

L

liczba rekordów w t

P(j│t

P

) =

liczba rekordów należących do klasy j w t

P

liczba rekordów w t

VII EKSPLORACJA DANYCH

Algorytm drzew klasyfikacyjnych CART

VII EKSPLORACJA DANYCH

Algorytm drzew klasyfikacyjnych CART

Podział Lewe poddrzewo

Prawe poddrzewo

1

zawartość węgla = mała

zawartość węgla = duża

2

zawartość manganu = mała zawartość manganu = duża

3

zawartość krzemu = mała

zawartość krzemu = duża

4

zawartość miedzi = mała

zawartość miedzi  {średnia, duża}

5

zawartość miedzi = średnia zawartość miedzi  {mała, duża}

6

zawartość miedzi = duża

zawartość miedzi  {mała, średnia}

7

zawartość magnezu = mała zawartość magnezu = duża

VII EKSPLORACJA DANYCH

Algorytm drzew klasyfikacyjnych CART

VII EKSPLORACJA DANYCH

Algorytm drzew klasyfikacyjnych CART

R

N

N

L

L

N

L

zawartość Si

5 mała, 1 średnia
zawartość Mn

duża 6

mała 14

8 średnia, 6 duża
zawartość Mn

duża 9

mała 5

5 średnia3 średnia, 6 duża

duża 1

mała 5

5 mała

1 średnia

VII EKSPLORACJA DANYCH

Algorytm C 4.5

Algorytm ID3 jest jednym z algorytmów

operujących

na

drzewach

decyzyjnych,

opracowanym w 1986 roku przez Rossa Quinlana.
Cechą charakterystyczną algorytmu jest wybór
atrybutów, dla których kolejno przeprowadzane są
testy pozwalające, by końcowe drzewo było jak
najprostsze i jak najefektywniejsze. Wybór atrybutu
bazuje na liczeniu entropii. Algorytm C4.5 jest
rozwinięciem algorytmu ID3 opracowanym w 1993
roku również przez Quinlana.

VII EKSPLORACJA DANYCH

Algorytm C 4.5

•

Algorytmy C4.5 nie jest ograniczony do

binarnych podziałów. Podczas, gdy CART tworzy
drzewo binarne, C4.5 tworzy drzewo o bardziej
zróżnicowanym kształcie.

•

Dla zmiennych jakościowych algorytm C4.5 z

definicji tworzy osobne gałęzie dla każdej wartości
atrybutu jakościowego. Może to powodować
nadmierne rozgałęzienie.

•

Metoda mierzenia jednorodności w

algorytmie C4.5 jest zupełnie inna niż w
algorytmie CART i używa pojęcia zysk informacji
lub redukcja entropii.

VII EKSPLORACJA DANYCH

Algorytm C 4.5

H(X) = –Σ p

j

log

2

(p

j

)

Dla zmiennej X przyjmującej k możliwych
wartości z prawdopodobieństwem p
odpowiednio p

1

, p

2

, …p

i

, można zdefiniować

wielkość nazwaną entropią X określoną
wzorem:

VII EKSPLORACJA DANYCH

Algorytm C 4.5

Dla założenia, że możliwy jest podział S,
dzielący zbiór T na kilka podzbiorów T

1

, T

2

, …

T

k

, wówczas ważona suma entropii dla

pojedynczych podzbiorów określona jest
wzorem:

H

S

(T) = Σ P

i

H

S

(T

i

)

i=1

k

VII EKSPLORACJA DANYCH

H(X) = –Σ p

j

log

2

(p

j

)

H

S

(T) = Σ P

i

H

S

(T

i

)

i=1

k

VII EKSPLORACJA DANYCH

H(X) = –Σ p

j

log

2

(p

j

)

Wytrzymałość:
mała – 5
średnia – 9
duża – 6

VII EKSPLORACJA DANYCH

R

N

N

zawartość C

3 mała,
5 średnia,
1 duża

duża 9

mała 11

2 mała,
4 średnia,
5 duża

VII EKSPLORACJA DANYCH

R

N

N

zawartość C

3 mała,
5 średnia,
1 duża

duża 9

mała 11

2 mała,
4 średnia,
5 duża

VII EKSPLORACJA DANYCH

VII EKSPLORACJA DANYCH

R

N

N

zawartość Cu

0 mała,
0 średnia,
5 duża

duża 5

mała 9

5 mała,
4 średnia,
0 duża

N

0 mała,
5 średnia,
1 duża

średnia 6

VII EKSPLORACJA DANYCH

Wady drzew decyzyjnych

•

im więcej klas oraz im bardziej się one

nakładają,

tym większe drzewo decyzyjne

•

trudno zapewnić jednocześnie wysoką

jakość

klasyfikacji i małe rozmiary drzewa

•

w węzłach testowany jeden

atrybut

VII EKSPLORACJA DANYCH

Wady drzew decyzyjnych nadmierne
dopasowanie

•

nadmierne uczenie prowadzi do

dopasowania także do zaszumionych danych

•

zbudowane drzewo dobrze radzi sobie z

danymi ze zbioru uczącego i źle z danymi ze
zbioru testującego

•

drzewo ma niską zdolność do generalizacji

dla nowych danych

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: dlaczego ?

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: przycinanie

dead
branc
h

codominant
stems

included
bark

dead
branch

water
sprouts

broken
branch

decay

sucke
r

Źródło:
Vancouver Urban Forestry
www.cityofvancouver.us/urbanforestry

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: przycinanie

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: dlaczego ?

Czy przycinanie poprawia dokładność:

•

w większości przypadków TAK,

•

ale efekty zależą od obszaru

zastosowania

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: metody

Przycinanie drzew może być

prowadzone na dwa sposoby:

•

pre – pruning (fw) polegający na

zatrzymaniu rozrostu drzewa jeśli prowadzi
to do tworzenia węzłów i liści grupujących
nieliczne przypadki

•

post – pruning, w którym prowadzimy do

wzrostu pełnego drzewa i dopiero wówczas
dokonujemy cięć

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: metody

Pre-pruning

Post-pruning

•

pre – pruning (fw) jest uważany za rozwiązanie gorsze

•

post – pruning, wykorzystuje poddrzewa (potomków)

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: metody

Przycinanie drzew metodami post:

•

zbuduj pełne drzewo decyzyjne,

pozwalając nawet na nadmierne
dopasowanie

•

przekształć drzewo w zbiór reguł

decyzyjnych

•

przycinaj każdą regułę niezależnie od

innych

•

uporządkuj pozostałe reguły w

sekwencję zdań gotową do użycia

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: metody

Przycinanie drzew metodami post:

•

reduced error pruning REP

•

minimum error pruning

MEP

•

pessimistic error pruning

PEP

•

error - based pruning

EBP

•

cost - complexity pruning

CCP

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: metody

Zbiór danych

Zbiór uczący

Zbiór do wzrostu drzewa

Zbiór do przycinania drzewa

Zbiór testujący

70 %

30 %

70 %

30 %

Typowy (powszechnie stosowany) podział danych na zbiory:

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania:

REP

Algorytm postępowania w metodzie

REP:

•

zbuduj drzewo korzystając z całego zbioru

uczącego

•

losowo wybierz i usuń węzeł

•

zamień węzeł w jego większościową

reprezentację

•

jeśli zmodyfikowane drzewo sprawdzane na

zbiorze testującym jest tak samo dobre lub
lepsze od drzewa podstawowego zastosuj je

•

powróć do punktu 2

VII EKSPLORACJA DANYCH

Unikanie nadmiernego dopasowania: REP,MEP,PEP

Większość algorytmów przycinania (reduced error
pruning, pessimistic error pruning, minimum error
pruning) opiera się na następującym schemacie:

repeat

przeglądaj węzły wewnętrzne drzewa T
if błąd dla poddrzewa T

t

> błąd dla liścia t

then

zastąp poddrzewo T

t

liściem

przypisz do liścia t etykietę

odpowiedniej

klasy

end if
until przycinanie zmniejsza błąd

Poszczególne metody różnią się sposobem szacowania błędu oraz
kolejnością przeglądania węzłów drzewa.