--- 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$.