Implementace - Diplomka

From Waritkova wiki
Jump to navigation Jump to search

Analýza

Kritéria pro úspěšnost analýzy

  • 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ň pět portálů v každé farmě
    • Ne více než 50 portálů v jedné farmě

Implementace

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

OBRAZEK STRUKTYRY DB Z NAVICATU !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Získávání dat

Získávání dat probíhá pomocí PHP skriptu, který je pouštěn pravidelně každých 15 minut pomocí časovače (cron na Ubuntu Linux). Jsou pomocí něj ukládána jak surová data, tak probíhá předzpracování dat pro statistickou analýzu. Data jsou zpracovávány 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í se serveru na data může vést k úplnému zablokování přístupu pro danou IP adresu a 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 a proto nebude působit podezřele a zároveň je dostatečně veliké, aby bylo získávání dat co nejrychlejší a nejefektivnější.

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 množství dat z minulosti, které se bude načítat (díky tomuto je možné například velmi jednoduché zotavení pro 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 pomerně 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 tedy také k zablokování IP adresy z které skript běží), na každou stránku proběhnou maximálně tři opakované dotazy. Pokud by i po takovémto počtu dotazů nebyly data úspěšně získány, 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á data nebudou ztracena.

Po načtení jsou data deserializována z formátu JSON do běžných PHP objektů, jejich strukturu si je možno prohlédnout v kapitole XXXX%ADD%REF. 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 narozdíl od MongoDB zálohováno na do dvou geograficky nezávislých úložišť.

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 XXXX%ADD%REF.

Tabulka s velikostí dat, ze kdy jsou, kolik denně

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, které 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.

Statistická analýza

Statistická analýza je zpracována jako readonly REST webové API, ke kterému je možno přistupovat na adrese http://ingress2.varak.net/.

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 zde používá v zásadě pouze model. Controller se stará pouze 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 bylo možno odlehčit 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í možnosti nastavení a intuitivní způsob konfigurace byl pro tento úkol zvolen 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 tedy v době, kdy lze předpokládat nejvyšší vytížení služby.

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, tedy 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. Každý z těchto portálů má nastavené číslo clusteru na hodnotu 0, která znamená ž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 patří stejné frakci. 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í.

Grafické znázornění výsledků

Jelikož správná analýza získaných dat a další experimentace 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 je možno si zobrazit 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, s pomocí které je možno 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.

Vyhodnocení experimentu

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

Vyhodnocení kritérií analýzy

  • Zpracovatelnost získaných dat - získaná data se ukázaly 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ň pět portálů v každé farmě
    • Ne více než 50 portálů v jedné farmě

Úspěšnost analýzy

ú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í z 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.

Experimentace 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ů. Tato vzdálenost mi přišla jako stále ještě rozumná 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 tato vzdálenost 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.