Statistické metody a zpracování dat X. 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í 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 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 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 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 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= 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 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).