Pokročilé metody analýzy v neurovědách IBA # RNDr. Eva Janoušová doc. RNDr. Ladislav Dušek, Dr. Jaro 2015 Blok 4 Shluková analýza Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^J/ 2 Osnova i- 1. Podstata a cíle shlukové analýzy dat 2. Shluková analýza hierarchická - hierarchické aglomerativní shlukování 3. Shluková analýza hierarchická - hierarchické divizivní shlukování 4. Shluková analýza nehierarchická 5. Identifikace optimálního počtu shluků Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^J Podstata a cíle shlukové analýzy dat Janoušová, Dušek: Pokročilé metody analýzy dat v neu Shluková analýza - cíle a postupy Shluková analýza se snaží o identifikaci shluků objektů ve vícerozměrném prostoru a následnou redukci vícedimenzionálního problému kategorizací objektů do zjištěných shluků Existuje řada různých metod pro shlukování dat lišících se: Měřením vzdálenosti mezi objekty - Algoritmem spojování objektů do shluků - Interpretací výstupů Každá z metod má své vlastní předpoklady výpočtu a je nasaditelná pro různé typy úloh Porušení předpokladů nebo nasazení chybné metody může vést k zavádějícím výsledkům Csl N 16 15 14 13 12 11 10 9 8 Ě Q 7 6 5 4 3 2 1 0 —< \ ( \) s_+ y c t •\ \ J /B r v J / \ V ■ - - - I - - - I - - - I - - - I ■ . I - - - I - - - I - - - I - - - I - - - I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Dimenze 1 Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA (Mi Obecný princip hledání shluků v datech • Vzájemnou pozici objektů ve vícerozměrném prostoru lze popsat jejich vzdáleností (např. Euklidovou, Čebyševovou apod.) • Smysluplnost výsledků shlukování závisí jednak na objektivní existenci shluků v datech, jednak na arbitrárne nastavených kritériích definice shluků oooo oooo oooo oooo Jednoznačné odlišení existujících Shluková analýza je možná i v tomto shluků v datech (obdoba případě, nicméně hranice shluků jsou multimodálního rozložení) dány pouze naším rozhodnutím. MU ,-.*■»»., Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách l^J 6 Shluková analýza - typy metod 1. Krok 2. Krok Shluková analýza I I I Hierarchické shluky jsou definovány postupným skládáním objektů I 1 Aglomerativní Po spojení první dvojice objektů dochází k postupnému napojování dalších objektů. Divizivní Objekty jsou nejprve rozděleny do dvou shluků, tyto shluky jsou dále rozděleny atd. co oo oo oo 1 Nehierarchické shluky jsou definovány v jednom kroku I I Divizivní objekty rozděleny do předem nastaveného počtu shluků. 1 Aglomerativní síť spojených bodů Kolik shluků chceme definovat? Například 4 Minimum spanning tree, Prime network X. Krok Atd. Atd. Výpočet ukončen Výpočet ukončen MU ,-.*■»»., Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách (^ 7 Shluková analýza hierarchická -hierarchické aglomerativní shlukování Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách Hierarchické aglomerativní shlukování • Při tomto způsobu shlukování jsou postupně shlukovány nejpodobnější objekty až do doby, kdy jsou všechny objekty propojeny do jednoho shluku spojujícího všechny objekty v analyzovaném souboru • Analýza má dva hlavní kroky: 1. Výběr vhodné metriky vzdálenosti/podobnosti pro výpočet asociační matice (analýza může probíhat na libovolných metrikách vzdálenosti/podobnosti) 2. Výběr shlukovacího algoritmu, který podstatným způsobem ovlivňuje výsledky analýzy a možnosti její interpretace • Algoritmus výpočtu postupuje v následujícím cyklu 1. Výpočet asociační matice 2. Spojení dvou nejpodobnějších objektů 3. Přepočítání asociační matice tak, že spojené objekty již nadále vystupují jako jediný objekt (v tomto kroku se uplatňuje zvolený shlukovací algoritmus, který definuje jak bude počítána vzdálenost/podobnost spojených objektů vůči ostatním objektům) 4. Spojení dvou nejpodobnějších objektů z přepočítané asociační matice 5. Atd. až do spojení všech objektů MU ,-.*■»»., Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách l^J 9 Hierarchické aglomerativní shlukování - schéma výpočtu Výběr metriky podobnosti/vzdálenosti Asociační matice Výpočet podobnosti sloučené dvojice objektů k ostatním objektům Výběr shlukovacího algoritmu Nalezení dvojice nejpodobnéjších objektů Ukončení výpočtu po spojení všech objektů Dendrogram A B C D E i ... i ... i ... i ... i ... i ... i ... i ■■ ■ i ... i ... i ... i ... i .. . i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Linkage Distance Amalgamation schedule/graph Amalgamation Schedule (clustering_demo) Complete Linkage Euclidean distances linkage distance Obj. No. 1 Obj. No. 2 Obj. No. 3 Obj. No. 4 Obj No 5 1.414214 □ E 4.000000 A B 5.830952 C D E 12.80625 A B C D E Janoušová, Dušek: Pokročilé metody analýzy dat v neurovédách IBA W io Popis výstupů - dendrogram Shlukované objekty - jejich pořadí je dáno přiřazením do shluků, není problém jejich pořadí v grafu měnit (např. v tomto konkrétním grafu prohodit A a B), pouze nesmí dojít ke změně shluků B D Tree Diagram for 5 Cases Complete Linkage <-Euclidean distances Výstupy shlukové analýzy musí být vždy popsány použitou metrikou vzdáleností a shlukovacím algoritmem Propojení shlukovaných objektů 6 7 8 9 10 11 12 13 14 age Distance Vzdálenost, na níž došlo ke spojení shluku: • je v rozměrech použité metriky vzdáleností/podobností a v tomto kontextu ji lze kvantitativně interpretovat • interpretace vzdálenosti shlukování se liší podle použitého shlukovacího algoritmu • někdy se uvádí ve škále 0-100%, kde 100% je maximální vzdálenost shlukování Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách l^J 11 Popis výstupů - Amalgamation schedule/graph Popis postupu shlukování; využitelné i pro identifikaci optimálního počtu shluků Amalgamation Schedule (clustering_demo) Complete Linkage Euclidean distances linkage distance Obj. No. 1 Obj. No. 2 Obj. No. 3 Obj. No. ObĽJtóf 1.414214 □ E 4.000000 A B 5.830952 C D E 12.80625 A B C D E Objekty spojené v jednotlivých krocích shlukování Souvislost s dendrogramem: Grafické vyjádření kroků shlukování a vzdálenostech, na nichž došlo k propojení objektů: 14 12 8 10 c co co Ô cd O) CC c A B C D E ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Linkage Distance Pokud je v grafu dlouhá vzdálenost bez napojení shluku, jde o možné místo zastavení shlukování a definici finálních shluků 2 3 Step 4 5 Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 12 Shlukovací algoritmy hierarchického aglomerativního shlukování Metoda nejbližšího souseda (nearest neighbour, simple linkage) - spojení dle nejmenší vzdálenosti mezi objekty shluků Průměrná vzdálenost (pair group average) - spojení dle průměrné vzdálenosti mezi objekty shluků - Vážená (weighted) - odstranění vlivu velikosti shluků, shluky bez ohledu na velikost přispívají k výpočtu spojovací vzdálenosti stejnou vahou - Nevážená (unweighted) - výpočet spojovací vzdálenosti je ovlivněn velikostí spojovaných shluků Středospojná vzdálenost (pair group centroid) - spojení dle vzdálenosti centroidů shluků - Vážená (weighted) - odstranění vlivu velikosti shluků, shluky bez ohledu na velikost přispívají k výpočtu spojovací vzdálenosti stejnou vahou - Nevážená (unweighted) - výpočet spojovací vzdálenosti je ovlivněn velikostí spojovaných shluků o Metoda nejvzdálenějšího souseda (farthest neigbour, complete linkage) - spojení dle největší vzdálenosti mezi objekty shluků o—o- Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 13 Shlukovací algoritmy hierarchického aglomerativního shlukování Metoda nejbližšího souseda (nearest neighbour, simple linkage) - spojení dle nejmenší vzdálenosti mezi objekty shluků Průměrná vzdálenost (pair group average) - spojení dle průměrné vzdálenosti mezi objekty shluků - Vážená (weighted) - odstranění vlivu velikosti shluků, shluky bez ohledu na velikost přispívají k výpočtu spojovací vzdálenosti stejnou vahou - Nevážená (unweighted) - výpočet spojovací vzdálenosti je ovlivněn velikostí spojovaných shluků Středospojná vzdálenost (pair group centroid) - spojení dle vzdálenosti centroidů shluků - Vážená (weighted) - odstranění vlivu velikosti shluků, shluky bez ohledu na velikost přispívají k výpočtu spojovací vzdálenosti stejnou vahou - Nevážená (unweighted) - výpočet spojovací vzdálenosti je ovlivněn velikostí spojovaných shluků Metoda nejvzdálenějšího souseda (farthest neigbour, complete linkage) - spojení dle největší vzdálenosti mezi objekty shluků Přechod mezi oběma extrémy (metoda flexible clustering umožňuje dle nastavení zcela plynulý přechod) Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 14 Shlukovací algoritmy hierarchického aglomerativního shlukování-Wardova metoda Principielně podobné ANOVA 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ů V počátečním kroku je každý objekt sám sobě shlukem, a tedy vzdálenost od centroidů shluku je rovna 0 Pro výpočet vzdáleností od centroidů je používána Euklidovská vzdálenost Pro popis vzdálenosti shlukování je v dendrogramu možné použít řadu postupů (nezbytné ověřit jaký přístup je k dispozici v použitém SW): - Čtverce vzdáleností - Odmocnina čtverce vzdáleností - Podíl variability (čtverce vzdáleností) připadající na daný shluk - Aj. Krok 1: každý objekt je sám sobě centroidem o° •* o 0 o Krok 2: spojení objektů, které nejméně přispějí k sumě čtverců vzdáleností od centroidů Krok 3: spojení objektů, které nejméně přispějí k sumě čtverců vzdáleností od centroidů Krok 4: stejný postup až do spojení všech objektů Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 15 Metoda nejbližšího souseda: 1. krok výpočtu Je vypočtena asociační matice A B C D E A 0.0 4.0 7.2 12.8 12.7 B 4.0 0.0 4.5 10.0 10.3 C 7.2 4.5 0.0 5.7 5.8 D 12.8 10.0 5.7 0.0 1.4 E 12.7 10.3 5.8 1.4 0.0 Je definován shluk dvou nejbližších objektů D-E OJ - • Výsledek analýzy je vizualizován ve formě dendrogramu Metoda nejvzdálenějšího souseda: 1. krok výpočtu Je vypočtena asociační matice A B C D E A 0.0 4.0 7.2 12.8 12.7 B 4.0 0.0 4.5 10.0 10.3 C 7.2 4.5 0.0 5.7 5.8 D 12.8 10.0 5.7 0.0 1.4 E 12.7 10.3 5.8 1.4 0.0 Je definován shluk dvou nejbližších objektů D-E OJ - • Výsledek analýzy je vizualizován ve formě dendrogramu Metoda nejbližšího a nejvzdálenějšího souseda -interpretace výsledků Metoda nejbližšího souseda Metoda nejvzdálenějšího souseda ) 1 2 3 4 5 Rozdílné zařazení objektu C 6 7 8 9 10 11 12 13 14 Linlkage Distance Vzdálenost, na níž došlo ke spojení shluku: • u metody nejbližšího souseda znamená nejmenší vzdálenost objektů shluku, tedy ve shluku mohou existovat objekty s větší vzdáleností 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Linlage Distance Vzdálenost, na níž došlo ke spojení shluku: • u metody nejvzdálenějšího souseda znamená největší vzdálenost objektů shluku, tedy objekty ve shluku už mohou být k sobě pouze blíže nebo stejně vzdálené jako je tato vzdálenost Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 26 Shluková analýza hierarchická -hierarchické divizivní shlukování Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 27 Hierarchické divizivní shlukování - postup • divizivní metody pracují ze začátku se všemi objekty jako s jednou skupinou • nejdříve je tato skupina rozdělena do dvou menších skupin • dělení podskupin pokračuje dále, dokud není splněno alespoň jedno z kritérií, které ukončí analýzu: — předem definovaný počet kroků — rozklad na samostatné objekty — dosažení kritéria minimálního Hierarchické divizivní shlukování - poznámky * výhoda oproti hierarch. aglomerativnímu shlukování: vhodné pro objemné datové soubory * výhodou rovněž, že ke každému dělení je připojeno kritérium, podle kterého dělení proběhlo * typy divizivních metod: - monotetické (dělení souboru podle jediné proměnné) — polytetické (dělení souboru podle komplexní charakteristiky získané na základě všech proměnných) - např. metoda TWINSPAN Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^J/ 29 Shluková analýza nehierarchická Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 30 Nehierarchické shlukování • pokud data nevykazují hierarchickou strukturu, je často vhodnější používat nehierarchické shlukování namísto hierarchického shlukování • výstupem vytvoření skupin stejného řádu • skupiny uvnitř co nejvíce homogenní a mezi sebou co nejvíce odlišné • nehierarchické metody vhodné pro velmi objemná data • metody nehierarchického divizivního shlukování: - metoda k- průměrů (k-means duste ring) - metoda x-průměrů — metoda /c-medoidů • metody nehierarchického aglomerativního shlukování: — Minimum spanning tree MU ,-.*■»»., Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách \J^j 31 Nehierarchické divizivní shlukování - metoda k-průměrů >- • Metoda zařazuje objekty do shluků na principu ANOVA, analogií je Wardova metoda shlukování v hierarchickém aglomerativním shlukování • Počet shluků je předem definován, výběr nejvhodnějšího počtu shluků je prováděn buď expertně nebo pomocí matematických metod výběru optimálního počtu shluků (analýza vnitro a mezishlukových vzdáleností) • Postup: 1. V prvním kroku je určeno k objektů jako počáteční středy shluků (výběr může být náhodný, daný uživatelem nebo maximalizující počáteční vzdálenosti k objektů) 2. Následně jsou objekty zařazeny do k shluků tak, aby byla minimalizována suma čtverců vzdáleností objektů k centroidům jejich shluků Výsledek pro k=2 Výsledek pro k=3 • Upozornění: Analýza vždy nalezne zadaný počet shluků, i když výsledek nemusí být vždy prakticky smysluplný! Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách \J^j 32 Nehierarchické aglomerativní shlukování - postup Do této skupiny lze zařadit metody hledající nejkratší spojnici mezi objekty ve vícerozměrném prostoru (i když lze vznést námitky proti nazývání těchto metod nehierarchickými) Metody hledají v asociační matici (prvním krokem je tak vždy výběr vhodné metriky vzdáleností/ podobností) propojení všech objektů s nejmenší sumou vzdáleností mezi propojenými objekty Na rozdíl od klasického hierarchického aglomerativního shlukování může být na jeden objekt napojeno několik dalších objektů Minimum spanning tree Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 33 Identifikace optimálního počtu shluků Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách Identifikace optimálního počtu shluků Cílem analýzy může být jednak zjistit vazby mezi objekty (dostatečným výstupem je dendrogram) nebo identifikovat v datech shluky, které budou využity v další analýze jako zjednodušení vícedimenzionálního problému Identifikace shluků ve výsledcích shlukové analýzy: - Expertní/intuitivní - hranice oddělení shluků je určena podle zkušeností analytika a praktického významu výstupu - Matematické metody (analýza mezishlukových/vnitroshlukových vzdáleností; silhouette metoda aj.) fungují dobře v případě existence přirozených shluků - V některých případech (při neexistenci přirozených shluků) je rozdělení souboru pouze arbitrárni Jednoznačný řez na více vzdálenostech Jediný identifikovatelný řez, navíc na malé vzdálenosti SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA SET OSA ■ ■ Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 35 Identifikace optimálního počtu shluků >- • Mezi shlukovou analýzou a pozicí objektů ve vícerozměrném prostoru existuje vztah Jednoznačný řez na více vzdálenostech Jediný identifikovatelný řez, navíc na malé vzdálenosti Identifikace optimálního počtu shluků - metody • Dunnůvvalidační index • Daviesův-Bouldinův validační index • Metoda siluety • Izolační index • C-index • Goodmanův-Kruskalův index MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách J^J 37 Poděkování Příprava výukových materiálů předmětu „DSAN02 Pokročilé metody analýzy dat v neurovědách" byla finančně podporována prostředky projektu FRMU č. MUNI/FR/0260/2014 „Pokročilé metody analýzy dat v neurovědách jako nový předmět na LF MU" Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách