Dobývání znalostí - shrnutí na zkoušku

Tato stránka se snaží o shrnutí základních pojmů probraných na přednáškách. Nenahrazuje slajdy a je maximálně povrchní, je určena k usnadnění si opakování po alespoň jednom kompletním průchodu slajdy. (Pokud ale kolem toho někdo chce začít stavět skriptíčka, do toho!).

Studenti předmětu nejsou o průběhu zkoušek příliš sdílní, takže velikost průniku toho zde uvedeného a zkoušené látky není definována.

Základy pravděpodobnosti

Pravděpodobnost - principy, Bayesův vzorec, rozptyl, binomické a normální rozdělení, intervaly spolehlivosti
Testování hypotéz, chyba hypotézy, srovnávání hypotéz (rozdíly chyb)
k-násobná křížová validace

Úvod

Motivace, základní postupy, prerekvizity
Metodiky
- 5A (Assess, Access, Analyze, Act, Automate)
- SEMMA (Sample, Explore, Modify, Model, Assess)
- CRISP-DM (taková neurčitá)

Databáze

Selekce, projekce, spojení
QBE/SQL, manažerské: EIS, OBL, OLAP
OLAP: Datová krychle - pěkná agregace podle různých dimenzí; roll-up, drill-down
OLAP: Storage
- MOLAP - řídká hyperkrychle nebo hustá multikrychle
- ROLAP - do relační databáze; snowflake (co dimenze, to tabulka s kompletními daty), star (centrální tabulka faktů, tabulky dimenzí jen schéma levelů k agregaci)
Datový sklad, datové tržiště - třívrstvá sumarizace
Dotazování: asociační (IF-THEN) pravidla, support, confidence

Rozhodovací stromy

Vstup: Vektory příznaků; Výstup: Třídy klasifikace
Vnitřní uzel se větví podle hodnoty svého atributu (s atributy rodičů již zafixovanými)
TDIDT indukce:
- Algoritmus - vytvoř kořen, pak pro každý uzel
  1. zvol dělící atribut
  2. je-li co dělit, vyrob syny a rekurze
  3. není-li co dělit, vytvoř list a ohodnoť třídou
- Entropie: $-\sum_i p_i\log p_i$ ( $p_i$ relativní četnost třídy i, pro 0 doplníme výsledek limitou = 0)
- Entropie jedné hodnoty jednoho atributu; entropie atributu vážený součet přes hodnoty
- Dělíme podle atributu s nejnižší entropií (nejvýraznější rozparcelování tříd)
ID3 indukce: Jako TDIDT, ale pracuje na výstupu místo třídy jen s bool hodnotami.
- rozumně algoritmus: http://en.wikipedia.org/wiki/ID3_algorithm
C4.5 indukce: chybějící data, spojitá data, pruning, roubování, rule post-pruning, dolní odhad správnosti, při dělení minimalizace gain ratio
C5.0: boosting - hlasování několika paralelních klasifikátorů
CART: binární strom; prostor hodnot atributu rozpivotován dělící hodnotou
- Minimalizace přes pivoty: $2PLPR∑i∣P(Ci∣tL)−P(Ci∣TR)∣2P_LP_R \sum_i |P(C_i|t_L) - P(C_i|T_R)|$
SPRINT: Divné?!

Závislosti v datech

Kontingenční tabulka - pro dva atributy matice, pro každou kombinaci hodnot četnost, marginály se sumamy přes řádky/sloupce
$χ2\chi^2$ -test - jsou atributy nezávislé? stupně volnosti (skoro počet kombinací), hladina významnosti (pravděpodobnost závěru)
- $e_{ij} = r_is_j / n$ (očekávaná četnost v případě nezávislosti)
- $χ2=∑i∑j(aij−eij)2eij\chi^2 = \sum_i \sum_j {(a_{ij} - e_{ij})^2\over e_{ij}}$
- Laicky: Měříme, jak daleko je očekávaná a reálná četnost, vážíme očekávanou četností
- Je-li $χ2\chi^2$ hodnota větší než "tabulková" hodnota $χ2\chi^2$ -distribuce, atributy jsou závislé
- počet stupňů volnosti = (počet řádků - 1) * (počet sloupců - 1)
  - idea: pokud chci změnit kontingenční tabulku, ale chci zachovat řádkové a sloupcové součty, po změně počet-stupňů-volnosti polí jsou zbývající hodnoty jednoznačně určené
Fisherův test - máme málo dat a jen dva booleovské atributy (= čtyřpolní kontingenčí tabulka)
- Přesná pravděpodobnost rozložení četností $\left({a_{11} + a_{12}} \choose {a_{11}}\right) \left({a_{21} + a_{22}} \choose {a_{22}}\right) / \left({n} \choose {a_{11} + a_{21}}\right)$ (http://artax.karlin.mff.cuni.cz/upload/index.php?action=view&filename=CodeCogsEqn-1.gif&directory=predmety/NDBI023& obrázek)
- Jiný vzorec pro Fisherův test: $p = (r_1! * r_2! * s_1! * s_2!) / (n! * a_11! * a_12! * a_21! * a_22!)$
  - r/s jsou řádkové/sloupcové součty, n je celkový součet
- Sesumuji p přes všechna možná rozložení při zafixovaných marginálech, výsledek je pravděpodobnost, že jsou atributy závislé
  - kanonický postup: protočím tabulku, aby nejnižší hodnota byla vlevo nahoře, postupně ji dekrementuju až do nuly a pro každou hodnotu upravím ostatní hodnoty (tak aby se nezměnily marginály) a spočtu p_i, ta pak sečtu a mám pst
Regresní analýza
- Lineární regrese - chci jeden atribut vyjádřit lineární rovnicí podle druhého; minimalizace MSE (derivace)
- Míra lineární závislosti (Pearson's r): $\over \sigma_x \sigma_y}$
- Vícerozměrná, mnohorozměrná regrese
- Logistická regrese
- Diskriminační analýza - vpodstatě zkoušíme vyrobit perceptron, měříme chybu
Shluková analýza
- K-means
  - http://is.muni.cz/th/172767/fi_b/5739129/web/web/kmeans.html
  - http://cmp.felk.cvut.cz/cmp/courses/recognition/Lab_archive/RPZ_02-03l/kmeans/index.html
  - http://en.wikipedia.org/wiki/K-means_algorithm
- kNN
  - http://www.youtube.com/watch?v=4ObVzTuFivY
- LVQ
  - http://ccy.dd.ncu.edu.tw/~chen/course/neural/ch4/index.htm

Výběr příznaků

Karhunen-Loevevův rozvoj - něco jako neperiodický Fourier, vliv prvků rozvoje se s indexem monotonně snižuje
PCA - vpodstatě metoda, jak ho získat. Spoustu různých způsobů:
- Klasicky:
  1. Vycentrovat data $μi=1n∑jxij\mu_{i} = {1 \over n}\sum_j x_{ij}$
  2. Disperzní matice $wij=1n∑k(xki−μi)(xkj−μj)w_{ij} = {1 \over n}\sum_k (x_{ki} - \mu_{i})(x_{kj} - \mu_j)$
  3. Najdeme charakteristické vektory disperzní matice
- Oja: hledáme hlavní dimenzi $w⃗\vec w$
  1. Náhodná inicializace, $γ\gamma$ parametr učení
  2. Vytáhneme z X náhodný vektor, $\vec x \vec w$
  3. Zupdatujeme váhu $w⃗=w⃗+γy(x⃗−yw⃗)\vec w = \vec w + \gamma y (\vec x - y \vec w)$
  - Vychází z Hebbovského učení, ale na rozdíl od něj konverguje - vlastně vezme Hebbovské pravidlo, to znormalizuje a normalizaci promítne zpět do původního vzorečku skrz Taylorův rozvoj; více viz wikipedie

Perceptrony

Lineární separabilita, absolutní lineární separabilita
Perceptronový algoritmus učení - hledáme dělící nadrovinu a na ní kolmý váhový vektor $w⃗\vec w$
- Chybně klasifikovaný vektor uvnitř (ve směru váhového vektoru) odčítáme (otáčíme $w⃗\vec w$ od něj)
- Chybně klasifikovaný vektor vně přičítáme (otáčíme $w⃗\vec w$ k němu)
Konvergence učení - řada předpokladů, počkáme si na událost $w⃗t+1=w⃗t+p⃗\vec w_{t+1} = \vec w_{t} + \vec p$
- Jak otočeni jsme k hledanému váhovému vektoru? $cos⁡ρ=w⃗∗w⃗t+1∣∣w⃗t+1∣∣\cos \rho = {\vec w^* \vec w_{t+1} \over ||\vec w_{t+1}||}$
- V čitateli i jmenovateli zvlášť rozvineme $w⃗t+1\vec w_{t+1}$ a vyrobíme nerovnosti, dostaneme $cos⁡ρ≥w⃗∗w⃗0+(t+1)δ∣∣w⃗0∣∣2+(t+1)\cos \rho \ge {\vec w^* \vec w_0 + (t+1)\delta \over \sqrt{||\vec w_0||^2 + (t+1)}}$
- Ale protože hodnota cos je omezená, musí být počet aktualizací (t) omezený.
Přihrádkový (ratchet) algoritmus - vždy si pamatuji váhový vektor, který zatím prošel nejvíce úspěšnými klasifikacemi za sebou, až zastavím učení, vydám ten

Back-propagation

Vícevrstvá neuronová síť, potřebuji propagovat updaty váhových vektorů
Výstup neuronu buď $f(\xi = \sum_i w_ix_i)$
Minimalizuji na trénovací množině odchylku přes výstupní neurony $\sum_p \sum_j (y_{jp} - d_{jp})^2$
Váhový update: $wij(t+1)=wij(t)+ΔEwij(t)w_{ij}(t+1) = w_{ij}(t) + \Delta_E w_{ij}(t)$
Výstupní neuron: $ΔEwij=−∂E∂wij=−∂E∂ξj∂ξj∂wij=−∂E∂ξjyi=−∂E∂yj∂yj∂ξjyi=−(yj−dj)f′(ξj)yi=δjyi\Delta_E w_{ij} = -{\partial E \over \partial w_{ij}} = -{\partial E \over \partial \xi_j}{\partial \xi_j \over \partial w_{ij}} = -{\partial E \over \partial \xi_j} y_i = -{\partial E \over \partial y_j}{\partial y_j \over \partial \xi_j} y_i = -(y_j-d_j)f'(\xi_j) y_i = \delta_j y_i$
Vnitřní neuron: $ΔEwij=−∂E∂yj∂yj∂ξjyi=−(∑k∂E∂ξk∂ξk∂yj)∂yj∂ξjyi=−(∑k∂E∂ψkwjk)∂yj∂ξjyi=−(∑kδkwjk)f′(ξj)yi=δjyi\Delta_E w_{ij} = -{\partial E \over \partial y_j}{\partial y_j \over \partial \xi_j} y_i = -(\sum_k {\partial E \over \partial \xi_k}{\partial \xi_k \over \partial y_j}) {\partial y_j \over \partial \xi_j} y_i = -(\sum_k {\partial E \over \partial \psi_k} w_{jk}) {\partial y_j \over \partial \xi_j} y_i = -(\sum_k \delta_k w_{jk}) f'(\xi_j) y_i = \delta_j y_i$

Hopfieldovy sítě

Sada binárních neuronů, propojené každý s každým; iterativně se neurony updatují, umí vyhlazovat zašuměný vstup (stabilní body dyn. systému), nízká kapacita
Hebbovské učení: $wij=∑pxipxjpw_{ij} = \sum_p x_i^p x_j^p$ (what fires together, wires together)
Konvergence při vybavení - energetická funkce neustále klesá

Kohonenovy mapy

Kompetice neuronů o vzorek, vítěz inhibuje ostatní
Neurony topologicky rozprostřeny, soutěží o váhový vektor nejbližší vstupu
c buď vítěz, pak $Δwij=α(t)P(c,j)(xi(t)−wij)\Delta w_{ij} = \alpha(t) \Rho(c,j)(x_i(t) - w_{ij})$
Vektorová kvantizace LVQ1 - podivnost?!

Genetické algoritmy

Selekce, křížení, mutace, elitismus, ...
Schema - abstraktní "šablona" genomu, na každé pozici wildcard nebo zafixovaná hodnota (teď nebudeme uvažovat nějaká konkrétní, ale prostě množinu všech možných)
Věta o schematech - v populaci roste počet schémat, která jsou krátká, mají malý počet pevných pozic a mají vysoké průměrné ohodnocení
- Idea důkazu: Díváme se postupně pro všechny genetické operátory, na čem závisí očekávaná četnost schématu v další populaci - ukazuje se, že právě na délce atd.

Předzpracování dat

Databázové relace atd.; redukce dat/atributů transformací, selekcí
- Metoda filtru - pro každý atribut charakteristika vhodnosti ( $χ2\chi^2$ , entropie, ...)
- Metoda obálky - vygenerujeme model z podmnožiny atributů a vybereme nejlepší model přes všechny podmnožiny
- Postup zdola nahoru (odstraňujeme atributy) vs. shora dolů (přidáváme)
- Ale co kombinace atributů? Blbé...
Diskretizace numerických atributů
- Lee-Shin: (bottom-up) Začneme od zvlášť intervalu pro každou hodnotu, ty iterativně slučujeme, dokud nemáme dost málo intervalů
  - V každé iteraci sloučíme intervaly s minimálním rozdílem množství informace
  - $E(ν)=∑t(P(t∣<ν)+P(t∣≥ν))2E(\nu) = \sqrt{ \sum_t (\sqrt{P(t|<\nu)} + \sqrt{P(t|\ge\nu)})^2 }$
- Fayad-Irani: (top-bottom) Rekurzivně dělí aktuální interval, uvažuje kandidáty na dělící body
  - Dělíme podle dělících bodů s dostatečným informačním ziskem - velkým zvýšením entropie po rozdělení
  - V rámci intervalu: $H(ν)=n(<ν)nH(<ν)+n(≥ν)nH(≥ν)H(\nu) = {n(<\nu) \over n} H(< \nu) + {n(\ge \nu) \over n} H(\ge \nu)$
  - Práh zisku je nepochopitelný vzoreček
- KEX: Ohodnoť hodnoty třídami, pak vyrob intervaly
  - Každou hodnotu ohodnoť třídou - přímo, je-li jen jedna třída; nejčetnější třídou, když $χ2\chi^2$ -test řekne, že se rozdělení tříd liší od apriorního; otazníkem jinak
  - Vytvoříme intervaly ze spojitých bloků tříd; otazníkové třídy v sousedstvích konkrétních napojíme na sousedy vybrané podle $χ2\chi^2$ -testu
- Fuzzy diskretizace: Vyrobíme fuzzy-intervaly; každý má na sobě definovanou char. funkci
  - Charakteristická funkce uvnitř intervalu 1, je-li soused otazník, po celé jeho délce lineárně klesá k nule
Kategoriální atributy - KEX, vpodstatě to samé, jen ne nutně spojité intervaly?

MBA, SF-sítě

Množina produktů v transakci, které se spolu vyskytují nejčastěji? Virtuální položky pro "metadata".
Tabulka četností a if-then pravidla; podpora, spolehlivost, zlepšení $\over p(i)p(j)$
Prořezávání, zobecňování (značky, výrobci), disociační pravidla (NOT; pochybná užitečnost), časové řady (rozšíření do okénka)
Scale-free sítě: Sítě, kde některé uzly mají mnohem více hran (huby) než ostatní
- http://cs.wikipedia.org/wiki/Bez%C5%A1k%C3%A1lov%C3%A1_s%C3%AD%C5%A5

APRIORI

Generování asociačních pravidel - frequent itemsets
Generování kombinací do šířky - kombinace délky k z kombinací délky k-1
- Každou kombinaci délky k-1 porovnáme s každou jinou, shodují-li se v k-2 itemech, spojíme
- Spojené zpětně profiltrujeme, chybí-li nám nějaká jejich podkombinace délky k-1, zahodíme je

Bayes

Naivní Bayesovský klasifikátor; mám jev a klasifikaci, při tréninku počítám četnosti a $P (j e v ∣ k l a s i f ika ce)$
- Při použití podle Bayesova pravidla počítám $P (k l a s i f ika ce ∣ j e v)$
- Naivní, protože předpokládám, že jevy jsou nezávislé; v praxi obvykle nejsou, přesto funguje překvapivě dobře
Bayesovské sítě - DAGy, uzel na výstupu dává pravděpodobnost generovanou statickým rozdělením přes vstupní pravděpodobnosti rodičů
- Inference - kauzální (top-bottom), diagnostická (bottom-up)
- Učení - různé varianty
  - Známe-li strukturu a vše vidíme - maximálně věrohodný odhad, vlastně naivní bayes
  - Známe-li strukturu, něco nevidíme nebo šum - gradientní metodou maximalizujeme pravděpodobnost, že vidíme, co vidíme; EM: podle parametrů distribuce spočítej hodnotu veličin, z nich urči max. věrohodný odhad parametrů, iteruj až k pevnému bodu; Kalmanovy filtry, atd.
  - Neznáme-li strukturu - průšvih