5.3
Rozhodovací pravidla
Zatímco asociační pravidla hledala zajímavé souvislosti mezi hodnotami různých atributů a jejich kombinací, rozhodovací pravidla se používají stejně jako rozhodovací stromy; pro klasifikaci. Syntaxe pravidla je tedy IF Ant THEN Class kde Ant (předpoklad) je kombinace vytvořená z kategorií vstupních atributů a Class je zařazení příkladu do třídy, tedy nějaká kategorie C(vt) cílového atributu C. Budeme se tedy opět zabývat algoritmy učení s učitelem, kde cílem je naučit se zařazovat příklady do různých tříd. Jeden algoritmus pro tvorbu rozhodovacích pravidel už známe, vytvoření pravidel z rozhodovacího stromu. Jiné možnosti vytváření pravidel si ukážeme v této kapitole.
5.3.1
Pokrývání množin
Podobné jméno, jako má Ross Quinlan v souvislosti s rozhodovacímí stromy, má Ryzsard Michalski v souvislosti s rozhodovacími pravidly, přesněji s algoritmem pokrývání množin (set covering algorithm), známým jako AQ [Michalski, 1969] 1. Zatímco TDIDT algoritmus pro tvorbu rozhodovacích stromů bývá nazýván algoritmus rozděl a panuj (divide and conquer), algoritmus pokrývání množin bývá nazýván odděl a panuj (separate and conquer). Při pokrývání množin jde totiž o to nalézt pravidla (konzistentní hypotézy), které pokrývají2 nějaké příklady hledaného konceptu a tyto příklady oddělit od jiných příkladů téhož konceptu i od příkladů třídy jiné. V prostoru atributů se tedy postupně vybírají oblasti, které obsahují příklady pouze jedné třídy. Nalezené oblasti mají, podobně jako v případě rozhodovacích stromů, podobu mnohorozměrných hranolů rovnoběžných s osami. Rozhodovací pravidla tedy mají stejnou vyjadřovací sílu jako rozhodovací stromy (Obr. 1).
Obr. 1 Vyjadřovací síla rozhodovacích pravidel
1
Postupně vznikla celá řada těchto algoritmů rozlišovaných číslem, tedy např. AQ15. Michalski je rovněž autorem myšlenky paprskového prohledávání za využití konceptu hvězda (star), které používá např. CN2 a CN4.
2
Pravidlo pokrývá příklad, pokud příklad vyhovuje předpokladu pravidla.
1
Základní podobu algoritmu pokrývání množin pro dvě třídy ukazuje Obr. 2. Uvedený algoritmus bude opět fungovat pouze pro kategoriální data (příklady popisujeme jako kombinaci hodnot atributů), která nejsou zatížena šumem ( hledáme pravidla pokrývající příklady pouze jedné třídy).
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. Obr. 2 Algoritmus pokrývání množin
Rozšíření algoritmu pro více tříd se obvykle3 provede tak, že pro každou třídu C(vt) se data rozdělí na příklady této třídy
{C(+)} = {o i : y i = v t } = D +TR a protipříklady této třídy
{C(-)} = {o i : y i ≠ v t } = D -TR . Rozšíření algoritmu pro práci s daty zatíženými šumem spočívá v tom, že v kroku 1 nepožadujeme, aby pravidlo pokrývalo příklady pouze jedné třídy4. Numerické atributy je opět třeba diskretizovat („uvnitř“ algoritmu pro tvorbu pravidel nebo ve fázi přípravy dat).
Klíčovým bodem algoritmu pokrývání množin je krok 1; nalezení jednoho pravidla. Zatímco algoritmus TDIDT postupoval v prostoru hypotéz „shora dolů“, při pokrývání množin najdeme obě varianty postupu: „zdola nahoru“5 (tedy metodu generalizace – odstraňování kategorie z kombinace) i „shora dolů“6 (metodou specializace – přidávání kategorie do kombinace).
Uveďme nejprve postup zdola nahoru, který odpovídá algoritmům AQ. Počáteční hypotéza pokrývající jeden pozitivní příklad, se postupně zobecňuje tak, aby pokrývala více pozitivních příkladů a žádný negativní příklad7. Krok 1 z algoritmu na Obr. 2 bude tedy mít podobu: 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í.
3
Jinou možností je vytvářet pravidla ke všem třídám současně. Tak postupuje algoritmus CN2/CN4 v modifikaci pro tvorbu rozhodovacích seznamů a algoritmus ESOD, které jsou popsány v dalších částech této kapitoly.
4
Připomeňme, že v případě rozhodovacích stromů byl tento problém řešen analogickým způsobem a sice tak, že jsme nepožadovali aby v listovém uzlu stromu byly příklady pouze jedné třídy.
5
Tento postup bývá rovněž nazýván postup řízený daty (data driven).
6
7
Tento postup bývá rovněž nazýván postup generování a testování (generate and test). Generování zde znamená prohledávání prostoru možných pravidel. Tento postup jsme již viděli u algoritmu FindS, který je popsán v kapitole o strojovém učení.
2
Vezměme si k ruce opět naše známá data (Obr. 3). Budeme-li při volbě příkladů v kroku 1 postupovat sekvenčně8, bude hledání pravidel vypadat takto: V prvním kroku vybereme příklad k1 popsaný kombinací příjem(vysoký) ∧ konto(vysoké) ∧ pohlaví(žena) ∧ nezaměstnaný(ne). Tuto kombinaci postupně zobecňujeme v sekvenci (v závorce jsou uvedeny pokryté příklady): příjem(vysoký) ∧ konto(vysoké) ∧ pohlaví(žena) ∧ nezaměstnaný(ne) (k1) příjem(vysoký) ∧ konto(vysoké) ∧
nezaměstnaný(ne) (k1, k2)
konto(vysoké)
(k1, k2, k4, k5).
Výsledná kombinace konto(vysoké) pokrývá pozitivní příklady k1, k2, k4 a k5 třídy úvěr(ano). Tyto příklady odstraníme z trénovací množiny a pokračujeme příkladem k7 pokrytým kombinací příjem(vysoký) ∧ konto(nízké) ∧ pohlaví(muž) ∧ nezaměstnaný(ne). Tuto kombinaci postupně zobecníme 9 na kombinaci příjem(vysoký), která pokrývá příklady k7, k8 a k10.
Zbývá příklad k12 popsaný kombinací příjem(nízký) ∧ konto(střední) ∧ pohlaví(muž) ∧ nezaměstnaný(ne). Jedná se o poslední pozitivní příklad v trénovacích datech. Při zobecňování tohoto příkladu nám pomohou negativní příklady; nalezená kombinace nesmí pokrývat žádný z nich. Tento požadavek splňuje kombinace konto(střední) ∧ nezaměstnaný(ne).
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
Obr. 3 Data pro tvorbu rozhodovacích pravidel 8
Při výběru jak jádra, tak příkladů pokrytých generalizací jádra bude hrát roli pořadí příkladů v trénovacích datech. Volba příkladu tedy může ovlivnit výslednou podobu pravidel.
9
Budeme-li procházet klienty postupně, pak zobecňujeme v sekvenci příjem(vysoký) ∧ konto(nízké) ∧ pohlaví(muž) ∧ nezaměstnaný(ne) (k7) → příjem(vysoký) ∧ konto(nízké) (k7, k8) → příjem(vysoký) (k7, k8, k10).
3
Pravidla nalezená algoritmem tedy budou10: IF konto(vysoké)
THEN úvěr(ano)
IF příjem(vysoký)
THEN úvěr(ano)
IF konto(střední) ∧ nezaměstnaný(ne)
THEN úvěr(ano).
Použití rozhodovacích pravidel pro klasifikaci nových příkladů je velice prosté. Postupně procházíme soubor pravidel až nalezneme pravidlo, které lze použít. Závěr pravidla pak určí třídu, do které máme uvažovaný příklad zařadit.
V následující podkapitole si ukážeme postup vytváření pravidel metodou specializace – tedy přidáváním kategorií do kombinace tvořící předpoklad pravidla. Pro generování předpokladů pravidel můžeme použít různé metody prohledávání prostoru kombinací. Nejpoužívanějšími způsoby pro nalezení jednoho pravidla (v souvislosti s algoritmem pokrývání množin) je gradientní prohledávání a svazkové prohledávání. V prvním případě se jedná o prohledávání do hloubky bez navracení: v každém kroku se vybere ta „nejlepší“ kategorie která specializuje předpoklad pravidla (kritéria kvality pravidel rovněž uvidíme v následujíci podkapitole). Ve druhém případě se paralelně sleduje předem daný počet nejvhodnějších „kandidátů“ na to býti předpokladem pravidla: v každém kroku se pak přidá nejlepší kategorie ke každému potenciálnímu předpokladu a výsledná množina (starých a nových kandidátů) se opět redukuje na požadovaný počet těch nejlepších.
5.3.2
Rozhodovací seznam
Soubor IF-THEN pravidel, tak jak jsme ho poznali v předcházející podkapitole, bývá někdy nazýván „neuspořádaný“ soubor pravidel. Opakem je „uspořádaný“ soubor pravidel, neboli rozhodovací seznam (decision list). V tomto druhém případě se jedná o strukturu typu IF Ant1 THEN Classi, ELSE IF Ant2 THEN Classj ELSE IF Ant3 THEN Classk . . ., kde v závěrech THEN se mohou objevovat různé třídy. Uspořádání zde spočívá v tom, že v každé podmínce ELSE IF se implicitně skrývá negace všech podmínek předcházejících pravidel. Nelze tedy již pravidla chápat jako navzájem nezávislá.
Příkladem systému, který vytváří jak rozhodovací pravidla (čti neuspořádaný soubor pravidel), tak rozhodovací seznamy (čti uspořádaný soubor pravidel) je CN2 [Clark, Nibblet, 1989], resp. jeho rozšíření CN4 [Bruha, Kočková, 1994] 11. Opět se jedná o algoritmus pokrývání množin (pokryté příklady se odstraňují z trénovacích dat), postupuje se ale metodou specializace, tedy „shora dolů“. Jádrem algoritmu (který odpovídá kroku 1 v obecném schématu algoritmu pokrývání množin) je funkce Search(Ant,DTR) hledající jedno pravidlo. Podoba této funkce je uvedena na Obr. 4. Algoritmus 10
Můžeme pozorovat značnou shodu s pravidly, vytvořenými z rozhodovacího stromu v jedné z předcházejících kapitol.
11
Tato verze nabízí řadu zlepšení ve srovnání s původním algoritmem: ošetření chybějících hodnot, cena vyhodnocování atributu, práce s numerickými atributy.
4
hledá pravidlo, které pokrývá velký počet objektů třídy Class a malý počet objektů ostatních tříd. Tvorba pravidel končí když už se nepodaří nalézt vyhovující pravidlo. Specializace pravidla se provádí přidáním kategorie ke kombinaci tvořící předpoklad pravidla12. Potenciální předpoklady se uchovávají v množině Star. Velikost této množiny určuje šířku paprsku pro paprskové prohledávání. Nejlepší pravidlo (krok 4.2.2 algoritmu) se hledá na základě negativní entropie T
F(Ant) =
∑
nt(Ant) nt(Ant) n(Ant) × log2 n(Ant) ,
t=1
na základě Laplaceova odhadu očekávané spolehlivosti pravidla 13 nt(Ant) + 1 F(Ant) = n(Ant) + T , nebo na základě m-odhadu (m-prob) nt(Ant) + m∗ft F(Ant) = n(Ant) + m , kde T je počet tříd, nt(Ant) je počet příkladů třídy t pokrytých pravidlem, n(Ant) je počet všech příkladů pokrytých pravidlem, ft = nt/n je relativní četnost třídy t a m je parametr. Ve všech těchto případech vyšší hodnota znamená lepší pravidlo.
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 Obr. 4 Funkce “najdi jedno pravidlo” v algoritmu CN4
Hlavní cyklus algoritmu se liší podle toho, jestli vytváříme uspořádaná nebo neuspořádaná pravidla. V případě neuspořádaných pravidel systém hledá pravidla pro jednotlivé třídy odděleně. Pro každou třídu se projde celá trénovací množina DTR s tím, že pozitivní příklady tvoří vždy příklady jedné třídy 12
V původním algoritmu se používá termín selektor (selector) pro kategorii a termín komplex (complex) pro kombinaci.
13
Oproti běžně používané spolehlivosti (platnosti) pravidla bere Laplaceova korekce do úvahy počet tříd T.
5
a negativní příklady tvoří příklady ostatních tříd (podobu hlavního cyklu algoritmu ukazuje Obr. 5). Tak se může stát, že se k jednomu příkladu naleznou pravidla, která by jej řadila k různým třídám. Tento spor lze řešit hlasování aplikovatelných pravidel. 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) Obr. 5 Hlavní cyklus algoritmu CN4 pro neuspořádaná pravidla
V případě uspořádaných pravidel (rozhodovacího seznamu) se hledají pravidla ke všem třídám najednou. DTR tedy odpovídá trénovací množině v nezměněně podobě. Třída predikovaná každým pravidlem odpovídá třídě, do které patří většina pokrytých příkladů. Při klasifikaci ke sporům nemůže dojít, protože pravidla mají přidělena pořadí použití.
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 Class, kde Class je majoritní třída příkladů v DTR(Ant) Obr. 6 Hlavní cyklus algoritmu CN4 pro uspořádaná pravidla
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 Obr. 7 CN4, neuspořádaná pravidla
6
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 Obr. 8 CN4, uspořádaná pravidla
Pro data z Obr. 3 vytvoří CN4 soubor neuspořádaných pravidel uvedený na Obr. 7 a soubor uspořádaných pravidel uvedený na Obr. 8 (jde o autentické výstupy z programu). Na těchto výstupech si můžeme všimnout, že pro naše data odpovídají neuspořádaná pravidla pravidlům vytvořeným „simulací“ algoritmu AQ (viz předcházející podkapitola) a uspořádaná pravidla odpovídají pravidlům vytvořeným z rozhodovacího stromu (viz příslušná kapitola). Numerické charakteristiky každého pravidla jsou: •
Kr: pro jednotlivé třídy počet příkladů pokrytých pravidlem, tedy četnosti nt(Ant),
•
signif: kritérium pro výběr předpokladu pravidla: T
signif =
∑ n (Ant) × t
t=1
⎛ n (Ant) n ⎞ log 2 ⎜ t ⎟, ⎝ n(Ant) n t ⎠
kde T je počet tříd, nt je počet příkladů třídy t a n je počet všech příkladů (v trénovacích datech), •
quality: hodnocení založené na počtu příkladů (majoritní) třídy pokrytých a nepokrytých daným pravidlem: ntm(Ant) ntm(Ant) quality = 0.8 n(Ant) + 0.2 ntm , kde tm je majoritní třída,
•
cost: cena vyhodnocení pravidla, standardně počet dotazů v předpokladu.
Poslední pravidlo (to s předpokladem true) je implicitní pravidlo, které odpovídá majoritní třídě v trénovacích datech. Toto pravidlo se při klasifikaci uplatní, pokud selhala všechna ostatní.
7
5.3.3
Pravděpodobnostní pravidla
Doposud uvedené příklady algoritmů hledaly pravidla tvořená pouze předpokladem a závěrem. Existují ale i algoritmy, které pravidlům přiřadí nějakou hodnotu (pravděpodobnost, váhu). Tato hodnota je použitelná v průběhu klasifikace při posuzování nových příkladů způsobem, který je blízký tzv. expertním systémům14. V následující podkapitole podrobně popíšeme algoritmus ESOD, výsledek výzkumu kolektivu autorů z VŠE v Praze, zde se podíváme na tzv. pravděpodobnostní pravidla vytvářená systémem ITRule [Goodman, Smyth, 1989]. Pravidla vytvářená systémem ITRule mají tvar IF Ant THEN Suc (p), kde Ant je kombinace kategorií, Suc je jedna kategorie a p je podmíněná pravděpodobnost cíle, a
nastane-li předpoklad, tedy hodnota a + b počítaná ze čtyřpolní tabulky. Jednotlivá pravidla jsou vyhodnocována na základě vzájemné informace, kterou autoři systému nazývají j-míra. Pro pravidlo IF Ant THEN Suc je vzájemná informace (j-míra) definována jako j(Suc,Ant) = P(Suc|Ant)×log2
P(¬Suc|Ant) ( P(Suc|Ant) P(Suc) ) + P(¬Suc|Ant)×log ( P(¬Suc) ), 2
kde pravděpodobnosti se opět odhadují jako relativní četnosti v trénovacích datech. První člen součtu se týká podmíněné pravděpodobnosti toho, že platí závěr, pokud víme, že platí předpoklad, druhý člen součtu se týká podmíněné pravděpodobnosti toho, že závěr neplatí, pokud víme, že platí předpoklad. Tato hodnota umožní stanovit průměrný informační obsah pravidla Javg(Suc,Ant) = p(Ant) × j(Suc,Ant),
Algoritmus ITRule postupuje jak metodou generalizace (ubírání podmínek v předpokladu pravidla), tak metodou specializace (přidávání podmínek do předpokladu pravidla). Jako kritérium pro zařazení pravidla slouží právě hodnota Javg. Báze pravidel je předem daným počtem pravidel s nejvyšším Javg. Zvláštností algoritmu je, že atributy ze závěru pravidla se mohou objevit v předpokladech jiných pravidel. Není zde tedy striktně stanoven jeden „cílový“ atribut, tak jak je tomu u ostatních algoritmů. ITRule hledá pravidla k hodnotám všech atributů. Bázi pravidel vytvořenou algoritmem lze použít v řadě expertních systémů. Pravidla jsou použitelná jak pro přímé řetězení, tak pro zpětné řetězení pravidel15. Práce s neurčitostí je založena na bayesovském přístupu. 14
Expertní systémy jsou počítačové programy, které se na základě vhodně zakódovaných znalostí z nějaké speciální oblasti snaží dosáhnout kvality rozhodování srovnatelné s lidským expertem. Vhodné oblasti pro nasazení expertních systémů jsou např. lékařská nebo technická diagnostika, posuzování bonity klienta banky, navrhování konfigurací počítačů apod. Podstatné je, že v expertních systémech jsou uloženy vysoce specializované znalosti získané od expertů v dané oblast. Vzhledem k tomu, že jsou tyto znalosti často reprezentovány v podobě pravidel, zkoumá se možnost jak tato pravidla získávat automatizovaně, z dat.
15
V expertních systémech se používají dva základní způsoby odvozování. Při přímém řetězení se použijí pravidla, která lze přímo aplikovat na daný příklad, při zpětném řetězení se ke zvolenému cíli nejprve naleznou všechna aplikovatelná pravidla a ta se pak použijí.
8
5.3.4
Algoritmus ESOD
Úlohy kombinační analýzy dat popsané v předcházející podkapitole umožňují nalézat vztahy (implikace a dvojité implikace), které jsou podporovány danými daty. Tak např. při analýze příčin jsme hledali podmínky, za kterých nějaký objekt patří do třídy Class. Každý takový vztah můžeme považovat za (objevenou) znalost. Tyto znalosti pak můžeme pak dále zkoumat a interpretovat. Problém je ale v tom, že takovýchto vztahů je obvykle značné množství a že nemáme zatím v ruce prostředek, jak tyto znalosti použít v případě, že máme rozhodnout o novém objektu, zda patří do uvažované třídy. Celkem logicky se tedy naskýtá otázka, zda je možné nalézt v souboru generovaných vztahů takové vztahy, které jsou důležitější než ostatní, a zda je možné tyto vztahy použít pro automatickou klasifikaci nových objektů. Kladnou odpověď na tuto otázku dává algoritmus ESOD. Základní myšlenkou algoritmu je vybrat z implikací nalezených při analýze příčin pravidla do báze znalostí expertního systému ([Ivánek, Stejskal, 1988]).V této podkapitole tedy budeme uvažovat o vybudování expertního systému, jehož znalosti by se automaticky získávaly z dat16. Při formulaci této úlohy musíme rozhodnout o •
podobě báze znalostí,
•
podobě inferenčního mechanismu,
•
způsobu, jak v souboru vztahů nalézt znalosti.
Začněme nejprve variantou systému pro situaci, kdy trénovací data DTR jsou rozdělena na příklady a protipříklady nějakého konceptu17. Báze znalostí je vytvářena v podobě souboru pravidel tvořených vztahy implikace k zadané cílové kombinaci. Vztahy jsou opatřeny váhou která vyjadřuje neurčitost ve znalostech. Pravidla v bázi znalostí tedy mají podobu 18 Ant ⇒ Class (w), kde
Ant je kombinace kategorií vstupních atributů, Class je kombinace definující pozitivní příklady (tedy Class = C(+)), w z intervalu [0,1] je váha vyjadřující neurčitost pravidla.
Inferenční mechanismus budovaného systému pracuje metodou přímého řetězení. V průběhu konzultace se pro nový objekt popsaný hodnotami vstupních atributů (popis objektu nemusí být úplný!) naleznou všechna aplikovatelná pravidla. Příspěvky těchto pravidel19 se složí pomocí kombinační funkce ⊕ a tak se naleznou výsledné váhy všech cílů. Jako kombinační funkce se používá
16
Tato myšlenka zdůvodňuje název algoritmu: Expertní Systém z Observačních Dat.
17
Algoritmus ESOD prošel podobným vývojem jako algoritmy „rozděl a panuj“ nebo „odděl a panuj“. První verze algoritmu ([Ivánek, Stejskal, 1988]) předpokládala pouze kategoriální data a dvě třídy. Umožňovala ale zpracovávat data zatížená šumem. Později byl algoritmus ESOD rozšířen pro více tříd (to bude popsáno vzápětí) a doplněn o algoritmus diskretizace numerických atributů (tento algoritmus je uveden v kapitole věnované předzpracování dat.
18
Ve srovnání s „klasickými“ expertními systémy, jejichž báze znalostí mívá bohatší strukturu má báze znalostí vytvořená z dat podobu tzv. „trávy“, tedy pravidel pouze od dotazů přímo k cílům. Symbol ⇒ naznačuje, že pravidlo má podobu implikace z kombinační analýzy dat.
19
Předpokládáme, že předpoklad aktivovaného pravidla platí s jistotou; přípěvek pravidla se tedy rovná váze pravidla.
9
pseudobayesovské skládání vah známé z expertního systému PROSPECTOR20 [Duda, Gasching, 1979]. Jsou-li w1, w2 váhy dvou pravidel, spočítá se jejich kombinace w⊕ jako: w1 ⊕ w2 =
w1 × w2 w1 × w2 + (1 - w1) × (1 - w2)
Při tvorbě báze pravidel se vlastně provádí postupné zpřesňování a zjemňování již existujících znalostí (knowledge refinement). Bázi pravidel vytváříme „shora dolů“ postupným přidáváním nových (speciálnějších) pravidel ve chvíli, kdy báze přestane být konsistentní s trénovacími daty reprezentovanými souborem všech implikací k zadanému cíli. Na počátku obsahuje báze pravidel tzv. prázdný vztah, který odpovídá rozdělení tříd v trénovacích datech. Do báze pravidel se pak postupně zařazují jen ty implikace, které nejsou odvoditelné z již získaných kratších pravidel. Vztah implikace Ant ⇒ Class považujeme v daných datech za odvoditelný z nějaké množiny KB pravidel se závěrem Class, jestliže v datech nezamítneme (na zvolené hladině významnosti) hypotézu, že platnost21 této implikace P(Class|Ant) =
n(Ant ∧ Class) n(Ant)
odpovídá tzv. naskládané váze w⊕(Ant) získané složením vah těch pravidel z KB, jejichž levá strana je podkombinací kombinace Ant. Pro testování této hypotézy se používá χ2 test dobré shody. Tento test je již zmíněn v kapitole věnované statistice jakožto test umožňující testovat nezávislost dvou veličin na základě porovnání očekávaných a skutečných četností. V podobném duchu je χ2 test použit i zde. V případě, že Class definuje pouze pozitivní příklady (tedy Class = C(+)) uvažujeme test pro dvě třídy (tedy T=2). Do testu vstupují implikace Ant ⇒ Class (označme Ant ⇒ Class1), a Ant ⇒ ¬Class (označme Ant ⇒ Class2) a naskládané váhy w⊕(Ant) (označme w1⊕(Ant)) a 1- w⊕(Ant) (označme w2⊕(Ant)). Testem porovnáváme hodnoty skutečných četností nt(Ant) nalezených pro implikace Ant ⇒ Classt v trénovacích datech a četností očekávaných, spočítaných jako n(Ant) × wt⊕(Ant), kde wt⊕(Ant) jsou váhy tříd Classt odvozené při konzultaci pro příklad popsaný kombinací Ant. Pro T tříd tedy spočítáme hodnotu T
χ2
=
∑
(nt(Ant) − n(Ant) × wt⊕(Ant))2 n(Ant) × wt⊕(Ant)
=
t=1 T
=
∑ t=1
T T nt(Ant) × nt(Ant) − 2 ∑ nt(Ant) + n(Ant) ∑ wt⊕(Ant) = ⊕ n(Ant) × wt (Ant) t=1 t=1
20
Tato operace se použije s ohledem na syntaktické závislosti mezi pravidly tak, jak to navrhl Hájek [Hájek, 1985].
21
Abychom se při výpočtu vyhnuli problémům s extremálními hodnotami platnosti implikace, provádíme následující korekce: • je-li P(Class|Ant)=0, položíme P(Class|Ant)=0.5/n(Ant), • je-li P(Class|Ant)=1, položíme P(Class|Ant)=(n(Ant)-0.5)/n(Ant), Tato korekce má podobný význam jako Laplaceova korekce použitá v případě systému CN4; zabránit tomu, aby podmíněná pravděpodobnost závěru při platnosti předpokladu nabývala hodnoty 0 nebo 1.
10
T
=
∑
nt(Ant) × nt(Ant) − n(Ant) . n(Ant) × wt⊕(Ant)
t=1 Pokud je tato hodnota větší než hodnota rozdělení χ2(T-1)(α) s (T-1) stupni volnosti na zvolené hladině významnosti α, zamítneme hypotézu o shodě platnosti a naskládané váhy a přidáme danou implikaci Ant ⇒ Class do báze znalostí, protože její platnost nelze ze stávající báze odvodit. Váhu nového pravidla zvolíme tak, „aby to vyšlo“, tedy tak, abychom po konzultaci s novou bázi znalostí (tj. s bázi včetně přidaného pravidla) pro příklad popsaný vstupní kombinací Ant odvodili právě platnost implikace Ant ⇒ Class. Pro nové pravidlo Ant ⇒ Class (w) musí platit w ⊕ w⊕(Ant) = P(Class|Ant). Váhu w tedy spočítáme jako u w= 1+u,
kde
u =
P(Class| Ant) 1 - P(Class| Ant) w ⊕ (Ant)
.
1 - w ⊕ (Ant)
Uvedený postup zařazování pravidla do báze si přiblížíme na následujícím příkladu. Řekněme, že právě testovanou implikací je22 7a ∧ 11a ⇒ 1+, která má v datech čtyřpolní tabulku: Class Ant 11 ¬Ant 74
¬Class 14 26
a 11 Tedy platnost této implikace je a + b = 11+14 = 0.44. Předpokládejme dále, že v bázi pravidel existují tři pravidla, aplikovatelná na kombinaci Ant: ∅ 11a 7a
⇒ ⇒ ⇒
1+ 1+ 1+
(0.6800) (0.2720) (0.3052)
Pokud složíme váhy těchto pravidel pomocí operace ⊕, získáme tzv. naskládanou váhu w⊕(Ant) w⊕(Ant) = 0.6800 ⊕ 0.2720 ⊕ 0.3052 = 0.2586. Tato váha se (na základě χ2 testu) statisticky významně liší od platnosti implikace 0.44. Proto do báze pravidel přidáme pravidlo 7a ∧ 11a ⇒ 1+ (w), kde váha w je taková , že w ⊕ 0.2586 = 0.44, tedy w = 0.6926. 22
Opět používáme úsporný zápis kategorií.
11
Podoba algoritmu je uvedena na Obr. 9. Opakovaně se střídá generování (krok 1.4) a testování (krok 1.3) nějaké implikace. Řídícími parametry jsou cílová třída Class, maximální délka předpokladu lmax, minimální četnost předpokladu nmin, a minimální platnost (spolehlivost) pravidla Pmin.
Algoritmus ESOD Inicializace 1. vytvoř CAT - seznam kategorií A(v) uspořádaný sestupně dle četnosti n(A(v)) 2. vytvoř OPEN - seznam implikací A(v) ⇒ Class uspořádaný sestupně dle n(A(v)) 3. přiřaď do KB prázdné pravidlo ∅ ⇒ Class (w), kde w je relativní četnost třídy Class Hlavní cyklus 1. dokud OPEN není prázdný seznam 1.1. vezmi první implikaci ze seznamu OPEN (označ ji Ant ⇒ Class ) 1.2. spočítej platnost této implikace P(Class|Ant) 1.3. pokud P(Class|Ant) ≥ Pmin ∨ P(Class|Ant) ≤ (1 - Pmin) potom 1.3.1. spočítej pomocí kombinační funkce ⊕ váhu w⊕(Ant) naskládanou z vah pravidel v bázi KB aplikovatelných na Ant 1.3.2. pokud se platnost implikace P(Class|Ant) signifikantně liší (na základě χ2 testu) od naskládané váhy w⊕(Ant) potom 1.3.2.1. přidej do KB pravidlo Ant ⇒ Class (w), kde w ⊕ w⊕(Ant) = P(Class|Ant) 1.4. je-li l(Ant) < lmax, pak 1.4.1. pro každou kategorii A(v) ze seznamu CAT takovou, že: • atribut A se nevyskytuje v Ant • A(v) je v CAT před všemi kategoriemi z Ant - tedy platí, že četnost n(A(v)) je větší nebo rovna četnosti n(Ant) 1.4.1.1. generuj novou kombinaci AntA = Ant ∧ A(v) 1.4.1.2. je-li n(AntA) > nmin přidej AntA do seznamu OPEN za poslední kombinaci Comb takovou, že n(Comb) ≥ n(AntA) 1.5. odstraň Ant ze seznamu OPEN Obr. 9 Algoritmus ESOD pro jednu třídu
Pro rozšíření algoritmu pro více tříd se nabízejí dvě možnosti: vytvářet pravidla k jednotlivým třídám samostatně opakovaným průchodem trénovacími daty (tedy analogicky s vytvářením neuspořádaných pravidel v algoritmu CN4), nebo vytvořit pravidla ke všem třídám současně (tady je analogie s vytvořením rozhodovacího seznamu v algoritmu CN4). Byla zvolena druhá varianta, která vede k tomu, že k jednomu předpokladu Ant se vytvoří tolik pravidel, kolik je hodnot cílového atributu. Báze znalostí má tedy podobu „baterií pravidel“ Ant ⇒ Classt (wt),
kde Classt=C(vt), t=1,…,T.
Uvedené rozšíření vede ke změnám v algoritmu z Obr. 9. Nejjednodušší změnou je to, že místo jedné implikace Ant ⇒ Class budeme uvažovat T implikací Ant ⇒ Classt a místo jednoho pravidla Ant ⇒ Class (w), budeme uvažovat T pravidel Ant ⇒ Classt (wt),. Zásadnější změna souvisí se způsobem skládání vah. Použitý inferenční mechanismus interpretuje váhu 1 jako „jistě ano“, váhu 0 jako „jistě ne“ a váhu 0.5 jako „nevím“. Váha „nevím“ přitom odpovídá situaci, kdy jsou všechny cíle v datech zastoupeny rovnoměrně, tedy kdy platnost je rovna hodnotě 1/T, kde T je počet tříd. Pro více než dvě třídy (resp. pro více než jednu třídu a její protipříklady) tedy musíme mezi sebou převádět váhy a
12
platnosti tak, aby při práci s pravděpodobnostmi (χ2 test) bylo pro „nevím“ použito 1/T, a při práci s vahami (operace ⊕) bylo pro „nevím“ použito 0.5 23: T
váha = 2 × platnost
pro platnost ∈ [0, 1/T]
(
T
T
)
váha = 2∗(T-1) × platnost + 1 - 2∗(T-1)
pro platnost ∈ [1/T, 1]
resp. 2
platnost = T × váha platnost =
2∗(T-1) T
pro váhu ∈ [0, 0.5]
(
× váha + 1 -
)
2∗(T-1) T
pro váhu ∈ [0.5, 1]
Obr. 10 Převod mezi platností a váhou
Graf na Obr. 10 ukazuje způsob převodu. Vytváření pravidel k více třídám tedy znamená následující změny v algoritmu pro tvorbu pravidel (Obr. 9): •
váha prázdného vztahu je relativní četnost převedená na váhu (krok 3 inicializace),
•
do χ2 testu vstupuje platnost implikace a naskládaná váha převedená na platnost (krok 1.1.2 hlavního cyklu),
•
váha wt pravidla se spočítá ze vztahu wt ⊕ wt⊕(Ant) = P´(Classt|Ant), kde P´(Classt|Ant) je platnost převedená na váhu (krok 1.1.2.1 hlavního cyklu).
Místo cílové kombinace Class uživatel zadává cílový atribut C. V modifikaci pro více tříd byl algoritmus implementován v systému KEX [Berka, 1993], [Berka, Ivánek, 1994], i v novém systému pro dobývání znalostí z databází nazvaném LISP-Miner.
23
Pro T=2 se žádný převod provádět nemusí.
13
Použijeme-li uvedený algoritmus pro naše oblíbená data (Obr. 3), získáme pravidla uvedená na Obr. 11 24. Výpis (převzatý ze systému KEX) ukazuje hodnoty n(Ant) (frequency left), n(Class) (frequency right) a n(Ant∧Class) (frequency both), váhu pravidla a vlastní pravidlo. První pravidlo s předpokladem 0- je tzv. prázdné pravidlo (implicitní pravidlo, default); toto pravidlo zařadí každý příklad do majoritní třídy (tedy úvěr(ano)). V zápise pravidla je každá kategorie uvedena jako dvojice [pořadové číslo atributu, písmeno označující hodnotu], tedy stejně jako v podkapitole věnované generování kombinací u asociačních pravidel. Pravidla, která rozhodují o tom, kdy půjčit jsou tedy 25: 1. úvěr(ano) (0.6667) 2. IF příjem(vysoký)
THEN úvěr(ano) (0.9802)
3. IF konto(vysoké)
THEN úvěr(ano) (0.9753)
4. IF nezaměstnaný(ne) ∧ pohlaví(žena) THEN úvěr(ano) (0.9512) 6. IF konto(střední) ∧ nezaměstnaný(ne)
THEN úvěr(ano) (0.9512)
GENERATED RULES Frequencies no. left right both weight Implication -----------------------------------------------------1 120.00 80.00 80.00 0.6667 0- ==> 5a 2 50.00 80.00 50.00 0.9802 1v ==> 5a 3 40.00 80.00 40.00 0.9753 2v ==> 5a 4 20.00 80.00 20.00 0.9512 4n3z ==> 5a 5 20.00 80.00 0.00 0.0127 2s4a ==> 5a 6 20.00 80.00 20.00 0.9512 2s4n ==> 5a 7 20.00 80.00 0.00 0.0127 2n1n ==> 5a 8 10.00 80.00 0.00 0.0256 2s3z1n ==> 5a Obr. 11 Pravidla nalezená systémem KEX
Uvedená pravidla odpovídají zadání lmax = 4, nmin = 1 a Pmin = 0.9 26. Zde je třeba říci, že vhodná volba těchto parametrů vyžaduje jistou zkušenost. Neplatí totiž, že se zvyšujícím se rozsahem prozkoumaných implikací se zlepšuje chování nalezené báze znalostí. Dochází zřejmě k přeučení systému. Jsou ale jakési standardní strategie, jak volit vstupní parametry pro tvorbu báze pravidel: •
plná analýza (lmax = počet všech atributů, které se nevyskytují v cíli, nmin = 1, Pmin = 0),
•
minimální analýza (lmax = 1, nmin = 1, Pmin = 0),
•
analýza "bez šumu" (Pmin = 1); toto zadání znamená, že se do báze zařadí pouze 100% vztahy27.
24
Dopustili jsme se přitom malého triku. Vzhledem k tomu, že algoritmus používá statistický test, je pro jeho správnou činnost potřeba dostatečný počet trénovacích příkladů. Zde jsme tedy každý příklad vážili (násobili) vahou 10.
25
Jedná se o pravidla, která mají váhu w>0.5.
26
Připomeňme, že kombinační analýza nalezla pro totéž zadání celkem 46 implikací se závěrem úvěr(ano).
27
Tato strategie je vhodná, víme-li apriori, že data neobsahují žádné kontradikce. Budeme pak do báze znalostí zařazovat pouze pravidla s velikou diskriminační silou.
14
Při klasifikaci nového příkladu použijeme všechna 28 aplikovatelná pravidla a pomocí funkce ⊕ poskládáme jejich váhy. Příklad zařadíme ke třídě, pro kterou odvodíme nejvyšší váhu; v případě jedné třídy příklad patří k této třídě, pokud odvodíme váhu w⊕>0.5. Kolem hodnoty w⊕=0.5 lze zvolit jakési „pásmo nerozhodnutelnosti“. Příklady pro které se odvodí váha v tomto pásmu nebudou systémem zařazeny do žádné třídy.
Jestliže porovnáme algoritmus ESOD s dříve uvedenými klasickými algoritmy strojového učení pro tvorbu rozhodovacích stromů a pravidel, nalezneme následující odlišnosti: 1. vzhledem k použitému statistickému testu je potřeba dostatečný počet příkladů, 2. pro jeden příklad lze nalézt více použitelných pravidel (z trénovacích dat se neodstraňují pokryté objekty), 3. v bázi pravidel se mohou objevit jako pravidla vztah i jeho prodloužení (redundance je měřena statistickým testem), 4. při konzultaci může systém pro jeden příklad doporučit (odvodit s pozitivní vahou) více cílů 29.
Algoritmus tedy vytváří více pravidel, což umožňuje různé pohledy na danou úlohu a umožňuje provést konzultaci i v případě neúplně (nebo částečně chybně) popsaného případu. Redundance (v tomto smyslu) je také výhodná při klasifikaci objektů, které nebyly zahrnuty v trénovacích datech.
5.3.5 Chybějící hodnoty Podobně jako v případě rozhodovacích stromů, i v případě rozhodovacích pravidel se chybějící hodnoty ošetřují ve fázi předzpracování dat (často implementované jako součást systému pro tvorbu pravidel). Brůha [Bruha, 1996] uvádí tyto relativně vyčerpávající možnosti, jak nakládá s chybějící hodnotou systém 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.
V systému KEX se používá pouze nejjednodušší možnost – ignorování příkladů s chybějícími údaji.
28
29
To je výrazný rozdíl ve srovnání s jinými algoritmy pro tvorbu rozhodovacích pravidel a stromů, kde se použije jediné pravidlo resp. cesta stromem. V případě, že se cíle navzájem nevylučují (např. pacient je imunní, pacient nemá infekci [Berka,1993d]), lze to objevit.
15
5.3.6
Numerické atributy
Vzhledem k tomu, že algoritmy pro tvorbu rozhodovacích pravidel pracují pouze s kategoriálními daty 30 , je třeba numerické atributy diskretizovat. Opět se nabízejí dvě možnosti, diskretizace ve fázi předzpracování (tak je např. řešena diskretizace v systému KEX), nebo diskretizace během běhu algoritmu. Tento druhý způsob si přiblížíme na příkladu diskretizace v systému CN4 [Berka, Bruha, 1998].
Diskretizace je v systému CN4 prováděna při každém průchodu hlavním cyklem algoritmu pro tvorbu pravidel. Každý atribut se diskretizuje samostatně. Cílem diskretizace je nalézt vhodné hodnoty xi atributu A, které tento atribut rozdělí na (polouzavřené) intervaly vi =(xi1,xi2]. To pak umožní vytvářet kategorie A(vi). Vhodné horní (dolní) meze hledaných intervalů odpovídají nerostoucím (neklesajícím) lokálním maximům heuristické vyhodnocovací funkce F(xi). Pro funkci F se používá buď negativní entropie, nebo Laplaceův odhad spolehlivosti (viz 5.3.2). Roli antecedentu pro výpočet četností figurujících v příslušných vzorcích nyní hraje testovaný interval.
Algoritmus SetBounds(a) 1. nechť PoleMezí je prázdné 2. pro každou hodnotu xi atributu A 2.1. spočítej pro každou třídu Classt (t=1,..,T) četnosti nt(A(≤xi)) a nt(A(>xi)) 2.2. spočítej hodnotu funkce F(A(≤xi)) (označ Flevá(xi)) pro případ, že xi je potenciální horní mez, tedy že A(≤xi) bude vytvořená kategorie 2.3. spočítej hodnotu funkce F(A(>xi)) (označ Fpravá(xi)) pro případ, že xi je potenciální dolní mez, tedy že A(>xi) bude vytvořená kategorie 3. pro každou hodnotu xi atributu A 3.1. pokud Flevá(xi) je nerostoucí lokální maximum, tedy Flevá(xi-1) ≤ Flevá(xi) > Flevá(xi+1) 3.1.1. přidej kategorii A(≤ xi) do PoleMezí v pořadí podle hodnoty Flevá(xi) 3.2. pokud Fpravá(xi) je neklesající lokální maximum, tedy Fpravá(xi-1) < Fpravá(xi) ≥ Fpravá(xi+1) 3.2.1 přidej kategorii A(>xi) do PoleMezí v pořadí podle hodnoty < Fpravá(xi) 4. pro každou dvojici hodnot xi1 , xi2 z PoleMezí 4.1. spočítej pro každou třídu Classt (t=1,..,T) četnosti nt(A(v)), kde v=(xi1,xi2] 4.2. spočítej hodnotu funkce F(A(v)) 4.3. přidej kategorii A(v), kde v=(xi1,xi2] do PoleMezí v pořadí podle hodnoty F(v) Obr. 12 Diskretizace v algoritmu CN4
Algoritmus diskretizace je uveden na Obr. 12. Diskretizační procedura postupně bere do úvahy všechny hodnoty vi jako potenciální meze a počítá pro ně hodnotu funkce F. Pak hledá lokální maxima (vhodné meze). V posledním kroku se z mezí vytvářejí intervaly. Vezměme si pro ilustraci tohoto algoritmu situaci, kdy máme 7 pozitivních příkladů (s hodnotami numerického atributu 45, 46, 50, 50, 100, 100, 120) a 5 negativních příkladů (s hodnotami atributu 51, 30
Při hodnocení pravidel nás zajímají četnosti.
16
51, 51, 99, 99). Průběh funkce F (počítané jako negativní entropie) je uveden na Obr. 13. Potenciální dolní meze intervalů jsou 45, 50, a 99, jedinou potenciální horní mezí je hodnota 50. To vede na vytvoření následujících intervalů seřazených podle hodnoty fukce F a četnosti n(A(v)). (Tab. 1): Interval v
F(A(v))
n(A(v))
50 < x <= 99
0.000
5
x <= 50
0.000
4
99 < x
0.000
3
45 < x <= 50
0.000
3
50 < x
-0.954
5
45 < x <= 99
-0.954
5
45 < x
-0.994
6
Tab. 1 Intervaly vzniklé diskretizací atributu A
Neg.entropie Flevá(x)
Fpravá(x)
0 x <= 50
x > 99
x > 50 -0.95 --0.99 --1 45
| 46
| 50
| 51
| 99
| 100
| 120
x
Obr. 13 Lokální maxima negativní entropie pro diskretizaci
To, že se diskretizace provádí dynamicky během tvorby pravidel znamená, že atributy mohou být diskretizovány opakovaně. Výsledky diskterizace ale mohou být různé, protože pokaždé vstupují do hry pouze dosud nepokryté (tedy různé) příklady.
17
5.3.7
Numerické třídy
Na rozdíl od rozhodovacích stromů, kde jsou algoritmy pro práci s numerickými třídami běžně používány 31, jsou algoritmy pro tvorbu rozhodovacích pravidel k numerickým třídám záležitostí spíše výzkumnou. K prvním takovým algoritmům patří R2 [Torgo,1995]. R2 hledá pravidla, která jsou „nejlepší“ vzhledem k střední absolutní odchylce mezi skutečnou hodnotou a hodnotou predikovanou. Algoritmus je omezen pouze na numerické atributy. Pravidla vytvářená systémem mají podobu IF Ant THEN avgAnt(y), nebo IF Ant THEN ∑i,Ant ki xi. kde předpoklad Ant je kombinace kategorií typu A(>xi), resp. A(≤xi), závěr pravidla je v prvním případě konstanta (průměrná hodnota cílového atributu pro příklady splňující předpoklad), v druhém případě lineární kombinace vstupních atributů (opět pro příklady splňující předpoklad).
Podrobněji se opět podíváme na modifikaci systému CN4 [Bruha, Berka,1997]. V případě numerických tříd hledá systém CN4 pravidla ve tvaru IF Ant
THEN avgAnt(y), MvarAnt(y).
Předpoklad Ant je opět kombinace kategorií. Vzhledem k tomu, že C je nyní numerický atribut, objevuje se v závěru pravidla průměrná hodnota cíle počítaná pro příklady, které jsou pokryty pravidlem avgAnt(y) a rozptyl tohoto průměru MvarAnt(y): 1
avgAnt(y) = n(Ant)
n(Ant)
∑ yi , pro oi ∈ {Ant}
i=1
varAnt2(y) MvarAnt(y) = n(Ant) , kde
n(Ant) 1 varAnt2(y) = n(Ant)-1 ∑ (yi - avgAnt(y))2 , pro oi ∈ {Ant}. i=1
Generování pravidel probíhá podobně jako ve verzi algoritmu pro diskrétní třídy; metodou specializace komplexů (kombinací) přidáváním selektorů (hodnot atributů). Pravidla se vyhodnocují na základě porovnání směrodatné odchylky cílového atributu pro příklady pokryté pravidlem a směrodatné odchylky pro celá trénovací data. Při klasifikaci nových příkladů se hledá aplikovatelné pravidlo, průměrná hodnota cílového atributu tohoto pravidla avgAnt(y) se pak považuje za hodnotu odvozenou pro uvažovaný příklad. Známe-li správnou hodnotu cíle pro tento příklad, můžeme posoudit přesnost provedené klasifikace tak, že zjistíme, zda tato správná hodnota leží v intervalu [avgAnt(y)-
31
MvarAnt(y) 3
, avgAnt(y)+
MvarAnt(y) 3
Jde v tomto případě o regresní stromy implementované např. v systému CART.
18
].
5.3.8
Koncepty proměnlivé v čase
Ve většině úloh dobývání znalostí se předpokládá, že koncept (třída) jehož popis se máme naučit je stálý a s přibývajícím počtem trénovacích příkladů se nemění. Použité algoritmy pak obvykle pracují s celými daty naráz, v dávkovém režimu. Jsou ale úlohy, kdy se koncept v průběhu času dramaticky změní. Příkladem může být předpovídání počasí, které silně závisí na roční době. Jasná obloha v létě dává tušit vysoké teploty, jasná obloha v zimě znamená teploty nízké. Pak je užitečné se takovýmto změnám konceptu přizpůsobit tak, že bereme do úvahy jen aktuální (čerstvá) data. V oblasti strojového učení se tento přístup nazývá inkrementální učení a zapomínání. Algoritmus takového typu byl implementován v systémech FLORA (např. [Widmer, Kubat, 1992]). Jádrem algoritmu je hledání hypotéz pokrývajících příklady dané třídy metodou generalizace analogicky jako u algoritmu AQ. Příklady jsou popsány hodnotami (kategoriálních) atributů a hypotézy mají podobu kombinací kategorií 32. Kombinace jsou ukládány do tří množin: množina POS obsahuje hypotézy konzistentní s konceptem (kombinace pokrývá pouze pozitivní příklady), množina NEG obsahuje hypotézy konzistentní s negací konceptu (kombinace pokrývá pouze negativní příklady), a množina POT obsahuje potenciální hypotézy (kombinace které pokrývají pozitivní i negativní příklady). U každé hypotézy Comb se sleduje, kolik pozitivních resp. negativních příkladů pokrývá (n+(Comb), n-(Comb)). Inkrementalita algoritmu učení spočívá v tom, že množiny POS, NEG a POT jsou aktualizovány po každém načtení nového příkladu. je-li např. nový pozitivní příklad pokryt hypotézu z NEG, přesune se tato hypotéza do POT. Popis algoritmu je na Obr. 14.
Algoritmus inkrementálního učení 1. pro každý příklad oi z trénovací množiny 1.1. je-li oi pozitivní potom 1.1.1. pro každou Comb z POS pokud Comb pokrývá oi přiřaď n+(Comb) := n+(Comb) + 1 1.1.2. pro každou Comb z POT pokud Comb pokrývá oi přiřaď n+(Comb) := n+(Comb) + 1 1.1.3. pro každou Comb z NEG pokud Comb pokrývá oi přiřaď n+(Comb) := 1 a přesuň Comb do POT 1.1.4. pokud v POS není žádná Comb která pokrývá oi, přidej do POS novou kombinaci CombN, která pokryje oi a nebude (kvůli sporu) v souladu s hypotézami v POT a NEG, a přiřaď n+(CombN) := 1 1.2. je-li příklad oi negativní potom 1.2.1. pro každou Comb z NEG pokud Comb pokrývá oi přiřaď n-(Comb) := n(Comb) + 1 1.2.2. pro každou Comb z POT pokud Comb pokrývá oi přiřaď n-(Comb) := nComb) + 1 1.2.3. pro každou Comb z POS pokud Comb pokrývá oi přiřaď n-(Comb):= 1 a přesuň Comb do POT 1.2.4. pokud v NEG není žádná Comb která pokrývá oi, přidej do NEG novou kombinaci CombN, která pokryje oi a nebude (kvůli sporu) v souladu s hypotézami v POT a POS, a přiřaď n-(CombN) := 1 Obr. 14 Inkrementální učení v systému FLORA
32
Každou kombinaci můžeme chápat jako předpoklad jednoho pravidla.
19
Reakce na změnu konceptu je umožněna díky mechanismu zapomínání. Ten je analogický algoritmu učení. Starší příklady jsou zapomínány, což opět vede ke změnám v množinách POS, NEG a POT – tentokrát se ale počty pokrytých příkladů odčítají. Zapomenou-li se např. všechny příklady, které odpovídaly nějaké hypotéze Comb z množiny POS (tedy n+(Comb) klesne na 0), odstraní se Comb z POS (viz Obr. 15). To že starší příklady jsou zapomínány znamená, že FLORA pracuje jen s jakýmsi „oknem“, které se posunuje podél trénovací množiny. V paměti se tak udržuje jen určitý počet nejaktuálnějších příkladů. Schematicky je celý proces učení a zapomínání znázorněn na Obr. 16. Algoritmus inkrementálního zapomínání 1. je-li příklad oi pozitivní příklad, potom 1.1. pro každou Comb z POS 1.1.1. pokud Comb pokrývá oi přiřaď n+(Comb) := n+(Comb) - 1 1.1.2. je-li n+(Comb) = 0, odstraň Comb z POS 1.2. pro každou Comb z POT 1.2.1. pokud Comb pokrývá oi přiřaď n+(Comb) := n+(Comb) - 1 1.2.2. je-li li n+(Comb) = 0, přesuň Comb do NEG 2. je-li příklad oi pozitivní příklad, potom 2.1. pro každou Comb z NEG 2.1.1. pokud Comb pokrývá oi přiřaď n-(Comb) := n-(Comb) - 1 2.1.2. je-li li n-(Comb) = 0, odstraň Comb z NEG 2.2. pro každou Comb z POT 2.2.1. pokud Comb pokrývá oi přiřaď n-(Comb) := n-(Comb) - 1 2.2.2. je-li n-(Comb) = 0, přesuň Comb do POS Obr. 15 Inkrementální zapomínání v systému FLORA
učení
u−
u+ POS
u+ POT
NEG
zapomínání z+
z−
u−
z+
z−
Obr. 16 Proces inkrementálního učení a zapomínání
Přizpůsobení se změně konceptu je umožněno dynamickou modifikací velikosti okna (počtu příkladů uchovávaných v paměti). Myšlenka této modifikace je poměrně jednoduchá: pokud se koncept nemění, okno má stabilní velikost (aby se hypotézy vytvářely na základě hodně příkladů), pokud se koncept začíná měnit, okno se zmenšuje (zapomínají se příklady, které odpovídají starému konceptu). Jak ale poznat začínající změnu konceptu? Změna konceptu je automaticky indikována tehdy, když klesá podíl počtu pozitivních příkladů pokrytých množinou POS ku velikosti množiny POS 33. Tento pokles znamená, že se nedaří nalézt dostatečně obecné hypotézy pokrývající pozitivní příklady, a že se tedy něco děje. Reakcí systému na tuto skutečnost je zmenšení velikosti okna o 10%. Pokud se zdá být kontext stabilní (výše uvedený podíl je vysoký), velikost okna se nemění. Pokud není podíl ani velký ani malý (systém se zotavuje ze změny konceptu), okno roste tak, že po načtení nového příkladu se nejstarší příklad nezapomene. 33
Velikost množiny POS se měří počtem kategorií vyskytujících se v hypotézách v množině POS.
20
Uvedený algoritmus byl schopen dobře zpracovávat pouze nezašuměná data, neboť v množině POS jsou hypotézy konzistentní s pozitivními příklady a v množině NEG jsou hypotézy konzistentní s negativními příklady. Novější verze algoritmu toto omezení odstranila tak, že neklade taková striktní omezení na obě množiny. Jednotlivé hypotézy se vyhodnocují statisticky ([Widmer, 1994]).
5.3.9
Integrace znalostí
Integrace znalostí je otázka, která budí pozornost řady odborníků. Integrací se rozumí zkombinování znalostí získaných z různých zdrojů do uceleného, konsistentního systému. O integraci znalostí se mluví v souvislosti s expertními systémy (kdy je třeba sloučit znalosti získané od více expertů) i v souvislosti se strojovým učením a dobýváním znalostí z dat V tomto druhém kontextu se může jednat o využití doménových znalostí (tzv. background knowledge) majících podobu např. hierarchie hodnot atributů nebo dílčích expertních znalostí 34, nebo o zpřesňování a revizi dříve získaných znalostí (knowledge refinement and revision) na základě dalších dat 35. Předpokládáme přitom, že staré i nové příklady odpovídají stejnému konceptu; na rozdíl od předcházející podkapitoly se tedy nic nezapomíná. Obr. 17 ukazuje dva možné přístupy k integrování znalostí; „složení“ jednotlivých modelů do modelu výsledného (vlevo), nebo aktualizace modelu na základě nových dat (vpravo). První možnost nalezneme např. v [Brazdil, Torgo, 1990]. Dílčí znalosti mají podobu pravidel získaných pomocí systémů ID3 nebo AQ z různých dat. Algoritmus pro integrování prochází seznam všech pravidel uspořádaný podle kvality 36 a postupně přidává do souhrnné báze jen ta nejlepší. Poté, co je vybráno nějaké pravidlo, algoritmus přepočítá kvalitu všech zbývajících pravidel 37. Proces výběru pravidel končí, když není k dispozici žádné pravidlo s dostatečnou kvalitou. Staré znalosti 1
......
Staré znalosti z
Nová trénovací data
Integrace znalostí
Staré znalosti
Integrace znalostí
Nové znalosti
Nové znalosti
Obr. 17 Obecné schéma integrace znalostí
Příklad druhého přístupu, zařazený do kontextu systému KEX, nalezneme např. v [Berka, 1997]. Integrace znalostí je zde řešena při zachování hlavní myšlenky algoritmu ESOD, přidávat do báze jen ty implikace, která přinášejí novou znalost k již existujícím pravidlům. Algoritmus integrace tedy 34
Viz pasáže věnované hierarchii atributů a induktivnímu logickému programování.
35
Při dobývání znalostí může nastat situace kdy získáme další trénovací data poté, kdy jsme již vytvořili nějaký model. Pro algoritmy umožňující inkrementální učení je tento typ integrování znalostí přirozeným způsobem práce. Rozhodovací stromy a pravidla se ale obvykle vytvářejí v dávkovém režimu
36
Kvalita pravidla závisí na přesnosti a pokrytí. Podrobněji v kapitole věnované asociačním pravidlům.
37
Kvalita zbývajících pravidel se počítá s vyloučením příkladů, pokrytých právě vybraným pravidlem. Aby to šlo spočítat, je ke každému pravidlu přiřazena informace o tom, které příklady pokrývá a které z nich patří k dané třídě.
21
porovnává implikace vytvořené pro nová trénovací data a dříve vytvořená pravidla. Pokud nějaká implikace Ant ⇒ Class bude zařazena jako nové pravidlo, může to ovlivnit taková již existující pravidla Combr ⇒ Class (wr) pro která je kombinace Combr prodloužením (nadkombinací) kombinace Ant. Tato pravidla je tedy třeba rovněž otestovat a buď je z báze pravidel odstranit (jsou-li nyní zbytečná), nebo modifikovat jejich váhu. Schéma algoritmu je na Obr. 18.
Algoritmus integrace znalostí Inicializace 1. nechť KB je již existující báze pravidel 2. nechť IMPL je seznam implikací Ant ⇒ Class vytvořených z nových dat uspořádaný sestupně dle četnosti n(Ant) Hlavní cyklus 1. dokud IMPL není prázdný seznam 1.1. vezmi první implikaci ze seznamu IMPL (označ ji Ant ⇒ Class ) 1.2. spočítej pomocí kombinační funkce ⊕ váhu w⊕(Ant) naskládanou z vah pravidel v bázi KB aplikovatelných na Ant 1.3. pokud se platnost implikace P(Class|Ant) signifikantně liší (na základě χ2 testu) od naskládané váhy w⊕(Ant) potom 1.3.1. přidej/přepiš do KB pravidlo Ant ⇒ Class (w), kde w ⊕ w⊕(Ant) = P(Class|Ant) 1.3.2. pro každé pravidlo Combr ⇒ Class (wr) z KB takové, že Ant je podkombinací kombinace Combr 1.3.2.1. spočítej pomocí kombinační funkce ⊕ váhu w⊕(Combr) 1.3.2.2. pokud se platnost implikace P(Class|Combr) signifikantně liší od naskládané váhy w⊕(Combr) potom modifikuj váhu wr , jinak ostraň pravidlo Combr ⇒ Class (wr) z KB 1.4. odstraň Ant ⇒ Class ze seznamu IMPL Obr. 18 Algoritmus integrování znalostí pro systém KEX
5.3.10 Hierarchie hodnot atributů S hierarchiemi (taxonomiemi) hodnot atributů jsme se již setkali u asociačních pravidel. Podobný problém hledání pravidel pro různé úrovně obecnosti se může vyskytnout i v souvislosti s úlohou klasifikace. Ukažme si jeden přístup práce s hierarchiemi atributů, který byl navržen v kontextu algoritmu ESOD. Svátek [Svátek, 1996] rozlišuje dva typy hierarchií: hierarchii hodnot “vstupních” atributů a hierarchii hodnot cílového atributu. V obou případech má hierarchie podobu stromu s kořenem odpovídajícím nejobecnější hodnotě “any”. Tato hodnota vyjadřuje, že na atributu nezáleží 38 . Příklady hierarchií jsou uvedeny na Obr. 19 a Obr. 20. Původní hodnoty atributů jsou v plných obdélnících, abstraktní v tečkovaných.
38
Podobně tomu bylo v kapitole o učení jako prohledávání
22
V případě hierarchie “na vstupu” 39 hledá navržený algoritmus pouze pravidla, která mají v předpokladu hodnoty všech atributů. Báze pravidel se tedy místo od prázdného pravidla začíná vytvářet od pravidla, které má v předpokladu hodnotu “any” u všech atributů. Specializace se provádí tak, že se hodnota “any” u nějakého atributu nahradí speciálnější hodnotou v rámci dané hierarchie. Četnost výskytu takové hodnoty bude samozřejmě menší než u hodnoty obecnější, je tedy zachováno generování kombinací podle četnosti. Podobně jako v původním algoritmu ESOD se postupně procházejí všechny implikace, a zjišťuje se, zda se mají zařadit do báze pravidel. Naskládaná váha w⊕(Ant) pro konkrétní implikaci Ant ⇒ Class se počítá ze všech pravidel Combr ⇒ Class obecnějších než tato implikace ve smyslu hierarchie hodnot atributů. Pravidlo Combr ⇒ Class je obecnější než implikace Ant ⇒ Class pokud hodnoty všech atributů v Combr jsou stejné nebo obecnější, než hodnoty atributů v Ant. V bázi pravidel se tak mohou vyskytnout pravidla s hodnotami atributů z různé úrovně hierarchie (bydlení(vlastní_dům) i bydlení(nájemní)).
any
vlastní
vlastní dům
družstevní
vlastní byt
nájemní
Nájemní byt státní
Nájemní byt s majitelem
Obr. 19 Hierarchie vstupního atributu “bydlení”
V případě hierarchie hodnot cílového atributu (příklad takové hierarchie je na Obr. 20) se vytváří samostatná báze pravidel pro každou nelistovou hodnotu c dané hierarchie. Do učícího se algoritmu přitom vstupují pouze ty příklady, které patří do podstromu této hodnoty. Přitom se mění i hodnota cíle, původní (nejspeciálnější) hodnota je nahrazena hodnotou obecnější, ležící ovšem rovněž v podstromu hodnoty v. Tedy např. pro nelistový uzel “stanovena” (Obr. 20) budeme vytvářet bázi pravidel k příkladům tříd “imunní” a “neimunní”. Schema algoritmu je na Obr. 21.
Vytvořená hierarchická báze pravidel je pak použitelná pro konzultaci na různých úrovních obecnosti. Tento přístup je spíše vhodnější pro vysvětlování než pro klasifikaci.
39
Jedna hodnota může být součástí více hierarchií. To je dokumentováno v [Svátek, 1996] na příkladu objektů zakreslených v mapě, kdy např. “potok” může být v jedné hierarchii chápan jako vodní plocha (stejně jako rybník) a v druhé hierarchii jako jednorozměrný útvar (stejně jako cesta).
23
any
nestanovena
stanovena
imunní
neimunní
neinfikován
infikován
Obr. 20 Hierarchie cíle “diagnoza”
Algoritmus tvorby pravidel 1. pro každou nelistovou hodnotu v cílového atributu C 1.1. zařaď do trénovací množiny DTRv ty příklady, které mají jako hodnotu cílového atributu speciálnější hodnotu, než v 1.2. v množině DTRv nahraď původní hodnoty cílového atributu vk hodnotou vx takovou, že vx je speciálnější než v ale obecnější než ck (pokud vk je bezprostřední následovník hodnoty v, ponech vk nezměněno) 1.3. aplikuj algoritmus ESOD na trénovací data DTRv 1.4. přiřaď nalezená pravidla Rv k uzlu v hierarchie Obr. 21 Použití algoritmu ESOD pro hierarchii tříd
Touto zmínkou o práci s hierarchiemi hodnot zakončíme celou kapitolu věnovanou rozhodovacím pravidlům.
Literatrura: [Berka, 1993] Berka,P.: Vybrané znalostní systémy, SAK, SAZE, KEX. Skripta VŠE, Praha 1993. [Berka, 1993b] Berka, P.: Knowledge EXplorer. A tool for automated knowledge acquisition from data. Tech. Report, Austrian Research Institute for AI, Vienna, TR-93-03, 1993, 23s. [Berka, 1993c] Berka,P.: Discretization of numerical attributes for Knowledge EXplorer. Výzkumná zpráva, Praha, LISP-93-03, 1993, 11s. [Berka, 1993d] Berka,P.: A comparison of three different methods for acquiring knowledge about virological hepatitis tests. Tech. Report, Austrian Research Institute for AI, Vienna, TR-93-10, 1993, 29s.
24
[Berka, 1997] Berka,P.: Towards knowledge integration via knowledge revision: The Knowledge Explorer approach. In: (Nakhaeizadeh, Bruha, Taylor eds.) Proc. ECML'97 Workshop Dynamically Changing Domains: Theory Revision and Context Dependence Issues. Prague, 1997, 1-8. [Berka, Bruha, 1998] Berka,P. - Bruha,I.: Empirical comparison of various discretization procedures. Int. J. of Pattern Recognition and Artificial Intelligence Vol. 12 No. 7 (1998) 1017-1032. [Berka, Ivánek, 1994] Berka,P. - Ivánek,J.: Automated knowledge acquisition for PROSPECTOR-like expert systems. In. (Bergadano, de Raedt eds.) Proc. ECML'94, Springer 1994, 339-342. [Brazdil, Torgo, 1990] Brazdil,P. – Torgo,L.: Knowledge acquisition via knowledge integration. In: Current Tredns in Knowledge Acquisition, IOS Press, 1990. [Bruha, 1996] Bruha,I.: Rule-induction in machine learning: Some latest enhancements and trends. In: Proc. Artificial Intelligence Techniques AIT’96, Brno, 1996. [Bruha, Berka, 1997] Bruha,I. – Berka,P.: Knowledge acquisition of rules with continuous classes: Empirical comparison of two methods. In: (Kaylan, Lehman eds.) Proc. European Simulation Multiconference ESM'97, SCS, 1997, Vol.2, 42-46. [Bruha, Kočková, 1994] Bruha,I. – Kočková,S.: A support for decision making: Cost-sensitive learning system. Artificial Intelligence in Medicine, 6 (1994), 67-82. [Clark, Niblett, 1989] Clark,P. - Niblett,T.: The CN2 induction algorithm. Machine Learning, 3 (1989), 261283. [Duda, Gasching, 1979] Duda,R.O. - Gasching,J.E.: Model design in the Prospector consultant system for mineral exploration. in: Michie,D. (ed.), Expert Systems in the Micro Electronic Age, Edinburgh University Press, UK, 1979. [Goodman, Smyth, 1989] Goodman,R.: Smyth,P. The induction of probabilistic rule sets – the ITRule algorithm. In: Proc. Int. Wshop on Machine Learning, Morgan Kaufman, 1989. [Hájek, 1985] Hájek,P.: Combining functions for certainty factors in consulting systems. Int.J. Man-Machine Studies 22,1985, 59-76. [Ivánek, Stejskal, 1988] Ivánek,J. - Stejskal,B.: Automatic acquisition of knowledge base from data without expert: ESOD (Expert System from Observational Data). In: Proc. COMPSTAT'88 Copenhagen, Physica-Verlag, 1988, 175-180. [Lavrac, 2000] Lavrac,N.: Decision Rules. Slajdy, http://www.cs.bris.ac.uk/Teaching/Resources/COMS70300/ slides/RulesHTML/, 2000. [Michalski, 1969] Michalski,R.S.: On the Quasi-minimal solution of the general covering problem. In: Proc. 5th Int. Symposium on Information Processing FCIP’69, Bled, Yugoslavia, 1969, 125-128. [Mitchell, 1997] Mitchell,T.: Machine learning. McGraw-Hill. 1997. ISBN 0-07-042807-7 [Svátek, 1996] Svátek,V.: Learning with value hierarchies in the ESOD framework. In: Proc. Artificial Intelligence Techniques AIT’96, Brno, 1996. [Torgo,1995] Torgo,L.: Data fitting with rule-based regresion. In: Proc. Artificial Intelligence Techniques AIT’96, Brno, 1996. [Widmer, Kubat, 1992] Widmer,G. – Kubat,M.: Learning flexible concepts from streams of examples: FLORA2. In: (Neumann ed.) Proc. 10th European Conf. on Artificial Intelligence ECAI’92, John Wiley, 1992. [Widmer, 1994] Widmer,G.: Combining robustness and flexibility in learning drifting concepts. In: (Cohn ed.) Proc: 11th European Conf. on Artificial Intelligence ECAI’94, John Wiley, 1994.
25
