Vizualizace v Information Retrieval

VŠB – Technická univerzita Ostrava Fakulta elektrotechniky a informatiky Katedra informatiky

Vizualizace v Information Retrieval

2007

Petr Kopka

Prohlašuji, že jsem tuto diplomovou práci vypracoval samostatně. Uvedl jsem všechny literární prameny a publikace, ze kterých jsem čerpal.

V Ostravě dne 9. května 2007

2

Poděkování Děkuji svému vedoucímu diplomové práce za jeho cenné rady a pomoc při řešení. Spousty díků patří také mým nejbližším a všem mým přátelům, kteří měli se mnou tu obrovskou trpělivost a vyjádřili mi neocenitelnou podporu a pomoc při řešení. Děkuji!

3

Abstrakt V dnešní době se stále více setkáváme s potřebou získat informaci na základě našeho dotazu. Výsledky odpovídající našemu dotazu můžeme vizualizovat pomocí spousty různých technik počínaje textovou prezentací a konče trojrozměrnými vizualizacemi. My se v této práci budeme zabývat nejrůznějšími postupy, jak se dají výsledky zobrazit pokud možno v přehledné formě. Ukážeme si také, jak se dá zobrazení některých výsledků potlačit. Moderní vizualizační nástroje umí vizualizovat různé struktury a my si některé postupy ukážeme na praktických příkladech a uvedeme, jaké jsou výhody nebo úskalí jednotlivých vizualizačních postupů.

Klíčová slova vizualizace, vyhledávání informací

Abstract We meet increasingly with a need to obtain the information based on our query nowdays. We can use a lot of approaches to visualize the results of our queries from textual presentation to trhree-dimensional visualization. This thesis deals with all sorts of methods that show the results preferebly in well-arranged form. We will show how to restrict displaying of some results. Modern visualization tools can display various structure. We will show some approaches on examples introducing advantages and pitfalls of the particular visualization approaches.

Keywords visualization, information retrieval

4

Obsah 1. Úvod 9 1.1 Struktura práce ............................................................................. 10 2. Information Retrieval 11 2.1 Co je Information Retrieval ............................................................. 11 2.2 Systém získávání dat...................................................................... 12 2.2.1 Model systému získávání dat ................................................... 12 2.2.2 Struktura informací ................................................................ 14 3. Vizualizace v IR 15 3.1 Zásady návrhu uživatelského rozhraní IR systému ......................... 15 3.2 Funkce vizualizace ......................................................................... 16 3.3 Hlavní techniky vizualizace ............................................................ 17 3.4 Hodnocení interaktivních systémů.................................................. 17 4. Proces přístupu k informacím 19 4.1 Standardní model přístupu k informacím – interakční .................... 19 4.2 Nevyhledávací část procesu přístupu k informacím......................... 21 5. Způsoby vizualizace v IR 23 5.1 Úvod .............................................................................................. 23 5.2 Standardní přístupy k vizualizaci ................................................... 25 5.2.1 Jednoduchý graf pojmů........................................................... 25 5.2.2 Histogramy ............................................................................. 29 5.2.3 Spojnicový graf........................................................................ 29 5.2.4 Kruhový graf ........................................................................... 31 5.2.5 Samoorganizující síť – SOM ..................................................... 36 5.2.6 Hyperbolické stromy................................................................ 41 5.2.7 Bifokální stromy...................................................................... 43 5.2.8 Třídimenzionální metody ......................................................... 45 5.2.9 Hybridní nástroje .................................................................... 47 6. Aplikace Graph Analysis 51 6.1 Projekt The Netron Project.............................................................. 51 6.2 Balík GraphApplications ................................................................ 51 6.3 Specifikace požadavků ................................................................... 52 6.3.1 Simulace trojrozměrné vizualizace grafu .................................. 52 6.3.2 Vstupní data ........................................................................... 54 6.4 Vizualizační nástroj Graph Analysis ............................................... 57 6.4.1 Třída MainForm ...................................................................... 57 6.4.2 Třída GraphControl ................................................................. 60 6.4.3 Třída Entity............................................................................. 62 6.4.4 Třída Shape ............................................................................ 62 6.4.5 Třída RoundNode .................................................................... 63

5

6.4.6 6.4.7 6.4.8 6.4.9

Třída Connection..................................................................... 64 Třída DefaultPainter ................................................................ 64 Načtení symetrické matice....................................................... 65 Načtení binárního stromu ....................................................... 66

7. Testování 68 7.1 Požadavky na systém ..................................................................... 68 7.2 Výsledky testů ............................................................................... 68 8. Závěr

74

Literatura

75

A. CD-ROM

77

6

Seznam obrázků 2.1: IR systém.......................................................................................... 12 4.1: Zjednodušený diagram modelu procesu přístupu k informacím ......... 20 5.1: Základní způsob prohledávání kategorií v systému dolování dat z textu .............................................................................................. 24 5.2: Kruhová spojová mapa s přiloženou ukázkou filtru............................ 24 5.3: Interaktivní graf znázoňující hierarchický strom ................................ 26 5.4: Graf asociací pojmů: jeden vrchol, jedna kategorie............................. 27 5.5: Graf asociací pojmů: jeden vrchol, různé kategorie ............................ 28 5.6: Histogramová reprezentace ............................................................... 30 5.7: Spojnicový graf hodnot asociací pro tři sady dotazů ........................... 31 5.8: Spojnicový graf zobrazující počet dokumentů obsahujících pojem Osama bin Laden během určitého časového rozpětí ................. 32 5.9: Dva příklady víceřádkového grafu srovnávajících vývoj hodnot v průběhu času ..................................................................... 32 5.10: Kruhový graf ................................................................................... 33 5.11: Kruhový graf asociací ...................................................................... 34 5.12: Spojovací diagram kategorií v kontextu osob a organizací ................ 34 5.13: Kruhové grafy a podgrafy................................................................. 36 5.14: WEBSOM........................................................................................ 38 5.15: Kartografická mapa SOM datového souboru ARIST.......................... 40 5.16: Hyperbolický strom pro vizualizaci stránek National Park Service............................................................................................ 42 5.17: Nástroj StarTree jako mapa stránek pro web automobilky Porsche........................................................................................... 42 5.18: Bifokální strom zobrazující hierarchii s přibližně 370 uzly................ 44 5.19: Bifokální strom: výměna vrcholu v detailní oblasti ........................... 45 5.20: 3D pohled na diagram společných citací autorů vědeckých prací ............................................................................................... 46 5.21: Daisy diagram spojující vzhled kruhového diagramu a komplexního srovnávacího histogramu ......................................... 47 5.22: HSOM ............................................................................................. 48 5.23: Pokračování ukázky příkladu použití HSOM z obrázku 5.22............. 49 5.24: Hybridní trojrozměrný síťový diagram, který obsahuje prvky grafu s uzly a spojeními a histogramové prezentace s trojrozměrnými efekty a tabulkami s popisy .................................. 50 6.1: Příklad zobrazení náhodně vygenerovaného grafu .............................. 52 6.2: Ideální představa zobrazení trojrozměrného grafu .............................. 53

7

6.3: Ukázka vizualizace. Vstupní data: symetrická matice......................... 55 6.4: Zjednodušený třídní diagram postihující zejména modifikované třídy ................................................................................................. 59 7.1: Vizualizace symetrické matice čítající sto objektů bez omezení (0-100).............................................................................................. 69 7.2: Vizualizace předchozí úlohy s omezením 8-92.................................... 70 7.3: Vizualizace předchozí úlohy s omezením 90-100................................ 70 7.4: Vizualizace symetrické matice čítající 50 objektů ............................... 71 7.5: Vizualizace symetrické matice čítající 200 objektů ............................. 71 7.6: Vizualizace symetrické matice čítající 500 objektů ............................. 72 7.7: Vizualizace předchozí úlohy s omezením 255-500 .............................. 72 7.8: Vizualizace symetrické matice čítající 1000 objektů ........................... 73 7.9: Vizualizace předchozí úlohy s omezením 963-1000 ............................ 73

8

1. Úvod Lidstvo si odjakživa předávalo vědomosti buď ústní formou, nebo se snažilo používat různé záznamové metody pro jejich uchování, ať už si pod pojmem „záznamové metody“ představujeme v dnešní době cokoliv. Moderní – současný – člověk se snaží své vědění uchovávat stále častěji a ve větším objemu než kdykoliv před tím. Kdysi pojem informace nebyl znám tak jako dnes, v době, kdy se s ním setkáváme zcela běžně každý den. Ať už naším znalostem říkáme informace nebo vědomosti, nevyhneme se potřebě tyto údaje nějakým způsobem pokud možno snadno a rychle – efektivně – vyhledat, kdykoliv je to potřeba. Pro vyhledání konkrétní informace stačilo ještě v minulém století otevřít encyklopedii, slovník, atlas nebo jiný tištěný zdroj. Dnes, pokud máme potřebu něco vyhledat, zpravidla zasedneme k počítači a snažíme se danou informaci vyhledat co nejrychleji bez zdlouhavého listování stovkami, až tisíci stránek. Současně v tichosti věříme, že zdroj, z něhož se danou informaci dovíme, je věrohodný. Předpokládejme, že údaj je pravdivý a zaměřme se jen na způsoby, jakými jsou prezentovány výsledky našeho hledání. Výsledky odpovídající našemu dotazu lze v dnešní době vizualizovat pomocí spousty různých technik počínaje textem uvedeném na jednotlivých řádcích a konče vizualizacemi simulujícími třetí rozměr. My se v této práci budeme zabývat nejrůznějšími postupy, jak se dají výsledky zobrazit v pokud možno přehledné formě. Ukážeme si, jak se některé výsledky nechají potlačit, ať už se jedná o méně relevantní informace nebo o zúžení – zaměření – pohledu na část výsledků z důvodu velkého množství odpovědí na náš dotaz. Zmínili jsme, že nejjednodušším způsobem prezentace výsledků dotazů je textová forma. Při vizualizaci odpovědí pomocí graficky atraktivnějších metod nebo dokonce nejrůznějších technik simulujících efektně působící trojrozměrná prostředí se však vždy neobejdeme bez minimální textové prezentace, třebaže se přímo nebude jednat o detailní odpovědi ale o označení rozdílných skupin výsledků, v nichž se má nebo může odpověď na náš dotaz vyskytovat. Zaměříme se tedy na možnosti vizualizace vyhledávání textových výsledků. Metody obrazových výsledků jako odpovědí na dotaz jsou zatím ve

9

fázích výzkumů a testů. Je stále velice obtížné získat jako odpověď sadu obrazových výsledků, pokud pomineme textové zadání dotazu. Chceme-li dostat sadu odpovědí tak, že jako vstup uvedeme třeba fotografii nějakého objektu, ocitáme se zatím v oblasti fikce. Stále je třeba zadávat vstupy v textové podobě. Je důležité si také uvědomit, že se nezaměřujeme jen na úlohy, kdy položíme jasný dotaz a na něj budeme očekávat pouze jednu dvě odpovědi, kterou si necháme zobrazit. Často chceme získat komplexní nebo – je-li to možné – všeobecný výsledek na náš dotaz. Výsledkem tak nebude třeba jednoslovná odpověď ale množina celých dokumentů týkajících se dané problematiky. Tyto dokumenty je často vhodné při velkém počtu organizovat do nějaké vhodné struktury, hierarchie. Moderní vizualizační nástroje umí takové struktury vizualizovat a my si ukážeme na praktických příkladech, jak taková prezentace může vypadat a jaké jsou výhody nebo úskalí jednotlivých vizualizačních postupů.

1.1

Struktura práce

Práce je rozdělena do osmi kapitol. Hned za touto sekcí následuje kapitola 2, která odpovídá na otázku, co je information retrieval a popisuje model systému získávání dat. V kapitole 3 se dočteme o zásadách návrhu vizualizačních prostředků a jejich funkcích a v kapitole 4 popíšeme proces přístupu k informacím. Kapitola 5 se zabývá jednotlivými vizualizačními metodami od jednoduchých grafů a histogramů až po trojrozměrné metody a další speciální nástroje, které spojují více technik do jedné. V kapitole 6 se budeme zabývat naší aplikací pro vizualizaci symetrických matic s velkým počtem objektů umožňující zobrazit také hierarchickou strukturu popsanou binárním stromem. Popíšeme si jednotlivé třídy, které bylo třeba upravit, abychom dosáhli požadovaných výsledků. V testech v kapitole 7 budeme na příkladech ilustrovat vizualizace symetrických matic čítajících až 1000 objektů a v kapitole 8 provedeme celkové shrnutí práce a provedených testů.

10

2. Information Retrieval 2.1

Co je Information Retrieval

Problém uložení a zpětného vyhledání informace si získává stále větší pozornost už od poloviny minulého století [1]. Důvod je zřejmý: lidstvo vytváří obrovské množství informací – informačních pramenů. K těmto zdrojům je požadován přesný a rychlý přístup, což se stává stále obtížnější. Jedním z rysů obtížnosti přístupu ke hledaným údajům je, že tyto zůstávají někdy nepovšimnuty, což postupně vede k opakování úsilí při vyhledávání. S nástupem výpočetní techniky byla velká část lidské snahy soustředěna směrem k využití počítačů poskytujících rychlé a „rozumné“ vyhledávácí systémy. Problémy spojené například s katalogizací a administrací dokumentů v knihovnách byly úspěšně přeneseny na bedra výpočetní techniky, avšak problém efektivního vyhledávání informací zůstává v obecné rovině stále nevyřešen. Uložení a nalezení informace je v podstatě jednoduché. Mějme kolekci dokumentů (knihovnu) s uloženými dokumenty a osobu formulující dotaz, na nějž je odpovědí soubor takových dokumentů, které uspokojí svou informační hodnotou osobu kladoucí dotaz. Získat takový soubor dokumentů můžeme třeba přečtením všech dokumentů z kolekce. Relevantní dokumenty si ponecháme a ostatní odložíme stranou. Je jisté, že takto máme zaručeno dokonalé prohledání dokumentů. Toto řešení je však velice nepraktické, ne-li neproveditelné. Nikdo přece nemá tolik času, aby pročítal celou sbírku dokumentů, nehledě na fakt, že to ani není v lidských silách. Pro zajímavost uvádíme údaj z listopadu 2004, kdy Google indexoval zhruba 8 miliard dokumentů a z toho je asi 20 milionů česky psaných. Stále narůstající výpočetní výkon počítačů dovolil vzniknout myšlence, že by počítače mohly být schopny „pročítat“ celé sklady dokumentů, aby získaly odpovídající dokumenty kladením dotazů v přirozeném jazyce. Ukázalo se, že takový postup problém neřeší. Rovněž nechává nevyřešený problém popisu obsahu dokumentu. Můžeme se jen domnívat, že za několik let bude možné provádět dotaz v přirozeném jazyce. Automatický popis dokumentů, při kterém software nahrazuje práci člověka, umožňuje efektivnější způsob při vyhledávání. Software přečte daný dokument a extrahuje z něj informaci, kterou použije k tomu, aby rozhodl, zdali je dokument relevantní nebo ne. Obtížnost však není jen

11

v tom, jak informaci extrahovat, ale také v tom, jak ji použít k vyhodnocení relevance. Jakmile je zhotoven popis dokumentu, je očekáváno, že bude uveden jako odezva na daný dotaz. Lidé tradičně popisují dokumenty tak, aby co nejlépe vystihli jejich obsah a umožnili je zobrazit jako výsledek dotazu s patřičnou relevancí. Nicméně stále je na člověku, aby stanovil relevanci dokumentu na daný dotaz. Chceme-li i tuto práci nějakým způsobem převést na počítač, musíme vytvořit takový model, v němž může být relevance snadno měřitelná. Je zajímavé si povšimnout, že většina výzkumů v získávání informací - Information Retrieval (dále jen IR) se týká různých hledisek na takové modely.

2.2 2.2.1

Sytém získávání dat Model systému získávání dat

Typický model systému získávání dat (dále jen IR systém) je znázorněn na obrázku 2.1 [2].

DOTAZY ODEZVA VSTUP

PROCESOR

VÝSTUP

DOKUMENTY Obrázek 2.1: IR systém

Hlavní problém je hned na začátku. Jak vlastně reprezentovat data a jak dotazy, aby je bylo možno zpracovat počítačem? Mějme kolekci dokumentů textového charakteru, které mají být popsány. Tyto dokumenty jsou reprezentovány například pomocí seznamu extrahovaných slov, která se považují za významná. Díky tomu je možno použít místo přirozeného jazyka jazyk umělý, který umožní formulovat dotaz. To samozřejmě předpokládá, že uživatel bude schopen vyjádřit svůj dotaz právě v takovém jazyce.

12

Jestliže je IR systém provozován on-line, je pravděpodobné, že uživatel bude několikrát upravovat požadavek během jednoho hledání s ohledem na vzorky odpovědí. Proto je také třeba zohlednit dodatečné procesy požadavků vedoucí k upřesnění dotazu. Tento proces se obvykle nazývá odezva – feedback (příklad takového důmyslného IR systému pracujícího on-line je systém MEDLINE [1]). Procesor (viz obrázek 2.1) je část IR systému týkající se samotného procesu získávání informací. Proces může zahrnovat uspořádání informací nějakým vhodným způsobem. To může rovněž zahrnovat vykonání aktuální vyhledávací funkce, kterou je provedení pomocí vyhledávací strategie v reakci na dotaz. V diagramu jsou dokumenty umístěny v samostatném obdélníku. Tím je zdůrazněn fakt, že dokumenty nejsou pouhým vstupem, ale mohou být použity během procesu získávání informací takovým způsobem, že se jejich struktura chápe jako část procesu získávání informací. Na výstupu se nakonec objeví množina citací nebo dokumentů. Proces IR lze tedy rozdělit do tří oblastí: •

Analýza obsahu

•

Uspořádání (struktura) informací

•

Vyhodnocení

Analýza obsahu se zabývá popisem obsahu dokumentů formou vhodnou pro zpracování počítačem. Uspořádání se podílí na využití vztahů mezi dokumenty ke zlepšení efektivity strategií IR. Vyhodnocení zahrnuje míru efektivity IR. Existují různé přístupy k reprezentaci dokumentů. Nejznámější je frekvenční analýza [2], která používá frekvenci počtu slov v textu dokumentu ke stanovení takových slov, která jsou dostatečně významná, aby mohla reprezentovat nebo charakterizovat dokument v počítači. Seznam takových slov zvaných klíčová slova je získán pro každý dokument. Frekvence výskytu těchto slov v těle textu je navíc použita pro vyjádření stupně důležitosti. Použití statistických informací o výskytu slov v dokumentech dále slouží k získání statistiky vztahů mezi klíčovými slovy. Tyto vztahy poskytují základ pro konstrukci tezauru, který se dá použít jako podpora při vyhledávání. Využití míry spojení mezi klíčovými slovy je základem pro frekvenci společného výskytu klíčových slov vyskytujících se společně ve stejném dokumentu. Tato související slova mohou být použita k efektivnímu

13

zlepšení odezvy, což vede ke zvýšení podílu relevantních dokumentů, které byly vyhledány.

2.2.2

Struktura informací

Termín struktura informací představuje zejména logické upořádání informací pro účely IR [2]. Velmi oblíbenou organizací dat se zpočátku ukázal být invertovaný soubor. Tato struktura však má svá omezení. V současné době se výzkum soustředí na shluky souborů pro on-line IR. Uspřádání těchto souborů je vytvořeno automatickými metodami uspořádání.

14

3. Vizualizace v IR Proces vyhledávání dat v obrovské kolekci informací v dnešní době vyžaduje poskytnout rozhraní mezi uživatelem - člověkem hledajícím informace – a systémem IR [1], které bude postupně vizualizovat výsledky hledání. Je třeba zohlednit fakt, že k takovému systému přistupuje i uživatel, který nemá zcela určitou představu o tom, jak dosáhnout svého cíle. A právě v takovém případě by mělo uživatelské rozhraní pomoci uživateli v porozumění a vyjádření svých potřeb. Mělo by uživateli poskytnout pomoc při formulaci dotazu, výběru mezi dostupnými informačními zdroji a porozumění výsledku hledání. Uživatelské rozhraní by mělo mít také mechanismy zajišťující sledování postupu během celého procesu vyhledávání. Uživatelské rozhraní mezi člověkem (uživatelem) a počítačem (systémem IR) je obtížné navrhnout zejména proto, že člověk uvažuje komplexněji a v mnohem širších rozměrech než v jakých dimenzích pracuje jakýkoliv systém IR. Je velice obtížné vůbec měřit nebo vyjádřit motivaci a chování uživatele během procesu vyhledávání. Tato oblast prochází obrovským vývojem. Dobře navržený počítačový systém má během jeho ovládání vytvářet mezi uživateli pocit úspěchu, způsobilosti, ovládnutí a srozumitelnosti systému. Pokud je interaktivní systém správně navržen, mělo by jeho rozhraní téměř vymizet, aby měl uživatel možnost soustředit se jen na svou práci, výzkum nebo zábavu.

3.1

Zásady návrhu uživatelského rozhraní IR systému

Aby bylo možno dosáhnout cílů uvedených v předchozím odstavci, je potřeba dodržet zásady pro návrh uživatelského rozhraní [1]: •

Poskytnutí zpětné vazby

•

Snížení zatížení operační paměti

15

•

Poskytnutí různého uživatelského rozhraní pro začátečníky a odborníky

Poskytnutí zpětné vazby je důležité zejména pro rozhraní poskytující přístup k informacím. Přístup k informacím je totiž obvykle iterativní proces, jehož cíl se může obměnit či posunout vhledem k právě dosaženým výsledkům. Snížení zatížení paměťového prostoru pak znamená poskytnutí takových mechanismů, které budou sledovat „směr“ dosavadních voleb uskutečněných během procesu vyhledávání a umožní udržet nebo změnit vyhledávací strategii nebo se vrátit k předchozím výsledkům. Pro běžného uživatele by mělo být poskytnuto jednoduché rozhraní poskytující základní funkce a jehož ovládání je intuitivní. Naopak expert by měl mít možnost se setkat s rozhraním, které mu nabídne mnohem více možností ovládání IR systému nebo zcela jiný interakční model.

3.2

Funkce vizualizace

Na počátku byly všechny interaktivní programy (dá-li se vůbec použít slovo interaktivní) ovládány z příkazové řádky. Odpověď na dotaz byla rovněž zobrazena v řádcích. Později začaly výstupy dostávat grafickou podobu. Uživatelská rozhraní postupně doznala také výrazných změn a dnes jsme již všichni zvyklí na to, že programy běží v graficky oddělených rámech – oknech – a tyto obsahují různé ovládací prvky, jejichž vzhled je vizuálně odlišen od ostatních částí okna. Méně známou avšak rozrůstající se oblastí je vizualizace informací, která poskytuje vizuální zobrazení obrovského informačního prostoru. Rostoucí převaha procesorů obsahujících instrukce pro zlepšení práce s grafikou a monitory s vysokým rozlišením a 32 bitovou barevnou hloubkou zvyšují zájem o vizualizaci informací. Nejrychleji se rozvíjejícím oborem v této oblasti jsou vizualizace fyzikálních jevů do dvojrozměrných či trojrozměrných grafů. Poslední výzkumy na tomto poli působnosti vedou ke snaze vizualizovat abstraktní informace, jako jsou třeba textová data, což je velice obtížné. Jazyk jako náš hlavní prostředek komunikace nemá jasný popis podle žádných přesně daných měřítek. Mohli bychom vyjmenovat spoustu dalších množin informací různé povahy, jež by bylo třeba vizualizovat. Navzdory všem překážkám se výzkum v této oblasti snaží vizualizovat všechny stránky procesu přístupu k informacím pomocí technik vizualizací informací, které budou popsány v následující kapitole.

16

3.3

Hlavní techniky vizualizace

Technika barevného zvýraznění a spojení se vztahuje k propojení dvou nebo více pohledů na tatáž data takovým způsobem, že změna v zobrazení informace v jednom pohledu ovlivní zobrazení také v ostatních pohledech [1]. Snímání pomocí virtuální kamery a přibližování (resp. vzdalování) simuluje filmovou kameru, která pluje napříč zobrazovanou scénou nebo se přibližuje - zoomuje (resp. vzdaluje). Tato metoda může být použita například při shlukování textových dokumentů. Při pohledu na nejvyšší úrovni se zobrazí hlavní témata z celé kolekce dokumentů. Přiblížení se k určité části zobrazí jednotlivé dokumenty jako ikony a další přiblížení navíc ještě ukáže text, který je přiřazen ke každému jednotlivému dokumentu. Přiblížení nám zobrazí mnohem více detailů v centru pozornosti, avšak ztratíme detailní informace o okolních datech. Technika zvaná focus-plus-context částečně zmírňuje efekt předchozí techniky. Idea je taková, že část pohledu, která je v ohnisku zájmu, se zvětší, zatímco ostatní objekty ustoupí (srovnatelné s rybím okem). Technika focus-plus-context využívá pohled na informační prostor integrovaný v jednom okně, přičemž používá různých vizuálních efektů, které zdůrazňují oblast v centru zájmu. K tomu jsou zapotřebí mechanismy, které pří změně ohniska zájmu zachovají souvislosti tak, aby zůstaly zobrazeny, jak nejvíce to jde. Magická lupa je vizualizační technika, kterou je možno chápat jako průhledné okno, jímž lze pohybovat přímo v zobrazovací oblasti. Když okno dosáhne na nějaký jiný typ dat, způsobí změny, které se projeví na těchto původních datech, což změní jejich reprezentaci.

3.4

Hodnocení interaktivních systémů

Z hlediska návrhu uživatelského rozhraní mají různí lidé různé schopnosti, požadavky a zvyky [1]. Při návrhu takového rozhraní rozhoduje schopnost prostorového vnímání, schopnost zapamatovat si určitý objem informací, rozhodovací schopnost, vyjadřovací schopnost a různé osobnostní rozdíly. Různá zlepšení v rozhraní takových systémů mohou být užitečná pro jedny uživatele a pro druhé mohu být naopak nepřekonatelně těžká.

17

Důležitým hlediskem interakce mezi člověkem a počítačem je metodika pro ohodnocení technik uživatelského rozhraní. Měření přesnosti a odezvy byla široce používaná k porovnání klasifikace výsledků neinteraktivních systémů, ale nebyly vhodné pro hodnocení interaktivních systémů. Standardní hodnocení klade důraz na vysoký počet odpovědí. Uživatelé však často požadují pouze několik relevantních dokumentů a neoceňují tak interaktivní systémy, které jim nabídnou vysoký počet odpovědí.

18

4. Proces přístupu k informacím 4.1

Standardní model přístupu k informacím - interakční

Uživatel hledající informace má na mysli zpravidla hned několik cílů a vyhledávací systém používá jako nástroj k dosažení svých cílů [1]. Jejich rozsah je vskutku široký a úloha přístupu k informacím musí pokrýt celé jejich spektrum, od specifických dotazů až k podrobnému zkoumání daného tématu. Přestože jsou mnohé cíle velice odlišné, mají všechny společné jádro týkající se vyhledávací části. Předpokládá se, že většina procesů přístupu k informacím bude tvořit jakýsi opakovací cyklus popsaný následující posloupností kroků: 1.

Poptávka po informaci.

2.

Výběr vyhledávacího systému.

3.

Formulování dotazu.

4.

Odeslání dotazu do systému.

5.

Obdržení výsledků v podobě jednotlivých položek.

6.

Vyhodnocení výsledků.

7.

Konec cyklu nebo pokračovat bodem 8.

8.

Přeformulování dotazu a opakování od bodu 4.

Tento model, který je užíván webovými vyhledávači, je lépe znázorněn na obrázku 4.1. Model nebere v úvahu fakt, že mnoho uživatelů se nerado potýká s dlouhým neuspořádaným seznamem získaných výsledků, které jim zcela přímo neodpoví na jejich dotaz. Model rovněž předpokládá, že uživatel postupně zdokonaluje svůj dotaz, dokud nedostane pouze ty správné dokumenty. Uživatelé se ve skutečnosti během vyhledávacího procesu učí. Prohlížejí si informace, čtou názvy v souboru výsledků, čtou samotné dokumenty získané jako odpovědi na dotaz, přičemž sledují seznam témat

19

vztahující se k jejich dotazu a procházejí vnitřní strukturou vzájemně propojených webových stránek. Současný nástup hyperodkazů - stěžejní část procesu vyhledávaní informací - způsobil, že si už nelze nevšímat úlohy prohlížení a procházení výsledků dotazu uvnitř samotného vyhledávacího procesu. Standardní model rovněž zlehčuje interakci, ke které dochází v době, kdy si uživatel prohlíží výrazy navržené jako odpovídající výsledky nebo si prochází témata kolekcí dokumentů. To snižuje úlohu výběru zdroje, který je v dnešní době mnohem více důležitý hned v prvním kroku, kdy jsou okamžitě dosažitelné desítky tisíc kolekcí informací.

Poptávka po informaci Dotaz Odeslání dotazu systému Získání výsledků

Přeformulování dotazu

Vyhodnocení výsledků

Ne

Platí ? Ano Konec

Obrázek 4.1: Zjednodušený diagram modelu procesu přístupu k informacím

Bates předložil model zvaný berry-picking (sbírání zrníček), který má dva hlavní body [1]. V prvním bodě uvádí, že výsledek čtení a učení se z informací, se kterými se setkáme v průběhu vyhledávacího procesu, vede k tomu, že se následující dotazy neustále posunují dopředu – vedou novým mnohdy neočekávaným směrem. Původní cíl může být částečně naplněn, čímž se

20

sníží priorita jednoho cíle ve prospěch druhého. Toto je v rozporu s předpokladem ‘standardního‘ získávání informací, kdy poptávka po informaci zůstává stejná po celou dobu vyhledávacího procesu. Ve druhém bodě uvádí, že poptávka po informaci není uspokojena jednoduchým a konečným souborem dokumentů, ale spíše nám vyhovuje skupina kousků informací, na které narazíme během vyhledávacího procesu. Toto je opět v rozporu s předpokladem, že hlavní cíl vyhledávacího procesu je zdokonalovat soubor získaných dokumentů, který odpovídá požadavku na informaci. Batesův model je podpořen mnoha studiemi [1]. Ukázalo se, že proces vyhledávání informací je složen z řady vzájemně propojených, ale rozdílných hledání, která se však týkají jednoho tématu. Studie také prokázaly, že výsledky hledání směřující k cíli mají tendenci vyvolat cíle nové a tím ubírat vyhledávání novým směrem, ale tak aby se kontext problému a předchozího vyhledávání přenesl z jednoho stupně vyhledávání na stupeň další. Uživatelské rozhraní pro přístup k informacím by tedy mělo uživateli dovolit přehodnotit své cíle a přizpůsobit tomu i vyhledávací strategii. Podobná situace nastane, když uživatel narazí na něco, co způsobí dočasnou změnu jeho strategie, třeba když se chce později vrátit k nějaké nedokončené aktivitě. Z tohoto pozorování vyplývá, že uživatelské rozhraní by mělo podporovat vyhledávací strategie tím, že by usnadnilo sledování cest vedoucích k předem neočekávaným výsledkům. Toho může být částečně dosaženo zaznamenáváním postupu aktuální vyhledávací strategie a uchovat, vyvolat a znovu zavést mezivýsledky a současně podporovat uplatnění hned několika strategií. Uživatelské rozhraní by mělo také podporovat metody pro sledování stavu aktuální strategie ve vztahu k uživatelově aktuálnímu úkolu. Jedním ze způsobů je vyhodnotit poměr „výdajů a výnosů“ a všímat si případné snižující se „návratnosti“. Jinými slovy zdá-li se v důsledku jiná strategie užitečnější než ta současná, použije se dočasně ta lepší.

4.2

Nevyhledávací část procesu přístupu k informacím

Studie O’Daye a Jeffriese ukazují [1], že hledání informací je pouze jedna část celého procesu, kterým se zabývají. Mezi jednotlivými částmi vyhledávání dochází k mnoha různým druhům činností se získanými informacemi včetně čtení, zaznamenávání výsledků a jejich analyzování. O’Day a Jeffries podrobněji zkoumali jednotlivé kroky analýzy a zjistili, že 80% činnosti lze rozdělit do šesti hlavních typů činností: hledání směru – trendu, porovnávání, seskupování informací, rozpoznávání kritických

21

podskupin, vyhodnocování a výklad – interpretace. Zbylých 20% se skládá ze vzájemného ověřování, shromažďování, hledání vhodné vizualizace a jiné činnosti. Proces přístupu k informacím lze tedy rozdělit na dvě hlavní části: •

hledání/nalezení dat

•

rozbor/shrnutí výsledků

Uživatelské rozhraní by v sobě mělo oba druhy aktivit implementovat. Nicméně rozbor a shrnutí výsledků jsou činnosti, které mohou být prováděny odděleně mimo vyhledávací činnost a proto je užitečné tyto druhy rozlišovat.

22

5. Způsoby vizualizace v IR 5.1

Úvod

Dolování dat z textu klade důraz na uživatelovu spolupráci během procesu objevování nových znalostí a v důsledku toho musí systémy dolování dat uživateli poskytovat řadu nástrojů pro manipulaci s daty [7]. Tyto nástroje se pro široké spektrum úloh spoléhají na velice jednoduché grafické metody jako výběrový seznam, rozevírací seznam a radio boxy, které se staly typické pro běžné aplikace, aby podpořily formulování dotazu a základní možnosti prohledávání potenciálně zajímavého obsahu. U rozsáhlých kolekcí dokumentů však problém nadbytečnosti zobrazení všech údajů najednou vedl návrháře těchto systémů přiklonit se k vytváření důmyslnějších vizualizačních prostředků, aby tak uživatelům usnadnili jejich práci, protože nasadit jednoduché vizualizační mechanismy na obrovské kolekce dokumentů je nepoužitelné. Důmyslnější prostředky vizualizace se již opírají o pokroky v nejrůznějších oblastech výzkumů informatiky, aby podpořily snadnější, intenzivnější a mnohem více interaktivní zkoumání vzorků v textových datech [7]. Mnoho běžných aktivit, které umožňují uživateli systému zajistit základní průzkum dat, jsou podpořeny grafickým uživatelským rozhraním, které slouží jako základní prohlížeč. Takový typický příklad základního rozhraní vidíme na obrázku 5.1. Tento typ často kombinuje omezenou funkci kladení dotazů spolu s omezeným pohledem na podmnožinu textových dat v kolekci dokumentů. Jako doplněk některé systémy podporují vykreslení statických grafů pro výsledky dotazů. I když základní prohlížeče i vizualizační nástroje umožňují interakci s daty, vizualizační nástroje obvykle používají mnohem propracovanější rozhraní, které se snaží co nejvíce využít zrakové schopnosti uživatele k rozpoznání vzoru. Interaktivní kruhový graf (viz obrázek 5.2) - běžný vizualizační nástroj v systémech dolování dat z textu - může být například přizpůsoben tak, aby výzkumníkům rakoviny umožnil kompletně prozkoumat celý soubor literatury týkající se medicínského výzkumu v jednoduchém grafu. Tento typ vizualizačního nástroje umožňuje výzkumníkům provádět nad obrovským množstvím dat různá vyhodnocování, manipulace a procházení

23

jejich strukturou a to vše relativně snadno a rychle. Ovládací prvky – jako jsou filtry nebo jiné omezující techniky – mohou být začleněny do celého procesu prováděné vizualizace pouhým kliknutím na určitý pojem.

Obrázek 5.1: Základní způsob prohledávání kategorií v systému dolování dat z textu

Obrázek 5.2: Kruhová spojová mapa lékařské literatury týkající se AIDS s přiloženou ukázkou filtru pro upřesnění výběru. Příklad demonstruje vztahy mezi geny a nemocemi získaných z 30.000 abstraktů MedLine. Výsledky jsou založeny na současném výskytu genů a onemocnění uvnitř téže věty

24

Nesporné výhody, které mají jednotlivé vizualizační techniky oproti znakově orientovanému prohledávání, jsou shrnuty v následujících bodech: •

Stručná reprezentace: schopnost zobrazit obrovské množství rozdílných typů dat najednou.

•

Přibližnost: schopnost snadno zobrazit shluky, schopnost zobrazit různé velikosti seskupení dat v poměru k jiným seskupením, schopnost zobrazit podobnost a rozdílnost seskupení,

•

Důraz na souvislosti: schopnost reagovat na určitý důležitý rys a zároveň vidět takový jev zasazen v jeho dalších souvislostech.

•

Schopnost změny perspektivy: možnost změny z blízkého pohledu na pohled vzdálený rychle a snadno v jednom kroku

•

Stimulace myšlení správným směrem: schopnost dovést uživatele ke spolupráci s textovými daty, která nebude vedena pouze předem promyšleným záměrem, ale též jako výsledek intuitivního nebo prostorově orientovaného poznávacího procesu za účelem rozpoznání zajímavých vzorků.

Na druhé straně přehnané přidávání komplexních grafických prvků do vizualizačního rozhraní nemusí hned nutně znamenat to, že je rozhraní vhodnější pro svůj účel než jiné. Příliš komplexní vizualizační nástroje mohou dokonce i zabránit prozkoumávání textových dat – zvláště když návrháři systémů dolování dat upustí ze zřetele hlavní výhody, které má grafická reprezentace prvků oproti obyčejným formátům prohlížečů založeným na formulářích a tabulkách.

5.2

Standardní přístupy k vizualizaci

5.2.1 Jednoduchý graf pojmů Tento vizualizační nástroj je velice účinný prostředek pro snazší pochopení tématiky kolekcí dokumentů. Hlavní výhody těchto nástrojů jsou jejich schopnost organizovat zkoumání textových dat a umožnit interaktivitu – což znamená, že uživatel může kliknout na každý uzel nebo hranu a získat hledané dokumenty nebo zahájit další operace na grafech. Mezi těmito výhodami je také vzájemná vazba. Uživatelsky jednoduché rozhraní s organizací dat dovede mnohem více podpořit interaktivitu s těmito daty.

25

Obrázek 5.3: Interaktivní graf je použit pro znázornění klasifikačních skupin jako hierarchického stromu

Jednoduchý graf množin pojmů Jedním z nejzákladnějších a všeobecně použitelných vizualizačních nástrojů v dolování dat z textu je jednoduchá hierarchická stromová struktura. Na obrázku 5.3 vidíme klasickou vizualizaci pro klasifikaci pojmů v kolekci dokumentů. Kořen a list vrcholů (uzlů) takové vizualizace jsou jednotlivé identifikátory pojmů (např. jména pro označení pojmů). Tento druh vizualizačního nástroje může být také snadno uživateli přizpůsoben tak, aby mohl kliknout na uzel a posunout se směrem k základním dokumentům obsahujícím pojem. Nejběžnější způsob jak graficky zobrazit množinu pojmů je tedy právě pomocí jednoduché hierarchické stromové struktury. Obrázek 5.3 ukazuje množinový graf pro často opakované množiny seřazené do stromové struktury. Uživatel může pracovat s tímto grafem vybráním uzlů, otevřít a uzavřít uzly, nebo definovat nové hledání s ohledem na tyto uzly například pro rozšíření stromu.

Jednoduchý graf asociací pojmů Zaměřuje se na reprezentaci spojení - asociací. Je složen z jednotlivých vrcholů, které mohou být hranami připojeny k množině několika dalších vrcholů. Tento typ grafu je typicky používán ke spojení pojmů určité kategorie. V každém vrcholu takového grafu je vždy pouze

26

jeden pojem. Dva pojmy jsou spojeny hranou, jestliže je jejich podobnost s ohledem na podobnostní funkci větší než dané omezení.

Overture 11 Yahoo MSN

37

17 29

Google

36 Sun

24 Microsoft

6

4

7 Convera

Autonomy 11

32

21

6

7 Verity 9

IBM

Lycos

3 Findwhat

Obrázek 5.4: Graf asociací pojmů: jeden vrchol, jedna kategorie (sofwarové společnosti v kontextu s vyhledávači)

Jednoduchý graf asociací pojmů může být neorientovaný nebo orientovaný, i když neorientované grafy jsou pravděpodobně typičtější. Neorientovaný graf může být například použit ke grafickému zobrazení asociací mezi generickými pojmy v dokumentu kolekcí generovaných z podnikové finanční dokumentace. Na druhou stranu orientovaný graf lze použít při vytváření nástroje k vizualizaci asociace mezi proteiny v těle z výzkumné literatury. Orientované hrany mezi jednotlivými vrcholy s pojmy

27

jsou pak označeny směrovými šipkami. Takový typ orientovaného grafu by mohl být užitečný nejen pro grafické znázornění hlavních asociací ale také pro zobrazení jevů, jak jeden protein účinkuje na jiný.

Google

Yahoo

Search

Microsoft

Verity

OEM Software

Database

IBM

Sun

Office Automation

Obrázek 5.5: Graf asociací pojmů: jeden vrchol, různé kategorie

Na obrázku 5.4 vidíme graf asociací pojmů pro kategorie společností v kontextu vyhledávačů a jednoduchou podobnostní funkci založenou na počtu dokumentů, ve kterých se společnosti zároveň vyskytují. Obrázek uživateli dovoluje rychle vyvodit závěr ohledně dat, což by jinak bylo možné pouze po pečlivém výzkumu, pokud by byl uživatel nucen tentýž úkol provést „ručním“ procházením objemného počtu tabulek nebo textových či statistických údajů. Z uvedeného příkladu lze tedy vyvodit následující závěry: •

Microsoft, Google a IBM jsou nejvíce propojené společnosti;

•

Lycos a Findwhat jsou jedinými členy samostatné komponenty grafu;

•

MSN je spojen pouze s Microsoftem, atd.

Jiný typ jednoduchého grafu asociací pojmů může představovat asociace mezi rozdílnými kategoriemi, jako jsou například společnosti a software. Jednotlivé vrcholy tohoto grafu jsou uspořádány do jakési mapy, na níž je rozdílné umístění objektů znázorňujících vrcholy použito k začlenění do kategorie pojmů. Hrany mezi společnostmi a softwarem pak představují odpovídající asociace. Často jsou takové grafy navrhovány jako bipartitní grafy zobrazující dvě kategorie pojmů tak, že jedna kategorie se nachází v horní části grafu a druhá kategorie v spodní části. Hrany mezi

28

nimi pak představují spojení mezi jednotlivými páry vrcholů. Obrázek 5.5 znázorňuje příklad takového grafu.

5.2.2 Histogramy Kromě základního způsobu vizualizace, jako jsou jednoduché grafy pojmů, spoléhaly často první systémy dolování dat z textu na klasické grafy, jako jsou histogramy (sloupcové grafy) [7]. Ačkoliv tvůrci takových systému ukázali vzrůstající vůli zakomponovat do svých systému mnohem komplexnější a interaktivní grafické nástroje, zachovaly si histogramy své využití při zkoumání vzorků v textových datech. Histogramy mají dnes stále své využití v systémech dolování textu a zdají se být vhodné zejména pro zobrazení výsledků dotazu týkajících se rozdělení a vzájemných poměrů hodnot. Nicméně i když se dvoudimenzionální sloupcové grafy během několika posledních let změnily jen trochu, celkově se prezentační prostředí, ve kterém jsou tyto grafy zobrazovány, značně zlepšilo. Reprezentace dat pomocí histogramu je nejčastěji doprovázena uživatelským rozhraním s oddělenými panely, které souběžně zobrazují odpovídající seznam nebo tabulky pojmů a jejich poměrů, viz obrázek 5.6. Histogramy jsou pro zobrazení takovýchto úloh velice užitečné, protože dovolují snadné srovnání různých pojmů v širším spektru jiných pojmů rovněž nalezených v kolekcích dokumentů. Nemůžeme však říct, že histogramy jsou jediným použitelným nástrojem v zobrazení těchto výsledků, nicméně jsou obvykle nejpoužívanější. Histogramy se navíc v poslední době stávají interaktivnější vzhledem k tomu, že jsou uživatelé schopni lépe ovládat různá omezení. Kombinace vysunovacích nebo rozdělených oken umožňuje pomocí posuvníků, různých číselníků a tlačítek nebo roletových menu nastavovat filtry tak, aby měl uživatel možnost vnímat změnu omezujících filtrů, které ovlivní výsledek dotazu, v reálném čase. Výrazné změny ve výškách jednotlivých sloupců v grafu jsou pro uživatele mnohem více patrnější než změny v číselných hodnotách v dlouhém seznamu nebo tabulce. Nevýhodou při zobrazování pojmů v celém rozsahu je, že menší rozdíly mezi sloupci jsou naopak těžko rozeznatelné.

5.2.3 Spojnicový graf Tak jako histogram nám nemusí hned na první pohled připadat jako nejvyspělejší metoda pro aplikace dolující data z textu, tak i spojnicový graf v nás může vyvolat stejný dojem [7]. Tento graf má však spoustu výhod. Mnoho akademických či komerčních systémů někdy používají spojnicový graf, aby podpořili proces objevování znalostí.

29

Obrázek 5.6: Levý panel uživatelského rozhraní ukazuje ve formě seznamu výsledky dotazu rozdělení pojmů. Pravý panel zobrazuje histogramovou reprezentaci stejného rozdělení

Spojnicový graf je příkladem „levného a uspokojivého“ řešení, jak údaje získané z textových dat vizualizovat. Tato řešení jsou „levná“, protože v sobě kombinují poměrně nízké systémové nároky a výdaje na jejich vývoj v tom, že existuje mnoho dostupných (levných nebo zcela zadarmo) softwarových knihoven, které mohou být využity k vytvoření určité vizualizační komponenty ve vlastní aplikaci. A tato řešení jsou „uspokojivá“, protože mnohé z těchto knihoven byly vyvíjeny zvláště proto, aby mohly být začleněny do co nejširšího okruhu aplikací [7]. V důsledku toho jsou integrace a přizpůsobení těchto knihoven poměrně snadno proveditelné a jejich nasazení vede přímo k požadovanému cíli. Tyto výhody činí ze spojnicových grafů dobrou volbu pro vývoj nekomplikovaných grafů během vytváření prvotních stupňů nově vyvíjených systémů dolování dat z textu. Implementace takových grafů je efektivní, protože pro vývojáře i uživatele umožňuje velice rychlou odezvu ohledně provádění algoritmů dolování textu. Mimo jejich využití jako vizualizačního nástroje pro vývoj jsou spojnicové grafy použitelné pro vizualizace výpočetních úloh vztahujících se

30

k širokému okruhu operací dolování textu. Vizualizační metody vztahující se k spojnicovým grafům jsou obecně dvojího typu.

Obrázek 5.7: Spojnicový graf ukazuje hodnoty asociací pro tři sady dotazů

První typ zahrnuje porovnání položek v celém jejich rozsahu. Jedna osa grafu představuje nějaké měřítko a druhá uvádí prvky pro srovnání. Příklad takového grafu můžeme vidět na obrázku obrázek 5.7. Druhý typ, který je pravděpodobně nejběžnější typ spojnicového grafu používaného v dolování dat z textu, je graf zobrazující vývoj veličiny či její velikost v průběhu času. Čárové diagramy poskytují velmi snadné pochopení grafické reprezentace analýz, které se provádí periodicky. Na vertikální ose je vynesena velikost hodnoty a horizontální osa označuje časové období. Viz obrázek 5.8. Spojnicový graf může být použit také jako hybrid předchozích dvou typů. Použitím víceřádkového grafu můžeme srovnávat různé typy společné pro úlohy dolování textu v souvislosti s časem. Viz obrázek 5.9.

5.2.4 Kruhový graf Kruhový graf je vizualizační metoda, která se dá použít pro umístění velkého množství informací do dvourozměrného formátu. Často se o něm hovoří jako o vizualizačním přístupu zřejmém „na první pohled“, protože

31

není potřeba žádné další navigace, abychom dostali kompletní a velmi přesnou vizualizaci pro případný rozsáhlý objem dat.

Obrázek 5.8: Spojnicový graf zobrazující počet dokumentů obsahujících pojem Osama bin Laden během určitého časového rozpětí

Obrázek 5.9: Dva příklady víceřádkového grafu srovnávajících vývoj hodnot v průběhu času [9]

32

Obrázek 5.10: Kruhový graf

Kruhový graf je vhodný zvláště při vizualizaci vzorků asociačních pravidel, ačkoliv se dá taky přizpůsobit k zobrazení informací o kategoriích. Tento formát získal oblibu díky hojnému používání komerčního vizualizačního nástroje pro dolování dat zvaného NetMap (http://www.altaanalytics.com/). Obrázek 5.10 ukazuje základní kruhový graf. Kruhový graf je v podstatě, jak již vyplývá z názvu, kruhovitý graf kopírující obvod kružnice, ve kterém jsou zakresleny položky. Vztahy mezi těmito položkami jsou představovány hranami, které spojují položky napříč vnitřním prostorem kruhu. Různé rozlišovací prvky, jako jsou barva a tloušťka spojovacích čar, mohou být použity tak, aby korespondovaly určitým typům vlastností spojení. Barevné přechody – gradienty – spojovacích čar mohou být použity pro zobrazení směru daného vztahu. Kruhové grafy jsou vynikající při modelování asociačních pravidel, která se vyskytují v množinách odpovědí na dotazy (viz obrázek 5.11). Jednotlivé pojmy jsou rozmístěny po okraji kruhu kruhového grafu a jejich asociace s jinými pojmy jsou znázorněny spojovacími hranami. V kruhovém grafu znázorňujícím asociace jsou zcela běžně používána různá vizuální vylepšení. Výše zmíněné gradienty mohou být použity k zobrazení směrovosti asociace, přičemž jiná zřetelně odlišná barva může být použita pro spojovací čáry k označení obousměrné asociace. Různá tloušťka spojovacích čar může být použita pro vyznačení příslušných informací o hodnotách vztahujících se k informacím. A konečně velikost, barva a typ písma zvolených pro popisky pojmů mohou být použity pro obrazové sdělení informace o jednotlivých pojmech v množinách výsledků dotazů. Pro zlepšení interaktivity v kruhových grafech je možno nechat pojmy na obvodu kruhu a vnitřní spojovací čáry reagovat na kliknutí myši. Když třeba uživatel klikne na pojem nebo pouze najede myší na jeho pozici, může získat další informace vztahující se k danému pojmu. Kliknutím myší na spojovací hranu může zase naopak vidět zvýrazněné asociace v seznamu asociací, které odpovídají případným stejným hodnotám.

33

Obrázek 5.11: Kruhový graf asociací

Obrázek 5.12: Spojovací diagram kategorií v kontextu osob a organizací

Ačkoliv se kruhové grafy hodí pro modelování rozsáhlých souborů dat asociací, je důležité rozpoznat, je-li taková vizualizační metoda skutečně vhodná a má-li vždy svůj efekt. Proto je vždy více než vhodné nabídnout uživateli snadný přístup k ovládacím prvkům pro možnost ovlivňovat různá omezení zobrazení tak, aby si mohl uživatel sám měnit vlastnosti zobrazení rychle a efektivně do podoby nejvhodnější pro danou úlohu vyhledávání.

34

Spojovací diagramy kategorií Kruhové grafy často slouží jako základ pro spojovací diagramy kategorií, což je další vizualizační nástroj užívaný při dolování dat z textu [7]. Spojovací diagramy kategorií zobrazují především asociace mezi pojmy z různých kategorií – všechny v daném kontextu. Obrázek 5.12 zobrazuje spojovací diagram kategorií s asociacemi mezi jedinci v kategorii People a objekty v kategorii Organization – všechny v souvislosti s terorismem. Při vytváření těchto diagramů je kladen velký důraz na formátování grafických a textových prvků na okraji kruhu. Na obrázku 5.12 jsou pojmy zakresleny kolem okraje kruhu takovým způsobem, že se pojmy z téže kategorie nachází vždy ve společné skupině. Všechny pojmy v dané kategorii mají typicky formátování ve stejné barvě a stejném typu písma k posílení názornosti vizualizační techniky, která zobrazuje pojmy uvnitř dané kategorie, přičemž se vždy výrazně liší od formátování jiných kategorií zobrazených v grafu. Hlavní popisky kategorií jsou nejčastěji zobrazeny doprostřed a vně celé skupiny svých pojmů jak je vidět například na obrázku 5.12, kde jsou názvy kategorií Person a Organization zvýrazněny tučným písmem podtrženy.

Metody vícenásobného kruhového grafu a kombinovaného grafu Aplikace používající kruhové grafy mívají grafické rozhraní podporující zobrazení více než jednoho kruhového grafu najednou [7]. Jedním z důvodů může být to, že je kruhový graf schopen zobrazit obrovské množství dat najednou, což může vést k nepřehlednosti. Vícenásobný kruhový graf může velice usnadnit práci při porovnávání výsledků dotazů. Takový přístup může mít stěžejní vliv na dolování dat z textu, když se nechají vykreslit dva a více grafy najednou majíc každý různé omezující hodnoty. Jiný příklad tohoto přístupu je spojovací diagram kategorií použitý na stejnou kolekci dokumentů a stejné seskupení kategorií ale v různých kontextech. Každý z těchto příkladů by mohl uživateli dovolit stanovit rozdílnosti a podobnosti v grafových vzorcích vícenásobného grafu. Obrázek 5.13 ilustruje použití vícenásobného kruhového grafu. Jiná technika týkající se zobrazení vícenásobných kruhových grafů najednou vyplývá z pokusů zvýraznit podgraf zvnitřku kruhového grafu. Protože je možno kruhovým grafem zobrazit najednou příliš velké množství dat, některé jemné vztahy se mohou stát nejasné – méně viditelné – díky obecnějším a silnějším shlukům v grafu.

35

Obrázek 5.13: Kruhové grafy a podgrafy zobrazeny vedle sebe

Tím že se dovolí uživateli kliknout na několik položek z hlavního grafu, může se nechat uživateli zobrazit podgraf zobrazující pouze vztahy mezi těmito položkami. Zobrazením podgrafu odděleně avšak zároveň s hlavním kruhovým grafem je dosaženo nové úrovně uživatelské interaktivity.

5.2.5 Samoorganizující síť - SOM Vizualizace dolování dat z textu je podporována díky výzkumům zaměřených na téma, jak mohou umělé neuronové sítě pomoci při vizualizaci informací [7]. Pravděpodobně nejdůležitějším přínosem jsou samoorganizující neuronové sítě (dále jen SOM), představeny v roce 1982 Teuvo Kohonenem a poprvé aplikované v roce 1991 v problematice vizualizace informací [4]. SOM jsou vytvářeny algoritmy, které během učící fáze opakovaně přizpůsobují váhové vektory mezi neurony, které jsou odvozeny ze vztahů nalezených ve vstupním souboru dat vysoké dimenze převedených do dvoudimenzionálních sítí. Díky tomuto přístupu mají SOM výhody v organizaci takových množin dat, které jsou extrémně velké co do objemu ale také vztahů mezi nimi.

36

Nyní si proces, díky kterému dochází k adaptaci vah uvnitř samoorganizující neuronové sítě, popíšeme podrobněji pomocí Kohonenova algoritmu v šesti bodech: 1. Inicializace sítě Na začátku jsou všechny váhy inicializovány malými náhodnými čísly. Parametr učení η (0 < η < 1) určující velikost změn při adaptaci vah je nastaven na hodnotu blízkou jedné a během učení se monotónně snižuje k nule. Tím je na začátku procesu učení dosaženo rychlejší adaptace vah. 2. Předložení vstupního vektoru Trénovací vzory jsou předkládány v náhodném pořadí ve formě

x1 (t ), x2 (t ),K, xn (t ) , kde xi (t ) je vstup uzlu i v čase t.

3. Výpočet vzdáleností – stanovení vítěze kompetice Kolem každého neuronu je definováno okolí, kolem kterého budou prováděny změny vah, pokud bude tento neuron vybrán v kompetici. Velikost, tvar a míra vlivu tohoto okolí jsou parametry sítě a mění se během učení. 4. Výběr minimální vzdálenosti Pro předložený vzor najdeme jemu odpovídající nejbližší neuron. 5. Úprava vah Váhy vítězného neuronu a neuronu v jeho okolí jsou adaptovány

(

)

podle vztahu mij (t + 1) = mij (t ) + η (t )h(v, t ) xi (t ) − mij (t ) , kde i = 1,2, K , n a j = 1,2, K , n a lokální okolí neuronu je vyjádřeno adaptační funkcí

h(v ) , jejíž hodnota se postupně snižuje, aby došlo ke stabilizaci

nastavených vah. 6. Přestup k bodu 2. K dosažení nejlepšího uspořádání neuronu do shluku se na začátku volí velké okolí a velký vliv učeného vzoru na změny ve vahách neuronu. Postupným učením se vytvoří jednotlivé shluky. Poté je nutné snížit okolí neuronu a vliv změn při učení vzoru. Zmenšení rozsahu prováděných změn v uspořádání neuronu se provede násobením hodnot u adaptační funkce s parametrem učení η, jehož hodnota se s časem učení postupně snižuje k nule. Další a podrobnější informace týkající se problematiky popisu formálního neuronu, neuronových sítí a různých adaptačních technik jejich vah naleznete v Umělá inteligence a neuronové sítě od Ivo Vondráka [13].

37

Re: Temporal Computation

Dr L S Smith (Staff), 7 Aug 1995, Lines: 71.

Help-Interpretation of hidden neuron weights

Ira Cohen, 1 Sep 1995, Lines: 11.

Re: Help-Interpretation of hidden neuron weights Neural training courses

Will Dwinnell, Tue, 5 Sep 95, Lines: 23.

John Z. Zhao, Fri, 26 Jan 1996, Lines: 12.

How good would a backprop network be for this task? Re: Neural Dynamics Question Re: Belgian Support

Teen Age Riot, Fri, 5 Apr 1996, Lines: 30.

Josh Reich, 28 Aug 1996, Lines: 42.

Dirk Bellemans, Wed, 15 Jan 1997, Lines: 29.

State Machine Model of a typical Neuron

"Anthony Q. Bachler", 13 Feb 1997, Lines: 11.

Obrázek 5.14: WEBSOM – během dotazování jsou uživatelé provázení mapou dokumentů díky uživatelskému rozhraní, které podporuje interaktivní zoomovací a prohlížecí funkce. Mapa je tvořena 12.088 publikovanými články a naleznete ji na: http://websom.hut.fi/websom/comp.ai.neural-nets-new/html/root.html

WEBSOM Jednou z nejznámějších a nejrozšířenějších aplikací SOM pro textová data je WEBSOM (http://websom.hut.fi/websom/) [14]. WEBSOM využívá upravenou verzi původního Kohonenova algoritmu pro SOM k uspořádání velkého množství dat do podoby, kterou návrháři nazývají „mapa dokumentů“, která je v podstatě graficky velice podobná mapě topografické (viz obrázek 5.14). Stíny na mapě zobrazují koncentraci textových dat nebo

38

slova, která jsou si velice podobná nebo jednotlivá témata. Světlejší místa představují menší koncentraci. Cílem metody WEBSOM je automaticky provést organizaci jakékoliv kolekce dokumentu tak, abychom v ní mohli snadněji prohledávat a zkoumat dokumenty. Nyní si ukážeme jednotlivé na sebe navazující části architektury WEBSOM: 1. Textové dokumenty 2. Vytvoření vektoru dokumentu − Předzpracování textu. − Vypočítání vektoru dokumentu jako vážený histogram slov. − Použití náhodné projekce k redukci dimenze. 3. Vytvoření velké mapy − Inicializace modelu nejmenších SOM. − Učení malých map. − Opakujeme, dokud nedosáhneme požadované velikosti mapy: • Odhadnutí velké mapy na základě menší. • Vytvoření ukazatelů z dat do modelu. • Doladění mapy paralelním Batch Map algoritmem. 4. Vytvoření uživatelského rozhraní − Automatické vybrání charakteristických bodů mapy. − Vytvoření nezbytných části pro operace s rozhraním. 5. Volba operací uživatelského rozhraní − Procházení uzlů − Vyhledávání typu obsah-adresa: • Vytvoření vektoru dokumentu pro hledaný dokument stejnou cestou jako v bodě 1. • Vrácení nejvíce podobné lokality a vizualizace výsledku − Hledání podle klíčových slov: vizualizace výsledku indexového vyhledávání v mapě. Jedna z největších předností WEBSOMu je schopnost zacházet s obrovským množstvím dat. Důkazem toho je, že WEBSOM vytvořil mapu dokumentů, která adresuje více než jeden milion dokumentů. Jeho automatický algoritmus pro tvorbu map je údajně schopen dodělat vizualizaci pro malou až středně velkou kolekci dokumentů (cca 10.000 dokumentů) za méně než pár hodin. Další výhoda WEBSOMu je robustnost. WEBSOM je plně zoomovatelné rozhraní, které dovoluje opakovaně se přibližovat na různé úrovně zvětšení. Rozhraní mapy dokumentů je také velmi interaktivní. Stačí kliknout na zvýrazněný název nebo na část mapy a zobrazí se seznam odpovídajících dokumentů, statistických informací nebo obojí v pop-up okně.

39

Obrázek 5.15: Kartografická mapa SOM datového souboru ARIST

Uvedeme si praktický příklad WEBSOM diagramu dokumentů, který vidíme na obrázku 5.15. Využívá SOM pro vytvoření doménové vizualizace ve stylu kartografické mapy. Trénování SOM je založeno na seznamu klíčových slov datového souboru ARIST [9] a pro vytvoření vizualizace je použit ArcGIS. Označení shluků bylo provedeno automaticky uvnitř ArcGIS pomocí pravidel, která byla do něj vložena na základě spojení mezi atributy a vlastnostmi jednotlivých označení [9]. Mapa na obrázku 5.15 se snaží o to, abychom mohli snadněji využít zkušenosti, které máme s tradičními geografickými mapami. Celá SOM je složena z 2200 neuronů. Pro tyto neurony byl vypočítán hierarchický strom shluků aby bylo možno datový soubor prozkoumávat v zoomovatelném rozhraní. Proto tato konkrétní vizualizace zobrazuje jen 25 označených oblastí. Pro bližší studium datového souboru ARIST a jiných konkrétní aplikací sítí SOM lze využít zdroj Katy Börner a kol. Visualizing Knowledge Domains [9].

40

5.2.6 Hyperbolické stromy Hyperbolické stromy, které byly zpočátku vyvíjeny ve výzkumném centru Xerox Palo Alto Research Center, patří mezi první metody focus-pluscontext (viz kap. 3.3), které byly vyvinuty proto, aby usnadnily vizualizaci rozsáhlého množství dat [7]. Technika vychází z určité interpretace Poincaréova modelu hyperbolické neeuklidovské plochy, čímž nabízí více zobrazovacího prostoru pro tu část oblasti, která je v centru pozornosti, avšak stále umístěna v celém - ač vizuálně poněkud „zeslabeném“ – kontextu celé hierarchie. Velice rozšířený komerční nástroj pro tvorbu rozhraní s hyperbolickými stromy je prodáván společností Inxight Software pod značkou StarTree Studio na http://www.inxight.com/ (viz obrázek 5.16). Hyperbolické stromy vynikají při analytických úlohách, ve kterých je užitečné vidět jak detaily, tak i celý kontext najednou. To potvrzují zejména ty situace, ve kterých analytik potřebuje prozkoumat velmi komplexní hierarchicky uspořádaná data nebo hierarchie mající obrovský počet uzlů. Nástroje pro vizualizaci hyperbolických stromů jsou od svého vzniku navrhovány tak, aby dynamicky podporovaly průzkum textových dat. Diagram hyperpolického stromu je na samém začátku zobrazen nejprve jako strom se svým kořenem uprostřed kruhového prostoru. Diagramem lze snadno manipulovat tak, aby se do středu pozornosti dostaly jiné uzly. Hlavní vlastnosti, které podporují možnosti hyperbolického stromu, jsou tyto: •

prvky diagramu se zmenšují, jsou-li přesouvány více k okraji

•

existuje exponenciální růst v počtu možných komponent.

Tyto dvě vlastnosti by mohly být popsány jako určitá forma deformace roviny sledované rybím okem a schopnost rovnoměrně zakomponovat exponenciálně rostoucí strukturu. Společně s Poincaréovým mapováním neeuklidovské plochy umožňují vizualizačním nástrojům prozkoumávat rozsáhle hierarchie na relativně omezeném prostoru Mimořádná funkcionalita hyperbolických stromů se stará o mnohem více než jen o to, že dovolí uživateli být v interakci s větším počtem hierarchických uzlů než jiné tradiční metody, velmi také podporuje aktivní přístup od uživatele k hierarchickému souboru dat. Na obrázku 5.17 vidíme další příklad hyperbolického stromu.

41

Obrázek 5.16: Service [12]

Hyperbolický strom pro vizualizaci stránek National Park

Obrázek 5.17: Nástroj StarTree použitý jako mapa stránek pro web automobilky Porsche [12]

42

Diagram hyperbolického stromu podporuje dynamické prohlížení dat založeném na vizualizaci a umožňujícím uživateli posouvat pomocí myši s celou hierarchií vyskytující se kolem položky, která je v centru zájmu, a pak kliknutím přeskočit na jiný uzel a podívat se na zbytek jeho kontextové hierarchie z jiných úhlů. Uživatel se tak stává plně zapojeným spoluúčastníkem v průzkumu vzorků, a není jen pasivním divákem, který pouze zapisuje dotazy.

5.2.7 Bifokální stromy Bifokální stromy jsou novou technikou pro vizualizace hierarchií, která je založena na metodě focus-plus-context, ale používá dvě ohniska na místo jednoho [11]. Tato technika dovoluje zlepšení prezentace jak detailů vztahujících se k nějaké položce v informačním prostoru tak i celého kontextu. Toho je dosaženo zobrazením hierarchie pomocí grafu s uzly a hranami vizuálně rozdělených do dvou spojených podgrafů. Jeden odpovídá podstromu s uzlem, který je předmětem zájmu a je zobrazen jako kořen. Druhý podgraf představuje context a obsahuje vybraný rodičovský uzel a zbývající podstromy. Ačkoliv bifokální stromy nejsou zcela založeny na hyperbolické geometrii, tak jako stromy hyperbolické, mají podobné vlastnosti, jak můžeme vidět na obrázku 5.18. Hierarchie je jakoby „ukotvena“ na dvou hlavních uzlech, které se nazývají kontextové a detailní ohnisko, přičemž jsou obě tato ohniska umístěna vedle sebe. Každý podstrom z obou oblastí je zobrazen v radiálním rozvržení, kde je vybraný uzel ve středu kruhu a jeho potomci jsou rozmístěni v soustředných kruzích závisejících na jejich úrovni ve struktuře. Aby se předešlo vzájemnému „pohlcení“ mezi objekty, je každý podstrom představován kruhovou výsečí a ne celým kruhem. Velikost uzlů potomků a jejich vzdálenost od uzlů v ohnisku jsou vypočítávány v závislosti na jejich relativní pozici od těchto uzlů. Je to jako kdybychom se dívali objektivem s krátkým ohniskem (tzv. rybí oko), ačkoliv to zcela přesně neodpovídá deformaci, jakou poskytuje skutečné rybí oko. Ve skutečnosti jsou uzly vzdálené od ohniska zobrazeny s menšími detaily než uzly, které jsou ohnisku blíže, a uzly nacházející se za určitou hranicí nejsou zobrazeny vůbec. Tato technika zabraňuje tomu, aby se zobrazily prvky, které jsou už příliš daleko od centra našeho zájmu.

43

Obrázek 5.18: Bifokální strom zobrazující hierarchii s přibližně 370 uzly

Viditelné uzly jsou zobrazeny jako obdélníky, jejichž šířka se počítá podobně jako vzdálenost od ohniska. Výška je fixní, aby mohl být zobrazen text nebo jeho část, pokud se jedná o vzdálenější uzly mající šířku vypočítanou na menší rozměr. Nejvzdálenější ještě viditelné uzly už jsou reprezentovány jen drobnými čtverci. Různé barvy jsou použity ke znázornění částí podstromů, což snižuje možnou dezorientaci, ke které může dojít díky rotacím a různým přesouváním během transformace podstromu, když je výběrem jiného uzlu jako ohniska změněn celý graf. Hlavní mechanismus interakce poskytovaný uživateli je tedy výběr uzlu. Vybrán může být kterýkoliv uzel, který chceme přenést do detailního pohledu. Tato operace modifikuje také kontextovou oblast, zatímco jsou rodiče nově vybraného uzlu přeneseny do kontextového ohniska. Tato operace skutečně přesune podstrom do detailní oblasti stejně, jako provede rotaci ve struktuře zobrazované v kontextové oblasti tak, aby se předešlo okluzi a rodičovské uzly byly přesunuty do kontextového ohniska (viz obrázek 5.19).

44

Obrázek 5.19: Vlevo rozvržení před výběrem uzlu navbar. Vpravo rozvržení po vybrání uzlu navbar

5.2.8 Třídimenzionální metody Spousta systémů dolujících data z textů se pokouší simulovat třídimenzionální efekty, aby tak vytvořily efektivnější nebo snadněji přizpůsobitelné modely složitých vztahů, které jsou mezi textovými daty v kolekcích dokumentů. Trojrozměrné vizualizace umožňují uživatelům prozkoumávat takové modely, které mají méně omezení než tradiční (2D) hierarchické reprezentace nebo reprezentace tvořené uzly a hranami díky posílení prostorové složky vhodné pro tvorbu takových grafických modelů, které jsou vytvářeny komplexnějšími vícevrstvými samoorganizujícími sítěmi [7]. Optimalizované 3D renderovací algoritmy a široká dostupnost výkonných grafických karet vhodných pro desktopy vytváří kromě výše uvedeného dobré podmínky pro tvorbu 3D vizualizací, které jsou vhodnějších pro použití v systémech dolování dat z textu než kdykoliv předtím. Příklad 3D síťového diagramu vidíme na obrázku 5.20. Navzdory všem potenciálním možnostem a výhodám, které 3D modely přinášejí pro vizualizaci informací, přinášejí tyto modely také

45

několik nových problémů. Dva podstatné problémy pro použití 3D vizualizace v dolování dat z textu jsou okluze a hloubka související s přidáním třetího rozměru. Oba problémy vyvstávají v situacích, ve kterých je požadována reprezentace vysoce objemných dat. A to jsou naneštěstí právě ty případy, ve kterých by se aplikace dolování dat z textů „nejraději spojily“ s 3D vizualizačními nástroji. 3D vizualizační nástroje obvykle nezjednodušují proces navigace a průzkumu dat. Uživatel se musí některé speciální navigační techniky často naučit. Vzrůstající komplexnost v navigaci je většinou nepřímo úměrná intuitivnímu jednání uživatele, který s takovým systémem spolupracuje. Není pochyb o tom, že se bude výzkum týkající se 3D vizualizace nadále ubírat takovým směrem, aby se 3D metody staly skutečně efektivní. V současné době převažují nevýhody 3D přístupu k vizualizaci nad jeho výhodami. Je taky docela možné, že 3D vizualizace nebude nikdy efektivní v pochopení 2D informací, se kterými se setkáváme při dolování dat z textu. V současné době by tedy měli návrháři takových systémů stále pečlivě vyhodnocovat praktické výhody i stinné stránky tkvící v případném začlenění 3D vizualizačních nástrojů do jejich aplikací.

Obrázek 5.20: 3D pohled na diagram společných citací autorů vědeckých prací navrhujících různé obory v oblasti renderingu a ray tracingu s vyznačením těch nejoblíbenějších

46

5.2.9 Hybridní nástroje Kombinace identických multigrafů nebo různých typů multigrafů má zvláštní úlohu při poskytování analytických informací o výsledcích dotazů. Návrháři vizualizačních nástrojů často přicházejí s prezentačními technikami, které vypadají jakoby spojovaly části různých vizualizačních formátů do nové souvislé podoby. Doplnění dobře známých grafických formátů o nové prvky může přinejmenším dramaticky zvýšit množství informací, které jsou spojeny s grafickým nástrojem [7]. Jedním z možných úskalí při tvorbě takových hybridních nástrojů je neúměrné zvýšení složitosti. V lepším případě uživatel pochopí aspoň hlavní sdělení bez větších obtíží. Dalším úskalím je však snížená srozumitelnost grafu a protože vizualizace často obsahuje nadbytek vzorků, komplexnější nástroje mohou vést spíše ke zmatkům v prezentaci. I přesto mají tyto nástroje uplatnění ve velmi specifických aplikacích dolování dat z textu a jsou skutečně použitelnější, než kdyby návrháři těchto systémů použili jen základních vizualizačních forem. Na obrázcích 5.21, 5.22 a 5.23 jsou ukázky různých typů hybridních nástrojů.

Obrázek 5.21: Daisy diagram spojující vzhled kruhového diagramu a komplexního srovnávacího histogramu

47

Obrázek 5.22: HSOM – hyperbolická samoorganizující síť, která promítá 3D prvky na hyperbolickou stromovou síť ve tvaru trojúhelníkové mozaiky. HSOM je nejvhodnější pro vizualizaci celkového přehledu rozsáhlých kolekcí dat, přičemž umí zároveň pracovat s velkým množstvím objektů určených k vizualizaci [10]

HSOM Ontrup a Ritter navrhli nový typ SOM pro navigaci v sémantickém prostoru rozsáhlých textových kolekcí HSOM (hyperbolická SOM [10]) založenou na pravidelné mozaice hyperbolické roviny, která je neeuklidovským prostorem. Exponenciálně se zvětšující velikost sousedství kolem bodů v hyperbolickém prostoru poskytuje více volnosti pro mapování celého informačního prostoru vyplývajícího z jazyka do prostorových vztahů. Hlavní výhodou HSOM je tedy její mimořádná schopnost mapovat vysoce dimenzionální vztahy do nízko rozměrného prostoru, se kterým může uživatel snadněji zacházet a lépe mu porozumět. Obrázek 5.22 ukazuje celkový pohled na data zpravodajské agentury Reuters. Pro vizualizaci deseti nejfrekventovanějších kategorií bylo použito deset různých glyfů. Přiřazení bylo provedeno manuálně tak, aby bylo snadno rozpoznatelné, které objekty patří do té které kategorie. Velikost glyfů a zetová hodnota, představována výškou nad „zemní plochou“, odráží

48

počet tréninkových a testovacích dokumentů mapovaných samostatně na každý odpovídající uzel.

Obrázek 5.23: Pokračování ukázky příkladu použití HSOM z obrázku 5.22

Všimněme si, že největší množství dat se namapovalo do oblastí, které jsou nejvíce na okraji prostoru, kde uzly HSOMu využívají nejvíce prostoru, který jim nabízí hyperbolická geometrie. Během procesu učení nebylo HSOM prezentováno žádné rozdělení do kategorií, i přesto bylo možno jasně rozpoznat některé shluky dokumentů. Nejvíce ze všech vynikají ty oblasti map, které jsou označeny slovy earn a acquisition, což odráží největší podíl těchto kategorií v celé kolekci dokumentů Reuters. Všimněme si také, že sémanticky příbuzné kategorie jsou umístěny blízko sebe. Na obrázku 5.23 je vidět stejný diagram jako na obrázku 5.22. Jediný rozdíl je v tom, že na obrázku 5.23 je nyní ohnisko přesunuto do směru, kde se nachází uzel ship, který byl velice nápadný už na obrázku 5.22 díky velké zetové hodnotě, která vyjadřuje obrovský počet testovacích dokumentů. Přesunutí ohniska celého diagramu do blízkosti tohoto uzlu také způsobilo zvětšení odpovídající oblasti. Tímto však také došlo k nahuštění dříve relativně dobře rozmístěných uzlů do části zcela napravo, čímž došlo k nepřehlednosti. My se však můžeme opět vrátit na předchozí ohnisko a poté se zaměřit pro změnu na jinou část diagramu.

49

Obrázek 5.24: Hybridní trojrozměrný síťový diagram, který obsahuje prvky grafů s uzly a spojeními a histogramové prezentace s trojrozměrnými efekty a tabulkami s popisy

Na obrázku 5.24 vidíme velice efektně působící vizualizaci, které se věnuje skupina kolem Katy Börner v práci Visualizing Knowledge Domains [9]. Vizualizace zachycuje detailní pohled několika shluků podél hlavní spojnice diagramu DCA (diagram zachycující analýzu společných citací dokumentů). Výška sloupců představuje počet citací na publikaci. Štítky označují články ve shlucích, přičemž několikeré publikace uvnitř stejného roku se na této úrovni nerozlišují.

50

6. Aplikace Graph Analysis 6.1

Projekt The Netron Project

Pro naši potřebu vizualizace jsme zvolili použití a následné doplnění existující aplikace, která je součástí projektu The Netron Project (dále jen TNP). Projekt je napsán v programovacím jazyce C# pro platformu .NET Framework. Hlavní aktivitou seskupení programátorů projektu TNP je návrh a vývoj softwarových nástrojů, které umožňují demonstrovat schopnost grafů a diagramů vizualizovat data. Výhodou celého programového balíku je to, že je jeho kompletní kód volně k dispozici. Každý programátor má tedy možnost vyvíjet vlastní aplikace založené na knihovnách TNP. Celý kód je velice stručně okomentován přímo ve zdrojovém kódu. Jednoduchost komentářů nijak nesnižuje jejich informační hodnotu. Všechna pojmenovaní a názvy vždy vystihují to, k čemu jsou určeny, což opět zrychluje orientaci v už tak relativně velkém zdrojovém kódu, který čítá odhadem 75.000 řádků.

6.2

Balík GraphApplications

Z projektu TNP jsme zvolili konkrétní vizualizační nástroj z aplikačního balíku GraphApplications zvaný Graph Analysis, který se jevil jako nejvhodnější pro naše potřeby vizualizace. Program jsme přeložili a ihned po spuštění se vygeneruje jednoduchý graf s několika vrcholy. Tyto vrcholy náhodně rozmístí na plátně a mezi několika těmito vrcholy vytvoří náhodně zvolené hrany. Vše již pak záleží na programátorovi, jaká data bude používat pro vstup. K dispozici je několik možností vstupních dat nejlépe pomocí binární matice. Je zde několik abstraktních tříd a několik tříd, které jsou z nich odvozeny, a každý si podle potřeby může vybrat tu nejvhodnější, která odpovídá povaze právě jeho vstupních dat nebo si dopsat třídu vlastní, která může dědit třeba z některé abstraktní třídy. Aplikace rovněž obsahuje vymodelované třídy pro export v různých formátech. Opět je na programátorovi, jestli si zvolí některou existující nebo ji přepíše a nebo si vytvoří vlastní.

51

Obrázek 6.1: Příklad zobrazení náhodně vygenerovaného grafu Graph Analysis

6.3

Specifikace požadavků

Vývoj našeho programu, který vychází z aplikace Graph Analysis a spočívá v přepsání jejího kódu podle našich představ, je shrnut v následujících bodech: •

•

simulace trojrozměrné vizualizace grafu −

různá velikost vrcholů

−

trojrozměrné vrcholy

−

gradientní hrany

procházení grafem −

•

omezení vizualizace objektů při zobrazení grafu, jehož vstupem bude symetrická matice obsahující stovky až tisíc objektů.

vstupní data −

textovým popisem zadaná symetrická matice vyjadřující podobnost mezi objekty

−

pomocí jazyka XML popsaná binární stromová struktura

6.3.1 Simulace trojrozměrné vizualizace grafu Nyní si slovně popíšeme jednotlivé detaily vizualizace, které se v konečném výsledku snaží navodit dojem, že se jedná o trojrozměrné zobrazení.

52

Obrázek 6.2: Ideální představa zobrazení trojrozměrného grafu

•

Velikost vrcholů Záměrem simulace zobrazení grafu je možnost zvýraznit určitá data a závislosti při zachování zobrazení ostatních dat. Toho je docíleno různou velikostí jednotlivých vrcholů v závislosti na hodnotě na dané pozici v matici, přičemž vrchol s menší hodnotou má vždy nižší hodnotu alfa kanálu a vyvolává dojem, jakoby ustupoval do pozadí. Velikost vrcholu je dána počtem spojení s jinými vrcholy. Nejmenší vrchol je tedy ten, který není spojen s žádným dalším vrcholem.

•

Trojrozměrné vrcholy Každý vrchol je zobrazen jako koule, která je osvětlena pomyslně umístěným zdrojem světla v levém horním rohu plátna, na němž se zobrazuje celý diagram. Hrany mezi spojenými vrcholy přebírají od těchto vrcholů jejich hodnotu alfa-kanálu. Představme si tedy situaci, že existuje hrana mezi dvěma vrcholy, z nichž první vrchol je v popředí zobrazen s vyšší hodnotou alfa-kanálu a druhý vrchol je v pozadí zobrazen s nižší hodnotou alfa-kanálu.

•

Gradientní hrany Zobrazení hrany je vždy odvozeno od obou vrcholů, se kterými je každá hrana spojena. Na konec hrany, která je spojena

53

s prvním vrcholem, je aplikována hodnota alfa-kanálu prvního vrcholu a na opačný konec hrany, která je spojena s druhým vrcholem, je aplikována hodnota alfa-kanálu druhého vrcholu. Obsahuje-li graf ve výsledku dostatečně velký počet vrcholů s několika hranami, dochází tak k zajímavému efektu pozvolna ustupujících hran, čímž se ještě více zvyšuje pocit trojrozměrného zobrazení takového grafu.

6.3.1 Vstupní data Jak jsme již uvedli v páté kapitole, výsledky dotazu se dají vizualizovat různými technikami. Tyto výsledky jsou vždy v určité formě, která je vhodná pro použití jako vstupu pro aplikaci zajišťující vizualizaci. Tak jako lze výsledky vizualizovat vhodnými metodami, lze pro jednu vizualizační metodu použít více forem vstupních dat, které však musí aplikace podporovat. Symetrická matice Prvním typem vstupních dat bude textovým popisem zadaná symetrická matice vyjadřující podobnost mezi objekty. Pro ilustraci si uveďme jednoduchý příklad. Mějme symetrickou matici, která vyjadřuje podobnost mezi objekty a je zadána takto:

0

5

1

1

3

0

5

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0 12

0

3

0

0 12

0

0

0

0

0

0

0

0

Výstupem takovéto matice bude graf se šesti vrcholy, jak napovídají rozměry matice. Z matice vyčteme, že první vrchol je propojen s nejvíce dalšími vrcholy. Dle specifikace bude tedy zobrazen jako největší. Dále můžeme vyčíst, že mezi čtvrtým a pátým vrcholem je nejsilnější vazba. Tyto vrcholy budou tedy zobrazeny jako nejvíce v popředí a také vazba mezi nimi bude zobrazena silnou čarou. Šestý vrchol bude zcela v pozadí, protože není spojen s žádným dalším vrcholem a jeho zobrazení bude potlačeno úplně nejvíc. Vizualizaci toho příkladu viz obrázek 6.3. Maticový zápis vstupních dat je tedy velice jednoduchý. Vstupem pro naši aplikaci bude textový soubor a v něm budou jednotlivé řádky matice

54

zapsány na jednotlivých řádcích textového souboru a každý prvek na řádku bude oddělen od předchozího mezerou.

Obrázek 6.3: Ukázka vizualizace. Vstupní data: symetrická matice

Binární strom popsaný pomocí XML Druhým formátem vstupních dat bude binární strom popsaný pomocí XML [22]. XML je ve své podstatě univerzální formát pro tvorbu, správu a výměnu dokumentů. V těchto dokumentech umožňuje mít informace inteligentně strukturované a to práci s nimi výrazně usnadňuje. XML je zkratka anglického eXtensible Mark-up Language, což znamená rozšířitelný značkovací jazyk. Značkování znamená označení některých údajů tak, abychom jim přiřadili určitý význam [22]. Značkováním v elektronickém dokumentu se rozumí kód, uložený spolu s textem dokumentu, který v sobě nese informace potřebné pro elektronické zpracování. Značkovací jazyk pak v počítačové terminologii znamená soubor pravidel ohledně tohoto kódu neboli značek: jak se budou tyto značky odlišovat od ostatního textu, co bude ta která značka znamenat, v jakých vzájemných vztazích mají být jednotlivé elementy (části textu vymezené značkami) použity a podobně. A konečně slovo „rozšiřitelný“ znamená možnost definovat si vlastní značky. Pomocí XML značek se označuje v dokumentu význam jednotlivých částí textu, proto jsou takové dokumenty informačně bohatší. Díky skutečnosti, že formát XML je založen na obyčejném textu, jsou i jeho

55

zdrojové texty snadno čitelné. Navíc lze takový soubor otevřít v libovolném textovém editoru a ručně jej upravit. Popis struktury XML dokumentu Nyní si popíšeme strukturu konkrétního formátu XML dokumentu pro naši aplikaci. Hlavní element Clusters se dělí na dva elementy Left a Right. Každý z těchto dvou elementů se už potom může dělit jen: •

na další dva elementy Left a Right nebo

•

na element Document, který se nedělí na žádný další element

Element Clusters a každý výskyt elementů Left i Right mají svůj atribut Id, aby byly v jakékoliv situaci snadno identifikovatelné, protože hodnota tohoto atributu je v celém dokumentu jedinečná a atribut Level pro určení hloubky při vizualizaci. Na následujících řádcích je ukázka velice jednoduchého dokumentu XML s naznačenou hloubkou zanoření.

Ukázka dokumentu XML s naznačenou hloubkou zanoření. C:\DOKUMENTY\INDEX\1.TXT C:\DOKUMENTY\INDEX\3.TXT C:\DOKUMENTY\INDEX\4.TXT C:\DOKUMENTY\INDEX\5.TXT C:\DOKUMENTY\INDEX\2.TXT

56

6.4

Vizualizační nástroj Graph Analysis

Aplikace Graph Analysis je napsána jako všechny aplikace z balíku TNP velice komplexně a snaží se pokrýt všechny hlavní prvky vizualizace grafů. Sama o sobě už obsahuje obrovské množství napsaných tříd, které často implementují řadu rozhraní. Detailní popis každé třídy a rozhraní je nad rámec této práce a proto se zaměříme na popsání důležitých částí kódu a to zejména těch, které jsme upravili tak, aby vizualizace odpovídala výše popsané specifikaci.

6.4.1 Třída MainForm Spustitelnou třídou je třída MainForm, která je ze jmenného prostoru Netron.GraphAnalysis. Veškerý zdrojový kód tohoto jmenného prostoru je součástí jednoho projektu z celého souboru projektů TNP zvaného GraphAnalysis. Třída MainForm dědí ze System.Windows.Forms.Form, což je komponenta představující hlavní formulář pro desktopové aplikace. Je to komponenta pro umístění standardních ovládacích prvků, jako jsou menu, stavové řádky, nástrojové lišty a další typy prvků a pro naše účely vykreslení diagramu jsme upravili její funkcionalitu tak, aby bylo vytvořeno velice jednoduché uživatelské rozhraní. Díky prostředí .NET Framework, které přináší zcela novou funkcionalitu zjednodušující a urychlující vývoj desktopových i internetových aplikací, je snazší i přidávání nových komponent do existujícího kódu. V našem případě tvoří formulář jakýsi kontejner, do něhož jsou při inicializaci vloženy další komponenty tvořící uživatelské rozhraní. Všechna nastavení týkající se vzhledu a chování tohoto formuláře se provádějí formou vlastností. Díky vizuálnímu design modu je možné všechny tyto operace provádět velmi snadno. MainForm má pomocí těchto vlastností nastavenou šířku a výšku, text v záhlaví okna, bitmapový soubor s ikonou programu a spoustu dalších vlastností.

Popis uživatelského rozhraní Třída obsahuje několik členských objektů, odpovídajících jednotlivým komponentám. Ty jsou instaciovány v metodě InitializeComponent, která je volána z konstruktoru třídy. Okno aplikace obsahuje ve své horní části menu. Hlavní část je rozdělena na panel s vykreslovací oblastí a na panel s needitovatelným textovým oknem zobrazujícím zajímavé informace o právě probíhající úloze. Panelu s vykreslovací oblastí je jako parametr přidána instance třídy GraphControl, která je kontejnerem pro vykreslované objekty. Více o třídě GraphControl pohovoříme v samostatné kapitole 6.4.2.

57

Dolní část programu je rozdělena na dvě skupiny. První skupina s názvem View settings shromažďuje prvky pro ovládání omezení zobrazení při vizualizaci symetrické matice. Snažili jsme se, aby naše aplikace byla schopna vizualizovat matice o stovkách až tisíci objektech. Je zřejmé, že na tak malé ploše, jako je vykreslovací oblast, nelze zobrazit graf v přehledné formě. Proto je uživateli umožněno, aby si vybral jen určitý interval hladin v trojrozměrné reprezentaci symetrické matice. Pro tento účel jsme vytvořili jakési zarážky, které určují horní a dolní mez. Tyto hranice jsou reprezentovány posuvníky, kterými si může uživatel nastavit požadované meze. Všechny objekty nacházející se uvnitř vymezených hodnot jsou pak vizualizovány bez ostatních, které jsou mimo tyto meze. Napravo od obou posuvníků se potom zobrazuje informace o aktuálním intervalu. Druhá skupina obsahuje ovládací prvky pro vygenerování symetrické matice o velikostech 50x50, 100x100, 200x200, 500x500 nebo 1000x1000. Uživatel si jednoduše vybere požadovanou velikost a klikne na tlačítko Generate similarity matrix. V aktuálním adresáři se vytvoří soubor s příponou txt obsahující textovým popisem zaznamenanou nově vygenerovanou symetrickou matici.

Popis položek v menu Ovládání programu je velice jednoduché. Uživatel si v menu zvolí, co chce vizualizovat. Na výběr má tři možnosti. První možností je Random Graph, která náhodně vygeneruje graf o dvaceti vrcholech a provede náhodná spojení mezi některými dvojicemi vrcholů. Tuto možnost jsme ponechali z původního projektu pro případ, že uživatel nebude mít žádná vstupní data a bude chtít pouze vidět, jak může takový graf pomocí naši vizualizace vypadat. V grafu nejsou vizualizovány různé tloušťky hran. Druhá možnost je Load Similarity Matrix, která otevře dialogové okno pro vybrání textového dokumentu s příponou txt a zobrazí diagram na základě symetrické matice vyjadřující podobnost mezi objekty. Požadovaný formát, v jakém musí být matice zadaná, je v kapitole 6.3.1. Po načtení matice do paměti provede aplikace její zobrazení na plátně a uživatel vidí její vizualizaci. Jak probíhá načtení dat matice a čeho je se třeba vyvarovat, popíšeme podrobněji v kapitole 6.4.8. Třetí možnost, kterou si může uživatel v menu zvolit, je Load XML Binnary Tree, která opět otevře dialogové okno pro načtení tentokrát XML dokumentu. Pomocí této volby se načte dokument ve formátu XML obsahující data binárního stromu. Po načtení do paměti se provede zobrazení grafu na plátně a uživatel tak může vidět jeho vizualizaci. Jak

58

probíhá načtení XML dokumentu a zobrazení uložených dat, popíšeme více v kapitole 6.4.9. Pro lepší orientaci ve zdrojovém kódu poslouží třídní diagram, zachycující některé důležité třídy, resp. ty třídy, které doznaly změn našim zapříčiněním. Uprostřed diagramu se nachází třída MainForm. Nechali jsme zobrazit jen některé třídy, i když bychom měli správně zobrazit jediný diagram postihující všechny aspekty výsledného systému. Systém tříd projektu TNP je však natolik rozsáhlý, že by zobrazení kompletního třídního diagramu ubralo na jeho srozumitelnosti, nehledě na to, že by se takový diagram na formát A4 ani nevešel. Vynechali jsme také atributy a metody, protože jejich výčet by byl také extrémně dlouhý a čtenář si může tyto údaje vyhledat sám v dobře strukturovaném zdrojovém kódu.

Obrázek 6.4: Zjednodušený modifikované třídy

třídní

59

diagram

postihující

zejména

6.4.2 Třída GraphControl Třída GraphControl je ze jmenného prostoru Netron.GraphLib.UI, který je pod jmenným prostorem Netron.GraphLib, což je assembly s funkcionalitou pro řízení grafů a dalších prvků, které se k tomuto vztahují. Třída rozšiřuje základní třídu ScrollableControl a chová se jako jakýsi kontejner objektů a její úlohou je také vlastnictví řízení nad vykreslováním těchto objektů. Co si pod tím můžeme představit? Tato třída obstarává funkcionalitu interakce uživatele s jednotlivými objekty grafu. Největší část celého kódu této třídy totiž zaujímají handlery pro události vyvolané operacemi s myší. My jsme však přes vlastnosti třídy GraphControl možnost pohybovat s vrcholy grafu deaktivovali. Spolu s touto možnosti jsme také deaktivovali ještě další operace. Jejich seznam je shrnut v následujících bodech: •

AllowAddConnection – umožňuje vytvoření nového propojení mezi dosud nepropojenými vrcholy

•

AllowAddShape – umožňuje přidávat do grafu další vrcholy

•

AllowDeleteShape – umožňuje odstranit existující vrcholy

•

AllowMoveShape zobrazovací ploše

–

umožňuje

s vrcholy

pohybovat

po

Abychom při vykreslování objektů grafu, které je implementováno v níže popsaných třídách, měli přehled o tom, který typ grafu dle vstupních dat byl zvolen, využili jsme rozhraní IGraphSite. Díky propojení přes toto rozhraní je možno ve třídě MainForm nastavit pomocí vlastnosti GraphType ve třídě GraphControl typ grafu. Díky tomu jsme zajistili, aby třídy starající se o vykreslování vrcholů grafu a spojení mezi těmito vrcholy měly informaci o typu grafu, podle kterého se řídí způsob vykreslení těchto objektů. Další vlastnosti, IGraphSite, jsou MaximumAllNodes.

které tato vlastnosti

třída implementuje z rozhraní MaximumConnectionsCount a

První vlastnost se stará o modifikaci atributu, který nese informaci o nejvyšším počtu spojení jednoho vrcholu s dalšími vrcholy. Uvedeme si příklad: vede-li z některého vrcholu grafu spojení na 5 dalších vrcholů a v grafu neexistuje žádný vrchol, který by měl spojení na šest a více dalších vrcholů, nastaví se pomocí této vlastnosti daný atribut na hodnotu 5.

60

Pomocí druhé vlastnosti se modifikuje atribut nesoucí informaci o nejvyšší hodnotě propojení mezi všemi vrcholy. Jinými slovy je to nejvyšší číslo, které nalezneme ve vstupní symetrické matici. K čemu vlastně slouží předchozí dvě vlastnosti? Dle specifikace mají být vrcholy různě velké a různě viditelné. Tyto vlastnosti nám slouží k tomu, abychom mohli vhodně vypočítat různé velikosti a viditelnosti pro každý uzel na základě aktuálních vstupních dat. Tato data způsobí, že ve výsledku budou mít atributy nastavované přes tyto vlastnosti pokaždé jinou hodnotu (ve stejné úloze – totožná vstupní data - však samozřejmě stejnou), a proto jsme si museli předem zvolit maximální hodnotu velikosti vrcholu a vlastnost MaximumConnectionsCount nám tak snadno pomůže při mapování hodnot ze vstupních dat na velikosti zobrazovaných vrcholů. Podobně je třeba namapovat ze vstupních dat i hodnoty viditelnost pro každý vrchol. Nemusíme sice vymýšlet maximální hodnotu alfa-kanálu, protože jeho hodnoty jsou v klasickém intervalu 0 – 255, ale mapování je stejně nutné provést, protože intervaly, ve kterých se pohybují hodnoty vstupních dat, budou v každé úloze jiné. Důležitými vlastnostmi, které tato třída implementuje také z rozhraní IGraphSite, jsou vlastnosti TopLimit a BottomLimit. V kapitole 6.4.1 jsme uvedli, že je uživateli umožněno vybrat jen určitý interval hladin v trojrozměrné reprezentaci symetrické matice. Interval se nastavuje v aplikaci pomocí dvou posuvníků a myšlenka pro realizaci této funkcionality byla taková, že první posuvník bude označovat horní mez intervalu z pravé strany a dolní posuvník bude označovat dolní mez intervalu z levé strany. Při pohybu posuvníků směrem k sobě se tedy bude interval zužovat. Nikdy však nedojde k překřížení hodnot mezí intervalů. Posuvníkem sice půjde posunout až na opačný konec, ale hodnoty obou mezí intervalu se zastaví na dvou nejbližších možných hodnotách. Popišme si algoritmus pro nastavení horní meze. Pro dolní mez bude postup analogický s otočenými operátory, vyměněnými položkami a indexy. V programu si uchováváme ve dvourozměrném poli hodnoty dolní a horní meze intervalu. Posunuje-li uživatel horním posuvníkem a je-li hodnota, na kterou ukazuje šipka posuvníku, větší než hodnota dolní meze, nastaví se do horní meze právě tato aktuální hodnota, na kterou ukazuje šipka. if (trackTop.Value > focusRange[0]) focusRange[1] = trackTop.Value;

Namapováním nové hodnoty meze na interval alfa-kanálu se pak nastaví patřičný atribut právě pomocí vlastnosti TopLimit. graphControl1.TopLimit = ((float)256 / (float)graphControl1.NodesCount) * (float)focusRange[1];

61

Posledními důležitými vlastnostmi, které tato třída implementuje z rozhraní IGraphSite, jsou vlastnosti MinLevel a MaxLevel. Čtenář jistě bude chtít najít spojitost s předchozími dvěma vlastnostmi, nicméně jejich význam je odlišný, i přestože opět ovlivňují vykreslování. Tyto dvě vlastnosti jsme zavedli pro účely namapování hodnot alfa-kanálu z dat představujících binární strom.

6.4.3 Třída Entity Entity je abstraktní třída (nemůže být instaciována) a tvoří základ pro vytvoření dalších specializovaných potomků. Těmi jsou třídy Connection, Shape a Connector. První dvě si více popíšeme v dalších kapitolách. Ve třídě jsme neprováděli žádné změny. Zmíníme se jen o tom, že tato třída popisuje základní atributy a metody společné pro všechny další její potomky včetně jejich metody Paint. Tato metoda je potom implementována ve třídách, které z ní dědí.

6.4.4 Třída Shape Třída Shape dědí ze třídy Entity a samotná je určena k tomu, aby z ní dědily další třídy, které už budou konkrétně představovat objekty zobrazované ve vykreslovací oblasti. Do této třídy jsme dopsali dvě důležité vlastnosti, které jsou tak trochu podobné vlastnostem MaximumConnectionsCount a MaximumAllNodes ve třídě GraphControl a uvedeme si, jak spolu souvisí. Jsou to vlastnosti ConnectionsCount a MaxINode. První vlastnost se stará o modifikaci atributu, který nese informaci o počtu spojení daného vrcholu s dalšími vrcholy. S vlastností MaximumConnectionsCount souvisí proto, že při vykreslování je potom snadné zjistit podíl na jeho hodnotě a spočítat tak velikost daného vrcholu. Pomocí druhé vlastnosti se modifikuje atribut nesoucí informaci o nejvyšší hodnotě propojení se všemi sousedními vrcholy. Jinými slovy je to nejvyšší číslo na daném řádku či sloupci vstupní symetrické matice. Vlastnost MaxINode souvisí s vlastností MaximumAllNodes proto, že při vykreslování je potom snadné zjistit podíl na jeho hodnotě z intervalu hodnot pro alfa-kanál a spočítat tak viditelnost daného vrcholu. Poslední vlastnost, kterou jsme do této třídy přidali, je vlastnost Level. Podobně jako vlastnost MaxINode i tato vlastnost pomáhá při vykreslování tak, že umožňuje zjistit podíl na hodnotě z intervalu hodnot pro alfa-kanál a spočítat tak viditelnost konkrétního vrcholu v binárním stromu.

62

6.4.5 Třída RoundNode Jak již z názvu vyplývá, jedná se o třídu reprezentující uzel grafu ve tvaru kruhu. Aplikace Graph Analysis volí pro vykreslování vrcholů grafu právě tuto třídu. Chceme-li tedy modifikovat vykreslování vrcholů grafu, musíme provést změny ve zdrojovém kódu právě této třídy. Třída je potomkem třídy Shape, ze které přebírá všechny její vlastnosti a metody a soustředí se na vykreslovací část objektu, který má představovat vrchol grafu. My jsme provedli přepsání zdrojového kódu v metodě Paint. Přepsání spočívalo na začátku v zavedení lokálních proměnných alphaSegment a sizeSegment. Hodnoty představují parametry, kterými se později násobí konkrétní hodnoty vlastností vrcholu. Do první proměnné se uloží podíl maximální námi zvolené hodnoty, o kterou se může zvětšit poloměr vrcholu, a vlastnosti MaximumConnectionsCount. sizeSegment = (float)20 / (float)this.mSite.MaximumConnectionsCount;

Získáme tak parametr, kterým se při výpočtu obdélníkové oblasti pro konkrétní vrchol násobí aktuální hodnota počtu spojení konkrétního vrcholu. float sizeSegConCount = sizeSegment * ConnectionsCount; r = new Rectangle ((int)(Rectangle.X - sizeSegConCount), (int)(Rectangle.Y - sizeSegConCount), (int)(Rectangle.Width + 1 + (2 * sizeSegConCount)), (int)(Rectangle.Height + 1 + (2 * sizeSegConCount)));

Do druhé proměnné se uloží podíl námi zvolené hodnoty alfa-kanálu, o kterou se může zvýšit hodnota alfa-kanálu daného vrcholu, a vlastnosti MaximumAllNodes. alphaSegment = (float)240 / (float)this.mSite.MaximumAllNodes;

My jsme zvolil hodnotu 240. Proč ne 255? Bylo by vhodné, kdyby i ty nejvzdálenější uzly byly aspoň trochu viditelné a proto jsme interval zúžili na 240 hodnot a potom při výpočtu viditelnosti se tento interval posune směrem k viditelné oblasti přičtením hodnoty 15. Původní interval pro alfakanál je tedy zúžen na hodnoty od 15 do 255. float alphaSegMaxINode = alphaSegment * MaxINode; g.FillEllipse(new LinearGradientBrush(r, Color.FromArgb(15 + (int)(alphaSegMaxINode), Color.Yellow), Color.FromArgb(15 + (int)(alphaSegMaxINode), Color.Brown), LinearGradientMode.ForwardDiagonal), r);

63

Pro nastavení viditelnosti textu je použita stejná technika jako pro viditelnost vrcholu. Popsali jsme si přímo dílčí algoritmy pro vykreslení vrcholů grafu. Ještě se musíme zmínit o způsobu vykreslení dle zvoleného intervalu v případě grafu založeném na symetrické matici. Díky informaci o typu vizualizovaného grafu si můžeme snadno zvolit alternativu zobrazení vrcholů na základě omezujícího intervalu. V sekvenci vykreslování pak stačí úplně na začátku zkontrolovat, zda-li se vrchol nachází uvnitř mezí intervalu. Jak se to provede? Logickým součinem podmínek dvou výrazů zjistíme, má-li se daný vrchol zobrazit nebo ne. Obě podmínky jen ověří, jestli se vypočítaná hodnota alfa-kanálu nachází uvnitř intervalu. Pozorný čtenář si všiml, že porovnáváme hodnoty z rozdílných rozsahů alfa-kanálu. Jeden končí na hodnotě 240 a druhý klasicky na hodnotě 255. pro správnost výsledku stačí ten z kratšího intervalu přizpůsobit hodnotě z intervalu druhého vynásobením podílu 255 / 240 což je rovno 1,0625. if (((alphaSegMaxINode * 1.0625) >= this.mSite.BottomLimit) && ((alphaSegMaxINode * 1.0625) <= this.mSite.TopLimit))

6.4.6 Třída Connection Spojení může existovat mezi dvěma různými vrcholy a pokud tomu tak je, vytvoří se instance třídy Connection. Tato třída podobně jako třída Shape má svého předchůdce v abstraktní třídě Entity. Z grafického hlediska totiž spojení mezi dvěma uzly není nic jiného než grafická entita, která má stejně důležité postavení na vykreslovacím panelu jako vrchol, i když je to jen čára. Pro potřeby naší vizualizace jsme museli do vlastností této třídy dopsat další položky. Přibyly vlastnosti FromMaxINode a ToMaxINode. Bylo třeba zajistit, abychom měli v této třídě informaci o obou vrcholech, jejichž spojení třída Connection zachycuje. Dle specifikace byl totiž požadavek na gradientní hrany, které budou napomáhat simulaci třetího rozměru. Jak by vypadaly čáry, které spojují vrcholy někde v pozadí, zobrazeny v plné viditelnosti? Bylo nutné mít informaci o viditelnosti obou spojovaných vrcholů a k tomu nám posloužily tyto vlastnosti. K podobnému účelu jsme zavedli i vlastnosti FromLevel a ToLevel. Tyto se využívají v případě vstupních dat v podobě binárního stromu.

6.4.7 Třída DefaultPainter Pro vykreslení spojení mezi dvěma vrcholy grafu vytvoří instance třídy Connection novou instanci třídy DefaultPainter. Tato třída se postará o vykreslení spojení metodou Paint. Její kód jsme upravili tak, abychom ve

64

výsledku získali gradientní hrany. Techniku pro výpočet viditelností jsme použili podobnou jako u vrcholů. Jedinou změnou bylo pouze zachování celého intervalu pro hodnoty alfa-kanálu, tedy interval hodnot 0 – 255. Nejjednodušším způsobem, jak vytvořit gradientní hranu, bylo vytvořit vlastní speciální štětec. Vytvořili jsme novou instanci třídy Pen s parametrem speciálního štětce a tloušťkou čáry. Specifický štětec je v našem případě odvozený z potomka abstraktní třídy Brush a nazývá se LinearGradientBrush. Různě vypadající výplně, jako jsou gradienty, vzory, textury, jdou aplikovat zpravidla jen na dvojrozměrné objekty. My jsme ovšem potřebovali aplikovat gradient na čáru. Tento derivát abstraktní třídy Brush umožňuje aplikovat lineární gradient i na takový objekt, jakým je čára. Výsledkem tak mohou být čáry s různými gradienty navozující dojem třetího rozměru díky tomu, že budou pozvolna jakoby ustupovat do pozadí.

6.4.8 Načtení symetrické matice Jak probíhá načtení dat symetrické matice a čeho je se třeba vyvarovat, si nyní popíšeme podrobněji v této kapitole. Aplikace předpokládá matici zadanou ve správném formátu, jaký je popsán v kapitole 6.3.1. Dodejme ještě pro úplnost, že prvky matice musí být celá nezáporná čísla a poslední řádek nesmí být prázdný. V opačném případě bude vyvolána výjimka. Pro načtení dat nám poslouží proud parametrem bude instance třídy FileStream.

StreamReader,

jehož

FileStream fs = new FileStream(openFileDialog.FileName, FileMode.Open); StreamReader sr = new StreamReader(fs);

Vytvoříme si instanci třídy String, do které bude vždy načítán jeden celý řádek matice. Poté vytvoříme pole znaků, do něhož uložíme jednotlivé znaky řetězce. String lineString = sr.ReadLine(); char[] lineCharacters = lineString.ToCharArray();

Nyní potřebujeme zjistit, jakého rozměru je vlastně načítána matice. K tomu nám poslouží cyklus, ve kterém budeme zjišťovat ze znaků prvního řádku matice, zda-li je načtený znak mezera a pokud ano zvýší se počítadlo. if (lineCharacters[i].CompareTo(' ') == 0) matrixDimension++;

Na základě zjištěného rozměru můžeme vytvořit pole, které bude představovat symetrickou matici. Projdeme první řádek ještě jednou za účelem vytvoření jednotlivých prvků matice. Pro šetření paměti si pro tyto

65

účely vytvoříme instanci třídy StringBuilder. Ta nám bude sloužit pro poskládání jednoho prvku matice z konkrétního řádku a sloupce matice a to tak, že opět budeme zjišťovat, zda-li není znak mezera. Pokud není, znak stále patří k prvku matice a připojí se k instanci StringBuilderu. sb.Append(lineCharacters[i]); Po přečtení všech znaků řádků se načte další řádek. Ten se opět uloží do pole znaků a celý postup se opakuje. Jakmile je celá matice načtena, může dojít k vytvoření vrcholů a propojení grafu na základě načtených dat.

6.4.9 Načtení binárního stromu Jak probíhá načtení XML dokumentu a zobrazení uložených dat, si popíšeme v této kapitole. Z povahy vstupních dat vyplývá, že pro načtení dat bude nutné použít rekurzi. Pro přístup do hierarchické struktury XML dokumentů jsme zvolili objektový model DOM. V případě použití tohoto přístupu nám vznikne v paměti počítače reprezentace struktury daného XML dokumentu. To nám umožňuje s dokumentem snadno manipulovat, protože je nám umožněno libovolně přistupovat k libovolné části XML dokumentu. Vytvoříme si instanci třídy XmlDocument a pomocí přetížené metody Load jednoduše načteme celou strukturu XML dokumentu. XmlDocument doc = new XmlDocument(); doc.Load(openFileDialog.FileName);

Nyní rovnou zavoláme rekurzivní metodu getTreeParams s parametrem kořenového elementu, která nám zjistí výšku stromu, minimální hodnotu parametru Level a maximální hodnotu parametru Level. double[] result = getTreeParams(doc.DocumentElement);

Tyto údaje potřebujeme znát ještě před vytvořením samotného stromu, který budeme vizualizovat. Nyní můžeme zavolat rekurzivní metodu createTreeFromXmlDoc pro vytvoření XML stromu. Jejími parametry jsou aktuální uzel, několik parametrů pro vypočítání pozice vrcholu stromu v zobrazovací oblasti a hodnota Level rodičovského uzlu. createTreeFromXmlDoc(doc.DocumentElement, 30, this.graphControl1.Width - 30, 30, (int) step_y, 0);

Při průchodu rekurzivní metodou se rovnou vytváří graf stromu s vrcholy a hranami. Vytváření instancí třídy Shape během průchodu a

66

jejich přidávání metodou AddShape bylo bezproblémové, nicméně při vytváření instancí třídy Connection jsme narazili na potíže a bylo nutné najít vhodné řešení, protože vykreslovací algoritmy požadovaly hned od začátku hodnotu alfa-kanálu ze správného intervalu. To je zcela pochopitelné a proto jsme metodu AddConnection přetížili a vytvořili její variantu se čtyřmi parametry, z nichž poslední dva nesou informaci o hodnotě Level obou vrcholů, které vstupují do spojení, a tím jsme zajistili namapování alfa-kanálu do správného intervalu.

67

7. Testování 7.1

Požadavky na systém

Aplikace byla vyvíjena a testována na desktopovém počítači s touto hardwarovou konfigurací a softwarovým vybavením: •

procesor Intel Celeron D 2,4 GHz

•

operační paměť 1 GB (2 x 512 MB)

•

grafická karta RADEON 9600 PRO 256 MB

•

dvoumonitorové řešení: 1280 x 1024 a 1680 x 1050 pixelů

•

operační systém Microsoft Windows XP Professional SP2

•

Microsoft Visual Studio 2005

Systém nebyl testován na jiné hardwarové konfiguraci ani jiném operačním systému. Vzhledem k velkému množství výpočtů v plovoucí desetinné čárce doporučujeme použití této nebo výkonnější konfigurace.

7.2

Výsledky testů

Aplikace, kterou jsme popsali v kapitole 6, slouží k vizualizaci symetrických matic a binárních stromů. Během vývoje bylo použito množství vstupních dat, která byla náhodně vygenerována i samotným programem. V případě symetrických matic byly použity matice o velikostech, které dosahovaly i tisíc objektů. Nejčastějším vzorkem byly matice o stovce objektů. Toto množství jsme používali proto, že bylo snadné a rychlé pozorovat výsledky práce, avšak v oblasti IR se v praxi samozřejmě setkáváme i se sta tisíci objekty. Při inicializaci vizualizace je patrné zpoždění rostoucí s množstvím vizualizovaných objektů. Vizualizace symetrických matic má dále možnost omezit se na určitý interval hladin a vizualizovat jen vybrané části. Během změny mezí intervalu je zpoždění s menším počtem objektů nepostřehnutelné a při větším počtu objektů již opět patrné. Vygenerování symetrické matice je uskutečněno v zanedbatelném čase. Tabulka na následující straně zachycuje velikost souboru pro určitý počet objektů a časy pro uvedené operace. Vždy samozřejmě závisí na

68

aktuálním počtu vrcholů a hran mezi vrcholy. Malé množství hran pro matici se stovkami objektů bude generovat kratší časy. Naopak budou-li objekty propojeny velkým množstvím hran, časy pro vizualizační operace rapidně narostou.

počet objektů 50 100 200 500 1000

čas potřebný k čas pro velikost souboru vygenerování inicializaci (kB) matice (s) vizualizace (s) 5 20 79 489 1995

< 0,1 < 0,2 0,7 - 0,8

< 0,1 3 11

čas potřebný ke změně omezení (s) < 0,1 <1 <5

Na následujících obrázcích jsou ilustrovány konkrétní úlohy. Ukážeme si, jak vypadá omezení intervalu a uvedeme si také úlohy pro různý počet objektů.

Obrázek 7.1: Vizualizace symetrické matice čítající sto objektů bez omezení (0-100)

69

Obrázek 7.2: Vizualizace předchozí úlohy s omezením 8-92

Obrázek 7.3: Vizualizace předchozí úlohy s omezením 90-100

70

Obrázek 7.4: Vizualizace symetrické matice čítající 50 objektů

Obrázek 7.5: Vizualizace symetrické matice čítající 200 objektů

71

Obrázek 7.6: Vizualizace symetrické matice čítající 500 objektů

Obrázek 7.7: Vizualizace předchozí úlohy s omezením 255-500

72

Obrázek 7.8: Vizualizace symetrické matice čítající 1000 objektů

Obrázek 7.9: Vizualizace předchozí úlohy s omezením 963-1000

73

8. Závěr V této prácí jsme se zaměřili na možnosti vizualizace výsledků vyhledávání při dolování dat z textu. Popsali jsme na základě dohledaných tištěných dokumentů a zdrojů v elektronické podobě různé přístupy vizualizace a snažili jsme se pokrýt rozsah od základních graficky nenáročných prezentací až po techniky na vysoké úrovní vizualizace zobrazující komplexní soubory dat. Popsali jsme výhody a úskalí jednotlivých postupů při vizualizaci konkrétními metodami. Na příkladech testů jsme ukázali, jak může vypadat vizualizace symetrické matice. Demonstrovali jsme aplikaci restrikce zobrazení na konkrétní množinu vstupních dat. Přesvědčili jsme se, že vizualizace obrovského množství objektů s sebou nese potřebu vysokého výpočetního výkonu a zjistili jsme, že ne vždy je vhodné vizualizovat celý soubor vstupních dat. Našim úkolem bylo provést vizualizaci dvou typů vstupních dat, kterými jsou symetrické matice a binární stromy. Zabývali jsme se pouze technickým provedením reprezentace grafu jako výstupu těchto vstupních dat a pro naše testy a lepší přehlednost jsme použili v grafech vrcholy označené jen čísly. Pro další vývoj této aplikace je možné přes vlastnosti dodat textové popisy k zobrazovaným vrcholům. Podle potřeby lze povolit pomocí vlastností také kliknutí na jednotlivé vrcholy a jejich následné posouvání po zobrazovací oblasti. Tato diplomová práce se také snaží demonstrovat poznatky jejího autora týkající se vývoje aplikace v prostředí .NET Framework a programování v moderním objektově orientovaném jazyce C#.

74

Literatura [1]

Ricardo Baeza-Yates and Berthier Ribeiro-Neto: Modern Information Retrieval. 1999, ISBN 020139829X, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA

[2]

C. J. van Rijsbergen: Information Retrieval (second ed.). Department of Computer Science, University of Glasgow, London, Butterworths, 1979 http://www.dcs.gla.ac.uk/Keith/Preface.html

[3]

Shneiderman, B. Designing the User Interface: Strategies for Effective Human-Computer Interaction (3 ed.). Addison-Wesley Pub Co. 1997

[4]

Teuvo Kohonen: Self-Organizing Maps. Springer Series in Information Sciences. 3rd edition, 2001.

[5]

Weili Wu, Hui Xiong and Shashi Shekhar (Eds.): Clustering and Information Retrieval. 2004, ISBN 1-4020-7682-7, Kluwer Academic Publishers

[6]

Ronen Feldman, Willi Klösgen, Amir Zilberstein: Visualization Techniques to Explore Data Mining Results for Document Collections. 2006

[7]

Ronen Feldman, James Sanger: The Text Mining Handbook. 2007, ISBN-13 978-0-521-83657-9, Cambridge Press

[8]

Ronen Feldman, Yizhar Regev, Michal Finkelstein-Landau, Eyal Hurvitz & Boris Kogan: Mining the biomedical literature using semantic analysis and natural language processing techniques. Biosilico 1(2):69-80 (2003).

[9]

Katy Börner, Chaomei Chen, Kevin Boyack: Visualizing Knowledge Domains. Annual Review of Information Science & Technology, Volume 37, 2003.

[10]

Jörg Ontrup, Helge Ritter: Hyperbolic Self-Organizing Maps for Semantic Navigation. 2001

[11]

Ricardo A. Cava, Paulo R. G. Luzzardi, Carla M. D. S. Freitas: The Bifocal Tree: a Technique for the Visualization of Hierarchical Information Structures. 2002

[12]

Hans-Christian Jetter: Hyperbolic Treebrowser – der hyperbolische Browser für hierarchische Daten. 2005

[13]

Ivo Vondrák: Umělá inteligence a neuronové sítě. Ostrava 2002, ISBN 80-7078-949-2.

75

[14]

Jan Martinovič: Information Retrieval a shlukování metodou WEBSOM. Department of Computer Science, VŠB - Technical University of Ostrava. 2005

[15]

Pokorný J., Snášel V., Húsek D.: Dokumentografické informacní systémy. Karolinum, Skriptum MFF UK Praha, 1998

[16]

Pavel Neuwirth: Vyhledávání na internetu. Diplomová práce, VŠB – TUO, Ostrava, 2002

[17]

Jaromír Pežga: Vyhledávání na internetu. Dilpomová práce, VŠB – TUO, Ostrava, 2002

[18]

Simon Robinson, K. Scott Allen, Ollie Cornes, Jay Glynn, Zach Greenvoss, Burton Harvey, Christian Nagel, Morgan Skinner, Karli Watson: C# Programujeme profesionálně. Computer Press, 2003

[19]

Dalibor Kačmář: Programujeme .NET aplikace ve Visual Studiu .NET. Computer Press, 2001

[20]

Chris Sells: C# a WinForms – programování formulářů Windows. Zoner Press, 2005

[21]

Elliotte Rusty Harold & W. Scott Means: XML v kostce. Computer Press, 2002

76

A. CD-ROM Obsah CD-ROM •

Text diplomové práce ve formátu PDF

•

Obrázky použité v tomto textu v původním rozlišení

•

Zdrojové kódy

•

Spustitelná aplikace

•

Testovací data

77