Cvičení 9
Shlukování k-means

Vojtěch Franc

Úvod

Cílem tohoto cvičení je implementace algoritmu k-means pro shlukovou analýzu dat. Algoritmus $k$-means iterativně hledá hodnoty $k$ vektorů $\mu_1, \mu_2, ...,\mu_k$ tak, že minimalizuje střední odchylku mezi zadanou množinou dat $x_1,...,x_l$, $l > k$ a vektory $\mu_i$, které mají k těmto datům nejmenší euklidovskou vzdálenost. Neformálně řečeno $k$-means algoritmus aproximuje množinu dat $k$ vhodně zvolenými vektory.

K-means

Algoritmus $k$-means je skutečně jednoduchý. Jeho vstupem je množina dat $x_1, x_2,...,x_l$ a číslo $k$ udávající počet vektorů $\mu_j$, $j=1,...k$. Na začátku se inicializují vektory $\mu_j$, $j=1,...,k$ na náhodně zvolenou hodnotu nebo použitím nějaké vhodně zvolené heuristiky (např. využívající apriorní znalost o úloze). Po inicializaci se začnou iterativně opakovat následující dva kroky:

1. Klasifikace: Všechna data $x_i$, $i=1,...,l$ se klasifikují do tříd určených vektry $\mu_i$, $j=1,...,k$ podle minima euklidovské vzdálenosti. Tedy vzor $x_i$ je přiřazen do třídy $y_i$ podle $y_i=\mathop{\rm argmin}\limits_{j=1,...,k} \vert\vert x_i - \mu_j\vert\vert$.
2. Přepočítání vektorů $\mu_j$: Vypočítají se nové hodnoty vektorů $\mu_j$ jako střední hodnoty dat $x_i$, které byly klasifikovány do třídy určené příslušným vektorem $\mu_j$. Tedy nová hodnota $\mu_j$ se spočte podle ztahu $\mu_j = \frac{1}{l_j} \sum\limits_{i=1, \atop y_i=j}^l x_i$, kde $l_j$ je poče vzorů $x_i$ klasifikovaných v druhém kroku do třídy určené vektorem $\mu_j$.

Kroky 1 a 2 se opakují do té doby dokud se alespoň jeden vektor $x_i$ klasifikuje do jiné třídy než byl klasifikován v předcházejícím kroku.

Zadání úlohy

Postupujte podle následujících bodů:

1. Seznamte se algoritmem $k$-means popsaném v odstavci 2 a implementujte ho.
2. Vygenerujte si datové množiny obsahující několik dobře oddělitelných shluků. Použijte program creatset ze Statistical Pattern Recognition Toolboxu.
3. Aplikujte algoritmus $k$-means na vygenerovaná data a výsledek, tj. klasifikování dat do shluků, si zobrazte pomocí funkce ppatterns.