ZÍSKÁVÁNÍ ZNALOSTÍ A ANALÝZA RIZIK Z DAT HRY INGRESS GAINING KNOWLEDGE AND RISK ANALYSIS FROM THE DATA OF THE INGRESS GAME

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY

ÚSTAV SOUDNÍHO INŽENÝRSTVÍ ÚSTAV SOUDNÍHO INŽENÝRSTVÍ INSTITUTE OF FORENSIC ENGINEERING INSTITUTE OF FORENSIC ENGINEERING

ZÍSKÁVÁNÍ ZNALOSTÍ A ANALÝZA RIZIK Z DAT HRY INGRESS GAINING KNOWLEDGE AND RISK ANALYSIS FROM THE DATA OF THE INGRESS GAME

DIPLOMOVÁ PRÁCE MASTER’S THESIS

AUTOR PRÁCE

Bc. MARTIN VAŘÁK

AUTHOR

VEDOUCÍ PRÁCE SUPERVISOR

BRNO 2015

Ing. VLADIMÍR BÁRTÍK, Ph.D.

Vysoké učení technické v Brně, Ústav soudního inženýrství Ústav soudního inženýrství Akademický rok: 2014/2015

ZADÁNÍ DIPLOMOVÉ PRÁCE student(ka): Bc. Martin Vařák který/která studuje v magisterském navazujícím studijním programu obor: Řízení rizik v informačních systémech (3901T047) Ředitel ústavu Vám v souladu se zákonem č.111/1998 o vysokých školách a se Studijním a zkušebním řádem VUT v Brně určuje následující téma diplomové práce: Získávání znalostí a analýza rizik z dat hry Ingress v anglickém jazyce: Knowledge Discovery and Risk Analysis in Data from the Ingress Game Stručná charakteristika problematiky úkolu: Technická zpráva diplomové práce musí obsahovat formulaci cíle, charakteristiku současného stavu, teoretická a odborná východiska řešených problémů a specifikaci etap, které byly vyřešeny v rámci semestrálního projektu (30 až 40% celkového rozsahu technické zprávy). Student odevzdá v jednom výtisku technickou zprávu a v elektronické podobě zdrojový text technické zprávy, úplnou programovou dokumentaci a zdrojové texty programů. Informace v elektronické podobě budou uloženy na standardním nepřepisovatelném paměťovém médiu (CD-R, DVD-R, apod.), které bude vloženo do písemné zprávy tak, aby nemohlo dojít k jeho ztrátě při běžné manipulaci. Podrobné závazné pokyny pro vypracování diplomové práce naleznete na adrese http://www.fit.vutbr.cz/info/szz/. Cíle diplomové práce: 1. Seznamte se s problematikou získávání znalostí z databází. 2. Detailně prostudujte vlastnosti dat z augmented reality hry Ingress a zvažte možnosti využití získávání znalostí pro analýzu míst s vysokou koncentrací portálů, kde je vysoké riziko obsazení portálu. 3. Po dohodě s vedoucím zvolte metodu získávání znalostí, která by byla pro tento typ dat vhodná. Tuto metodu poté prostudujte podrobněji. 4. Zvolenou metodu implementujte. 5. Proveďte experimenty s vhodně zvoleným vzorkem dat a vyhodnoťte úspěšnost. 6. Zhodnoťte dosažené výsledky a další možné pokračování v projektu.

Seznam odborné literatury: Han, J., Kamber, M.: Data Mining - Concepts and Techniques, 2nd Edition. Morgan Kaufmann Publishers, 2006.

Vedoucí diplomové práce: doc. Ing. Vladimír Adamec, CSc. Termín odevzdání diplomové práce je stanoven časovým plánem akademického roku 2014/2015. V Brně, dne 24.10.2014 L.S.

_______________________________ doc. Ing. Aleš Vémola, Ph.D. Ředitel vysokoškolského ústavu

Abstrakt Tato diplomová práce popisuje vyhledávání rizikových shluků portálů ve hře Ingress pomocí metod data miningu. Práce popisuje pozadí zpracovávané problematiky a jednotlivé metody a experimenty použité k vyhledávání těchto informací. Summary This thesis describes searching for high-risk clusters of portals in the Ingress game by using data mining techniques. The work contains background for descibed problematics and methods and experiments used to search for theese information. Klíčová slova Dolování z dat, data mining, klasifikace, riziko, databáze, shluk, Ingress Keywords Data mining, clasification, risk, database, cluster, Ingress

VAŘÁK, M.Získávání znalostí a analýza rizik z dat hry Ingress. Brno: Vysoké učení technické v Brně, Ústav soudního inženýrství, 2015. 64 s. Vedoucí Ing. Vladimír Bártík, Ph.D.

˘ ˘ Prohlašuji, Ĺľe jsem tuto diplomovou prAˇci vypracoval samostatnÄ> pod vedenAm ˘ ˘ ˘ pana Ing. VladimAra BAˇrtAka, Ph.D. Bc. Martin Vařák

˘ BAˇrt ˘ Akovi, ˘ ˘ ˘ pĹTM i vyc vedenA DÄ>kuji panu Ing. VladimAru Ph.D. za odbornA ˘ A ˘ tA ˘ to ˘ ˘ ˘ poskytl. c prAˇce c mi k nA pracovAˇn a za podnÄ>ty, kterA Bc. Martin Vařák

OBSAH

Obsah 1 Úvod

3

2 Augmented reality hra Ingress 2.1 Co to znamená Augmented Reality 2.2 Ingress . . . . . . . . . . . . . . . . 2.2.1 Příběh . . . . . . . . . . . . 2.2.2 Popis hry . . . . . . . . . . 2.3 Popis dat . . . . . . . . . . . . . . 2.3.1 Formát získavaných dat . . 2.3.2 Sběr dat . . . . . . . . . . . 2.4 Popis řešeného problému . . . . . . 2.4.1 Real-time statistická analýza 2.4.2 Vyhledávání farem . . . . . 3 Databázové systémy 3.1 PostgreSQL . . . . . . . . . . . 3.2 Oracle . . . . . . . . . . . . . . 3.3 Microsoft SQL Server . . . . . . 3.4 Firebird . . . . . . . . . . . . . 3.5 MySQL . . . . . . . . . . . . . 3.6 SQLite . . . . . . . . . . . . . . 3.7 Couchbase . . . . . . . . . . . . 3.8 MongoDB . . . . . . . . . . . . 3.9 Vyhodnocení a výběr databáze

. . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

4 Práce s daty 4.1 Použité technologie . . . . . . . . . . . . . . . . . . . . . 4.1.1 Formát JSON . . . . . . . . . . . . . . . . . . . . 4.1.2 Databáze MySQL . . . . . . . . . . . . . . . . . . 4.1.3 Nerelační databáze MongoDB . . . . . . . . . . . 4.1.4 Skriptovací jazyk PHP . . . . . . . . . . . . . . . 4.2 Čištění a transformace zdrojových dat . . . . . . . . . . 4.2.1 Příprava pomocných dat pro statistickou analýzu 4.2.2 Odstranění nevhodných dat . . . . . . . . . . . . 4.2.3 Úprava dat do vhodného formátu . . . . . . . . . 5 Analýza získaných dat 5.1 Kritéria pro úspěšnost analýzy . . . . . 5.2 Metody klasifikace dat . . . . . . . . . 5.2.1 Rozhodovací stromy . . . . . . 5.2.2 Systém rozhodovacích pravidel . 1

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . .

. . . . . . . . . .

4 4 6 6 6 10 11 11 12 12 12

. . . . . . . . .

14 14 15 15 16 17 18 18 19 19

. . . . . . . . .

21 21 21 23 23 24 24 25 26 27

. . . .

29 29 30 30 31

OBSAH

5.3

5.4 5.5 5.6

5.2.3 Statistické metody . . . . . . . . . 5.2.4 Neuronové sítě . . . . . . . . . . . 5.2.5 Kombinované či odvozené techniky Metody shlukování dat . . . . . . . . . . . 5.3.1 Metoda K-means . . . . . . . . . . 5.3.2 Metoda K-medoids . . . . . . . . . 5.3.3 Hierarchické metody . . . . . . . . 5.3.4 Metoda DBSCAN . . . . . . . . . . Volba vhodné metody . . . . . . . . . . . Vyhledávání shluků . . . . . . . . . . . . . Výsledky statistické analýzy . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

6 Riziková analýza portálů 6.1 Hodnocení portálu z hlediska vlastnictví . . . . . . . 6.1.1 První časový faktor – doba jednoho burnoutu 6.1.2 Druhý časový faktor – Interval hackování . . . 6.1.3 Faktor jednoduchosti odhalení . . . . . . . . . 7 Implementace 7.1 Získávání dat . . . . . . . . . . 7.2 Předzpracování dat pro analýzu 7.2.1 Statistická analýza . . . 7.3 Vyhledávání shluků . . . . . . . 7.4 Grafické znázornění výsledků . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . .

32 33 34 35 36 38 38 39 40 42 42

. . . .

45 45 46 46 47

. . . . .

48 48 50 50 51 52

8 Vyhodnocení experimentu 55 8.1 Vyhodnocení kritérií analýzy . . . . . . . . . . . . . . . . . . . . . . . . . . 55 8.2 Úspěšnost analýzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 8.2.1 Experiment s maximální vzdáleností portálů ve shluku . . . . . . . 56 9 Možnosti dalšího rozšíření

57

10 Závěr

58

2

1. Úvod Tato diplomová práce se zabývá dolováním znalostí z dat dosažených v průběhu augmented reality hry Ingress na území města Brna. Cílem je vytvořit postupy pro zpracování a analýzu dat tak, aby bylo možno systematicky vyhledávat rizikové shluky portálů a na ty zaměřit pozornost. Vyhledané shluky portálů by měly být zveřejněny pro obě skupiny hráčů. Pokud by byly výsledky mé práce zvěřejněny pouze pro jednu skupinu, hra by byla nefér. Dolování dat představuje proces výběru, prohledávání a modelování ve velkých objemech dat. Provádí se za účelem získání neznámých vztahů z rozsáhlých databází s cílem těchto informací využít. Obecně při dolování dat platí zásada nalézt a poskytovat přehledné informace pro následné rozhodování. Typické využití je v obchodním procesu, zejména při zpracování databází zákazníků k oslovení cílových skupin. Dalším častým využitím je vyhledávání rizikových případů v pojišťovnictví, medicíně, meteorologii, telekomunikaci, atd. Druhá kapitola čtenáře seznamuje s problematikou augmented reality hry Ingress a tím mu dává povědomí o pozadí celé práce. Je zde také diskutován formát získaných vstupních dat. Třetí kapitola popíše vhodné technologie pro práci s daty. Dále se v ní diskutuje o formě předzpracování a čištění dat do takové podoby, aby byla vhodná k analýze. Čtvrtá a pátá kapitola se pak obecně zabývá analýzou získaných dat. Jsou zde popsány metody získávání znalostí z databází a diskutuje se výběr vhodné metody. Další kapitoly jsou zaměřeny na implementaci zpracované metody procesu dolování dat a na vyhodnocení experimentu. V závěru se věnuji zhodnocení dosažených výsledků a snažím se nastínit budoucí experimenty, které by mohly být prováděny za účelem dalšího pokračování projektu.

3

2. Augmented reality hra Ingress V této kapitole bych se chtěl věnovat problematice formátu Augmented reality, popisu hry Ingress a popisu získaných dat. Dále se zaměřím na rozčlenění typů informací, které mohu z dat opatřit. Popíšu, k čemu budou očištěná data následně využívána.

2.1. Co to znamená Augmented Reality Augmented Reality (česky rozšířená nebo také posílená realita) je označení, které se dnes používá pro obraz reálného světa, který je následně doplněn (rozšířen) o další informace, obvykle generované pomocí počítače (případně o spojení několika obrazů reálného světa z vícero různých zdrojů). Z uvedené charakteristiky by mohlo čtenáře napadnout, že se jedná pouze o vizuální záležitost, avšak i přesto, že vizuální pojetí je jedno z nejčastějších, rozhodně není jediné. Stejným způsobem jsou uživateli dodávány rozšířené sluchové či hmatové vjemy (bohužel, dnes jen na velmi omezené úrovni). V současné době je věnována velká pozornost vývoji zařízení pro rozšíření možností, jak dodávat uživateli další vnímání. Lze očekávat, že v nejbližších letech vznikne nový trh s multimediálními produkty, které umožňují propojení reality s rozšířenými digitálními prvky. To jistě přinese celou řadu pozitivních a negativních důsledků. Mezi pozitivní důsledky bych podle mého názoru zařadil variabilitu dostupných forem bydlení a odívání „na míruÿ pro každého. Mezi negativní důsledky by jistě mnoho z nás začlenilo čím dál větší odcizení mezi lidmi, které vzniká nedostatkem přímých sociálních kontaktů. Z tohoto popisu logicky vyplývá, že Augmented Reality je jakýmsi mezistupněm mezi skutečnou a virtuální realitou. Hra se snaží spojit to nejlepší z obou přístupů. V příštích letech se jistě bude rozvíjet široká diskuse na téma, co znamená „to nejlepšíÿ. Z mého pohledu budou mechanismy zajištění bezpečnosti sdílených údajů ve virtuálním světě velmi důležité. Dovedu si představit, že množství dat získaných o každém člověku na planetě, bude nadále velmi rychle narůstat. S rozšířením internetu, vyhledá-

4

2.1. CO TO ZNAMENÁ AUGMENTED REALITY vačů, internetových obchodů, platebních systémů a mobilních telefonů je zřejmé, že o každém z nás je evidována celá řada informací. Většina lidí si stále ještě neuvědomuje, co všechno o sobě nevědomky publikují. Nebráníme se tomu, že moderní technologie shromažďují a ukládají citlivé údaje, i když tušíme přímou možnost zneužití. Neřešíme, kdo má k těmto informacím přístup, protože používání moderních technologií je tak pohodlné. Vítám, že již probíhá diskuse o tom, co je ještě etické, která data by o nás měla být shromažďována, a jak je zajistit proti zneužití. V současné době metody dolování dat hrají hlavní úlohu ve zpracování cílených údajů. Do budoucna je možné předpokládat, že se tento obor bude dále bouřlivě rozvíjet. Rovněž předpokládám, že se budou dále vyvíjet i technologie zabezpečující soubory dat proti zneužití. V dnešní době často využíváme mobilní telefon (smartphone) a tablet pro snímání reality. Je to možné díky jejich vysoké rozšířenosti a díky funkcionalitě, která poskytuje poměrně širokou škálu vstupních informací (audio, video, GPS lokace, zrychlení, do jisté míry pak i teplota). I zde je možné očekávat rychlý vývoj. Velké uplatnění Augmented Reality je možno nalézt například v oblasti navigačních systémů, kdy lze navigační údaje a mapu promítat řidiči přímo na čelní sklo takovým způsobem, že nemusí spouštět oči z cesty, a přitom jsou údaje velmi dobře viditelné. Velmi zajímavým se také jeví využití pro různé turistické průvodce. Obrovský potenciál má využití Augmented Reality v oboru stavebnictví a architektury, kdy je možné promítat virtuální stavbu přímo do reálné krajiny a poskytnout tak výrazně lepší představu o tom, jak výsledná buduva zapadne do okolí. V poslední době je velmi diskutované zařízení Google Glass, které s sebou nese potenciál rozšíření posílené reality v nebývalé míře a jednoduchosti pro široké masy uživatelů. I zde je možné sledovat dva odlišné názory na toto zařízení. U technicky orientovaných uživatelů vidíme pozitivní reakce. Negativní reakce sledujeme u lidí, kteří si velmi cení svého soukromí.

5

2.2. INGRESS

2.2. Ingress 2.2.1. Příběh Vlastní hra je koncipována na základě následujícího scénáře [15]: Jako důsledek experimentu s vysokoenergetickými částicemi ve švýcarském CERNu vznikla kaskáda událostí, která měla za následek celosvětový výskyt takzvané exotické hmoty (Exotic Matter, XM). Jak bylo později zjištěno, tato hmota se nachází v úzkém vztahu s cizí rasou Shapers (tvůrci), jejíž plány s lidstvem jsou nám zatím neznámé. Je však jasné, že k ovlivňování lidstva již dochází po dlouhé věky. Největší koncentrace XM se vyskytuje okolo soch, kostelů, monumentů, památek a jiných zajímavých, veřejně dostupných míst a uměleckých děl. Na těchto místech pak byly později objeveny portály, které kromě masivní produkce (nebo přenosu) exotické hmoty také dovolily její manipulaci. Tyto zvláštní úkazy začaly přitahovat dvě frakce, které jsou ve vzájemné neshodě, přerůstající až v otevřené nepřátelství. Jedná se o skupinu Osvícených (Enlightened) a skupinu Odporu (Resistance). Osvícení jsou frakcí, která sympatizuje s bytostmi známými jako Shapers a snaží se všemožně pomáhat jejich působení na lidstvo. Enlightened jsou frakcí, která věří, že Shapers jsou schopni lidstvu přinést osvícení, pomocí kterého se bude schopno povznést na novou úroveň bytí. Na druhé straně je Resistance, frakce, která je veskrze skeptická k veškerým motivům Shapers. Vynakládá veškeré jí dostupné prostředky na zabránění jejich vlivu na Zemi a lidstvo. Některým může připadat, že Odpor brání pokroku, avšak oni sami pevně věří, že vše, co dělají, je v nejlepším zájmu lidstva.

2.2.2. Popis hry Ve hře se vyskytují dvě vzájemně soupeřící frakce (Enlightened a Resistance), které, jak již bylo napsáno výše, sledují vlastní cíle ve využití Exotic Matter a jejího vlivu na

6

2.2. INGRESS lidskou mysl. Základním stavebním kamenem celé hry jsou takzvané portály. Portál je místo (obvykle kulturní památka, význačná budova, umělecké dílo nebo místo se silným spirituálním nábojem), přes které se do našeho světa dostává XM. Každý portál může být napájen až osmi rezonátory, což jsou jakési „baterkyÿ, které napájí daný portál a umožňují mu jeho existenci. Různé úrovně rezonátorů pak poskytují portálu různou sílu. Existující portál lze takzvaně hackovat. Tuto akci může provést libovolný agent na portálu kterékoliv strany, ovšem pouze za předpokladu, že má ve svém scanneru dostatečnou zásobu XM. Obecně se touto akcí získávají předměty potřebné k další hře, hlavně pak klíče. Úroveň získaných předmětů (v případech, kdy se aplikuje) je závislá na úrovni jak portálu, tak agenta. Platí zde, že hack dává předměty v rozsahu dvou úrovní, a to z nižší úrovně agenta nebo pravděpodobněji z vyšší úrovně portálu. Hack lze provést pouze čtyřikrát během čtyř hodin vždy s alespoň pětiminutovým odstupem mezi jednotlivými hacky bez posílení portálu speciálním vybavením, které je poměrně vzácné. Modifikace, které mění tyto limity nejsou pro předmět, který tato práce zkoumá, příliš podstatné, neboť potenciál jejich využití zde bude vyhodnocen jiným způsobem. Pomocí klíče zvoleného portálu lze provádět několik akcí, z nichž ty nejdůležitější pro řešení daného problému jsou popsány níže. Vlastnictví portálu lze získat jen tak, že agent dané frakce fyzicky dorazí na místo, na kterém se portál nachází a obsadí jej. Tento proces pak probíhá ve dvou krocích. Nejprve je třeba u nepřátelského portálu zbořit jeho rezonátory, čímž se portál stane neaktivním a je plně připraven na obsazení. Takovýto portál je možno posléze obsadit vlastní sadou rezonátorů. Úroveň portálu se počítá jako aritmetický průměr úrovní všech obsazených rezonátorů, kde se ale prázdný slot počítá jako rezonátor s nulovou úrovní. Pro osazování portálu rezonátory platí určitá omezení, a to podle úrovně osazovaných rezonátorů. Pro předmět této práce je však podstatná pouze skutečnost, že rezonátor dvou nejvyšších úrovní (sedmé a osmé) může každý jednotlivý agent osadit pouze jeden. Proto, aby se daly efektivně stavět farmy portálů sedmé respektive osmé úrovně, je třeba,

7

2.2. INGRESS

Obrázek 2.1: Screenshot ze hry Ingress s výsledkem hacku aby se na jednom místě sešli tři až osm hráčů osmé úrovně. To již vyžaduje jistou dávku koordinace. Každý z rezonátorů zároveň dodává portálu určité množství energie. Ta mimo jiné určuje, jak dlouho bude portál schopen odolávat nepřátelským útokům a jak silně se jim je schopen bránit. Tato energie však klesá každých 24 hodin o patnáct procent svého maxima. Portál, o který by se nikdo nestaral, by se tedy stal neutrálním sám o sobě během jediného týdne. Aby bylo možné portál držet delší dobu, je třeba tuto energii dobíjet. To lze učinit buď vzdáleně pomocí klíče, nebo přímo na místě u portálu.

8

2.2. INGRESS Pokud frakce vlastní dva portály, které jsou plně osazeny rezonátory a agent vlastní alespoň jeden klíč k jednomu z těchto portálů, je možné tyto dva portály vzájemně propojit. Spojení (link ) dvou portálů lze provést jedině v případě, že jejich spojnici nekříží žádné jiné spojení. Dalším omezením je, že se ani jeden z portálů nesmí nacházet uvnitř existujícího pole (může však být jeho hraničním bodem). Pomocí popsaného propojování portálů se následně tvoří pole (field ). Právě pole jsou výsledkem základní snahy obou znepřátelených frakcí. Pomocí nich lze ovlivňovat myšlení obyčejných lidí, kteří se pod ním nacházejí, a nasměrovat jejich smýšlení k ideologii dané frakce. Pole se vytvoří tak, že se spolu vzájemně propojí tři portály, které tím vytvoří trojúhelník. Pole se mohou vzájemně překrývat tak, že menší z nich je plně překryto polem větším (nikdy se však ze zjevného důvodu nemohou křížit). Pro účely této práce je také potřeba popsat záměr a průběh stavby takzvané farmy. Farma je uskupení portálů, které jsou relativně blízko sebe, lze mezi nimi pohodlně přecházet a optimálně jsou umístěny v částečně odlehlé oblasti. Důvodem stavby tohoto uskupení je získat vybavení, které je samotným agentům obtížně dostupné z důvodu popsaného výše.

Obrázek 2.2: Screenshot z webového rozhraní Ingress Intel

9

2.3. POPIS DAT

Obrázek 2.3: Detail farmy Brno-Žabovřesky Tato hra spojuje několik technologií. V prvé řadě je zde uplatněna typická soutěž (boj) o nějaký cíl (portál, předměty). Dále je zde uplatněna netypická potřeba skutečné fyzické aktivity. Účastníci hry musí být fyzicky přítomni u daného portálu (někteří nachodí během jednoho dne i deset kilomentrů). Také je zde zužitkován potenciál historických budov a památek. V neposlední řadě je inspirující nutnost fyzického setkávání se účastníků hry. Aby byli úspěšní, musí se domluvit a setkat se například u konkrétního kostela. To vše zastřešuje tato moderní počítačová hra, která je postavena na využití moderních technologií (telefonech či tabletech s dostatečným výpočetním výkonem a trvalým internetovým a GPS připojením).

2.3. Popis dat Data, která budou v rámci tohoto tématu zpracována a analyzována, pocházejí z webového přehledu o stavu hry. Přehled je poskytován autory hry a všichni hráči ho mají k dispozici. Tato otevřenost však není typická a je možné očekávat, že do budocna již ne-

10

2.3. POPIS DAT budou data veřejně dostupná ve stávajícím rozsahu. Každá zpráva může znamenat jednu z následujících událostí: • Osazení portálu rezonátorem • Vytvoření linku mezi dvěma portály • Vytvoření pole • Obsazení portálu • Zničení rezonátoru • Zničení linku mezi dvěma portály • Zničení pole • Komunikační zpráva mezi hráči • Upadnutí linku mezi dvěma portály z důvodu nedostatečné energie portálu • Osobní zprávy relevantní pouze pro jednoho hráče

2.3.1. Formát získavaných dat Data jsou získávána z webového rozhraní ve formátu JSON [16]. Tento formát je velmi často využíván pro komunikaci v prostředí webových stránek díky jeho snadnému zpracování v jazyce JavaScript. Jeho výhodou je také menší datový objem oproti formátu XML a snadnější rozšiřitelnost přenášených dat oproti binárním formátům serializace. Ukázka jedné zprávy je v 10.

2.3.2. Sběr dat Sběr dat probíhá automaticky čtyřikrát za hodinu za pomocí mého vlastního automatizovaného skriptu. Data jsou poté částečně předzpracována pro jejich použití na jednoduchou statistickou analýzu, která může probíhat v reálném čase. Data v úplné podobě jsou poté uložena do dvou různých úložišť. Důvody pro využití dvou různých úložišť budou popsány dále.

11

2.4. POPIS ŘEŠENÉHO PROBLÉMU

2.4. Popis řešeného problému V této části nastíním, jakými problémy se bude práce zabývat a k jakému účelu budou vydolovaná data sloužit.

2.4.1. Real-time statistická analýza Prvním problémem, kterým se bude tato práce zabývat, je dolování dat metodou statistické analýzy. V této části je důležitým kritériem, aby bylo možné výsledky získat z libovolného monitorovaného období vždy co nejrychleji a s minimálním výpočetním zatížením. To mi umožní, abych mohl prezentovat takto získaná data online širšímu okruhu lidí. Počet požadavků na tyto data je tedy vyšší než malý. Výsledná data budou prezentována formou webového API. Popis tohoto API lze nalézt například online na [20]. Tímto způsobem budou získávány a prezentovány následující znalosti: • Maximální pozorovaná úroveň hráče spolu s datem jeho poslední aktivity • Získané zkušenostní body hráčů za zvolené časové období • Rozložení jednotlivých akcí hráče přes časové období • Rozložení jednotlivých typů akcí v průběhu dne

2.4.2. Vyhledávání farem Dalším problémem, kterým se tato práce zabývá, je vyhledávání vzorů v získaných datech, které mohou indikovat, že skupina portálů je vhodná ke stavbě farmy. Portály, které se nacházejí v těchto vzorech, jsou potenciálně rizikové pro jednu z frakcí a proto je třeba jim věnovat zvýšenou pozornost. Takto vytypované portály je nutné buď více chránit (v případě vlastnictví jedné strany), nebo je účelné se snažit je získat (v případě druhé strany). Vyhledávání existujících nebo potenciálních farem však také může být prospěšné nejen pro monitoring rizikových portálů, ale i pro členy frakce, která danou farmu vlastní. Její 12

2.4. POPIS ŘEŠENÉHO PROBLÉMU členové, kteří se nepodíleli na vzniku farmy, tím získávají možnost, jak si vylepšit vlastní vybavení a tím i herní připravenost. Rizikovost portálů se zvyšuje s počtem farem, které byly okolo daného portálu postaveny, protože to naznačuje jeho opakované úspěšné využití. Jedním z rizikových vzorů, které indikují, že na daném místě bude postavena farma, je obsazování shluku portálů samotným hráčem osmé úrovně tak, že každý portál plně osadí. Poté tyto obsazené portály spojí, aby vytvořil co největší počet linků. Tím zajistí, že další zvyšování úrovně portálu bude prakticky neviditelné pro druhou stranu a zároveň bude existovat velký počet linků, které pomáhají při obraně. Bohužel, z dat, která jsou k dispozici, nelze takovéto chování odlišit od běžné hry, a tedy nemá smysl ho monitorovat. Existuje poměrně vysoká pravděpodobnost, že toto chování nebude na rizikových portálech převažovat a proto budou odhaleny a korektně ohodnoceny.

13

3. Databázové systémy V této kapitole se budu věnovat dostupným databázovým systémům a srovnání jejich výhod a nevýhod. Zaměřím se zde převážně na možnosti urychlení a usnadnění třech hlavních částí procesu: • Čištění dat • Transformace dat do vhodnějšího formátu • Analýza transformovaných dat

3.1. PostgreSQL Jedná se o open-source relační databázi [10], dotazování na data probíhá tradičně pomocí jazyka SQL. Historie této databáze začala v polovině osmdesátých let, kdy započly práce na jejím návrhu, který značně vycházel z databázového systému Ingres. Své současné podoby dosáhl zhruba v roce 1995, kdy byl interpret jazyka QUEL nahrazen SQL interpreterem. PostgreSQL je v současné době podporováno většinou majoritních operačních systémů, včetně MS Windows, Linux, *BSD, Sun Solaris a jiných. Zároveň existují společnosti, jež tento systém komerčně vyvíjejí a poskytují k němu podporu, například EnterpriseDB. V mnoha oblastech tak tato databáze může soutěžit se zavedenými značkami jako je například Oracle. Databáze již tradičně podporuje tvorbu uložených procedur a triggerů i v jiných jazycích, než je PL/SQL. Existují tedy rozsáhlé knihovny uživatelských funkcí, často kompilované do nativního kódu. Paměťová náročnost této databáze je velmi přívětivá, zvládá efektivní práci v prostředí s omezenými paměťovými prostředky. Taktéž při rozkládání výpočetního výkonu na více procesorů se databáze chová velmi přívětivě. 14

3.2. ORACLE Databáze velmi dobře podporuje použití vlastních datových typů, včetně těch výčtových. Práce s výčtovýmy typy je zde nadstandardně rychlá a efektivní. Limity pro uložení dat ve standardně dostupné verzi vysoce převyšují potřeby projektu a kapacity bežně používaného hardware. Efektivita uložení dat je průměrná.

3.2. Oracle Opět se jedná o tradiční relační databázi [9], dotazování probíhá pomocí jazyka SQL. Databáze je licencovaná pod proprietární licencí. K dispozici je verze zdarma, která však má jistá omezení na využitou paměť (max 2 GB) a velikost databáze (max 4 GB). Vývoj této databáze započal v roce 1977, v současné době se již vyskytuje ve verzi 11g. Je to jedna z nejpoužívanějších databází v enterprise sféře. Databáze podporuje tvorbu vlastních procedur i triggerů v jazyce PL/SQL, mimo to je komerčně dostupná celá řada rozšíření. Paměťová náročnost databáze není úplně zanedbatelná, avšak stále je úměrná velikosti databáze a především náročnosti dotazů nad ní prováděných. Protože jsem pracoval pouze s Express verzí, neměl jsem možnost vyzkoušet, jak se chová při výpočetně náročných úlohách omezujícím důsledkem využití pouze jednoho jádra. Podpora využití vlastních datových typů není triviální, pro vytvoření výčtového typu je výrazně jednodušší definovat databázové konstanty typu int. Práce s nimi je pak samozřejmně velmi efektivní. Bohužel, díky limitu dat, které je dovoleno uložit do databáze, by bylo nutné rozdělit data na několik částí a s nimi poté pracovat odděleně. Efektivita uložení dat je průměrná.

3.3. Microsoft SQL Server Tento relační databázový server [6] byl vytvořen firmou Microsoft jako přímá konkurence databázového systému od IBM v prostředí malých a středních firem.

15

3.4. FIREBIRD Vývoj započal v roce 1992, kdy Microsoft dosáhl obrovského úspěchu s produkty Access a FoxPro. Aby však byl schopný IBM konkurovat, potřeboval vlastní plnohodnotný databázový systém. Tento systém zpočátku vznikal ve spolupráci s firmou Sybase. První verze, která vznika pouze v Microsoftu bez pomoci vnější firmy, nese označení 6.0. Od verze 2000 pak podporuje interní zpracování jazyka XML. Veřejně je k dispozici zdarma verze Express, která má v současné verzi (2012) jistá omezení, a to maximálně 4GB velikost databáze, 10GB velikost všech databází dohromady a omezené množství využitelné paměti na 2GB. Také není schopna využít více než jedno jádro pro výpočty. Paměťové nároky databáze samotné jsou poměrně nízké, avšak ke svému běhu vyžaduje systém MS Windows, se kterým je hluboce integrována. Tato skutečnost snižuje její využití, kvůli drahým licencím pro serverový OS. Podpora výčtového datového typu se zde nenachází, je třeba využít celočíselných konstant. Tato nevýhoda se poněkud ztrácí v případě tvorby kódu na platformě .NET, kde lze výčtový typ využívat, a je implicitně konvertován na celočíselný a zpět. Díky limitu velikosti dat databázi nelze efektivně využít pro skladování surových dat, avšak předzpracovaná data zde jsou uložena poměrně efektivním způsobem.

3.4. Firebird Firebird je open-source relační databáze [4], která plně podporuje ANSI standard SQL92. Databázi lze provozovat na širokém spektru operačních systémů a to jak ve variantě plnohodnotné databáze, tak i její embedded varianty. Databáze vnikla v roce 2000 jako odnož open-source verze proprietárního systému InterBase od firmy Borland. Zhruba od verze 1.5 je však většina systému přepsána. Do budoucna se počítá s tvorbou uživatelských funkcí v kompilovaných jazycích jako například Java nebo C++. V současné době jsou podporovány pouze uložené procedury v jazyce PL/SQL. 16

3.5. MYSQL Paměťová náročnost databáze je velmi malá, avšak uživatel za to platí poměrně vysokou daň v podobě výrazně nižší rychlosti složitých dotazů oproti konkurenci. Schopnost využít více procesorů je velmi dobrá. Databáze nepodporuje použití výčtového datového typu, je nutno zvolit celočíselný formát sloupce. Efektivita uložení dat je průměrná. Datové limity databáze dalece převyšují potřeby aplikace a možnosti běžně dostupného hardware. Velikou výhodou je vysoce výkonný systém pro zálohování dat.

3.5. MySQL Jedná se o open-source databázi [8], která je dostupná pod duální licencí (GPLv2 a komerční licence). Jde o velmi rozšířenou databázi, zvláště v prostředí webových služeb. Vývoj této databáze započal roku 1995, v současné době se nachází ve stabilní verzi 5.6. Databáze byla roku 2008 odkoupena společností Oracle a je nyní distribuována pod její hlavičkou. V současné době podporuje dva hlavní typy datových úložišť. Prvním typem je starší engine MyIsam, který nepodporuje transakce na úrovni řádků ani referenční integritu, jako protihodnotu však nabízí výrazně vyšší výkon při ukládání až středně složitých dotazech. Druhým úložištěm je InnoDB, což je novější engine, již plně podporující zamykání na úrovni řádků a cizí klíče. Z méně známých úložišť pak poskytuje formát ARCHIVE [18], což je speciální engine pro ukládání dat, která se nemění a není důležité je často číst. Toto úložiště podporuje pouze dotazy typu select a insert. Jeho výhodou je malá velikost uložených dat, jelikož jsou data ukládána v komprimované podobě. MySQL má výbornou podporu výčtových typů, umožňuje efektivní konverzi mezi výčtovými a znakovými typy. Limity pro uložení dat jsou ve většině datových úložišť daleko za potřebami a možnostmi projektu, obzvláště díky funkci ukládat surová data do tabulky formátu AR-

17

3.6. SQLITE CHIVE. Datový engine MyISAM naopak poskytuje velmi rychlé a efektivní ukládání dat v případě, že není potřeba transakčního zpracování.

3.6. SQLite SQLite je jedna z nejpoužívanějších relačních embedded databází [11], která je šířena pod open-source licencí. Vývoj této databáze započal v roce 2000, první verze databáze byla založena na gdbm. Následující verze již používají vlastní implementaci binárních stromů. Tato databáze implementuje většinu standardu SQL92, avšak některé vlastnosti, převážně ty, které se váží na management serveru a uživatelů, zde chybějí. Výhodou je, že paměťová náročnost databáze je velmi nízká. Nevýhodou je, že knihovna nedokáže využít více jader a celková rychlost databáze se tím velmi snižuje. Výčtový typ zde není podporován, avšak díky architektuře, s jakou je databáze navržena, není velkého rozdílu mezi použitím číselných a řetězcových konstant. Limity pro maximální velikost databáze jsou zde výrazně vyšší, než projekt požaduje pro správné nastavení velikosti databázových stránek.

3.7. Couchbase Couchbase je open-source distribuovaná NoSQL databáze [1], která je již od základů konstruována pro vysoké možnosti škálování. Jedná se o poměrně nový projekt, vývoj byl zahájen v roce 2010. V prvních fázích byla zamýšlena jako alternativa Memcached, která umí ukládat hodnoty do perzistentního úložiště (disk). V prosinci roku 2012 pak vyšla verze 2.0, která již podporuje ukládání dokumentových dat ve formátu JSON. Tato databáze nabízí velmi dobrou škálovatelnost a transakční atomicitu při úpravě jednoho dokumentu. Komunikace mezi serverem a klientem pak probíhá přes JSON REST API. 18

3.8. MONGODB Datové limity úložiště hluboce přesahují potřeby tohoto projektu, v případě nedostatečné kapacity jednoho stroje lze databázi bez jakýchkoliv problémů rychle rozšířit na další stroje.

3.8. MongoDB MongoDB [12] (název vznikl od slova humongous) se řadí do rodiny takzvaných NoSQL databází. Data jsou uchovávána v binárním formátu, který ideově vychází z formátu JSON. Distribuován je pod open-source licencí. Vývoj tohoto databázového prostředí začal v roce 2007, nyní se již nachází ve verzi 2.6.1. V současné době se jedná o nejrozšířenější typ objektové databáze. Její hlavní výhodou je komunikace s klientem pomocí binárního protokolu a z toho vyplývající vyšší rychlost serializace a deserializace uložených objektů. Limity na ukládaná data jsou v 64 bitové verzi MongoDB natolik vysoké, že značně překračují požadavky, které by na ně mohl tento projekt klást.

3.9. Vyhodnocení a výběr databáze Vzhledem k tomu, že vyhledávání shluků portálů bude mimo fázi čištění a transformace probíhat převážně v paměti (toto je možné díky relativně omezenému množství vstupních dat po transformaci, maximálně cca 2500 portálů), zaměřím se zde převážně na efektivní ukládání surových dat a na algoritmy jejich rychlého získání zpět. Dále se soustředím na výkon jednotlivých databází při získávání statistických dat potřebných pro webové API. Požadavky na tyto data jsou volány relativně často a výpočetně stojí právě na rychlosti databáze. Testování probíhalo na dvou případech, u každého pak byl dotaz opakován 10x v cyklu a z něho určena průměrná hodnota. Poté byla databáze smazána a opět nahrána zpět. Tento cyklus byl opakován 3x po sobě. Zpracované výsledky jsou publikovány v níže

19

3.9. VYHODNOCENÍ A VÝBĚR DATABÁZE uvedené v tabulce a k ní se vztahujícímu grafu. Testovány byly pouze tradiční relační databáze. Databáze

Max level Overall AP

PostgreSQL

436 ms

734 ms

Oracle

396 ms

685 ms

MS SQL

122 ms

243 ms

Firebird

753 ms

1643 ms

MySQL

176 ms

415 ms

SQLite

2248 ms

6492 ms

Tabulka 3.1: Porovnání rychlosti různých databází

Obrázek 3.1: Graf porovnání rychlosti databáze

20

4. Práce s daty V této kapitole se budu věnovat zpracování dat do takové podoby, která bude očištěna od nedůležitých informací a stane se výchozím zdrojem prováděné analýzy. V první části se budu zabývat použitými technologiemi, jejich výhodami a nevýhodami. Rozeberu důvody, které mě vedly právě k jejich volbě. Další část se zabývá problematikou čištění dat a jejich transformace do podoby, která je již vhodná pro analýzu.

4.1. Použité technologie 4.1.1. Formát JSON JSON [16] je odlehčeným formátem pro přenos dat, terý je zároveň dobře čitelný jak strojově, tak lidsky. Tento formát byl založen jako podmnožina programovacího jazyka JavaScript. Jedná se o textový formát, který je nezávislý na použitém jazyce, přesto však používá konvence známé z většiny běžných programovacích jazyků (Python, Java, C#). Základem formátu JSON jsou dvě struktury, a to kolekce párů klíč-hodnota (většina jazyků jej realizuje jako slovník nebo objekt) a seřazený seznam hodnot (většina jazyků jej realizuje jako seznam nebo pole). Objekt je zde realizován jako neuspořádaná kolekce párů klíč-hodnota vzájemně oddělených čárkou a uvozených složenými závorkami.

Obrázek 4.1: Struktura objektu v JSON (Převzato z [16]) Naopak pole je zde seřazenou kolekcí hodnot. Hodnoty, oddělené čárkami, jsou uvozeny hranatými závorkami. 21

4.1. POUŽITÉ TECHNOLOGIE

Obrázek 4.2: Struktura pole v JSON (Převzato z [16]) Hodnotou se v předchozích případech myslí kterákoliv možnost z řetězce uvozeného dvojitými uvozovkami, čísla, objektu, pole neboo konstant true, false, null. Řetězcem je možno rozumět nula a více znaků v kódování Unicode uvozených uvozovkami. Jsou zde využity escape sekvence začínající zpětným lomítkem. Znak je řetězec o délce jedna.

Obrázek 4.3: Struktura řetězce v JSON (Převzato z [16]) Struktura čísla je velmi podobná decimálnímu zápisu v jazycích Java nebo C, s tím rozdílem, že zde není možný hexadecimální nebo oktalový zápis čísla.

22

4.1. POUŽITÉ TECHNOLOGIE

Obrázek 4.4: Struktura čísla v JSON (Převzato z [16])

4.1.2. Databáze MySQL Jako primární databázi k ukládání dat jsem zvolil open-source databázi MySQL. Jako další úložiště jsem zvolil MongoDB. Open-source databázový server MySQL jsem zvolil ze dvou důvodů. Prvním důvodem je existence úložiště ARCHIVE, které je vhodné k archivování dat v jejich zdrojové podobě. Druhým důvodem pak je vysoká rychlost engine MyIsam, který je vhodný pro uložení a následné zobrazování statistické analýzy dat za předpokladu, že budu schopen udržet konzistanci dat na úrovni aplikace. Tuto podmínku lze splnit na základě toho, že do systému data vstupují pouze jedním kontrolovaným bodem.

4.1.3. Nerelační databáze MongoDB Jako důsledek jiného způsobu ukládání dat je tato databáze výrazně rychlejší při provádění určitých operací a tím unožňuje velmi efektivní filtrování dat. K dalším výhodám této databáze patří schopnost pokládat dotazy přímo na vlastnosti objektů bez nutnosti náročného převodu složitých objektů do normalizované formy a zpět. Díky propracovanému systému indexů je pak takovéto vyhledávání rychlé a efektivní i pro velké sady dat.

23

4.2. ČIŠTĚNÍ A TRANSFORMACE ZDROJOVÝCH DAT V případě, že by objem dotazů do databáze přesáhl schopnosti jednoho databázového stroje na zpracování v rozumném čase, lze provádět prakticky neomezené horizontální rozšiřování pomocí tzv. shardingu, kdy jsou data dělena mezi jednotlivé databázové stroje podle hodnoty vybraného klíče. Obrovskou výhodou zde je funkcionalita přidávání nových strojů do již existujícího a běžícího clusteru přímo za chodu. Tuto databázi jsem zvolil z důvodu jednoduché a rychlé filtrace dat na základě libovolných vlastností jednotlivých objektů bez nutnosti jejich složitého převodu do normalizované formy relačních dat.

4.1.4. Skriptovací jazyk PHP Skriptovací jazyk PHP [13] původně vznikl jako šablonovací jazyk pro vývoj webových stránek. V dnešní době se jedná o multiparadigmatický jazyk pro obecné využití. Jedná se o dynamicky typovaný jazyk. Nyní se již nachází ve verzi 5.5. Tento jazyk jsem si zvolil z důvodu jednoduché práce s dynamicky typovanými objekty a uživatelsky velmi přívětivé implementace serializéru/deserializéru dat do formátu JSON. Skripty napsané v jazyce PHP používám jak pro pravidelné načítání dat ze zdroje do databáze, tak pro jejich následné čištění a předzpracování. Zároveň mi implementace v tomto jazyce umožňuje velmi jednoduchou integraci s webovým REST API, která poskytuje výsledky statistické analýzy.

4.2. Čištění a transformace zdrojových dat V této kapitole se budu zabývat způsobem čištění zdrojových dat od přebytečných nebo chybných záznamů a jejich následné transformaci do takové podoby, která bude vhodná a současně výhodná pro následující zpracování některou z dolovacích metod. Čištění dat je důležitý proces, který umožní velmi efektivně zmenšit objem zpracovávaných dat. Jedná se o akci, jejíž náročnost roste přinejhorším lineárně s objemem dat, ale umožní výrazné zrychlení samotného dolování informací. Díky využití MongoDB s vhodně

24

4.2. ČIŠTĚNÍ A TRANSFORMACE ZDROJOVÝCH DAT nastavenými indexy lze tuto akci škálovat v zásadě na neomezený počet výpočetních zařízení s jen malým overheadem na distribuci. Transformace dat zajistí přeměnu do takového formátu, na který lze smysluplně aplikovat některou z dolovacích metod. Zároveň transformace umožňuje odfiltrovat data, která mají pro analýzu malý nebo žádný význam.

4.2.1. Příprava pomocných dat pro statistickou analýzu Proces přípravy dat pro statistickou analýzu probíhá souběžně s procesem ukládání surových dat do databáze v souladu s co nejrychlejší odezvou. Data jsou ukládána do dvou nepříliš složitých tabulek na MySQL serveru. Zpracovávají se pouze ty záznamy, které obsahují informaci o obsazení portálu, či vytvoření nebo zničení jedné z následujících položek: • Rezonátor • Link mezi dvěmi portály • Pole (Field) Přezdívka hráče, který akci provedl, je převedena pomocí jeho globálně unikátního ID na lokální odkaz do tabulky hráčů. V případě, že by se vyskytl dosud nepozorovaný hráč, je pro něj vytvořen nový záznam. Jak je ze schématu 4.5 vidět, celá struktura je optimalizována na rychlé dotazování na statistická data, proto se zde nacházejí některé duplicitní sloupce (např. ap a akce). Tabulka je také již připravena k nasazení systému pro několik navzájem nezávislých oblastí (v současné době Brno, Kroměříž, Ostrava). Množina akcí se skládá z následujících položek: • capture - Obsazení portálu • resonator create – Osazení portálu rezonátorem • resonator destroy – Zničení rezonátoru • link create – Vytvoření propojení mezi dvěma portály 25

4.2. ČIŠTĚNÍ A TRANSFORMACE ZDROJOVÝCH DAT

Obrázek 4.5: Diagram databáze pro API statistické analýzy • link destroy – Zničení propojení mezi dvěma portály • field create – Vytvoření pole • field destroy – Zničení pole

4.2.2. Odstranění nevhodných dat Pro hledání a analýzu kritických portálů vzhledem k tvorbě farem není třeba zpracovávat veškeré získané údaje, ale některé akce je možno vypustit jako nerelevantní k danému problému. • Komunikace mezi hráči – veškerá důležitá komunikace mezi hráči velmi pravděpodobně neprobíhá na veřejném kanále, který sdílí obě frakce, ale probíhá buď na kanále specifickém pro danou frakci, nebo pomocí prostředků třetích stran (Jabber, Google Hangouts, atd.) • Akce zničení linků nebo polí – tyto akce typicky doprovázejí ničení a přebírání portálů a proto nejsou pro vyhledávání farem relevantní • Akce vytváření polí – opět se jedná o doprovodnou akci provázející tvorbu linků mezi portály, která není pro daný předmět zkoumání relevantní

26

4.2. ČIŠTĚNÍ A TRANSFORMACE ZDROJOVÝCH DAT • Osobní notifikace hráče — nejedná se o data, která by jakkoliv informovala o stavu hry ve městě a obvykle se jedná o duplicitní data k jiným akcím • Zprávy o spadnutí linku díky vybití portálu – opět se nejedná o relevantní data, navíc se tato akce objevuje pouze u samostatně stojících portálů na okrajích města, která jsou málo navštěvovaná a tedy nezajímavá. Odstranění dalších dat by bylo potenciálně možné, avšak v současné době je datový vzorek natolik malý (řádově jednotky milionů akcí), že jeho zpracování nepřínáší výrazný datový problém. Redukce by naopak mohla zastřít důležité informace.

4.2.3. Úprava dat do vhodného formátu Surový formát dat, který dostanu po jejich pročištění, je stále velmi nevhodný pro následnou analýzu některou z dolovacích metod. Jednak data obsahují velké množství nadbytečných informací, dále pak je jejich struktura špatně přizpůsobená k vyhledávání poblíž sebe stojících portálů s určitými vlastnostmi. Pro účely analýzy budou data transformována do seznamu portálů s dobami, kdy byl který portál obsazen kterou frakcí. Z takovéhoto seznamu pak není problém získat portály, jež pro daný časový interval splňují vybraná kritéria. Jelikož není možno sledovat, které rezonátory byly na portálu vylepšeny na vyšší úroveň, je poměrně častým jevem, že průměrná úroveň ničených rezonátorů je vyšší, než průměr úrovní rezonátorů původně osazovaných. Pro takový případ je vhodné držet v rámci jednoho životního cyklu portálu obě hodnoty a analýzu upravuji podle jejich vzájemné relace. Zároveň s úpravou dat do vhodnějšího formátu jsou pak data ukládána do takových struktur, které umožňují co nejjednodušší dotazování na seznamy portálů, které by v daném okamžiku vyhovovaly daným podmínkám (obvykle minimální úroveň původně osazených nebo zničených rezonátorů).

27

4.2. ČIŠTĚNÍ A TRANSFORMACE ZDROJOVÝCH DAT Pomocné struktury Pro rychlé a pohodlné získání portálů, které se v určeném časovém intervalu vyskytovaly na daných úrovních, jsem vytvořil pomocnou strukturu PortalList. Tato struktura je v současné době využita ve dvou fázích, a to jak při transformaci dat, tak při jejich analýze. Při transformaci se stará o rychlou změnu úrovně portálu v případě, že byl přidán nebo odebrán rezonátor. Zároveň také vytváří pro daný portál seznam časových intervalů, které zaznamenávají jeho existenci na zajímavých úrovních. Při analýze dat pak plní svůj primární účel, a to získávání relevantních dat pro daný časový vzorek. V současné době, díky relativně malému objemu dat, se kterými je nakládáno, není tato struktura plně optimalizována, místo toho je preferována jistota správnosti výpočtu. V případě, že by bylo potřeba výrazně zvýšit výkon, mohu předzpracovaná data uložit do MongoDB a značnou část výpočetních nároků tak přenést na databázový server, který je pro některé operace daleko lépe vybaven.

28

5. Analýza získaných dat V této kapitole se budu věnovat analýze již vyčištěných a transformovaných dat, pomocí nichž mohu efektivně vyhledávat potenciální farmy. První část se zabývá popisem možných metod analýzy, diskutuji zde také výhody a nevýhody těchto metod vzhledem k řešenému problému. V další části se zabývám popisem samotné analýzy dat, tím jak je provedena a jaká úskalí při ní mohou nastat.

5.1. Kritéria pro úspěšnost analýzy Abych mohl vyhodnotit, zda jsem zvolil správnou metodu zpracování dat a jejich následné analýzy, zvolil jsem si níže uvedená kritéria. Zároveň splnění těchto kritérií zaručuje správnost implementace zvolených algoritmů. Zároveň pokud budou splněna níže uvedená kritéria, je možno přistoupit k faktickému ověření správnosti získaných informací pro jiná města než jen Brno. • Zpracovatelnost získaných dat • Správnost zvolené metody – Zvolená metoda poskytuje pro zpracovávané data výsledky – Metoda je schopna se vyrovat s charakteristikou vstupních dat • Smysluplná velikost získaných farem – Alespoň 5 portálů v každé farmě – Ne více než 50 portálů v jedné farmě

29

5.2. METODY KLASIFIKACE DAT

5.2. Metody klasifikace dat Klasifikací dat se rozumí rozdělení vstupní množiny objektů na konečný, předem známý počet podmnožin, kdy každý objekt patří do právě jedné podmnožiny a objekty v každé podmnožině spolu sdílí určitou vlastnost nebo sadu vlastností. Výhodou klasifikačních metod je jejich relativně vysoká rychlost, která plyne převážně ze skutečnosti, že počet množin je jen omezený a jejich vlastnosti jsou často předem známé. Z toho také plyne největší nevýhoda těchto metod, že je lze klasifikovat jen do předem známých podmnožin, a tím se stávají méně variabilní. Metody, které zde probírám jsou detailněji popsány například v [19], [14] nebo [17].

5.2.1. Rozhodovací stromy Rozhodovací strom si můžeme představit jako strom, ve kterém veškeré uzly, jež nejsou listy, představují jeden test na určitou vlastnost objektu. Ohodnocení listových uzlů poté představuje výslednou třídu, do které je daný objekt klasifikován. Klasifikace pomocí rozhodovacího stromu pak představuje cestu stromem od jeho kořene až k listu. V každém uzlu cesty se provede příslušný test a podle jeho výsledku se rozhoduje, kterou cestou pokračovat dále (pokračuje se po větvi, která je shodná s výsledkem testu). Určitou nevýhodou této metody je, že klasifikaci lze provádět pouze na diskrétních datech. V případě dat spojitých následuje proces jejich převodu do diskrétních hodnot. Při konstrukci rozhodovacího stromu pomocí algoritmu, jež je uveden například v [6], nemusí být vždy zajištěn optimální tvar výsledného stromu. To má za následek buď zpomalení klasifikace, nebo ztrátu její přesnosti. Z těchto důvodů je tedy vhodné rozhodovací strom modifikovat pomocí takzvaného ořezávání (pruning). Na to je možné použít metodu prepruning, postpruning nebo jejich kombinaci. Prepruning znamená ořezávání stromu již v okamžiku jeho vytváření. Obvykle bývá realizován jako předčasné ukončení některých větví výsledného rozhodovacího stromu. Důvodem k tomuto ukončení může být například vysoká pravděpodobnost příslušnosti 30

5.2. METODY KLASIFIKACE DAT

Obrázek 5.1: Diagram rozhodovacího stromu (převzato z [3]) k určité kvalifikační třídě. Problémem zde je určení vhodné hranice, kdy takovou větev ukončit a kdy raději pokračovat dále ve větvení uzlu. Postpruning je realizován jako ořezání stromu teprve po dokončení jeho konstrukce. Tato metoda je sice výrazně výpočetně náročnější, avšak díky tomu bude obvykle poskytovat lepší výstupní rozhodovací strom.

5.2.2. Systém rozhodovacích pravidel Systém rozhodovacích pravidel si lze představit jako lineární zápis rozhodovacího stromu. Nemusí však vznikat pouze jeho transformací, ale také například jako výsledek převedení klasifikačního modelu neuronové sítě. Každé z pravidel se skládá z podmínky a jejího závěru (všem důvěrně známé if-then). Množina pravidel z rohodovacího stromu vzniká tím, že každou cestu od kořene stromu až k listu vyjádříme jako jedno pravidlo. Podmínka je pak určena logickým součinem veškerých testů, kterými je třeba na dané cestě projít.

31

5.2. METODY KLASIFIKACE DAT Vlastní klasifikace pak probíhá vyhodnocením sady pravidel na každém z klasifikovaných objektů. Výsledná třída je pak přiřazena podle závěru prvního pravidla, jehož podmínce objekt vyhovuje. Pořadí, ve kterém jsou pravidla na objektu testována, není obecně nijak definováno, avšak v některých modelech je možné a výhodné přiřadit každému pravidlu jeho váhu (např. šance na úspěch nebo složitost pravidla) a následně je vyhodnocovat v sestupném pořadí dle jejich váhy. Vylepšení tohoto algoritmu lze provést například aplikací fuzzy logiky, kdy uplatnění jednotlivých pravidel přispívá k příslušnosti objektu do dané třídy. Systém rozhodovacích pravidel se vylepšuje pomocí aplikace evolučních genetických algoritmů. Jednotlivá pravidla jsou v tomto případě vyjádřena jako bitová sekvence (genom) a pomocí genetických manipulací crossover a mutation jsou modifikována. Po dokončení každé iterace (pro každou novou populaci), je třeba zkontrolovat chybovost takto vytvořených pravidel pomocí testovací sady dat. Nově vzniklá pravidla s vysokou chybovostí jsou následně vyloučena. Proces je u konce ve chvíli, kdy se chybovost všech pravidel vyskytuje v pořadovaných mezích.

5.2.3. Statistické metody Pro klasifikaci dat se využívají dvě statistických metod, regrese a Bayesovské klasifikace. V případě regrese dochází k predikci spojitého atributu, kdy se snažíme zjistit hodnotu závislé proměnné na funkci nezávislých proměnných. Bayesovská klasifikace využívá důsledků Bayesovy věty, přiřazuje objektu třídu z množiny možných tříd. Pro řešení výše nastíněného problému jsou tyto metody zcela nevhodné.

32

5.2. METODY KLASIFIKACE DAT

5.2.4. Neuronové sítě Neuronovou sítí rozumíme neorientovaný graf, kde každý z jeho uzlů je označen číslem vrstvy a svým pořadím v této vrstvě. Hrany pak mohou spojovat pouze uzly vrstev, které spolu přímo sousedí. První vrstvu neuronové sítě nazýváme vstupní vrstvou, poslední vrstva se pak nazývá výstupní vrstva. Mezi těmito dvěma vrstvami se může vyskytovat libovolný počet skrytých vrstev. Neuronová síť je označována za n-vrstvou právě v tom případě, kdy počet skrytých a výstupní vrstvy je roven číslu n.

Obrázek 5.2: Diagram neuronové sítě (převzato z [5]) Veškerý vstup dat do neuronové sítě probíhá jen přes vstupní vrstvu, kde vstupem každého uzlu je hodnota části analyzovaného záznamu. V případě diskrétní hodnoty atributu je možné její vyjádření pomocí n uzlů vstupní vrstvy, kdy vždy právě jeden uzel nabývá hodnoty 1, ostatní uzly mají hodnotu rovnu nule. Výstup (a tedy vyjádření, do které třídy je objekt klasifikován) probíhá pomocí uzlů výstupní vrstvy, kdy příslušnost k m-té třídě je signalizována hodnotou 1 na m-tém uzlu výstupní vrstvy. Ostatní uzly pak nabývají hodnoty 0.

33

5.2. METODY KLASIFIKACE DAT Vlastní trénování neuronové sítě poté probíhá pomocí algoritmu zpětné propagace (backpropagation), který se skládá ze dvou základních kroků. V prvním kroku, kterým je dopředná propagace, dochází k předání vstupní hodnoty uzlů na výstup beze změny, poté dochází ke klasifikaci. V druhém kroku zpětné propagace je takto získaný výsledek porovnán s očekávaným výsledkem a hodnota chyby se zpětně propaguje od výstupní vrstvy až po vrstvu vstupní. Algoritmus je ukončen v případě, že dochází pouze k malým změnám korekce hran nebo pokud je procento neúspěšné klasifikace zanedbatelné. Pro lepší porozumění a kontrolu výsledných pravidel, podle ktarých jsou data neuronovou sítí klasifikována, je možné ji převést na systém klasifikačních pravidel, který je již popsán výše.

5.2.5. Kombinované či odvozené techniky ALgoritmy ID3, C4.5, C5.0 a Gini se zabývají rozšířením a vylepšením metody klasifikace pomocí rozhodovacích stromů. Algoritmus ID3 Přínos algoritmu ID3 spočívá v přidání informačního zisku atributu daného objektu Gain(A). Funkce Gain je definována jako snížení míry entropie za předpokladu znalosti atributu A. Algoritmus C4.5 Dalším rozšířením algoritmu ID3 je algoritmus C4.5, který zásadně vylepšuje práci s chybějícími daty (při stavbě stromu jsou takovéto atributy ignorovány a při klasifikaci dochází k jejich predikci na základě znalosti ostatních hodnot tohoto atributu). Dále je zde pak zlepšena práce se spojitými daty a způsob výstavby stromu.

34

5.3. METODY SHLUKOVÁNÍ DAT Algoritmus C5.0 Algoritmus C5.0 je komerčním rozšířením předchozího algoritmu. Jeho přínos spočívá především v lepším způsobu generování systému pravidel a také zpřesnění klasifikace pomocí metody boosting. Algoritmus Gini Algoritmus Gini se pokouší vyřešit zásadní problém ID3, kterým je poměrně náročný výpočet funkce Gain. Místo ní zavádí zcela novou hodnotu, takzvaný Gini-index. Při výstavbě stromu pak není využito hodnoty funkce Gain ale ∆ Gini. Klasifikace pomocí hrubých množin Tato metoda na objektech zavádí relaci ekvivalence na základě některých atributů. To znamená, že se vstupní množina objektů rozpadá na několik podmnožin, kdy objekty v každé podmnožině spolu sdílí identické hodnoty některých atributů. Poté se buď pokusí algoritmus zařadit všechny objekty v dané podmnožině do jedné klasifikační třídy (v případě, že takováto třída existuje), nebo klasifikuje záznamy do jedné z tříd, například na základě kritéria vzdálenosti.

5.3. Metody shlukování dat Shlukováním dat se rozumí zařazení vstupních objektů do podmnožin takovým způsobem, že objekty v každé podmnožině spolu sdílí určitou podobnost atributů. Shlukování vždy poskytuje 1-n navzájem disjunktních množin, kde n je počet vstupních objektů. Z hlediska jejich klasifikace se jedná o algoritmy učení bez učitele, jelikož jejich využití nepožaduje žádné předdefinované třídy ani trénovací množinu objektů. Nevýhodou shlukovacích algoritmů je jejich obvykle vyšší náročnost oproti algoritmům pro klasifikaci. Tuto nevýhodu však bohatě vyvažují mnohem větší pružností při rozdělování dat do podmnožin.

35

5.3. METODY SHLUKOVÁNÍ DAT Výsledek analýzy velmi záleží na vhodně zvolené míře vzdáleností mezi objekty a shluky, záleží i na zvoleném algoritmu výpočtu. Obecně by mohl počet shluků dosahovat počtu jednotlivých objektů, avšak význam má jen takový počet shluků, který je výrazně menší než počet objektů. K hodnocení podobnosti objektů se obvykle používá míra vzdálenosti mezi nimi, například eukleidovská, Hammingova nebo Čebyševova. Pro řešení problému, kterým se tato práce zabývá, se přímo nabízí vzdálenost eukleidovská, jelikož se jedná o vzdálenosti objektů v dvojrozměrném prostoru. Jednotlivé shlukovací metody se od sebe liší způsobem, jakým se stanovuje vzdálenost mezi dvěmi shluky, je možné použít například následující metody: • Metoda nejbližšího souseda — vzdálenost shluků je určena vzdáleností dvou nejbližších prvků • Metoda nejvzdálenějšího souseda – vzdálenost shluků je určena vzdáleností dvou nejvzdálenějších prvků • Metoda průměrné vzdálenosti – vzdálenost dvou shluků je určena průměrnou vzdáleností všech dvojic objektů z jednotlivých shluků • Centroidní metoda – vzdálenost dvou shluků je dána vzdáleností jejich středů Metody shlukování také lze rozdělit podle principu, na kterém jsou založeny a to na • Metody založené na rozdělování • Hierarchické metody • Metody založené na hustotě • Metody založené na mřížce • Metody založené na modelech

5.3.1. Metoda K-means Jedná se o shlukovací metodu založenou na rozdělování. Je třeba před započetím shlukování znát počet tříd, do kterých budou data rozdělena. 36

5.3. METODY SHLUKOVÁNÍ DAT Nalezení optimálního řešení by vyžadovalo vyhodnocení všech možných rozdělení databáze, což je pro reálné velikosti databází nereálný požadavek. Z tohoto důvodu dochází k využití heuristiky pro urychlení výpočtu. Na počátku shlukování se náhodně vybere k objektů (instancí), které budou reprezentovat jednotlivé shluky. Následně jsou ostatní objekty rozděleny do těchto tříd na základě jejich podobnosti. Poté jsou určeny nové středy shluků a objekty jsou přesouvány mezi shluky na základě jejich vzdálenosti od středu. Tento krok se opakuje do té doby, dokud dochází k přesunu objektů.

Obrázek 5.3: Ukázka shlukování pomocí K-means (převzato z [7]) V této metodě je třída reprezentována pomocí fiktivního centrálního bodu, jehož atributy se určí jako střední hodnota daného atributu veškerých objektů, které se v této třídě nacházejí.

37

5.3. METODY SHLUKOVÁNÍ DAT Tato metoda vykazuje velmi dobré výsledky v případě, že data tvoří kompaktní shluky, které lze od sebe zřetelně oddělit. Naopak se špatně vypořádává s odlehlými hodnotami a nekonvexním tvarem shluků.

5.3.2. Metoda K-medoids Narozdíl od metody K-means jsou u této metody jednotlivé shluky reprezentovány jedním skutečným objektem z množiny. Jedná se o ten objekt, který se nachází nejblíže od středu daného shluku. Tato změna umožňuje snížit vliv odlehlých hodnot na podobu výsledných shluků. Daní za to však je vyšší výpočetní náročnost algoritmu, který je proto vhodný převážně pro menší množiny dat. Zásadním problémem, který se zde řeší, je, jak určit, zda se změnil reprezentující model pro danou třídu a zda má být nahrazen jiným objektem z příslušné podmnožiny. Po každém kole přesunu objektů mezi shluky je třeba určit, jak se změnila celková průměrná vzdálenost objektů od objektu reprezentujícího. Pokud došlo ke snížení celkové vzdálenosti objektů od objektu reprezentujícího, je nutné hledat nový objekt, který se pro daný shluk stane reprezentujícím.

5.3.3. Hierarchické metody Obecně lze hierarchické metody rozdělit podle toho, jakým směrem postupují při vytváření shluků. Metoda zdola nahoru (AGNES) nejprve považuje každý objekt za samostatný shluk a poté se jednotlivé shluky snaží spojovat. Metoda shora dolů (DIANA) začíná s jedním shlukem, který obsahuje veškeré objekty a tento shluk se snaží postupně dělit na dílčí shluky. Tyto metody narozdíl od výše popsaných nevyžadují znalost počtu tříd, do nichž budou objekty shlukovány. Pro jejich hladký běh je však vhodné určit, za kterých podmínek se má shlukování ukončit a výsledné rozdělení objektů prohlásit za konečné.

38

5.3. METODY SHLUKOVÁNÍ DAT

Obrázek 5.4: Ukázka shlukování pomocí hierarchických metod (převzato z [7]) Výraznou výhodou těchto metod je menší výpočetní náročnost. Bohužel tyto metody neumožňují opravit chybné rozhodnutí a pokud dojde ke sloučení nebo rozdělení dvou množin, nelze je již zpětně rozdělit (spojit). Navíc tyto metody nejdou příliš škálovat.

5.3.4. Metoda DBSCAN Jedná se o shlukovací metodu založenou na hustotě. V těchto metodách jsou za shluky považovány oblasti s velkou hustotou objektů, které jsou vzájemně odděleny oblastmi s malou hustotou. Shluky jsou tak zvětšovány do té doby, než hustota okolních objektů poklesne pod předem danou hranici. Díky tomu lze hledat shluky různých tvarů a šum či odlehlé hodnoty nemají na výsledné hodnoty žádný vliv. Je dokonce možné detekovat shluk, který zcela obklopuje jiný, nezávislý shluk objektů.

39

5.4. VOLBA VHODNÉ METODY Nevýhodou této metody je skutečnost, že je třeba vhodně definovat parametry, podle kterých bude probíhat výpočet hustoty, a stanovní spodní meze této hustoty. Popisovaná metoda si také nevede příliš dobře při práci s vysoce dimenzionálními daty. Metoda pro tvorbu shluků využívá funkci vzdálenosti mezi objekty, v našem případě Euklidovskou vzdálenost. V ε-okolí objektu se musí nacházet jistý minimální počet objektů aby bylo se dalo prohlásit, že objekt je jádrem shluku.

Obrázek 5.5: Ukázka shlukování pomocí metody DBSCAN (převzato z [2]) V případě, že se jeden objekt nachází v jádru dvou rozdílných shluků, nabízí se tyto dva shluky spojit dohromady.

5.4. Volba vhodné metody Nyní záleží na rozhodnutí, zda se vydat cestou klasifikace nebo shlukové analýzy. Klasifikační metody mají obrovskou výhodu ve své rychlosti a relativní paměťové nenáročnosti. Jejich značnou nevýhodou pro řešení daného problému je nutnost mít data, na kterých je možno metodu trénovat. V tomto případě nemám k dispozici relevantní 40

5.4. VOLBA VHODNÉ METODY údaje. Další značnou nevýhodou je nutnost předem znát třídy, do kterých budou objekty klasifikovány. Naopak u shlukové analýzy vyžadují algoritmy výrazně vyšší výpočetní výkon a jejich paměťová náročnost je také obvykle výšší. Za to ale nabízí data organizovat do neznámého počtu podmnožin, kdy jejich vlastnosti nemusí být předem vůbec známy. Jak je zřejmé z předchozího textu, jedním z hlavních požadavků je možnost data rozdělit na předem neznámý počet disjunktních množin. Z toho důvodu jsem se rozhodl jít cestou shlukové analýzy. Díky tomu, že nevíme, kolik shluků vznikne, jsou metody založené na rozdělování, tedy K-means a K-medoids, zcela nevhodné pro tento účel. Matematický model vývoje hry Ingress ve městě také není znám, stejně tak jako libovolný jiný formální popis daného problému. Z toho důvodu jsem vyřadil metody, které jsou založeny na modelech. Teoreticky lze tedy použít libovolnou z hierarchických metod či metody založené na hustotě nebo mřížce. Hierarchické metody nejsou pro tento účel příliš vhodné, protože nelze opravit špatné rozhodnutí. Metody založené na mřížce se vyznačují velkou rychlostí zpracování dat, avšak jsou vhodné především pro datové množiny s velmi vysokým počtem prvků. Pro řešení daného problému nejvíce vyhovuje metoda DBSSCAN, která pro shlukování přímo používá hustotu, což je v případě problému vyhledávání shluků objektů v 2D prostoru ideální. Rychlost této metody je také velmi dobrá a díky tomu, že se objekty vyskytují pouze v dvojrozměrném prostoru a nedochází zde k problémům s použitím euklidovské vzdálenosti, dosahuje metoda dobrých výsledků. Další nezanedbatelnou výhodou této metody je její necitlivost na odlehlé hodnoty, jichž se v analyzovaném vzorku vyskytuje velké množství.

41

5.5. VYHLEDÁVÁNÍ SHLUKŮ

5.5. Vyhledávání shluků Pročištěná a transformovaná data jsou nejprve načtena do struktury, která umožňuje jejich filtrování podle času, kdy portál byl aktivní a osazený na určnou minimální úroveň. Následně jsou data vzorkována po určitém časovém intervalu (implicitně jedna hodina). Na takto získaný obraz hry v určitém časovém intervalu již lze aplikovat shlukovací algoritmus. Pro vyhledávání farem je nejvhodnější metodou DBSCAN, u níž je minimální počet objektů v ε-okolí objektu nastaven na pouhý jeden. To umožní vyhledávání případných řetězců portálů. Tyto útvary, které se ve většině případů považují za negativní jev, jelikož mohou spojit dva nesouvisející shluky řetězcem téměř samostatných bodů, zde žádný problém nepředstavují a v jistých případech naopak mohou být žádoucí či nezbytné. Maximální vzdálenost mezi portály, která ještě dává smysl pro tvorbu farmy, jsem po konzultaci s experty stanovil na 150 metrů. Dále je potřeba provést filtraci získaných shluků a odstranit takové množiny, které jsou příliš malé na to, aby mělo význam se jimi zabývat. Opět po konzultaci s experty jsem stanovil minimální množství portálů na pět. Výstupem je časová mapa, která říká, v kterých intervalech se v Brně nacházely farmy. Na tomto obraze již lze provádět analýzu, jak moc rizikové nalezené portály jsou.

5.6. Výsledky statistické analýzy Provedl jsem statistickou analýzu na menším vzorku dat pomocí programu RapidMiner. Zaměřil jsem se zde na získání dvou informací a to: • Rozložení poměru AP mezi frakcemi v průběhu dne • Rozložení jednotlivých akci v průběhu dne Rozložení poměru AP mezi frakcemi je zajímavá informace z toho důvodu, že indikuje, ve kterém okamžiku je daná frakce nejaktivnější a kdy naopak je většina členů převážně 42

5.6. VÝSLEDKY STATISTICKÉ ANALÝZY pasivních. Této informace lze například využít pro plánování farmy v době, kdy je nepřátelská aktivita ve hře na co nejnižší úrovni. Grafu 5.6 nabízí pohled na výsledné rozložení. Vyšší hodnoty znamenají větší aktivitu frakce Enlightened.

Obrázek 5.6: Graf rozložení získaných AP mezi frakcemi Rozložení akcí v průběhu dne, jak vidíme z grafu 5.7, je zajímavé v tom, že v určitých časových intervalech převažuje množství rozbitých rezonátorů nad rezonátory osazenými, (které budou vždy celkově dominantnější díky tomu, že určité procento osazených rezonátorů je zničeno samovolně díky přirozenému klesání jejich energie). Tento jev bych vysvětlil tím, že v ranních a pozdních večerních hodinách hrají především zkušenější hráči, kteří často portál neosazují plně, ale zato boří plně osazené portály nepřátel.

43

5.6. VÝSLEDKY STATISTICKÉ ANALÝZY

Obrázek 5.7: Graf rozložení jednotlivých akcí v průběhu dne

44

6. Riziková analýza portálů Jakmile jsou nalezeny kýžené shluky portálů, je potřeba provést jejich analýzu z hlediska rizik, které jsou společné pro obě znepřátelené frakce. Základní premisou zde je skutečnost, že ne všechna místa jsou vhodná na stavbu farem, ty se proto mají tendenci opakovat na podobných místech. Je tedy praktické tato místa průběžně hlídat před nepřátelskou aktivitou. Zásadním problémem, kterým se tato kapitola bude zabývat, je určení vhodného způsobu, jak hodnotit rizikovost portálů z hlediska jedné ze stran. Nabízí způsob vyhodnocení těchto portálů.

6.1. Hodnocení portálu z hlediska vlastnictví Při zužitkování farmy je třeba brát v úvahu několik časových faktorů, jež významně určují její nebezpečnost pro opozici. Důkladným rozborem těchto faktorů se zabývám v následujících podkapitolách. Dalším, neméně významným faktorem, je možnost jednoduchého a rychlého odhalení farmy v okamžicích blízkých její stavbě. Na to má opět vliv více faktorů, které hlouběji rozebírám níže. Rizikovost portálu je vyjádřena jako reálné číslo v intervalu <0; 1>. Algoritmus jeho výpočtu však pracuje s dvojicí celočíselných bezrozměrných hodnot, jedna pro každou frakci. Tyto hodnoty (dále uváděny jako koeficient nebezpečnosti) jsou upravovány pro každý portál a shluk portálů zvlášť v závislosti na velikosti shluku a níže uvedených faktorech. Koeficient nebezpečnosti K každého portálu je upravován v závislosti na velikosti nalezeného shluku, a to podle následujícího vzorce: K = Ki ·

N +5 10

Kde Ki je původní koeficient nebezpečnosti portálu a N je počet portálů v daném shluku. 45

6.1. HODNOCENÍ PORTÁLU Z HLEDISKA VLASTNICTVÍ Událost

Bodové hodnocení

Portál stojí prvních 30 min

10

Portál nevydržel prvních 30 min

-2

Portál vydržel 1 hodinu

5

Portál vydrží první 4h 10 min

5

Každé další 4h 10 min

1

Portál byl postaven na úrovni 5 nebo nižší

10

Tabulka 6.1: Porovnání rychlosti různých databází

6.1.1. První časový faktor – doba jednoho burnoutu Prvním a nejdůležitějším časovým milníkem je doba, za kterou lze portál plně využít. Ten je v ideálním případě 15 minut, avšak reálné zkušenosti ukazují, že se pohybuje spíše okolo půl hodiny, často v závislosti na velikosti postavené farmy. Důvod, proč je tento prvotní interval tak důležitý, je nasnadě. Právě v tomto časovém rozestupu je možné plné využití potenciálu portálu. Zároveň se obvykle jedná o tak krátký časový okamžik, že nepřítel nestačí včas reagovat na přítomnost farmy. Pokud portály vydržely alespoň tento časový okamžik, je straně, která vlastní portál, připsáno 10 bodů. Pokud by však portály tuto dobu nevydržely, odečítají se dva body, protože to velmi pravděpodobně znamená, že farma byla stvořena na nevhodném místě a vydržela příliš krátkou dobu. Pokud se portálu podaří vydržet alespoň dvojnásobek této doby, přičítá se dalších pět bodů, a to z důvodu výrazně lepšího využití portálu ostatními členy, kteří se nepodíleli na stavbě.

6.1.2. Druhý časový faktor – Interval hackování Druhým důležitým časovým faktorem je doba, po jakou musí portál minimálně vydržet, aby na něm mohlo být provedeno nové kompletní kolo hackování.

46

6.1. HODNOCENÍ PORTÁLU Z HLEDISKA VLASTNICTVÍ Z podstaty hry vyplývá, že tato doba je čtyři hodiny. Díky nepřesnostem při stavbě a časomíře jsem se rozhodl tuto dobu navýšit na 4 hodiny a 10 minut. Tímto je možné efektivně negovat lidský faktor při měření času. Poté, co tento interval uběhne poprvé od postavení farmy, se k hodnocení přičítá pět bodů. Za každý další interval, kdy portál vydrží stát, se příčítá již jen jeden bod. Speciální ohodnocení prvního uplynutí je způsobeno tím, že pokud je farma dostatečně nová, stále se najde dostatek lidí, kteří ji budou chtít využít, avšak již z ní celkově neplyne takový užitek jedné straně, jako když je nově postavena. Pokud by portál vydržel déle, než počátečních cca 8 hodin, nabízí se dvě vysvětlení. Buď je založen na natolik odlehlém místě, že má pouze malou návštěvnost, nebo je pro nepřátelskou stranu výhodné ho nechat stát, a za cenu větší náročnosti z něj získává předměty. V obou případech již není přínos pouze pro jednu stranu veliký, tomu pak odpovídá i ohodnocení.

6.1.3. Faktor jednoduchosti odhalení Dalším, velmi zásadním parametrem je skutečnost, jak moc jednoduché je právě probíhající farmu najít pro agenta, který se vyskytuje v poli (a tedy nesleduje mapu na PC). Snadno odhalitelný je portál, na kterém se v průběhu krátkého časového okamžiku zobrazí jeho osazení velkým množstvím lidí. Naopak, mnohem hůře se bude odhalovat takový portál, který někdo postavil na nižší úroveň a jednotlivé rezonátory byly následně pouze upgradovány. Proto, pokud měl portál při plném postavení úroveň 5 a nižší, ale bořen byl již jako portál úrovně 7 nebo 8, je k jeho ohodnocení připočteno 10 bodů.

47

7. Implementace V této kapitole se budu zabývat samotnou implementací výše popsaných algoritmů a metod.

Obrázek 7.1: Schéma databáze

7.1. Získávání dat Získávání dat probíhá pomocí PHP skriptu, který je časovačem pouštěn pravidelně každých 15 minut (cron na Ubuntu Linux). Pomocí něj jsou ukládána surová data a probíhá

48

7.1. ZÍSKÁVÁNÍ DAT předzpracování dat pro statistickou analýzu. Data jsou upravena pro několik různých měst (např. Brno, Ostrava, Kroměříž). Čtvrt hodinový interval byl zvolen jako kompromis mezi bezpečností, kdy příliš časté dotazování serveru na data může vést k úplnému zablokování přístupu pro danou IP adresu, a mezi nutností mít co nejčerstvější data. Stahování dat a jejich ukládání probíhá po dávkách (dále také nazývané jako stránky), obvykle o velikosti 200 záznamů (akcí). Tato velikost, která výrazně překračuje výchozí limit 50 akcí na stránku, byla zvolena z důvodu, že podobnou velikost již používají některá JavaScriptová rošíření prohlížeče. Získávání dat nebude působit podezřele a zároveň je dostatečně veliké, aby bylo co nejrychlejší a efektivní. Pro každé město je na začátku zjištěno časové razítko nejnovějšího záznamu, které je použito jako zarážka pro načítané množství dat z minulosti. Díky tomuto opatření je možné velmi jednoduché zotavení dávky v případě, že získávání dat nebude po nějakou dobu možné. Zároveň jsou také načteny GUID identifikátory všech zpráv, které se nacházely v této sekundě. To je nutné díky tomu, že není zaručeno načtení všech záznamů z konkrétního časového razítka v jediném běhu skriptu. Jelikož je Ingress Intel poměrně vytížený systém, není vzácné, že načtení stránky dat neproběhne hned na první pokus, ale je třeba dotaz opakovat. Aby nemohlo docházet k přílišnému zahlcování serveru požadavky a k zablokování IP adresy, z které skript běží, proběhnou na každou stránku maximálně tři opakované dotazy. Pokud by i po takovémto počtu dotazů nebyla data úspěšně načtena, dochází k zahození (rollback) transakce a pokus se bude opakovat až při dalším spuštění skriptu. Tak je zaručeno, že žádná dávka nebude ztracena. Po načtení jsou data deserializována z formátu JSON do běžných PHP objektů. Poté dochází k uložení každé kompletní zprávy na dvou místech, a to v textovém formátu do ARCHIVE tabulky na MySQL serveru a jako objektu do MongoDB. MySQL databáze v tomto případě slouží jako záložní úložiště v případě ztráty dat, neboť je tato databáze zálohována, narozdíl od MongoDB, do dvou geograficky nezávislých úložišť.

49

7.2. PŘEDZPRACOVÁNÍ DAT PRO ANALÝZU Udaj Velikost databáze

Hodnota 2.4 GBytes

Množství zpracovávaných záznamu Průměrny denní přírustek

2 727 060 14 020 záznamu

Časový úsek

189 dni

Tabulka 7.1: Informace o zpracovávaných datech Dále probíhá zpracování načtených zpráv do formátu pro statistickou analýzu. Tento proces je zevrubně popsán v kapitole 4.2.1.

7.2. Předzpracování dat pro analýzu Skripty, které se starají o předzpracování dat do vhodného tvaru pro shlukovou analýzu, jsou rovněž implementovány v jazyce PHP. Sada se skládá z několika skriptů. Třída Portal reprezentuje jeden samostatný portál a jeho historii. Ve fázi předzpracování pak slouží zejména jako samostatná jednotka, které jsou předkládány jednotlivé akce. Ty jsou pak interně zpracovány do podoby historie vlastníků portálu. Třída PortalList je sice součástí preprocessing packu, ale její hlavní využití se nachází při implementaci cluster analýzy. Slouží převážně k filtraci portálů podle časového rozmezí, čímž zpřehledňuje celý kód shlukování. Samotné předzpracování je pak řízeno orchestračním skriptem, který provádí filtraci zpráv, jejich dekódování a stará se o volání vhodných metod v pomocných třídách. Výsledná data – seznam objektů typu Portal – jsou následně serializovány pomocí nativního PHP serializeru a vloženy do tabulky v databázi. Toto řešení poskytuje nejpohodlnější způsob, jak předávat data mezi preprocessing a clustering částí implementace.

7.2.1. Statistická analýza Statistická analýza je zpracována jako readonly REST webové API, ke které jsem nastavil přistup na adrese http://ingress2.varak.net/. 50

7.3. VYHLEDÁVÁNÍ SHLUKŮ Celé API je psáno jako webová aplikace pomocí MVC frameworku Nette v jazyce PHP. V současné době jsou data nabízena pouze ve formátu JSON, avšak celá aplikace je koncepčně připravena pro přechod na libovolný jiný formát serializace dat, a to včetně binárních formátů s pevným formátem zprávy, jako jsou například Google ProtoBuffers. Z celého MVC stacku se používá v zásadě pouze model. Controller se stará o zavolání vhodné metody modelu a serializaci výsledných dat do požadovaného formátu. Jelikož data nejsou zobrazována, view část frameworku je naprosto nevyužita. V minulosti, kdy byla tato webová služba hojně využívána, docházelo ke krátkodobému ukládání HTTP odpovědí do paměťové cache, aby se odlehčilo zátěži na databázi, která tak nemusela provádět nákladné operace (group by, join pomocí char atd.) při každém dotazu. Výsledky zůstávaly v cache po dobu 15 minut, tedy po dobu, kdy se data nemohla měnit. Pro komplexní nastavení a intuitivní způsob konfigurace jsem zvolil pro tento úkol software Varnish. Zrychlení by mohlo být také dosaženo používáním tzv. materializovaných pohledů (materialised views). Toto řešení však skýtá mnohé nevýhody. Jednak, materializované pohledy nejsou na databázi MySQL nativně podporovány, takže jejich implementace je buď záležitostí použití software třetí strany, nebo ručního vytvoření příslušných uložených procedur a triggerů, což skýtá velký prostor pro potenciálně fatální chyby v implementaci. Druhým důvodem pak je vysoké zatížení serveru v době, kdy je přijímáno velké množství dat a kdy lze předpokládat nejvyšší vytížení služby.

7.3. Vyhledávání shluků Samotné vyhledávání shluků používá výše vybranou metodu DBSCAN, která je vhodná pro svou rychlost a dobré vyrovnání se s odlehlými hodnotami (v tomto případě samostatně stojícími portály). Nejprve s pomocí třídy PortalList získám seznam portálů, které jsou relevantní pro daný časový úsek. Jsou to veškeré portály s definovanou minilální úrovní, které byly aktivní v intervalu začínajícím 5 minut před zadaným časem a končícím 5 minut po něm. 51

7.4. GRAFICKÉ ZNÁZORNĚNÍ VÝSLEDKŮ Každý z těchto portálů má nastavené číslo clusteru na hodnotu 0, které tím ukazuje, že zatím nepatří do žádného shluku. Následně, pokud portál nepatří do žádného existujícího shluku, se portálu přiřadí nejbližší volné číslo clusteru a najdou se veškeré zbývající portály se seznamu, které splňují podmínku maximální vzdálenosti a náležitosti do stejné frakce. Tyto portály jsou následně zařazeny do zpracovávaného shluku. V případě, že některý z okolních portálů již patří do existujícího clusteru, dojde k jejich sloučení pod číslem existujícího shluku. Zde by bylo možno dosáhnout minoritního zrychlení porovnámím velikosti shluků a následným použitím čísla většího z nich. Avšak při průměrné velikosti shluku okolo pěti portálů by tato optimalizace mohla být naopak kontraproduktivní. Tento krok je opakován pro veškeré portály ze seznamu. Posledním krokem shlukování je vyřazení příliš malých shluků (v současné době je experimentálně stanovena nejmenší velikost shluku na 5 portálů). Výsledné shluky jsou následně vypsány, aby mohly být použity pro jejich grafické znázornění.

7.4. Grafické znázornění výsledků Jelikož správná analýza získaných dat a další experimenty s nimi je jen velmi obtížně realizovatelná jen s pomocí textového umístění portálu (adresy portálu) a jeho jména, implementoval jsem jednoduché grafické rozhraní, na kterém se zobrazují jednotlivé shluky portálů přímo na mapě města Brna. Základním stavebním kamenem je zde Google Maps API, které poskytuje platformu, pomocí které lze jednotlivé portály patřící do shluků zobrazit na mapě. Klientská část API je psána v jazyce JavaScript, celý proces vykreslení proto probíhá v klientském prohlížeči. Vstupními daty jsou jednotlivé shluky portálů, kdy každý portál je reprezentován jeho názvem a GPS souřadnicemi. Vstupní data jsou pro jednoduchost zpracování předávána ve formátu JSON, který je ideální pro zpracování JavaScriptem.

52

7.4. GRAFICKÉ ZNÁZORNĚNÍ VÝSLEDKŮ

Obrázek 7.2: Grafické znázornění shluku

53

7.4. GRAFICKÉ ZNÁZORNĚNÍ VÝSLEDKŮ

Obrázek 7.3: Grafické znázornění shluku – větší přiblížení

54

8. Vyhodnocení experimentu Experiment jsem provedl s datovým vzorkem z oblasti Brna tak, jak jsem popsal v předchozí kapitole.

8.1. Vyhodnocení kritérií analýzy • Zpracovatelnost získaných dat – získaná data se ukázala jako zpracovatelná, jejich objem je dostatečný vzhledem ke zvoleným metodám předzpracování a následné analýzy. • Správnost zvolené metody – zvolená metoda DBSCAN se ukázala správnou, poskytuje pro vstupní sadu dat výsledky a nemá problém se vyrovnat s velkým počtem odlehlých dat, které nepatří do žádného se shluků – Zvolená metoda poskytuje pro zpracovávané data výsledky – Metoda je schopna se vyrovat s charakteristikou vstupních dat • Smysluplná velikost získaných farem – po vhodném vyladění parametrů metody jsou výstupem shluky portálů (farmy), jež vyhovují uvedeným kritériím. Ve zpracovávaném časovém rámci se podařilo najít větší množství shluků, které vyhovují těmto kritériím. – Alespoň 5 portálů v každé farmě – Ne více než 50 portálů v jedné farmě

8.2. Úspěšnost analýzy Z výchozích dat pro město Brno a okolí se mi podařilo získat celou řadu míst, kde se nacházejí shluky portálů vysoké úrovně. Následně jsem tato místa diskutoval se zkušenějšími členy brněnské Ingress komunity. 55

8.2. ÚSPĚŠNOST ANALÝZY Z této diskuse vyplynulo, že mnou nalezená místa odpovídají jejich empirické zkušenosti o umístění farem. Úspěšnost zvolené metody vyhodnocuji jako potvrzení domněnky o lokaci běžně známých shluků. Chování hráčů potvrzuje, že zvolená metoda dolování dat odpovídá realitě. Na zvoleném vzorku dat se podařilo dokázat, že použitá metoda je schopna zpracovávat skutečná data. Následně jsem zkusil zpracovat a analyzovat také získaná data pro město Ostrava. Z těchto dat se mi opět podařilo získat několik lokací s častým výskytem shluků portálů. Avšak, díky tomu, že se mi nepodařilo kontaktovat žádného ze zkušenějších ostravských hráčů, mohl jsem jejich polohu oproti reálným zkušenostem porovnat pouze přibližně. Z výše uvedeného tedy vyplývá, že mnou navrženou metodu je možno použít nad libovolným městem (i takovým, se kterým nemá hráč žádné zkušenosti) k nalezení osvědčených míst pro vytvoření farmy.

8.2.1. Experiment s maximální vzdáleností portálů ve shluku Pro relevanci výsledků, které poskytuje shlukování pomocí metody DBSCAN, je důležitým parametrem maximální vzdálenost jednotlivých bodů ve shluku, v tomto konkrétním případě maximální vzdálenost dvou portálů v rámci jedné farmy. Jako výchozí hodnotu jsem zvolil vzdálenost 150 metrů. Vyhodnotil jsem ji jako stále ještě rozumnou vzdálenost, kterou je hráč ochoten ujít mezi dvěma portály. V průběhu analýzy dat se však ukázalo, že je příliš velká a metoda má sklon ke spojování dvou shluků pomocí řetězce osamocených portálů. Takovýto výsledek se hrubě neshodoval s reálným průběhem hry a proto bylo potřeba přistoupit ke korekci tohoto parametru. Postupnými úpravemi vzdálenosti jsem nakonec dospěl k maximální vzdálenosti portálů 50 metrů, při které výsledné umístění a tvar shluků nejvíce odpovídá empirické zkušenosti.

56

9. Možnosti dalšího rozšíření Velmi zajímavou možností by mohlo být sledování opakujících se vzorců u vybraných portálů, které následně indikují, že dojde ke stavbě farmy. Případně tento pattern recognition zkusit rozšířit až na úroveň celých shluků nebo měst. Větší pozornost by se mohla věnovat sledování farmy ve stylu „Capture and Forgetÿ. Jedná se o případ, kdy jedna strana portál obsadí, postaví na level 8, provede jeden hack a poté ji již zanechá nepříteli, který je poblíž a portály ničí. Případným rozšířením by také mohla být další gamifikace celé hry, například za pomoci hráči definovaných „achievementůÿ. Popsané varianty dalšího vyhodnocování situací u hry Ingress znamená tak výrazné rozšíření tématu, které by mohlo být předmětem nového projektu.

57

10. Závěr Poté, co jsem provedl úpravu a analýzu dat výše uvedeným způsobem, jsem zjistil několik zajímavých informací. Prvním, málo očekávaným poznatkem bylo, že shluk portálů okolo VUT FIT, ačkoliv zdánlivě splňuje veškeré podmínky pro ideální místo na výstavbu Enlightened farmy, je takto využíván pouze sporadicky a jeho rizikovost pro Resistance je nízká. Další zjištění je spíše praktický postřeh toho, která část práce měla největší dopad na stav hry Ingress v Brně. Překvapivě je hráči nejvíce využívaná stránka se statistikami na brněnském portálu BEER (http://beer.pirozek.com). Hlubší analýza rizik pro všeobecné využití se nesetkala s příliš velkým ohlasem. Program vyhledal takové shluky portálů, které již byly v době vytvoření programu známy obou komunitám hráčů. Hráči si tedy sami našli nejvhodnější shluky portálů. Z toho je možné vyvodit, že realita hry pracovala stejně, jako použité metody datového dolování zpracované v implementaci. Tento fakt mi potvrdil správnost použitých metod dolování dat na výše popsaný příklad. Z toho také vyplývá, že rozhodovací proces je založen na stejných datech (i když jinak získaných) jako můj algoritmus. Je to způsobeno tím, že metody datového dolování byly nasazeny na již ustálený stav portálů. Bylo by zajímavé sledovat vývoj a vytváření shluků v nově vznikající lokalitě. Zde by již bylo možné vyhodnotit, jakým způsobem lze získat informace o poteciálních shlucích portálů před jejich skutečným vznikem. Také by bylo lákavé sledovat časové souvislosti. Z tohoto pohledu by bylo pozoruhodné sledovat rychlost reakce vytváření shluků (farem) bez informací získaných dolováním a s informacemi získanými dolováním. Zde by se tepve plně potvrdila efektivita datového dolování v reálném prostředí komunity hráčů. Z psychologického hlediska by bylo přínosem další využití takto získaných dat pro sledování chování komunity bez zásahu zvenčí (bez poskytnutí informací) a chování komunity s výhodně získanými informacemi k skrytým souvislostem vybrané strategie.

58

LITERATURA

Literatura [1] CouchBase – document-oriented No-SQL database [online]. [cit. 20. května 2014]. Dostupné na: . [2] DBSCAN [online]. [cit. 20. května 2014]. Dostupné na: . [3] Decision Tree [online]. [cit. 20. května 2014]. Dostupné na: . [4] Firebird: The true open source database for Windows, Linux, Mac OS X and more [online]. [cit. 20. května 2014]. Dostupné na: . [5] Forex Neural Backpropagation [online]. [cit. 20. května 2014]. Dostupné na: . [6] Microsoft SQL Server [online]. [cit. 20. května 2014]. Dostupné na: . [7] Mining for Groups Using Clustering Algorithms [online]. [cit. 20. května 2014]. Dostupné na: . [8] MySQL :: The world’s most popular open source database [online]. [cit. 20. května 2014]. Dostupné na: . [9] Oracle Database 12c [online]. [cit. 20. května 2014]. Dostupné na: . [10] PostgreSQL: The world’s most advanced open source database [online]. [cit. 20. května 2014]. Dostupné na: . [11] SQLite Home Page [online]. [cit. 20. května 2014]. Dostupné na: . 59

LITERATURA [12] Introduction to MongoDB [online]. 2014 [cit. 20. května 2014]. Dostupné na: . [13] PHP Manual [online]. 2014 [cit. 20. května 2014]. Dostupné na: . [14] Han, J., Kamber, M. a Pei, J. Data mining: concepts and techniques. [b.m.]: Morgan kaufmann, 2006. [15] Ingressia. Co je to Ingress? [online]. 2014 [cit. 20. května 2014]. Dostupné na: . [16] JSON. Úvod do JSON [online]. 2014 [cit. 20. května 2014]. Dostupné na: . [17] Klímek, P. SHLUKOVACÍ METODY V DATA MININGU. E+ M Ekonomie a Management/E+ M Economics & Management. 2008, roč. 2008, č. 2. [18] Manual, M. . R. The ARCHIVE Storage Engine [online]. 2014 [cit. 20. května 2014]. Dostupné na: . [19] Rychlý, M. Klasifikace a predikce. Ústav Informačních Systémů, VUT Brno. 2003. [20] Vařák, Martin. BEER API [online]. 2014 [cit. 20. května 2014]. Dostupné na: .

60

LITERATURA

Seznam použitých zkratek a symbolů SQL

Structured Query Language

XM

Exotic Matter

AP

Action Points

JSON

JavaScript Object Notification

REST

Representational State Transfer

61

SEZNAM OBRÁZKŮ

Seznam obrázků

62

2.1

Screenshot ze hry Ingress s výsledkem hacku . . . . . . . . . . . . . . . . .

8

2.2

Screenshot z webového rozhraní Ingress Intel . . . . . . . . . . . . . . . . .

9

2.3

Detail farmy Brno-Žabovřesky . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1

Graf porovnání rychlosti databáze . . . . . . . . . . . . . . . . . . . . . . . 20

4.1

Struktura objektu v JSON (Převzato z [16]) . . . . . . . . . . . . . . . . . 21

4.2

Struktura pole v JSON (Převzato z [16]) . . . . . . . . . . . . . . . . . . . 22

4.3

Struktura řetězce v JSON (Převzato z [16]) . . . . . . . . . . . . . . . . . . 22

4.4

Struktura čísla v JSON (Převzato z [16]) . . . . . . . . . . . . . . . . . . . 23

4.5

Diagram databáze pro API statistické analýzy . . . . . . . . . . . . . . . . 26

5.1

Diagram rozhodovacího stromu (převzato z [3]) . . . . . . . . . . . . . . . 31

5.2

Diagram neuronové sítě (převzato z [5]) . . . . . . . . . . . . . . . . . . . . 33

5.3

Ukázka shlukování pomocí K-means (převzato z [7]) . . . . . . . . . . . . . 37

5.4

Ukázka shlukování pomocí hierarchických metod (převzato z [7]) . . . . . . 39

5.5

Ukázka shlukování pomocí metody DBSCAN (převzato z [2]) . . . . . . . . 40

5.6

Graf rozložení získaných AP mezi frakcemi . . . . . . . . . . . . . . . . . . 43

5.7

Graf rozložení jednotlivých akcí v průběhu dne . . . . . . . . . . . . . . . . 44

7.1

Schéma databáze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

7.2

Grafické znázornění shluku . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

7.3

Grafické znázornění shluku – větší přiblížení . . . . . . . . . . . . . . . . . 54

SEZNAM OBRÁZKŮ

Seznam příloh Příloha A - Zpráva ve formátu JSON ["901 b 3 f 2 f 8 0 2 5 4 4 c 2 8 a 6 5 c 2 f d d 7 4 8 4 f 3 f . d " , 1363469414731 , { " plext ": { " text ": " PanBobek destroyed the Link Kostel N e j s v u 0 1 1 b t u 0 1 1 b j u 0 1 6 1 u 0 0 e d Trojice ( B ou 0 1 7 ee t u 01 1 b ch o v a 2502/2 A , 612 00 Brno - Brno Kru00e1lovo Pole , Czech Republic ) to Pomnu00edk padlu00fdm p u 0 1 5 9 u 0 0 e d s l u u 0 1 6 1 n u 0 0 e d k u 0 1 6 f m Rud ( B ou 0 1 7 ee t u 01 1 b ch o v a 2502/2 A , 612 00 Brno - Brno Kru00e1lovo Pole , Czech Republic ) " , " markup ": [ [" PLAYER " , { " plain ": " PanBobek " , " guid ": "1 d f 4 f 4 6 2 1 f a b 4 5 b 2 9 4 4 c d 9 e 6 e 9 a 5 e e 2 a . c " , " team ": " RESISTANCE " }] , [" TEXT " , { " plain ": " destroyed the Link " }] , [" PORTAL " , { " name ": " Kostel N e j s v u 0 1 1 b t u 0 1 1 b j u 0 1 6 1 u 0 0 e d Trojice " , " plain ": " Kostel N e j s v u 0 1 1 b t u 0 1 1 b j u 0 1 6 1 u 0 0 e d Trojice ( B ou 0 1 7e e t u0 1 1 bc h o va 2502/2 A , 612 00 Brno - Brno - Kru00e1lovo Pole , Czech Republic ) " , " team ": " ALIENS " , " latE6 ": 49227201 ,

63

SEZNAM OBRÁZKŮ " address ": " B o u 01 7 e et u 0 11 b c ho v a 2502/2 A , 612 00 Brno - Brno - Kru00e1lovo Pole , Czech Republic " , " lngE6 ": 16596125 , " guid ": " d 1 1 7 a 9 f f c 7 e 9 4 4 e 1 9 b 9 7 c d 2 1 d b f 8 c c 7 a .11" }] , [" TEXT " , { " plain ": " to " }] , [" PORTAL " , { " name ": " Pomnu00edk padlu00fdm p u 0 1 5 9 u 0 0 e d s l u u 0 1 6 1 n u 0 0 e d k u 0 1 6 f m Rud " , " plain ": " Pomnu00edk padlu00fdm p u 0 1 5 9 u 0 0 e d s l u u 0 1 6 1 n u 0 0 e d k u 0 1 6 f m Rud ( B ou 0 1 7e e t u0 1 1 bc h o v a 2502/2 A , 612 00 Brno - Brno Kru00e1lovo Pole , Czech Republic ) " , " team ": " ALIENS " , " latE6 ": 49227573 , " address ": " B o u 01 7 e et u 0 11 b c ho v a 2502/2 A , 612 00 Brno - Brno - Kru00e1lovo Pole , Czech Republic " , " lngE6 ": 16595859 , " guid ": "7736733 c 7 c 3 1 4 0 7 2 9 c b 4 1 c 1 0 4 a f c 9 f e 4 .11" }] ], " plextType ": " SYSTEM_BROADCAST " , " team ": " ALIENS " } }]

64