Zh I u ková analýza MU IBA 'nštitút bioštatistiky a analýz, Masarykova univerzita ♦ Mnohorozmerné metódy: 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 »Qh o KT 30 podobnosť RDINACI ♦ Usporadúva vzorky pozdĺž trendu v dátach rO vet Faktorové osi hl£ž y x X Zh I u ková 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 3 3 "U 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 Zh I u ková 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áta ♦ Tabuľka spojitých alebo katego-riálnych dat popisujúca objekty t- CM CO Výstupy analýzy ♦ 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 Zh I u ková analýza hierarchical techniques ♦ skupiny usporiadané do hierarchickej štruktúry single-linkage clustering average-linkage clustering complete-linkage clustering ... agglomerative clustering M divisive clustering H 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 o (x19x2) = 2a + b + c ^9 V^l ? "^2 ) 3a 3a + b + c Jaccardov koeficient a O'y l ./Vi 2 «A"2 y ---- a + Z? + c Sorensenov kvantitatívny koef. C = 2jN (aN + bN) Morisota-Horn index ^mH {da + db).aN.bN J] an? da- aN' Hierarchické aglomeratívne zhlukovanie Metriky vzdialenosti Euklidovská vzdialenosť A(*i>*2)= \Zli (yji~yj2 í Vážená euklidovská vzdialenosť d90i>*2)=JZL rf(yji - y^ý Manhattanská vzdialenosť p D7(xl,x2) = YJ\yji-yJ: 7=1 Minkowski (power distance) D6\xl,x2) — p H\yji-y. 7=1 J2 Á 1 I 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 f^_ + ♦ 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 souseda (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) Medziskupinová (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 agregácie 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 vnutroskupinoveho 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 _________I M K1 i_ r~ D2 I2 G2 ____Qi I I |_ __________________r^ B2 ,v I3 K2 ----------------------1^—i __________i—' I-------K3" x/ S1 V S2 S3 n J 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: 1991-1992 pred prehradením Dunaja ♦ 2: 1993-1997 prvých 5 rokov po prehradení ♦ 3: 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álni 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ĺžky spojnice medzi uzlami (objektami) je minimálny. *F 2----------4j ^.i "*.£ ■?----------a----------$: 3 11 tí----------1.0--------28--------32--------23--------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. 3 12 5ti 1.4 30 23 3tí 13 43 22 13 7 42 54 44 p 31 51 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 výsledkom analýz sú 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 (\ntemode) a vetví (branch). nezakorenený dendrogram {unrooted) zakorenený dendrogram (rooted) N J tree from Matrix fro m Example data set Unrooted NJ tree from Matrixfrom Example data set n rfvrvh 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 i 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)11 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 f 0.4 0.3 0.2 O.l II O.7 O.6 O.5 O.4 O.3 O.2 O.l HNntfififl^ffl O.7 H O.6 O.5 A ^5 0.4 O.3 H O.2 O.l A HWFÍtf WtfE^ffl i HWFÍW tftffflř- 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 D1 D2 __________J---------1 I2 D3 I3 K2 K3 S2 n_ r- h I------------------ S3 B2 _________i __________________|— B3 G3 S1 G1 1 B1 G2 11 K1 _______1 M 6 0 6.5 7.0 7.5 8 Linkage Dis 0 tan 8 ce 5 9.0 9.5 average-linkage D1 Gl ----------1-------------------1 B1 ________i M —i- ____. Kl S1 D2 I2 i—^-i D3 G2 G3 B2 i--------- B3 I3 i ____________J—i K2 S2 S3 K3 ---------------------^n 1-------------------' 8 9 10 11 Linkage Distance 12 13 14 complete-linkage D1 Gl -------------1 r B1 11 i i__ K1 D2 i i I2 D3 i i G2 i__ G3 B2 i i______ B3 ■ i I3 i f K2 K3 i 1 S1 S2 J i i S3 i 8 10 12 14 Linkage Distance 16 18 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. 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). Hierarchické divizívne zhlukovanie hierarchical techniques divisive clustering ♦ delenie prebieha „zhora"; začína všetkými objektami ako s jednou skupinou ♦ rozdelenie súboru na 2 časti ♦ ďalšie delenie častí Časté použitie ku klasifikácii biologických spoločenstiev Hierarchické divizívne zhlukovanie hierarchical techniques — divisive clustering monothetic method association analysis Puc. mar. Agro. sto. ♦ delenie na základe jedného parametra ♦ najprv je nájdený druh, ktorý je najviac asociovaný s ostatnými druhmi; skupiny sú rozdelené na základe prezencie/absencie tohto druhu ♦ metóda citlivá na prítomnosť vzácnych druhov a neprítomnosť bežnejších druhov Psor. lur. + Sper, med + Glau. mar. Cera, atr. + Coch. dan. IV V VI VI K/IN polythetic method l two way indicator species analysis A binary key for identifying types of salt-marsh habitat (Ivemey-Cook, Proctor 1966) TWINSPAN Hierarchické divizívne zhlukovanie polythetic method I two way indicator species analysis TWINSPAN ♦ delenie skupiny je založené na všetkých druhoch podľa ich skóre na prvej osi vytvorenej ordináciou (v TWINSPAN-e korešpondenčná analýza) ♦ dichotómia vzniká ordináciou lokalít na základe diferenciálnych druhov ♦ berie do úvahy aj abundancie druhov vo forme tzv. pseudo-druhov => potrebné určiť mezné hodnoty (cut levels) Pôvodná tabuľka Species B Cirsium oleraceum 0 1 Glechoma hederacea 6 0 Juncus tenuis 15 25 cut levels 0,1, 5 a 20 Tabuľka s pseudodruhmi použitými v TWINSPAN Species B Cirsolerl 0 1 Glechedel 1 0 Glechede2 1 0 Junctenul 1 1 Junctenu2 1 1 Junctenu3 1 1 Junctenu4 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 ^1 poskytuje jednoduchý binárny kľúč, ktorý sa dá použiť na klasifikovanie ďalších vzoriek ^\ 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é zhlukovanie hierarchical techniques agglomerative clustering ^u 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 \^3 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 c^zi 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 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 (jedná 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 ill ♦ 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