Rozhodovací stromy. Úloha klasifikace objektů do tříd. Top down induction of decision trees (TDIDT) - metoda divide and conquer (rozděl a panuj)

Dobývání znalostí z databází

T5: rozhodovací stromy

Rozhodovací stromy Úloha klasifikace objektů do tříd. Top down induction of decision trees (TDIDT) metoda divide and conquer (rozděl a panuj) metoda specializace v prostoru hypotéz – stromů (postup shora dolů, počínaje prázdným stromem). Cílem je nalézt nějaký strom konsistentní s trénovacími daty. Přitom se dává přednost menším stromům (Occamova břitva).

TDIDT algoritmus 1. vezmi jeden atribut jako kořen dílčího stromu, 2. rozděl data na podmnožiny podle hodnot tohoto atributu, 3. nepatří-li všechna data v podmnožině do téže třídy, pro tuto podmnožinu opakuj postup od bodu 1. Obecný algoritmus pro tvorbu rozhodovacích stromů

Omezení obecného algoritmu: jen kategoriální atributy jen data bez šumu P. Berka, 2011

1/18



Volba atributu (krok 1 algoritmu) Entropie c H=-

(pi * log2 pi) , i=1

entropie

Y1

Y2

……….

YS

X1

a11

a12

……….

a1S

r1

X2

a21

a22

……….

a2S

r2

:

:

:

:

:

:

:

:

:

:

XR

aR1

aR2

……….

aRS

rR

s1

s2

……….

sS

n

H ( A)

R i 1

ri n

S

aij

j 1

ri

log 2

aij ri

Hledáme atribut s minimální hodnotou kritéria P. Berka, 2011

2/18



příklad: klient k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12

příjem vysoký vysoký nízký nízký nízký nízký vysoký vysoký nízký vysoký nízký nízký

H(příjem) =

konto vysoké vysoké nízké vysoké vysoké nízké nízké nízké střední střední střední střední

pohlaví žena muž muž žena muž žena muž žena muž žena žena muž

nezaměstnaný ne ne ne ano ano ano ne ano ano ne ano ne

úvěr ano ano ne ano ano ne ano ano ne ano ne ano

n(příjem(vysoký)) H(příjem(vysoký)) + n n(příjem(nízký)) H(příjem(nízký)) n

P. Berka, 2011

3/18


H(příjem) =


5 7 H(příjem(vysoký)) + H(příjem(nízký)) 12 12

5 5 0 0 H(příjem(vysoký)) = - log2 - log2 = 0 + 0 = 0 5 5 5 5 3 3 4 4 H(příjem(nízký)) = - log2 - log2 = 0.9852 7 7 7 7 H(příjem) = 0.5747 H(konto) = 4/12*H(konto(vysoké)) + 4/12*H(konto(střední)) + 4/12*H(konto(nízké)) = 1/3 * 0 + 1/3 * 1 + 1/3 * 1 = 0.6667 H(pohlaví) = 6/12*H(pohlaví(muž)) + 6/12*H(pohlaví(žena)) = 1/2 * 0.9183 + 1/2 * 0.9183 = 0.9183 H(nezaměstnaný) = 6/12*H(nezaměstnaný(ano)) + 6/12*H(nezaměstnaný(ne)) = 1/2 * 1 + 1/2 * 0.6500 = 0.8250

P. Berka, 2011

4/18



H(konto) = 2/7 H(konto(vysoké)) + 3/7 H(konto(střední)) + 2/7 H(konto(nízké)) = 2/7 0 + 3/7 0.9183 + 2/7 0 = 0.3935 H(pohlaví) = 4/7 H(pohlaví(muž)) + 3/7 H(pohlaví(žena)) = 4/7 1 + 3/7 0.9183 = 0.9650 H(nezaměstnaný) = 5/7 H(nezaměstnaný(ano)) + 2/7 H(nezaměstnaný(ne)) = 5/7 0.9709 + 2/7 1 = 0.9792

H(pohlaví) = 2/3 H(pohlaví(muž)) + 1/3 H(pohlaví(žena)) = 2/3 1 + 1/3 0 = 0.6667 H(nezaměstnaný) = 2/3 H(nezaměstnaný(ano)) + 1/3 H(nezaměstnaný(ne)) = 2/3 0 + 1/3 0 = 0

Pozn: V případě kategoriálních atributů se každý atribut může pro větvení stromu vybrat nejvýše jednou.

P. Berka, 2011

5/18



Tedy, tvorba rozhodovacích stromů je založena na prohledávání prostoru stromů: Shora dolů Heuristické Jednoduché

P. Berka, 2011

6/18



Gini index c

Gini = 1 -

(pi 2)

i=1

Gini( A)

R i 1

ri 1 n

S

aij

j 1

ri

2

Hledáme atribut s minimální hodnotou kritéria

Chí kvadrát 2

( A)

R

S

i 1 j 1

aij

ri s j

2

n ri s j n

Hledáme atribut s maximální hodnotou kritéria

Informační zisk Zisk(D,A) = H(D) - H(A) Hledáme atribut s maximální hodnotou kritéria Zisk(D,A) Poměrný informační zisk(D,A) = Větvení(D,A)

P. Berka, 2011

7/18



Převod stromů na pravidla

If příjem(vysoký) then úvěr(ano) If příjem(nízký) konto(vysoké) then úvěr(ano) If příjem(nízký) konto(střední) nezaměstnaný(ano) then úvěr(ne) If příjem(nízký) konto(střední) nezaměstnaný(ne) then úvěr(ano) If příjem(nízký) konto(nízké) then úvěr(ne)

P. Berka, 2011

8/18



Prořezávání stromů Důvody: Bezchybná klasifikace trénovacích dat nezaručuje kvalitní klasifikaci dat testovacích (overfitting) Úplný strom může být příliš veliký

Redukce stromu, aby v listovém uzlu „převažovaly“ příklady jedné třídy. pre-pruning – modifikuje se zastavovací kritérium (krok 3 algoritmu) = větvit se nebude pokud počet příkladů v uzlu klesne pod danou hodnotu nebo pokud relativní počet příkladů jedné třídy překročí danou hodnotu post-pruning – vytvoří se úplný strom, který se následně redukuje Algoritmus post-pruning 1. Převeď strom na pravidla, 2. Generalizuj pravidlo odstraněním podmínky z předpokladu, pokud dojde ke zlepšení odhadované přesnosti, 3. Uspořádej prořezaná pravidla podle odhadované přesnosti; v tomto pořadí budou pravidla použita pro klasifikaci

P. Berka, 2011

9/18



Práce s numerickými atributy Algoritmus pracuje s kategoriálními atributy, numerické je třeba diskretizovat: 1. off-line v rámci přípravy a předzpracování dat 2. on-line v rámci běhu modifikovaného algoritmu binarizace na základě entropie Algoritmus 1. Seřaď vzestupně hodnoty diskretizovaného atributu A, 2. Pro každou možnou hodnotu dělícího bodu spočítej entropii H(A ) 3. Vyber dělící bod hodnotu H(A )

, který dá nejmenší

n(A(< )) n(A(> )) H(A ) = H(A(< )) + H(A(> )) n n

P. Berka, 2011

10/18



Příklad: Klient K101 K102 K103 K104 K105 K106 K107 K108 K109 K110 K111 K112

příjem 3000 10000 17000 5000 15000 20000 2000 5000 10000 20000 10000 17000

Konto 15000 15000 15000 30000 30000 50000 60000 90000 90000 90000 100000 100000

úvěr ne ne ano ne ano ano ne ano ano ano ano ano

H(konto22500) = 3/12 H(konto(<22500)) + 9/12 H(konto(>22500)) = 1/4

0.9183 + 3/4

0.5640 = 0.6526


0.9706 + 7/12

0.5917 = 0.7497


1 + 1/2

0.6500 = 0.8250


P. Berka, 2011

0.9852 + 5/2

0 = 0.5747

11/18



na rozdíl od kategoriálních atributů se mohou v jedné větvi numerické atributy opakovat

0.6

1.5

1.7

petalwidth

P. Berka, 2011

12/18



Regresní stromy Úloha odhadu hodnoty nějakého numerického atributu.

Volba atributu (krok 1): kritérium redukce směrodatné odchylky n(A(v)) S(A(v)) n v Val(A)

kde S(A(v)) = (

n

(yi - y')2 ) / (n-1)

i=1

P. Berka, 2011

a

1 n y' = yi n i=1

13/18



Implementované algoritmy ID3 (Quinlan, 1986): základní algoritmus, entropie

C4.5 (Quinlan, 1993): informační zisk, postpruning, on-line diskretizace

P. Berka, 2011

14/18



CART (Breiman a kol., 1984): Gini index, jen binární stromy (atributy se mohou opakovat)

P. Berka, 2011

15/18



CHAID (Biggs a kol., 1991): Chi kvadrát, seskupování hodnot kategoriálních atributů 1R, Decision stump (Holte, 1993): strom obsahuje pouze kořenové větvení

Random Tree (Breiman, 2001): pro každý větvící uzel se náhodně vybere množina atributů ze kterých se pak dle Gini indexu vybere ten nejlepší

Random Forest (Breiman, 2001): soubor náhodných stromů, náhodně se pro každý strom vybere podmnožina trénovacích dat (kombinování modelů – viz téma vyhodnocení výsledků)

P. Berka, 2011

16/18



ETree (Berka, 2010): Chi kvadrát, jen kategoriální atributy, pre-pruning, volba k nejlepších atributů pro každý větvící uzel - výsledkem je více stromů, pro klasifikaci lze vybrat jen jeden nebo všechny - implementováno v systémech LISp-Miner a Ferda

Implementace v systému Ferda

P. Berka, 2011

17/18



Použití rozhodovacích stromů příklady jsou reprezentovány hodnotami atributů, úkolem je klasifikovat příklady do konečného (malého) počtu tříd, hledaný popis konceptů může být tvořen disjunkcemi, trénovací data mohou být zatížena šumem, trénovací data mohou obsahovat chybějící hodnoty.

Rozhodovací stromy dělí prostor atributů na (mnoharozměrné) hranoly rovnoběžné s osami souřadné soustavy:

P. Berka, 2011

18/18

Rozhodovací stromy. Úloha klasifikace objektů do tříd. Top down induction of decision trees (TDIDT) - metoda divide and conquer (rozděl a panuj)

Recommend Documents