Pattern Mining in Dynamic Graphs
Karel Vaculík · 2015
Tato prace se zabýva dolovanim z dynamických grafů, což jsou grafy, ktere se měni v case. V prvni casti je prezentovano dolovani castých vzorů z binarnich stromů. Konkretně je představena metoda, ktera umožňuje reprezentovat binarni stromy pomoci množiny podgrafů, na nichž je možne použit metody pro klasifikaci a detekci anomalii. Tato metoda zaroveň provadi generalizaci znacek uzlů, cimž usnadňuje praci s přilis různorodými znackami. Metodu jsme ověřili na stromech rezolucnich důkazů a objevili jsme pomoci ni neobvykle důkazy, ktere předtim nebyly zachyceny nastrojem pro automatickou detekci chyb. Pro analýzu binarnich stromů prezentujeme v teto casti prace take metodu založenou na dolovani ze sekvencnich dat a shlukovani. Pomoci teto metody je možne shlukovat a analyzovat různe strategie řeseni rezolucnich důkazů. Existujici algoritmy pro dolovani vzorů z dynamických grafů jsou typicky omezeny na specialni druhy vzorů, ktere zachycuji pouze urcite změny v grafech. V dalsi casti prace prezentujeme DGRMiner, algoritmus vhodný pro dolovani obecných castých vzorů. Tyto vzory jsou ve tvaru pravidel a umožňuji zachytit nejrůznějsi změny v grafech, jako je přidavani a mazani uzlů a hran, nebo změna znacek uzlů a hran. V navaznosti na dolovani castých vzorů popisujeme take rozsiřeni tohoto algoritmu pro detekci anomalnich vzorů. Anomalni vzory jsou takove, ktere se odchyluji od vzorů castých. Caste vzory pote slouži jako vysvětleni nalezených anomalnich vzorů. Užitecnost algoritmu DGRMiner je demonstrovana extrakci castých a anomalnich vzorů z emailove sitě ENRON a z rezolucnich důkazů. V zavěrecne casti prace je představen algoritmus WalDis pro dolovani diskriminativnich vzorů z dynamických grafů. WalDis se odlisuje od ostatnich algoritmů, u kterých jde větsinou o odlisovani celých statických grafů. WalDis naproti tomu odlisuje udalosti na lokalni urovni grafů, tedy udalosti spojene s jednotlivými uzly a hranami. Tento algoritmus použiva techniku nahodných prochazek, na kterou navazuje buď hladovým algoritmem, nebo genetickým algoritmem. Tyto techniky umožňuji hledat i nepřesne výskyty vzorů, což pomaha vypořadat se s vysokou variabilitou hodnot atributů a casových znamek v grafech při hledani vzorů. Diskriminativni vzory jsou užitecne pro zkoumani rozdilů mezi dvěma skupinami udalosti, respektive kontextů, za jakých tyto udalosti vznikaji. Ověřeni algoritmu WalDis proběhlo na grafech vytvořených z datových sad DBLP a ENRON, na kterých se povedlo rozlisit konference strojoveho uceni, respektive typy emailových zprav.