2. Charakteristika vstupních dat mkweb.bcgsc.ca technology.sbkb.org www.padowan.dk axblog4u.wordpress.com Jak probíhá vizualizace dat • Generování dat – Měření, simulace, modelování • Může být velmi dlouhé (měření, simulace) i velmi drahé (simulace, modelování) • Vizualizace (zbytek vizualizační pipeline) – Vizuální mapování, renderování • Může být rychlá nebo pomalá, v závislosti na hardware a implementaci • Interakce (user feedback) – Jak může uživatel interagovat Pasivní vizualizace • Tyto tři kroky jsou striktně odděleny – Generování dat – po skončení této fáze – Off-line vizualizace • Zobrazení vygenerovaných dat • Výsledkem je video nebo animace – Pasivní vizualizace • Prohlížení výsledků předchozí fáze Interaktivní vizualizace • Pouze fáze generování dat je oddělena – Off-line generování dat – Interaktivní vizualizace • Generovaná data jsou dostupná pro interaktivní vizualizaci • Možnosti: výběr, parametrizace vizualizačních technik • V současnosti velmi populární a rozšířené Interaktivní řízení (steering) • Všechny tři kroky jsou spojeny – Generování dat „on the fly“ – Interaktivní vizualizace umožňující „real-time“ náhled na data – Rozšířené možnosti interakce • Uživatel může ovlivňovat průběh simulace, změnit design při modelování, atd. • Velmi náročné na provedení i náklady Srovnání Data • Jsou ústředním tématem vizualizace, vše se točí kolem dat • Data ovlivňují výběr vhodné vizualizační techniky (výběr ovlivňuje samozřejmě i uživatel) • Důležité otázky: – Kde data „žijí“ (jaký je datový prostor) – Typ dat – Jaká reprezentace je smysluplná blogs.agi.com Datový prostor • Různé vlastnosti – Dimenzionalita datového prostoru – Souřadný systém – Region vlivu (lokální nebo globální dopad) wiki.brown.edu en.wikipedia.org Definice dat • Raw (surová) data x předzpracovaná data • Data ve tvaru (r1, r2, …, rn) • Každý ri záznam obsahuje m proměnných (v1, v2, …, vm) • vi je často označována jako pozorování Definice proměnných • Nezávislá (ivi) proměnná – není ovlivněna jinou proměnnou (např. čas) • Závislá (dvj) proměnná – je ovlivněna jednou nebo více nezávislými proměnnými (např. teplota) • Záznam tedy může být reprezentován ve tvaru ri = (iv1, iv2, …, ivmi, dv1, dv2, …, dvmd) kde m = mi + md Data generovaná pomocí funkce • Nezávislé proměnné = definiční obor • Závislé proměnné = obor hodnot mathworld.wolfram.com Typy proměnných • Fyzické typy – Charakterizovány vstupním formátem – Charakterizovány typem možných operací – Příklad: bool, string, int, float,… • Abstraktní typy – Popis dat – Charakterizovány metodami/atributy – Mohou mít hierarchickou strukturu – Příklad: rostliny, zvířata, … Typy dat • Ordinální – Binární – Diskrétní – Spojitá • Nominální – Kategorická – Setříděná – Náhodná www.123rf.com orgmode.org www.forbes.com www.icoachmath.com tennysusantobi.blogspot.com www.cincomsmalltalk.com Scale – měřítko • 3 základní atributy: – Relace uspořádání na datech – Vzdálenostní metrika – Existence absolutní nuly • Fixace minimální hodnoty proměnné Reprezentace dat • Závisí na: – Přítomnosti vlastní prostorové domény • Pokud není, jakou prostorovou doménu zvolit? – Jak jsou využity jednotlivé dimenze? • Charakteristika dat • Dostupný prostor pro zobrazení (2D/3D) • Na kterou část dat se zaměřujeme (focus)? • Ve kterých částech lze naopak abstrahovat? Datový prostor vs. vlastnosti dat Příklady • Diskrétní data – sada hodnot, vizualizace pomocí sloupcových grafů, koláčových grafů, … wiki.opossem.org Příklady • Spojitá data – funkce, vizualizace pomocí grafů www.isanybodylistening.com.au Příklady • 2D reálná čísla – Funkce dvou proměnných, vizualizace pomocí 2D výškových map, kontur ve 2D, … acko.net timothyandrewbarber.blogspot.com Příklady • 2D vektorová pole, vizualizace pomocí tzv. hedgehog plots, LIC (line integral convolution), streamlets, … en.wikipedia.org csis.pace.edu www.cg.tuwien.ac.at Příklady • Prostorová data + čas – 3D tok, vizualizace pomocí tzv. streamlines, streamsurfaces www.solartornado.info www2.cs.uh.edu Příklady • Prostorová data – 3D hustota, vizualizace pomocí izopovrchů, volume rendering www.ssg-surfer.com viscg.uni-muenster.de Příklady • Multidimenzionální data – Sada n-tic, vizualizace pomocí paralelních souřadnic, glyfů, ikon, … datamining.typepad.com www.emeraldinsight.com www.cs.umd.edu Struktura uvnitř a mezi záznamy • Datové množiny mají: – Syntaxi – způsob reprezentace (tzv. datový model) – Sémantiku – vztahy uvnitř jednoho záznamu nebo mezi záznamy (tzv. konceptuální model) • Typy struktur: – Skaláry, vektory, tenzory – Geometrie a gridy – Jiné formy hamiltonhealth.ca Skaláry, vektory a tenzory • Skalár = jednotlivé číslo v datovém záznamu – např. věk • Vektor = kompozice několika proměnných do jednoho záznamu – např. bod ve 2D prostoru, RGB barva • Tenzor = definován řádem a dimenzí prostoru, ve kterém je definován. Reprezentován pomocí pole nebo matice. – např. transformační matice ve 3D Geometrie a gridy • Geometrie zaznamenána pomocí souřadnic záznamů • Grid – geometrii lze odvodit ze startovní pozice, orientace a velikosti kroku v horizontálním a vertikálním směru m.ihned.cz danielwalsh.tumblr.com Neuniformní geometrie • Je nutné uchovávat souřadnice všech záznamů – nejdou odvodit • Neuniformní grid www.scielo.org.mx www.tafsm.org blog.nasm.si.edu Jiné formy struktur • Další důležitou strukturou je topologie • Definuje tzv. konektivitu • Významná při převzorkování a interpolaci xpertnetworking.wordpress.comwww.bugman123.com Čas • Obrovský rozsah hodnot (pikosekundy vs. tisíciletí) • Vyjádřen absolutně nebo relativně • Datové množiny obsahující časovou složku mohou být rozloženy rovnoměrně (pravidelný sampling) i nerovnoměrně (zpracovávání transakcí – podle doby jejich přijetí a zpracování) megworden.com Další příklady strukturovaných dat • Magnetická rezonance (MRI) • Computational fluid dynamics (CFD) • Finančnictví • CAD systémy • Sčítání lidu • Sociální sítě www.demografie.infosuccessfulworkplace.com www.impactlab.net lotusenthusiast.net www.mjmdesigns.co.uk Taxonomie – 7 typů dat • 1D (lineární sady a sekvence) • 2D (mapy) • 3D (objekty, tvary) • nD (relační) • Stromy (hierarchie) • Sítě (grafy) • Temporální www.janscholten.com Lineární data • Dlouhé seznamy položek – Položky menu – Zdrojový kód • Fisheye displays http://ds.cc.yamaguchi-u.ac.jp/~ichikay/pfp7/iv/pics/SeeSoft-line.jpg http://ds.cc.yamaguchi-u.ac.jp/~ichikay/pfp7/iv/pics/SeeSoft-line.jpg http://www.cs.umd.edu/hcil/fisheyemenu/ 2D data - mapy • GIS (geografické informační systémy) – Zobrazení map (např. Google Earth) http://www.youtube.com/watch?v=ouqjv1MBmI8 http://www.wimp.com/unusualplaces/ – Prostorové dotazování – Prostorová analýza dat www.bowdoin.edu 3D data • Různé typy zobrazení 3D dat • Scientific visualization en.wikipedia.org www.ornl.gov gvis.grc.nasa.gov Multidimenzionální data • Záznamy v relační databázi • Dvě řešení: – Vykreslení všech možných párů proměnných ve 2D grafu • Jednoduché, ale nepoužitelné pro zobrazení dat jako celku – „Paralelní souřadnice“ • Metoda pro vykreslení multidimenzionálních dat (Alfred Inselberg) en.wikipedia.org Paralelní souřadnice andrewgelman.com eagereyes.org Paralelní souřadnice vis.lbl.gov whyevolutionistrue.wordpress.com Stromy • Nutné zobrazit nejen data, ale i jejich strukturu – např. rodokmen, file systém • Počet dat významně roste při sestupování do nižších vrstev vtipy7.blog.cz Stromy • Tree Maps – Zobrazení stromových dat ve formě vnořených obdélníků – Mapa o milionu záznamů: www.cs.umd.edu Sítě • Podobná situace jako u stromů – nutné zobrazovat data i jejich strukturu • Síť = uzly + hrany • Návrh by měl zahrnovat: – Minimální průniky hran – Minimální délky hran – Minimální ohýbání hran archaeologicalnetworks.wordpress.com Sítě sydney.edu.au wallblog.co.uk us.fotolia.com Temporální data • Zobrazení časově závislých dat – Tradičně pomocí vývojových (trend) grafů a sezónních grafů www.psdgraphics.com www.demondemon.com Temporální data www.sciencedirect.com Temporální data - LifeLines www.cs.umd.edu Předzpracování dat • Zobrazování „raw“ dat = nedochází ke ztrátě přesnosti, identifikace problémových míst, chybějících dat • V některých případech je preprocessing nutný blog.wpfwonderland.com Předzpracování dat - techniky • Metadata a statistiky • Chybějící hodnoty a „čištění“ dat • Normalizace • Segmentace • Vzorkování a interpolace • Snižování dimenze • Agregace dat • Vyhlazování a filtrace • Konverze rastrových dat do vektorových Metadata a statistiky • Metadata – informace pro předzpracování – Referenční bod měření – Jednotka měření – Symbol pro indikaci chybějící hodnoty – Rozlišení pořizovaných dat • Statistická analýza – Detekce chybných záznamů – Analýza pomocí klastrů – Korelační analýza Chybějící hodnoty a „čištění“ dat – metody řešení • Odstranění špatného záznamu • Přiřazení definované hodnoty • Přiřazení průměrné hodnoty • Přiřazení hodnoty odvozené od nejbližšího souseda • Spočtení náhradní hodnoty www.statistical-solutions-software.com Normalizace • Transformace vstupní datové množiny • Normalizace do intervalu [0.0, 1.0]: dnormalized = (doriginal - dmin)/(dmax - dmin) • Ořezání podle hraničních hodnot Segmentace • Klasifikace vstupních dat do předem specifikovaných kategorií • Split-and-merge iterativní algoritmus blog.campaigner.com blog.campaigner.com Split-and-merge similarThresh = definuje podobnost dvou regionů s danými charakteristikami homogeneousThresh = definuje homogenitu (uniformitu) regionu do { changeCount = 0; for each region { porovnej region se sousedními regiony a najdi nejpodobnější; if nejpodobnější soused leží uvnitř similarThresh aktuálního regionu { spoj tyto dva regiony; changeCount++; } vyhodnoť homogenitu regionu; if homogenita regionu je menší nez homogeneousThresh { rozděl region na dvě části; changeCount++; } } until changeCount == 0 Komplexní části algoritmu • Určení podobnosti dvou regionů • Vyhodnocení homogenity regionu – histogram • Rozdělení regionu www.statcan.gc.ca Potenciální problém • Vytvoření nekonečné smyčky opakování rozdělování a spojování stejného regionu • Řešení: – Změna hodnoty prahu podobnosti nebo prahu homogenity – Zahrnutí jiných vlastností regionů (vyhlazení hranic, velikost a tvar regionů) www.rootninja.com Vzorkování a interpolace • Transformace vstupních dat • Interpolace = metoda vzorkování – Lineární interpolace – Bilineární interpolace – Nelineární interpolace inperc.com Lineární interpolace (xC - xA)/(xB - xA) = (dC - dA)/(dB - dA) dC = dA + (dB - dA)*(xC - xA)/(xB - xA) d je hodnota proměnné. Dále předpokládáme, že A, B i C leží na ose x. • Obecné rozložení bodů v rovině: P(t) = PA + Vt, kde V = PB - PA • Dosadíme za P(t) PC, spočteme hodnotu t a následně: d(t) = dA + Ut, kde U = dB - dA Bilineární interpolace • Uniformní grid • Horizontální + vertikální interpolace 1) procentuální vzdálenost bodu x mezi body x a x+1, spočtení d na pozicích (x, j) a (x, j+1) 2) dx,y = dx,j + t * (dx,j+1 – dx,j) kde t = procentuální vzdálenost bodu y mezi body j a j+1 Nelineární interpolace • Problémy lineární interpolace – spojitost 0 v bodech mřížky • Řešení použitím kvadratických a kubických křivek www.root.cz Catmull-Rom spline • 4 kontrolní body q(t) = 0.5 * (1.0 t t2 t3) * * q(t) = 0.5 * ((2*p1) + (-p0 + p2) * t + (2*p0 – 5*p1 + 4*p2 – p3) * t2 + (-p0 + 3*p1 - 3*p2 + p3) * t3)                  1331 1452 0101 0020               3 2 1 0 p p p p Výsledek • Původní obrázek (24x24 pixelů) kubický B-spline filter Catmull-Rom research.cs.wisc.edu Metody převzorkování • Replikace pixelů • Průměrování sousedů • Data subsetting giscommons.org Snižování dimenze • např. pro účely zobrazení • zachovat co nejvíce informací obsažených ve vstupní množině • techniky: – PCA (principal component analysis) – MDS (multidimensional scaling) – SOMs (Kohonen self-organizing maps) Interactive Data Visualization - Fondations, Techniques and Applications. Matthew Ward PCA intuitivně 1. Vybereme přímku v prostoru, který zobrazuje ndimenzionální data. Tato přímka pokrývá co nejvíce těchto vstupních dat. Přímka pak reprezentuje první hlavní komponentu (PC). 2. Vybereme přímku kolmou k první přímce – ta tvoří druhou PCA. 3. Opakujeme tento postup, dokud nejsou spočteny všechny PC dimenze nebo dokud není dosažen požadovaný počet hlavních komponent (PCAs). web.media.mit.edu PCA – principal component analysis 1) 2) 3) 4) http://ordination.okstate.edu/PCA.htm MDS – multidimensional scaling • Založen na porovnání vzdáleností mezi jednotlivými body v původním a redukovaném prostoru. scikit-learn.org MDS – multidimensional scaling 1) Spočítáme vzdálenosti všech dvojic bodů v původním prostoru. Pokud máme na vstupu n bodů, tento výpočet vyžaduje n(n – 1)/2 operací. 2) Převedeme všechny body vstupní množiny do prostoru o požadované nižší dimenzi (často náhodně). 3) Spočteme stress, tedy rozdíl mezi vzdálenostmi bodů v původním a novém prostoru. Tento výpočet může být proveden různými způsoby. 4) Jestliže průměrný nebo akumulovaný stress je menší než uživatelem definovaný práh, ukončíme celý algoritmus a vrátíme výsledek. 5) Jestliže je práh překročen, pak každému datovému bodu spočteme směrový vektor označující směr, ve kterém by se bod měl posunout, abychom redukovali stress mezi ním a všemi ostatními body. Ten je určen jako vážený průměr vektorů mezi tímto bodem a všemi jeho sousedy, jeho směr může být k nebo od souseda a váha je odvozena ze stressu spočteného mezi jednotlivými páry. Kladná hodnota stress body vzájemně oddaluje, záporná přibližuje a čím větší je absolutní hodnota stressu, tím větší je pohyb. 6) Na základě těchto výpočtů transformujeme datové body do cílové nižší dimenze – s ohledem na spočtené vektory. Vrátíme se ke kroku 3 algoritmu. MDS - příklad • Vzdálenost mezi městy MDS – multidimensional scaling lear.inrialpes.fr/src/yorg/doc/index.html Mapování nominálních hodnot na ordinální • Jedna nominální proměnná – Použita jako label grafického elementu • Více nominálních proměnných – Multiple correspondence analysis www.survo.fi Agregace dat • Agregace = shlukování podobných dat do skupin podle jejich podobnosti. Zahrnuje dvě metody: – Shlukování – Zobrazení shluků Vyhlazování a filtrace • Běžné při zpracování signálu – odstranění šumu • Konvoluce v 1D: 424 11   iii ppp pi Konverze rastrových dat to vektorových • Převod je používaný při: – kompresi dat – porovnání obrázků – transformaci dat • Metody: – Prahování – Narůstání regionů (semínkové vyplňování) – Detekce hranic – Ztenčování www.articulate.com Shrnutí • Zmíněné techniky zvyšují efektivitu vizualizace • Nutné uživatele informovat o tom, že data byla transformována www.smashingmagazine.com enormousface.com