Cvičení 9
Shlukování k-means
Vojtěch Franc
Cílem tohoto cvičení je implementace algoritmu k-means pro shlukovou analýzu
dat. Algoritmus
-means iterativně hledá hodnoty
vektorů
tak, že minimalizuje střední odchylku mezi zadanou množinou dat
,
a vektory
, které mají k těmto datům nejmenší
euklidovskou vzdálenost. Neformálně řečeno
-means algoritmus aproximuje
množinu dat
vhodně zvolenými vektory.
K-means
Algoritmus
-means je skutečně jednoduchý. Jeho vstupem je množina dat
a číslo
udávající počet vektorů
,
.
Na začátku se inicializují vektory
,
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:
- Klasifikace: Všechna data
,
se klasifikují do tříd
určených vektry
,
podle minima euklidovské
vzdálenosti. Tedy vzor
je přiřazen do třídy
podle
.
- Přepočítání vektorů
: Vypočítají se nové hodnoty vektorů
jako střední hodnoty dat
, které byly klasifikovány do třídy
určené příslušným vektorem
. Tedy nová hodnota
se spočte
podle ztahu
,
kde
je poče vzorů
klasifikovaných v druhém kroku do třídy určené
vektorem
.
Kroky 1 a 2 se opakují do té doby dokud se alespoň jeden vektor
klasifikuje do jiné třídy než byl klasifikován v předcházejícím kroku.
Postupujte podle následujících bodů:
- Seznamte se algoritmem
-means popsaném v odstavci 2
a implementujte ho.
- Vygenerujte si datové množiny obsahující několik dobře
oddělitelných shluků. Použijte program
creatset ze Statistical Pattern Recognition
Toolboxu.
- Aplikujte algoritmus
-means na vygenerovaná data a výsledek,
tj. klasifikování dat do shluků, si zobrazte pomocí funkce
ppatterns.
Vojtech Franc
2001-12-05