Shluková analýza

Metody shlukové analýzy se používají pro klasifikaci objektů. Cílem je vytvořit takové skupiny, v rámci kterých jsou jednotlivé objekty maximálně podobné a zároveň jednotlivé skupiny jsou vzájemně od sebe maximálně odlišné. Shlukové analýzy se dělí v zásadě na hierarchické a nehierarchické metody. My se v rámci tohoto cvičení budeme zabývat právě těmi nehierarchickými metodami. Jedná se o takové metody,které nevytváří žádnou hierarchickou strukturu. Ve výsledku je průnik výsledných shluků prázdný, jedná se tedy o disjunktní množiny. Většina metod začíná s předem daným roztříděním do shluků. Toto roztřídění se dále upravuje a hledá se optimální rozdělení do kategorií. Nalezení nejlepšího rozdělení do shluků posouzením všech možných alternativ je často nemožný. Mezi tyto metody patří např. metoda k-means, k-medoids, model-based clustering.

Teoretické poznatky k těmto metodám, stejně jako k rozhodovacím stromům, získáte z prezentace doc. Radoslava Harmana z Univerzity Komenského v Bratislavě.

Metoda k-means

Tento algoritmus třídí jednotlivé objekty do shluků na základě jejich vlastností. Před spuštěním tohoto algoritmu je potřeba definovat celkový počet shluků, který musí být opět menší než je celkový počet objektů a maximální počet iterací. Algoritmus přiřazuje každý objekt do shluku, k jehož středu je nejblíže. Středy shluků se při každé iteraci přepočítají jako aritmetické průměry všech bodů shluku. Cílem je minimalizovat funkcionál součtu vzdáleností objektů od středu daného shluku. Existuje celá řada postupů, jak vyřešit tento problém, nicméně všechny tyto postupy přináší jen “dobré” řešení, které není vždy optimální. Příkladem může být Lloydův algoritmus:

1. vytvoří náhodný počet shluků, který byl uživatelem definován
2. v cyklu s počtem opakování definovaným uživatelem nebo dokud bude docházet ke zlepšení bude:
3. vypočítá centroidy shluků
4. vytvoří nový shluk pro všechny objekty, které jsou blíže k centroidu nového shluku než ke kterémukoliv jinému centroidu shluku.

Metoda je výhodná vzhledem ke své rychlosti a jednoduchosti, dokáže také pracovat s velkým počtem vstupních dat a to v konečném počtu iterací. Nevýhodou je nutnost stanovení předem daného počtu shluků. K-means je negativně ovlivněna existencí izolovaných a vzdálených objektů (ovlivnění průměru). Rozdílné počáteční umístění centroidů shluků mohou vést k různým výsledkům. Doporučuje se tak provést metodu několikrát s různými počátky. Metoda je citlivá na jednotky, pokud jsou vstupní ukazatele v různých jednotkách nebo silně variabilní, je lepší provést standardizaci.

Pro výpočet v R použijeme funkci kmeans() z balíčku stats:

kmeans (x, centers, iter.max, nstart, algorithm)

kde argument x je datový rámec nebo vektory hodnot; centers je počet shluků; iter.max je maximální počet iterací, nstart je počet restartů a algorithm je použitá metoda (Hartigan-Wong, Lloyd, Forgy, MacQueen).

Jednou z klíčových otázek při použití metody k-means je definování počtu shluků. K odhadnutí optimálního počtu shluků je vyvinuta řada postupů a my si představíme jednu z grafických heuristik, která se nazývá elbow method. Tato metoda spočívá v grafickém posouzení a hledání “zlomu, lokte”. Pro vykreslení grafu je potřeba redukovat prostor pro zobrazení ve 2D grafu. K tomuto cíli je vhodné opět použít metodu PCA a vykreslit závislost rozptylu na počtu hlavních komponent. Z grafu níže (data s relativními čísly pro obce ze SLDB 2011) je patrné, že optimální počet shluků jsou dva.

Když víme počet shluků, je potřeba připravit datovou matici, která bude vstupovat do výpočtu k-means, tzn. vytvořit matici jen s číselnými ukazateli, kterou si nazveme dataKM. Nyní můžeme spustit metodu k-means, která rozdělí obce do dvou shluků.

clusters=kmeans(dataKM, 2, 50, 5, “Lloyd”)

clusters$size # tento příkaz zobrazí počty objektů v jednotlivých shlucích

V prvním shluku máme 2874 obcí a v druhém shluku máme pak 3372 obcí. Je potřeba zmínit, že jsme pracovali v třinácti-rozměrném prostoru, tedy jakákoliv vizualizace výsledků je problematická. Nyní můžeme v originálních datech přidat sloupec, který si pojmenujeme “shluk” a do tohoto sloupce zapíšeme výslednou příslušnost ke shluku a to příkazem clusters$cluster. Parametr cluster vrací číslo shluku.

K-means shlukování v prostředí R

K-means shlukování v prostředí IBM SPSS Statistics

Metoda k-medoids

Tato metoda se liší oproti k-means tím, že se nepoužívají centroidy shluků, ale nejvíce centrální objekty – nejreprezentativnější objekt – každého shluku. Nevytváří se tedy centroid kdekoliv v n-rozměrném prostoru, ale vybírá se jeden z objektů. Toto nám tedy umožňuje stanovovat odlišnosti mezi objekty – shluk je tedy tvořen objekty s nejmenší odlišností od reprezentanta daného shluku. Opět existuje několik algoritmů pro optimální vyřešení tohoto problému. Jedním z nich je např. algoritmus PAM – Partitioning around medoids:

1. je náhodně vybráno k objektů – počáteční reprezentanti
2. v cyklu s počtem opakování definovaným uživatelem nebo dokud bude docházet ke zlepšení bude:
3. provede shlukování na základě přiřazení každého objektu k nejbližšímu medoidu a vypočte výslednou funkci
4. pro všechny páry objekt-medoid se snaží zlepšit výslednou funkci tak, že vybírá nové medoidy a z medoidů se stávají běžné objekty.

Výhody této metody jsou podobné jako v případě k-means metody – je rychlá, jednoduchá, s konečným počtem iterací. Oproti k-means je méně citlivá na odlehlé hodnoty a umožňuje využít odlišnosti objektů. K nevýhodám patří opět dosažení různých výsledků vzhledem k různému počátečnímu výběru medoidů. Opět se tak doporučuje provést celý výpočet několikrát. Výsledné shluky rovněž závisí na jednotkách a rozptylu a doporučuje se opět provést standardizaci.

Pro výpočet v R použijeme funkci pam, která je součástí balíčku cluster.

pam(x, k, diss, metric, medoids, stand, …)

kde x je skupina vektorů nebo matice odlišností; k definuje počet shluků; argumentem diss definujete, zda x je je matice odlišností; argumentem metric vybíráte použitou metriku (euclidean nebo manhattan); medoids obsahuje vektor vstupních medoidů a stand má hodnotu TRUE pokud chceme data standardizovat.

Silueta – the silhouette

Jistě je důležité ověřit, zda shlukování, které jsme vytvořili je dobré, resp. rádi bychom zjistili, jak je shlukování dobré. Silueta vybraného objektu měří, jak dobře je daný objekt shlukován ve shluku. Výsledná hodnota této metody je z intervalu <-1, 1>, kdy pokud je hodnota blízko 1, tak je objekt dobře shlukován, pokud je blízko 0, tak je na hranici daného shluku a pokud je menší než 0, tak je objekt pravděpodobně shlukován ve špatném shluku.

Pro SPSS je možné stáhnout extenzi.

Model-based clustering

Tato metoda je další alternativou pro nehierarchické shlukování. Oproti předchozím dvěma metodám je tato metoda více obtížná a zároveň komplikovanější. Zároveň je komplexnější. Nelze použít jen rozdílnosti, jako je tomu u k-medoids. Mezi výhody patří tvar výsledných shluků, které mají více eliptický tvar, zatímco u předchozích mají spíše kruhový tvar (resp. koule). Výsledky nezávisí na jednotkách ukazatelů, není tedy nutné standardizovat. Umožňuje najít tzv. skryté shluky, které jsou uvnitř jiných více rozptýlených shlucích. Umožňuje také testování nejlepšího počtu shluků.

V R je tato metoda implementována ve funkci Mclust(), která je součástí knihovny mclust.

Mclust(data, modelNames,…)

kde data je datový rámec vektorů proměnných, modelNames pak definuje použitý model (EII, VII, EEI, VEI, EVI, VVI, EEE, EEV, VEV, VVV).

Samostatná práce

• Použijte stejná data, jako pro samostatný úkol z PCA.
• Spusťte metodu k-means na daná data a definovaný počet shluků.
• Uložte příslušnost ke shluku do nového sloupce a posuďte kvalitu shlukování dle siluety.
• Posuďte výsledky a případně spusťte k-means na jiný počet shluků.
• Porovnejte výsledky a interpretujte.
• Termín odevzdání: 31. 5. 2020

Data – SLDB 2011 a výsledky voleb na úrovni okresů

Cvičení je vytvořeno v rámci projektu Inovace bakalářských a magisterských studijních oborů na Hornicko-geologické fakultě VŠB-TUO pod číslem CZ.1.07/2.2.00/28.0308. Tento projekt je realizován za spoluúčasti EU.