RNDr. Eva Janousova IBA » Podzim 2015 Shluková analýza - typy metod - opakování 1. Krok Shluková analýza I Hierarchické shluky jsou definovány postupným skládáním objektů Nehierarchické shluky jsou definovány v jednom kroku 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. Divizivní objekty rozděleny do předem nastaveného počtu shluků. Aglomerativní síť spojených bodů oo Kolik shluků chceme Minimum spanning definovat? Například 4 tree, Prime network 2. Krok •• • OO oo X. Krok Atd. Atd. Výpočet ukončen Výpočet ukončen MU Janoušová: Vícerozměrné metody - cvičení ^j^- I^J 2 Příklad 1 V experimentu byla u 5 buněčných linií zjišťována kvantita membránových markerů popisujících jejich citlivost k chemoterapii. V přiložené tabulce naleznete změřené hodnoty standardizované na referenční buněčnou linii. Buněčná linie Marker 1 Marker 2 A 2 4 B 2 8 C 6 10 D 10 14 E 11 13 Vztahy mezi liniemi jsou vyjádřeny následující asociační maticí: 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 1. Výše uvedená asociační matice vyjadřuje podobnost nebo vzdálenost? A proč? 2. K výpočtu prvků asociační matice byl použit Jaccardův koeficient, Gowerův koeficient, Euklidova metrika nebo Hammingova (manhattanská) metrika? 3. Zdůvodněte vhodnost či nevhodnost použití tohoto koeficientu či metriky v případě těchto dat. 4. Vytvořte dendrogram pomocí algoritmu nejbližšího a nejvzdálenějšího souseda, rozepište jednotlivé kroky výpOČtU. Janoušová: Vícerozměrné metody-cvičení fl£ (j| 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 C\l V ( i / V J 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Dimenze 1 Janoušová: Vícerozměrné metody - cvičení IBA Metoda nejbližšího souseda: 4. krok výpočtu Je vypočtena asociační matice, kde objekty (A-B)-C již vystupují jako jeden objekt, jehož vzdálenost od ostatních objektů je dána nejmenší vzdáleností od jeho členů (A, B, C) A+B C D+E A+B 0.0 4.5 10.0 C 4.5 0.0 5.7 D+E 10.0 5.7 0.0 O A+B+C D+E A+B+C 0.0 5.7 D+E 5.7 0.0 • Je definován shluk dvou nejbližších objektů ((A-B)-C)-(D-E) • Všechny objekty jsou spojeny, algoritmus je ukončen C\l i ŕ i / V P / 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Dimenze 1 Janoušová: Vícerozměrné metody - cvičení IBA Metoda nejbližšího souseda: výsledek analýzy )- • Výsledek analýzy je vizualizován ve formě dendrogramu Metoda nejbližšího souseda: výsledek analýzy Pokud bychom v dendrogramu provedli řez na podobnosti/vzdálenosti 5, kolik dostaneme shluků? Které buněčné linie budou v jednotlivých shlucích? Výsledek interpretujte. Tree Diagram for 5 Cases Single Linkage Euclidean distances 2 3 4 Linkage Distance -> dostaneme 2 shluky: (A+B+C) a (D+E); přičemž linie D a E mají mnohem vyšší hodnoty obou markerů než linie A, B a C Janoušová: Vícerozměrné metody - cvičení IBA 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 C\l vt\í 3 / 2 \ J 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Dimenze 1 Janoušová: Vícerozměrné metody - cvičení IBA W 12 Metoda nejvzdálenějšího souseda: 4. krok výpočtu Je vypočtena asociační matice, kde objekty (D-E)-C již vystupují jako jeden objekt, jehož vzdálenost od ostatních objektů je dána největší vzdáleností od jeho členů (D, E, C) A+B C D+E A+B 0.0 7.2 12.8 C 7.2 0.0 5.8 D+E 12.8 5.8 0.0 A+B D+E+C A+B D+E+C 0.0 12.8 12.8 0.0 • Je definován shluk dvou nejbližších objektů ((D-E)-C)-(A-B) • Všechny objekty jsou spojeny, algoritmus je ukončen C\l 7 8 9 10 11 12 13 14 15 16 Dimenze 1 Janoušová: Vícerozměrné metody - cvičení IBA W 13 Metoda nejvzdálenějšího souseda: výsledek analýzy )- • Výsledek analýzy je vizualizován ve formě dendrogramu Janoušová: Vícerozměrné metody - cvičení ^jjj- 14 Metoda nejvzdálenějšího souseda: výsledek analýzy Pokud bychom v dendrogramu provedli řez na podobnosti/vzdálenosti 5, kolik dostaneme shluků? Které buněčné linie budou v jednotlivých shlucích? Výsledek interpretujte. Tree Diagram for 5 Cases Complete Linkage Euclidean distances 16 15 14 13 12 11 10 (N 9 JXL 8 ^^^^^^^^ f D \ y \ f 1 / J / 3 / / / // 8 \ / A 2 H / V ' \ ^^^^ ___' . . . . . . . . . . . . . . . . . . . . . . . . 0 1 2 3 4 £ 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Linkage Distance Marker 1 -> dostaneme 3 shluky: (A+B), (C) a (D+E); přičemž linie D a E mají vysoké hodnoty obou markem, A a B mají nízké hodnoty obou markerů a linie C má střední hodnoty markem MU Janoušová: Vícerozměrné metody - cvičení l^J 15 Metoda nejbližšího a nejvzdálenějšího souseda -interpretace výsledků Metoda nejbližšího souseda Metoda nejvzdálenějšího souseda B C D E Rozdílné zařazení objektu C 3 4 5 6 7 8 9 10 11 12 13 14 Linkage 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í B D E 3 4 6 7 8 9 10 11 12 13 14 Linkage 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á: Vícerozměrné metody - cvičení IBA W 16 Příklad 2 Bylo provedeno měření objemu hipokampu a mozkových komor (v cm3) u 5 pacientů se schizofrenií. Naměřené hodnoty objemu hipokampu a mozkových komor byly zaznamenány do matice XD: "4,6 3,4-1 6,1 3,0 6,7 3,1 6,2 2,3 .6,9 3,1. Určete podobnost pěti pacientů na základě naměřených charakteristik pomocí hierarchické shlukové analýzy, použijte metodu nejbližšího a nejvzdálenějšího souseda. Janoušová: Vícerozměrné metody - cvičení IBA W 17 Příklad 2 - asociační matice Nejprve vypočteme matici vzdáleností mezi objekty založenou na Euklidovské vzdálenosti: 1 2 3 4 5 1 0,0 1,6 2,1 1,9 2,3 2 1,6 0,0 0,6 0,7 0,8 3 2,1 0,6 0,0 0,9 0,2 4 1,9 0,7 0,9 0,0 1,1 5 2,3 0,8 0,2 1,1 0,0 Pro snadnější představu postupu výpočtu si jednotlivé objekty vykreslíme do jednoduchého xy grafu. 2 0 3«« 5 40 Janoušová: Vícerozměrné metody - cvičení IBA W 18 Metoda nejbližšího souseda - krok 1 1 2 3 4 5 1 0,0 1,6 2,1 1,9 2,3 2 1,6 0,0 0,6 0,7 0,8 3 2,1 0,6 0,0 0,9 0,2 4 1,9 0,7 0,9 0,0 1,1 5 2,3 0,8 0,2 1,1 0,0 1 2 3+5 4 1 0,0 1,6 2,1 1,9 2 1,6 0,0 0,6 0,7 3+5 2,1 0,6 0,0 0,9 4 1,9 0,7 0,9 0,0 10 20 T" 4 5 —i— 6 -i— 7 -1 8 Dendrogram Euklidovská vzdálenost 0.5 1 1.5 2 2.5 3 —i 5 — Janoušová: Vícerozměrné metody - cvičení IBA W 19 Metoda nejbližšího souseda - krok 2 1 2 3+5 4 1 2+3+5 4 1 0,0 1,6 2,1 1,9 1 0,0 1,6 1,9 2 1,6 0,0 0,6 0,7 _ 2+3+5 1,6 0,0 0,7 3+5 2,1 0,6 0,0 0,9 4 1,9 0,7 0,0 4 1,9 0,7 0,9 0,0 X, 10 Dendrogram Euklidovská vzdálenost 0.5 1 1.5 2 2.5 3 —i 5 —1 2 — Janoušová: Vícerozměrné metody - cvičení IBA W 20 Metoda nejbližšího souseda - krok 3 1 2+3+5 4 1 4+2+3+5 1 0,0 1,6 1,9 1 0,0 1,6 2+3+5 1,6 0,0 0,7 _ 4+2+3+5 1,6 0,0 4 1,9 0,7 0,0 X, 10 Dendrogram Euklidovská vzdálenost 0.5 1 1.5 2 2.5 3 —i 5 —1 2 — Janoušová: Vícerozměrné metody - cvičení I^J 21 Metoda nejbližšího souseda - krok 4 1 4+2+3+5 1 4+2+3+5 0,0 1,6 1,6 0,0 Metoda nejvzdálenějšího souseda - krok 1 1 2 3 4 5 1 2 3+5 4 1 0,0 1,6 2,1 1,9 2,3 1 0,0 1,6 2,3 1,9 2 1,6 0,0 0,6 0,7 0,8 -> 2 1,6 0,0 0,8 0,7 3 2,1 0,6 0,0 0,9 0,2 3+5 2,3 0,8 0,0 1,1 4 1,9 0,7 0,9 0,0 1,1 4 1,9 0,7 1,1 0,0 5 2,3 0,8 0,2 1,1 0,0 10 "T" 4 5 20 40 —i— 6 -i— 7 -1 8 3 —i 5 — Dendrogram Euklidovská vzdálenost 0.5 1 1.5 2 2.5 Janoušová: Vícerozměrné metody - cvičení IBA W 23 Metoda nejvzdálenějšího souseda - krok 2 1 2 3+5 4 1 0,0 1,6 2,3 1,9 2 1,6 0,0 0,8 0,7 3+5 2,3 0,8 0,0 1,1 4 1,9 0,7 1,1 0,0 1 2+4 3+5 1 0,0 1,9 2,3 2+4 1,9 0,0 1,1 3+5 2,3 1,1 0,0 X, 10 Dendrogram Euklidovská vzdálenost 0.5 1 1.5 2 2.5 3 —i 5 — 2 — 4 — X, Janoušová: Vícerozměrné metody - cvičení IBA W 24 Metoda nejvzdálenějšího souseda - krok 3 1 2+4 3+5 1 4+2+3+5 1 0,0 1,9 2,3 1 0,0 2,3 2+4 1,9 0,0 1,1 _ 4+2+3+5 2,3 0,0 3+5 2,3 1,1 0,0 X, 10 Dendrogram Euklidovská vzdálenost 0.5 1 1.5 2 2.5 3 —i 5 —1 2 — 4 — Janoušová: Vícerozměrné metody - cvičení I^J 25 Metoda nejvzdálenějšího souseda - krok 4 1 4+2+3+5 1 4+2+3+5 0,0 2,3 2,3 0,0 Srovnání metody nejbližšího a nejvzdálenějšího souseda X, Metoda nejbližšího souseda Dendrogram Euklidovská vzdálenost 0 0.5 1 1.5 2 2.5 3 I_I_I_I_I_I_I 3 —i 5 —1 2 — 4 1 "T-1-1-1- 3 4 5 6 X1 7 8 X, , ,,, v.v,. - Dendrogram Metoda nejvzdalenejsího souseda Euklidovská vzdálenost 0 0.5 1 1.5 2 2.5 _i_i 3 —i 5 — 2 — 4 1 -> metoda nejbližšího souseda má tendenci vytvářet protáhlé shluky Janoušová: Vícerozměrné metody - cvičení IBA W 27