---
# System prepended metadata

title: SZ 7. Dobývání znalostí
tags: [Společný základ]

---

---
tags: Společný základ
---

<style>
    blockquote span{color:black;}
    blockquote blockquote span{color:gray;}
</style>

Zápisky  -> https://drive.google.com/file/d/1MCmc4wQ0jqZvxZ_tet85L0NY1I0Nk2eJ/view

# SZ 7. Dobývání znalostí

Předzpracování dat. Učení častých vzorů a asociačních pravidel. Nástroje pro strojové učení a dolování z dat (obecně + popis jednoho podrobně). Analýza temporálních dat. (PV056)


## Co to je?
Knowledge Discovery (KDD) nebo taky data mining je disciplína, která se zajímá o využití statistických nástrojů, algoritmů strojového učení, nebo vizualizačních technik k získání zajímavých/užitečných informací z dat. Příkladem může být educational data mining (EDM) space, který se zaměřuje na zpracování dat ve vzdělávání. 

## Předzpracování dat
- Data cleaning
    - Incomplete data (missing values)
        - ignore data point
        - fill value manually
        - fill automatically
            - mean
            - global constant
            - class mean
            - most probable value
    - Noisy data (error values, duplicates)
        - binning - split data into bins and take the bin mean, median, boundaries...
        - regression - smooth by fitting data to regression function
        - clustering - detect and remove outliers
    - Inconsistent data
        - age vs birth date
- Data reduction
    - main idea: obtain reduced representation of the dataset. Much smaller, but produces almost the same analytical results
    - helps with too big datasets
    - select or create features that are important
    - types:
        - histrogram analysis
            - store data into buckets and take average for each bucket
        - clustering
            - cluster based on similarity and only store cluster representation (center+diameter)
        - sampling
            - obtain small sample to represent the whole dataset
            - simple random sampling
            - sampling with and without replacement
            - stratified sampling (the ratio of classess remains the same)
- Data transformation
    - function that maps entire set of values of a given attribute to new set of replacement values
    - types:
        - smoothing
        - attribute/feature construction
        - aggregation
        - normalization
        - discretization
- Dimensionality reduction
    - feature selection
        - find subset of the original variables
        - remove redundant attributes
        - remove irrelevant attributes
    - feature extraction
        - transform data to fewer dimensions
        - PCA

## Učení častých vzorů a asociačních pravidel
Časté vzory jsou podmnožiny (itemsets, subsequences, nebo substructures) objevující v datech frekventovaně.

### Asociační pravidla
Asociační pravidla spadají pod časté vzory. Slouží k popisu chování např. zákazníků v obchodě. Hledají se především pravidla, kde konjunkce či disjunkce itemů (itemset) $X$ implikuje další itemset $Y$. Např. Pokud si koupím pivo a rohlík, tak si koupím salám a sýr.

Nejzáměnší použití je právě analýza nákupního košíku.
Slajdy: 
https://is.muni.cz/auth/el/fi/jaro2022/PV056/um/62159290/ass1.pdf https://www.karlin.mff.cuni.cz/~antoch/robust18/PREDNASKY/STREDA/navratil.pdf 

Nejznámějším algoritmem je algoritmus Apriori.
https://is.muni.cz/auth/el/fi/jaro2020/PV056/um/advanced_machine_learning/62159290/ass.pdf
https://is.muni.cz/auth/el/fi/jaro2019/PV056/um/62159239/62159290/

#### Důležité koncepty
K měření kvality asociačních pravidel se využívají následující koncepty:

##### Support
>Jak frekventovaná je daná množina položek (itemset). Tj.: $\frac{pocet\_vyskytu\_mnoziny}{velikost\_datasetu}$
>
> $supp(X) = \frac{\{|t\in T; X \subseteq t|\}}{|T|}$

##### Confidence
> Jak často je pravdivé pravidlo $X \Rightarrow Y$. Tj.: $\frac{frekvence_{X \cup Y}}{frekvence_X}$
>
> $conf(X\Rightarrow Y) = \frac{supp(X\cup Y)}{supp(X)} = \frac{
\frac{\{|t\in T; X \subseteq t\ \wedge Y \subseteq t|\}}{|T|}
}{
\frac{\{|t\in T; X \subseteq t|\}}{|T|}
} = \frac{
\{|t\in T; X \subseteq t\ \wedge Y \subseteq t|\}
}{
\{|t\in T; X \subseteq t|\}
} = \frac{pocet\_vyskytu\_XY}{pocet\_vyskytu\_X}$


##### Lift
>Poměr pozorované frekvence a očekávané frekvence v případě že jsou X a Y nezávislé.
>
> $lift(X\Rightarrow Y) = \frac{supp(X \cup Y)}{supp(X)supp(Y)}$

> * lift = 1 -- společný výskyt X a Y pravděpodobně nezávislý.
> * lift > 1 -- potenciálně závislý výskyt.
> * lift < 1 -- potenciálně závislý nevýskyt (Pokud jeden je pak druhý chybí). 

##### Conviction
> $conv(X \Rightarrow Y) = \frac{1-supp(Y)}{1-conf(X\Rightarrow Y)}$




## Nástroje pro strojové učení a dolování z dat (obecně + popis jednoho podrobně)
Skoro jakýkoliv strojově učící se alg. jde použít k dolování dat.
V praxi se tedy využívají spíše snadno vysvětlitelné metody oproti blackboxům, ale i např. u neuronových sítí se dost pokročilo ve vysvětlování a vizualizacích co vlastně ten blackbox dělá.

Základní techniky:

1. Classification -- stromy, KNN, svm, ...
2. Regression -- stromy, lineární regrese, ...
3. Clustering -- k-means, HAC, ...
4. Pattern discovery (Asociation rules discovery, Subgroup discovery, ..)
5. Multi-relační učení (Inductive Logic Programming - ILP)


### Text mining
[zdroj](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.132.6973&rep=rep1&type=pdf)
![](https://i.imgur.com/k0vrKEx.png)

Text mining je KDD aplikované na text, tedy se snaží o extrakcí užitečných znalostí z textových dat. V praxi se může jednat o rozšíření investičního bota o tweety vlivných osobností (Trump, Musk, ...) či získání vzorů pro detekci trolů na soc. sítích. Abych citoval: 
> "Doslova tam leží peníze na zemi!" -- prof. PhDr. Karel Pala, CSc.



### Popis jedné metody text mining (kategorizace, desambiguace, extrakce informace)
Všechny jsou vypracovány v otázce: [ML 5. Strojové učení](https://hackmd.io/GRCnEcJwSYuiACquxjKF3w?both).


### Praktické nástroje pro strojové učení a dolování z dat

* sklearn (scikit-learn)
    * knihovna pro strojové učení pro Python
    * podporuje supervised i unsupervised učící algoritmy
    * supervised:
        * lineární regrese/clasifikace
        * SVM
        * nearest neighbors
        * rozhodovací stromy
        * ansambly
        * MLP
    * unsupervised:
        * clustering (k-means)
        * PCA
    * preprocesing:
        * one-hot
        * scaling
        * bag-of-words (pro textové zpracování)
        * selekce featur
    * lazení modelu:
        * cross-validace
        * hledání hyperparametrů
    * evaluační metriky
        * MSE, accuracy, precision, recall, F1, ROC křivka, ...
* Gensim
    * knihovna pro zpracování přirozeného jazyka (NLP)
    * topic modelling, document indexing, retrieval by similarity, etc.
* NLTK
    * knihovna pro zpracování přirozeného jazyka (NLP)
    * classification, tokenization, stemming, tagging, parsing, etc.




## Analýza temporálních dat
zdroje:
- https://www.statslab.cam.ac.uk/~rrw1/timeseries/t.pdf
- http://home.ef.jcu.cz/~janaklic/OPVVV_SMAC/
- https://otexts.com/fpp3/

Analýza časových řad odkazuje na úkoly, kde jsou datapointy zaznamenávané v časových intervalech a kde po sobě jdoucí pozorování vzájeně korelují.

Příklady: denní měnové kurzy, vývoj ceny akcíí, měsíční úhrny srážek, hladina glukózy v krvi během dne, ...


### Časová řada

Časové řady jsou dvou druhů:

- s měřením v pravidelných intervalech
- s měřením v nepravidelných intervalech

Pro jednoduchost budeme uvažovat pravidelné intervaly, nepravidelné vyžadují rozšíření a složitější techniky

Formálně, časová řada je posloupnost náhodných proměnných, kterou můžeme indexovat celými čísly:

$$ \ldots, X_{-2}, X_{-1}, X_{0}, X_{1}, X_{2}, \ldots $$

Náhodná proměnná $X_i$ nabývá reálných hodnot $\mathbb{R}$.



### Stacionarita

Časová řada je **silně (striktně) stacionární**, pokud pro všechny okamžiky $t_1, ... t_k$ a nějaké celé číslo $h$ platí:

$$(X_{t_1}, ..., X_{t_k}) \stackrel{\text{D}}{=} (X_{t_1+h}, ..., X_{t_k+h})$$

tedy že záznamy jsou v určitých intervalech generované shodnou distribucí. Tj. budeme-li řadu pozorovat v nějakém časovém okně, potom na základě pozorování nejsme schopni rozlišit, kde (časově) je okno umístěné.

Časová řada je **slabě stacionární**, ak expectation (mean), rozptyl a autokorelácia sú v čase konštantné (vyššie momenty sa môžu líšiť). 
Intuitívne, ak sa pozerám na určité kontextové okno (výber) v čase $t$ a pozorujem $\mathbb{E}(X_t) = \mu$, $\text{Var}(X_t) = \sigma^2$, tak v ľuboľonom inom čase $t+m$ budem pozorovať rovnaké hodnoty $\mu$ a $\sigma^2$.

<!--  pokud pro konstantní $\mu$ a pro $\gamma_k$ nezávislé na $k$, platí: -->
<!-- 1. $\mathbb{E}(X_t) = \mu$ -->
<!-- 2. $cov(X_t, X_{t+k}) = \gamma_k$ -->

<!-- (slabou stacionaritu moc intuitivně nechápu) -->

### Klasická dekompozice

Většina skutečných časových řad není řadou nezávislých stejně rozdělených náhodných veličin ani stacionární časovou řadou. 

V klasické dekompozici se často předpokládá, že časovou řadu lze rozložit do čtyř komponent, které se dají lépe samostatně analyzovat: 

1. **Trend ($T_t$):** dlouhodobý průměrný pohyb
1. **Sezónní efekty ($I_t$):** pravidelné výkyvy související s kalendářem (např. počet nakoupených ponožek před Vánoci) (cyklické patterny s fixnou frekvenciou)
1. **Cyklické efekty ($C_t$):** jiné výkyvy, nemusí mít pravidelnou délku nebo velikost (např. růst nebo pokles ekonomiky)
1. **Resizuální ($E_t$):** Zbývající složka po odstranění trendů, sezónních a cyklických efektů z časové řady

Cílem dekompozice časových řad je rozložiť časovú radu na jednotlivé komponenty (trend, sezónnost, residuals), ktoré sú jednoduchšie interpretovateľné a pomôžu pri následnej analýze a prípadnej predikcii.

Klasická dekompozice má dvě základní varianty, additivní a multiplikativní.

V additivní se časová řada modeluje jako součet jednotlivých složek a je vhodnejšia ak veľkosť sezónnych výkyvov a rozptylov nezávisí od levelu časovej rady.

$$X_t = T_t + I_t + C_t + E_t$$

Multiplikativní je naopak vhodnejšie ak výkyvy a rozptyly sú proporčné s levelom časovej rady:

$$X_t = T_t \cdot I_t \cdot C_t \cdot E_t$$





### Diferencování časové řady

- jde o rozdíly sousedních měření a značí se $\Delta$:

$$ \Delta X_t = X_t - X_{t-1} $$

- vyjadřuje změny v originální řadě
- odstraňuje trend z časové řady
- zachovává "lokální" informaci
- diferencovaná řada je obvykle "více stacionární" než původní

Příklad:

![image](https://hackmd.io/_uploads/SksTp-Gr0.png)


Můžeme definovat i difference vyššího řádu:

$$ \Delta^2 X_t = \Delta(\Delta X_t) = (X_t - X_{t-1}) - (X_{t-1} - X_{t-2}) = X_t - 2X_{t-1} + X_{t-2}  $$

- diference přispívá stacionaritě, ale nezajisťuje ji
- diferenci můžeme opakovat, dokud nezajistíme stacionaritu
- v praxi obvykle stačí diference 2. řádu pro dosažení rozumné stacionarity


### Sliding window

Metoda rozdělení časové řady na překrývající se okna fixní délky. Každé okno je potom procesované nezávisle na ostatních. Zvolená velikost okna je důležitý hyperparametr - širší okno zvýší množsví zahrnutého kontextu a může zpřesnit trénovaný model, ale zárověň zvýší množství zpracovaných dat a výpočetní náročnost. Možnosť využiť dilated sliding window approach so stride parametrom pre zväčšenie kontextového okna pri zachovaní nárokov na compute.


### Klouzavý průměr a vyhlazování

Klouzavé průměry jsou statistiky počítané na časové řadě a slouží primárně k vyhlazování. Vyhlazování odstraňuje krátkodobé fluktuace (vysokofrekvenční šum) z řady.

Běžně používané:
- Jednoduchý klouzavý průměr (**SMA** - simple moving average)
    - průměr posledních $k$ měření:
    $$ Y_t = \frac{1}{k} \sum_{i=0}^{k-1} X_{t-i} $$
    ![image](https://hackmd.io/_uploads/HJa6ANfBR.png)

    - popřípadě symetricky kolem středu okna - průměr okolních $k$ měření:
    $$  Y_t = \frac{1}{k} \sum_{i=-\lfloor \frac{k}{2} \rfloor}^{\lfloor \frac{k}{2} \rfloor} X_{t+i}  $$
    
- Exponenciální klouzavý průměr (**EMA** - exponential moving average)
    - vážený průměr podle aktuálnosti
    - novější měření mají vyšší váhu
    - váha exponenciálně klesá se stářím
    - lze počítat rekurzivně (přepočítávat když mi přicházení nová měření)
    $$ Y_t = \alpha \cdot X_t + (1 - \alpha) \cdot Y_{t-1} $$
- Klouzavý medián
    - počítá medián v jednotlivých oknech
    - je robustní vůči anomálním chybným měřením


| Originální řada | Klouzavý průměr | Klouzavý medián |
| -------- | -------- | -------- |
| ![image](https://hackmd.io/_uploads/HkGZOffHR.png) | ![image](https://hackmd.io/_uploads/Hkt-OzzHA.png)     | ![image](https://hackmd.io/_uploads/BJR-OfzSA.png)


### Train-test split pro sekvence a časové řady

zdroj - paper z 2023 na splitting časových řad: https://arxiv.org/pdf/2307.14294
částečně sem si to vymyslel tho...

Dělení temporálních dat na trénovací a testovací sadu je důležitý hyperparametr a silně závisí na velikosti a typu dat a řešeném úkolu. 

U časových řad musíme správně rozdělit train-test split abychom se vyhnuli data leaku.

- **temporální splitting**: prvních $x$% časové řady je použito k tréninku, $(100-x)\%$ je pak použito k testování. Testujeme, jak model generalizuje z historických dat na budoucí - vhodné pro forecasting. Např.: predikce ceny akcie.
- **časová řada jako samostatné pozorování**: v případě, že máme více časových řad a bereme každou z nich jako samostatné pozorování. Testujeme, zda model generalizuje na jiné časové řady. Např.: klasifikace ptačího zpěvu.
- **náhodné splitování sliding windows**: pokud přistupujeme k oknům jako k nezávislým pozorováním, mohou se dát rozdělit náhodně do trénovací a testovací sady. Zde musíme ale zajistit, aby se trénovací a testovací okna vzájemně nepřekrývaly.



### Autoregresivní proces (AR)

V autoregresivních procesech jsou jednotlivé pozorování závislé na předchozích.

Formálně, AR řádu $p$ je pro konstanty $\phi_1, \phi_2, ..., \phi_p$ a nezávislé náhodné errory $\epsilon_t$ definovaný vztahem: 

$$X_t = \sum_{r=1}^{p} \phi_r X_{t-r} + \epsilon_t$$

kde $p$ značí na kolika předchozích pozorování je pozorování závislé. $\epsilon_t$ mají nulový průměr a konstantní rozptyl $\sigma^2$.


### Korelace a autokorelace

- je součástí [otázky statistika](https://hackmd.io/@uizd-suui/ryQrtIvzU)


### ARMA

ARMA (AutoRegressive Moving Average) model slouží pro predikování budoucích hodnot pro stacionárne časové řady (pre nestacionárne sa používa rozšírenie ARIMA). Skládá se ze dvou částí: Autoregresivní (AR) část a Moving average (MA) část

Rovnice pro $ARMA_{(p, q)}$ model, tj. model s autoregresivním modelem řádu $p$ a moving-average modelem řádu $q$: 

$$\hat{X_t} = \phi_0 +  \sum_{r=1}^{p} \phi_r X_{t-r} + \sum_{s=0}^{q} \theta_s \epsilon_{t-s}$$

1. **Autoregresivní (AR) část** 
    - $\sum_{r=1}^{p} \phi_r X_{t-r}$
    - popisuje vztah mezi současnou hodnotou a předešlými hodnotami
2. **Moving average (MA) část**
    - $\sum_{s=0}^{q} \theta_s \epsilon_{t-s}$
    - $\epsilon_{t-s}$ je chyba, které se model dopustil před $s$ kroky
    - předpokládáme, že $\epsilon_t$ jsou "white noise" - posloupnost nekorelovaných náhodných proměnných se střední hodnotou 0 a konstatním rozptylem


Proces je stacionární pro vhodné $\phi$ a $\theta$.

