1
Statistické metody a zpracování dat
Shluková analýza
Petr Dobrovolný
Ilustrativní případ pro m=2
Klimatické poměry n stanic jsou charakterizovány
dvěma proměnnými (m=2): Průměrnou roční
teplotou vzduchu (T) a ročním úhrnem srážek (S)
INTERPRETACE: Stanice s vysokými srážkami a nízkými
teplotami tvoří shluk stanic vysokohorských, stanice s nízkými
úhrny srážek a vysokými teplotami tvoří shluk stanic níže
položených. Ve většině případů není vymezení shluků takto
triviální.
Shluková analýza (Cluster analysis)
Je to skupina metod, jejichž cílem je rozdělení
souboru jednotek na několik navzájem
vylučujících se relativně stejnorodých
podmnožin (shluků = clusters).
Rozdělení jednotek je provedeno tak, aby
jednotky patřící do téhož shluku si byly co
nejvíce ,,podobné", zatímco jednotky
pocházející z různých shluků by měly být co
nejvíce odlišné.
Charakteristika metody I.
Jednotky představují body v n-rozměrném prostoru,
jehož osy tvoří hodnoty jednotlivých znaků (v1, v2,
v3).
V takto definovaném prostoru tvoří jednotky
s podobnými hodnotami znaků PŘIROZENÉ shluky.
Jednotlivé metody shlukové analýzy řeší problém
definice a výpočtu ,,podobnosti" či ,,odlišnosti"
jednotek a jejich PŘÍSLUŠNOST k určitým shlukům.
Shluková analýza je vícerozměrnou
metodou. K charakterizování
jednotek, kterých je obecně n
využívá většího počtu znaků (m>=2).
Charakteristika metody II.
Shluková analýza nesnižuje počet proměnných
(jako např. faktorová či komponentní analýza).
Jde jí o shrnutí jednotek do skupin, jejichž počet
může nabývat hodnot od 1 do n, kde n je počet
výchozích jednotek.
Význam má shlukování pro počet shluků výrazně
menší než n. Shlukování může mít vlastnosti
hierarchického spojování objektů (skladebnost
tříd).
Je-li soubor jednotek postupně pospojován do
menšího počtu shluků, jednotky v jednotlivých
shlucích jsou si méně ,,podobné" a naopak.
Charakteristika metody III.
Analogicky jako v případě faktorové či
komponentní analýzy můžeme spojovat
(shlukovat) sloupce (proměnné) a nebo řádky
(případy) vstupní matice.
Výsledek shlukové analýzy závisí především na
těchto parametrech:
ˇ na zvolených znacích a na jejich počtu
ˇ na zvolené míře ,,podobnosti" jednotek
ˇ na způsobu shlukování
2
Princip shlukování a míry vzdálenosti
Kritériem víceznakové podobnosti ve shlukové
analýze je VZDÁLENOST.
Čím blíže se nacházejí body v m-rozměrném
prostoru, tím jsou si podobnější. Nulová vzdálenost
znamená identitu ­ tedy maximální podobnost.
Eukleidovská vzdálenost ve 2D
2
22
2
11 )()( jijiij xxxxd -+-=
Eukleidovská vzdálenost ve 3D
2
33
2
22
2
11 )()()( jijijiij xxxxxxd -+-+-=
Vzdálenost v m- rozměrném
prostoru
Pomocí vlastností eukleidovského metrického
prostoru lze tento typ vzdálenosti bodů definovat
obecně pro m-rozměrný prostor:
=
-=
m
k
kjkiij xxd
1
2
)(
Eukleidovská vzdálenost předpokládá ortogonalitu
os definovaného prostoru ­ to znamená
vzájemnou nezávislost použitých znaků.
Jiné typy měr vzdálenosti
Hammingova vzdálenost (městská metrika,
Manhattan distance)
=
-=
m
k
kjkiij xxd
1
Jiné typy měr vzdálenosti
Čebyševova vzdálenost ­ je definována jako
maximální hodnota z absolutního rozdílu
souřadnic objektů. Je vhodná v případě, kdy
dva objekty považujeme za odlišné, jestliže se
významně odlišují alespoň v jenom rozměru.
kjkiij xxd -= max
3
Předpoklady použití shlukové analýzy
1. Předpoklad vzájemné nezávislosti
(nekorelovanosti) proměnných
2. Předpoklad nezávislosti na jednotkách měření
3. Předpoklad stejné významnosti uvažovaných
proměnných
ad 1) lze zajistit použitím výsledků faktorové
či komponentní analýzy
ad 2) lze zajistit standardizací vstupních dat
ad 3) viz. dále
Předpoklad stejné významnosti uvažovaných
proměnných - řeší se přidáním vah do vzorců pro
výpočet vzdáleností.
Váhy slouží ke zdůraznění rozdílů mezi znaky
důležitými a k potlačení rozdílů mezi znaky málo
důležitými.
Vztah pro výpočet vážených vzdáleností:
k
m
k
kjkiij vxxd -= =1
2
)(
kde vk je váha příslušející znaku k.
Předpoklady použití shlukové analýzy
Algoritmus výpočtu shlukové
analýzy
Algoritmus výpočtu obsahuje dva základní kroky:
1. analýzu vzdáleností
2. vlastní shlukování
Pro splnění prvních dvou výše uvedených
podmínek vychází vlastní shlukování často ne
z původních m proměnných ale z tzv.
komponentních skóre získaných metodou analýzy
hlavních komponent.
Ilustrativní příklad - vstupní datový soubor
Tzv. komponentní skóre získaná metodou analýzy
hlavních komponent.
První čtyři interpretované hlavní komponenty
popisující strukturu zaměstnanosti v 10-ti
pražských obvodech (viz. Heřmanová, 1991)
Komponentní skóre poskytují
míru vztahu mezi každým
pozorováním (případem) a
novými komponentami. Jsou
důležitá pro interpretaci
výsledků v geografii při analýze
prostorových struktur. Ukazují
do jaké míry je konkrétní
pozorování zastoupeno v nových
proměnných (komponentách).
Analýza vzdáleností
Spočívá ve výpočtu zvoleného typu vzdálenosti mezi všemi
jednotkami a v jejich sestavení do symetrické čtvercové
matice, která má na diagonále nuly (tj. maximální podobnost).
Matice vzdáleností
Vlastní postup shlukování I.
1. Zvolení způsobu shlukování. Z řady variant
spojování (viz. dále) je zde použita metoda
průměrné vzdálenosti.
2. V matici vzdáleností nalezneme minimální
prvek a matici vzdáleností typu [n,n]
redukujeme na typ [n-1,n-1].
3. Jednotky, kterým přísluší minimální hodnota
vzdálenosti si jsou nejpodobnější.
4. Sloučíme odpovídající si jednotky do prvního
shluku.
5. V dalších krocích se mohou slučovat jednotky
se shlukem či dva shluky.
{ }ijdmin
4
Vlastní postup shlukování II.
6. Vypočtou se nové vzdálenosti mezi vzniklým
shlukem a zbylými jednotkami (či shluky). Ty
se vypočtou v našem případě jako aritmetický
průměr vzdáleností mezi jednotkami, které
patří do nově agregovaného shluku a zbylými
jednotkami.
7. Vzdálenosti, kterých se slučování netýká jsou
pouze přepsány do nové matice vzdáleností.
8. V nové matici se opět hledá prvek
9. Analyzujeme-li n jednotek, v procesu
shlukování je n-1 kroků. V posledním kroku
dochází ke sloučení všech jednotek do jednoho
shluku.
{ }ijdmin
1. krok - nalezení minimálního prvku v původní matici
Ve výchozí matici je minimální vzdálenost mezi prvky 8 a 10:
d8,10 = 1,75.
Tyto dvě jednotky se sloučí.
Vypočítáme vzdálenosti tohoto nového shluku
k stávajícím jednotkám (příklad pro pro jednotku 1):
88,10
2
38,1039,11
2
)1,10()1,8(
)1,108( =
+
=
+
=+
dd
d
Analogicky se vypočtou nové vzdálenosti mezi
novým shlukem a zbylými jednotkami, tedy
d(8+10,2), d (8+10,3) ..... d (8+10,9)
Výsledkem je nová matice vzdáleností.
2. krok - nová matice vzdáleností
Hodnota v závorce vyjadřuje vzdálenost, při které
dochází ke sloučení a využívá se ke konstrukci tzv.
dendrogramu (viz. dále).
Opět se najde minimální hodnota a celý výpočet se
opakuje tak, jak je naznačeno v dále uvedených
maticích vzdáleností ...
4. krok
3. krok
6. krok
5. krok
5
9. krok
8. krok
7. krok
V posledním kroku dochází ke sloučení všech
jednotek do jednoho shluku na vzdálenosti 8,58.
To je průměrná vzdálenost mezi dvěma
jednotkami.
Průběh shlukování se obvykle zaznamenává do
tzv. dendrogramů ­ hierarchicky uspořádaných
,,stromů").
Ukončení shlukování a
prezentace jeho průběhu
Na svislé ose lze
vynášet skutečné
vzdálenosti a nebo
vzdálenosti
ekvidistantní
(jednotkové).
Dendrogram Dendrogram ­ ekvidistantní vzdálenost
Charakteristiky dendrogramu
Rozdělíme-li dendrogram na jakékoliv úrovni
pomyslným řezem, vždy dostaneme homogenní
shluky.
Čím později ho rozdělíme, tím méně podobné
jednotky jsou spojeny v jednom shluku. Šipka značí
pokles míry podobnosti jednotek ve shlucích Slouží ke stanovení optimálního rozdělení souboru
na skupiny.
Při každém kroku shlukování dochází ke ztrátě
informace o výchozím souboru tím, že používáme
jistá generalizující vyjádření shlukovaných jednotek
(např. průměrná vzdálenost v uvedeném příkladě).
Tedy při rozdělení na n jednotek (na počátku
shlukování) je ztráta informace nulová, při spojení do
jedné jednotky (na konci) je ztráta maximální (100%).
Charakteristiky procesu shlukování
ˇ Koeficient ztráty informace
ˇ Index grupování
ˇ Graf ztráty informace
6
Koeficient ztráty informace
Koeficient ztráty informace se počítá po každém kroku
jako součet vzdáleností právě agregovaných jednotek
v původní matici [n,n]. Potom stav shlukování před
krokem, kterému přísluší maximální hodnota
koeficientu představuje optimální dělení souboru.
Součin hodnot, vyjadřujících počty jednotek v právě
agregovaných shlucích. Největší ,,skok" v řadě
kumulovaných hodnot indexu grupování indikuje
okamžik optimálního rozdělení souboru z hlediska
zachování relativního maxima informace.
Index grupování
Graf ztráty informace
Znázorňuje počet kroků shlukování (osa x) a
hodnotu indexu grupování resp. koeficientu
ztráty informace v absolutních či relativních
hodnotách (osa y).
V uvedeném příkladě dosahuje velikost ztráty
informace maxima v 8. kroku. Tedy jako
optimální se jeví členění souboru po 7. kroku.
Výsledkem je tedy členění jednotek do tří
shluků:
1: (8, 10, 3, 4, 2, 7, 1)
2: (5, 9)
3: (6)
Metody (varianty) shlukování
Metoda průměrné vzdálenosti ­ dva shluky se spojí
do jednoho, je-li mezi nimi minimální průměrná
vzdálenost
 
=
kjhi
kh
Sx
ji
Sxkh
SS xxd
nn
d ),(
1
dShSk ­ průměrná vzdálenost mezi shluky Sh a Sk
nh, nk ­ počet jednotek ve shluku Sh a Sk
Jednotka se spojí se
shlukem má-li k
jednotkám, které k
němu náležejí nejmenší
průměrnou vzdálenost
Do jednoho shluku jsou spojeny jednotky (resp.
shluky) mezi nimiž je minimální vzdálenost
mezi jejich nejbližšími jednotkami
Metoda nejbližšího souseda
( ){ }jiSS xxdd kh
,min=
Do jednoho shluku jsou spojeny jednotky (resp.
shluky) mezi nimiž je minimální vzdálenost mezi
jejich nejvzdálenějšími jednotkami.
Metoda nejvzdálenějšího souseda
( ){ }jiSS xxdd kh
,max=
7
Vymezování homogenních regionů
metodou shlukové analýzy
Klasické použití shlukové analýzy umožňuje provádět
TYPOLOGII ­ tedy podobné skupiny bez uvažování
kritéria sousedství spojovaných jednotek, výsledkem
jsou většinou územně nesouvislé oblasti.
Tzv. regionální shlukování ­ uvažuje se nejen
vzájemná podobnost vlastních znaků popisujících
jednotky, ale též jejich vzájemná poloha ­ jde tedy o
shlukování podobných a územně souvislých jednotek.
Takovýto přístup potom dovoluje provádět
REGIONALIZACI.
Matice obsahuje jedničky resp. nuly podle toho, zda dvě
jednotky spolu sousedí (mají společnou hranici) či nikoli.
Vzdálenost jednotek se vypočítává pouze pro ta políčka,
která obsahují jedničky. Dále je postup shlukování stejný.
Regionalizace metodou shlukové
analýzy
Informace o poloze jednotek může do shlukování
vstupovat v podobě binární matice sousedství.
01100E
10101D
11011C
00101B
01110A
EDCBA
Metody shlukové analýzy
hierarchické
aglomerativní
nehierarchické
rozkladové optimalizační ...
Rozdělení metod shlukové analýzy Hierarchické metody shlukové
analýzy
Výše uvedený text prezentuje postupy
aglomerativní hierarchické (jednotky se
postupně spojují do shluků
Hierarchické metody rozkladové naopak
postupně dělí vstupní soubor do 2, 3, 4, ...
skupin.
Nehierarchické metody shlukové
analýzy (optimalizační)
Hledají takový rozklad množiny objektů, který je
optimální podle vhodně zvoleného kritéria.
Mohou být založeny na předem daném
(přibližném) počtu shluků a jejich postupném
,,zlepšování" převodem vybraných jednotek mezi
shluky, na eventuelním spojování či rozdělování
shluků.
Výpočty využívají iteračního počtu.
Shluková analýza metodou k- průměrů
(k-means) jako příklad nehierarchického
třídění
Algoritmus předpokládá, že dopředu známe počet
shluků, do kterého si přejeme rozdělit vstupní
soubor.
Výpočet začne s k náhodnými shluky. Jednotky
se poté postupně přesouvají mezi jednotlivými
shluky a to tak, aby:
1) minimalizovaly variabilitu mezi jednotkami
uvnitř jednoho shluku
2) Maximalizovaly variabilitu mezi jednotlivými
shluky
8
Postup shlukování metodou k- průměrů
1. Definování požadovaného počtu výsledných shluků.
2. Určení počáteční polohy středu shluku (centroidu) pro každý
shluk (a, b, c).
3. Postupné přiřazení všech jednotek ke shluku, k němuž mají v
analyzovaném prostoru nejblíže.
4. Výpočet nové polohy centroidu pro každý shluk na základě
přiřazených jednotek.
5. Opakování kroku 3 a 4 do té doby, dokud se poloha shluku či
počet jednotek zařazených do shluku výrazně nemění (tzv.
stabilní shluky).