Shluková analýza

Shluková analýza (též clusterová analýza, anglicky cluster analysis) je vícerozměrná statistická metoda, která se používá ke klasifikaci objektů. Slouží k třídění jednotek do skupin (shluků) tak, aby si jednotky náležící do stejné skupiny byly podobnější než objekty z ostatních skupin. Shlukovou analýzu je možné provádět jak na množině objektů, z nichž každý musí být popsán prostřednictvím stejného souboru znaků, které má smysl v dané množině sledovat, tak na množině znaků, které jsou charakterizovány prostřednictvím určitého souboru objektů, nositelů těchto znaků.

Klasifikace shlukovacích metod

Základní členění shlukovacích metod podle cíle je na hierarchické a nehierarchické metody.

# Hierarchické shlukování vytváří systém podmnožin, kde průnikem dvou podmnožin - shluků je buď prázdná množina, nebo jeden z nich. Pokud nastane alespoň jednou druhý případ, je systém hierarchický. +more Tedy je to jakési větvení, zjemňování klasifikace. K hierarchickému shlukování lze přistupovat ze dvou stran - rozlišujeme přístup divizní (vycházíme z celku, jednoho shluku, a ten dělíme) a aglomerativní (vycházíme z jednotlivých objektů, shluků o jednom členu, a ty spojujeme). Hierarchické shlukování nabízí více alternativních řešení, výsledek shlukování je pak možné vyjádřit dendrogramem. Tato metoda však není vhodná pro velké datové soubory. # Nehierarchické shlukování vytváří takový systém, kde je jsou shluky disjunktní množiny. Používá se nejčastěji algoritmus k-means.

Měření podobnosti objektů

Shluková analýza vychází z podobnosti, resp. vzdálenosti objektů. +more Její kvantitativní vyjádření je jedním ze základních problémů clusterové analýzy. Existuje mnoho způsobů konstrukce tohoto ukazatele.

Vlastnosti vzdálenosti

Standardními požadavky pro vhodný předpis míry vzdálenosti (metriky) d dvou objektů O_i a O_j jsou: * nezápornost: d(O_i, O_j) \ge 0; * symetrie: d(O_i, O_j) = d(O_j, O_i); * shodné objekty by měly mít ukazatel vzdálenosti roven 0: d(O_i, O_i) = 0 (zároveň míra podobnosti bude rovna maximální hodnotě, obvykle 1). * trojúhelníková nerovnost: d(O_i, O_j) \le d(O_i, O_h) + d(O_h, O_j).

Příklady ukazatelů

metriky - základní je eukleidovská vzdálenost a od ní jsou odvozeny další ukazatele (např. čtverec euklidovské vzdálenosti), další metriky jsou Manhattanská, Čebyševova ad. +more) * koeficienty asociace - určeny pro hodnocení podobnosti pro objekty vyjádřené dichotomickými znaky, ukazatele založeny na počtu shod a počtu znaků. Konkrétních ukazatelů je celá řada, některé operují jen s pozitivními shodami (např. koeficient Jaccardův, Russel & Rao, Diceův ad. ), některé i s negativními (např. Sokalův, Hamannův). Mohou se vztahovat k celkovému počtu znaků, k počtu rozdílných případů nebo k různým kombinacím předchozích. * korelační koeficient - hodí se především pro shlukování proměnných.

Existuje řada dalších způsobů měření vzdálenosti či podobnosti (míry asymetrie, Lambda, kosinus vektorů, chí-kvadrát). Někdy je způsob hodnocení podobnosti/vzdálenosti přímo dán shlukovací metodou. +more I pokud tomu tak není, je třeba při výběru ukazatele brát v úvahu metodu shlukování a charakter souboru.

Metody hierarchického shlukování

Existují různé přístupy, jak shlukovat objekty na základě jejich vzdálenosti či podobnosti. Mezi základní metody patří: * metoda nejbližšího souseda (single linkage, nearest neighbor) - vzdálenost shluků je určována vzdáleností dvou nejbližších objektů z různých shluků. +more Při použití této metody jsou objekty taženy k sobě, výsledkem jsou dlouhé řetězy. * metoda nejvzdálenějšího souseda (complete linkage, furthest neighbor) - vzdálenost shluků je určována naopak vzdáleností dvou nejvzdálenějších objektů z různých shluků. Funguje dobře především v případě, že objekty tvoří přirozeně oddělené shluky, nehodí se, pokud je tendence k řetězení. * centroidní metoda - vzdálenost shluků je určována vzdáleností jejich center (hypotetická jednotka s průměrnými hodnotami znaků). Může být nevážená nebo vážená. Ta zohledňuje velikosti shluků a je vhodná pokud očekáváme jejich rozdílnost. Užívá se vyjádření vzdálenosti objektů čtvercovou euklidovskou vzdáleností. * párová vzdálenost (pair-group average) - vzdálenost shluků je určována jako průměr vzdáleností všech párů objektů z různých shluků. Opět může být ve vážené i nevážené podobě. * Wardova metoda - vychází z analýzy rozptylu. Slučuje takové shluky, kde je minimální součet čtverců. Obecně lze říci, že je tato metoda velmi účinná, nicméně má tendenci vytvářet poměrně malé shluky. Vzdálenosti objektů se měří čtvercovou euklidovskou vzdáleností.

Odkazy

Použitá literatura

A. Lukasová, J. Šarmanová: Metody shlukové analýzy. SNTL, Praha 1985.

Externí odkazy

Detailnější rozbor včetně matematického aparátu [https://web. archive. +moreorg/web/20100601174454/http://gerstner. felk. cvut. cz/biolab/X33BMI/slides/KMeans. pdf] * Kapitola z české online učebnice prostorových analýz [http://gis. vsb. cz/pad/Kap_6/kap__6_5_1. htm] * Kapitola z anglické online učebnice statistiky (anglicky)[url=http://www. statsoft. com/textbook/stcluan. html#d]] * Popis a ukázka aplikace některých shlukovacích [[Algoritmus|algoritmů[/url]] - fuzzy shluková analýza, shlukování kolem medoidů (PAM) a CLARA - a prostředků k hodnocení klasifikačního modelu (silhouette plot) [url=http://data. tulipany. cz/ClustR. pdf]].

[[Kategorie:Data mining[/url]] Kategorie:Matematická statistika