# **NDBI023** Dobývání znalostí

<{Box(infobox)}>
|-----|-----|
| **Stránka předmětu:** | [ksvi.mff.cuni.cz/~mraz/datamining/](http://ksvi.mff.cuni.cz/%7Emraz/datamining/index.html) |
| **Vyučující:** | [doc. RNDr. Iveta Mrázová, CSc.](https://www.mff.cuni.cz/cs/fakulta/organizacni-struktura/lide?hdl=186) |
| **SIS:** | [Odkaz do SISu](https://is.cuni.cz/studium/predmety/index.php?do=predmet&kod=NDBI023) |
<{/Box}>

## Poznámky
- ![Poznámky.pdf](/NDBI023/dobyvani-znalosti-poznamky.pdf)
- ![Poznámky.rar](/NDBI023/poznamky.rar)


## Zkoušky
- [Zkouška Mrázová 05. 06. 2026](/NDBI023/zkouska_mrazova_05-06-2026)
- [Zkouška Mrázová 03. 06. 2026](/NDBI023/zkouska_mrazova_03-06-2026)
- [Zkouška Mrázová 26.05. 2023](/NDBI023/Zkouška Mrázová 26.05. 2023)
- [Zkouška Mrázová 14.06. 2021](/NDBI023/Zkouška Mrázová 14.06. 2021)
- [Zkouška Mrázová 14.06. 2018](/NDBI023/Zkouška Mrázová 14.06. 2018)
- [Zkouška Mrázová 08.06. 2017](/NDBI023/Zkouška Mrázová 08.06. 2017)
- [Zkouška Mrázová 31.05. 2016](/NDBI023/Zkouška Mrázová 31.05. 2016)
- [Zkouška Mrázová 20.06. 2016](/NDBI023/Zkouška Mrázová 20.06. 2016)
- [Zkouška Mrázová 04.06. 2015](/NDBI023/Zkouška Mrázová 04.06. 2015)
- [Zkouška Mrázová 27.05. 2014](/NDBI023/Zkouška Mrázová 27.05. 2014)
- [Zkouška Mrázová 19.06. 2012](/NDBI023/Zkouška Mrázová 19.06. 2012)
- [Zkouška Mrázová 09.06. 2014](/NDBI023/Zkouška Mrázová 09.06. 2014)
- [Zkouška Mrázová 12.06. 2012](/NDBI023/Zkouška Mrázová 12.06. 2012)
- [Zkouška Mrázová 27.06. 2011](/NDBI023/Zkouška Mrázová 27.06. 2011)
- [Zkouška Mrázová 10.06. 2010](/NDBI023/Zkouška Mrázová 10.06. 2010)


## Zdroje k předmětu
- [Wikipedia:Datamining](https://en.wikipedia.org/wiki/Data_mining)
- [Statistics Tutorials](http://home.okstate.edu/homepages.nsf/toc/onlinetutorialsstatistics)
- [How to choose a statistical test](http://www.graphpad.com/www/book/choose.htm)
- [Statistical Data Mining Tutorials](http://www.autonlab.org/tutorials/)
- [Data mining in Matlab](http://matlabdatamining.blogspot.cz/)


## Požadavky 12/13
- výsledná známka = 40% body ze zkoušky, 20% body z dvou písemek, 40% body z úkolů ze cvičení a projektu (včetně bodů ze cvičení, všechny úkoly jsou povinné)
- vypracovat projekt
- celkem je potreba splnit aspon 56%
- terminy v září budou jeden až dva

### Fisherův test
- [http://en.wikipedia.org/wiki/Fisher%27s_exact_test#Example](http://en.wikipedia.org/wiki/Fisher%27s_exact_test#Example) - odvození, příklad jednostranného
- [http://oldweb.izip.cz/ds3/hypertext/JZAAA.htm](http://oldweb.izip.cz/ds3/hypertext/JZAAA.htm) - příklad česky
- [http://www.quantpsy.org/fisher/fisher.htm](http://www.quantpsy.org/fisher/fisher.htm) - hezké vysvětlení jednostranných a oboustranných testů, kalkulačka
- [http://graphpad.com/quickcalcs/contingency2/](http://graphpad.com/quickcalcs/contingency2/) - ještě jedna kalkulačka pro kontrolu :)
- [http://www.stahroun.me.cz/interstat/kategorialni/asociace/fisher/index.htm](http://www.stahroun.me.cz/interstat/kategorialni/asociace/fisher/index.htm) - spousta zdrojů

### chi-kvadrát test
- [http://mathhelpforum.com/advanced-statistics/44800-two-tailed-chi-squared-tests.html](http://mathhelpforum.com/advanced-statistics/44800-two-tailed-chi-squared-tests.html) - trošku světla na oboustranné testy
- [http://stats.stackexchange.com/questions/22347/chi-squared-always-a-one-sided-test](http://stats.stackexchange.com/questions/22347/chi-squared-always-a-one-sided-test) - a jeste jednou oboustranné testy
- [http://itl.nist.gov/div898/handbook/eda/section3/eda3674.htm](http://itl.nist.gov/div898/handbook/eda/section3/eda3674.htm) - tabulky


## Příklady ze cvičení

### Algoritmus TDIDT/ID3

- [http://ksvi.mff.cuni.cz/~mraz/datamining/Cvicenie_DT.pdf](http://ksvi.mff.cuni.cz/~mraz/datamining/Cvicenie_DT.pdf)

Zvol jeden atribut jako kořen podstromu

#### Kořen

##### Vitamín

- B (2+, 3-)

$-\frac{n_+(Vit(B))}{n(Vit(B))}.log_2\frac {n_+(Vit(B))}{n(Vit(B))} - \frac{n_-(Vit(B))}{n(Vit(B))}.log_2\frac {n_-(Vit(B))}{n(Vit(B))} = - \frac{2}{5}.log_2\frac {2}{5} - \frac{3}{5}.log_2\frac {3}{5} = 0.97$

- C (4+, 0-)

$\dots = 0.0$ (z "definície"...)

- D (3+, 2-)

$\dots = 0.97$

Entropia: $H(Vit) = \frac{0.971*5 + 0*4 + 0.971*5}{14} = 0.6936$ (vážený priemer)

##### Velikost rodiny

- veľká (2+, 2-)

$-\frac{n_+(Rodina(velka))}{m(Rodina(velka))}.log_2\frac {n_+(Rodina(velka))}{n(Rodina(velka))} - \frac{n_-(Rodina(velka))}{n(Rodina(velka))}.log_2\frac {n_-(Rodina(velka))}{n(Rodina(velka))} = 1$

- stredná (4+, 2-)

$\dots = 0.9183$

- malá (3+, 1-)

$\dots = 0.8113$

Entropia: $H(Rodina)=0.9111$

##### Cvičil

- pravidelně (3+, 4-)

$\dots = - \frac{3}{7}.log_2\frac {3}{7} - \frac{4}{7}.log_2\frac {4}{7} = 0.985$

- málo (6+, 1-)

$\dots = - \frac{6}{7}.log_2\frac {6}{7} - \frac{1}{7}.log_2\frac {1}{7} = 0.592$

Entropia: $H(Cvicil) = \frac{0.985*7 + 0.592*7}{14} = 0.7885$

##### Bypass

Entropia: $H(Bypass)=0.8922$

... budeme teda pokračovať podľa atribútu Vitamín (najmenšia entropia).

Množinu rozdelíme na 3 skupiny (B,C,D). C-čko všetci prežili, máme dve skupiny pre Bcomplex a D - spočítame znovu strednú entropiu (aby sme vedeli, podľa čoho ďalej štiepiť).

#### B ####

vyberieme riadky s Bcomplex a robíme to isté :)

##### Velikost rodiny

- veľká (0, 2-)

$\dots = 0$ (z "definice"...)

- stredná (1+, 1-)

$\dots = 1$

- malá (1+, 0)

$\dots = 0$ (z "definice"...)

Entropia: $H(Rodina) = \frac{0*2 + 1*2 + 0*1}{5} = 0.4$

##### Cvicil

$H(Cvicil)=0$

##### Bypass

$H(Bypass)=0.9183$

#### C

...je jasné, tam nik nezomrel... :)

#### D

$H(Rodina)=0.9183$
$H(Cvicil)=0.9183$

$H(Bypass)=0$

...ďalej sa teda bude štiepiť v Bčku podľa "Cvicil" a v Dčku podľa "Bypass"

Vitamin / | \ B/ C| \D Cviceni + Bypassprav./ m.| a| n\ - + - +

### Perceptron

- uloha: naucit perceptron rozoznavat body v 2D na 2 skupiny...

- popis perceptronu v matlabe: $p=\begin{bmatrix} w_1 & w_2 & prah \end{bmatrix}$
- vyhodnoti sa potom... $x=\begin{bmatrix} x_1 & x_2 \end{bmatrix}$ => $perc_{recall} = w_1*x_1 + w_2*x_2 + prah*1$
- ...rozsireny vstupny vektor $x_1'=\begin{bmatrix} x_1 & x_2 & 1 \end{bmatrix}$
- $vystup=hardlim1(p*x_1')$ (hardlim1(<=0)=0; hardlim1(>0)=1)

- inicializacia : $p=\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}$
- vstup: $A=\left[ \begin{matrix} 1 & 1 & 2 & 3 \\ 1 & 3 & 2 & 1 \end{matrix} \right]$
- vystup (chceme): $c = \begin{bmatrix} 1 & 1 & 0 & 0 \end{bmatrix}$

- uciaca konstanta $a=0.2$
- ucenie prebieha takto:
- vezme sa vzor, ak sedi, nic nerobime
- ak najdeme chybu - pricitame/odcitame (pozadovany-skutocny vystup - napr. v priklade $y=hardlim1(p*AA); dif=c(3)-y(3)$) dany vektor k vaham... $(c(3)-y(3))*AA(:,3)$
- dostavam novy perceptron $p1=p+a*((c(3)-y(3))*AA(:,3))'$
- $y1=hardlim1(p1*AA) = \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}$
- to je zla matica (ma byt samozrejme $\begin{bmatrix} 1 & 1 & 0 & 0 \end{bmatrix}$)- znovu zopakujeme postup...

- $p1=\begin{bmatrix} 0.6 & 0.6 & -0.2 \end{bmatrix} => y1=\begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}$
- $p2=\begin{bmatrix} 0 & 0.4 & -0.4 \end{bmatrix} => y2=\begin{bmatrix} 0 & 1 & 1 & 0 \end{bmatrix}$

teraz budeme skusat prvy vektor (ktory je nespravny)

- $p3=\begin{bmatrix} 0.2 & 0.6 & -0.2 \end{bmatrix} => y2=\begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}$

- ... N iteracii (N=?)