Informační systémy pro podporu rozhodování

Machine Learning, Artificial Intelligence, Data Mining

Informační systémy pro rozhodování

Informační systémy pro podporu rozhodování 2 Jan Žižka, Naděžda Chalupová Ústav informatiky PEF Mendelova universita v Brně


Informační systémy pro rozhodování Strojové učení, umělá inteligence, dolování z dat Strojové učení je moderní, rychle a neustále se rozvíjející technologie pro získávání (“dolování”) znalosti z dat. Umělá inteligence se zabývá technologiemi prohledávání libovolných (reálných a abstraktních) prostorů; cílem je nalezení optima (globálního maxima), což je nejlepší řešení nějakého zadaného problému. Dolování z dat je zaměřeno na odkrytí znalosti v datech ukryté: data → informace → znalost. Dolování z dat využívá veškeré vhodné technologie, zejména strojové učení, umělou inteligenci, logiku a matematiku.


Informační systémy pro rozhodování Mezi vytvářením dat a jejich porozuměním neustále narůstá mezera. Souvisí to úměrně s narůstajícím množstvím dat. Data ukrývají informaci jako svou potenciálně užitečnou část pro řešení různých konkrétních úloh. Data obsahují skupiny vzájemně si podobných hodnot, které představují vzory, tj. vzor (něco společného a typického) je zobecněním určité skupiny dat: ● ● ● ●

lovci sledují typické chování své kořisti, zemědělci sledují typické souvislosti při pěstování plodin, politici sledují typické vzory názorů voličů, milenci typické odezvy svých partnerů, apod.


Informační systémy pro rozhodování Dolování z dat se zaměřuje na elektronicky uložená data, přičemž prohledávání dat je automatizované pomocí počítačů. Odhaduje se, že množství uložených dat na celém světě se zdvojnásobuje každých 20 měsíců. Obecně platí, že více dat obsahuje více informace, tj. více znalosti, která je stále složitější. Inteligentně analyzovaná data představují velmi cenný zdroj. Z komerčního hlediska může jít o zvyšování konkurenční schopnosti; z vědeckého hlediska např. o zvýšení znalosti o řešeném problému.


Informační systémy pro rozhodování Dolování z dat se zabývá řešením problémů pomocí analýzy dat, která jsou v daném čase k dispozici. Odhalená znalost pak může účinně pomáhat při odhadu budoucích jevů. Užitečné vzory umožňují netriviální predikce o nových, v budoucnu se vyskytujících instancích. Data získaná libovolným způsobem nemají obecně nijak zřetelnou strukturu. Dolování z dat odhaluje různé skryté, avšak existující struktury — vzory struktur, tj. něco obecného, typického, aplikovatelného na více či méně si podobné popisy objektů. Objekty pak lze kategorizovat do jim příslušných skupin (tříd), kde není rozhodující unikátní individualita, nýbrž společné vlastnosti definující typ, např.: červené, zelené, modré, ... předměty (libovolného tvaru).



+

+

+

+

Metody alternativní ke statistice umožňují nalézt skryté datové struktury, které statistika odhalí jen velice obtížně nebo vůbec ne. Ilustrace ukazuje čtyři jednoduché případy, kdy odhalení neznámé struktury statisticky do druhého řádu selhává, protože všechny čtyři ukázky mají stejný střed + i kovarianci, takže se jeví stejně – ve skutečnosti by individuální případy měly být zařazeny do příslušných shluků či kategorií odlišně. Vícerozměrné případy jsou pak mnohem komplikovanější.


Informační systémy pro rozhodování Příklad dolování z dat: Kontaktní čočky ID 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Age young young young young young young young young pre-presbyopic pre-presbyopic pre-presbyopic pre-presbyopic pre-presbyopic pre-presbyopic pre-presbyopic pre-presbyopic presbyopic presbyopic presbyopic presbyopic presbyopic presbyopic presbyopic presbyopic

Spectacle prescription myope myope myope myope hypermetrope hypermetrope hypermetrope hypermetrope myope myope myope myope hypermetrope hypermetrope hypermetrope hypermetrope myope myope myope myope hypermetrope hypermetrope hypermetrope hypermetrope

Astigmatism no no yes yes no no yes yes no no yes yes no no yes yes no no yes yes no no yes yes

Tear produc- Recommended lenses tion rate reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal

none soft none hard none soft none hard none soft none hard none soft none none none none none hard none soft none none

presbyopic: dalekozraký starší (pokles akomodace věkem) myope: krátkozraký hypermetrope: dalekozraký


Informační systémy pro rozhodování Data kontaktní čočky popisují podmínky, kdy optik (ne)má předepsat určitý druh kontaktních čoček. Tabulka je mírně zjednodušená (nejsou v ní všechny atributy mající vliv na předpis čoček). Databáze popisuje všechny možné případy, které jsou bez chybějících hodnot a bez šumu. Dohromady je 24 instancí, popis čtyřmi atributy, které nabývají nominálních hodnot. Klasifikační třídy jsou tři. Data pocházejí ze srpna 1990. Jsou ve veřejně přístupném souboru různých dat UCI Repository Of Machine Learning Databases and Domain Theories (Univ. of California, Irvine, CA).


Informační systémy pro rozhodování Je v datech nějaká struktura? Jsou tři třídy: none (žádné čočky), soft (měké) a hard (tuhé) čočky. Podle čeho lze každou kombinaci nominálních hodnot zařadit do jednotlivých tříd?

young, myope, no, reduced: none presbyopic, hypermetrope, no, reduced: none pre-presbyopic, hypermetrope, yes, reduced: none presbyopic, myope, yes, reduced: ? Z tabulky plyne, že když je tear-production-rate = reduced, tak je vždy třída none. Ale ne vždy je hodnota atributu tear-production-rate = reduced pro třídu none!


Informační systémy pro rozhodování Například:

pre-presbyopic, hypermetrope, yes, normal: none Takže nestačí se řídit pouze jedním atributem, relevantní jsou zjevně i další: v jaké kombinaci hodnot? Popis struktury dat z hlediska klasifikační třídy může být různý, například srozumitelně pomocí pravidel nebo rozhodovacího stromu (white-box), nebo nesrozumitelně pomocí natrénované umělé neuronové sítě (black-box). Příklad pravidel a stromu získaných strojovým učením z dat kontaktní čočky:


Informační systémy pro rozhodování If astigmatism = no and tear-prod-rate = normal and spectacle-prescrip = hypermetrope then soft If astigmatism = no and tear-prod-rate = normal and age = young then soft If age = pre-presbyopic and astigmatism = no and tear-prod-rate = normal then soft If astigmatism = yes and tear-prod-rate = normal and spectacle-prescrip = myope then hard If age = young and astigmatism = yes and tear-prod-rate = normal then hard If tear-prod-rate = reduced then none If age = presbyopic and tear-prod-rate = normal and spectacle-prescrip = myope and astigmatism = no then none If spectacle-prescrip = hypermetrope and astigmatism = yes and age = pre-presbyopic then none If age = presbyopic and spectacle-prescrip = hypermetrope and astigmatism = yes then none

Celkem 9 pravidel popisuje kompletně problém předepsání kontaktních čoček. Pravidla vygenerována algoritmem PRISM.


Informační systémy pro rozhodování tear-prod-rate = reduced: none tear-prod-rate = normal | astigmatism = no | | age = young: soft | | age = pre-presbyopic: soft | | age = presbyopic | | | spectacle-prescrip = myope: none | | | spectacle-prescrip = hypermetrope: soft | astigmatism = yes | | spectacle-prescrip = myope: hard | | spectacle-prescrip = hypermetrope | | | age = young: hard | | | age = pre-presbyopic: none | | | age = presbyopic: none

Rozhodovací strom vytvořený algoritmem ID3 popisuje problém rovněž zcela správně. Každá větev zároveň představuje jedno pravidlo.


Informační systémy pro rozhodování t-p-r normal

reduced

none

no

age young

soft

pre-pre

astig

pre

myope

soft spect myope

none

yes

hard

hyper

soft

spect

hyper

age young

hard

pre-pre

none

Překreslený rozhodovací strom ID3

pre

none


Informační systémy pro rozhodování Detailní popis demonstrovaných algoritmů:

PRISM algoritmus: J. Cendrowska (1987). PRISM: An algorithm for inducing modular rules. International Journal of Man-Machine Studies. 27(4):349-370. ID3 algoritmus: R. Quinlan (1986). Induction of decision trees. Machine Learning. 1(1):81-106.


Informační systémy pro rozhodování Alternativní algoritmus: Umělá neuronová síť se sigmoidálními přenosovými funkcemi neuronů (nelineární hranice oddělující třídy) trénovaná tzv. zpětným šířením chyb (backpropagation). Není zřejmé, jakou architekturu má síť mít. Lze zkusit různé architektury (pouze počet vstupních a výstupních jednotek je dán úlohou). Jako výsledek se vybere dle Occamova (resp. Ockhamova) pravidla architektura nejjednodušší, dává-li stejně dobré výsledky jako architektury složitější (tzv. Occamova břitva, Occam’s / Ockham’s razor):

Entia non sunt multiplicanda praeter necessitatem. (Počet věcí, které mají vysvětlovat jevy, nemá být zbytečně násobený.)








Informační systémy pro rozhodování Dolování z dat − data mining Metody strojového učení jsou prakticky zaměřené, využívají všech vhodných teorií a postupů včetně exaktní matematiky, pravděpodobnosti, umělé inteligence, přibližného usuzování, logiky, apod. Strojové učení nepředpokládá žádný filosofický přístup k termínu učení − jde o naučení se (zobecnění) znalosti z dat a informace, zejména induktivně, z příkladů. Algoritmy, metody, jejich kombinace, příprava dat, zpracování a interpretace výsledků většinou bývají dosti složité a vyžadují výkonné počítače (rychlý procesor, lépe více procesorů, a rozsáhlou paměť).


Informační systémy pro rozhodování Klasickým příkladem dolování znalosti je tzv. problém počasí a hry v tenis: Sledují se lidé, zda jdou či nejdou hrát tenis v závislosti na některých atributech popisujících počasí. Naměřené hodnoty a jejich kombinace nepokrývají veškeré možnosti. Idea je v zobecnění disponibilní informace tak, aby bylo možno předvídat, zda se půjde hrát či ne i pro kombinace hodnot, které během učení nebyly známy, a predikce má být co nejlepší, s minimální chybou. Disponibilní informaci ukazuje následující tabulka:


Informační systémy pro rozhodování předpověď

teplota

vlhkost

větrno hrát

slunečno slunečno zataženo deštivo deštivo deštivo zataženo slunečno slunečno deštivo slunečno zataženo zataženo deštivo

horko horko horko příjemně chladno chladno chladno příjemně chladno příjemně příjemně příjemně horko příjemně

vysoká vysoká vysoká vysoká normální normální normální vysoká normální normální normální vysoká normální vysoká

ne ano ne ne ne ano ano ne ne ne ano ano ne ano

ne ne ano ano ano ne ano ne ano ano ano ano ano ne

Počet možných kombinací hodnot je 36, známo je 14.

zataženo, horko, normální, ano: hrát = ano? hrát = ne?


Informační systémy pro rozhodování atribut teplota je pro trénovací data irelevantní vždy, když předpověď byla zataženo, se hrálo, takže na ostatních atributech nezáleželo

zataženo, horko, normální, ano: hrát = ano? hrát = ne?


Informační systémy pro rozhodování předpověď

teplota

vlhkost

větrno hrát



vysoká vysoká vysoká vysoká ? normální normální vysoká normální normální normální vysoká normální vysoká



Chybějící hodnota atributu vlhkost (původně = = normální).



Celkový počet instancí je opět 14: 3.00 2.00 7.54 1.46

neznámá (chybějící) hodnota nahrazena dle výskytu hodnot v jiných instancích: (7.54/1.0): 7.54 zařazeno do třídy správně, 1 instance chybně

strom je nyní odlišný:

normální

14.00

vysoká neúplná instance náleží částečně do více tříd


Informační systémy pro rozhodování Instance s chybějícími hodnotami přinášejí méně informace do zpracování, takže výsledek klasifikace má obecně vyšší chybovost. Při dostatečném množství trénovacích instancí lze ty neúplné ze zpracování vyřadit; jinak je nutno chybějící hodnoty nahradit pomocí např. pravděpodobnostního výpočtu. Lze také zavést umělou hodnotu missing a strom pak ukáže, kam vede větev při výskytu chybějící hodnoty určitého atributu, což může napovědět, do jaké míry chybějící hodnoty ovlivňují výsledek. Někdy lze atribut s chybějícími hodnotami vyřadit jako irelevantní i za cenu zvýšení chyby klasifikace.


Informační systémy pro rozhodování Entropie a rozhodovací stromy Odpovědi na dotazy v testovacích uzlech by měly dát co nejvíce informace, tj. odpovědi by měly být co nejužitečnější vzhledem k řešené úloze (např. rozdělení heterogenní množiny instancí na co nejhomogennější podmnožiny pro dosažení optimální klasifikace). Jedním z problémů při konstrukci rozhodovacího stromu je stanovení vhodných dotazů. K dobrým a praktickým možnostem při hledání dotazů patří využití entropie. Entropie je definována v teorii informace a lze ji využít k mnoha účelům, nejen pro rozhodovací stromy.


Informační systémy pro rozhodování Cílem klasifikace je přiřazení správné vlastnosti (tj. třídy) pro danou instanci (vzorek). Pro trénovací data jsou jejich vlastnosti známy, takže jsou známy odpovědi na možné dotazy — kvalitní dotazy mají odpovědi, které pro trénovací data vyvolají co nejmenší “překvapení”. Mírou “překvapení” je zde entropie, která ji měří pomocí pravděpodobnosti. S růstem pravděpodobnosti výskytu jevu klesá “překvapení” nad jeho výskytem, tj. je-li pravděpodobnost p = 1.0 pak lze daný jev očekávat zcela jistě. Podobně je tomu naopak pro p = 0.0, kdy také nevzniká překvapení. Překvapení (surprise) dvou nezávislých jevů s pravděpodobnostmi p a q: S(pq) = S(p) + S(q).


Informační systémy pro rozhodování Teorie informace, jejíž základy položil zejména Shannon [Shannon C. E., Weaver W. (1949) The Mathematical Theory of Communication. Univ. of Illinois Press], definuje funkci typu S(p) vztahem

S(p) = -logb p kde b je nějaký základ. Vyjadřujeme-li míru informace v jednotkách bit (binary digit), pak b = 2 (odpověď je buď ano nebo ne, např. zařazení instance do určité třídy). Entropie H(X) pro náhodnou proměnnou X je definována:

H X  =

∑n p n S  p n 

= −∑n p n log2 p n


Informační systémy pro rozhodování H  X  = −∑n p n log2 p n ≥ 0,

0 ≤ p ≤ 1

Proměnná X má možné hodnoty xn s pravděpodobnostmi

pn (kde n = 1, 2, 3, ...). Záporné znaménko poskytuje kladné hodnoty entropie: logaritmy z hodnot pravděpodobností jsou záporné. H

Průběh funkce entropie ukazuje graf. Odpověď na “dobrý dotaz” je co nejblíže 0 nebo 1. “Špatný dotaz” bude zařazovat instance víceméně náhodně.

0

maximální entropie

0.5

1

p


Informační systémy pro rozhodování Entropie H(p)

H(p) 1 0.9 0.8

H(p) = -p·log2 p - (1-p)·log2(1-p)

0.7 0.6 0.5 0.4 0.3 0.2 0.1

p

0 0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1


Informační systémy pro rozhodování Při konstrukci rozhodovacího stromu se tedy hledají testy v uzlech tak, aby odpověď na test poskytla co nevíce informace, tj. aby byla co nejmenší entropie. Počáteční heterogenní množina trénovacích instancí je na základě odpovědí na test rozdělena na homogennější podmnožiny, snižuje se neuspořádanost (“chaos”). Principem je výběr atributu, na jehož hodnoty se uzel ptá. Je nutno vyzkoušet všechny uvažované atributy, tj. zjistit, jakou poskytují entropii, a pak vybrat atribut s nejnižší entropií. Vznikne nová úroveň stromu (kořenem je počáteční množina trénovacích instancí), kterou lze rekursivně dále testovat. Konec generování stromu je dán nemožností dosažení nižší entropie (listy).


Informační systémy pro rozhodování Příklad vytvoření rozhodovacího stromu pro výše uvedený problém počasí a hry v tenis: předpověď

teplota

vlhkost

větrno hrát



vysoká vysoká vysoká vysoká normální normální normální vysoká normální normální normální vysoká normální vysoká




Informační systémy pro rozhodování Který atribut (předpověď, teplota, vlhkost, větrno) dá jako

odpověď nejlepší rozdělení do homogennějších podmnožin? Postupně se spočítají entropie; např. pro předpověď: 9x se hrálo, 5x se nehrálo (9+5=14 trénovacích instancí). Pravděpodobnosti a posteriori pro ano jsou:

o

ano ano ano ano

deštiv

ano ano ne ne ne

zataženo

sluneč n

o

předpověď = ?

ano ano ano ne ne

2/9 + 4/9 + 3/9 = 1.0, resp. pro ne: 3/5 + 0/5 + 2/5 = 1.0. Entropie je mírou neuspořádanosti množiny (dokonalá uspořádanost je dána hodnotou entropie = 1 nebo 0). Protože test zde rozdělí množinu na 3 podmnožiny, které obecně mohou mít různé neuspořádanosti, tak se stanoví průměrná neuspořádanost na konci větví vedoucích z testovacího uzlu. Neuspořádanost množiny každé větve se váhuje rozměrem množiny relativně vzhledem k celkovému rozměru množin ve všech větvích. Váha je tedy počet příkladů nb ve větvi b ku celkovému počtu příkladů nt ve všech větvích: nb / nt .


Informační systémy pro rozhodování Průměrná neuspořádanost:

H avg =

H avg = kde

nb

∑b n

[

∑b

× neuspořádanost větve b 

t

nb nt

] [ ×

n bc

∑c − n

b

log2

n bc nb

]

nb ... počet příkladů ve větvi b nt ... celkový počet příkladů ve všech větvích nbc ... celkový počet příkladů ve větvi b třídy c

(Vzorec není “posvátný”, v praxi se osvědčil; lze samozřejmě použít i jiný vhodný, dává-li dobré výsledky.)


Informační systémy pro rozhodování Zpátky k příkladu “hrát tenis či ne?”: Entropie pro předpověď:

deštiv o

zataženo

sluneč n

o

předpověď = ?

Havg = [- 5/14 (2/9 log22/9 + 3/5 log23/5)] + [- 4/14 (4/9 log24/9 + 0/5 log20/5)] + [- 5/14 (3/9 log23/9 + 2/5 log22/5)] = 0.8592 (Pozn.: 0 logb 0 = 0 [def.]; logb x = log10 x / log10 b)

ano ano ne ne ne

ano ano ano ano

ano ano ano ne ne

Z výsledku je vidět, že zvolený test předpověď snížil do určité míry původní neuspořádanost (jedna ze vzniklých podmnožin, zataženo, je již zcela homogenní a není nutno ji už dále nijak dělit; podmnožiny ve větvi slunečno a deštivo jsou stále ještě heterogenní, takže se dále bude hledat možnost jejich rozdělení).

Otázka nyní je, zda jiný atribut nemůže dát ještě lepší výsledek, bude-li použit jako test.


Informační systémy pro rozhodování Další tři atributy včetně větvení a hodnot:

an o

horko

ne

ano ano ano ne ne ne ne

větrno = ?

lní

ano ano ano ne

normá

ano ano ano ano ne ne

o chladn

příjemně

ano ano ne ne

vysoká

vlhkost = ?

teplota = ?

ano ano ano ano ano ano ne

ano ano ano ano ano ano ne ne

ano ano ano ne ne ne


Informační systémy pro rozhodování Spojité a diskrétní atributy Atributy popisující objekty mají velmi často číselný charakter (nejen binární či nominální). Obecně mohou být numerické atributy definovány na spojité reálné ose. Některé algoritmy jsou schopny zcela přirozeně pracovat i s číselnými atributy, část z nich pouze s numerickými hodnotami (např. metoda nejbližšího souseda k–NN využívající Eukleidovy vzdálenosti, nebo algoritmy založené na regresních technikách, např. regresní strom M5P, kde i klasifikační třída je numerická). V takových případech je nutno převést data buď ze spojitého universa na diskrétní, resp. naopak.


Informační systémy pro rozhodování Popisovaný typ rozhodovacích stromů vychází z původního algoritmu pro indukci rozhodovacího stromu ID3 (Interactive Dichotomizer No. 3), který umí zpracovat pouze nominální atributy. [Vysoká praktická úspěšnost aplikace ID3 vedla k rozšíření na atributy numerické. Nejznámější je c4.5 Rosse Quinlana, včetně následné komerční verze c5/See5 *) pro operační systémy Unix/Linux/Windows]. Princip rozšíření je v tzv. diskretizaci. Diskretizaci lze provést mnoha různými metodami, včetně zcela automatické (unsupervised) nebo řízené (supervised). Zpět k problému počasí a hry v tenis, tentokrát s atributy teplota avlhkost numerickými: *) Demonstrační, plně funkční verzi c5/See5 s omezením na počet příkladů lze získat zdarma na URL (2007): http://rulequest.com


Informační systémy pro rozhodování předpověď 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.


teplota

vlhkost

větrno

hrát

85 80 83 70 68 65 64 72 69 75 75 72 81 71

85 90 86 96 80 70 65 95 70 80 70 90 75 91



Diskretizace musí rozdělit číselný interval, považovaný za spojitý, na soubor podintervalů. Každý vzniklý podinterval pak hraje roli nominální hodnoty.

Pozn.: Teplota je ve stupních Farenheita: 32°F ... 212°F odpovídá 0°C ... 100°C. Vlhkost je relativní v %.


Informační systémy pro rozhodování teplota: 85, 80, 83, 70, 68, 65, 64, 72, 69, 75, 75, 72, 81, 71 vlhkost: 85, 90, 86, 96, 80, 70, 65, 95, 70, 80, 70, 90, 75, 91

Některé z možných a používaných metod diskretizace: a) Rozdělení na určitý počet podintervalů stejné délky (nevýhoda může být ve velmi různém počtu hodnot v každém intervalu). b) Rozdělení na podintervaly, kde každý obsahuje (přibližně) stejný počet hodnot (v praxi se osvědčuje – jako heuristika se pro stanovení počtu intervalů často používá druhá odmocnina z celkového počtu hodnot daného atributu; intervaly ovšem mohou mít velmi různou délku). c) Rozdělení na podintervaly pomocí entropie, kde každý podinterval obsahuje (pokud možno) pouze hodnoty patřící do jediné třídy (diskretizace řízená tréninkovými daty).



a)

b)

c)


Informační systémy pro rozhodování První krok diskretizace spočívá v seřazení hodnot: teplota: 64, 65, 68, 69, 70, 71, 72, 72, 75, 75, 80, 81, 83, 85

chladno

příjemně

horko

vlhkost: 65, 70, 70, 70, 75, 80, 80, 85, 86, 90, 90, 91, 95, 96

normální

vysoká

Tento krok bývá z hlediska výpočetní složitosti obvykle nejnáročnější, ale jednou setříděné hodnoty se využijí i pro rekursivní generování podstromů na dalších úrovních stromu, takže stačí setřídit pouze jedenkrát. V dalším kroku se jednou z možných metod hledají dělící body mezi hodnotami, tj. hranice podintervalů.


Informační systémy pro rozhodování Původní nominální a jim odpovídající numerická data: teplota 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.


85 80 83 70 68 65 64 72 69 75 75 72 81 71

vlhkost vysoká vysoká vysoká vysoká normální normální normální vysoká normální normální normální vysoká normální vysoká

85 90 86 96 80 70 65 95 70 80 70 90 75 91

Postupně se musí (do značné míry “hrubou silou”) zkoušet, která hranice mezi intervaly dá nejmenší entropii. Proto jsou úlohy s numerickými daty výpočetně složitější než úlohy s daty nominálními. V realitě však jsou numerické atributy poměrně běžné, obvykle doprovázeny atributy binárními i nominálními (smíšená reprezentace).


Informační systémy pro rozhodování Výsledek entropické diskretizace atributu teplota:

64

65

ano ne

68

69

70

71

72

75

ano

ano

ano

ne ne/ano ano/ /ano

80

81

83

85

ne

ano ano ne

Je teoreticky dokázáno, že metoda minimalizace entropie při diskretizaci nikdy neumístí hranici mezi intervaly tak, aby byly odděleny dvě instance téže třídy (pozn.: zde mezi 72 a 75 je hranice, která odděluje ano/ne od ano/ano, tj. nikoliv dvě instance téže třídy). To vede k urychlení výpočtu: je třeba testovat hranice pouze mezi instancemi z různých tříd (takže ne 68/69, 69/70, apod.).


Informační systémy pro rozhodování Další možné diskretizační metody: ● Nikoliv “shora dolů”, jak ukázáno, ale naopak “zdola nahoru”, tj. napřed každá jednotlivá instance je oddělena a pak se hledá, zda ji lze spojit se sousední. ● Počítání chyb, ke kterým dojde při predikci pro různé diskretizace (hrozí degenerace, že každá instance bude prohlášena za interval; je nutno předem omezit počet intervalů). ● Metoda “hrubou silou” vyzkoušet všechny možnosti je exponenciálně náročná (počet intervalů k je v exponentu). ● Dynamické programování (způsob optimalizace) rozdělí N instancí do k intervalů v čase úměrném kN 2.


Informační systémy pro rozhodování Převod diskrétních atributů na numerické: Některé algoritmy vyžadují pouze numerické hodnoty, takže je zapotřebí “opačný” převod. Atributy s nominálními hodnotami předpokládají různost dvou nominálních hodnot jako nenulovou vzdálenost a stejnost jako vzdálenost nulovou. Je-li k různých nominálních hodnot, jsou uměle nahrazeny binárními hodnotami 0/1, např. atribut barva může nabývat tří hodnot (modrá, zelená, červená), takže tento atribut je převeden na tři binární atributy: modrý, zelený, červený, a modrý objekt pak má odpovídající hodnoty nových umělých atributů 1, 0, 0. Pak lze počítat např. vzdálenosti mezi objekty, kde nulová vzdálenost znamená identitu (dva stejné objekty), apod. Seřaditelné nominální hodnoty lze nahradit celými čísly.


Informační systémy pro rozhodování Trénování a testování Pro odhad chyby klasifikátoru na budoucích datech, která nebyla k dispozici během trénování, je nutno klasifikátor otestovat. K tomu se buď použijí nějak vyčleněná data, která se tréninku nezúčastní (testovací data), nebo se dá využít části tréninkových dat tím, že se použijí jako testovací, což ale vede ke snížení počtu trénovacích příkladů a dále k vyřazení určitých příkladů; negativním důsledkem může být zhoršený trénink a nižší kvalita klasifikátoru. Existují metody, kdy lze použít pro trénink všechny příklady a zároveň klasifikátor týmiž daty otestovat. Rozšířená (ale ne jediná) je např. metoda krosvalidace.


Informační systémy pro rozhodování Krosvalidace (cross-validation) Tato metoda rozdělí náhodným výběrem data na k pokud možno stejně velkých částí, např. na 10 podmnožin ( k může záviset na celkovém množství trénovacích instancí). Pak proběhne 10 tréninků tak, že v každém z nich se použije 9 podmnožin jako trénovací a 1 jako testovací. Každý trénink používá pro testování různou z podmnožin, takže postupně všechna data jsou využita na trénování a testování. Každé testování zjistí chybu klasifikátoru, a výsledná očekávaná chyba je průměrem. Tato chyba je tzv. pesimistická, protože byla odhadnuta na menším počtu trénovacích příkladů (zde např. na 90 %). Výsledný klasifikátor se pak natrénuje pomocí všech příkladů.


Informační systémy pro rozhodování Počet podmnožin může být i jiný, 10 je prakticky osvědčená heuristika. Extrémem je rozdělení trénovací množiny na počet podmnožin odpovídající počtu trénovacích příkladů n. Pak se jedná o tzv. krosvalidaci 1-z-n, která má výhodu v trénování téměř všemi instancemi v každém z n trénovacích kroků. Nevýhodou je úplná ztráta rozložení hodnot [které je při obyčejné krosvalidaci (náhodným výběrem) do určité míry v podmnožinách zachováno]. Pro odhad chyby lze také použít obě metody a výsledky porovnat – jsou-li např. chyby všech jednotlivých kroků velmi podobné a navíc jsou podobné i mezi krosvalidací obyčejnou a 1-z-n, pak je systém datově robustní.


Informační systémy pro rozhodování Protože výběr prvků do podmnožin se provádí náhodně, může být i výsledek náhodně velmi špatný nebo náhodně příliš dobrý. Generátor (pseudo)náhodných čísel potřebuje na začátek tzv. násadu, z níž odvozuje posloupnost generovaných čísel s rovnoměrným rozložením. Takových posloupností lze vytvořit mnoho a předem není jasné, která povede k jakému výsledku. Proto je velmi vhodné celý proces krosvalidace zopakovat vícekrát, pokaždé s jinak provedeným náhodným výběrem. Strojové učení má jako empirický standard tzv. desetinásobně opakovanou krosvalidaci s dělením na 10 částí (10-times 10-fold crossvalidation). Lze ovšem použít i jiné hodnoty – odpověď dají experimenty a jejich pečlivé vyhodnocení.


Informační systémy pro rozhodování Bootstrap Bootstrap je statistická metoda založená na výběru s vracením. Znamená to, že tímto výběrem vzniklá sada příkladů může obsahovat některé příklady vícekrát (takže nelze hovořit o množině). Myšlenka vychází z toho, že když některé příklady jsou náhodně vybrány vícekrát, jiné nejsou vybrány nikdy – a právě tyto nevybrané příklady pak vytvoří testovací množinu.


Informační systémy pro rozhodování Data, mající n příkladů, jsou podrobena n výběrům s vracením. Šance, že nějaký příklad nebude vybrán v žádném z n pokusů (výběr musí být náhodný), je založena na tom, že pravděpodobnost být vybrán je 1/n a nebýt vybrán 1–1/n. Opakuje-li se výběr n-krát, pak vynásobením pravděpodobností vznikne pravděpodobnostní odhad, kolikrát nedojde k výběru: (1–1/n) = e n

-1

. = 0.3678794412... (pro n

∞),

kde e je základ přirozených logaritmů. Např. pro n = 1000 . 1000 pokusů je (1–1/1000) = 0.3676954248... = 36.77 %.


Informační systémy pro rozhodování Odhad stanovuje, že v testovací množině bude cca 36.8 % příkladů, zatímco v trénovací množině zůstane 63.2 %, takže originální data jsou statisticky oprávněně rozdělena přibližně na 2/3 trénovacích a 1/3 testovacích. Někdy se této metodě výběru říká 0.632 bootstrap. Samozřejmě, že ani trénovací ani testovací množina pak neobsahují opakované příklady.


Informační systémy pro rozhodování Vzhledem k náhodnosti výběru mohou být data rozdělena i příliš “dobře” nebo “příliš špatně”, takže testovací část vůči trénovací může poskytnout neoprávněně malou či velkou chybu [ale míra “(ne)oprávněnosti” není známá, pouze se statististicky odhaduje]. Aby bylo možno se vyhnout výsledkům ovlivněných náhodností negativně, je vhodné trénování a testování provést opakovaně několikát, pokaždé s novým náhodným rozdělením výchozí datové množiny. Je nutno dát pozor na to, aby generátor náhodných čísel, používaných k výběru, vždy vyprodukoval jinou posloupnost hodnot s rovnoměrným rozdělením. To zajišťuje tzv. násada (seed).


Informační systémy pro rozhodování Každé testování pak dá obecně více či méně odlišnou odhadnutou budoucí chybu a výsledná očekávaná chyba se spočítá jako průměr (platí i pro krosvalidaci). Rozptyl průměrně očekávané chyby poskytuje informaci o stabilitě algoritmu vůči složení dat. Pro dosažení dobré stability (robustnosti algoritmu) je ideální co nejmenší rozptyl. To především ovlivňují samotná data, ale různé algoritmy mohou dát různé výsledky i z tohoto hlediska, přestože průměrná chyba může být téměř stejná. Výsledky testování jsou tedy dalším hlediskem pro výběr algoritmu i z hlediska robustnosti.


Informační systémy pro rozhodování Prořezávání (pruning) Znalost je zobecněná informace, a strom je jednou z možných reprezentací znalosti. Proto by měl být dostatečně obecný, tj. ne být dokonalý na tréninkových datech – velmi často může velice chybovat na testovacích datech, i když na tréninkových dosahuje nízkých chyb. Ukazuje se, že k lepším výsledkům na testovacích datech přispívá tzv. prořezávání po celkovém vytvoření stromu. Strom se nenechá tak “rozkošatět”. Jednou z metod je tzv. náhrada podstromu, kdy podstrom je nahrazen listem. Tato operace zvýší chybu na trénovacích datech, ale pro testovací data je chyba nižší než před náhradou.


Informační systémy pro rozhodování Příčina je zřejmá např. z extrémního případu, kdy mohou tréninkem vzniknout listy obsahující jedinou instanci; to je špatná generalizace, protože ideální je, aby každý list pokrýval co nejvíce příkladů. Obsahují-li tréninkové příklady šum, pak jednoprvkové množiny v listech mohou vést k chybné klasifikaci řízené spíše šumem než zobecněním souboru hodnot relevantních atributů. Takové přetrénování hrozí nejen při entropické tvorbě rozhodovacích stromů, ale i pro mnoho jiných algoritmů. U stromů lze zabránit přetrénování prořezáváním.


Informační systémy pro rozhodování Existují dva postupy prořezávání: ● Shora dolů (pre-pruning) ● Zdola nahoru (post-pruning) Pre-pruning zastaví růst větve, když začne poskytovat nespolehlivou informaci. Post-pruning nechá strom zcela vyrůst a rozkošatět, a pak zpět směrem od listů ruší nespolehlivé části. V praxi se dává přednost metodě post-pruning (zdola nahoru), protože pre-pruning mívá tendenci zastavit růst větve příliš brzo. Pre-pruning je ale výpočetně rychlejší metoda než post-pruning.


Informační systémy pro rozhodování Pre-pruning využívá test statistického významu propojení atributu s klasifikační třídou pro konkrétní uzel. Pro testování se nejčastěji používá χ2 (chí-kvadrát), což je test vycházející z frekvencí hodnot, zde vzhledem ke třídě. Předčasné zastavení růstu lze demonstrovat na klasickém případu parity (neboli XOR-problému): id x1 x2 c 1 2 3 4

0 0 1 1

0 1 0 1

0 1 1 0

Ani jeden z individuálních atributů x1 a x2 nevykazuje žádný významný vztah ke třídě c. Struktura je vidět pouze na zcela vyrostlém stromě, avšak pre-pruning a χ2 zastaví růst hned v kořeni – zcela degenerovaný strom. Přesto ale lze pro XOR korektní strom vytvořit.


Informační systémy pro rozhodování XOR-problém: Obrázek ukazuje dvě zcela správná řešení. XOR je pro řadu algoritmů obtížný typ id x1 x2 c problému. V praxi se však vyskytuje poměrně zřídka. XOR je typická ukázka případu, kdy 1 0 0 0 jednotlivé atributy nemají prediktivní význam, 2 0 1 1 ale jejich kombinace ano. 3 1 0 1 4 1 1 0

0 0 0

x2

x1

0

1

1

0

1

1

x2

1

0

0

0

x1

x2

1

1

0

1

1

x1

1 0


Informační systémy pro rozhodování Post-pruning vychází z následujícího principu: zcela homogenní listy vzniklé ze společného uzlu se zpětně uměle sloučí s rodičovským uzlem a vytvoří se tak list, který už není homogenní (má entropii > 0). Tím se zvýší chyba stromu na trénovacích příkladech, ale ta není rozhodující. Zato však může lépe generalizovat, což je podstatné pro klasifikaci testovacích datových příkladů. Úvaha platí i pro listy pokrývající více příkladů, a nemusí být homogenní.

Zda nahradit či nenahradit podstrom listem, na to odpoví odhad chyby na testovacích datech (vždy po náhradě je nutno překlasifikovat příklady použité pro vytvoření neprořezaného stromu). Je-li po prořezání chyba na testovacích datech nižší, pak je doporučena náhrada listem .


Informační systémy pro rozhodování Následující příklad demonstruje post-pruning na reálných (veřejně přístupných) vzorcích z vyjednávání o kolektivních smlouvách a podmínkách v kanadském průmyslu (listopad 1998). Data jsou popsána 57 příklady a 16 atributy a jsou k dispozici (spolu s mnoha dalšími z nejrůznějších oborů) na URL (rok 2007): http://www.ics.uci.edu/~mlearn/MLRepository.html

Následující obrázek ukazuje vygenerovaný strom (ne úplný), v němž lze postupně zkoušet náhradu podstromů listy. Každý pokus vyžaduje po stanovení místa prořezání zjistit chybu na trénovacích i testovacích datech. Zvýšení trénovací chyby se snížením testovací chyby (ve srovnání se stromem bez náhrady podstromu) určí, že náhrada listem je správná.


Informační systémy pro rozhodování Post-pruning pracuje tak, že napřed nechá strom zcela vyrůst, čímž jsou zachyceny i kombinace mezi atributy. Poté hledá, zda lze nějaké podstromy nahradit listem.

bad

bad


Informační systémy pro rozhodování Dva podstromy (viz předchozí obrázek) byly postupně nahrazeny listem bad. Zeleně ohraničený podstrom listem bad, a pak modře ohraničený podstrom rovněž listem bad. Strom je značně zjednodušen, lépe generalizuje na testovacích datech (na trénovacích má o něco vyšší chybu).


Informační systémy pro rozhodování Další obrázky ukazují výsledky dosažené algoritmem J48 (c4.8) systému WEKA (labor-negotiation data jsou součástí WEKA jako jeden z příkladů, labor.arff). Lze srovnat různé výsledky dosažené nad týmiž daty pro různé koeficienty CF (0.1, 0.25, 0.5,1.0), kde menší hodnota znamená větší prořezání stromu. Sleduje-li se chyba testování pomocí krosvalidace 10 (implicitně nabízená hodnota), tak lze pozorovat, že testovací chyba klesá až do CF = 0.5 (a platí to i pro chybu trénovací). Výsledný strom by měl být vybrán tak, aby dosahoval minimální předpovězené testovací chyby a aby nebyl příliš prořezán. Lepší je mít pro testování oddělená data, krosvalidace zde snižuje počet trénovacích.


Informační systémy pro rozhodování CF = 0.1

CF = 0.25 (implicitní hodnota daná statistikou)

Faktor jistoty (confidence factor, CF ) je parametr ovlivňující prořezávání. Nižší hodnota znamená větší prořezávání a naopak. Parametr zadává uživatel, implicitně platí CF = 0.25.



CF = 0.5



CF = 1.0 Maximální jistota poskytované informace vede k neprořezanému stromu. Může i nemusí snižovat generalizaci – závisí na konkrétní aplikaci.



Přehled rozložení hodnot pro atributy dat labor-negotiation


Informační systémy pro rozhodování Výše popisovaný problém XOR dává při použití J48/c4.8 degenerovaný strom pro každou hodnotu CF (první z následujících tří obrázků). Modernější (avšak komerční) verze c5/See5 pro vhodné nastavení parametrů vygeneruje správný strom. Je nutno zadat minimální pruning (pro c5 je to hodnota 99 % což odpovídá 1.0 či 0.99 pro J48/c4.8). Vzhledem k aplikaci je nutno povolit, aby v listech mohl být i pouze jeden příklad (implicitně je nastaveno minimální množství instancí pokrytých listem na 2). Implicitní hodnoty c5/See5 zde dávají špatný výsledek.



Zdegenerovaný strom J48 (c4.8) pro XOR problém

list (kořen) pokrývá všechny 4 případy, z toho 2 chybně: 4/2, výsledná chyba je 50 %


Informační systémy pro rozhodování Komerční verze c4.5/c4.8 pod názvem c5/See5 může dát správný výsledek, má-li nastaveny správně parametry:

Je nutno omezit pruning a povolit jedinou instanci na list (dáno konkrétním problémem).


Informační systémy pro rozhodování Implicitní parametry dávají ovšem chybný výsledek:

Informační systémy pro podporu rozhodování

Recommend Documents