Metody fyzické geografie 3:
Biogeografie & ekologie
Jan Divíšek
Geografický ústav & Ústav botaniky a zoologie
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Metody fyzické geografie 3 – 14. 11. 2017
• Teoretická část
• Hierarchické klasifikační metody
• Výběr optimálního počtu klastrů
• Praktická část
• UPGMA
• Wardova metoda + transformace matice vzdáleností
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Hierarchické klasifikační metody
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Základní typy klasifikačních metod
Klasifikační
metody
Nehierarchické Hierarchické
Divizivní Aglomerativní
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Hierarchická aglomerativní shluková analýza
• Shluky jsou hierarchicky uspořádány (výsledkem je klasifikační strom =
dendrogram)
• Shluky jsou tvořeny „odspodu“, tzn. postupným shlukováním jednotlivých vzorků
do větších skupin
• Obecný postup shlukové analýzy:
1. Volba vhodného indexu vzdálenosti (ekologické nepodobnosti)
2. Výpočet matice vzdáleností
3. Volba shlukovacího algoritmu (jakým způsobem budou vzorky shlukovány)
4. Aplikace shlukovacího algoritmu (clustering algorithm) na matici vzdáleností
5. Volba výsledného počtu shluků, který budu interpretovat
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Dendrogram
• záleží na tom, které vzorky jsou spojeny na které úrovni
• nezáleží na tom, který vzorek (skupina) je vpravo a který vlevo
1
5
6
7
2
10
11
18
17
19
14
16
15
20
13
12
4
3
8
9
0.00.51.01.52.02.5
distance
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Nejpoužívanější algoritmy
• Single linkage
• Complete linkage
• Flexible clustering
• Average linkage (UPGMA, WPGMA, UPGMC, WPGMC)
• Wardova metoda
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Single & complete linkage
Sigle linkage (metoda jednospojná)
• Uvažuje nejpodobnější vzorky → vzorek se připojí ke shluku, ve kterém ne
nejpodobnější snímek
Complete linkage (metoda všespojná)
• Uvažuje nejméně podobné vzorky → vzorek se připojí ke shluku, ve kterém je
nejpodobnější snímek
single linkage
complete linkage
hclust()
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Jak funguje Single linkage?
Matice podobností Páry vzorků seřazené podle podobnosti
Výsledný dendrogram
Legendre & Legendre (2012)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Single & complete linkage
• Single linkage se výrazně řetězí
17
19
11
18
1
2
10
5
6
7
13
12
4
3
8
9
14
16
15
20
Bray-Curtis distance / Complete linkage
17
19
1
14
16
15
20
11
18
13
12
2
10
5
6
7
4
3
8
9
Bray-Curtis distance / Single linkage
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Flexible clustering
Beta flexible
• Nastavení parametru β ovlivňuje řetězení
dendrogramu
• Nejvíc se řetězí pro β ~ 1, nejméně pro β
= -1
• optimální reprezentace vzdáleností mezi
vzorky je při β = -0,25
Legendre & Legendre (2012)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Average linkage
• Zahrnuje řadu metod, které stojí mezi single a complete linkage a v ekologii jsou
smysluplnější
• Unweighted pair-group method using arithmetic averages (UPGMA)
• Vzorek se připojí ke shluku, ke kterému má největší (neváženou) průměrnou podobnost se
všemi jeho vzorky
• Další metody
• Weighted arithmetic average clustering (WPGMA)
• Unweighted centroid clustering (UPGMC)
• Weighted centroid clustering (WPGMC)
6
5
7
2
10
17
19
1
11
18
14
16
15
20
13
12
4
9
8
3
Euclidean distance / UPGMA
hclust()
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Úkol
• Zkonstruujte ručně dendrogram metodami single linkage, complete linkage a
average linkage
A 100
B 30 100
C 20 10 100
D 50 10 30 100
E 60 40 20 10 100
A B C D E
Matice podobností pěti vzorků A - E
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Řešení
C
B
D
A
E
0.400.450.500.550.600.650.70
Cluster Dendrogram
hclust (*, "single")
dis.d
Height
B
A
E
C
D
0.40.50.60.70.80.9
Cluster Dendrogram
hclust (*, "complete")
dis.d
Height
B
A
E
C
D
0.40.50.60.70.80.9
Cluster Dendrogram
hclust (*, "complete")
dis.d
Height
Single linkage Complete linkage UPGMA
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Wardova metoda
Ward’s minimum variance method (Ward, 1963)
• Ke shluku se připojí vzorek, jehož vzdálenost od
centroidu shluku je nejmenší
• Počítáno přes čtverce vzdáleností mezi vzorky a
centroidy shluků (stejně jako v k-means
clustering)
• Vzdálenosti od centroidu počítá euklidovskými
vzdálenostmi → podmínkou je, aby bylo možné
s maticí vzdáleností pracovat v euklidovském
prostoru
2
10
6
5
7
17
19
1
11
18
14
16
15
20
13
12
4
9
8
3
Euclidean distance / Ward's method
hclust()
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Indexy vzdálenosti v euklidovském prostoru
1. Metrické indexy
• Minimum = 0: jestliže a = b, potom D(a, b) = 0
• Všechny hodnoty jsou pozitivní: jestliže a ≠ b, potom D(a, b) > 0
• Jsou symetrické: D(a, b) = D(b, a)
• Splňují podmínku trojúhelníkové nerovnosti: D(a, b) + D(b, c) ≥ D(a, c)
→ vzdálenosti mohou být vynášeny v euklidovském prostoru
→ „euklidovský index“
2. Semimetrické indexy
• Nesplňují podmínku trojúhelníkové nerovnosti: D(a, b) + D(b, c) < D(a, c)
→ vzdálenosti NEmohou být vynášeny v euklidovském prostoru
→ „neeuklidovský index“
3. Nemetrické indexy
• Mají negativní vzdálenosti
a c
b
a c
b
Legendre & Legendre (2012)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Semimetrické („neeuklidovské“) indexy
• V případě, že vzdálenosti (ekologické nepodobnosti) nemohou být vynášeny
euklidovskou geometrií, lze použít korekci
• Cailiez (1983)
• korekce spočívá ve vyhledání nejmenší možné hodnoty (konstanty), kterou následně přičte ke
všem členům matice vzdáleností
• Lingoez (1971)
• vyhledá hodnotu (konstantu), kterou transformuje matici vzdáleností podle rovnice
𝐷𝑖𝑗
′
= 𝐷𝑖𝑗
2
+ 2 × 𝑘
cailliez {ade4}
lingoes {ade4}
Cailliez, F. (1983) The analytical solution of the additive constant problem. Psychometrika, 48: 305–310.
Lingoes, J.C. (1971) Some boundary conditions for a monotone analysis of symmetric matrices. Psychometrika, 36: 195–203.
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Aplikace Wardovy metody
Výpočet matice vzdáleností
Lze s maticí pracovat v
euklidovském prostoru?
is.euclid {ade4}
Aplikace Wardovy metody Korekce matice vzdáleností
cailliez {ade4}
lingoes {ade4}
Aplikace Wardovy metody
TRUE FALSE
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Aplikace Wardovy metody
• V literatuře se objevují dva různé způsoby výpočtu Wardovy metody
1. Při tvorbě klastrů jsou používány prosté vzdálenosti → neodpovídá původnímu Wardovu
(1963) algoritmu
• ve funkci hclust atribut ward.D
• ve verzích R <= 3.0.3 je pouze tento algoritmus (označen jako ward)
2. Při tvorbě klastrů jsou používány čtverce vzdáleností → původní Wardův (1963) algoritmus
• ve funkci hclust atribut ward.D2
hclust()
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Jaký je „optimální“ počet shluků?
1
5
6
7
2
10
11
18
17
19
14
16
15
20
13
12
4
3
8
9
0.00.51.01.52.02.5
distance
k = 2
k = 3
k = 4
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Silhouette
• Hodnotí stupeň podobnosti daného vzorku ke
klastru, do kterého byl zařazen, a srovnává ho
s jeho podobností k nejbližšímu jinému klastru
• Negativní hodnoty – tyto vzorky byly s velkou
pravděpodobností špatně klasifikovány (ve
skutečnosti patří jinam)
Borcard et al. (2011)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Mantelova korelace
• Porovnává matici vzdáleností vzorků s binární maticí zařazení vzorků do
jednotlivých shluků
• 1 – pokud jsou dva vzorky ve stejném shluku
• 0 – pokud je každý v jiném shluku
Samp1 Samp2 Samp3 Samp4 Samp5
Samp1 0 0.50 0.39 0.50 0.42
Samp2 0.50 0 0.57 0.68 0.67
Samp3 0.39 0.57 0 0.49 0.57
Samp4 0.50 0.68 0.50 0 0.67
Samp5 0.42 0.67 0.57 0.67 0
Samp1 Samp2 Samp3 Samp4 Samp5
Samp1 0 0 1 1 1
Samp2 0.50 0 0 0 0
Samp3 0.39 0.57 0 1 0
Samp4 0.50 0.68 0.50 0 0
Samp5 0.42 0.67 0.57 0.67 0
Matice vzdáleností Matice zařazení snímků
Borcard et al. (2011)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
(Jaccard, Sørensen, β-sim, Hellinger…)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Prostorově omezené shlukování
• Modifikace tradičních shlukovacích metod
• Shlukuje vzorky podle jejich podobnosti (vzdálenosti), ale pouze ty, které spolu
sousedí podle zvoleného schématu propojenosti vzorků
• Do procesu shlukování vstupuje:
1. Matice vzdáleností (nepodobností) vzorků (distance/dissimilarity matrix)
2. Matice propojenosti vzorků (connectivity matrix)
• 1 = propojené (sousedící) vzorky
• 0 = nepropojené (nesousedící) vzorky
• Výhody
• Vytváří prostorově kompaktní shluky, které jsou často lépe interpretovatelné
• Díky prostorovým omezením dávají různé klasifikační algoritmy podobné výsledky
• Nevýhody
• Shluky jsou vnitřně více heterogenní než v případě neomezené klasifikace
• Výsledek značně závisí na volbě schématu propojenosti vzorků (další arbitrární rozhodnutí)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Prostorově omezené shlukování
Legendre & Legendre (2012)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Schémata propojenosti
• Vzorky rozmístěné v pravidelné síti
• Rook connection
• Bishop connection
• Queen connection
• Kritérium vzdálenosti
• Vzorky rozmístěné nepravidelně
• Delaunay triangulation
• Gabriel criterion
• Relative neighbourhood
• Maximum distance
• Minimum spanning tree (MST)
Fortin & Dale (2005)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Delaunay triangulation
• Trojice vzorků je propojena pouze pokud kružnice, na které tyto vzorky leží
neobsahuje žádný další bod
Legendre & Legendre (2012)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Gabriel criterion
• Dvojice vzorků je propojena pouze pokud kružnice procházející těmito vzorky
neobsahuje žádný další vzorek
Legendre & Legendre (2012)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Relative neighbourhood
• Dvojice vzorků je propojena pouze pokud průnik kružnic, jejich poloměr se rovná
vzdálenosti mezi body neobsahuje žádný další vzorek (vzorky tvoří středy kružnic)
Legendre & Legendre (2012)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Maximum distance
• Vzorky jsou propojeny na základě kritéria vzdálenosti
Legendre & Legendre (2012)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Minimum spanning tree (MST)
• Spojuje n vzorků n-1 spojnicemi tak, aby součet jejich délek byl minimální
Legendre & Legendre (2012)
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Software
• Pro hierarchické aglomerativní metody
• funkce constrained.clust v knihovně const.clust (není na CRANu, ale zde)
• Pro nehierarchické metody
• spatially constrained k-means v S.A.M.
• Grouping Analysis v ArcGIS
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Metodyfyzickégeografie3:Biogeografie&ekologieJanDivíšek
Literatura
• Legendre, P. & Legendre, L. (2012): Numerical ecology. Third Edition. Elsevier,
Amsterdam.
• Borcard, D., Gillet, F. & Legendre, P. (2011): Numerical ecology with R. Springer,
New York.
• Koleff, P., Gaston, K.J. & Lennon, J.J. (2003): Measuring beta diversity for
presence–absence data. Journal of Animal Ecology, 72(3): 367–382
• Fortin, M-J. & Dale, M.R.T. (2005): Spatial analysis: a guide for ecologists.
Cambridge University Press. New York.