Cvičení 6 - Shluková analýza

A) Teoretický úvod

Shluková analýza se jako soubor matematických postupů používá v počítačovém vidění zpravidla ve dvou případech: v klasifikátorech (oblast rozpoznávání) a při segmentaci (oblast zpracování obrazu). V prvním případě je zvolená metoda shlukové analýzy aplikována na prostor příznaků, ve druhém přímo na prostor obrazové funkce. Pokud uvažujeme tento druhý případ, lze na obvyklý šedotónový obraz nahlížet jako na trojrozměrnou matici bodů, kdy dvě dimenze tvoří původní osy obrazu x a y a třetí dimenzi tvoří jasové hodnoty f(x,y).

Jednoduchou a současně účinnou nehierarchickou metodou shlukové analýzy je iterační metoda k-means. Tato metoda hledá pro zadanou množinu vstupních dat X={x1, x2, ..., xN} množinu středů shluků µ={µ1, µ2, ..., µk} tak, aby byla minimalizována chybová funkce J. Na následujícím obrázku je příklad dvojrozměrných vzorků rozdělených do tří shluků (vlevo množina X, vpravo barevně rozlišená skutečná příslušnost vzorků do tříd).

Skutečná příslušnost vstupních vzorků do tříd není v netrénovací množině samozřejmě známa, je pouze aproximována více či méně přesným výpočtem reprezentantů jednotlivých shluků. Jediným kritériem správnosti výpočtu je chybová funkce J, která je zpravidla definována jako střední kvadratická odchylka množiny vstupních dat X od množiny µ.

Pokud je minimalizována chybová funkce J lze říci, že množina vektorů µ aproximuje vstupní množinu dat X. Metodu k-means je možné aplikovat na libovolnou dimenzi vstupních dat a libovolný počet tříd (shluků reprezentovaných vektory µj). Shluková analýza má však teoretický význam jen tehdy, pokud k<N a prakticky dokonce jen pokud k<<N. Samotný algoritmus pracuje iterativně ve dvou krocích: klasifikace a učení. Krok klasifikace spočívá v zařazení každého z N vzorků xi do některé z k výstupních tříd yj podle konceptu nejbližšího souseda tj. vektor xi je zařazen do té třídy yj, k jejímuž středu µj má nejnižší euklidovskou vzdálenost.

Po kroku klasifikace následuje krok učení, tedy aktualizace souřadnic středů shluků µj podle aktuální příslušnosti vektorů xi do shluků. Nová hodnota středu shluku je vypočítána jako střední hodnota všech vektorů xi, které byly v dané iteraci klasifikovány do třídy yj reprezentované středem µj.

Oba dva kroky iteračního algoritmu se opakují do té doby, dokud se mění zařazení alespoň jednoho vstupního vzorku. Poté platí µj(t)=µj(t-1) pro všechna j, čímž algoritmus dokonvegroval do stabilního rozložení středů shluků. Ačkoliv jediným volitelným parametrem metody je počet shluků k, závisí výsledek výpočtu také na způsobu inicializace vektorů shluků µj před první iterací. Obvykle se používá buď náhodná inicializace vektorů µj v intervalu hodnot vstupních dat xi, anebo inicializace přiřazením prvních k vstupních dat xi vektorům µj.

B) Úkoly

  1. Sestavte funkci [X] = GenerateClusters(k,N,C,σ) pro generování vektoru náhodných vzorků X v dvojrozměrném prostoru. Celkový počet vzorků v rovině je dán počtem shluků k a počtem vzorků v jednom shluku N, množiny shluků mají tedy stejnou mohutnost. Rozložení vzorků ve shluku musí mít normální náhodné rozložení s nulovou střední hodnotou a směrodatnou odchylkou σ. Středy shluků jsou určeny maticí C, která obsahuje k dvojic souřadnic [xc yc].

  2. Pomocí funkce z minulého bodu vygenerujte a zobrazte testovací množinu vzorků s parametry (3,100,[1 1;2 1;x3 y3],0.2). Dvojici hodnot [x3 y3] navrhněte tak, aby středy shluků tvořily v rovině rovnostranný trojúhelník.

  3. Navrhněte a implementujte funkci [Y] = KMeansClustering(X,k) vracející vektor indexů Y příslušností vstupních vzorků X do k shluků. Sloupcový vektor Y má stejný počet řádků jako matice X, v níž každý řádek představuje jeden vzorek a hodnoty vektoru Y jsou indexy shluků (nabývají hodnot <1,k>). Inicializaci středů v první iteraci proveďte náhodně a funkci navrhněte tak, aby fungovala s libovolnou dimenzí vstupních vzorků (počet sloupců matice X).

  4. Na data z bodu 2 aplikujte shlukovou analýzu pomocí vámi vytvořené funkce a do jednoho okna vedle sebe zobrazte tři roviny: nezařazené vzorky, skrytou příslušnost a vzorky zařazené funkcí z předchozího bodu. Pro zobrazení skrytých příslušností využijte obvykle nedostupné znalosti o seřazení vzorků ve vektoru X (prvních N vzorků náleží shluku k1, dalších N vzorků náleží shluku k2 atd.). Vysvětlete rozdíly mezi výsledkem klasifikace a skutečnou příslušností.

  5. Do jednoho okna zobrazte barevně odlišené trajektorie pohybu středů shluků během iteračního výpočtu a do titulku grafu vypište hodnoty chybové funkce všech iterací (střední kvadratická odchylka X od µ). Potřebná data si zajistěte úpravou rozhranní funkce pro shlukovou analýzu a úsečkami vyznačte postupný posun středů až do poslední iterace.

  6. Zodpovězte následující otázky:

    • co nastane v případě k = N?
    • vysvětlete zda je zaručena konvergence vstupních dat do právě k shluků?

C) Dobré vědět

  • Povolené funkce: randn, rand, norm, sum

  • Nepovolené funkce: kmeans

D) Ilustrace výsledků