{{indexmenu_n>4}}


<timer 2000-01-01 00:00:01=2017-10-26 12:45:00>
Obsah této stránky bude přístupný od 26. 10. 2017.
Test: https://goo.gl/forms/1nRnCPNxmsQ1891K3
</timer>

<timer 2018-10-25 12:45:01=->
<WRAP center round box 80%>
**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?
</WRAP>
</timer>

<timer 2017-10-26 12:45:01=->

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

<code>
mydata <- na.omit(mydata) # smazání chybějících hodnot
mydata <- scale(mydata) # normalizace dat
</code>

==== 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ů.

<WRAP center round box 90%>
**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í.
</WRAP>


=== 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).

<code>
kc <- kmeans(data_bez_class, pocet shluku)
print(kc)
</code>

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

<code>
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")
}
</code>

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ů?

<WRAP center round box 90%>
**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. 
<code>
aggregate(data = teens, age ~ gradyear, mean, na.rm = TRUE)
</code>
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í?
</WRAP>



==== 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''.

<code>
library(mclust)
cl_gmm <- Mclust(data,G=pocet_shluku)
summary(cl_gmm)
plot(cl_gmm)
</code>

  * 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''

<code>

hc <- hclust(dist(zvirata[,2:14]), method="complete")
plot(hc, hang = -1, labels=zvirata[,1])

help(cutree)

</code>

  * Projděte si vytvořenou hierarchii.
  * Dendrogram lze vykreslit i pomocí celé řady pokročilých balíčků. Vyzkoušejte balíček ''dendextend''.
<code>
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
</code>
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)**. 
<WRAP group>
<WRAP half column>
**Standardní R kód pro vytváření dendrogramu**
<code>
data <- scale(USArrests)
dist.res <- dist(data)
hc <- hclust(dist.res, method = "ward.D2")
dend <- as.dendrogram(hc)
plot(dend)
</code>
</WRAP>

<WRAP half column>
**R kód pro vytváření dendrogramu pomocí řetězového operátoru**
<code>
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)
</code>
</WRAP>
</WRAP>

\\

<WRAP center round box 90%>
**Ú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:\\ 
<latex>
\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}
</latex>
  - 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.
</WRAP>

R skript z hodiny: {{courses:a6m33dvz:cviceni:04_skript_shlukovani.r.txt|04_skript_shlukovani.r.txt}}

</timer>