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