Microsoft PowerPoint - hd-06-drzewa-decyzyjne

decyzyjne

Tadeusz Pankowski

www.put.poznan.pl/~tadeusz.pankowski

Klasyfikacja obiekt

–

Drzewa decyzyjne

decyzyjne

Klasyfikacja i predykcja

1. Odkrywaniem

reguł klasyfikacji

nazywamy proces

znajdowania modeli (lub funkcji) klasyfikacji

umożliwiających określenie klasy, do której powinien

należeć wskazany obiekt.

2. Model klasyfikacji budowany jest w wyniku analizy zbioru

danych treningowych

, tj. zbioru obiektów o znanej

przynależności klasowej.

3. Model klasyfikacji może być reprezentowany za pomocą:

• reguł o postaci IF_THEN,
• drzew decyzyjnych,
• sieci neuronowych,
• innych ...

decyzyjne

Klasyfikacja i predykcja

1. Klasyfikacja danych jest procesem dwuetapowym.

2. W pierwszym kroku budowany jest model (np. relacyjny)

opisujący zadany zbiór danych (treningowy zbiór

danych) składający się ze zbioru obiektów (krotek)

opisanych za pomocą atrybutów.

3. Jeden z atrybutów jest

atrybutem klasyfikującym

(predykcyjnym)

i jego wartości określają

etykiety klas

do których należą obiekty.

4. Obiekty tworzące zbiór treningowy wybierane są losowo

z pewnej populacji.

5. Ten etap klasyfikacji nazywany jest też

uczeniem z

nadzorem

, gdyż podana jest klasyfikacja każdego

obiektu (przykładem nauczania bez nadzoru jest

tworzenie skupień,

clustering

)

decyzyjne

Klasyfikacja i predykcja (c.d.)

Utworzony model klasyfikacji reprezentowany jest w postaci:

reguł klasyfikacji,
drzew decyzyjnych,
formuł matematycznych.

Przykład: mając bazę danych z informacjami o osobach (wiek,

wykształcenie, dochód, pochodzenie społeczne) można utworzyć

reguły klasyfikacyjne istotne dla biur turystycznych (tzn. reguły

określające, w jakiego rodzaju wycieczkach osoby te byłyby skłonne

uczestniczyć).

Podstawą utworzenia tych reguł jest analiza dotychczas znanych

przypadków opisujących zachowanie się klientów. Przypadki te

tworzą zbiór treningowy (uczący).

Reguły mogą być wykorzystane do klasyfikacji przyszłych

przypadków, jak również do lepszego zrozumienia zawartości bazy

danych.

decyzyjne

Klasyfikacja i predykcja (c.d.)

Utworzony model jest następnie używany do klasyfikacji.

Najpierw oceniana jest dokładność modelu (klasyfikatora). W tym

celu posługujemy się zbiorem testowym, który wybrany jest

losowo i jest niezależny od zbioru treningowego.

okładność

modelu na zadanym zbiorze testowym określona jest

przez procentową liczbę trafnych klasyfikacji, tzn. jaki procent

przypadków testowych został prawidłowo zaklasyfikowany za

pomocą modelu. Dla każdego przypadku możemy porównać znaną

etykietę klasy z etykietą przypisaną przez model.

Jeśli dokładność modelu została oceniona jako wystarczająca,

model można użyć do klasyfikacji przyszłych przypadków

(obiektów) o nieznanej etykiecie klasy.

decyzyjne

Klasyfikacja i predykcja (c.d.)

W czym

predykcja

różni się od

klasyfikacji

redykcja

(

przewidywanie

) może być rozumiana jako

wykorzystanie modelu do oszacowania (obliczenia) wartości

(lub przedziału wartości), jaką z dużym prawdopodobieństwem

może mieć atrybut analizowanego obiektu. Wartością tego

atrybutu może być w szczególności etykieta klasy.

Z tego punktu widzenia

klasyfikacja

regresja

są dwoma

głównymi rodzajami problemów predykcyjnych; przy czym

klasyfikacja jest używana do przewidzenia wartości

dyskretnych lub nominalnych, a

regresja

do oszacowania

wartości ciągłych lub uporządkowanych.

Umowa:

przewidywanie etykiet klas –

klasyfikacja

przewidywanie wartości ciągłych (technikami regresji) –

predykacja

decyzyjne

Klasyfikacja i predykcja

–

zastosowania

¾ Klasyfikacja i predykcja mają wiele zastosowań,

na przykład:

akceptacja udzielenia kredytu,
diagnostyka medyczna,
przewidywanie wydajności,
selektywny marketing,
inne

decyzyjne

Klasyfikacja za pomoc

drzew

decyzyjnych

1. Drzewo decyzyjne jest diagramem przepływu o

strukturze drzewa, gdzie każdy wierzchołek wewnętrzny

oznacza

testowanie

atrybutu, każda krawędź

reprezentuje

wyjście

z testu (wartość lub zbiór wartości

atrybutu), a każdy liść reprezentuje

klasę

2. W celu sklasyfikowania nieznanego obiektu wartości jego

atrybutów testowane są zgodnie z informacją zawartą w

drzewie decyzyjnym.

3. W procesie testowania przechodzimy ścieżkę w drzewie

od korzenia do jednego z liści – w ten sposób określana

jest klasa, do której zostanie zaklasyfikowany obiekt.

4. Drzewa decyzyjne mogą być łatwo przekształcone w

reguły klasyfikacyjne.

decyzyjne

Drzewo decyzyjne

–

inna kolejno

ść

testowania atrybut

decyzyjne

Drzewa decyzyjne klasyfikuj

ce dane

treningowe

–

dwa warianty

decyzyjne

Budowa drzewa decyzyjnego

–

podstawy teorii informacji

Charakterystyka zbioru treningowego

S - zbiór złożony z s obiektów (zbiór treningowy), s = 14
m – liczba klas, do których klasyfikowane są obiekty; etykiety klas

określone są przez atrybut "ZakupKomp", który przyjmuje dwie

wartości: TAK, NIE; m = 2
C

- klasa TAK, C

- klasa NIE

- liczba obiektów w C

, s

- liczba obiektów w C

, s

= 9, s

= 5

- prawdopodobieństwo, że losowo wybrany obiekt należy do

klasy C

, 0 < p

< 1, p

+ p

E(p

, p

) - oczekiwana informacja potrzebna do klasyfikacji

danego obiektu (

entropia układu

E(p

,... ,p

) = – p

*log

) – p

log

), I(9/14, 5/14) = 0.9403

Entropia uk

adu

Niech danych będzie układ złożony z 8 jednoelementowych klas.

Entropia

tego układu wyraża się wzorem:

Entr(1,1,1,1,1,1,1,1) = log

8 = 3

i oznacza średnią

ilość informacji

(

bitów informacji

), jaka jest potrzebna,

aby zadany element zaklasyfikować do jednej z tych klas. (Argumenty

funkcji Entr oznaczają liczbę elementów w zbiorach tworzących układ).

{0} {1} {2} {3} {4} {5} {6} {7}

Entropia uk

adu

{0} {1} {2} {3} {4} {5} {6} {7}

•

Komunikat, że obiekt należy do klasy {i}

niesie w sobie

(

zawiera, przekazuje

) 3 bity

informacji.

•

Prawdopodobieństwo wyboru klasy {i} wynosi 1/8.

•

Zatem średnia ważona (entropia) całego układu, a więc średnia ilość informacji

(bitów informacji) przekazywana w komunikacie, że obiekt należy do klasy {i}

jest równa ilości informacji potrzebnej do zaklasyfikowania obiektu do klasy {i}

wyraża się wzorem:

−

∑

log

)

(

Entr

Entropia uk

adu

{0,1} {2,3} {4,5} {6,7}

−

∑

log

)

(

Entr

Dla rozważanego przykładu utwórzmy klasy 2-elementowe.

Wówczas:

•

Komunikat, że obiekt należy do określonej klasy

niesie:

log

8/2 = 2 bity informacji.

•

Prawdopodobieństwo wyboru każdej klasy wynosi 2/8.

•

Zatem entropia układu, a więc średnia ilość informacji (bitów informacji)

potrzebnej do zaklasyfikowania obiektu do klasy wyraża się wzorem:

Entropia uk

adu

Utwórzmy teraz 3 klasy, które zawierają odpowiednio: 1, 2 i 5 elementów.
Zauważmy, że wówczas:
•

ilość informacji potrzebnej do zaklasyfikowania obiektu do każdej z

tych klas wynosi odpowiednio:

log

8 = 3, log

4 = 2, log

8/5 = 0,678

•

prawdopodobieństwo, że obiekt zaklasyfikowany zostanie do każdej z

grup wynosi odpowiednio:

1/8, 1/4, 5/8

•

entropia tego układu (średnia ilość informacji potrzebna do

zaklasyfikowania obiektu do klasy) jest więc równa:

{0} {1, 2} {3, 4, 5, 6, 7}

log

)

(

Entr

Entropia dla przyk

adowych uk

1,585

1,555

1,500

1,483

1,459

1,384

1,252

1,325

1,281

1,189

1,041

0,817

0,414

0,000

Entropia

Klasa3

Klasa2

Klasa1

Entropia dla trzech klas zawierających 12 elementów

log

)

(

∑

−

(Argumentami funkcji E są prawdopodobieństwa przynależności elementów do
poszczególnych zbiorów tworzących układ.)

Entropia

–

podsumowanie

Entropia układu jednostkowego złożonego ze zbioru A o
prawdopodobieństwie p:

E(p) = – log

(p)

Entropia układu jednostkowego złożonego ze zbioru o
prawdopodobieństwie 1 jest równa 0

E(1) = 0

Entropia układu jednostkowego złożonego ze zbioru będącego
sumą zbiorów rozłącznych o prawdopodobieństwach odpowiednio
p

i p

, jest równa entropii układu jednostkowego złożonego ze

zbioru o prawdopodobieństwie p

+ p

E(p

∪ B

) = E(p

+ p

)

Entropia układu złożonego z n zbiorów o prawdopodobieństwach
odpowiednio p

, …, p

, jest średnią ważoną entropii n układów

jednostkowych złożonych z każdego z tych zbiorów:

E(p

,…,p

) = – (p

E(p

) + … + p

E(p

))

Analiza informacyjna

–

miara ilo

ci informacji

I(s1,s2)

h=log(N/s;2)

1,0000

13,0000

0,0714

0,9286

0,3712

3,8074

2,0000

12,0000

0,1429

0,8571

0,5917

2,8074

3,0000

11,0000

0,2143

0,7857

0,7496

2,2224

4,0000

10,0000

0,2857

0,7143

0,8631

1,8074

5,0000

9,0000

0,3571

0,6429

0,9403

1,4854

6,0000

8,0000

0,4286

0,5714

0,9852

1,2224

7,0000

0,5000

1,0000

8,0000

6,0000

0,5714

0,4286

0,9852

0,8074

9,0000

5,0000

0,6429

0,3571

0,9403

0,6374

10,0000

4,0000

0,7143

0,2857

0,8631

0,4854

11,0000

3,0000

0,7857

0,2143

0,7496

0,3479

12,0000

2,0000

0,8571

0,1429

0,5917

0,2224

13,0000

1,0000

0,9286

0,0714

0,3712

0,1069

14,0000

0,0000

1,0000

0,0000

h = log

(N/s) = log

(1/p) = -log

(p) – wysokość binarnego drzewa poszukiwań obiektu,

= ilość bitów informacji potrzebna do klasyfikacji obiektu do klasy o prawdopodob.

= ilość informacji, jaką posiadamy wiedząc, że obiekt należy do klasy o prawdop.

I(s

, s

) = średnia ważona klasyfikacji obiektu do jednej z dwóch klas (entropia układu!)

decyzyjne

Entropia

–

miara ilo

ci informacji

1. Powyższy wzór wyraża entropię układu składającego się z

rozłącznych klas (podzbiorów):

, ...,

o liczebnościach,

odpowiednio s

,…, s

; s

+…+ s

= s.

2. Prawdopodobieństwo zaklasyfikowania obiektu do klasy

wynosi

= s

/s, 0 <

< 1,

= 1,2, ...,

3. Wzór wyraża oczekiwaną ilość informacji potrzebną do

zaklasyfikowania podanego obiektu do jednej z klas.

4. Entropia osiąga wartość maksymalną przy jednakowym rozkładzie, tj.

gdy klasy są jednakowo prawdopodobne, tej samej wielkości.

5. Im większe zróżnicowanie układy tym mniejsza entropia.

Entropia:

log

)

,...,

(

∑

−

decyzyjne

Ocena informacyjna wa

ci atrybut

1. W zadaniach eksploracji danych, a przede wszystkim w

problemach klasyfikacji istotna jest analiza istotności

atrybutów (

attribute relevance analysis

2. W wyniku tej analiza uzyskujemy uporządkowanie zbioru

atrybutów od najbardziej do najmniej istotnych z punktu

widzenia klasyfikacji obiektów do zadanych klas.

3. Atrybut jest tym bardziej istotny (z punktu widzenia

klasyfikacji obiektów) im mniejsza jest jego entropia.

4. Wyniki analizy istotności atrybutów mają zastosowanie

do charakterystyki opisowej i dyskryminacyjnej klas

obiektów, a także podczas budowy drzew decyzyjnych.

Analiza istotno

ci atrybut

w w zadaniach

klasyfikacji

• S – zbiór obiektów podzielony na m klas C

,...,C

, gdzie s

oznacza liczbę

obiektów w klasie C

, i = 1,...,m, a s liczbę wszystkich obiektów.

•

Niech A będzie atrybutem opisującym obiekty ze zbioru S i niech

, ..., a

) będzie zbiorem wartości atrybutu A.

• Niech

i,k

– liczba obiektów klasy i, dla których atrybut A ma wartość a

Wówczas wartość a

atrybutu A wyznacza układ m klas określony za

pomocą wektora liczebności tych klas:

1,k

,… ,s

m,k

)

• Entropię tego układu nazywamy

entropią wartości a

atrybutu A

log

)

,...,

(

)

(

EntrWartAt

∑

−

gdzie p

i,k

oznacza prawdopodobieństwo przynależności obiektu do klasy

, gdy wartość atrybutu A tego obiektu jest równa a

...

Analiza istotno

ci atrybut

w w zadaniach

klasyfikacji

•

Entropią atrybutu A

nazywamy średnią ważoną entropii wszystkich

wartości tego atrybutu

(

EntrWartAt

)

(

)

(

EntrAtr

∑

gdzie waga entropii wartości a

atrybutu A, w

(A), jest równa

prawdopodobieństwu tego, że wartość atrybutu A dla rozważanego
zbioru obiektów jest równa a

...

)

(

Analiza istotno

ci atrybut

w w zadaniach

klasyfikacji

Za najbardziej istotny uważany jest ten atrybut, którego wartość

entropii

EntrAtr

(

) względem podziału {

,...,

} jest

najmniejsza

Najistotniejszy atrybut maksymalizuje funkcję

zysk informacji

(

information gain

Gain

(

) = E(

, ...,

) –

EntrAtr

(

W analizie istotności atrybutów obliczamy zysk informacji każdego

atrybutu opisującego obiekty w zbiorze treningowym.

Atrybut o największej wartości zysku informacji jest atrybutem

najbardziej dyskryminującym (rozróżniającym).

5. Gain

(

) opisuje różnicę między ilością informacji potrzebnej do

klasyfikacji obiektu ze zbioru S, a klasyfikacją tego obiektu, gdy

wartość atrybutu

ma ustaloną wartość.

6. Gain

(

) określa więc

zysk informacji

przy wyborze atrybutu

. Im jest

on większy, tym mniejsze będzie „zaszumienie” w zbiorach powstałych

w wyniku podziału S względem wartości atrybutu

Budowa drzewa decyzyjnego

–

wyb

r atrybutu

pierwszego poziomu

Zbiór treningowy:

Ocena atrybutu Wiek:

= nie,

= tak

E(5/14, 9/14) = – (5/14*log

(5/14) +

9/14*log

(9/14)) = 0.9403

EntrWartAtr(Wiek,<=30) =
= E(3/5, 2/5) = – (3/5*log

(3/5) + 2/5*log

(2/5)) = 0.9710

EntrWartAtr(Wiek,31..40) = E(0/4, 4/4) = = 0.0
EntrWartAtr(Wiek,>40) = E(2/5, 3/5) = 0.9710

<=30

(Wiek) = 5/14,

31..40

(Wiek) = 4/14,

>40

(Wiek) = 5/14,

EntrAtr(Wiek) =

<=30

(Wiek) * EntrWartAtr (Wiek,<=30) +

+ w

31..40

(Wiek) * EntrWartAtr(Wiek,31..40) +

+ w

>40

(Wiek) * EntrWartAtr(Wiek,>40) = 0,6935

Gain(Wiek) = E(5/14,9/14) – EntrAtr(Wiek) = 0.2467

k =

<=30

31..40

>40

s1k =

3,0000

0,0000

2,0000

s2k =

2,0000

4,0000

3,0000

5,0000

4,0000

5,0000

Budowa drzewa decyzyjnego

–

wyb

r atrybutu

pierwszego poziomu

Zbiór treningowy:

Ocena atrybutu Dochód:

= nie,

= tak

E(5/14, 9/14) = – (5/14*log

(5/14) +

9/14*log

(9/14)) = 0.9403

EntWartAtr(Dochód, niski) = E(1/4,3/4) = 0.8113
EntWartAtr(Dochód, średni) = E(2/6,4/6) = 0.9183
EntWartAtr(Dochód, wysoki) = E(2/4,2/4) = 1.0000

niski

= 4/14,

redni

= 6/14,

wysoki

= 4/14,

EntrAtr(Dochód) =
=

niski

* EntWartAtr(Dochód, niski) +

redni

* EntWartAtr(Dochód, średni) +

wysoki

* EntWartAtr(Dochód, wysoki) = 0.9111

Gain(Dochód) = E(5/14,9/14) – EntrAtr(Dochód) = 0.0292

k =

niski

redni

wysoki

s1k =

1,0000

2,0000

s2k =

3,0000

4,0000

2,0000

4,0000

6,0000

4,0000

decyzyjne

Budowa drzewa decyzyjnego

–

wyb

r atrybutu

pierwszego poziomu

Zbiór treningowy:

Ocena atrybutu Studia:

= nie,

= tak

E(5/14, 9/14) = – (5/14*log

(5/14) +

9/14*log

(9/14)) = 0.9403

EntWartAtr(Studia, tak) = E(1/7,6/7) = 0.5917
EntWartAtr(Studia, nie) = E(4/7,3/7) = 0.9852

tak

= 7/14,

nie

= 7/14,

EntrAtr(Studia) =
=

tak

* EntWartAtr(Studia, tak) +

nie

* EntWartAtr(Studia, nie) = 0.7885

Gain(Studia) = E(5/14,9/14) – EntrAtr(Studia) = 0.1518

k =

tak

nie

s1k =

1,0000

4,0000

s2k =

6,0000

3,0000

7,0000

Budowa drzewa decyzyjnego

–

wyb

r atrybutu

pierwszego poziomu

Zbiór treningowy:

Ocena atrybutu OcenaKred:

= nie,

= tak

E(5/14, 9/14) =
– (5/14*log

(5/14) + 9/14*log

(9/14))

= 0.9403

EntrWartAtr(OcenaKred,dobra) = 0.8113
EntrWartAtr(OcenaKred,znakomita) = 1.0000

dobra

= 8/14,

znakomita

= 6/14,

EntrAtr(OcenaKred) =
=

dobra

* E(2/8, 6/8) +

znakomita

* E(3/6, 3/6) = 0.8922

Gain(Studia) = E(5/14,9/14) – EntrAtr(OcenaKred) = 0.0481

k =

dobra

znakomita

s1k =

2,0000

3,0000

s2k =

6,0000

3,0000

8,0000

6,0000

Analiza istotno

ci atrybut

–

podsumowanie

OcenaKred: Gain(OcenaKred) = 0.0481

k =

dobra

znakomita

s1k =

2,0000

3,0000

s2k =

6,0000

3,0000

8,0000

6,0000

Studia: Gain(Studia) = 0.1518

k =

tak

nie

s1k =

1,0000

4,0000

s2k =

6,0000

3,0000

7,0000

Dochód: Gain(Dochód) = 0.0292

k =

niski

redni

wysoki

s1k =

1,0000

2,0000

s2k =

3,0000

4,0000

2,0000

4,0000

6,0000

4,0000

Wiek: Gain(Wiek) = 0.2467

k =

<=30

31..40

>40

s1k =

3,0000

0,0000

2,0000

s2k =

2,0000

4,0000

3,0000

5,0000

4,0000

5,0000

Analiza istotności atrybutów wykazała, że z punktu widzenia klasyfikacji
związanej z rozważanym zbiorem treningowym, najbardziej istotny jest
atrybut Wiek. Atrybut ten powinien więc być jako pierwszy brany pod uwagę
przy budowie drzewa decyzyjnego.

Wiedza o wartości atrybutu Wiek najbardziej pomaga w procesie klasyfikacji.
Ma on właściwość największego różnicowania obiektów z punktu widzenia
rozważanego zadania klasyfikacji.

Algorytm ID3: Decision_tree

(

Wej

cie:

S – zbiór treningowy obiektów;

– zbiór atrybutów o dyskretnych wartościach opisujących obiekty z

Wyj

cie:

Drzewo decyzyjne.

Kroki:

1. Utwórz wierzchołek N;
2.

wszystkie obiekty z

należą tej samej klasy

C then

return

liść N z etykietą

;

stop

;

if U

jest pusty

then

return

liść etykietowany najczęstszą klasą w

;

stop

;

– atrybut z

o najmniejszej entropii (największym zysku informacji);

wierzchołkowi

przypisz etykietę

;

for each

wartości

atrybutu

begin

a) utwórz krawędź wychodzącą z

dla warunku

b) niech

S’

będzie zbiorem obiektów w zbiorze

, dla których

c) końcem krawędzi jest wierzchołek zwrócony przez

Decision_tree

(

S’

– {

})

end;