V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!

Shluková analýza

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
m (1 revizi)
m (Nahrazení textu „</math>“ textem „\)</big>“)
 
(Nejsou zobrazeny 2 mezilehlé verze.)
Řádka 1: Řádka 1:
-
{{Wikipedia-cs|Shluková analýza|700}}
+
'''Shluková analýza''' (též '''clusterová analýza''', [[angličtina|anglicky]] cluster analysis) je [[vícerozměrné statistické metody|vícerozměrná]] [[statistika|statistická]] metoda, která se používá ke [[klasifikace|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 ze skupin různých. Shlukovou analýzu je možné provádět jak na [[množina|množině]] objektů, z nichž každý musí být popsán prostřednictvím stejného souboru [[znak (lingvistika)|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ů.
 +
 +
== Dělení shlukovacích metod ==
 +
Základní dělení shlukovacích metod podle cíle, ke kterému směřují, je na hierarchické a nehierarchické.
 +
 +
# ''Hierarchické shlukování'' je systém [[podmnožina|podmnožin]], kde [[průnik]]em 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ý. 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í, celý proces shlukování je pak možné vyjádřit [[dendrogram]]em. Tato metoda však není vhodná pro velké datové soubory.
 +
# ''Nehierarchické shlukování'' je takový systém, kde je průnik shluků prázdný, jedná se o [[disjunkce|disjunktní]] množiny.
 +
 +
== Měření podobnosti objektů ==
 +
Shluková analýza vychází z podobnosti, resp. vzdálenosti objektů. Její kvantitativní vyjádření je jedním ze základních problémů clusterové analýzy. Existuje mnoho způsobů sestrojení tohoto ukazatele.
 +
 +
=== Vlastnosti vzdálenosti ===
 +
Standardními požadavky pro vhodný předpis míry vzdálenosti <big>\(d\)</big> dvou objektů <big>\(O_i\)</big> a <big>\(O_j\)</big> jsou:
 +
* nezápornost: <big>\(d(O_i, O_j) \ge 0\)</big>;
 +
* symetrie: <big>\(d(O_i, O_j) = d(O_j, O_i)\)</big>;
 +
* shodné objekty by měly mít ukazatel vzdálenosti roven 0: <big>\(d(O_i, O_i) = 0\)</big> (zároveň míra podobnosti bude rovna maximální hodnotě, obvykle 1).
 +
* trojúhelníková nerovnost: <big>\(d(O_i, O_j) \le d(O_i, O_h) + d(O_h, O_j)\)</big>
 +
 +
=== Příklady ukazatelů ===
 +
* [[metrika|metriky]] - základní je [[eukleidovská metrika|eukleidovská vzdálenost]] a od ní jsou odvozeny další ukazatele (např. čtverec euklidovské vzdálenosti), další metriky jsou [[Manhattanská metrika|Manhattan]]ská, [[Čebyšev]]ova ad.)
 +
* [[koeficient asociace|koeficienty asociace]] – určeny pro hodnocení podobnosti pro objekty vyjádřené [[dichotomie|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ř. [[ Jaccardův koeficient |koeficient Jaccardův]], Russel & Rao, [[Diceův koeficient |Diceův]] ad.), některé i s negativními (např. [[Solkalův koeficient |Sokalův]], [[Hamannův koeficient |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íra asymetrie|míry asymetrie]], Lambda, [[kosinus]] [[vektor]]ů, [[Test_dobré_shody|chí-kvadrát]]). Někdy je způsob hodnocení podobnosti/vzdálenosti přímo dán shlukovací metodou. 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é způsoby, 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ů. 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 klastrů a hodí se, pokud očekáváme jejich rozdílnost. Požaduje 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ýza rozptylu|analýzy rozptylu]]. Vybírá takové shluky ke sloučení, kde je minimální součet čtverců. Obecně lze říci, že je tato metoda velmi účinná, ale má tendenci tvořit poměrně malé shluky. Požaduje vyjádření vzdálenosti objektů čtvercovou euklidovskou vzdáleností.
 +
 +
== 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 [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)[http://www.statsoft.com/textbook/stcluan.html#d]
 +
* Popis a ukázka aplikace některých shlukovacích algoritmů - fuzzy shluková analýza, shlukování kolem medoidů (PAM) a CLARA - a prostředků k hodnocení klasifikačního modelu (silhouette plot) [http://data.tulipany.cz/ClustR.pdf]
 +
 +
 +
{{Článek z Wikipedie}}
[[Kategorie:Statistika]]
[[Kategorie:Statistika]]

Aktuální verze z 14. 8. 2022, 14:53

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 ze skupin různých. 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ů.

Obsah

Dělení shlukovacích metod

Základní dělení shlukovacích metod podle cíle, ke kterému směřují, je na hierarchické a nehierarchické.

  1. Hierarchické shlukování je 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ý. 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í, celý proces shlukování je pak možné vyjádřit dendrogramem. Tato metoda však není vhodná pro velké datové soubory.
  2. Nehierarchické shlukování je takový systém, kde je průnik shluků prázdný, jedná se o disjunktní množiny.

Měření podobnosti objektů

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

Vlastnosti vzdálenosti

Standardními požadavky pro vhodný předpis míry vzdálenosti \(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ů

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. 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é způsoby, 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ů. 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 klastrů a hodí se, pokud očekáváme jejich rozdílnost. Požaduje 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. Vybírá takové shluky ke sloučení, kde je minimální součet čtverců. Obecně lze říci, že je tato metoda velmi účinná, ale má tendenci tvořit poměrně malé shluky. Požaduje vyjádření vzdálenosti objektů čtvercovou euklidovskou vzdáleností.

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 [1]
  • Kapitola z české online učebnice prostorových analýz [2]
  • Kapitola z anglické online učebnice statistiky (anglicky)[3]
  • Popis a ukázka aplikace některých shlukovacích algoritmů - fuzzy shluková analýza, shlukování kolem medoidů (PAM) a CLARA - a prostředků k hodnocení klasifikačního modelu (silhouette plot) [4]


Citováno z „http://www2000.multimediaexpo.cz/mmecz/index.php/Shlukov%C3%A1_anal%C3%BDza“