Shluková analýza

 

Shluková analýza (cluster analysis) seskupuje, shlukuje data do společných skupin a to na základě podobnosti (ne podobnosti, vzdálenosti). O datech toho většinou víme velmi málo. Data jsou reprezentována svými k charakteristikami, dostáváme k-rozměrný vektor. Výsledkem shlukové analýzy je vytvoření dendogramu (hierarchický strom shluků), kde platí, že podobné případy budou ve stejném nebo blízkém shluku a rozdílné případy (a shluky do kterých padnou) budou od sebe vzdáleny.

Standardizace dat

Vzdálenost samotná je závislá na měřítkách jednotlivých veličin. V případě nesourodosti (statisíce vs. jednotky) je možné data standardizovat, protože jinak by celá analýza závisela nejvíce na proměnné s největším rozsahem. Neexistuje však pravidlo, zda standardizaci použít nebo ne.

Vzdálenost objektů

Postup pří shlukové analýze probíhá v zásadě ve dvou krocích. V prvním kroku se vypočtou vzdálenosti objektů (proměnných nebo případů) a uloží se do matice vzdáleností. Ve druhém kroku se na základě této matice objekty postupně slučují do shluků. Shluky nahradí sloučené objekty a podrobují se novému vypočtu vzdáleností podle stejných principů.

V statistických software je možné zvolit z několika různých způsobů výpočtu vzdálenosti:

  • Euklidovké vzdálenosti - d(x,y) = {Si (xi - yi) }1/2, - klasická míra vzdálenosti, která pro dva body v prostoru určuje délku „nejkratší cesty“ z jednoho bodu do druhého
  • Blokové vzdálenosti (Manhattan) - d(x,y) = Si |xi - yi| - suma vzdáleností v jednotlivých dimenzích. Název i výpočet je inspirován vzdáleností, kterou na Manhattanu člověk urazí při cestě z jednoho bodu do druhého. Nelze jít po spojnici, musí se jít po kolmých ulicích
  • Čebyševovy vzdálenosti - d(x,y) = Max |xi - yi| - maximum ze vzdáleností v jednotlivých dimenzích
  • Mocninné vzdálenosti - d(x,y) = (Si |xi - yi|p)1/r - uživatelem definovaná míra vzdáleností. Čím vyšší parametr p, tím vyšší váha se přikládá větším vzdálenostem v jednotlivých dimenzích a snižuje se význam malých vzdáleností. Vysoké p nejvíce „propaguje“ body hodně vzdálené ve všech dimenzích. Parametr r působí opačným směrem, čím vyšší r, tím menší váha se přikládá větším vzdálenostem. r ovšem působí celkově bez ohledu na dimenze
  • Procentuální neshoda - d(x,y) = (počet xi ≠ yi) / i - je vhodná pouze pro kategorické proměnné. Pro dva objekty se spočte jako podíl počtu dimenzí, v nichž se jejich hodnota liší, ku celkovému počtu dimenzí
  • 1- Pearsonův r - d(x,y) = 1- r(x,y) - míra založená na korelaci. Největší vzdálenost přiřazuje negativně korelovaným objektům, nejmenší naopak pozitivně korelovaným objektům. Nevhodná pro malý počet dimenzí.

Kterou míru vzdálenosti vybrat? Procentuální neshoda je určena pro kategorické proměnné. Pokud neprovedeme standardizaci dat, pak některé proměnné mají větší rozptyl jiné menší. Pokud bychom zvolili Čebyševovu míru vzdálenosti, bude o zařazení do clusterů rozhodovat právě proměnná s největším rozptylem a vliv ostatních proměnných bude zanedbatelný. Všechny ostatní míry jsou přijatelné a lze je postupně vyzkoušet. Nejběžnější je použití Euklidovské vzdálenosti.

POZOR. Obecně ale nemusí být proměnná s největším rozptylem skutečně ta, která nejvíce odlišuje objekty!

Pravidla slučování

V matici vzdáleností se nalezne minimum a objekty, jimž tato vzdálenost přísluší se spojí do shluku. Dojde k výpočtu nové matice vzdáleností. Celý cyklus se opakuje až do vytvoření jediného velkého shluku.

I v pravidlech pro spojování je možné vybrat několik možností.

  • Jednoduché spojení - vzdálenost dvou shluků se určí jako vzdálenost dvou nejbližších objektů (případů/proměnných). Rozumí se dvou nejbližších objektů z různých shluků! Tento algoritmus má tendenci spojovat objekty do dlouhých „řetízků“
  • Úplné spojení - vzdálenost shluků je naopak dána vzdáleností těch dvou objektů, které jsou nejdále od sebe. Algoritmus je vhodný pro případy, kdy jsou objekty přirozeně rozdělené do určitých skupin. Má tendenci spíše tvořit skupiny s podobným počtem objektů
  • Nevážený průměr skupin dvojic - vzdálenost shluků je prostým průměrem vzdáleností všech párů objektů, které lze vytvořit tak, že z každého shluku vezmeme jeden objekt. Tato varianta algoritmu pracuje lépe v případech, kdy vstupní objekty mají spíš charakter oddělených skupin. Lze ale použít i pro objekty mající „řetízkovou“ strukturu
  • Vážený průměr skupin dvojic - obdoba předchozího algoritmu. Při výpočtu průměru se navíc berou jako váhy počty objektů v jednotlivých clusterech
  • Nevážený centroid skupin dvojic - vzdálenost shluků je určí jako vzdálenost mezi centroidy shluků. (Centroid je bodem definovaným průměry v jednotlivých dimenzích)
  • Vážený centroid skupin dvojic (medián) - vážená varianta předchozího algoritmu

Využití shlukové analýzy

Použitím jiného způsobu výpočtu vzdálenosti objektů a pravidel slučování lze dojít k různým hierarchickým stromům. Každý takový výsledek může být způsoben jinou vlastností původních dat. Výsledek shluková analýzy musí být potvrzen i jiným úsudkem a znalostí vědeckého pracovníka, bez ní (ostatně jako v celé statistice) se jedná pouze o „hru čísel“.

 

* * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * *

Otázky k procvičení (přístupné v informačním systému)

Vstoupit

* * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * *


Příklad 1 Shluková analýza

Zadání: Přirozený pohyb obyvatelstva v České republice v letech 1985 - 1995 je uveden v tabulce 47. Vytvořte shluky poměrně stejnorodých ročníků.

Tab. 47 Vstupní data

Rok

Sňatky na 1000 obyv.

X1

Rozvody na 1000 obyv. X2

Živě naroz. na 1000 obyv.

X3

Zemřelí na 1000 obyv. X4

Kojenecká úmrtnost v ‰ X5

Potraty na 1000 obyv. X6

1985

7,8

2,95

13,1

12,7

12,5

9,6

1986

7,9

2,86

12,9

12,8

12,3

9,6

1987

8,1

3,00

12,7

12,3

12,0

12,0

1988

7,9

2,96

12,8

12,1

11,0

12,2

1989

7,8

3,03

12,4

12,3

10,0

12,0

1990

8,8

3,09

12,6

12,5

10,8

12,0

1991

7,0

2,85

12,5

12,1

10,4

11,4

1992

6,2

2,77

11,8

11,7

9,9

10,3

1993

6,4

2,93

11,7

11,4

8,5

8,0

1994

5,7

2,99

10,3

11,4

7,9

6,5

1995

5,3

3,01

9,3

11,4

7,7

6,0

Statistiky → Vícerozměrné průzkumné statistiky → Shluková analýza

Řešení:

Shluková analýza je metodou vyhledávání homogenních skupin v rámci souboru nějakých statistických jednotek, které bývají v této souvislosti označovány jako objekty. Shluková analýza rozkládá toto „mračno“ do jistého počtu disjunktních podmnožin - shluků. Pravidla tohoto shlukování bývají konstruována tak, aby shlukování vedlo k vytvoření shluků, v jejichž rámcích jsou jednotky co nejvíce homogenní, zatímco jednotky z různých shluků se ve svých vlastnostech co nejvíce odlišují. Shluková analýza je spíše než metodou, rozsáhlým komplexem metod typologického třídění, které můžeme klasifikovat z ně-kolika různých pohledů. Podle typu výpočetního algoritmu dělíme metody shlukové analýzy na hierarchické, paralelní a sekvenční, přičemž hierarchické metody můžeme dále podrobněji klasifikovat na aglomerativní a divizní. Využijeme výhradně metody z hierarchickým aglomerativním algoritmem.

Při tvorbě shluků využijeme nabídky programu STATISTICA 10, který pro měření vzdálenosti objektů využívá několik způsobů výpočtu vzdálenosti

Obr. 13 Euklidovké vzdálenosti

Obr. 14 Čebyševovy vzdálenosti

Závěr:

Všechny výše uvedené metody pro výpočet vzdálenosti mezi shluky daly stejné výsledky, jak pro dva shluky, tak pro tři shluky. Viz obr. 13 a obr. 14. První shluk podobných objektů tvoří roky (1985, 1986), (1989, 1991) a (1994, 1995) a ve druhém shluku jsou zbývající roky.


Příklad 2 Shluková analýza

Máme 5 objektů. Jeden objekt je charakterizován metrickými znaky (2, 10), druhý (3, 8), třetí (4, 9), čtvrtý (10, 4) a pátý (11, 5). Vypočtěte matici vzdáleností v Euklidově metrice a proveďte shlukování metodou jednoduchého spojení. Výsledky interpretujte graficky.

Řešení:

Euklidova metrika je definována vztahem

                                                                     (2.1)

vzdálenost podle kriteria průměrné vazby se vypočte podle vztahu

                                                        (2.2)

kde N1 a N2 jsou počty objektů ve třídách S1 a S2.

Matice vzdáleností D, do níž sestavujeme vypočtené vzdálenosti všech možných dvojic objektů xk, xl, je čtvercová symetrická matice řádu N (počet objektů), s nulami na hlavní diagonále. V našem příkladu je matice vzdáleností

Tab. 48 „ruční“ a software výpočet matice vzdáleností

Z matice D plyne, že objekty, jejichž vzdálenost (2.1) je rovna (objekty S2 a S3; S4 a S5) tvoří dva shluky – řádky 1 a 2 (tab. 4). Další shlukování provedeme podle vztahu (15). Shluk z objektů S2 a S3 vytvoří nový shluk A = (S1, S2, S3), nikoliv shluk B = (S1, S4, S5) protože vzdálenost. Procedura shlukování končí vytvořením shluku, který zahrnuje všechny objekty.

Tab. 49 Rozvrh shlukování

Závěr:

Proces shlukování metodou jednoduchého spojení je znázorněn v tab. 49 a na obr. 15 je odpovídající dendrogram.

Obr. 15 Dendrogram