Rozhodovací pravidla

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

T7: rozhodovací pravidla

Rozhodovací pravidla Úloha klasifikace příkladů do tříd. pravidlo Ant

C,

kde Ant je konjunkce hodnot atributů a C je cílový atribut

A. Algoritmus pokrývání množin metoda separate and conquer (odděl a panuj) hledáme hypotézy, které pokrývají příklady téže třídy a oddělují je od příkladů třídy jiné. Algoritmus pokrývání množin 1. najdi pravidlo, které pokrývá nějaké pozitivní příklady a žádný negativní, 2. odstraň pokryté příklady z trénovací množiny DTR, 3. pokud v DTR zbývají nějaké nepokryté pozitivní příklady, vrať se k bodu 1, jinak skonči. Rozšíření algoritmu pro více tříd: pro každou třídu C i se data rozdělí na příklady a protipříklady této třídy Rozšíření algoritmu pro práci s daty zatíženými šumem: v kroku 1 nepožadujeme, aby pravidlo pokrývalo příklady pouze jedné třídy P. Berka, 2011

1/22



Základem algoritmu nalezení jednoho pravidla = učení jako prohledávání prostoru pravidel (hypotéz) 2 možnosti pohybu v prostoru hypotéz: zdola nahoru (AQ - Michalski, FindS - Mitchell) shora dolů (CN2 - Clark, Niblett, CN4 - Bruha)

Pokrývání množin zdola nahoru:

1. vezmi jeden pozitivní příklad jako jádro (seed), 2. najdi jeho generalizaci, která pokrývá nějaké pozitivní příklady a žádný negativní.

Pokrývání množin shora dolů:

1. vezmi pravidlo s prázdným předpokladem, 2. najdi jeho specializaci, která pokrývá nějaké pozitivní příklady a žádný negativní.

P. Berka, 2011

2/22



Pokrývání množin zdola nahoru

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ý

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

(Neuspořádaná) pravidla nalezená algoritmem tedy budou: If konto(vysoké) then úvěr(ano) (k1, k2, k4, k5) If příjem(vysoký) then úvěr(ano) (k7, k8, k10) If konto(střední) nezaměstnaný(ne) then úvěr(ano) (k12) Klasifikace: nalezení prvního aplikovatelného pravidla

P. Berka, 2011

3/22



Rozhodovací pravidla „vybírají“ v prostoru atributů (mnoharozměrné) hranoly rovnoběžné s osami souřadné soustavy:

P. Berka, 2011

4/22



Rozhodovací seznam uspořádaný seznam pravidel If – then, Else if – then, Else if – then …

Příklad: Systém CN2 [Clark, Nibblet, 1989], resp. CN4 [Bruha, Kočková, 1994]

Pokrývání množin shora dolů (paralelní heuristické) funkce Search(Ant,DTR) 1. nechť Star je množina obsahující prázdnou kombinaci [ ] 2. nechť Ant je prázdná kombinace 3. nechť Sel je množina všech kategorií A(v) vyskytujících se v DTR 4. dokud Star je prázdné nebo dokud nebyly testovány všechny kategorie A(v) v Sel 4.1. nechť NewStar je prázdné 4.2. pro každou kombinaci Comb Star 4.2.1. proveď specializaci přidáním kategorie A(v) ze Sel 4.2.2. vyhodnoť kvalitu kombinace CombA = Comb A(v) pomocí funkce F(CombA) 4.2.3. zařaď kombinaci CombA do NewStar 4.3. pro každou kombinaci Comb NewStar 4.3.1. pokud Comb je (signifikantně) lepší než Ant, přiřaď Ant

:= Comb

4.4. pokud počet kombinací v NewStar překročí zadaný práh, vyhoď nejhorší kombinaci 4.5. přiřaď Star := NewStar

P. Berka, 2011

5/22



Nejlepší pravidlo (krok 4.2.2) se hledá na základě negativní entropie T F(Ant) =

at at + b

log2

at , at + b

t=1

na základě Laplaceova odhadu očekávané spolehlivosti F(Ant) =

at + 1 , at + b + T

nebo na základě m-odhadu (m-prob) F(Ant) =

at + m ft , at + b + m

kde T je počet tříd, at je počet příkladů třídy t pokrytých pravidlem, at + b je počet všech příkladů pokrytých pravidlem, ft = (at + ct)/n je relativní četnost třídy t a m je parametr.

Ant Ant

C(vt)

Ostatní třídy

at

b

r

ct

d

s

kt

l

n

Ve všech těchto případech vyšší hodnota znamená lepší pravidlo.

P. Berka, 2011

6/22



V případě neuspořádaných pravidel systém hledá pravidla pro jednotlivé třídy odděleně. Algoritmus CN4 – rozhodovací pravidla 1. nechť ListOfRules je prázdný seznam 2. pro každou třídu C(vt), t=1,..,T 2.1. dokud množina pozitivních příkladů této třídy DTRt není prázdná 2.1.1. pomocí funkce Search(Ant,DTRt) nalezni nejlepší kombinaci Ant 2.1.2. přiřaď DTRt := DTRt – DTRt(Ant), kde DTRt(Ant) jsou příklady pokryté kombinací Ant 2.1.3. do ListOfRules přidej pravidlo IF Ant THEN C(vt)

V případě uspořádaných pravidel (rozhodovacího seznamu) se hledají pravidla ke všem třídám najednou Algoritmus CN4 – rozhodovací seznam 1. nechť ListOfRules je prázdný seznam 2. dokud trénovací množina DTR není prázdná 2.1. pomocí funkce Search(Ant,DTR) nalezni nejlepší kombinaci Ant 2.2. přiřaď DTR := DTR – DTR(Ant), kde DTR(Ant) jsou příklady pokryté kombinací Ant 2.3. do ListOfRules přidej pravidlo IF Ant THEN C, kde C je majoritní třída příkladů v DTR(Ant)

P. Berka, 2011

7/22



if příjem=vysoký then class is ano; Kr=[ 5 0]; signif=5.850; quality=0.925; cost=1 if konto=vysoké then class is ano; Kr=[ 4 0]; signif=4.680; quality=0.900; cost=1 if příjem=nízký && konto=nízké then class is ne; Kr=[ 0 2]; signif=6.340; quality=0.900; cost=2 if konto=střední && nezaměstnaný=ano then class is ne; Kr=[ 0 2]; signif=6.340; quality=0.900; cost=2 if konto=střední && nezaměstnaný=ne then class is ano; Kr=[ 2 0]; signif=2.340; quality=0.850; cost=2 if true then class is ano; Kr=[ 8 4]; signif=0.000; quality=0.733; cost=0 (neuspořádaná) Rozhodovací pravidla

if příjem=vysoký then class is ano; Kr=[ 5 0]; signif=5.850; quality=0.925; cost=1 else if konto=vysoké then class is ano; Kr=[ 2 0]; signif=2.340; quality=0.850; cost=1 else if nezaměstnaný=ano then class is ne; Kr=[ 0 3]; signif=9.510; quality=0.950; cost=1 else if konto=střední then class is ano; Kr=[ 1 0]; signif=1.170; quality=0.825; cost=0 else if true then class is ne; Kr=[ 0 1]; signif=3.170; quality=0.850; cost=0 (uspořádaný) Rozhodovací seznam

P. Berka, 2011

8/22



Implementované algoritmy (weka) PART – pokrývání množin založené na částečných

rozhodovacích stromech, z dat se vytvoří prořezaný strom a pro list s největším pokrytím se vytvoří jedno pravidlo (Frank, Witten, 1998)

Prism – pokrývání množin shora dolů, hledají se pravidla s přesností rovnou 1 (Cendrowska, 1987)

P. Berka, 2011

9/22



JRip (RIPPER) – pokrývání množin shora dolů po

kterém následuje prořezávání pravidel (Cohen, 1995)

Ridor – pokrývání množin shora dolů, hledají se if-true

a if-false pravidla, která nemusí mít spolehlivost rovnou 1 (Gaines, Compton, 1995)

P. Berka, 2011

10/22



B. Pravděpodobnostní pravidla Pravidla doplněná neurčitostí

ITRule (Goodman, Smyth, 1989) pravidla

Ant

C (p),

kde Ant je předpoklad (konjunkce hodnot atributů), C je závěr (hodnota atributu), p je podmíněná pravděpodobnost cíle, nastane-li a předpoklad, tedy hodnota počítaná ze čtyřpolní a+b tabulky.

P. Berka, 2011

11/22



ESOD (Ivánek, Stejskal, 1988) pravidla

Ant

C (w),

kde Ant je kombinace (konjunkce) hodnot atributů C je atribut, nebo konjunkce hodnot atributů, která nese informaci o zařazení objektu do třídy, w z intervalu [0,1] je váha vyjadřující neurčitost pravidla.

platnost pravidla P(C|Ant) = a/(a+b) (ze čtyřpolní tabulky)

Inferenční mechanismus Přímé řetězení pravidel za použití pseudobayesovské kombinační funkce

x

y

x*y

x*y (1 x ) * (1

y)

Získávání znalostí zpřesňování a zjemňování již existujících znalostí (knowledge refinement) postupem shora dolů (počínaje prázdným vztahem). vložit pravidlo s platností, kterou nelze odvodit z báze znalostí,

P. Berka, 2011

12/22



např. 7a11a ==> 1+

C

non C

Ant

11

14

non Ant

c

d

11a 7a

==> 1+ (0.6800) ==> 1+ (0.2720) ==> 1+ (0.3052)

čtyřpolní tabulka

pravidla

11 platnost = = 0.44 11+14

naskládaná váha = 0.2586

platnost a naskládaná váha se od sebe liší (dle

2

testu)

7a11a ==> 1+ je pravidlo s vahou w takovou, že w 0.2586 0.44 , tedy w = 0.6926.

w

u 1 u

u ,

P (C | Ant ) 1 P (C | Ant ) cw(C , Ant ) 1 cw(C , Ant )

První verze algoritmu ([Ivánek, Stejskal, 1988]) předpokládala: pouze kategoriální data, zařazení objektů do dvou tříd (příklady a protipříklady). P. Berka, 2011

13/22



Algoritmus ESOD Inicializace 1. vytvoř CAT - seznam kategorií A(v) uspořádaný sestupně dle četnosti 2. vytvoř OPEN - seznam implikací A(v) C uspořádaný sestupně dle četnosti levé strany implikace 3. přiřaď do KB prázdné pravidlo C (w), kde w je relativní četnost třídy C v datech Hlavní cyklus 1. Dokud OPEN není prázdný seznam 1.1. vezmi první implikaci ze seznamu OPEN (označ ji Ant C) 1.2. spočítej platnost této implikace P(C|Ant) 1.3. pokud P(C|Ant) Pmin P(C|Ant) (1 - Pmin) potom 1.3.1.spočítej pomocí kombinační funkce váhu cw(C,Ant) naskládanou z vah pravidel v bázi KB aplikovatelných na Ant 1.3.2.pokud se platnost implikace P(C|Ant) signifikantně liší (na základě 2 testu) od naskládané váhy cw(C,Ant) potom 1.3.2.1. přidej do KB pravidlo Ant C (w), kde w cw(C,Ant) = P(C|Ant) 1.4. pokud délka(A) dmax 1.4.1. pro každé A(v) ze seznamu CAT takové, že A(v) je v CAT před všemi hodnotami atributů z COMB (Tedy platí, že četnost A(v) je větší nebo rovna četnosti COMB) 1.4.2.pokud se atribut A nevyskytuje v COMB potom 1.4.2.1. generuj novou kombinaci COMB A(v) 1.4.2.2. přidej COMB A(v) do seznamu OPEN za poslední kombinaci C takovou, že četnost(C) četnost(COMB A(v)) 1.5. odstraň COMB ze seznamu OPEN

P. Berka, 2011

14/22



Modifikace pro více tříd Váha = 0.5 odpovídá platnosti 1/R kde R je počet tříd

modifikace algoritmu: váha prázdného vztahu je relativní četnosti převedené na váhu (krok 3 inicializace), 2

testu vstupuje platnost implikace a naskládaná váha převedená na platnost (krok 1.3.2 hlavního cyklu), do

váha pravidla se spočítá ze vztahu w cw(C,Ant) = P’(C|Ant), kde P’(C|Ant) je platnost převedená na váhu (krok 1.3.2.1 hlavního cyklu).

P. Berka, 2011

15/22



Implementace algoritmu KEX v systému LISp-Miner

Uvedená pravidla odpovídají zadání dmax = 4, fmin = 1 a Pmin = 0.9.

Strategie volby parametrů: plná analýza (dmax = počet všech atributů, které se nevyskytují v cíli, fmin = 1, Pmin = 0), minimální analýza (dmax = 1, fmin = 1, Pmin = 0), analýza "bez šumu" (Pmin = 100); toto zadání znamená, že se do báze zařadí pouze 100% vztahy.

P. Berka, 2011

16/22



Práh pro provedení klasifikace: je-li výsledná váha > , pak příklad patří do třídy je-li výsledná váha < 1- , pak příklad nepatří do třídy je-li výsledná váha [1- , ], pak nelze rozhodnout

Prediction performance of the KEX system

# of classified cases by the KEX system 250

97

200 # classified cases

prediction accuracy (%)

99

95 93 91 89

150

100

50 87 85

0 0.4

0.6

0.8

1

0.4

alpha

0.6

0.8

1

alpha

Rozdíl oproti algoritmům pokrývání množin: 1. je potřeba dostatečný počet příkladů, 2. pro jeden příklad lze nalézt více použitelných pravidel, 3. v bázi pravidel se může objevit pravidlo i jeho specializace, 4. při konzultaci může systém pro jeden příklad doporučit více

cílů. P. Berka, 2011

17/22



Numerické atributy Příklad CN4 (On-line diskretizace v průběhu učení) Algoritmus SetBounds(a) 1. nechť PoleMezí je prázdné 2. pro každou hodnotu vj atributu a 2.1. spočítej pro každou třídu Cr (r=1,..,R) četnosti Dlevár, (Dpravár) hodnot v takových, že v vj (v vj) 2.2. spočítej hodnotu funkce Hlevá(vj) pro případ, že vj je potenciální horní mez, tedy že a vj bude selektor 2.3. spočítej hodnotu funkce Hpravá(vj) pro případ, že vj je potenciální dolní mez, tedy že a vj bude selektor 3. pro každou hodnotu vj atributu a 3.1. pokud Hlevá(vj) je nerostoucí lokální maximum, tedy Hlevá(vj-1) Hlevá(vj) Hlevá(vj+1) přidej selektor a vj do PoleMezí v pořadí podle hodnoty Hlevá(vj) 3.2. pokud Hpravá(vj) je neklesající lokální maximum, tedy Hpravá(vj-1) Hpravá(vj) Hpravá(vj+1) přidej selektor a vj do PoleMezí v pořadí podle hodnoty Hpravá(vj) 4. pro každou dvojci hodnot v1 , v2 PoleMezí 4.1. spočítej pro každou třídu Cr četnost Dr hodnot v takových, že v1 v v2 4.2. spočítej hodnotu funkce H(v1,v2) pro četnosti Dr 4.3. přidej selektor v a v2 do PoleMezí v pořadí podle hodnoty H(v1,v2)

P. Berka, 2011

18/22



Příklad: 7 pozitivních příkladů (s hodnotami 45, 46, 50, 50, 100, 100, 120), 5 negativních příkladů (s hodnotami 51, 51, 51, 99, 99).

entropie 0

horni meze

dolni meze

ww <= 50

ww > 99

ww > 50 -0.95 --0.99 --1 45

| 46

| 50

| 51

| 99

| 100

| 120

ww

Lokální maxima entropie pro diskretizaci

50<ww<=99;

entropy=0.000; maxfreq=5

ww<=50;


ww>99;


45<ww<=50;


ww>50;

entropy=-0.954; maxfreq=5

45<ww<=99;


ww>45;


P. Berka, 2011

19/22



Numerické třídy Příklad CN4 pravidla

Ant

avgA(C), MvarA(C)

kde Ant je předpoklad (konjunkce hodnot atributů), avgA(C) je průměrná hodnota cílového atributu, MvarA(C) je rozptyl tohoto průměru

P. Berka, 2011

20/22



Chybějící hodnoty Příklad CN4 1) ignoruje příklad s nějakou chybějící hodnotou, 2) nahradí chybějící hodnotu novou hodnotou „nevím“, 3) nahradí chybějící hodnotu některou z existujících hodnot atributu a sice: a) nejčetnější hodnotou, b) proporcionálním podílem všech hodnot, c) libovolnou hodnotou.

P. Berka, 2011

21/22



Hierarchie hodnot atributů příklad pro algoritmus ESOD (Svátek 1996) Hierarchie vstupních atributů any

vlastní

vlastní dům

družstevní

nájemní

Nájemní byt státní

vlastní byt

Nájemní byt s majitelem

Hierarchie tříd any

nestanovena

stanovena

imunní

neinfikován

P. Berka, 2011

neimunní

infikován

22/22

Rozhodovací pravidla

Recommend Documents