Multivariační analýzy v prostorových aplikacích – shlukování Geoinformatika a doprava Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 1 Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 2 −Lai, S., Erbach-Schoenberg, E.z., Pezzulo, C. et al. Exploring the use of mobile phone data for national migration statistics. Palgrave Commun 5, 34 (2019). https://doi.org/10.1057/s41599-019-0242-9 −Dostupné zde: https://www.nature.com/articles/s41599-019-0242-9 − −Otázky: −Data: −Jaký typ dat z mobilních telefonů byl použit? −Jaká další data byla použita? −Metodika: −Jak byla data zpracovávána? −Jaká byla přesnost modelů? −Diskuze: −Jaké jsou limity použitích metod? − ÚKOL Z MINULA Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 3 −Redukce množství dat a průzkumu multidimenzionálního atributového prostoru s cílem identifikovat malý počet zajímavých subdimenzí (resp. kombinací atributů), které pak mohou být zkoumány z prostorového hlediska (uplatnění klasických multivariačních metod a následně vizualizace výsledků a jejich interpretace). −Průzkumu prostorových vzorů) a vztahů. −Prostorová klasifikace a diskriminace („rozdělování)“. − − SHLUKOVÁNÍ – APLIKACE Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 4 −Shluková analýza je společný název pro celou řadu metod, jejichž cílem je využití informací z analýzy vícerozměrných dat k roztřídění množiny objektů do několika relativně homogenních podsouborů, označených jako shluky (clustery). −Objekty uvnitř shluků mají být co nejvíce podobné a objekty patřících do různých shluků co nejvíce rozdílné. Podobnost mezi objekty je uplatněna jako kritérium pro tvorbu shluků objektů. −Podobnost se měří různými prostředky: −míry korelace – korelační koeficienty (Pearsonův, Spearmanův) −míry vzdálenosti – euklidovská vzdálenost, Manhanattanská vz., … −míry asociace – nominální (kvalitativní) data – Sokalův-Michenerův koeficient asociace, Russelův-Raoův koeficient asociace, … − −Korelační a vzdálenostní míry jsou míry metrických dat − − SHLUKOVÁNÍ Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 5 −UNIVARIATE versus MULTIVARIATE − − ROZDĚLENÍ METOD – počet proměných Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 6 ROZDĚLENÍ METOD II. – princip Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 7 ROZDĚLENÍ METOD IIO. – „prostorovost“ −Lze pracovat jen s atributy! (bez prostorové složky) à Statistika apod. − −„Soft“ prostorové −K-means −DBSCAN - −„Hard“ prostorové −SKATER = Spatial `K’luster Analysis by Tree Edge Removal, −REDCAP = REgionalization with Dynamically Constrained Agglomerative clustering and Partitioning Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 8 −Metoda „k průměrů“ −algoritmus nehierarchické shlukové analýzy. −Předpokládá, že shlukované objekty lze chápat jako body v nějakém eukleidovském prostoru a že počet shluků k je předem dán (případně lze vyzkoušet různá k, pro každé spustit algoritmus znovu a výsledky porovnat). −Shluky jsou definovány svými centroidy −Objekty se zařazují do toho shluku, jehož centroidu jsou nejblíže. −Algoritmus postupuje iterativně tak, že se vyjde z nějakých (obvykle náhodně zvolených) centroidů, přiřadí do nich body, přepočítá centroidy tak, aby šlo o těžiště shluku bodů, pak opět přiřadí body k nově stanoveným centroidům a tak dál, až dokud se poloha centroidů neustálí. K-means Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 9 K-means K Means variable selection K Means cluster map (k=5) Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 10 −Např.: metoda nejbližšího souseda, Wardova metoda, … −aglomerační = opakované spojování dvou shluků až do jednoho počínaje jednotlivými objekty jako jednoprvkovými shluky −divizivní = opakované rozdělování nějakého shluku až na jednotlivé prvky počínaje jedním shlukem se všemi objekty −Grafické zobrazení: dendrogramu = stromový diagram −Vhodné pro aplikace vyžadující hierarchii shluků, např. taxonomie tříd objektů Hierarchické shlukování Single link hierarchical clustering toy example Nearest neighbors Single linkage iterations Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 11 Dendrogram (k=5) Hierarchical cluster map (Ward, k=5) −… Hierarchical clustering option Hierarchical clustering variable selection Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 12 −„Density-based spatial clustering of applications with noise“ −Vychází z hustoty definované pro blízké okolí každého objektu, z dosažitelnosti objektů zjištěné na základě této hustoty a propojenosti dvou objektů ověřené pomocí dosažitelnosti vybraných objektů −Není založen na vzdálenostech mezi objekty, a tím umožňuje nacházet shluky obecně libovolného tvaru (i shluky uvnitř jiného shluku) −Nevýhodou je nutnost zadat parametry hustoty, nebo minimální počet prvků ve shluku. − DBSCAN DBSCAN cluster map with d=3000 and MinPts = 4 Heat map with bandwidth of 3000 d=3000 MinPts = 4 Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 13 −GeoDa −QGIS −ArcGIS Pro − SOFTWARE Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 14 −Analýza hlavních komponent −Cílem je redukce původního počtu popisovaných proměnných novými veličinami (umělými), označenými jako komponenty, které shrnují informaci o původních proměnných za cenu minimální ztráty informace. − −Faktorová analýza −Cílem je popsat chování množiny cílových proměnných pomocí menšího počtu nových proměnných, označovaných jako faktory − −Diskriminační analýza −Slouží k nalezení pravidel resp. funkcí, podle kterých lze roztřídit objekty do jednotlivých známých tříd s využitím hodnot vybraných proměnných (diskriminátory). Další metody multivarianční analýzy Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 15 −HORÁK, Jiří. Prostorové analýzy dat. Ostrava: VŠB - Technická univerzita Ostrava, 2012. ISBN 978-80-248-4368-1. https://homel.vsb.cz/~hor10/Vyuka/PAD/PAD_skripta2022.pdf −https://gistbok.ucgis.org/bok-topics/classification-and-clustering −https://geodacenter.github.io/documentation.html −https://cs.wikipedia.org/wiki/K-means −https://core.ac.uk/download/161962896.pdf − ZDROJE Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 16 −mapování silničních a uličních sítí −logistika −plánování nové výstavby infrastruktury −sledování vozidel pomocí GPS −navigační systémy −aktuální zpravodajství o uzavírkách, dopravních nehodách a stavu vozovek −plánování silničních oprav −sjízdnost vodních toků −mapy cyklostezek a jejich poskytování prostřednictvím webových služeb −evidence vozidel −evidence letišť a nádraží a dalších dopravních uzlů −inteligentní mobilita −atd. … − − GEOINFORMATIKA V DOPRAVĚ Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 17 GEOINFORMATIKA V DOPRAVĚ 2.1 – The Geography of Transportation Networks | The Geography of Transport Systems Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 18 GEOINFORMATIKA V DOPRAVĚ −Statistický popis sítí −Síťová analýza – „stručně“ a „motivačně“ – více viz Aplikovaná geoinformatika − Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 19 Statistický popis sítí −Síť, hrany a uzly (nódy) −Deskriptory: −sítě jako celku: Gama index, Alfa index −relací jednotlivých segmentů sítě: stupeň uzlu (nodalita), acccessibility (dostupnost hran) − −Základním topologickým aspektem sítě je způsob propojení jednotlivých segmentů – konektivita −Matice konektivity − Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 20 Konektivita −Matice konektivity shrnuje informaci o tom, které segmenty sítě spolu souvisí (jsou bezprostředně spojeny). −Lze však charakterizovat i úroveň konektivity sítě jako celku. −Pro fixní počet vrcholů má síť s větším počtem spojů lepší konektivitu. Dále existuje minimální počet spojů, který zajišťuje spojení všech vrcholů. − − −v – počet vrcholů sítě, e – počet hran sítě potom: − −Minimálně propojená síť (Minimally conneted network – MCN): odstraníme–li jakoukoliv jednu hranu, síť se rozpadne na dvě části (subsystémy). −Beta index: podíl počtu hran a počtu vrcholů −Jednoduché sítě a stromy mají hodnotu menší než 1, komplexní sítě mají hodnotu vyšší než 1. Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 21 Gamma index −Poměr aktuálního a maximálního počtu vrcholů sítě − − − −Maximální počet hran lze vypočítat pro zadaný počet vrcholů, které spojují všechny vrcholy. Tedy maximální počet hran v síti o v vrcholech: − − − −Hodnoty gama indexu jsou mezi 0 a 1, kde hodnota 1 označuje zcela propojenou síť je velmi nepravděpodobná. −Gama index je efektivní hodnota pro popis vývoje sítě v čase. − − Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 22 Alfa index −Další jednoduchou charakteristikou konektivity sítě je počet okruhů. Výskyt okruhů v síti značí možnost dostat se z jednoho místa do jiného alternativními cestami. −Síť s minimální konektivitou nemá žádný okruh. −Počet okruhů lze zjistit tak, že od aktuálního počtu hran v síti odečteme počet hran potřebný pro minimálně propojenou síť (MCN), tedy e-(v-1) nebo e-v+1. −Obdobně pro daný počet vrcholů je maximální počet okruhů roven 2v-5. −S oběma uvedenými počty okruhů lze vytvořit poměr aktuálního počtu k počtu maximálnímu – tedy tzv. alfa index − − − −Stromy a jednoduché sítě budou mít hodnotu indexu 0. Hodnota 1 značí kompletně propojenou síť. −Alfa index měří úroveň konektivity sítě nezávisle na počtu uzlů. − − Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 23 Křivolakost −Skutečná délka linie dělena vzdáleností počátečního a koncového bodu −ENG: Detour index = actual route distance/ straight line distance × 100/1 −Lze aplikovat jak na jednotlivé linie (silnice, železnice), tak na celé sítě − − Hustota sítě −L: Délka linií (km), −S: plochu (km2). −Čím je síť hustší, tím je území rozvinutější. − Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 24 Nodalita, dostupnost hran −Jedná se o charakteristiku jednotlivých vrcholů či hran sítě. −Popisuje jejich dostupnost v rámci sítě. −Jednoduchým ukazatelem dostupnosti hrany v rámci sítě je, s kolika jinými hranami daná linie přímo souvisí. −Tuto informaci lze vyčíst z binární matice konektivity, pokud tuto doplníme řádkovým součtem. − − Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 25 Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 26 Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 27 −HORÁK, Jiří. Prostorové analýzy dat. Ostrava: VŠB - Technická univerzita Ostrava, 2012. ISBN 978-80-248-4368-1. https://homel.vsb.cz/~hor10/Vyuka/PAD/PAD_skripta2022.pdf −https://transportgeography.org/contents/chapter2/geography-of-transportation-networks/ −https://transportgeography.org/contents/methods/graph-theory-measures-indices/ −https://www.geographynotes.com/articles/4-important-measures-of-transport-networks-with-diagram/16 5 −Materiály předmětu Z6101 Základy geostatistiky − ZDROJE Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 28 Síťové analýzy −hledání nejkratší – viz Aplikovaná geoinformatika −optimální trasy −stanovení obsluhovaných oblastí −analýza nejbližšího střediska obsluhy či zařízení −matice nákladů – náklady pro přesun zboží mezi dvojicí bodů −obslužnost bodů více auty −vytvoření cestovního itineráře − − 191f6bdee8_46756272_o2.jpg Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 29 Síťový dataset Sit.png −uzly, hrany −hranově / uzlově ohodnocený graf −orientovaný graf, planární graf? − −pravidla konektivity (propojení) −atributy síťového datasetu: −Usage Type (role atributu): −Cost – náklad (časová délka) −descriptors – vlastnost hrany (počet jízdních pruhů) −restrictions – omezení směru (jednosměrka) −hierarchy – priority hrany (třída silnice) −Units, Data Type, Use by Default − − Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 30 Tvorba síťového datasetu −kontrola a oprava topologie −Must Not Have Pseudonodes −Must Not Overlap, Must Not Self-Overlap −File database > New… > Network dataset > Network dataset wizard −politika propojení hran (Endpoint Connectivity) −pravidla odbočování (Global Turns) −přidání a nastavení parametrů (Evaluators) − − −Lze využít existující (př.: ArcGIS Pro), ale …. top_ptavidla.gif u-turn.png Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 31 Tvorba síťového datasetu −Rychlost = náhrada (doplněk, povinný atribut) za(ke) vzdálenost(i) při tvorbě analýz −Slouží k výpočtu časové zátěže pro dané úseky a posléze také časové dostupnosti −Často se vychází z limitů (doporučených/průměrných…) rychlostí na jednotlivých třídách komunikací − Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 32 Hranově a uzlově ohodnocený graf Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 33 Optimální cesta −úloha obchodního cestujícího (úloha minimálního Steinerova stromu) −rozšíření předchozích, spojení více bodů – hledá se nejvýhodnější pořadí − − best_route.png Route2.png Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 34 Obsluhované oblasti −vytváří areály dané potřebnými náklady na cestu ze střediska služeb (Facilities) − − dojezdnost.png obsluhovane_polygony.png Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 35 Obsluhované oblasti − − Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 36 − − Obsluhované oblasti • https://is.muni.cz/auth/th/aujpp/ Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 37 Nebližší středisko obsluhy −hledá cestu mezi místem (Incident) a servisními středisky (Facilities) −opačný přístup než předcházející obsluhované oblasti − − neblizsi_sluzba.png Closest facility (static) | ArcGIS Maps SDK for Java | ArcGIS Developers Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 38 „OD“ matice −Origin – Destination Cost Matrix −vytváří matici nákladů na cestu z bodu do ostatních bodů (Facilities) − − od_matice.png od_matrix.png Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 39 Obslužnost bodů více auty − − − −„Rozvozní problém“, stanovení optimálních tras pro jednotlivé auta −výpočetně nejnáročnější − − veh_rout_pr.png vehicle_routing.png Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 44 „Loccation – allocation“ − − − −Řešíme vhodné umístění různých zařízení −Minimalizování impedance (zátěže), maximalizování pokrytí, minimalizování zařízení, maximalizování návštěvnosti, maximalizování podílu na trhu, cílový podíl na trhu − − Choosing the best fire station facilities Geografický ústav, Přírodovědecká fakulta, Masarykova Univerzita 45 Zdroje − − − −http://gisak.vsb.cz/~pen63/Systemy_GIS_v_PO/Navod_ke_cvicenim.pdf −http://webhelp.esri.com/arcgiSDEsktop/9.3/index.cfm?TopicName=welcome −http://gis-service.com/arcgis-network-analist-step-3/ −http://gis.zcu.cz/studium/agi/referaty/2009/Cejka_SilnicniDatasetProArcCR500/ −http://faculty.biu.ac.il/~shnaidh/zooloo/trnsprt2/ws_NetAnalystIntroSlides.pdf −http://geomatika.kma.zcu.cz/studium/dp/2009/Sladky__Sitove_analyzy_v_GIS_pro_slozky_IZS__DP.pdf −http://theses.cz/id/emr5ky/ − − −