courses:a6m33dvz:cviceni:04-shluky [CourseWare Wiki]

(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 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 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

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

R skript z hodiny: 04_skript_shlukovani.r.txt

Table of Contents