Doc. RNDr. Jan Rauch, CSc.

Katedra informačního a znalostního inženýrství

Zpracování informací a znalostí Cíle a základní metody dobývání znalostí z databází

2

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

Jan Rauch: Systém LISp-Miner. Studijní materiál pro posluchače

kurzů Metod zpracování informací, 2005, viz soubor

LM_SKRPT.pdf

http://lispminer.vse.cz/

Petr Berka: Dobývání znalostí z databází ACADEMIA 2003, 366

stran (pro zájemce o hlubší studium)

http://kdnuggets.com (pro zájemce o hlubší studium)

3

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

Úvod

Úlohy a metody

Metodologie CRISP

Rozhodovací stromy

Asociační pravidla (viz též otázka 9)

Metoda GUHA (viz též otázka 9)

4

Zjištění, že lze získat z uchovávaných dat více než proč byly ukládány Potřeba předpovídat budoucí trendy a chování Obavy ze ztráty konkurenceschopnosti Snaha o získání konkurenčních výhod …

Úvod – příčiny vzniku DZD

5

Databáze

• relační databáze• datové sklady• OLAP• …

Statistika

Strojové učení

DZD

Úvod – hlavní zdroje pro DZD

• rozhodovací stromy• neuronové sítě • ...

• kontingenční tabulky• regresní analýza• diskriminační analýza• shluková analýza• …

6

široce aplikováno

desítky firem nabízejí software a služby

výuka na vysokých školách

rozsáhlý výzkum

rozvoj nových směrů (text mining, relational data mining, complex

data mining, web mining, … )

integrace s jinými disciplinami (např. se znalostním inženýrstvím)

řada mezinárodních konferencí

http://kdnuggets.com

…

Úvod – současný stav

7

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

Úvod

Úlohy a metody

Metodologie CRISP

Rozhodovací stromy

Asociační pravidla (viz též otázka 9)

Metoda GUHA (viz též otázka 9)

8

DZD – základní typy úloh

klasifikace / predikce po naučení na trénovací množině chceme zařazení

(ohodnocení) neznámých objektů

deskripce chceme získat popis vlastností množiny objektů jako

celku

hledání „nugetů“ chceme zjistit zajímavosti, výjimky od normálu

9

DZD – příklady úloh

rozpoznání problémových nebo vysoce bonitních klientů banky

analýza klientů pojišťovny

analýza nákupních košíků

predikce spotřeby elektřiny (vody, plynu)

analýza poruchovosti automobilů

analýza dat o pacientech

analýza příčin změny mobilních operátorů

analýza chování zákazníků internetových obchodů (clickstreamy)

text mining

…

10

DZD – vybrané metody

Asociační pravidla (viz též otázka 9) Klasifikace / predikce

Rozhodovací stromy Rozhodovací pravidla Neuronové sítě

Statistické metody Kontingenční tabulky Regresní analýza Diskriminační analýza Shluková analýza (viz též otázka 4) …

GUHA (viz též otázka 9) …

11

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

Úvod

Úlohy a metody

Metodologie CRISP

Rozhodovací stromy

Asociační pravidla (viz též otázka 9)

Metoda GUHA (viz též otázka 9)

12

CRoss Industry Standard Process for Data Mining

CRISP-DM http://www.crisp-dm.org/

Porozuměníproblematice

Porozuměnídatům

Transformacedat

Analyticképrocedury

Interpretacevýsledků

Využitívýsledků DATA

13

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

Úvod

Úlohy a metody

Metodologie CRISP

Rozhodovací stromy

Příklad rozhodovacího stromu

Obecný algoritmus pro tvorbu rozhodovacích stromů

Asociační pravidla (viz též otázka 9)

Metoda GUHA (viz též otázka 9)

14

Příklad rozhodovacího stromu (1)

Dáno: známá data

Úloha:

• dán nový, neznámý klient

• půjčit nebo nepůjčit?

15

Příklad rozhodovacího stromu (2)

Způsob řešení

Daná (trénovací) data

Proces učení Vhodná forma znalosti

Nový, neznámý klient úvěr: ano/ne

16

Příklad rozhodovacího stromu (3)

Způsob řešení

Daná (trénovací) data

Vhodná forma znalosti – rozhodovací strom:

příjem

vysoký nízký

ano kontovysoké

ano

nízké

nestřední

nezaměstnanýano

nene

ano

17

Příklad rozhodovacího stromu (4)

Nový klient

• příjem: nízký

• konto: střední

• nezaměstnaný: ne

Půjčit: ?

Aplikace rozhodovacího stromu: Ano!

18

Příklad rozhodovacího stromu (5)

Nový klient

• příjem: nízký

• konto: nízké

Půjčit: ?

Aplikace rozhodovacího stromu: Ne!

19

Obecný algoritmus pro tvorbu rozhodovacích stromů

Dáno:trénovací data Výstup: rozhodovací strom

Algoritmus TDIDT

1. Zvol jeden atribut jako kořen dílčího stromu

2. Rozděl data v tomto uzlu na podmnožiny podle hodnot zvoleného atributu a přidej uzel pro každou podmnožinu

3. Existuje-li uzel, pro který nepatří všechna data do téže třídy, opakuj pro tento uzel postup od bodu 1., jinak skonči

TDIDT = Top down induction of decision tree

metoda „rozděl a panuj“

využití teorie informace a pravděpodobnosti