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í 3 Jan Žižka, Naděžda Chalupová Ústav informatiky PEF Mendelova universita v Brně


Informační systémy pro rozhodování Nejbližší sousedi k–NN Algoritmus k-nejbližších sousedů (k-nearest neighbors) patří k základním algoritmům dolování z dat. Jeho princip je velmi jednoduchý: Tréninkové příklady jsou uloženy do databáze. Každý příklad je popsán atributy, jejichž hodnoty jsou považovány za souřadnice v prostoru, v němž tedy určují polohu příkladu jako vícerozměrného bodu (resp. vektoru). Příklady mají své zařazení do tříd známé. Objeví-li se případ, jehož příslušnost do některé ze tříd není známá, hledá se jeho nejbližší, “nejpodobnější” soused (nebo k sousedů), a neznámý případ se zařadí do stejné třídy.


Informační systémy pro rozhodování Pokud je k >1, tj. neznámý případ se porovnává s více než jedním sousedem, pak rozhoduje o zařazení do příslušné třídy většina. Blízkost je zde ekvivalentní podobnosti, takže se vlastně hledá k nejpodobnějších případů. Kolik sousedů se má použít, to nelze předem říci, optimální počet se hledá experimentálně. Je-li počet sousedů velký, pak jsou asi příklady značně ovlivněny šumem. k-NN je algoritmus citlivý na šum, irelevantní atributy a výjimky. Data bez šumu, výjimek a pouze s relevantními atributy však lze tímto postupem zpracovávat velmi úspěšně.


Informační systémy pro rozhodování Obecně je výhodné mít uložen velký počet příkladů, protože pak je problém dobře popsán. Na druhé straně však se musí počítat velké množství vzdáleností vůči neznámému případu, což je výpočetně náročné, zejména pro mnoharozměrné prostory. Vzdálenost l mezi dvěma body (1) a (2) lze měřit různě. Obvyklá je vzdálenost Eukleidova (platná v nadrovině): 2 2 1 2 2 1 2 2 l =   a 1 − a   a − a  ... a − a 1 1 2 2 m m  =



m

2 2

∑  a i −a i  , 1

i =1

kde m je počet atributů, ai (1) jsou souřadnice prvního bodu,

ai(2) souřadnice druhého bodu. Eukleidova vzdálenost (neboli tzv. L2 norma) předpokládá, že v rovině se lze pohybovat po libovolné přímce (i šikmé).


Informační systémy pro rozhodování Pokud je pohyb omezen jen na přímky rovnoběžné s osami, pak se používá tzv. Manhattanská vzdálenost (název inspirován vzájemně rovnoběžnými a kolmými ulicemi vedoucími ze severu na jih a z východu na západ ve stejnojmenné čtvrti města New York): m

l = ∑ ∣ a −a i =1

1 i

∣

2 i

,

tj. součet vzdáleností (absolutních hodnot z rozdílů) mezi souřadnicemi obou bodů na jednotlivých osách ( L1 norma).


Informační systémy pro rozhodování Používají se i další typy vzdáleností, např. vycházející z Mahalanobisova vztahu založeného na vzdálenosti mezi vektorem středu μ a vektorem příkladu x :

r 2 =  x −t −1  x − , kde (x – μ)t je transponovaný vektor a Ψ matice kovariance.

–1

je inverzní

Znamená to, že podobné příklady leží uvnitř hyperelipsoidu, jehož osy uvedený vztah určuje.


Informační systémy pro rozhodování Podobnost mezi vektory se často určuje pomocí jejich vzájemného úhlu α, resp. cos(α), kde hodnota = 1 znamená totožnost a 0 odlišnost, a hodnoty uvnitř jednotkového intervalu pak různou míru podobnosti. Tato metoda se uplatňuje např. při srovnávání podobnosti textových dokumentů, kde jednotlivé souřadnice jsou dány konkrétními slovy jako hodnotami atributů. Podobnost se počítá dle vztahu:

xty t cos  = , kde ∥v ∥=  v v . ∥x ∥∥y ∥ Typickým problémem je, že nelze spolehlivě předpovědět, který způsob měření vzdáleností je pro danou úlohu správný. Eukleidova vzdálenost poskytuje dobré výsledky velmi často a používá se jako základní východisko, nebrání-li tomu nic.


Informační systémy pro rozhodování Jsou-li hodnoty atributů nominální nebo binární, podobnost mezi vektory se často určuje Hammingovou vzdáleností dH , která poskytuje číslo vyjadřující v kolika atributech se mezi sebou vzory liší. Pro dH = 0 platí, že vzory jsou identické (je mezi nimi nulová vzdálenost).

Obrázek ilustruje vzdálenost mezi dvěma binárními vektory:

0 0

1 0

1 1

0 0

Vzdálenost je zde dH = 4.

1 1

0 1

0 1

1 1

0 0

0 1


Informační systémy pro rozhodování U k-NN může nastat potíž tehdy, jsou-li měřítka na osách různá; např. výška v mm a váha v kg. Problém se řeší normalizací do intervalu (0.0, 1.0):

ai =

v i −min  v i  max  v i − min  v i 

,

kde vi je skutečná hodnota i-tého atributu, a maximální

resp. minimální hodnota je určena ze všech trénovacích dat. Pro nominální atributy se použije 0, jsou-li hodnoty atributu stejné a 1, jsou-li různé; z toho plyne, že není zapotřebí změna měřítka na ose.


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

Ilustrace možného vlivu normalizace měřítka os na nalezení nejbližšího souseda: původní rozsah hodnot stanovil jako vzdálenější , normalizace určuje naopak jako vzdálenější .

1

0

0

0.01

0

0

1


Informační systémy pro rozhodování Při hledání více (k > 1) podobných sousedů lze v případě potřeby uplatnit i požadavek, aby větší vliv na kategorizaci měli bližší (podobnější) sousedé než sousedé vzdálenější (nestejně velká platnost hlasu při hlasování). Toho lze dosáhnout váhováním dle vzdálenosti, kde váhy se počítají z převrácených hodnot vzdáleností mezi klasifikovaným bodem a jeho k sousedy, takže vzdálenější příklady poskytují nižší váhu. Takto lze kompenzovat hlasovací převahu méně podobných (vzdálenějších) tréninkových příkladů vůči podobnějším (bližším), které mohou nakonec převážit, i když jsou v menšině. Při přesné shodě, kdy vzdálenost = 0, se klasifikovanému případu prostě přiřadí třída tréninkové instance.



? 11-NN

Klasifikovaný případ, označený černou hvězdičkou, může být buď červené nebo bílé kolečko. Pro 1-NN je zařazen k bílým kolečkům.

1-NN 5-NN

Pro 5-NN k červeným (hlasování 3:2). Pro 11-NN opět k bílým kolečkům (6:5). Záleží tedy na vhodně zvoleném k.


Informační systémy pro rozhodování Příklad demonstruje typickou potíž: algoritmus je jednoduchý a velmi efektivní, ale potřebuje mít vzhledem k aplikaci dobře zadaný parametr k a způsob měření vzdálenosti (tj.podobnosti) za předpokladu neexistence šumu a irelevantních atributů. Existuje oblast, zvaná Instance Based Learning (IBL), která je obecnější (a zahrnuje popsaný k-NN) a která obsahuje modifikace nejbližšího souseda odstraňující řadu nedostatků. Popsaný k-NN je tzv. IB1 (instance-based learning No. 1). Jednoduchou modifikací lze snížit jeho vysokou paměťovou náročnost, je-li k dispozici dostatečné množství trénovacích příkladů (IB2):


Informační systémy pro rozhodování IB2 pracuje tak, že sleduje, zda doposud v databázi uložené tréninkové příklady jsou schopny správně klasifikovat další předkládaný tréninkový případ. Pokud ano, pak ten další příklad už není zapotřebí; pokud ne, je přidán do databáze. Cenou za obvykle poměrně velkou úsporu paměti bývá o něco vyšší klasifikační chyba na testovacích příkladech, protože je použito méně vzorů. V praxi to může být zcela přijatelné, pokud se tak vyřeší velmi obtížný paměťový problém. Navíc menší množství uložených vzorů sníží výpočtovou náročnost i z časového hlediska.

IB3 se snaží odstranit zašuměné instance tak, že se stanoví práh odmítnutí instance. Předpokládá se, že doposud uložené instance jsou spolehlivými klasifikátory.


Informační systémy pro rozhodování Významový test rozhoduje o tom, zda instance je zašuměná nebo přijatelná. Přijatelná je tehdy, když přesnost její klasifikace je statisticky významně větší než její pozorovaná frekvence ve třídě (z frekvence se počítá pravděpodobnost aposteriori). V opačném případě je instance vyřazena z databáze. Nedostatkem je, že takto nelze odlišit zašuměné instance od výjimek, které by bylo vhodné mít v databázi, ale které se jeví jako šum (mají nízkou frekvenci).

IB4 je rozšířením IB3 tím, že nepředpokládá stejný význam všech atributů (irelevantní atributy). Význam atributu je dán nastavením jeho váhy. Atributy, které při učení (testování) přispívají ke správné klasifikaci více, získávají vyšší váhu.


Informační systémy pro rozhodování Problém náročnosti výpočtů vzdáleností neznámého případu vůči všem uloženým příkladům se často řeší pomocí tzv. K-D stromu (K-dimensionální strom). Pro dvourozměrný prostor (2D) se na ose x1 rozdělí existující interval na dvě části (např. mediánem, aby strom byl pokud možno vyvážený). Pak se pracuje už jen s tou částí, v níž leží neznámý případ; příklady z druhé části jsou vzdálenější, proto nebudou využity. V dalším kroku se totéž provede na ose x2, takže odpadne řada příkladů pro výpočet vzdáleností. Pak následuje znovu x1, x2, x1, x2, …, a to tak dlouho, dokud

stromová reprezentace uvedeného postupu má v příslušné větvi testovací uzly. Neznámý případ nakonec dojde do listu, kde je odpověď na jeho umístění do příslušné třídy.


Informační systémy pro rozhodování Princip postupného dělení intervalů na dvě části mediánem ukazuje obrázek. Pro faktor větvení b = 2 a hloubku d má strom 2d listů. Počet testů ve stromu pak není úměrný k, ale jen log2k (výrazné snížení výpočetní složitosti): 2d ≥ k, z čehož plyne počet porovnání ≈ d = log2k (průchod d uzly pouze v jedné větvi K-D stromu). x2

max

medián medián

min min

medián

medián

max

x1




Informační systémy pro rozhodování Uvedená metoda K-D stromu dělí prostor do podprostorů majících tvar hyperkvádrů (vícerozměrných kvádrů). Rovné, s osami rovnoběžné stěny hyperkvádrů mohou však být problematické, zejména v oblasti, kde jsou rohy kvádrů: obrázek ukazuje, že i nevelký posun dále od způsobí přesah zkoumané oblasti do dalšího hyperkvádru (označeno žlutě), i když přímo v přesahu nejsou žádné trénovací instance – musely by se (zbytečně) počítat další vzdálenosti. Kromě toho je neznámé instanci blíže než .


Informační systémy pro rozhodování Řešením je modernější přístup, využívající tzv. hypersféry (obecně mnoharozměrné elipsoidy) místo hyperkvádrů. Na nich jsou založeny tzv. ball trees (koulovité stromy); užívá se též název metric trees (metrické stromy). Metrika [vzdálenost D (a,b) mezi bodem a a b] má obecně tyto čtyři vlastnosti: ● ● ● ●

D (a,b) D (a,b) D (a,b) D (a,b)

≥ = = +

0 (vzdálenost je vždy kladná), 0 jedině tehdy, když a = b (reflexivita), D (b,a) (symetrie), a D (b,c) ≥ D (a,c) (trojúhelníková nerovnost).

Lze snadno dokázat, že např. Eukleidova i Manhattanská vzdálenost je metrika v m-rozměrném prostoru.


Informační systémy pro rozhodování Algoritmus k-NN se dá použít i k aproximaci spojitých funkcí, čili k regresi. Např. jednoduchá aproximace fˆ reálné funkce f: R n R: k

f  x q  

∑i =1 f  x i  k

,

tj. střední hodnota z k známých hodnot funkce v bodech xi se dosadí za hledanou funkční hodnotu v bodě xq .

Pozn.: k-NN se aplikuje i na složitější aproximace, např. lokálně váhovánou regresi.


Informační systémy pro rozhodování Voronoi diagram: obrázek ukazuje rozhodovací 2D prostor indukovaný 1-NN algoritmem. Jde o konvexní polygon kolem každé trénovací instance, který indikuje jí nejbližší oblast.


Informační systémy pro rozhodování Obrázek ukazuje 16 trénovacích instancí v 2D prostoru. Instance jsou pokryty překrývajícími se kruhy. Ve spodní části je nakreslena odpovídající stromová struktura se vztahy mezi uzly a kruhy. Každý uzel reprezentuje kruh. Ve stromu jsou do uzlů zapsány počty bodů, které jsou uzlem (kruhem) pokryty. Body z překrývajících se částí jsou zařazeny pouze do jedné kruhové oblasti, ne do více.


Informační systémy pro rozhodování Uzly ve skutečnosti neobsahují počty jim náležejících bodů, ale středy a poloměry příslušných hyperkruhů. Platí to i pro listy stromu. Počítají se vzdálenosti mezi středy kruhů a neznámým vzorkem; berou se do úvahy kruhy na stejné úrovni ve stromu (tzv. sourozenecké uzly). Je-li vzdálenost mezi klasifikovaným bodem a středem sourozeneckého uzlu větší než jeho poloměr a zároveň než součet tohoto poloměru s poloměrem kruhu, + v němž se bod nachází, pak sourozenec nemůže obsahovat blžšího souseda. V opačném případě se musí zkoumat i sourozenec.


Informační systémy pro rozhodování Ball trees se dají konstruovat různým způsobem. Minimální počet bodů v hyperkruhu lze zadat a tak omezit nárůst stromu. Rozdělení kruhu na dva je možné udělat např. tak, že se stanoví nejvzdálenější bod od středu a pak se najde bod nejvzdálenější k právě stanovenému bodu. Takto jsou definovány středy dvou nových shluků a do nich přiřazeny body ležící blíže k těmto středům. Potom se spočítají těžiště pro každý z obou shluků a minimální poloměr potřebný pro zahrnutí bodů, které jsou shlukem reprezentovány. Uvedená metoda má výhodu v tom, že náročnost rozdělení kruhu na dva kruhy je lineárně úměrná počtu bodů v kruhu. Existují i složitější, výpočtově ale náročnější postupy.



+

+

Šedý velký kruh obsahuje 9 bodů. Z jeho středu vede červená šipka k nejvzdálenějšímu bodu, z něhož pak vede zelená šipka k bodu nejvzdálenějšímu k němu. Fialový a žlutý kruh představují dva shluky. V nich jsou nalezena těžiště, označená bílými křížky, která na závěr představují středy, do nichž se příslušné shluky přesunou. Výsledkem rozdělení šedého (hyper)kruhu je tedy (hyper)kruh modrý se 4 body a (hyper)kruh zelený s 5 body.


Informační systémy pro rozhodování Bayesovské učení Bayesova metoda inference je založena na použití teorie pravděpodobnosti. Strojové učení poskytuje kvantitativní přístup ke zvažování důkazů podporujících alternativní hypotézy. Základem je Bayesův teorém:

P  h ∣D  =

P  D ∣h ⋅P  h  , P D 

kde P(h) je apriorní pravděpodobnost platnosti hypotézy h před tím, než byla získána trénovací data D, P(D) je pravděpodobnost pozorování dat D bez jakéhokoliv vztahu k nějaké hypotéze h, P(D|h) pravděpodobnost zpozorování dat D ve světě, kde platí hypotéza h, a P(h|D) je aposteriorní pravděpodobnost hypotézy h za předpokladu pozorování dat D.


Informační systémy pro rozhodování Důležité je, že P(h) platí bez ohledu na jakákakoliv data, která jsou k dispozici, zatímco P(h|D) je ovlivněno daty, která se podařilo pozorovat.

P(h|D) klesá s rostoucí P(D), protože roste-li pravděpodobnost pozorování D bez vztahu k h, pak D poskytují stále menší podporu hypotéze h (zvyšuje se vzájemná nezávislost). Logicky také očekáváme, že P(h|D) poroste jak s P(h), tak s P(D|h). Triviální ilustrační příklad se vztahuje k medicínské diagnóze, kdy pro jednoduchost předpokládáme, že jsou dvě možnosti: pacient určitou nemoc buď má nebo nemá (dvě klasifikační třídy). Dále, výsledky vyšetření nemusí být 100% spolehlivé.


Informační systémy pro rozhodování Nechť výsledky laboratorního vyšetření jsou opět pouze dva možné: 1 nemoc potvrzuje, 0 ne. Apriorní znalost o rozšíření choroby v populaci říká, že tak onemocní 0.8 % lidí. Výsledky vyšetření dosud dávaly 98% spolehlivost, že pacient nemoc skutečně měl a 97% spolehlivost, že ji skutečně neměl. Tyto apriorní znalosti lze shrnout takto (¬ nemoc znamená, že nemoc ve skutečnosti nebyla, a nemoc říká, že ve skutečnosti byla, tj. diagnóza pak byla či nebyla potvrzena):

P(nemoc) = 0.008, P(1 |nemoc) = 0.98, P(1 |¬nemoc) = 0.03,

P(¬nemoc) = 0.992, P(0 |nemoc) = 0.02, P(0 |¬nemoc) = 0.97.

Např. P(1|¬nemoc) znamená, že vyšetření řeklo ano, pacient nemoc nemá, ale ve skutečnosti měl: 3 %, tj. (100-97) % je chybovost vyšetření. P(1|nemoc) znamená, že vyšetření řeklo ano, pacient nemoc má, a doopravdy měl, tj. (100-98) % = 2 % je chybovost vyšetření.


Informační systémy pro rozhodování Uvedené údaje jsou doposud známé výsledky. Nyní přijde nový (budoucí) pacient, a je třeba ho zařadit do příslušné třídy má/nemá nemoc na základě ne 100% spolehlivého vyšetření a disponibilní znalosti z minula – neboli hledá se P(h |D) čili pravděpodobnostní podpora hypotézy, že nemoc pacient má (resp. komplementárně nemá), s využitím P(D |h) a P(h). Není zapotřebí použít P(D), protože tato pravděpodobnost je pro obě hypotézy stejná, takže odpadne dělení stejným číslem pro dvě uvažované alternativy:

P(1 |nemoc)∙P(nemoc) = p+= 0.98∙0.008 = 0.00784, a P(1 |¬nemoc)∙P(¬nemoc) = p–= 0.03∙0.992 = 0.02976. 0.02976 > 0.00784, takže výsledek je ¬nemoc, tj. pacient obdržel ano z laboratoře, že nemoc má, ale výsledek je, že ne.


Informační systémy pro rozhodování Příklad ukazuje dvě věci: jednak jak se počítá Bayesovská inference ze známých pravděpodobností k určení podpory hypotézám, a dále, že výsledek je nutno obezřetně posuzovat, protože může být z různých důvodů nevěrohodný. Je pravda, že vzhledem k nespolehlivosti vyšetření (2 % pro ano) pacient opravdu nemusí nemoc mít, i když vyšetření říká, že má, ale takový výsledek by se objevoval vždy. Problém zde působí aplikace statistické hodnoty P(h) = 0.008 jako apriorní pravděpodobnosti – v takových případech ji lze vynechat (tj. všechny hypotézy pak mají tutéž apriorní pravděpodobnost, zde 50 %). V realitě by se časem P(h) samozřejmě příslušně zvýšilo, kdyby se ukazovalo, že diagnózy jsou stále chybné, a pak by výsledky začaly být lepší, ale to není pro reálné aplikace možné.


Informační systémy pro rozhodování Pokud by bylo zapotřebí mít jako výsledek skutečné pravděpodobnostní hodnoty [zde součet obou P(h|D) nedává 1.0], pak je lze získat normalizací do jednotkového intervalu, např.:

P(nemoc |1) = 0.00784/(0.00784+0.02976) = 0.2085106383, tj. pravděpodobnost hypotézy, že pacient na základě výsledku vyšetření a statistických hodnot nemoc nemá, je asi 0.79, a 0.21 pro to, že nemoc má (0.79+0.21 = 1.0).

Je dobré si všimnout, že zde je aposteriorní pravděpodobnost nemoci P(h|D) = 0.21 >> P(h) = 0.008 (apriorní pravděpodobnost choroby). V takovém případě je dobré uvažovat o vlivu P(h) na výsledek: silný vliv P(h) bez závislosti na pozorovaných reálných datech D je obdoba chybné aplikace statistiky.


Informační systémy pro rozhodování Pokud by třeba apriorní pravděpodobnost choroby v populaci byla p(h) = 0.65 (nějaká běžná nemoc, kterou dostalo 65 % lidí), pak by se výpočet změnil:

P(1 |nemoc)∙P(nemoc) = p+= 0.98·0.65 = 0.637, a P(1 |¬nemoc)∙P(¬nemoc) = p–= 0.03·0.35 = 0.0105.

0.637 > 0.0105, takže výsledek je nemoc, tj. pacient obdržel ano z laboratoře, že nemoc má, a výsledek je, že ano. Normalizace dá pravděpodobnosti hypotéz, že pacient na základě výsledku vyšetření a statistických hodnot nemoc má, p+= 0.984, a p–= 0.016, že nemá – tj. realističtější výsledek. Kombinaci p(D|h) a apriorní pravděpodobnosti p(h) je nutno věnovat velkou pozornost, aby nevznikla zkreslená p(h|D)!


Informační systémy pro rozhodování Je dobré si povšimnout i toho, že žádná hypotéza není ani zcela potvrzena, ani zcela zamítnuta. Jejich pravděpodobnosti se mění s tím, jak jsou postupně získávána reálná data D. Je také dobré shromáždit z různých zdrojů podporu hypotézám a výsledné rozhodnutí založit na kombinaci znalostí, které poskytují, zejména u tak rizkových rozhodování, jako je např. diagnóza.

Základním problémem při dolování z dat je stanovit, jaká je nejpravděpodobnější klasifikace dané instance, jsou-li dána určitá trénovací data. Není to však totéž jako určení nejvyšší pravděpodobnosti pro jednu z hypotéz.


Informační systémy pro rozhodování Nechť v prostoru hypotéz existují 3 hypotézy, které mají za předpokladu určitých trénovacích dat následující aposteriorní pravděpodobnosti:

P(h1|D) = 0.4, P(h2|D) = 0.3, P(h3|D) = 0.3. h1 je tedy hypotéza s nejvyšší pravděpodobnostní podporou. Předpokládejme, že se objeví nová instance x, klasifikovaná pozitivně od h1 a negativně od h2 a h3. Uvážíme-li všechny

hypotézy, pak pravděpodobnost být pozitivní je 0.4 ( h1), ale negativní 0.3+0.3=0.6 (h2 a h3)!


Informační systémy pro rozhodování Může-li klasifikace nabýt libovolné hodnoty vj є V , pak

pravděpodobnost korektní klasifikace vj je dána vztahem: P  v j ∣D  =

∑ P v j ∣h i  P  h i ∣D  .

h i ∈H

Optimální Bayesovská klasifikace nové instance je pak taková hodnota vj , pro niž je P(vj |D) maximální: v j = argmax v j ∈V

∑

h i ∈H

P  v j ∣h i  P  h i ∣D  .

Výsledek klasifikace tedy nebude pozitivní (i když h1 má

podporu větší než jsou podpory ostatním individuálním hypotézám h2 nebo h3), nýbrž negativní (h2 + h3 převáží h1).




Informační systémy pro rozhodování Příklad výpočtu pro zadané tři hypotézy:

v є {+,–}, P(h1|D) = 0.4, P(–|h1) = 0, P(+|h1) = 1, P(h2|D) = 0.3, P(–|h2) = 1, P(+|h2) = 0, P(h3|D) = 0.3, P(–|h3) = 1, P(+|h3) = 0, takže

∑ P  ∣ h i  P  h i ∣D  = 0.4

h i ∈H

v j = argmax

∑

v j ∈{ , − } h ∈H i

,

∑ P  −∣ h i  P  h i∣D  = 0.6

h i ∈H

P  v j ∣h i  P  h i ∣D  = − .

,


Informační systémy pro rozhodování Libovolný systém, který používá pro klasifikaci nových příkladů vztah pro Bayesův optimální klasifikátor, se nazývá optimální Bayesovský učící se systém (OBK). Neexistuje žádná jiná klasifikační metoda, která bude (za předpokladu použití téhož prostoru hypotéz a téže apriorní znalosti) dávat lepší výsledky (mohou být stejně dobré). Tato metoda maximalizuje pravděpodobnost, že nové instance budou klasifikovány korektně za předpokladu, že jsou k dispozici určitá data pro natrénování (tj. stanovení aposteriorních pravděpodobností), prostor hypotéz a apriorní pravděpodobnosti nad těmito hypotézami.


Informační systémy pro rozhodování Naivní Bayesovský klasifikátor, NBK, je jednou z vysoce praktických metod strojového učení. Vychází z popsaného optimálního Bayesova klasifikátoru (OBK) a umožňuje snížit výpočetní složitost za předpokladu určitého, teoreticky ne zcela korektního zjednodušení – cenou je možné snížení přesnosti, ale pragmatický přínos je velmi výrazný pro úlohy popsané mnoha atributy (desítky a mnohem více). NBK může dosáhnout i stejné přesnosti jako OBK, nebo se výsledkům OBK dostatečně přiblížit, jak ukazují výsledky tisíců aplikací v reálném světě, protože praktická realita většinou do značné míry vyhovuje teoretickým požadavkům. Samozřejmě, že výsledky NBK mohou být špatné, pokud je odchylka od teoretického předpokladu velká; pak nelze NBK použít.


Informační systémy pro rozhodování NBK je použitelný, když lze každou instanci x popsat jako konjunkci hodnot atributů a kde cílová funkce f(x) může nabýt libovolné hodnoty z nějaké konečné množiny V. NBK je založen na zjednodušujícím předpokladu, že hodnoty atributů ai jsou navzájem podmíněně nezávislé za předpokladu dané cílové hodnoty vj . Jinými slovy: Pravděpodobnost NBK pro výskyt určité konjunkce hodnot atributů je dána pouze součinem pravděpodobností výskytu hodnot individuálních atributů: P  a 1 , a 2 ,  , a n ∣ v j  = ∏ P a i ∣ v j  , i

což není (obecně a teoreticky) korektní předpoklad.


Informační systémy pro rozhodování Použije-li se uvedené zjednodušení, vznikne následující vztah pro klasifikaci naivním Bayesovým klasifikátorem: v NBK = argmax P  v j  ∏ P  a i ∣ v j  . v j ∈V

i

apriorní pravděpodobnost

V NBK je počet různých termů P (ai |vj ) , které je nutno

odhadnout pomocí trénovacích dat, roven právě počtu různých hodnot atributů násobeno počtem různých cílových hodnot (výpočetní složitost daná kombinací hodnot). To je výrazně menší počet, než kdyby se musely odhadovat pravděpodobnosti P(a1, a2, …, an | vj ) bez uvažovaného zjednodušení za předpokladu nezávislosti – to však bývá v praxi velmi často alespoň pro část atributů splněno, takže narušení teoretických předpokladů většinou příliš výsledky nenarušuje (ale někdy může!).


Informační systémy pro rozhodování Pro ilustraci předpovědi naivním Bayesovým klasifikátorem se lze opět vrátit k problému, zda hrát či nehrát tenis při určité kombnaci hodnot popisujících počasí: 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

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

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

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

Data v tabulce jsou použita jako trénovací příklady, aby se systém naučil přiřazovat spávně třídu ano/ne pro odlišné instance, např.:

slunečno, chladno, vysoká, ano: hrát či nehrát?


Informační systémy pro rozhodování Pro ilustraci předpovědi naivním Bayesovým klasifikátorem se lze opět vrátit k problému, zda hrát či nehrát tenis při určité kombnaci hodnot popisujících počasí:

vNB = argmax [P(vj )·P(slunečno|vj )·P(chladno|vj )· P(vysoká|vj )·P(ano|vj ) ] počítáno pro všechny hodnoty vj (j = 1, 2; tj. v1=ano a v2=ne).

Z tabulky je nutno získat 2x5=10 pravděpodobností. Apriorní pravděpodobnosti P(vj ) se snadno spočítají

z frekvencí výskytu hodnot ano/ne v posledním sloupci tabulky:


Informační systémy pro rozhodování P(hrát tenis=ano) = 9/14 = 0.64, P(hrát tenis=ne) = 5/14 = 0.36. Obdobně se stanoví podmíněné pravděpodobnosti, např.:

P(větrno=ano|hrát tenis=ano) = 3/9 = 0.33, P(větrno=ano|hrát tenis=ne) = 3/5 = 0.60, tj. ze 14 pozorovaných případů se 9x hrálo a 5x nehrálo, z toho kombinace větrno|ano je 3x a větrno|ne taky 3x. Stejným postupem se spočítají další pravděpodobnosti pro kombinace cílové hodnoty hrát/nehrát s hodnotami dalších atributů vzhledem k jejich četnosti, takže výsledek pro nový klasifikovaný případ je:


Informační systémy pro rozhodování P(ano)·P(slunečno|ano)·P(chladno|ano)· P(vysoká|ano)·P(ano|ano) = 0.0053, P(ne)·P(slunečno|ne)·P(chladno|ne)· P(vysoká|ne)·P(ano|ne) = 0.0206. vj = argmax(0.0053, 0.0206) => vj = ne, neboli pro uvedenou konstelaci hodnot atributů nové instance radí naivní Bayes nejít hrát tenis. Normalizací lze získat pravděpodobnost pro nehrát = 0.795 a pro hrát = 0.205. Vyplývá z toho, že žádná možnost není vyloučena, ale na základě pozorovaných dat dostává vyšší přednost cílová hodnota tenis nehrát.


Informační systémy pro rozhodování Domácí úkol: podle uvedeného postupu dopočítat všechny zbývající pravděpodobnosti, které zde výpočetně uvedeny nebyly (kromě pro větrno), a ověřit výše zmíněný výsledek. Dále navrhnout další odlišnou kombinaci hodnot atributů, která není v tabulce trénovacích příkladů, a spočítat detailně, jaké jsou pravděpodobnosti pro obě možné cílové hodnoty. Získané výsledky intuitivně zhodnotit, zda odpovídají tabulce (tj. dosud naměřeným hodnotám) a zda mají oprávnění v realitě (tj. zda vypadají “rozumně”).

Tabulky obecně nemusí dostatečně realitu pokrývat , proto je nutné nespoléhat (u libovolné aplikace) pouze na získaná čísla, ale pokusit se o jejich interpretaci.


Informační systémy pro rozhodování Příkladem aplikace naivního Bayesova klasifikátoru je i použití pro zařazování elektronických nestrukturovaných textů do příslušných kategorií. Typické je např. filtrování e-mail zpráv, kde uživatel může jednoduše označit nechtěnou zprávu jako spam. Slova wi ve zprávě jsou použita jako konjunkce hodnot charakterizujících konkrétní klasifikační třídu spam:

[

n

]

c NBK = argmax p  c j  ∏ p  w i ∣ c j  , kde cj

i =1

n je počet slovních pozic v dokumentu klasifikovaném do cj , j je index jedné z uvažovaných klasifikačních tříd, p(cj ) je apriorní pravděpodobnost výskytu dokumentu v cj , dále p(wi |cj ) je aposteriorní pravděpodobnost výskytu slova wi ve třídě cj na základě trénovacích dat D.


Informační systémy pro rozhodování Např. konkrétní dokument dk může být reprezentován třeba

n = 143 různými slovy w1 , w2 , w3 , … , w143 a klasifikován do j = 3 různých tříd: cj ∈ { zajímavý, nezajímavý, neutrální }. Pro každé cj se spočítá pravděpodobnost, s níž tam dokument patří, a výsledek cNBK je dán maximální hodnotou argmax dle výše uvedené rovnice. Triviální ilustrační příklad pro dvě klasifikační třídy a malý počet slov i dokumentů je uveden dále (pro získání spolehlivých pravděpodobností je nutno shromáždit dostatečný počet trénovacích příkladů). Za povšimnutí stojí, že v každé z obou tříd se nacházejí dokumenty, které mají část slov společnou a část rozdílnou:


Informační systémy pro rozhodování w1 Trénovací texty:

w2

je je není není velmi chladno

. . .

+ texty : celkem 6 slov – texty : celkem 7 slov

w3

pěkné počasí chladno velmi chladno pěkné chladno

. . .

. . .

cj + + -

. . .

počet unikátních slov : 6

Klasifikovaný dokument to není pěkné chladno : + nebo – ?


Informační systémy pro rozhodování Po vytvoření celkového slovníku z unikátních slov (je jich zde 6), výpočtu apriorních pravděpodobností (2 texty + a 4 texty – v celkem 6 textech), výpočtu aposteriorních pravděpodobností výskytu slov v + a –, a následné normalizaci lze určit výsledek (slovo to se ignoruje, protože v trénovacích datech nebylo ):

setříděný slovník :

w1

w2

chladno je

w3

w4

w5

w6

není pěkné počasí velmi

četnost slova wi v +

1

1

1

1

1

1

četnost slova wi v –

3

1

1

1

0

1

p (wi |+)

1/6

1/6

1/6

1/6

1/6

1/6

p (wi | –)

3/7

1/7

1/7

1/7

0/7

1/7


Informační systémy pro rozhodování p = p ( 'není', 'pěkné', 'chladno' | +/–) = = pNBK ('není' | +/–) ∙ p ('pěkné' | +/–) ∙ p ('chladno' | +/–) Nový případ, který je nutno zařadit do příslušné třídy: “w3 w4 w1” = “není pěkné chladno ”

P

+

= p (+)∙p (w3 = 'není' | +)∙p (w4 = 'pěkné' | +)∙

p (w1 = 'chladno' | +) = 0.00154

P – = p (–)∙p (w3 = 'není' | –)∙p (w4 = 'pěkné' | –)∙ p (w1 = 'chladno' | –) = 0.00583 P – = 0.00583 > P

+

= 0.00154 ⇒ negativní

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

Recommend Documents