EuroMISE centrum – Kardio, spolunositelské pracoviště Vysoká škola ekonomická Praha

2  Metody dobývání znalostí

2.1  Rozhodovací stromy
2.2  Rozhodovací pravidla
2.3  Asociační pravidla
2.4  Neuronové sítě
2.5  Statistické metody
2.6  Nejbližší soused

Výpočetním jádrem celého procesu dobývání znalostí z databází je použití analytických metod. Tento krok bývá v anglické literatuře nazýván data mining, modeling nebo analyzis. Vstupem do analytických procedur jsou předzpracovaná data, výstupem jsou znalosti.

Všechny používané metody vycházejí z předpokladu, že jednotlivé objekty (příklady, pozorování) lze popsat pomocí charakteristik takových, že objekty patřící k témuž konceptu (do téže třídy) mají podobné charakteristiky (tyto metody bývají proto někdy nazývány učení na základě podobnosti similarity-based learning). Pokud jsou objekty popsány hodnotami atributů, lze je reprezentovat body v n-rozměrném prostoru atributů (příznaků), kde n je počet atributů. Učení na základě podobnosti pak vychází z představy, že objekty představující příklady téhož konceptu vytvářejí jakési shluky v tomto prostoru. Cílem modelování je tedy nalézt vhodnou reprezentaci těchto shluků. Způsob reprezentace znalostí přitom může být značně rozmanitý. Mohou to být reprezentativní příklady-etalony (tak je tomu u metod založených na analogii), mohou to být funkce přiřazené jednotlivým shlukům (to je případ subsymbolických metod), může to být rozdělení prostoru atributů na snadno popsatelné, pravidelné útvary (to je případ metod symbolických).

Jednotlivé metody se ovšem neliší pouze způsobem reprezentování hledaných znalostí. Další rozdíly mezi metodami spočívají v tom:

V této kapitole se podíváme na nejčastěji používané analytické metody. Z metod symbolických to budou metody pro tvorbu rozhodovacích stromů, asociačních pravidel a rozhodovacích pravidel. Z metod subsymbolických to budou neuronové sítě a regresní metody. Jako ilustrační příklad použijeme údaje o osobách – klientech banky, kterým banka půjčuje na základě informací o jejich příjmech a výši konta (Tab. 1). Tato tzv. trénovací data můžeme použít v procesu dobývání znalostí.

Tab. 1 – Demonstrační data
klient příjem konto pohlaví nezaměstnaný úvěr
k1 vysoký vysoké žena ne ano
k2 vysoký vysoké muž ne ano
k3 nízký nízké muž ne ne
k4 nízký vysoké žena ano ano
k5 nízký vysoké muž ano ano
k6 nízký nízké žena ano ne
k7 vysoký nízké muž ne ano
k8 vysoký nízké žena ano ano
k9 nízký střední muž ano ne
k10 vysoký střední žena ne ano
k11 nízký střední žena ano ne
k12 nízký střední muž ne ano

2.1 Rozhodovací stromy

Způsob reprezentování znalostí v podobě rozhodovacích stromů je dobře znám z řady oblastí. Vzpomeňme jen nejrůznějších „klíčů k určování“ různých živočichů nebo rostlin známých z biologie. Indukce rozhodovacích stromů patří k nejznámějším algoritmům z oblasti symbolických metod strojového učení. Při tvorbě rozhodovacího stromu se postupuje metodou „rozděl a panuj“ (divide and concquer). Trénovací data se postupně rozdělují na menší a menší podmnožiny tak, aby v těchto podmnožinách převládaly příklady jedné třídy.

Rozhodovací strom
Obr. 2 – Rozhodovací strom

Použití rozhodovacích stromů pro klasifikaci odpovídá analogii s klíči k určování rostlin nebo živočichů. Od kořene stromu se na základě odpovědí na otázky (umístěné v nelistových uzlech) postupuje příslušnou větví stále hlouběji, až do listového uzlu, který odpovídá zařazení příkladu do třídy.

2.2 Rozhodovací pravidla

If-then konstrukce nalezneme ve všech programovacích jazycích, používají se i v běžné mluvě. Není tedy divu, že pravidla s touto syntaxí patří, vedle stromů k nejčastěji používaným prostředkům pro reprezentaci znalostí, ať už získaných od expertů, nebo vytvořených automatizovaně z dat.

Jedním z nejznámějších algoritmu pro tvorbu pravidel je algoritmus pokrývání množin pracující metodou odděl a panuj (separate and conquer). Při pokrývání množin jde totiž o to nalézt pravidla, která pokrývají příklady téže třídy a oddělit je od příkladů třídy jiné. Pro naše data bychom nalezli pravidla uvedená na Obr. 3. Použití těchto pravidel pro rozhodování o novém klientovi je opět velice jednoduché. Nalezneme první pravidlo, jehož předpokladům klient vyhovuje. Závěr tohoto pravidla pak určí, zda půjčit nebo ne.

If konto=vysoké then úvěr=ano
If příjem=vysoký then úvěr=ano
If příjem=nízký & konto=střední
& pohlaví=muž & nezaměstnaný=ne
then úvěr=ano

Obr. 3 ” Rozhodovací pravidla

2.3 Asociační pravidla

V případě asociačních pravidel neni žádný atribut (sloupec tabulky) vyčleněn jako cíl klasifikace. Asociační pravidla hledají „všechny zajímavé“ asociace (implikace, ekvivalence) mezi hodnotami různých atributů. K výše uvedeným (rozhodovacím) pravidlům tak mohou přibýt např. pravidla uvedená na Obr. 4.

If nezaměstnaný=ano then příjem=nízký
If příjem=vysoký then nezaměstnaný=ne

Obr. 4 Asociační pravidla

2.4 Neuronové sítě

Umělé neuronové sítě vycházejí z analogie s lidským mozkem. Podobně jako mozek jsou tvořeny množstvím navzájem propojených elementů; neuronů. V umělých neuronových sítích je neuron chápán jako buňka, která přijímá podněty od jiných neuronů, které jsou k ní připojeny „na vstupu“. Pokud souhrnný účinek těchto vstupních podnětů překročí určitý práh, neuron se aktivuje a sám začne svým výstupem působit na další neurony (obr. 5). První modely neuronů a neuronových sítí se zkoumaly v rámci umělé inteligence již v 50. letech.

Model neuronu
Obr. 5 – Model neuronu

Důležitá (z hlediska dobývání znalostí) je schopnost těchto modelů učit se z příkladů. Na rozdíl od strom; nebo pravidel, kde jsou nalezené znalosti srozumitelné uživateli, v neuronové síti jsou znalosti „rozprostřeny“ v podobě vah jednotlivých vazeb mezi neurony. Neuronová síť se vlastně chová jako černá skříňka; není příliš zřejmé, co se uvnitř děje.

Pro náš demostrační případ vystačíme s jedním neuronem. Nalezené znalosti jsou váhy wi neuronu; tyto váhy odpovídají parametrům přímky uvedené na obr. 6, která od sebe odděluje příklady (klienty) patřící do různých tříd.

Diskriminace lineárním neuronem
Obr. 6 – Diskriminace lineárním neuronem

Složitější umělé neuronové sítě bývají tvořeny množstvím různě navzájem propojených neuronů. K nejznámějším typům umělých neuronových sítí (používaných pro klasifikaci) patří vícevrstvá síť uvedená na obr. 7.

Vícevrstvá síť
Obr. 7 – Vícevrstvá síť

2.5 Statistické metody

Statistika nabízí celou řadu teoreticky dobře prozkoumaných a léty praxe ověřených metod pro analýzu dat. Pro oblast dobývání znalostí z databází mají význam (ať už přímo jako používané metody nebo nepřímo jako zdroj inspirace):

Použijeme-li na naše demonstrační data (z tab. 1) lineární diskriminační analýzu, získáme parametry diskriminační funkce, které budou odpovídat modelu uvedenému na obr. 6.

2.6 Nejbližší soused

V případě nejbližšího souseda jsou koncepty (třídy) reprezentovány svými typickými představiteli. V procesu klasifikace se pak nový příklad zařadí do třídy na základě podobnosti (nejmenší vzdálenosti k reprezentantovi nějaké třídy – viz obr. 8). Jde tedy o metodu která vychází ze shlukové analýzy. Klíčovým pojmem je koncept podobnosti, resp. vzdálenosti dvou příkladů.

Klasifikace dle nejbližšího souseda
Obr. 8 – Klasifikace dle nejbližšího souseda


Datum: 21. 09. 2017

URL: