Zhluková analýza Podzim 2009 MU IBA 'nštitút bioštatistiky a analýz, Masarykova univerzita Úvod ♦ Mnohorozmerné metody: názov „mnohorozmerné" - dáta sú tvorené objektami (vzorky, lokality), každý z nich je charakterizovaný viacerými parametrami (druhmi) každý z týchto parametrov môžme považovať za jeden rozmer objektu (vzorky) DATOVÁ MATICA CM CO ■u -o -o vzorka 1 vzorka 2 vzorka 3 vzorka 4 vzorka 5 vzorka 6 Hodnoty pre druhy (presencia/absencia; abundancia; dominancia) pre každú vzorku Ordinácia a zhluková analýza sú jediné možné techniky, ktoré môžeme použiť bez nameraných environmentálnych dát. HLUKOVÁ ANALÝZ ♦ Klasifikuje vzorky (lokality), druhy alebo premenné ♦ Nachádza skupiny v dátach *Qn lLb-i íO BO íO podobnosť vod RDINACI ♦ Usporadúva vzorky pozdĺž trendu v dátach its VCt Faktorové osi ■íTž>IO y X Zhluková analýza Zhluková analýza: ♦ Roztriedenie objektov do niekoľkých pomerne homogénnych zhlukov ♦ Zníženie počtu dimenzií objektov tak, že radu uvažovaných premenných (druhy) zastúpi jediná premenná, vyjadrujúca príslušnosť objektu k definovanej skupine Na základe druhov (premenných) CM CO 3 "O 3 i. ■u 3 vzorka 1 vzorka 2 vzorka 3 vzorka 4 vzorka 5 vzorka 6 Klasifikácia objektov do skupín ♦ zhluky sú disjunktně ♦ objekty vnútri zhluku si sú čo najviac podobné a s objektami z rôznych zhlukov čo najmenej vzorka 1 vzorka 2 vzorka 3 vzorka 4 vzorka 5 vzorka 6 Zhluková analýza Ciele klasifikácie sú hlavne: ♦ poskytnúť informáciu o konkurencii druhov (vnútorná štruktúra dát), ♦ stanoviť typy spoločenstiev pre deskriptívne štúdie (syntaxonomia alebo mapovanie), ♦ odhaliť vzťahy medzi spoločenstvami a prostredím analyzovaním skupín vytvorených zhlukovou analýzou s ohľadom na environmentálne premenné (externá analýza). Vstupné dát ♦ Tabuľka spojitých alebo katego-riálnych dat popisujúca objekty t- CM CO Výstupy analýz ♦ Tzv. dendrogram popisující väzby medzi objektami alebo parametrami ♦ Rozdelenie objektov alebo parametrov do daného počtu skupín vzorka 1 vzorka 2 vzorka 3 vzorka 4 vzorka 5 vzorka 6 vzorka 1 vzorka 2 vzorka 3 vzorka 4 vzorka 5 vzorka 6 6.0 6.5 7.0 7.5 8.0 8.5 9.0 9.5 Linkage Distance Zhlukova analýza hierarchical techniques ♦ skupiny usporiadané do hierarchickej štruktúry single-linkage clustering average-linkage clustering complete-linkage clustering agglomerative clustering H divisive clustering monothetic method association analysis polythetic method two way indicator species analysis non-hierarchical techniques K-means clustering Hierarchické aglomeratívne zhlukovanie Koeficienty podobnosti Sorensenov koeficient O 8 {Xl, X2 ) = — - 2a + b + c &9 v-^i? X2) 3a 3a + b + c Jaccardov koeficient O 7 l »A/1 * J\/^ I a a + b + c Sorensenov kvantitatívny koef. r = 2jN (aN + bN) Morisota-Horn index ^mH (da + db).aN.bN da = _Z an; aN' Hierarchické aglomeratívne zhlukovanie Metriky vzdialenosti Euklidovská vzdialenosť Dl(xl,x2) =^jj^ji-yji) Vážená euklidovská vzdialenosť d9(x1,x2)=AE=iw/0'./i" y^ Manhattanská vzdialenosť p D7(xvx2) = Y}yji-y 7=1 j2 Minkowski (power distance) LJ6{Xl,x2) — p 7=1 lA 7'2 A - celé číslo A =1 Manhattan (city block) A = 2 Euklidovská vzdialenosť Výsledok zhlukovej analýzy je silne ovplyvnený výberom metriky vzdialenosti, resp. indexu podobnosti Hierarchické aglomeratívne zhlukovanie hierarchical techniques agglomerative clustering ♦ začína jednotlivými objektami, ktoré sú spájané do väčších zhlukov ♦ vyžaduje maticu podobností alebo nepodobností (site by site), ktorou začína ♦ pre dáta presencie/absencie aj pre kvantitatívne dáta existuje mnoho indexov podobnosti ♦ Všetky aglomeratívne metódy sú založené na spájaní jednotlivých objektov (vzoriek) alebo zhlukov do väčších skupín Definícia podobnosti medzi skupinami sa u jednotlivých metód líši. Metódy sa navzájom líšia chápaním vzdialenosti medzi zhlukmi. -|- centroid vzdialenosť pri single linkage vzdialenosť pri complete linkage Iné metódy: • vzdialenosť medzi centroidmi • average linkage Hierarchické aglomeratívne zhlukovanie Metóda najbližšieho suseda (jednospojná metóda, metoda jedinej väzby, single linkage, the nearest neighbor method) Vzdialenosť medzi dvoma zhlukmi je daná ako minimálna vzdialenosť medzi všetkými možnými zástupcami zhluku. Často sa i veľmi vzdialené objekty môžu zísť v rovnakom zhluku, ak väčší počet ďalších objektov medzi nimi vytvorí akýsi most. Hierarchické aglomeratívne zhlukovanie Metóda najvzdialenejšieho suseda (všespojná metóda, metóda úplnej väzby, complete linkage, the furthest neighbor method) Vzdialenosť medzi dvoma zhlukmi je daná maximálnou vzdialenosťou medzi všetkými možnými zástupcami oboch zhlukov. Zhluky sú medzi sebou dobre oddelené. Tendencia k tvorbe kompaktých zhlukov, nie však veľmi veľkých. Hierarchické aglomeratívne zhlukovanie Metóda priemernej vzdialenosti (stredospojná metóda, metóda priemernej väzby, average linkage, UPGMA - unweighted pair-group method using arithmetic averages) Medziskupinova (ne)podobnosťje definovaná ako priemerná (ne)podobnosť medzi všetkými možnými pármi členov. Metóda vedie často k podobným výsledkom ako metóda najvzdialenejšieho suseda. Hierarchické aglomeratívne zhlukovanie Centroidová metóda (Gowerova metóda, centroid method, UPGMC unweighted pair-group method using centroids) centrálny bod ABDEC 1 Táto metóda nevychádza už z agregacie informácií o medzizhlukových vzdialenostiach objektov. Kritérium je euklidovská vzdialenosť centroidov. Pri tejto metóde je vzdialenosť medzi zhlukmi počítaná ako vzdialenosť medzi centroidmi týchto zhlukov. Hierarchické aglomeratívne zhlukovanie Mediánová metoda (median method, WPGMC- weighted pair-group method using centroids, weighted centroid clustering) centrálny bod ABDEC centrálny bod ABDE Hierarchické aglomeratívne zhlukovanie Wardova metóda (Minimum variance clustering) Wardova metóda je podobná stredospojnej a centroidnej metóde. Kritérium pre spojovanie zhlukov je prírastok celkového vnútroskupinového súčtu štvorcov odchýlok pozorovaní od zhlukoveho priemeru. Prírastok je vyjadrený ako súčet štvorcov v novo vznikajúcom zhluku, zmenšený o súčty štvorcov v oboch zanikajúcich zhlukoch. Wardova metóda má tendenciu odstraňovať malé zhluky, teda tvoriť zhluky zhruba zhodnej veľkosti. 12 4 3 5 Hierarchické aglomeratívne zhlukovanie Metóda najbližšieho suseda by v dôsledku reťazového efektu spojila do jedného zhluku plné trojuholníky a do druhého prázdne trojuholníky, zatiaľ čo Wardova metóda a metóda priemernej vzdialenosti by priniesli skupiny ohraničené čiarami (podľa Everitt & Dunn 1983). Hierarchické aglomeratívne zhlukovanie Výsledkom hierarchického aglomeratívneho zhlukovania je dendrogram (strom). V tomto prípade boli použité: ♦ všespojná zhlukovacia metóda (complete linkage) ♦ miera vzdialenosti: Euklidovské vzdialenosti D1 I G1 B1 -------------1 r ______I K1 i__ ______i______j___r^ | I-------Ď2" I2 m 52 G2 I G3 i i i i ____________________i_____I I B2 ,v I3 K2 --------------------1 i i _________j—' I-------K3" V S2 S3 i J ■H i i 8 10 12 14 Linkage Distance 16 18 Dendrogram znázorňuje podobnosť spoločenstiev kôrovcov šiestich lokalít v záplavovej oblasti Dunaja v troch obdobiach ♦ 1 ♦ 2 ♦ 3 1991-1992 pred prehradením Dunaja 1993-1997 prvých 5 rokov po prehradení 1999-2004 ďalších 6 rokov po prehradení Sledované lokality: ♦ D: Dobrohošť ♦ G: Gabčíkovo ♦ B: Bodíky ♦ I: Istragov ♦ K: Kráľovská lúka ♦ S: Sporná sihoť Hierarchické aglomeratívne zhlukovanie Minimálna kostra (minimum spanning tree) graf, ktorý spojuje všetky objekty tak, že sa tu nevyskytujú žiadne smyčky alebo kružnice a zároveň súčty dĺžok spojníc medzi uzlami (objektami) je minimálny. 47 2---------4. 4.1 4.tí -<---------a---------0: 3 11 tí----------10--------28--------32--------2.3--------3.5--------25--------24--------i.tí---------17--------27--------33 13 Grafické zobrazenie je podobné hierarchii získanej pomocou zhlukovacej metódy najbližšieho suseda. Rozdiel je ten, že minimálna kostra zobrazuje tie objekty, ktoré sú za spojenie príslušných zhlukov zodpovedné. Výstup je možné zobraziť na ordinačnom diagrame. 54 44 3 12 53 1.4 30 2.3 3tí 13 43 22 13 7 42 .0 31 Hierarchické aglomeratívne zhlukovanie Metóda spojovania susedných objektov (neighbor-joining method) Metóda je podobná zhlukovacím metódam. Používa sa napr. k hodnoteniu dát získaných pri analýze dĺžkového polymorfizmu DNA, tj. v situáciách, kedy sú výsledkom analýz matice binárnych dat (přítomnost alebo neprítomnosť prúžkov v odpovedajúcich pozíciách na elektroforetickom gély). Je založená na genetickej vzdialenosti, ktorá závisí na počte zhodujúcich sa prúžkov v príslušných vzorkách. Pri výpočte vzdialenosti vytvorených zhlukov od zostávajúcich objektov sa postupuje podobne ako pri metóde priemernej vzdialenosti. Ale „susedné objekty" sa nespájajú tie, ktoré ležia najbližšie, ale tak, aby bol výsledkom čo najkratší strom (dendrogram). Dendrogram sa skladá z uzlov (node) spojených medziuzlami (intemode) a vetví (branch). nezakorenený dendrogram (unrooted) zakorenený dendrogram (rooted) NJ tree from Matrixfrom Example dal Unrooted NJ tree from Matrixfrom Example data set í rTrPíľj Hierarchické aglomeratívne zhlukovanie Výsledok klasifikácie je ovplyvnený rozhodnutím na niekoľkých úrovniach Zber dát Hrubé dáta Matica (ne) podobnosti dôležitostná hodnota (pokryvnosť, početnosť) transformácia, štandardizácia, meranie podobnosti zhlukovací algoritmus Dendrogram t Podľa Kovářa a Lepša (1986) majú transformácie väčší vplyv na výsledok zhlukovania než metódy zhlukovania. Kritické problémy analýzy ♦ Veľké množstvo parametrov alebo objektov v dendrograme je obtiažne interpretovať ♦ Analýza je silne závislá na zvolení vhodnej metriky vzdialenosti ♦ Analýza je silne závislá na zhlukovacom algoritme Hierarchické aglomeratívne zhlukovanie Zhody (ties) ♦ Při použití aglomeratívnych zhlukových metód môže nastať situácia, kedy sa v matici podobností vyskytujú tzv. zhody {ties) ♦ Najčastejšie dochádza k zhodám pri analýze binárnych dát, je tu veľká pravdepodobnosť rovnakej vzdialenosti medzi objektami ♦ Náhodné riešenie takejto situácie môže ovplyvniť výslednú klasifikáciu (dendrogram) A a - graf je úplný, b - graf je nesúvislý a všetky izolované komponenty sú úplné, c - graf je nesúvislý a aspoň jedna komponenta nie je úplná, d - graf je súvislý, ale nie je úplný Hierarchické aglomeratívne zhlukovanie Riešenie situácií a) spoja sa všetky objekty naraz b) paralelne sa vytvorí viac skupín (tzv. multiple fusion) c) a d) tri možnosti riešenia: 1 „silent mode (arbitrary)" Väzby sa riešia náhodne, spojí sa len posledná nájdená dvojica (je tu vplyv poradia objektov v primárnej matici) 2 „single linkage11 Všetky objekty, ktoré sú spojené väzbou, sa spoja do jedného zhluku 3 „suboptimal fusions" Nekompletné komponenty sa ignorujú a hľadanie najmenších vzdialeností v matici pokračuje kým sa už žiadne nekompletné komponenty nevyskytujú 0.7 o.e 0.5 l 0.4 0.3 0.2 O.l n O.7 O.6 O. 5 O.4 O.3 O.2 O.l HWPÍtf WtfE^ffl HWFÍtf WtfE^ffl O . 7 J l_^ 0.6 J n G.5 -M 0.4 -M 0.3 J O.2 -M O.l J Hwnfijflcs^ Hierarchické aglomeratívne zhlukovanie hierarchical techniques agglomerative clustering REÁLNE DATA ► 6 lokalít, každá lokalita monitorovaná v 3 obdobiach dátová matica: 18 vzoriek x 63 planktonnych druhov; hodnoty = stupeň dominancie single-linkage 7.0 7.5 8.0 8.5 Linkage Distance 9.5 D1 G1 B1 11 K1 S1 D2 I2 D3 G2 G3 B2 B3 I3 K2 S2 S3 K3 average-linkage -----1 —1~ ~l_ ---------1—-i r ■—i _______________. i——i i-——n ---------------------1 ^Ě^hm 8 9 10 11 12 13 14 Linkage Distance Dendrogramy vytvorené pomocou troch rôznych zhlukovacích algoritmov: single-linkage, average, and complete-linkage. V prvom prípade (single-linkage) je zjavné silné zreťazenie objektov. complete-linkage D1 G1 B1 11 K1 D2 I2 D3 G2 G3 B2 B3 I3 K2 K3 S1 S2 S3 i-----------n ----------------------1 _____________i -------------1 ________i --------------------1—l ---------------'—i— -----------------1—i i— i------------------- ________i i X 6 8 10 Linkage 12 U Distance \ 16 1£ Hierarchické aglomeratívne zhlukovanie Podobne môžeme počítať aglomeratívnu hierarchickú klasifikáciu (cluster analysis) pre premenné (napr. pre druhy). V tomto prípade bude zrejme rozumným merítkom distribučnej podobnosti druhu korelačný koeficient (merítko rozumnej podobnosti sa líši podľa toho, či porovnávame vzorky alebo druhy). 30 25 o o c (O tfí 5 o O) (O ■-, 10 20 15 rfi x n x rTft. £Si 2i x IL 1 JCXl izi-z _l ZCÜZQüjljjXOc£ljj potrebné určiť hraničné hodnoty (cut levels) Pôvodná tabuľka Species B Cirsium oleraceum 0 1 Glechoma hederacea 6 0 Juncus tenuis 15 25 cut levels 1,5 a 20 Tabuľka s pseudodruhmi použitými v TWINSPAN Species A B Cirsolerl 0 1 Glechedel 1 0 Glechede2 1 0 Junctenul 1 1 Junctenu2 1 1 Junctenu3 0 1 Hierarchické divizívne zhlukovanie hierarchical techniques divisive clustering ♦ začína so všetkými objektami ako s jednou skupinou ♦ skupina je rozdelená na dve menšie skupiny, ... monothetic method polythetic method 1 association analysis two way indicator species analysis * poskytuje jednoduchý binárny kľúč, ktorý sa dá použiť na klasifikovanie ďalších vzoriek O získané skupiny sú viac homogénne ako skupiny vytvorené monotetickou metódou len pre dáta prezencia/absencia získané skupiny - menej homogénne ako skupiny vytvorené polytetickou metódou konečná klasifikácia - nie robustná neposkytuje jednoduchý kľúč vhodný pre zaradenie novej vzorky do danej triedy (skupiny) predpokladá len jeden základný trend v dátach Hierarchické zh I u kovanie hierarchical techniques agglomerative clustering ,-TL Zhlukovanie je intuitívne => je to 'najpopulárnejšia klasifikačná metóda Výsledok je sumarizovaný v dendrograms -jednoduchá interpretácia Neexistuje „správny" zhlukovací algoritmus Výsledky sa dramaticky menia s • rôznym zhlukovacím algoritmom • rôznym indexom podobnosti Aglomeratívne zhlukovanie nieje efektívne pre veľmi veľké dáta i—i divisive clustering \^j jednoduchá interpretácia výsledkov divizívne techniky sú pre veľmi objemné objemné dáta vhodnejšie ako aglomeratívne techniky monotetická metóda nieje robustná polytetická metóda neposkytuje jednoduchý kľúč vhodný pre zaradenie novej vzorky do danej skupiny Nehierarchické zhlukovanie non-hierarchical techniques Nehierarchické zhlukovanie Objekty sú na základe zadaného počtu zhlukov rozdelené podľa kritéria maximálnej homogenity zhlukov. Ukážka rozdelenia objektov do zhlukov nehierarchickou metódou k-means clustering. Výsledok je ovplyvnený voľbou počtu zhlukov. Vľavo: počet zhlukov 3 je dobrá voľba; vpravo: počet zhlukov 2 je zlá voľba. Nehierarchické zhlukovanie Princíp nehierarchického zhlukovania ♦ Pre výpočet sa používa opakovaná relokačná procedúra. Začína s k skupinami a potom presúva objekty tak, aby minimalizovala variablitu vnútri skupín a maximalizovala variabilitu medzi skupinami. ♦ Relokačná procedúra sa ukončí, keď žiadny ďalší presun už kritéria nezlepší. ♦ Takto získavame však len lokálny extrém, nemáme istotu, že je zároveň globálnym extrémom ♦ Odporúča sa začať s rôznymi počiatočnými skupinami a sledovať, či sú výsledky týchto analýz rovnaké. Rizika analýzy ♦ pri chybnom odhade počtu zhlukov dáva metóda chybné výsledky ♦ výpočet je možný len na Euklidovských vzdialenostiach so všetkými jej obmedzeniami Nehierarchické zhlukovanie non-hierarchical techniques K-means clustering ♦ skupiny nie sú zahrnuté do väčších skupín, ani neobsahujú menšie skupiny ♦ rozdeľuje objekty do určitého počtu skupín ♦ K-means clustering pracuje s euklidovskými vzdialenosťami ^p Nehierarchické metódy môžu byť vhodnejšie ako hierarchické techniky • v prípade väčšieho objemu dát • v prípade, že v dátach neexistuje hierarchická štruktúra i—i počet skupín K je potrebné špecifikovať vopred užívateľom K-means clustering pracuje s euklidovskými vzdialenosťami => to môže byť problémom v prípade, keď euklidovská vzdialenosť nie je „najlepšiou" metrikou Zhluková analýza všeobecne Keď dáta nemajú úplne jednoznačnú a zreteľnú štruktúru Qedná sa viacmenej o náhodne rozptýlené objekty), je pravdepodobné, že použitie rôznych zhlukovacích techník prinesie odlišné výsledky. Pokiaľ rôzne zhlukovacie techniky prinášajú z toho istého súboru dát zhodné, resp. podobné výsledky, je to do istej miery potvrdenie štruktúry obsiahnutej v dátach (hoci zhlukovacie metódy patria k postupom produkujúcim hypotézy a nie sú určené k ich testovaniu). Mnohé zhlukovacie techniky sú citlivé na prítomnosť odľahlých objektov (outliers, výrazne atypické prípady). Pred samotnou zhlukovou analýzou je preto vhodné použiť niektorú z metód na ich detekciu, napr. PCA. Výrazne odľahlé objekty spravidla z ďalších analýz vylúčime. Zhlukové analýzy všeobecne nie sú vhodné na dáta, ktoré popisujú variabilitu znaku závislom na gradiente prostredia. Zhluková analýza súhrn Vstup zhlukovej analýzy: ♦ Matica podobnosti alebo vzdialenosti objektov ♦ Tabuľka objektov charakterizovaných niekoľkými parametrami Výstup zhlukovej analýzy: ♦ Strom (dendrogram) pri hierarchickej zhlukovej analýze ♦ Zaradenie objektov do vopred definovaného počtu zhlukov pri nehierarchickej analýze Pri použití zhlukovej analýzy je nutné pamätať na obmedzenia: ♦ aglomeratívne zhlukovanie nie je efektné pre veľmi veľké dáta ♦ pri hierarchickej aglomeratívnej analýze je výsledok silne ovplyvnený výberom indexu podobnosti, resp. metrikou vzdialenosti a zhlukovacím algoritmom ♦ / neexistuje správny zhlukovací algoritmus!!! ♦ pri hierarchickej divizívnej analýze: monotetická metóda nieje robustná; polytetická metóda predpokladá jeden hlavný trend v dátach a je ovplyvnená nastavením hraníc pseudo-druhov ♦ pri nehierarchickom zhlukovaní je nutné určiť počet skupín vopred