logo-IBA Asociační matice – opakování Shluková analýza Analýza hlavních komponent Bi8600: Pokročilé statistické metody 3. cvičení logo-IBA NxP datová tabulka Výpočet metriky vzdálenosti Asociační matice – Q mode analýza p1 p2 p3 n1 n2 n3 n4 n5 n1 n2 n3 n4 n5 n1 0 n2 0 n3 0 n4 0 n5 0 NxN asociační matice Výpočet metriky podobnosti p1 p2 p3 n1 n2 n3 n4 n5 n1 n2 n3 n4 n5 n1 1 n2 1 n3 1 n4 1 n5 1 Hodnota subjektu n5 v parametru p1 Hodnota subjektu n5 v parametru p1 Vzdálenost subjektu n5 od subjektu n1. Podobnost subjektu n5 se subjektem n1. logo-IBA Euklidova vzdálenost I —Euklidova vzdálenost vychází z Pythagorovy věty: — — — — 1 4 2 6 A B X Y d(A,B)=5 logo-IBA Euklidova vzdálenost II plat počet cigaret/den n1 15 000 10 n2 25 000 15 n3 20 000 20 n4 13 000 25 n5 18 000 10 —Proměnné s číselně většími hodnotami budou mít větší váhu při shlukování!!! —Např. pokud budeme hodnotit výšku (150–200 cm) a cholesterol (do 5 mmol/l), výška bude mít větší váhu při shlukování – objekty budou rozděleny do shluků podle jejich výšky. — Data s nesrovnatelnými hodnotami proměnných je potřeba před analýzou standardizovat. Jak? — Např. standardizace na z-skóre. — Jak byste popsali rozložení z-skóre? POZOR! Výsledek obrázku pro z-score, range standardization logo-IBA Shluková analýza logo-IBA Shluková analýza – jaký je cíl? •Seskupení objektů do shluků podle toho, jak si jsou podobné – chceme co nejpodobnější objekty v rámci shluků a co nejodlišnější mezi shluky. •Shluková analýza vychází z asociační matice vzdáleností objektů (Q mode) nebo závislosti parametrů (R mode). •Můžeme provést dvě hlavní chyby: špatný výběr metriky a špatný výběr algoritmu shlukování. •Smysluplnost výsledků shlukování závisí jednak na objektivní existenci shluků v datech, jednak na arbitrárně nastavených kritériích definice shluků. Jednoznačné odlišení existujících shluků v datech Shlukovou analýzu lze provést i na datech bez objektivní existence shluků logo-IBA Shluková analýza: typy metod logo-IBA Shluková analýza: typy metod Prezentace s multimédii obrys https://www.youtube.com/watch?v=QXOkPvFM6NU Hierarchické shlukování 11:35 minuta logo-IBA Shluková analýza: typy metod 1. Krok 2. Krok X. Krok Atd. Atd. Kolik shluků chceme definovat? Například 4 Výpočet ukončen Minimum spanning tree, Prim network Výpočet ukončen logo-IBA Pojmenujte shlukovací algoritmus I http://portal.matematickabiologie.cz/ 1. krok 2. krok logo-IBA Hierarchické aglomerativní algoritmy G J K I H A B C D E F G J K I H F E D C B A 0 max Prezentace s multimédii obrys Dendogram Pokračování ve videu ze slidu 5 (13:20) logo-IBA Shlukovací algoritmy hierarchické aglomerativní Metoda nejbližšího souseda („single linkage“) - spojení na základě nejmenší minimální vzdálenosti dvou objektů Metoda nejvzdálenějšího souseda („complete linkage“) - spojení na základě nejmenší maximální vzdálenosti dvou objektů https://portal.matematickabiologie.cz/index.php?pg=analyza-a-hodnoceni-biologickych-dat--vicerozmer ne-metody-pro-analyzu-dat--shlukova-analyza--shlukova-hierarchicka-analyza--hierarchicke-shlukovani --hierarchicke-aglomerativni-shlukovani Centroidová metoda („centroids“) - spojení na základě minimální vzdálenosti centroidů (= průměrů) shluků Wardova metoda („Ward’s method“) - shluky jsou vytvářeny tak, aby nově vzniklý shluk přispíval co nejméně k sumě čtverců vzdáleností objektů od centroidů jejich shluků - vstupem je čtverec Euklidovy vzdálenosti logo-IBA Úkol č. 1 A B C D E A 0 B 9 0 C 3 7 0 D 6 5 9 0 E 11 10 2 8 0 §Na základě asociační matice sestrojte dendrogram pomocí algoritmu nejvzdálenějšího souseda. 1)Jaká je minimální vzdálenost dvou objektů? 2)Vykreslete spojení objektů v dendrogramu a přepočítejte asociační matici. Matice je symetrická podél diagonály 0 ? logo-IBA logomuni Práce ve skupinách —Společně pracujete na samostatném úkolu, podklady jsou v Excelu „ukol_c_1.xlsx “ ve studijních materiálech —Výsledný dendogram kreslete do Jamboardu a jednotlivé kroky zapisujte do Excelu —https://jamboard.google.com/d/1sGpFKEuHgp6lwrGgJSZkBt8JRux1MoSe11rEokdF7Lg/edit?usp=sharing — —! Každá místnost (1-5) má svůj slide ! Vytvořil Institut biostatistiky a analýz, Masarykova univerzita J. Jarkovský, L. Brožová logo-IBA Shluková analýza – rozhodovací proces 1)Výpočet asociační matice (pozor na správný výběr metriky vzdálenosti / podobnosti). 2)Výběr shlukovacího algoritmu. 3)Volba počtu shluků. 4) 4) G J K I H A B C D E F G J K I H F E D C B A 0 max logo-IBA Výběr vhodného shlukovacího algoritmu Kofenetická matice •Matice dimenze n x n (n = počet objektů) popisující vzdálenost, kdy byly objekty poprvé spojeny do jednoho shluku. •Hodnoty kofenetické matice závisí na typu algoritmu shlukování. • • • • • • Kofenetický index •Korelace kofenetické matice s původní maticí vzdáleností. Čím vyšší korelace, tím lepší algoritmus (algoritmus lépe popisuje realitu). A B C D E A 0 4.0 12.7 12.7 12.7 B 0 12.7 12.7 12.7 C 0 5.7 5.7 D Matice je symetrická podél diagonály 0 1.4 E 0 Kofenetická matice Dendrogram Vzdálenost, kdy došlo k prvnímu spojení D+C logo-IBA Shluková analýza – rozhodovací proces 1)Výpočet asociační matice (pozor na správný výběr metriky vzdálenosti / podobnosti). 2)Výběr shlukovacího algoritmu. 3)Volba počtu shluků. 4) 4) G J K I H A B C D E F G J K I H F E D C B A 0 max ? logo-IBA Shluková analýza – rozhodovací proces 1)Výpočet asociační matice (pozor na správný výběr metriky vzdálenosti / podobnosti). 2)Výběr shlukovacího algoritmu. 3)Volba počtu shluků. 4) 4) G J K I H A B C D E F G J K I H F E D C B A 0 max ? logo-IBA Určení optimálního počtu shluků I •Subjektivní rozhodování podle: 1)počtu objektů ve shluku, 2)vzdálenosti shluků, 3)na základě charakteru dat. 4) •Objektivní např. pomocí Silhouette indexu, kde a(i) je průměrná vzdálenost objektu ke všem ostatním objektům v daném shluku a b(i) je nejmenší průměrná vzdálenost objektu i k objektům ostatních shluků (odkazuje tedy na vzdálenost k sousednímu shluku). • • • • •Platí: -1 ≤ s(i) ≤ 1. •s(i) blízké -1 značí špatné zařazení do shluku, blízké 1 správné zařazení do shluku, hodnoty blízké 0 značí, že objekt leží na hranici dvou shluků. •Počítá se průměr s(i) v rámci shluků a do grafu vykreslujeme průměr s(i) pro všechny shluky. Počet shluků s nejvyšší hodnotou celkového s(i) odkazuje na nejlepší dělení souboru. • • b(i) a(i) Objekt i Nakonec ale stejně může vyhrát naše subjektivní rozhodnutí J Prezentace s multimédii obrys https://www.youtube.com/watch?v=AtxQ0rvdQIA Čas 2:50 Silhouette method – celkem 5 minut, je to dlouhé… logo-IBA Určení optimálního počtu shluků II •Objektivní pomocí Mantelova testu. •Hodnotíme korelaci původní asociační matice vzdáleností a asociační matice (vypočítanou pomocí Gowerova indexu), která obsahuje 1, pokud jsou spolu objekty ve shluku a 0 pokud nejsou. R si matici určující současný výskyt ve shluku převede na vzdálenosti – tedy 0 pokud jsou spolu objekty ve shluku a 1 pokud nejsou. • • • • • • • • • •Kladná korelace (nízká vzdálenost → objekty jsou spolu ve shluku) nám říká, že objekty sobě podobné leží spolu ve shluku. •Počet shluků s nejvyšší hodnotou korelace odkazuje na nejlepší dělení souboru. A B C D E A 0 5.0 6.2 11.8 11.7 B 5.0 0 3.5 11.0 9.3 C 6.2 3.5 0 4.0 4.8 D 11.8 11.0 4.0 0 2.4 E 11.7 9.3 4.8 2.4 0 A B C D E A 1 0 0 0 0 B 0 1 1 0 0 C 0 1 1 0 0 D 0 0 0 1 1 E 0 0 0 1 1 shluky A, B+C, D+E A B C D E A 0 1 1 1 1 B 1 0 0 1 1 C 1 0 0 1 1 D 1 1 1 0 0 E 1 1 1 0 0 matice vzdáleností asociační matice vs. logo-IBA Funkce v R – shluková analýza cluster<-hclust(dist(data), method='single')= provede shlukovou analýzu plot(cluster)= vykreslí dendrogram cutree(cluster,k=3)= klasifikuje objekty do 3 skupin podle vzdáleností v dendrogramu cutree(cluster,h=3)= klasifikuje objekty do skupin na vzdálenosti 3 v dendrogramu logo-IBA logomuni Práce ve skupinách —Společně pracujete na samostatném úkolu —Výstupy zapisujete do Jamboardu —https://jamboard.google.com/d/1sGpFKEuHgp6lwrGgJSZkBt8JRux1MoSe11rEokdF7Lg/edit?usp=sharing — —! Každá místnost (1-5) má svůj slide ! —Pokud Vám nebude stačit jeden slide, přidáte si další. —Ad 1. úkol – přehled vhodných asociačních matic je v předchozím cvičení (2B) Vytvořil Institut biostatistiky a analýz, Masarykova univerzita J. Jarkovský, L. Brožová