{{indexmenu_n>4}}
Obsah této stránky bude přístupný od 26. 10. 2017.
Test: https://goo.gl/forms/1nRnCPNxmsQ1891K3
**TEST 03**\\
- (0.5 b) Stručně popiště klasifikátor //n nejbližších sousedů// (k-NN). Jak probíhá učící a klasifikační fáze? Proč je tento klasifikátor nevhodný pro velké trénovací množiny?
- (0.5 b) Uvažujte trénovací množinu S se 100 prvky (|S| = 100). Klasifikátor datům z S přiřazuje klasifikační atribut //y//, který má jen 2 hodnoty {0,1}. K 30 záznamům z S bylo přiřazeno y=0, k 70 záznamům pak y=1. Spočtěte entropii množiny S vzhledem k dané klasifikaci. (Nápověda: $\log_2 0.3 = -1.7$, $\log_2 0.7 = -0.5$).
- (0.5 b) Co je přeučení klasifikátoru? Co platí pro chybu na trénovací a testovací množině při přeučeném klasifikátoru?
===== Cvičení 4 - Shluková analýza =====
V dnešním cvičení opět využijeme několik souborů s daty - všechny jsou v následujícím souboru {{courses:a6m33dvz:cviceni:cviceni_10_shluky.zip|cviceni_10_shluky.zip}}
=== Shluková analýza ===
- Co je shluková analýza?
- Jaký je rozdíl mezi hierarchickými a nehierarchickými metodami?
- Vysvětlete princip algoritmu k-means.
- Vysvětlete proč je nutná normalizace dat při shlukování.
=== Příprava dat ===
Při shlukování je **vždy** nutné přemýšlet o normalizaci dat.
mydata <- na.omit(mydata) # smazání chybějících hodnot
mydata <- scale(mydata) # normalizace dat
==== Algoritmus k-means ====
K-means je shlukovací algoritmus, jehož cílem je nalezení takových shluků jednotlivých pozorování, které budou minimalizovat vzdálenost ke středům shluků.
**Algoritmus k-means**
**Vstup:** Množina pozorování $T = \{\mathbf{x_1}, ..., \mathbf{x_n}\}$, počet shluků K, maximální počet iterací.\\
**Výstup:** Množina prototypů shluků $\{\mathbf{c_1}, ..., \mathbf{c_K}\}$
//Inicializace:// Nastavíme středy $\{\mathbf{c_1}, ..., \mathbf{c_K}\}$ na různé náhodně vybrané vstupní pozorování $\mathbf{x_i}$.
Kroky:
- //Přiřaď// (klasifikuj) pozorování $\{\mathbf{x_l}\}^L_{l=1}$ do shluku náležejícího k nejbližšímu středu $\{\mathbf{c_k}\}^K_{k=1}$.
- //Nastav// středy $\mathbf{c_k}$ na střední hodnotu všech vektorů $\mathbf{x_l}$ patřících do k-té třídy.
Opakuj body 1 a 2, dokud se přiřazení do tříd mění a ještě nebyl překročen stanovený maximální počet iterací.
=== Tvary shluků ===
Vyzkoušejte postupně algoritmus k-means na datových souborech ''kruhy.csv'' a ''tvary.csv''. Pozor, nezapomeňte vyloučit atribut class ze shlukování. Atribut class použijte pouze pro vizualizaci shluků. Zvolte počet shluků roven 3 (parametr ''k''=3).
kc <- kmeans(data_bez_class, pocet shluku)
print(kc)
* Jak se shodují shluky získané shlukovou analýzou se shluky v datech? Porovnejte pomocí vizualizace.
* Jaká je nevýhoda algoritmu k-means vzhledem k tvaru shluků?
* Vyzkoušejte, jaké výsledky dává kmeans, pokud bychom v datech čekali 2 resp. 4 shluky. Porovnejte.
=== Počet shluků ===
U algoritmu k-means je nutné nastavit počet shluků. Ukážeme si, jak je možné počet shluků volit.
Vyzkoušejte následující funkci v R.
cluster_num_plot <- function(data,n){
result <- vector(length=n-1)
for(i in 2:n){
cl <- kmeans(data, i)
result[i-1] <- sum(cl$withinss)
}
plot(2:n,result,xlab="počet shluků", ylab="průměrná vzdálenost")
}
Funkce provede postupně shlukování metodou ''kmeans'' pro počet shluků ''1'' až ''n''. Kvalitu shlukování odhadneme pomocí parametru ''cl$withinss'' (průměrnou vzdálenost uvnitř všech shluků) a uložíme do vektoru ''result''. Následně vykreslíme závislost počtu shluků na objektivní funkci (použijeme právě průměrnou vzdálenost uvnitř všech shluků).
* Jak byste na základě obrázku odhadli optimální počet shluků?
**Praktická úloha 1**
Pro tuto úlohu si stáhněte soubor {{courses:a6m33dvz:cviceni:snsdata.txt|snsdata.txt}} s daty získaných z profilů sociální sítě 30 000 amerických teenagerů. Tento dataset obsahuje infomaci o ročníku střední školy (celkem 4 ročníky), pohlaví, věku a počtu přátel studenta. Dále byl profil každého ze studentů zpracován metodami text miningu a zaznamenán počet výskytů každého z 36 vytipovaných klíčových slov.
* Zjistěte poměr počtu chlapců a dívek. Nacházíme nějaká chybějící data? Pokud ano, vytvořte pro jejich reprezentaci kategorickou proměnnou 0/1.
* Zkoumejte příznak ''age''. Jsou v datech chybějící hodnoty? Za teenagera považujeme pouze člověka ve věku 13-19 let. Věk subjektů mimo toto rozpětí nahraďte průměrným věkem studentů v příslušném studijním ročníku.
Použijte funkci ''aggregate()'' pro výpočet statistiky nad skupinami.
aggregate(data = teens, age ~ gradyear, mean, na.rm = TRUE)
Pro vytvoření nového sloupce s průměrným věkem ve skupině využijte funkci ''ave()'' s příslušnými parametry.
* Proveďte shlukování pomocí ''kmeans()'' s 5 shluky. Využijte příznaků 5:40. Nezapomeňte je znormalizovat. Abychom na cvičení mohli všichni sledovat stejné výsledky, tak ještě před provedením funkce ''kmeans()'' proveďte příkaz ''set.seed(2345)''.
* Zkontrolujte velikost shluků a jejich středy. Co můžeme o shlucích prohlásit? Jaké skupiny teenagerů představují?
* Pomocí funkce ''aggregate'' zjistěte průměrný věk, rozložení pohlaví a počet přátel subjektů v jednotlivých shlucích? Odpovídají výsledky očekávání?
==== Gaussian mixture model estimated by expectation maximization algorithm ====
{{:courses:a6m33dvz:cviceni:mixture_old_kiwi.jpg?400|}}\\
//Bishop, C.: Pattern Recognition and Machine Learning, Springer, 2011//
Gaussian mixture model je flexibilnější než algoritmus k-means. Porovnejte výsledky shlukování pomocí k-means a pomocí GMM EM na datech ''tvary.csv''.
library(mclust)
cl_gmm <- Mclust(data,G=pocet_shluku)
summary(cl_gmm)
plot(cl_gmm)
* Jak funguje EM algoritmus
* jaké parametry má GMM
* Jak byste zhodnotili výsledky k-means a GMM EM na datech ''tvary.csv''
==== Hierarchické shlukování ====
Vyzkoušejte hierarchické shlukování na datovém souboru ''zvirata.csv'' a známých ''iris''
hc <- hclust(dist(zvirata[,2:14]), method="complete")
plot(hc, hang = -1, labels=zvirata[,1])
help(cutree)
* Projděte si vytvořenou hierarchii.
* Dendrogram lze vykreslit i pomocí celé řady pokročilých balíčků. Vyzkoušejte balíček ''dendextend''.
library(dendextend)
library(magrittr)
dend <- zvirata[,2:14] %>%
dist %>%
hclust(method = "complete") %>%
as.dendrogram
dend %>% set("labels", zvirata[,1]) %>% set("labels_col", value = c("green", "blue"), k=2) %>% plot
Balíček ''magrittr'' navíc umožňuje pohodlné používání řetězového operátoru - //pipe//. Místo **f(x, y)** lze tak psát **x %>% f(y)**.
**Standardní R kód pro vytváření dendrogramu**
data <- scale(USArrests)
dist.res <- dist(data)
hc <- hclust(dist.res, method = "ward.D2")
dend <- as.dendrogram(hc)
plot(dend)
**R kód pro vytváření dendrogramu pomocí řetězového operátoru**
dend <- USArrests[1:5,] %>% # data
scale %>% # Scale the data
dist %>% # calculate a distance matrix,
hclust(method = "ward.D2") %>% # Hierarchical clustering
as.dendrogram # Turn the object into a dendrogram.
plot(dend)
\\
**Úloha 2**
Uvažujte následujících 7 datových záznamů, z nichž se každý skládá ze 2 příznaků: $p_1 = (0.5, 2.0)$, $p_2=(2.5, 3.0)$, $p_3=(4.2, 0.7)$, $p_4=(5.5, 0.3)$, $p_5=(4.8, 3.5)$, $p_6 = (7.0, 2.5)$, $p_7=(8.5, 2.8)$. Matice Eukleidovských vzdáleností mezi jednotlivými body je uvedena v následující tabulce:\\
\begin{table}[ht]
\centering
\begin{tabular}{rrrrrrrr}
\hline
& $p_1$ & $p_2$ & $p_3$ & $p_4$ & $p_5$ & $p_6$ & $p_7$ \\
\hline
$p_1$ & 0.00 & 2.24 & 3.92 & 5.28 & 4.55 & 6.52 & 8.04 \\
$p_2$ & 2.24 & 0.00 & 2.86 & 4.04 & 2.35 & 4.53 & 6.00 \\
$p_3$ & 3.92 & 2.86 & 0.00 & 1.36 & 2.86 & 3.33 & 4.79 \\
$p_4$ & 5.28 & 4.04 & 1.36 & 0.00 & 3.28 & 2.66 & 3.91 \\
$p_5$ & 4.55 & 2.35 & 2.86 & 3.28 & 0.00 & 2.42 & 3.77 \\
$p_6$ & 6.52 & 4.53 & 3.33 & 2.66 & 2.42 & 0.00 & 1.53 \\
$p_7$ & 8.04 & 6.00 & 4.79 & 3.91 & 3.77 & 1.53 & 0.00 \\
\hline
\end{tabular}
\end{table}
- Na tato data aplikujte základní aglomerativní hierarchický shlukovací algoritmus. Jako míru vzdálenosti dvou shluků zvolte vzdálenost jejich dvou nejbližších prvků (//single link//): $D(X,Y)=\min_{x \in X, y \in Y} d(x,y)$. Výsledek znázorněte ve formě **dendrogramu**.
- Nyní zopakujte předchozí postup, ale jako míru vzdálenosti dvou shluků volte vzdálenost jejich 2 nejvzdálenějších prvků (//complete link//): $D(X,Y)=\max_{x \in X, y \in Y} d(x,y)$. Porovnejte výsledky.
R skript z hodiny: {{courses:a6m33dvz:cviceni:04_skript_shlukovani.r.txt|04_skript_shlukovani.r.txt}}