[e-mail] 2006

Drzewa decyzyjne

Klasyfikacja

Czynność podziału zbioru na podzbiory
nazwane klasami. Podziałem zbioru X nazywa
się każdy zupełny i rozłączny układ podzbiorów
tego zbioru.

W wyniku klasyfikacji określamy nieznaną
wartość pewnego atrybutu obiektu,
przyjmującego skończoną liczbę wartości.

Drzewo decyzyjne

Drzewo decyzyjne jest
to drzewo, w którym:



węzły nie będące liśćmi
odpowiadają atrybutom



gałęzie wychodzące z
takiego węzła odpowiadają
wartościom tego atrybutu.



liście odpowiadają
wartościom zmiennej
decyzyjnej (atrybutu
klasyfikującego)

Zasady konstrukcji drzewa decyzyjnego

1.

Punktem wyjścia jest korzeń drzewa, któremu odpowiada ciąg uczący T, w którym
znajdują się obserwacje, z których każda opisane jest atrybutami i zaklasyfikowana
jest do jednej z klas na podstawie pewnego wyróżnionego atrybutu (zmiennej
klasyfikującej, decyzyjnej).

2.

Konstrukcja drzewa opiera się na następującej procedurze powtarzanej rekurencyjnie
dla każdego węzła począwszy od korzenia:

•

Ciąg danych uczących T zawierający przynajmniej jeden element, przy czym
wszystkie elementy należą do tej samej klasy C

j.

Drzewo decyzyjne dla T jest

liściem wskazującym na kategorię C

j.

•

Ciąg uczący T nie zawiera żadnych elementów – podobnie jak w punkcie
poprzednim, drzewo dla T jest liściem jednak związany jest z klasą wyznaczoną
na podstawie poprzednika

•

T zawiera elementy należące do różnych klas. Podział T na takie podzbiory, by
wszystkie elementy w ramach podzbioru należały do tej samej klasy (podzbiory
powinny być możliwie jednorodne). W oparciu o pojedynczy wybrany atrybut,
przeprowadzany jest test, który powoduje podział na rozłączne podzbiory.
Drzewo decyzyjne dla T jest węzłem zawierającym test i jedną gałąź dla każdego
wyniku testu.

3.

Po zakończeniu procedury generowania węzłów drzewa, może opcjonalnie nastąpić
przycinanie drzewa (zastąpienie całego poddrzewa pojedynczym liściem).

Algorytmy budowy drzew

Elementy algorytmów budowania drzewa decyzyjnego:



kryterium wyboru atrybutu używanego jako test w węźle drzewa



wyznaczenie wartości atrybutów dla gałęzi wychodzących z
węzła (rząd drzewa)

Przykładowe algorytmy



ID3 (Quinlan)



C4.5 (Quinlan) rozszerzenie ID3 o brakujące wartości, atrybuty

ciągłe, obcinanie drzewa)



CART (Classification And Regression Trees) – drzewo binarne.



CHAID (Chi-squared Automatic Interaction Detector, 1980),

Wybór atrybutu testowego dla węzła

T – zbiór uczący, w którym każda obserwacja zaklasyfikowana jest według wartości atrybutu C do
jednej z k klas {C

1

, C

2

... C

k

}

Entropia zbioru S:

T

T

C

freq

T

T

C

freq

T

Info

i

k

i

i

)

,

(

log

)

,

(

)

(

1

2

∑

=

−

=

T

1

, T

2

...T

n

- rozłączne podzbiory zbioru T, utworzone na podstawie pewnego testu t. Test jest

oparty o wartości atrybutu X.

Entropia zbioru przykładów ze względu na wynik r testu t jest definiowana jako ważona entropia
dla poszczególnych wyników testu:

∑

=

⋅

=

n

r

i

r

x

T

Info

T

T

T

Info

1

)

(

)

(

,

Przyrost informacji wynikający z zastosowania testu opartego na wartościach atrybutu X do zbioru
przykładów:

Gain(X) = Info(T) - Info

x

(T)

Jako podstawę podziału zbioru obserwacji w węźle wybieramy ten atrybut, dla którego Gain(X)
jest maksymalne.

Inne kryteria wyboru testu

Kryterium przyrostu informacji - tendencja do nieuzasadnionego preferowania testów o wielu
możliwych wynikach.

Współczynnik przyrostu informacji:

T

T

T

T

T

Info

Split

i

n

i

i

∑

=

=

1

2

log

)

(

_

Wartość mierzy równomierność, z jaką test t dzieli zbiór uczący na podzbiory. Jest ona duża jeśli
rozmiary podzbiorów wyznaczonych przez różne wyniki testu są zbliżone i maleje przy wyraźnej
przewadze niektórych podzbiorów nad innymi.

)

(

_

)

(

)

(

_

X

Split

X

Gain

X

ratio

Gain

Info

=

Algorytm Id3

Podział – atrybuty ciągłe

Zbiór wartości, które przyjmuje atrybut sortujemy
{v

1

, v

2

,… v

k

}

Rozważamy wszystkie (k-1) potencjalnych punktów
podziału: {v

1

, v

2

,… v

i

} {v

i+1

, v

i+2

,… v

k

}

Wybieramy tą wartość podziału Z, dla którego kryterium
przyrostu informacji jest największe. Gałęzie opisane są
nie pojedynczymi wartościami atrybutu, lecz podzbiorami
wartości, wyznaczonymi przez punkt podziału Z.

Przykład

Zbudować drzewo decyzyjne dla
wyznaczania wartości atrybutu C w
oparciu o wartości atrybutów A1, A2.

Ciąg uczący:

A1

A2

C

Y

1

C2

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

A1

A2

C

Y

1

C2

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

A1

A2

C

Y

1

C2

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

A1

A1

A1

A2

A2

A2

C

C

C

Y

Y

1

1

C2

C2

Y

Y

2

2

C1

C1

N

N

2

2

C2

C2

N

N

2

2

C2

C2

N

N

2

2

C1

C1

N = 5
C1 2 (40%)
C2 3 (60%)

97

,

0

)

74

,

0

(

5

3

)

32

,

1

(

5

2

5

3

log

5

3

5

2

log

5

2

)

(

2

2

=

−

⋅

−

−

⋅

−

=













−













−

=

T

Info

0,03

0,94

-

0,97

Gain(A1)

94

,

0

91

,

0

5

3

1

5

2

)

(

91

,

0

)

59

,

1

(

3

1

)

59

,

0

(

3

2

3

1

log

3

1

3

2

log

3

2

)

(

1

2

1

log

2

1

2

1

log

2

1

)

(

)

(

5

3

)

(

5

2

)

(

1

2

2

'

'

1

2

2

'

'

1

'

'

1

'

'

1

1

=

=

=

⋅

+

⋅

=

=

−

−

−

⋅

−

=













−













−

=

=













−













−

=

+

⋅

=

=

=

=

=

T

Info

T

Info

T

Info

T

Info

T

Info

T

Info

A

N

A

Y

A

N

A

Y

A

A

0,18

0,8

-

0,97

Gain(A2)

8

,

0

1

5

4

0

5

1

)

(

0

)

(

1

2

1

log

2

1

2

1

log

2

1

)

(

)

(

5

4

)

(

5

1

)

(

2

1

2

2

2

2

2

2

2

1

2

2

=

=

=

⋅

+

⋅

=

=

=













−













−

=

+

⋅

=

=

=

=

=

T

Info

T

Info

T

Info

T

Info

T

Info

T

Info

A

A

A

A

A

A

Podział następuje ze względu na A2, gdyż Gain(A2) > Gain(A1)

A1

A2

C

Y

1

C2

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

A1

A2

C

Y

1

C2

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

A1

A1

A1

A2

A2

A2

C

C

C

Y

Y

1

1

C2

C2

Y

Y

2

2

C1

C1

N

N

2

2

C2

C2

N

N

2

2

C2

C2

N

N

2

2

C1

C1

N = 5
C1 2 (40%)
C2 3 (60%)

N = 4
C1 2 (50%)
C2 2 (50%)

A2

A2=2

A2=1

N = 1
C1 0 (0%)
C2 1 (100%)

A1

A2

C

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

A1

A2

C

Y

1

C2

A1

A2

C

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

1

2

1

log

2

1

2

1

log

2

1

)

(

2

2

=













−













−

=

T

Info

0,32

0,68

-

1

Gain(A1)

68

,

0

91

,

0

4

3

0

)

(

91

,

0

)

59

,

1

(

3

1

)

59

,

0

(

3

2

3

1

log

3

1

3

2

log

3

2

)

(

0

)

(

)

(

4

3

)

(

4

1

)

(

1

2

2

'

'

1

'

'

1

'

'

1

'

'

1

1

=

=

=

⋅

+

=

=

−

−

−

⋅

−

=













−













−

=

=

+

⋅

=

=

=

=

=

T

Info

T

Info

T

Info

T

Info

T

Info

T

Info

A

N

A

Y

A

N

A

Y

A

A

0

1

-

1

Gain(A2)

1

)

(

1

2

1

log

2

1

2

1

log

2

1

)

(

)

(

0

)

(

4

4

)

(

2

2

2

2

2

2

2

2

2

2

=

=

=

=













−













−

=

⋅

+

⋅

=

=

=

=

T

Info

T

Info

T

Info

T

Info

T

Info

A

A

A

A

A

Podział następuje ze względu na A1, gdyż Gain(A1) > Gain(A2)

A1

A2

C

Y

1

C2

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

A1

A2

C

Y

1

C2

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

A1

A1

A1

A2

A2

A2

C

C

C

Y

Y

1

1

C2

C2

Y

Y

2

2

C1

C1

N

N

2

2

C2

C2

N

N

2

2

C2

C2

N

N

2

2

C1

C1

N = 5
C1 2 (40%)
C2 3 (60%)

N = 4
C1 2 (50% )
C2 2 (50% )

A2

A2=2

A2=1

N = 1
C1 0 (0% )
C2 1 (100% )

A1

A2

C

Y

2

C1

N

2

C2

N

2

C2

N

2

C1

A1

A2

C

Y

1

C2

N = 1
C1 1 (100% )
C2 0 (0% )

A1

A1=Y

A1=N

N = 3
C1 1 (33% )
C2 2 (67% )

A1

A2

C

N

2

C2

N

2

C2

N

2

C1

A1

A2

C

Y

2

C1

Szacowanie błędów klasyfikacji

Przedział ufności o poziomie ufności 1-p dla parametru
p rozkładu dwumianowego:

N – liczba prób, p – prawdopodobieństwo sukcesu w
pojedynczej próbie.

P nie jest znana, do jej oszacowania na podstawie
eksperymentu

Yp – estymator – liczba sukcesów do liczby wykonanych
prób,

Przedział ufności dla estymatora:

Klasyfikowanie przykładów ma cechy próby
Bernoullliego: sukcesem jest pomyłka w klasyfikacji.

Przycinanie drzewa (prunning)

Obcinanie polega na zastąpieniu poddrzewa liściem, którym przypisuje się
etykietę kategorii najczęściej występującej wśród związanych z nim
przykładów.



Nadmierne dopasowanie do danych trenujących (overfitted) – duży błąd dla
danych spoza ciągu uczącego



Zbudowane drzewo ma zbyt dużą wysokość (niedopuszczalna złożoność
procedury klasyfikującej)

Począwszy od dołu drzewa, dla każdego poddrzewa nie będącego liściem:



Obcinamy, jeżeli zastąpienie poddrzewa liściem z przypisaną kategorią
reprezentowaną przez potomka o największej liczności zmniejsza błąd.
Modyfikacja błędów dla rodziców.

Estymacja błędu klasyfikacji:



Szacowanie na podstawie błędu próbki na oddzielnym zbiorze przycinania,
złożonym z przykładów spoza zbioru trenującego.



Szacowanie na podstawie błędu próbki na zbiorze trenującym.

Zadanie

Na podstawie zbioru danych
treningowych ( ciągu
uczącego)



Znaleźć wartość podziału dla
atrybutu A



Znaleźć wartość podziału dla
atrybutu B



Zbudować drzewo decyzyjne

Jaki jest proporcja błędnych
klasyfikacji dla ciągu
testowego ?

Literatura

Paweł Cichosz „Systemy uczące się” WNT
2000

Hand David, Mannila Heikki, Smyth
Padhraic „Eksploracja danych”, WNT 2005