Vysoká škola báňská – Technická univerzita Ostrava, Fakulta bezpečnostního inženýrství, Katedra ochrany obyvatelstva
Bezpečnostní informatika III Ing. Pavel Šenovský, Ph.D. (2. vydání)
Ostrava 2010
Bezpečností informatika III
3
Obsah Úvod ...................................................................................................................... 5 1 Úvod do průmyslové automatizace .................................................................... 7 2 Úvod do tvorby SCADA systémů .................................................................... 13 2.1 Systém Promotic ....................................................................................... 13 3 Bezpečnostní aspekty automatizace ................................................................. 28 3.1 Zabezpečení perimetru firewallem ............................................................ 29 3.2 Duální počítače .......................................................................................... 30 3.3 Duální server ............................................................................................. 31 3.4 Filtrace provozu na bázi switch/router ...................................................... 32 3.5 Firewall jako vnitřní hranice ..................................................................... 33 3.6 Použití demilitarizované zóny (DMZ) ...................................................... 34 3.7 Oddělení sítí dvěma firewally ................................................................... 34 4 Jemný úvod do dataminingu ............................................................................ 36 4.1 Datamining obecně .................................................................................... 36 4.2 Zdroje údajů .............................................................................................. 40 5 Pravidlově orientované metody dataminingu................................................... 44 5.1 Rozhodovací pravidla ................................................................................ 44 5.2 Rozhodovací stromy .................................................................................. 48 5.3 Asociační pravidla ..................................................................................... 50 5.4 Pravidlově orientované metody dataminingu - příklad ............................. 51 5.4.1 Příklad rozhodovací strom ................................................................. 52 5.4.2 Příklad rozhodovací pravidla ............................................................. 57 5.4.3 Příklad asociační pravidla .................................................................. 59 6 Bayesovy filtry ................................................................................................. 67 7 Neuronové sítě .................................................................................................. 73 8 Evoluční algoritmy ........................................................................................... 79 Literatura ............................................................................................................. 82
4
Bezpečnostní informatika III
Bezpečností informatika III
5
Úvod Vážený studente, dostává se Vám do rukou učební text předmětu Bezpečnostní informatika III. Tato skripta se zaměřují především do dvou oblastí a to do úvodu do průmyslové automatizace – především systémů pro vizualizaci technologických procesů, tzv. SCADA systémů a úvodu do problematiky dolování informací. V obou případech výklad navazuje na předmět Bezpečnostní informatika II, jeho absolvování však není pro pochopení problematiky bezpodmínečně nutný, absolventi tohoto předmětu by však měli vidět další souvislosti. Část zaměřená na dolování informací navazuje na předměty Modelování rozhodovacích procesů, Statistika a Expertní systémy. Absolvování těchto předmětů není podmínkou nutnou pro absolvování tohoto předmětu, jejich absolventi však budou mít menší práci s pochopením jednotlivých metod dolování (protože by je již měli znát) a mohou se zaměřit na jejich aplikaci. Pro zpříjemnění čtení jsem se také rozhodl, zpracovat tento text formou vhodnou pro „distanční vzdělávání“, tak aby práce s ním byla co možná nejjednodušší. Z tohoto důvodu je text jednotlivých kapitol segmentován do bloků. Každá kapitola začíná náhledem kapitoly, ve kterém se dozvíte, o čem budeme v kapitole mluvit a proč. V bodech se pokusím shrnout, co byste po prostudování kapitoly měli znát a kolik času by Vám studium mělo zabrat. Prosím mějte na paměti, že tento časový údaj je pouze orientační, nebuďte proto prosím smutní nebo naštvaní když ve skutečnosti budete kapitole věnovat o něco méně nebo více času. Za kapitolou následuje shrnutí, ve kterém budou zdůrazněny informace, které byste si rozhodně měli zapamatovat. To, že jste správně pochopili probíranou látku, si budete moci ověřit pomocí kontrolních otázek, které by Vám měly poskytnout dostatečnou zpětnou vazbu k rozhodnutí, zdali jít dále nebo věnovat delší čas opakování. Pro zjednodušení orientace v textu jsem zavedl systém ikon: Průvodce studiem Slouží pro seznámení studentů s látkou, která bude v kapitole probírána. Čas nutný ke studiu Představuje odhad doby, který budete potřebovat k prostudování celé kapitoly. Jedná pouze o orientační odhad, neznepokojujte se proto, pokud Vám studium bude trvat o něco déle nebo budete hotovi rychleji.
6
Bezpečnostní informatika III
!
?
Vysvětlení, definice, poznámka U této ikony najdete vysvětlující text, poznámku k probíranému tématu, která problém uvede do širších souvislostí, popřípadě důležitou definice. Kontrolní otázky Na závěr každé kapitoly je zařazeno několik otázek, které prověří, zda jste problematice kapitoly dostatečně porozuměli. Pokud nebudete vědět odpověď na některou otázku, je to signál pro Vás, abyste se ke kapitole vrátili. Chvilka oddechu Text označený touto ikonkou neberte příliš vážně, je tam pro Vaše pobavení. Korespondenční úkol Tímto způsobem může být definováno zadání projektu, který máte zpracovat a odeslat svému vyučujícímu. Věnujte prosím pozornost Vašemu vyučujícímu, který Vám sdělí které úkoly je potřeba vypracovávat a odevzdávat . Příklad V takto označené části se setkáte s nějakým příkladem, který by měl osvětlit probíranou problematiku.
Přeji Vám, abyste čas, který strávíte s tímto textem, byl co možná nejpříjemnější a abyste jej nepovažovali za zcela ztracený. Autor.
Bezpečností informatika III
7
1 Úvod do průmyslové automatizace Průvodce studiem V této kapitole se podíváme na specifika průmyslové automatizace, především ve srovnání s nasazováním IT ve formách. Po prostudování této kapitoly budete umět co rozumíme průmyslovou automatizací jak se liší průmyslový počítač od počítače běžného proč se vůbec touto oblastí jako neinformatici zabývat Čas nutný ke studiu Pro prostudování této kapitoly budete potřebovat minimálně dvě hodiny.
Automatizace je základním nástrojem pro řízení technologických celků. Touto automatizací rozumíme zavádění automatizovaných systémů pro měření a regulaci procesů. Úkolem této regulace je zajistit plynulý (ve smyslu rychlosti procesu i kvality) provoz regulované soustavy. Nejprve se automatizace zaváděla do velkých výrobních linek, dnes se však automatizují prakticky všechny procesy od procesů výrobních, po systémy klimatizační ve velkých budovách až k regulaci kotle ve Vašem rodinném domě. Podívejme se na základní schéma regulační soustavy (obr. 1). Regulační soustavou přitom rozumíme jakoukoliv soustavu, která může být regulována.
Obr. 1: Obecné schéma regulační soustavy
8
Bezpečnostní informatika III
Aby bylo soustavu možno regulovat, je nutné mít zavedené nějaké mechanismy pro zjištění zpětné vazby na snahy regulovat (nebo jejich absenci), z tohoto důvodu jsou tyto soustavy opatřovány senzory. Senzory mohou být různého druhu, může se jednat o teplotní čidla, váhy, měřidla velikosti, ale třeba také kamery. Údaje získané z těchto senzorů jsou porovnávány s regulačními cíli a v případě, že se neshodují, pak je v soustavě provedena změna a celý proces se opakuje. Je očividné, že běžné PC není pro tento typ úkolů právě dělané, z tohoto důvodu se používají speciálně pro tento účel navržené počítače, tzv. PLC – Programable Logic Controler. Nejprve se podívejme, jak takový PLC vypadá (viz. obr. 2).
Obr. 2: Příklad PLC (převzato z [8]) PLC se liší od běžného PC v několika zásadních věcech. 1. Programy se nevyvíjejí přímo na něm, ale na běžném PC pomocí vývojových nástrojů dodaných výrobcem PLC. Programy nejsou obvykle přenositelné mezi PLC různých výrobců. 2. PLC je specializované, s vyšší životností, použitelné modulárně, tak aby jej bylo možno jednoduše rozšířit o nová rozhraní, kterých je zapotřebí v regulovaném procesu. Údaje získané ze senzorů je potřeba nějakým způsobem zpracovat nebo připravit k revizi operátorovi (dispečerovi/kontrolorovi/odpovědné osobě). Data ze senzorů je samozřejmě možné zobrazit tak, jak jsou zachytávána, tedy v tabulce jako sled měření s časovou značkou. Údaje v takové formě však jsou odpovědnou osobou obtížně interpretovatelné, obvykle se proto tyto údaje
Bezpečností informatika III
9
snažíme před jejich zobrazením vizualizovat v jednodušší formě. Právě k tomuto účelu jsou využívány tzv. SCADA systémy (Supervisory Control and Data Acquisition). SCADA systémy tvoří další vrstvu v logice průmyslové automatizace. Připomeňme si, že tu nejnižší tvoří PLC automaty regulující proces v reálném čase. SCADA systém, jelikož údaje musí, načíst (obvykle po sítí), zpracovat a zobrazit funguje ve skoro reálném čase – je zde již určité s trochou štěstí nepatrné zpoždění. Je důležité si taktéž uvědomit, že SCADA systém informace obvykle nebere přímo ze senzorů (prostřednictvím PLC), ale z nějakého k tomu určeného místa, obvykle výkonného databázového serveru. Někdy jsou tyto servery označovány jako real-timové databáze. Nedá se říci, že by přímé připojení SCADA – PLC pro získání informací nebylo možné, je však potřeba mít na paměti, že PLC je přizpůsobeno regulaci, ale není schopna poskytovat informace v podobě srovnatelné s relační databází. Na druhou stranu je jednoduché nastavit, aby PLC použil jako úložiště dat nějaký databázový server (spojení PLC – databáze) a propojit tento server se systémem SCADA (databáze – SCADA). Real timové databáze jsou v zásadě relačními databázemi s některými úpravami. Běžné relační databáze pracují se všemi údaji, které jsou v nich obsaženy prakticky bez rozdílu. Zadáte dotaz a počkáte si na odpověď. Doba čekání je přitom přímo úměrná počtu záznamů, které je třeba projít a může tak narůst až na minuty nebo desítky minut. V případě, že tato data jsou potřeba okamžitě je takový přístup očividně nepoužitelný. Realtimové databáze oproti tomu určitou záruku včasného doručení informací poskytují. Hlavní vlastností, která toto zaručuje, jsou tzv. realtimové transakce. Transakci přitom můžeme definovat jako skupinu operací, která splňují vlastnosti skrývající se pod zkratkou ACID (atomicita – konzistence – izolovanost – nevratnost). Atomicitou rozumíme, že transakce probíhá jako celek, tedy proběhne úspěšně celá, anebo neproběhne vůbec. Jinými slovy, v případě, že některá operace v rámci transakce selže, předchozí, úspěšně provedené operace v rámci transakce jsou revokovány a databáze se dostane do stavu jako před započetím transakce. Konzistence zaručuje, že databázový systém je transakcemi transformován z jednoho konzistentního stavu do druhého, opět konzistentního, stavu. Tato vlastnost souvisí s úplným provedením transakce. Nekonzistence jsou do databáze vnášeny buď chybným návrhem databáze, tento problém však transakce neřeší, nebo provedením pouze částečných změn (jako třeba pouze polovina požadovaných operací). Protože transakce se provede celá nebo vůbec – tento typ nekonzistence by neměl nastat.
10
Bezpečnostní informatika III
Izolovanost – transakce je izolována od zbytku databáze. Ostatním operacím/transakcím nejsou dostupné výsledky operací prováděných v rámci transakce do doby úplného dokončení této transakce. Nevratnost – transakce je neodvolatelná. Změny transakce je možné zvrátit pouze v průběhu transakce, po jejím dokončení jsou však tyto změny již nevratné. Realtimové databáze k těmto principům přidávají ještě časové omezení. Realtimová transakce musí být dokončena v určitém časovém intervalu. Tento interval obvykle nastavují tvůrci aplikací, které s těmito systémy pracují. Možná Vás napadne otázka, co s transakcemi, které neskončí včas. Důvodů přitom může být celá řada od technických – proces zachycený transakcí včas neskončil (stále trvá) až po to, že došlo k přetížení serveru, který nestačí vyřizovat transakce. Z tohoto pohledu je potřeba rozlišit přínos, jaký má dokončení této opožděné transakce: 1. opožděné dokončení transakce je přínosné – hodnota přínosu obvykle se ale obvykle nerovná přínosu ze včas dokončené transakce (např. aktuální hodnota senzoru výrobní linky vs. hodnota téhož senzoru z minulého dne). V takovém případě se databázový systém snaží transakci dokončit – obvykle ale opožděné transakci přiřazuje nižší prioritu tak, aby nebyla ohrožena aktuálnost nově zadávaných (čerstvých) údajů. 2. V okamžiku, kdy transakce ztratí hodnotu úplně nebo její hodnota klesne pod určitou úroveň, může databázový systém její dokončení stornovat, tak aby si uvolnil systémové zdroje pro vyřizování přínosných transakcí. Ne všechny typy transakcí lze stornovat. 3. Hodnota nedokončené transakce může dokonce poklesnout pod nulovou hodnotu – nedokončení transakce způsobuje další náklady. V takovém případě systém může naopak navýšit prioritu transakce, tak aby transakce byla přednostně dokončena a nepřinášela další náklady. V zájmu celého řešení samozřejmě je, aby opožděných transakcí bylo co nejméně. Tomu lze dopomoci (bohužel ne na 100% zajistit) s užitím vhodné konstrukce databáze, s použitím vhodně nakonfigurovaných indexů, s využitím rychlých RAM/flash disků, dostatečně výkonným hardware (a pokud nepostačuje jeden databázový server použít databázový cluster). Opatření budou záviset na významu aplikace, která s databází pracuje. Podívejme se, jakým způsobem dosud probraná zařízení vzájemně spolupracují (viz obr. 3). Údaje ze senzorů jsou ukládána do real-timové databáze, ze které jsou přímo zobrazována pomocí SCADA systémů na pracovních stanicích jednotlivých operátorů. PLC automaty přitom pracují autonomně na základě svých programů. V případě nějaké mimořádné události, může ale operátor ze svého stanoviště zasáhnout do technologického procesu přímo přenastavením jednotlivých ovládacích prvků technologie. Tímto způsobem efektivně obejde
Bezpečností informatika III
11
PLC automat. Takovým zásahem může být nouzové odstavení části nebo celé technologie. Alternativou k tomuto postupu je manuální ovládání prvků technologie na místě. V takovém případě k ovládacímu prvku musí odpovědná osoba fyzicky dojít a provést požadované změny. I tento postup je někdy nutné použít, zejména v případě, že v důsledku mimořádné události došlo k vyřazení/narušení přenosového kanálu nebo ovládací prvek na požadavky nereaguje. Podrobněji se bezpečnostními aspekty automatizace budeme zabývat ve stejnojmenné kapitole.
Obr. 3: Architektura průmyslové automatizace Pro časově náročnější operace nelze použít real-timovou databázi. Došlo by totiž k jejímu dalšímu zatížení, což by mohlo způsobit neschopnost práce v reálném čase. Z tohoto důvodu se data obvykle replikují na běžný, samostatný databázový server, se kterým pak normálně uživatelé pracují ať už přímo nebo prostřednictvím k tomu určených informačních systémů.
?
Kontrolní otázky 1. Co jsou to SCADA systémy a k čemu slouží? 2. Jako úlohu plní PLC automaty? 3. Čím se liší real-timové databáze od běžných relačních databází? 4. Co je to transakce?
12
Bezpečnostní informatika III
5. Vysvětlete principy ACID transakcí.
?
Úkoly k zamyšlení Zamyslete se nad možnými ohroženími automatizační části technologického procesu. Dále v těchto skriptech tuto představu korigujte s dalšími informacemi, které získáte.
Bezpečností informatika III
13
2 Úvod do tvorby SCADA systémů Průvodce studiem Dozvíte se jaké prostředky a jakým způsobem se používají pro tvorbu SCADA systémů. Zaměříme se také na praktické ukázky tvorby v systému Promotic. Po prostudování této kapitoly budete umět vytvořit jednoduchou aplikaci v systému Promotic Čas nutný ke studiu Pro prostudování této kapitolu budete potřebovat minimálně 4 hodiny (pokud budete zkoušet vytvořit a pochopit aplikaci v systému Promotic).
2.1 Systém Promotic Tvůrcem systému Promotic [3] je česká firma MICROSYS s.r.o. Promotic je koncipován jako jednodušší systém (v porovnání s některými zahraničními konkurenty jako je InTouch firmy Wonderware a další), který však umožňuje vytváření plnohodnotných SCADA aplikací. Pro náš účel základního seznámení s možnostmi SCADA systémů je zajímavé některé jeho vlastnosti, protože Promotic je: malý plně lokalizovaný jeho demo, které budeme pro naše pokusy používat je ke stažení z domácích stránek výrobce.
!
Upozornění Pro optimální pochopení problematiky by bylo vhodné, abyste v této chvíli stáhli a nainstalovali demo verzi systému Promotic a příklad si zkoušeli zpracovat přímo v něm. Vzhledem k tomu, že v rámci semestrálního projektu musíte zpracovat jednoduchou vizualizaci právě v systému Promotic – budete jej nejspíš stejně dříve nebo později instalovat.
Demo verze má vlastnosti plné verze, pouze je omezena počtem prvků, se kterými je možno pracovat, což nám pro naše experimentování bude naprosto dostačovat.
14
Bezpečnostní informatika III
Nejprve si proberme nějaký jednoduchý problém a způsob jeho řešení. Zkusme si tímto způsobem zpracovat fungování UPS systému chránícího nějaký počítač. Úkolem UPS je chránit počítač proti přepětí nebo podpětí v elektrické síti. V okamžiku, kdy taková situace nastane, je elektrická energie dodávána připojenému zařízení z baterie. Zkusme si tuto situaci znázornit na nějakém schématu (viz obr. 4).
Obr. 4: Zapojení UPS Z popisu problému vyplývá, že musí existovat senzor, který bude měřit napětí na vstupu UPS a v případě, že jeho hodnota poklesne/přesáhne nastavenou mez, začne se energie odebírat z baterie a odběr z baterie bude pokračovat, dokud nedojde k navrácení hodnot napětí do povolených mezí nebo úplné vyčerpání baterie. Tedy náš SCADA systém bude muset zachytit: stav baterie, aktuální napětí na vstupu, horní mez napětí, dolní mez napětí. Samozřejmě bychom určitě byli schopni vymyslet další vylepšení, jako je třeba indikace běhu počítače, míra nabití baterie, při které dojde k automatickému vypnutí, životnost baterie apod. Vybaveni základní představou o potřebách řešení našeho problému, můžeme se pustit do jeho řešení pomocí systému Promotic. Novou aplikaci vytvoříme pomocí menu Aplikace -> Nová aplikace. Při experimentování s tímto systémem se snažte každou aplikace vložit do samostatné složky, předejdete tak možným konfliktům v názvech zdrojů apod. Po vytvoření nové aplikace se nám objeví základní vývojové prostředí systému Promotic (viz obr. 5). Levá polovina obrazovky nám představuje strukturu aplikace. Jelikož naše aplikace je nová a tedy prázdná, objevuje se v ní pouze kořen (aplikace) a základní panel nástrojů (toolbox).
Bezpečností informatika III
15
Naším prvotním úkolem bude dotvořit tuto strukturu tak, aby obsahovala všechny prvky, které jsme vymysleli výše.
Obr. 5: Základní obrazovka nové aplikace Stavební kameny, ze kterých sestavíme aplikaci, vytvoříme jednoduše, tak že klikneme pravým tlačítkem myši na kořenovém uzlu aplikace. Objeví se kontextové menu, které nám umožní provádět s daným uzlem celou řadu činností. Názvy většiny z nich jsou poměrně výstižné, takže byste neměli mít problémy s orientací. Nás bude zajímat především první položka kontextového menu a to Nový objekt. Máme možnost tímto způsobem vytvořit celou řadu různých typů objektů. Některé z nich si blíže popíšeme, nejdříve si však všimněte pojmenování jednotlivých objektů - všechny začínají PmNěco (PmFolder, PmNumber, …). Zkratka Pm je zkratkou Promotic. Druhá část názvu je tvořena popisem charakteru objektu v angličtině, česká verze Promotic ale rovno v menu nabízí český překlad názvu. Nyní již k jednotlivým objektům: 1. PmFolder umožňuje strukturovat prvky aplikace do jednotlivých složek. Tímto způsobem se může zpřehlednit struktura aplikace. Složky je výhodné používat především ve větších (normálních) projektech – pro naši miniaplikaci nebude mít až takový význam. 2. PmNumber umožňuje pracovat s jednou číselnou hodnotou. Ve vlastnostech tohoto objektu přitom můžeme specifikovat, o jaký typ čísla se bude jednat. 3. PmString umožňuje pracovat s textovými řetězci. Promotic zná celou řadu dalších objektů, ale my budeme používat pro naši aplikaci už pouze PmTimer (časovač), ke kterému se dostaneme až trochu později. Jaké objekty budeme potřebovat:
16
Bezpečnostní informatika III
1. 2. 3. 4.
stav baterie – číslo (PmNumber), aktuální napětí na vstupu – číslo, horní mez napětí - číslo, dolní mez napětí – číslo.
Všechny proměnné budou typu číslo, u všech můžeme ponechat i nastavení celočíselného typu (integer). Všechny tyto prvky postupně vložíme do naší aplikace (pravým tlačítkem na uzlu aplikace -> nový objekt -> PmNumber). Výsledek našeho snažení by měl vypadat následovně (viz obr. 6).
Obr. 6: Tvorba základních prvků aplikace Máme vytvořený základní rámec, ve kterém naše aplikace bude fungovat, je však potřeba vytvořit nějaké grafické uživatelské rozhraní, které nám umožní vizualizovat a případně ovládat náš „technologický proces“. V Promotic k tomuto účelu slouží editor obrazů.
Obr. 7: Vlastnosti PmPanel
Bezpečností informatika III
17
Obrazem se v tomto případě rozumí obrazovka se všemi vizuálními i ovládacími prvky, kterou bude mít k dispozici operátor procesu. K tomuto editoru se dostaneme tak, že vytvoříme nový objekt typu PmPanel (okno), který má obsahovat kompletní GUI aplikace a klikneme na tlačítko editace grafického obsahu (viz obr. 7). Kromě výše uvedeného tlačítka si všimněte zaškrtávacích polí přímo vedle něj. otevřít při startu aplikace způsobí, že tento obraz se automaticky zobrazí po spuštění aplikace. zařadit do seznamu obrazů umožňuje zavést obraz do seznamu všech obrazů s nastavenou touto vlastností. Operátor se ze své aplikace pak může mezi jednotlivými obrazy přepínat. Pokud obraz nebude v seznamu obrazů, neznamená to, že bude úplně nepřístupný, jeho zpřístupnění bude ale nutné prostřednictvím nějakého grafického prvku jiného obrazu, třeba tlačítka. nezávislé časování obrazu vyjme obraz ze systémové obnovy obrazů. Takový obraz je pak aktualizován pouze manuálně nebo automaticky systémem Promotic na základě námi definované procedury časovače. při hromadném zavření obrazů ponechat tento obraz otevřen – měl by být zatržen pro kriticky důležité obrazy, tak abychom zajistili, že důležité informace z technologického procesu budou vždy k dispozici. Zkusme sestavit aplikaci. Aplikaci sestavujeme z jednotlivých konstrukčních prvků, které vybíráme z Palety prvků (viz obr. 8). Aplikace, resp. její základ se sestavuje pouhým klikáním, není k němu tedy potřeba programování, pro oživování jednotlivých prvků, již programování ale může být potřeba.
18
Bezpečnostní informatika III
Obr. 8: Paleta prvků Už víme, jaké informace chceme zobrazovat nebo získávat od uživatele. Z hlediska prvků aplikace je můžeme rozdělit do dvou skupin: prvky pro zadávání údajů prvky pro vizualizaci údajů Kromě těchto dvou skupin máme k dispozici ještě třetí skupinu prvků, která slouží pro vizuální dotvoření aplikace, ale je statického charakteru – tedy není napojena na nějaké zdroje dat apod. Horní a dolní mez bude potřeba nastavit. Vzhledem k povaze těchto parametrů by se hodilo nějaké táhlo. V Promotic máme k dispozici táhlo a táhlo s vodorovnou nebo svislou stupnicí (paleta prvků -> zadávací přístroje). Pro naši aplikaci použijeme táhlo s vodorovnou stupnicí. Prvek vložíme do pracovní plochy tak že na jeho název dvakrát klikneme (zmizí panel prvků) a klikneme na pracovní plochu editoru obrazů v místě, kam chceme prvek umístit. Prvek můžeme metodou drag & drop přesunovat dle potřeby a také měnit jeho velikost. Implicitně se stupnice objeví v intervalu 0 – 100, což nám zcela jistě nevyhovuje. Zatím však ponecháme tento prvek tak jak je. Vytvoříme celkem dvě stupnice s vodorovným táhlem. Stav baterie a aktuální napětí, jsou hodnoty, které budeme chtít monitorovat. Pro vytvoření prvků zobrazujících stav a napětí použijeme opět paletu prvků, tentokrát ale použijeme Měřicí přístroje a zde použijeme prvek Ručkový s nadpisem. Prvek na pracovní ploše vytvoříme dvakrát, tedy pro obě měřené veličiny. Výsledek našeho snažení by měl vypadat podobně jako na obr. 9.
Bezpečností informatika III
19
Obr. 9: Základní rozhraní aplikace Měřicí přístroje, podobně jako přístroje zadávací, jsou nastaveny na interval 0 – 100. Nyní je potřeba změnit vlastnosti jednotlivých prvků obrazu tak, aby odpovídaly úkolům, které jim hodláme svěřit. Dolní mez by měla umožňovat výběr v intervalu tak mezi 150 – 200 V. Jako předvolená hodnota pro vysokou citlivost UPS se obvykle zadává 190V. Horní mez by měla umožňovat výběr v intervalu 240 – 300 V s předvolenou hodnotou okolo 250 V. Stupnice měřicího přístroje pro stav baterie může zůstat tak jak je, tedy v intervalu 0 – 100, což odpovídá procentu nabití baterie. Měřicí přístroj pro aktuální napětí na vstupu by měl být v intervalu 0 – 350. Vlastnosti jednotlivých prvků zobrazíme dvojitým kliknutím na prvku. Začněme se zadávacím prvkem pro dolní mez. Zadávací přístroj jako celek je tvořen dvěma prvky – zadávacím táhlem a textovým popisem (obsahuje implicitně nápis Zadavatel). Zkusme nejprve změnit tento popisek. Ve vlastnostech klikneme na položku vložené prvky (tlačítko +). V okně, které se nám objeví, vybereme TextTitle, pod kterým se skrývá titulek, který chceme změnit a klikneme na tlačítko Editace. Zde se již nachází vlastnost text, kterou přepíšeme na Dolní povolená mez [V]. Všechna okna vlastností postupně zavřeme kliknutím na tlačítko OK. Vzhled oken vlastností se zvýrazněnými vlastnostmi popsanými výše je znázorněn na obr. 10.
20
Bezpečnostní informatika III
Obr. 10: Změna popisku zadávacího prvku Stejným způsobem budeme postupovat u druhého zadávacího prvku, ovšem s tím, že popisek bude Horní povolená mez [V]. Analogickým způsobem budeme postupovat i u měřících přístrojů s popisky Aktuální napětí [V] a Stav baterie [%]. Nyní provedeme nastavení mezí jednotlivých prvků, tedy kromě prvku stav baterie, kde nám rozsah 0 – 100 vyhovuje. Změnu provedeme opět ve vlastnostech prvku. Začněme opět s prvkem Dolní povolená mez. Ve vlastnostech tohoto prvku můžeme nalézt táhlo, která nám umožňuje nastavit rozsah funkčnosti zadávacího prvku. Budou nás zajímat především vlastnosti dolní mez (150), horní mez (200) a kam zapisovat (190). Kam zapisovat je hodnota, která je v táhlu předvolená. Můžeme změnit směr přírůstku, tedy zda stupnice stoupá nebo klesá. Nastavení naleznete na obr. 11. Stejný způsobem nastavíme i Horní povolenou mez. Parametry nastavení budou následující: dolní mez 240, horní mez 300, kam zapisovat 250. Horní a dolní mez měřicího přístroje můžeme nastavit přímo v základní obrazovce (viz obr. 12) vlastností měřicího přístroje: dolní mez 0, horní mez 350, kam zapisovat ponecháme tak jak je. Výsledek našich úprav by měl vypadat podobně jako na obr. 13. Grafický vzhled je hotov, zkusíme tedy aplikaci spustit, předtím je však nutné obraz zkompilovat. Kompilace se provede kliknutím na patřičné tlačítko na panelu nástrojů (třetí a čtvrté zleva). Editor obrazů zvládá dva typy kompilace a to kompilaci úplnou nebo inkrementální.
Bezpečností informatika III
21
Obr. 11: Nastavení táhla Úplná kompilace provede zkompilování obrazu, zatímco inkrementální provede pouze přeložení částí, které se od poslední kompilace změnily. Výhodou tohoto typu kompilace je úspora času. Pro naši aplikaci, která se skládá pouze ze čtyř prvků, ale úspora času bude prakticky nulová. Po provedení kompilace můžeme editor obrazů uzavřít.
Obr. 12: Vlastnosti měřicího přístroje
22
Bezpečnostní informatika III
Obr. 13: Vzhled obrazu po změně vlastností jednotlivých prvků Spuštění aplikace provedeme z hlavního vývojového prostředí, tam jsme také definovali jednotlivé proměnné aplikace, kliknutím na ikonu semaforu. Nezapomeňte, že pokud svůj obraz chcete vidět, je potřeba zaškrtnout volbu otevřít při startu aplikace ve vlastnostech obrazu (popřípadě obraz přidat do seznamu obrazů). Běhové prostředí Promotic bude vypadat následovně (viz obr. 14).
Obr. 14: Běhové prostředí Promotic V běhovém prostředí můžete manipulovat s jednotlivými ovládacími prvky, nicméně nyní ať s nimi manipulujeme, jak chceme, tak se nic neděje, pouze se posune táhlo. Bylo by samozřejmě lepší, kdyby se něco dělo. Koneckonců jsme pro naši aplikaci vymysleli „pokročilou“ funkčnost. Problém je
Bezpečností informatika III
23
v tom, že obraz, který jsme vytvořili, není napojen na proměnné a také, že zde není obsaženo nic dynamického, co by se měnilo. Za normálních okolností by prvky obrazu byly napojeny na dynamický zdroj dat, nějaký skutečný senzor, který by snímal v čase se měnící veličinu a tu by přenášel do naší aplikace (buď přímo nebo zprostředkovaně s pomocí data historianu). V našem případě toto není možné, a proto dynamické chování budeme muset simulovat přímo v prostředí Promotic. K této simulaci využijeme prvek PmTimer (časovač). Časovač nám umožní, abychom v pravidelných intervalech spouštěli určitý skript, který bude provádět simulaci tohoto dynamického chování. Zkusme si navrhnout algoritmus, jakým by tento prvek měl fungovat. Základem simulace dynamického chování bude generátor náhodných čísel – ten nám bude simulovat kolísání napětí v síti a na něj bude reagovat UPS. Jak si všimněte na obr. 15, jsou vlastnosti časovače jiné než vlastnosti jiných prvků, se kterými jsme se dosud setkali. Předně zde existuje přehled událostí, které jsou s prvkem spojeny. V případě časovače těmito událostmi ObjectStart, který se provede po spuštění časovače ObjectStop, který se provede při zastavení časovače TimerTick se provede pokaždé po uplynutí určitého časového intervalu, tento interval můžete nastavit na záložce časovač. Implicitně je interval časovače nastaven na 1 sekundu, což pro náš účel bude naprosto vyhovovat. Procedura, která bude výše uvedený algoritmus vykonávat, může vypadat třeba takto: dim n, zmena, proud, dmez, hmez, stav set proud = Pm(„/NapetiVstup“) set dmez = Pm(„/DolniMez“) set hmez = Pm(„/HorniMez“) set stav = Pm(„/StavBaterie“) n = rnd() if n < 0.5 then zmena = -1 else zmena = 1 end if if (proud.value + zmena) < dmez.value or (proud.value + zmena) > hmez.value then if (stav.value > 0) then stav.value = stav.value - 1 else if stav.value < 100 then stav.value = stav.value + 1 end if
24
Bezpečnostní informatika III
if (proud.value + zmena) >= 0 then proud.value = proud.value + zmena
Obr. 15: Vlastnosti časovače (PmTimer) Možná si řeknete, co to proboha je, pravdou ale je, že skript samotný je velmi jednoduchý a dalšími podrobnostmi k programování v rámci Promotic Vás zatěžovat nebudu. Skripty v Promotic jsou tvořeny v jazyku VisualBasic for Applications, jedná se o stejný jazyk, jako se používá pro tvorbu maker v MS Office nebo balíku Corel Draw. VisualBasic má některé příjemné vlastnosti jako je třeba, že nevyžaduje před použitím deklarovat proměnnou (vůbec neškodí, když ji ale nadeklarujete) a některé další vlastnosti pro které je tento jazyk oblíbený zejména mezi programátory začátečníky. V našem skriptu jsou obecně nadeklarovány pomocí příkazu dim proměnné, které budeme využívat. Do proměnné n budeme ukládat výsledek generátoru náhodných čísel. Do proměnné zmena budeme ukládat změnu aktuální hodnoty proudu na základě generátoru náhodných čísel.
Bezpečností informatika III
25
Proměnné dmez, hmez, stav a proud nám budou sloužit pro propojení na systémové objekty, které jsme si nadefinovali v základním rozhraní Promotic. Propojení mezi těmito proměnnými a objekty Promotic se provádí příkazem set. Např. set proud = Pm(„/NapetiVstup“) provede propojení proměnné proud s objektem Promotic NapetiVstup. Pokud by objekty Promotic byly obsaženy v nějaké složce, bylo by nutné uvést celou cestu k proměnné. V mém případě se ale objekt nachází přímo v kořenové části, takže se specifikaci cesty mohu vyhnout. Funkce rnd() provede vygenerování náhodného čísla v intervalu <0; 1). Na základě tohoto náhodného čísla určíme velikost změny, pokud náhodné číslo bude menší než 0.5, pak se budeme snažit změnit napětí tak, že z jeho velikosti odebereme 1V. V případě, že vygenerované číslo bude větší nebo rovno 0.5 naopak k aktuální velikosti proudu přičteme 1. Tímto způsobem simulujeme náhodné kolísání proudu v elektrické síti. Poslední podmínka nám umožní pracovat s velikostí nabití baterie. Provedeme kontrolu, zda velikost proudu po změně je v povolených mezích. Pokud tomu tak skutečně je, pak k stavu nabití baterie přičteme 1 (baterie se dobijí). Pokud je aktuální hodnota proudu mimo povolený rozsah tak od stavu baterie naopak 1 odečteme – systém je napájen z baterie. Zajisté jste si také všimli, že nepoužíváme proud a další proměnné samy o sobě, ale používáme je jako objekty. K samotné hodnotě proudu tak můžeme přistoupit prací s vlastností value např. proud.value. Je příjemnou vlastností (která však za určitých podmínek může být zdrojem chyb), že se nemusíme starat a datové typy – VisualBasic for Applications provede automatické přetypování. Jediné, co nám zbývá v naší aplikaci provést je spojení prvků obrazu s objekty definovanými v hlavním editačním okně promotic. Spojení se provádí ve vlastnostech prvku. Pro táhla je to vlastnost kam zapisovat. Tentokrát ovšem nevyplníme předpřipravené textové pole, ale klikneme na tlačítko vedle něj. Objeví se nové dialogové okno, které nám umožní definovat datovou vazbu. My budeme chtít napojit prvek obrazu na objekt Promotic, který jsme definovali, proto budeme definovat PP Vlastnost Pmobjektu – ve které můžeme kliknutím na tlačítko … vybrat objekt Promoticu, na který chceme propojení nadefinovat. Je potřeba nastavit vlastnost, která se má pro přebrání hodnoty použít, v našem případě to bude hodnota value. Znázornění dialogových okem propojení naleznete na obr. 16.
26
Bezpečnostní informatika III
Obr. 16: Nastavení propojení obrazu s objektem Promotic. Analogicky propojíme i ostatní prvky obrazu s objekty Promotic. Aplikaci zkompilujeme a můžeme si ji prohlédnout, nyní by již měla také něco ukazovat.
! ?
Důležité Pokud Vám nešlo zprovoznit výše uvedený příklad, pak samozřejmě můžete konzultovat, ale můžete vyzkoušet také jiný příklad, který je podrobně vysvětlen přímo v dokumentaci systému Promotic. Dokumentace je v češtině, takže se není třeba obávat. Kontrolní otázky 1. Jaký je rozdíl mezi inkrementální a úplnou kompilací. Jaké činnosti prování objekt PmTimer. Jakým způsobem se můžeme dostat k jednotlivým definovaným
Bezpečností informatika III
27
obrazům v rámci běhu aplikace Promotic.
?
Samostatná práce 1. Přidejte do našeho projektu (automatizace UPS) signalizaci, zda je systém napájen z elektrické sítě, nebo používá baterii. Korespondenční úkol. Vymyslete a vypracujte v systému Promotic automatizační úkol. Tento úkol nemusí být rozsáhlý, je ale potřeba abyste jej sami vymysleli a sami zpracovali tak, aby skutečně něco dělal (hýbaly se ručičky apod.). Prováděná činnost musí mít samozřejmě nějaký účel.
28
Bezpečnostní informatika III
3 Bezpečnostní aspekty automatizace Průvodce studiem V této kapitole se budeme zabývat důvody, proč je nutné věnovat pozornost zabezpečení automatizační části podniku a jaké následky může mít selhání této části. Po prostudování této kapitoly budete vědět jaké problémy s bezpečností se řeší jaké jsou úskalí metod propojení průmyslové (automatizační) a běžné sítě Čas pro studium Pro prostudování této kapitoly budete potřebovat přibližně dvě hodiny.
SCADA systémy byly ve svém prvopočátku jako nenáročné, levné a spolehlivé systémy. Těchto úkolů dosahovaly přenesením práce operátora ze samotné technologie na pracoviště operátorů, kteří tuto technologii spravují na dálku. Koncepčně v tomto původním pohledu je automatizační část naprosto samostatnou vůči běžné počítačové síti. S postupem doby a především s prudkým rozvojem technologií založených na Internetu se ale mění pohled na postavení SCADA systémů v podniku. Automatizační část je vnímána jako velmi cenný zdroj informací, který musí být zapojen do běžných „neautomatizačních“ procesů, tak aby firma jako celek dosáhla vyšší efektivity. Heslem dneška je taktéž propojování různých podniků do podnikatelských clusterů. Propojování se přitom může dít na úrovni personální, ale také na úrovni sdílení informací umožněním přístupu dalších subjektů k informačním systémům podniku popřípadě určitých částí sítě. Tento přístup, ačkoliv je z finančního hlediska výhodný, může s sebou nést také rizika bezpečnosti počítačové sítě jako celku, včetně možného úniku informací nebo vyřazení z činnosti některé části technologie. Nové technologie s sebou nesou nové příležitosti ke zvýšení efektivity podniku, spolu s tím však jdou ruku v ruce nové hrozby, které je nutné zvládnout. Obecně se snažíme, co možná nejvíce oddělit část automatizační od běžné počítačové sítě, rezignovali jsme však již na úplné oddělení těchto sítí. Jednotlivá automatizační technika by měla být oddělena (izolována od Internetu). Ovládání po Internetu za splnění určitých bezpečnostních opatření je možné, ale ne na
Bezpečností informatika III
29
přímo, mezi vzdáleným pracovištěm operátora a zařízením musí být infrastruktura pro filtraci síťového provozu. Základní součástí opatření k zajištění bezpečnosti nejen automatizační části je ošetření perimetru (hranic) sítě. Hranicí rozumíme jakékoliv zařízení umožňující komunikaci s vnějším světem mimo síť podniku, tedy pevné linky, modemy, GPRS, Wi-fi přípojné body, Bluetooth zařízení apod. Pro údržbu všech zařízení je potřeba mít plně zmapovanou používanou infrastrukturu. Jednotlivá zařízení používaná v automatizaci jsou obvykle používaná déle než běžná výpočetní technika. Z tohoto důvodu je nutné zejména v souvislosti se zavádění nových metod řízení, provádět pravidelnou aktualizaci systému v těchto zařízení obsaženého, je totiž možné, že po tomto zařízení budeme chtít něco, na co původně toto zařízení konstruováno nebylo. Samozřejmostí by mělo být taktéž tvorba bezpečnostní politiky práce s těmito zařízeními a její striktní dodržování. Zaměřme se na jednotlivé typy zabezpečení oddělování co možná největší části automatizační sítě. 3.1 Zabezpečení perimetru firewallem Vnější svět oddělíme od sítě jednoduchým použitím firewallu, viz obr. 17.
Obr. 17: Oddělení sítě pomocí firewallu (převzato z [5]) Firewall se obvykle překládá jako požární stěna. Jeho základním úkolem je filtrovat síťový provoz mezi sítěmi. Pomocí tohoto zařízení je tedy možné nastavit protokoly, porty, a zařízení (podle IP adresy) jejichž komunikace může přes firewall projít. Realizace firewallu jako přehrady oddělující vnější svět od počítačové sítě organizace je správnou volbou, která ovšem neřeší všechny bezpečnostní aspekty, které je nutné vzít v úvahu při zabezpečování sítě.
30
Bezpečnostní informatika III
Množství komunikace, která projde firewallem je relativně velké. Jsou přes něj zpřístupněny některé služby sítě, jako jsou třeba WWW servery apod., koncové stanice mohou přistupovat ke službám internetu, některé služby sítě mohou být vystaveny kontraktorům nebo jinak spolupracujícím firmám, u kterých nemáme plnou kontrolu nad tím, jakým způsobem budou síťové prostředky využívat. Dalším problémem, který tato architektura neřeší je komunikace uvnitř sítě. Firewall ovlivňuje pouze komunikaci, která je směrována přes něj. Zařízení za firewallem, uvnitř sítě však mohou komunikovat přímo, což tato architektura zabezpečení neřeší. Přes tyto výhrady je zabezpečení vnějšího perimetru organizace první věcí, která by měla být provedena, kromě ní je však potřeba realizovat další ochranná opatření. 3.2 Duální počítače Možností jak zabezpečit separaci automatizační části od běžné sítě je využít tzv. duální počítače. Graficky je tento koncept znázorněn na obr. 18.
Obr. 18: Použití duálních počítačů (převzato z [5]) Duálními počítači rozumíme počítače disponující dvěma síťovými kartami, které slouží pro připojení do obou druhů sítě (automatizační a běžné). Nevýhody tohoto konceptu jsou jasně patrné. Předně je to nutnost pořizovat dvě síťové karty na každý počítač, který má pracovat v obou sítích, což je nepraktické. Ke každé takové stanici bude nutné přivést dvojici síťových kabelů, což také není obzvláště výhodné.
Bezpečností informatika III
31
Další nevýhodou je že tyto počítače slouží jako most mezi oběma sítě, k čemuž běžný počítač není úplně vhodně vybaven. Tyto počítače jsou tak vystaveny útokům, které ohrožují běžnou síť a mohou je propagovat dále do sítě automatizační. Tato architektura se tak hodí spíše pro malé organizace s velmi malým počtem stanic, které mají mít přístup k oběma částem sítě. Tyto stanice je potřeba maximálně zabezpečit, aby bylo omezeno riziko napadení ze strany běžné sítě s následnou propagací útoku do automatizační části sítě. Obecně lze spíš před tímto způsobem varovat než jej doporučovat. 3.3 Duální server Jedná se o modifikaci předchozího přístupu. Duální v tomto případě není pracovní stanice, ale server samotný, viz obr. 19. Historianem z obr. 19 se rozumí především realtimový databázový systém, který slouží jako koncentrátor dat shromažďovaných senzory instalovanými na technologii a tento server je v tomto případě chráněný osobním firewallem (tedy nikoliv dedikovaným zařízením jako je např. na obr. 17).
Obr. 19: Duální server (převzato z [5]) Server nějakým způsobem by měl být přístupný oběma částem sítě, neboť obsahuje cenné poznatky o provozu technologie, které mohou být v rámci podniku dále využity. Otázkou je tedy forma realizace tohoto propojení, nikoliv zda jej vůbec realizovat. Osobní firewall teoreticky funguje stejně jako firewall běžný (myšleno dedikované zařízení), kromě této funkčnosti ovšem obsahuje některé další funkce jako je kontrola síťového provozu na úrovni aplikací nebo kontrola integrity programů. Slovo teoreticky je v předchozí větě použito zcela záměrně a to proto, že osobní firewall jako produkt může být sám předmětem útoku.
32
Bezpečnostní informatika III
Jde o způsob jakým je rozhodováno, zda komunikace bude povolena nebo zamítnuta. K vyhodnocení je potřeba, aby paket byl přijat počítačem, a teprve potom je analyzován firewallem, porovnáván s pravidly a potom povolen jeho doručení na místo určení povoleno nebo zamítnuto. Problém tohoto způsobu je v tom že paket může být upraven tak, aby využil slabin známých osobních firewallů – tzv. leaků. Leak je v doslovném překladu průsak. V hantýrce osobních firewallů hovoříme o průsacích v souvislosti s neschopností firewallu vypořádat se s takto zákeřně upravenými pakety. Výsledkem mohou být chyby buffer overflow, propuštění komunikace nebo dokonce získání kontroly nad zařízením. Protože zařízení, o kterém v této souvislosti hovoříme, je zároveň klíčový server automatizační části síťové infrastruktury organizace, je jasné, že obavy jsou na místě. Různé osobní personální firewally jsou různě náchylné k tomuto typu chyb. Jako vodítko pro nasazení mohou sloužit tzv. leak testy, jako je test z http:www.matousec.com [6]. Dedikovaná zařízení firewall jsou považována za odolnější vůči tomuto typu útoku, navíc výsledkem útoku není vyřazení nebo přímé ohrožení klíčového zařízení automatizační části sítě. Proti dedikovaným firewallům mají osobní firewally sice některé dodatečné schopnosti ve smyslu white listingu spouštěných aplikací, poskytují úplnou kontrolu nad síťovou komunikací na úrovni aplikací, ale tyto schopnosti s sebou nesou také určitá úskalí – osobní firewall předpokládá, že bude obsluhován „živým“ operátorem a to u serverů samozřejmě neplatí. 3.4 Filtrace provozu na bázi switch/router Bezpečnost je zde založena na filtraci na úrovni linkové vrstvy, pomocí aktivních prvků sítě typu switch a router, tak jak je to znázorněno na obr. 20. Výhodou této formy oddělení je vysoká spolehlivost zajištěná realizací na hlubší vrstvě síťového modelu ISO/OSI než například firewall. Nevýhodou tohoto přístupu je horší přehlednost tohoto řešení, chybí zde abstrakce typická pro řešení na vyšších vrstvách síťového modelu jako je třeba firewall. Podrobný popis filtrování TCP/IP přesahuje možnosti tohoto textu, případní zájemci o podrobnější popis principu filtrace jej mohou najít třeba v literatuře [7].
Bezpečností informatika III
33
Obr. 20: Filtrace provozu na bázi router/switch (převzato z [5]) 3.5 Firewall jako vnitřní hranice Router/switch z předchozího případu můžeme nahradit firewallem. Výhodou tohoto řešení je jednodušší možnost spravovat infrastrukturu. Máme možnost, nastavit jaká zařízení mezi sebou mohou komunikovat a jaké prostředky pro tuto komunikaci mohou použít.
Obr. 21: Firewall jako vnitřní hranice (převzato z [5]) Všimněte si také umístnění serveru (historian), který je u této i předchozí architektury v běžné části podnikové sítě. Bezpečnost tohoto serveru je tak klíčovou pro další úvahy protože oddělení obou typů sítě (vnitřní perimetr) pomocí firewalu můžeme považovat za dostatečné opatření z hlediska bezpečnosti.
34
Bezpečnostní informatika III
Server v této architektuře je náchylný k útokům vedeným z podnikové sítě. Dá se dokonce říci, že v této architektuře bezpečnost tohoto serveru vůbec neřešíme, resp. předpokládáme, že bezpečnost běžné sítě je spolehlivě vyřešena. 3.6 Použití demilitarizované zóny (DMZ) Řešením předchozího problému, může být vytvoření tzv. demilitarizované zóny (DMZ). DMZ rozumíme architekturu, kdy veškerý provoz k chráněnému serveru je směrován přes firewall, který řídí, jaký druh komunikace se serverem je povolen a to i pro komunikaci uvnitř sítě. Stejným způsobem je efektivní řešit i zabezpečení různých vnějších přípojných bodů. Filtrace jejich provozu je z hlediska bezpečnosti velmi důležitá, aby se omezila možnost jejich zneužití. Jedinou nevýhodou této architektury je teoretická propustnost firewallu. O tom, že komunikace z a do automatizační části sítě projde, rozhoduje jediné zařízení. V případě chybné konfigurace může dojít k ohrožení. Tento problém řeší použití dvou firewallů pro realizaci úplného oddělení sítí.
Obr. 22: Konstrukce demilitarizované zóny (převzato z [5]) 3.7 Oddělení sítí dvěma firewally Každý z firewallů na obr. 23 řídí komunikaci pouze mezi jedním typem sítě (běžná/automatizační) a serverem, což je mnohem robustnější řešení bezpečnosti než u předchozích architektur. Nevýhodou tohoto řešení je nutnost spravovat více firewallů.
Bezpečností informatika III
35
Obr. 23: Oddělení sítí dvěma firewally (převzato z [5])
?
Kontrolní otázky 1. jaký je rozdíl mezi firewallem a osobním firewallem 2. co rozumíme pojmem demilitarizovaná zóna. 3. z hlediska bezpečnosti seřaďte řešení bezpečnosti na bázi duálních počítačů, demilitarizované zóny a serveru chráněného firewallem.
36
Bezpečnostní informatika III
4 Jemný úvod do dataminingu Průvodce studiem V této kapitole se přesuneme k problematice získávání znalostí z databází. Po prostudování této kapitoly budete vědět
co je to datamining
jaké jsou jeho základní úlohy
jakých metod se pro něj využívá
Čas pro studium Pro prostudování této kapitoly budete potřebovat přibližně dvě hodiny.
4.1 Datamining obecně V předmětech, které jste absolvovali v minulých ročnících, jsme se setkávali s řadou pojmů a technologií, které se nějakým způsobem týkaly. Bezpečnostní informatice I jsme mimo jiné řešili teorii informace a šifrování, v Bezpečnostní informatice II to pak byly informační systémy, v počítačích a ochraně dat pak úvahy nad zabezpečením IT obecně, v předchozích kapitolách jsme pak doplnili dosud chybějící část IT a to problematiku průmyslové automatizace. Výsledkem všech těchto snah je shromáždění velkého množství různorodých dat, které obsahují zajímavé znalosti – pokud se k nim budeme umět dostat. V předmětech, jako je Statistika, jste již získali základní nástroje, které mohou vést k cíli – především regresní analýzu. V následujících kapitolách se zaměříme na další možnosti k získávání znalostí. Proces, kterým získáváme znalosti z různých datových zdrojů, často označujeme jako datamining. Objevují se i jiné názvy, které ale v zásadě označují totéž – český překlad: dolování informací z databází, KDD – knowledge discovery in databases, BI – business inteligence, a další. Datamining jako takový je výhodný používat všude tam, kde se shromažďuje velké množství různých údajů, které jsou vhodné pro analýzy různého druhu. Vzhledem k tomu, že k plnohodnotnému dataminingu je zapotřebí specializovaných (a finančně extrémně náročných) analytických nástrojů, primárně dolujeme informace v „bohatých“ sektorech jako je
Bezpečností informatika III
37
pojišťovnictví, bankovnictví, ale také ve velkých nadnárodních společnostech, ve statistických úřadech, státní správě. Pro možnosti zjišťování různých závislostí mezi naměřenými daty a jejich lepší pochopení, popis je datamining oblíbený také ve vědecké komunitě, která takové údaje potřebuje rutinně získávat. Schematicky bychom si proces dataminingu mohli znázornit podobně jako na obr. 24.
Obr. 24: Obecné schéma dataminingu Jak je patrno ze zpětných vazeb, datamining není jednosměrným procesem. To je způsobeno tím, že jsou hledány nové znalosti, a proto není možné předem odhadnout, jaké znalosti budou ve skutečnosti nalezeny – kdybychom to věděli, nemuseli bychom dolovat. Tedy na základě zjištěných údajů upravujeme naše vstupní představy a požadavky na analýzy i data, která k těmto analýzám použijeme. Podívejme se na jednotlivé fáze dataminingu: 1) získáme data z různých zdrojů, které máme k dispozici 2) data předzpracujeme – sestavíme z nich vhodné tabulky, přidáme vypočtené sloupce apod. 3) transformace dat – předpřipravená data transformujeme do podoby použitelné zvolenými analytickými metodami – může se jednat o výmaz řádků s chybějícími údaji, interpolace chybějících údajů, výběr vhodné podmnožiny údajů apod. 4) nasazení analytických metod – aplikace vhodných analytických metod 5) interpretace výsledků Na problematiku dataminingu se můžeme podívat i z pohledu manažerského, tedy z pohledu řízení. Takovýto pohled naleznete na obr. 25. Samotný proces dataminingu je velmi podobný průběhu obr. 24, ale v tomto případě nás zajímají také určité mocenské vazby, tedy kdo zadává úkol vedoucí k dataminingu, kdo tvoří řešitelský tým a jak jsou ve finále využity výsledky.
38
Bezpečnostní informatika III
Obr. 25: Manažerský pohled na datamining Datamining řeší tři základní úlohy: 1) klasifikace/predikce 2) deskripce 3) hledání „nuggetů“ Klasifikací rozumíme proces, kterým na základě již v minulosti správně klasifikovaných případů zařazujeme případy nové do kategorií (klasifikujeme). Příkladem klasifikační úlohy by mohla být snaha zatřídit klienta banky do některé skupiny zákazníků podle bonity na základě informací shromážděných o daném zákazníkovi. Specifickou úlohou klasifikace je predikce – tou se snažíme posunout klasifikaci do budoucnosti. Mohli bychom zůstat třeba u příkladu s bonitou klientů. Prediktivní úloha by se snažila zjistit, jak zatřídit zákazníka z hlediska bonity na základě informací o něm (potud běžná klasifikace) a odhadů vývoje ekonomiky (to už je predikce). Deskriptivní úlohy slouží k popisu zajímavých vlastností, které jsou v daném datovém souboru dominantní. Dominantnost je hlavním rozdílem od hledání nuggetů, v rámci kterého se snažíme najít zajímavé vlastnosti datového souboru, které lze ale vztáhnout pouze na minoritní část dostupných dat (to však nesnižuje cenu takových poznatků). Příklady možných úloh řešitelných pomocí dataminingu Segmentace a klasifikace klientů banky Predikce vývoje kurzů akcií Predikce spotřeby el. energie Analýza příčin poruch v tel. síti Určení příčin poruch automobilů
Bezpečností informatika III
39
Rozbor databáze klientů v nemocnici …
Obr. 26: Metodika SEMMA(převzato z [9]) Jak je patrno z obrázků 24, 25, ale také textu této kapitoly jsme při nasazování metod dataminingu odkázáni na použití jednotlivých nástrojů. Každý z těchto nástrojů přitom implementuje trochu jiný přístup pro zpracování dat. Můžeme zde zmínit metodiky: - 5A (firma SPSS vyvíjející stejnojmenný nástroj) - SEMMA (firmy SAS vyvíjející stejnojmenný nástroj) - CRISP-DM (nezávislý standard) Protože se v rámci tohoto předmětu seznámíme pouze s nástrojem SAS, zaměříme se z výše uvedených metodik také jenom na metodiku SEMMA (zbývající můžete zkusit pohledat na Internetu ).
40
Bezpečnostní informatika III
SEMMA je zkratka pro Sample – Explore – Modify- Model – Asses, kterou bychom schematicky mohli popsat podobně jako na obr. 26. Opět tato metodika vychází z obecného pojetí dataminingu a v hrubých rysech odpovídá postupu představeném na obr. 24. Všimněte se ale trošku rozdílné filosofie dolování dat uprostřed obr. 26. Proces dolování se zde rozděluje do paralelních (zároveň probíhajících) probíhajících procesů např. ve fázi explore (průzkum dat) tato data prozkoumáváme zároveň pomocí různých typů grafů, ale také některých základních metod pro shlukování dat a podobně. Tento paralelismus je typickým znakem SASu. Očividné je to v modelovací fázi, kde dataminingový nástroj (SAS Enterprise Dataminer) je schopen na data nasadit libovolné množství analytických metod (včet různě nastavených metod téhož druhu) a výsledky pak automaticky validovat a vybrat model, který odpovídá nejlépe navrženému konceptu. 4.2 Zdroje údajů Základním místem, odkud budeme brát údaje nutné pro analýzu, jsou databázové systémy, které slouží jako back-end pro jednotlivé informační systémy. Tyto databáze ale mohou být různého druhu: - Klasické relační databáze - EIS (Excecutive Information Systém) - OLAP (On-Line Analytical Processing) Kromě databázových systémů můžeme jako vstup pro analýzy použít také různé statistiky, ale třeba také výsledky předchozích analýz. Zatímco klasické relační databáze byste si měli být schopni alespoň rámcově představit (hovořili jsme o nich např. v předmětu Bezpečnostní informatika 1 nebo Počítačové sítě a ochrana dat, kde jste měli možnost se s jedním z těchto databázových prostředků blíže seznámit). S představením si EIS a OLAP byste už ale mohli mít problém. Podívejme se proto na ně podrobněji. Vraťme se k obrázku, který jste měli možnost (v lehce jiné formě) vidět ve skriptech z Bezpečnostní informatiky 2 [10]. Tento zachycuje vzájemné působení různých druhů informačních systémů v rámci podniku.
Bezpečností informatika III
41
Obr. 27: Informační systémy podniku vs způsob uložení dat Průvodce studiem Pokud Vám výše uvedené zkratky nic neříkají, možná by nebylo od věci provést krátké zopakování problematiky informačních systémů. K tomuto účelu můžete použít skripta z Bezpečnostní informatiky 2, která v aktuální podobě naleznete na http://prometheus.vsb.cz/ ve stejnojmenném modulu. Klíč k zápisu je informatika2. Údaje z jednotlivých bází dat je pro účely vyšší úrovní řízení nutno zpracovávat jiným způsobem, než je běžné u používaných „transakčních“ informačních systému. Tato integrace probíhá do datových skladů nebo do OLAP řešení. OLAP je zkratka pro on-line analytical procesing. OLAP se od klasických databází liší způsobem uložení dat i způsobem, jakým provádíme manipulaci s nimi. Tato manipulace je v mnoha ohledech intuitivnější, což umožňuje abstrakce dat ze složitých struktur tabulek a relací mezi nimi. Data OLAP jsou zachycovány multidimenzionálně – tvoříme z nich tzv. datové krychle, se kterými dále manipulujeme.
42
Bezpečnostní informatika III
Obr. 28: Multidimenzionální pohled na prodejní data (převzato z [9]) S krychlí dle potřeb lze otáčet (operace pivot), vybírat části (dice), provádět řezy (slice) a samozřejmě zobrazovat agregované výsledky. Data lze integrovat do jediné velké krychle (hypercube) nebo do několika menších (multicube). Oba tyto přístupy mají své výhody a nevýhody zejména v intuitivnosti použití a nárocích na datový server. Podle způsobu fyzického uložení dat rozlišujeme dále řešení MOLAP a ROLAP. MOLAP je zkratka pro Multidimenzionální OLAP – jedná se o OLPA v pravém slova smyslu, protože data jsou uložena v krychli.ROLAP oproti tomu pracuje nad klasickými databázemi – datová krychle je zde pouze virtuální – koncovému uživateli se jeví, že pracuje s datovou krychlí ačkoliv reálně pracuje s klasickou databází. Posledním pojmem, který bychom v souvislosti s ukládáním dat měli probrat, jsou tzv. datové sklady. Existují různé definice datových skladů. Můžeme jej obecně definovat, jako místo kam se ukládají analyzovaná data. Existují i definice, které pohlížejí na datový sklad z manažerské pohledu, např. W. H. Inmon definoval datový sklad jako soubor dat, který slouží pro podporu rozhodování. Z hlediska obecných vlastností jsou pro datový sklad typické: - Subjektová orientovanost - Integrovanou - Časová proměnlivost - Strukturální stálost Subjektová orientovanost představuje základní rozdíl od klasických informačních systémů, které jsou obvykle orientovány transakčně. Klasický IS zajímají jednotlivé případy (např. naskladnění výrobku, prodej, apod.) zatímco v datovém skladu budeme s těmito daty pracovat trochu jinak – budou nás zajímat trendy, vazby na další data atd.
Bezpečností informatika III
43
Integrovaností rozumíme import dat z míst jejich původu do jednotné báze dat. S tím souvisí zároveň další vlastnost datového skladu a tou je časová proměnlivost. S tím jak se mění data v jednotlivých systémech, musí se měnit také data ve skladu, aby morálně nezastarával. Struktura skladu na druhou stranu musí být stálá – proces importu dat z jejich původního umístnění a především jejich integrace do datového skladu totiž není úplně triviální, aby se mohla příliš často měnit.
?
Kontrolní otázky 1. Jaký je rozdíl mezi MOLAP a ROLAP? 2. Čím se liší běžné IS (a způsob jejich práce s daty) od OLAP řešení? 3. Jaké jsou základní vlastnosti datového skladu? 4. Vysvětlete specifika metodologie SEMMA? 5. V čem se metodologie SEMMA liší od obecného postupu dataminingu?
44
Bezpečnostní informatika III
5 Pravidlově orientované metody dataminingu Průvodce studiem Existuje poměrně velké množství různých metod dolování dat. V této kapitole se podíváme na skupinu metod, které mají tu společnou vlastnost, že pracují s pravidly. Těmito metodami jsou: - rozhodovací pravidla, - rozhodovací stromy a - asociační pravidla. Po prostudování této kapitoly budete vědět vědět k čemu lze použít pravidlově orientované metody dataminingu jak sestavit rozhodovací strom Čas pro studium Pro prostudování této kapitoly budete potřebovat přibližně dvě hodiny. Pro lepší pochopení doporučuji projít si pečlivě také příklady k této kapitole. Při práci s příklady se může doba práce s kapitolou poněkud protáhnout. Pravidlově orientované metody dataminingu jsou oblíbenými nástroji pro řešení různých typů úloh a to zejména z oblasti deskripce problémové domény, ale také dolování nuggetů. V současnosti používáme tři základní pravidlově orientované metody a to: - rozhodovací pravidla, - rozhodovací stromy a - asociační pravidla. Zatímco rozhodovací pravidla a stromy používáme primárně pro deskripci, asociační pravidla se hodí především pro dolování nuggetů. 5.1 Rozhodovací pravidla Rozhodovací pravidla vypadají přibližně následovně: IF předpoklad/předpoklady THEN třída Ti, kteří se v minulosti setkalis prakticky jakýmkoliv programovacím jazykem by výše uvedená konstrukce měla být jasná. Pokud je splněna
Bezpečností informatika III
45
předporadová část pravidla jsme schopni, nade vší pochybnost, určit třídu, kam hodnocený případ zařadíme. Rozhodovací pravidla používáme především pro klasifikaci – tedy na základě vstupních údajů (atributů) se rozhodujeme o příslušnosti posuzovaného případu k některé cílové třídě. Vstupní údaje používáme v předporadové části pravidla, zatímco cílové třídy použijeme v důsledkové části pravidla. Obvykle přitom vytváříme celou sadu pravidel. Tato pravidla jsou přitom posuzována postupně (směrem shora dolů). Naším cílem je, aby výsledná sada pravidel na jednu stranu pokrývala, co možná nejvěrněji, zvolenou problémovou doménu, na druhou stranu aby přitom byla co možná nejjednodušší (tedy obsahovala pouze nezbytné minimum pravidel). Nejpoužívanějším algoritmem pro tvorbu rozhodovacích pravidel je algoritmus AQ, někdy se pro něj používají i jiná jména jako třeba algoritmus pokrývání množin (set covering algorithm) nebo algoritmus rozděl a panuj (divide and conquer algorithm). Principielně se jedná o stejný algoritmus, který navrhl v roce 1969 Ryszard S. Michalski (1937 – 2007). Ke své funkci potřebuje algoritmus trénovací množinu DTR. Trénovací množina obsahuje v minulosti správně klasifikované případy a vstupní atributy, které ke klasifikaci vedly. Tato klasifikace byla ale provedena pomocí alternativních metod jako například expertním posudkem apod. Berka [9] popisuje algoritmus AQ následovně: 1) najdi pravidlo, které pokrývá nějaké pozitivní příklady a žádný negativní 2) odstraň pokryté příklady z trénovací množiny 3) pokud v trénovací množině zbyly ještě nějaké nepokryté pozitivní příklady, pokračuj další iterací algoritmu. Jak jednoduché a jasně, že ? Podívejme se velmi zjednodušený demonstrující.
příklad,
celý
mechanismus
Příklady algoritmus AQ Firma XY často přijímá čerstvé absolventy technických univerzit do svého výzkumného oddělení. Pro hodnocení používá následující vstupní atributy: - hodnocení teoretická části státnice (1 – 4) - hodnocení obhajoby diplomové práce (1 – 4) - brigáda během studia (A/N) - publikoval v odborném periodiku (A/N) Cílovým atributem je vhodnost k přijetí (A/N). Několik úvodních kroků řešení je patrno dále. Upozornění: nejedná se o plnohodnotný přiklad rozhodovacích
46
Bezpečnostní informatika III
pravidel, pro plnohodnotný příklad konzultujte kapitolu 5.4. Tab. 1: Trénovací množina Státnice T Státnice DP 1 1 S1 2 2 S2 2 2 S3 1 1 S4 …
Brigáda N A N A
Publikoval N N A N
Vhodnost N N A A
Pravidlo by mohlo vypadat následovně: IF Publikovat(A) THEN Vhodnost(A) Řádek S3 bychom odstranili z trénovací množiny a pokračovali bychom IF StátniceT(1) AND StátniceDP(1) AND Brigáda(A) THEN Vhodnat(A) A tak dále. Demonstrační případ je bohužel velmi zjednodušený (to je nakonec i plnohodnotný příklad z kapitoly 5.4), v reálném světě naše data jsou totiž zatížena šumem, jsou tedy nepřesná. Úplné pokrytí konceptu v takovém případě je nemožné, jelikož jednotlivé cílové třídy se nám budou z hlediska vstupních atributů překrývat. Tuto skutečnost je potřeba při vytváření pravidel zohlednit. Sada pravidel, tak jak jsme k ní došli, bude ve výsledku nevýhodná z hlediska efektivity vyhodnocení – protože musíme projít všechna zjištěná pravidla pro provedení úplné klasifikace. Z tohoto důvodu někdy převádíme tyto sady pravidel do podoby rozhodovacího seznamu tedy do následující podoby: IF př.1 THEN třída1 ELSE IF př.2 THEN třída2 ELSE IF … ELSE třídaX Takový uspořádaný seznam má výhodu v tom, že pozitivní vyhodnocení podmínky vede automaticky k negativnímu vyhodnocení ostatních částí pravidla, což ocením z hlediska rychlosti vyhodnocování a její náročnosti na systémové zdroje. Existují i alternativní algoritmy, které lze použít pro tvorbu pravidel např. algoritmus Search. Kvalitu pravidel můžeme také hodnotit pomocí informační intropie. Pravidla lze také stanovovat podmíněným způsobem – tedy lze stanovit
Bezpečností informatika III
47
vádu pravidla. Popis těchto „vychytávek“ však již překračuje možnosti výkladu problematiky v těchto skriptech. Co bychom však měli ještě vědět předtím, než přejdeme k výkladu rozhodovacích stromů je úvahy nad podobou vstupních dat, popřípadě s absencí dat. Pravidlově orientované metody (a tedy i rozhodovací pravidla) neumějí zpracovávat chybějící údaje. Např. pokud by v tabulce 1 chyběl v některých řádcích údaj o absolvování brigády, rozhodovací pravidla by nebylo možné použít. Pokud v trénovací množině nějaké údaje chybí, musíme před nasazením metody tuto množinu upravit. Možností pro úpravu je relativně dost: - řádky s chybějícími hodnotami můžeme smazat, - chybějící hodnoty můžeme nahradit hodnotou nevím - chybějící hodnoty nahradíme jinou hodnotou o ve vstupním souboru nejčetnější o proporcionálním podílem všech hodnot o náhodnou hodnotou Ať už zvolíme, kterýkoliv způsob doplnění (nebo smazání) měli bychom si být vědomi následků, které to pro nás může mít. Všechny tyto úpravy totiž ve finále mohou ovlivnit výsledek – naruší se tím totiž do určité míry vypovídací schopnost trénovací množiny. Pro úplné zachycení celého konceptu, musí být trénovací množina, pokud možno, sestavena tak, aby pokrývala celý koncept – výmazem některých řádků (zejména pokud jej jich větší množství) nám může toto pokrytí výrazně narušit. Pokud tedy chybí větší množství údajů, preferujeme jejich náhradu před smazáním. Doplnění nejčetnější hodnoty je použitelné v případě, pokud v množině je jeden údaj, který se zde vyskytuje majoritně (například v devíti případech z desíti), dá se tedy bezpečně předpokládat, že i majorita chybějících údajů bude obsahovat tuto majoritní hodnotu. Proporcionální podíl hodnot daného atributu doplňujeme v případě, že není možné doplnit nejčetnější hodnotu a zároveň máme dostatek údajů, abychom mohli usuzovat na frekvenční charakteristiky rozložení souboru dat, v opačném případě lze doplnit náhodnou hodnotu. V každém případě se musíme smířit s tím, že úpravou dat vnášíme do našeho uvažování určitou chybu/nejistotu (šum) a ten bude nutné zohlednit i při dosahování výsledku. Problémem mohou být také čistě numerické atributy. Pravidlově orientované metody totiž jsou založeny na diskrétních hodnotách. V našem příkladě jsme sice měli také číselné hodnoty (výsledky státnic), ale ve skutečnosti se jednalo o hodnoty diskrétní odpovídající stupnici známkování (výborně, velmi dobře, dobře, neprospěl). V případě použití spojitých numerických atributů
48
Bezpečnostní informatika III
preferujeme spíše statistické metody. V případě, že přece jenom chceme použít pravidlově orientované metody, pak je nutné numerické atributy diskretizovat – nejjednodušší způsob je převodem na omezený počet intervalů. Pozor Úvahy o chybějících hodnotách, šumu, numerických atributech jsou společné pro všechny pravidlově orientované metody – rozepsány jsou však pouze zde! V následujících kapitolách o nich nebude ani zmínka. 5.2 Rozhodovací stromy V rozhodovacích stromech segmentujeme znalosti do podoby stromu. Každý uzel tohoto stromu představuje jeden atribut a každá vazba z něho jsoucí pak představuje jednu hodnotu atributu. Pro stanovení struktury metod se používají podobné metody jako pro tvorbu rozhodovacích pravidel. Ono taky ne náhodou lze rozhodovací strom převést na rozhodovací pravidla a opačně. Kromě metody rozděl a panuj, kterou jsme zmínili už u rozhodovacích pravidel, můžeme použít celou řadu jiných algoritmů jako např. algoritmus TDIDT (Top Down Induction of Decision Trees). Algoritmus TDIDT spočívá v tom, že zvolíme jeden atribut, jako kořen stromu, následně rozdělíme data v tomto uzlu podle hodnot zvoleného atributu a pro každou podmnožinu přidáme jeden uzel. Pokud zbývá ve stromu takový uzel, ve kterém všechna data nepřináležejí k jediné třídě, opakujeme postup (volíme další atribut a pokračujeme dále). Atribut, který použijeme k větvení stromu, samozřejmě nemá smysl volit náhodně. K volbě vhodného atributu využíváme pomůcky umožňující zhodnotit „přínos“ atributu vysvětlit problém. K tomuto účelu využíváme veličiny odvozené z výpočtu informační entropie. Možná si vzpomenete z předmětu Bezpečnostní informatika 1, že informační entropii H jsme vypočítávali následovně (1): T
H ( pt log 2 pt )
(1)
t 1
Kde H p
informační entropie pravděpodobnost, že nastane jev t
Pravděpodobnost jako takovou pro výpočty okolo rozhodovacích stromů (a řadu dalších výpočtů) není úplně vhodné použít, protože tuto pravděpodobnost neznáme – nahrazujeme ji proto četnostmi, které získáváme z trénovací datové množiny.
Bezpečností informatika III
49
O volbě atributu rozhoduje střední entropie atributu H(A), kterou vypočteme podle vzorce (2). H ( A)
n( A(v)) H ( A(v)) n vVal ( A)
Kde H(A) v n(A(v)) n H(A(v))
(2)
střední entropie atributu A hodnota, kterou může nabývat atribut A počet řádků, pro které nabývá atribut A hodnoty v celkový počet řádků v datovém souboru entropie hodnoty v atributu A
Entropii hodnoty v atributu A H(A(v)) spočteme podle vzorce (3). T
H ( A(v)) t 1
nt ( A(v)) n ( A(v)) log 2 t n( A(v)) n( A(v))
(3)
Pro větvení vybíráme takový atribut, jehož střední míra entropie je nejmenší (tedy schopnost přinést informaci je největší). Pro volbu atributu lze použít i jiné vzorce, např. se často používá tzv. Ginni index, který je z výpočetního hlediska o něco jednodušší (viz např. [9]). Příklad Nezapomeňte, že příklad je obsažen v kapitole 5.4. Pokud vám proto výše uvedený výklad není jasný, je vhodné si tento příklad projít ještě předtím, než budeme pokračovat dále ve výkladu rozhodovacích stromů. Výsledný strom bohužel nemusí být optimální – reálně hrozí tzv. přeučenost stromu (overfiting). Řešením v takovém případě bývá klasický návrh stromu s následným prořezáváním větví. Při tvorbě stromu postupujeme od kořene k listům, při prořezávání opačně. Při prořezávání tedy některé uzly stromu převádíme na listové (koncové uzly) a zahazujeme větve z něho jdoucí. Vyhodnocení, který uzel takto upravit není úplně jednoduché a vyžaduje, abychom každou takovou úpravu validovali vůči další, nezávislé (validační) sadě dat popisující danou problémovou doménu. Vhodnost prořezání pak testujeme pomocí výpočtu směrodatné odchylky klasifikace stromu, kterou porovnáváme s dolním odhadem správnosti pro zvolený interval spolehlivosti.
50
Bezpečnostní informatika III
5.3 Asociační pravidla Asociační pravidla slouží k jinému účelu než rozhodovací pravidla nebo rozhodovací stromy – umožňují v datech hledat zajímavé souvislosti, které na první pohled nejsou zřejmé. Asociační pravidla tedy slouží pro dolování nuggetů. Tuto metodu zpopularizoval počátkem 90. let Rakesh Agrawal, který ji použil pro analýzu nákupního košíku. Tato analýza spočívá ve zkoumání vzájemného vztahu mezi zbožím v nákupním košíku. Vzhledem k tomu, že žádnou z položek nepreferujeme, žádný z atributů nelze označit jako cílový. Řešení všech klasifikačních problémů je založeno na nutnosti stanovení cílové položky a zkoumání, jaký k ní mají vztah ostatní dostupné (vstupní) atributy. Volíme tedy různé předpoklady (ant – antecedent) a jejich a závěry (suc – sukcedent) a zkoumáme povahu jejich vztahu. Takto vytváříme kombinace všech dvojic atributů. Vztah atributů zkoumáme s použitím kontingenční tabulek. Tab. 2: Kontingenční tabulka dvou atributů Suc !Suc ∑ Ant
a
b
r
!Ant
c
d
s
∑
k
l
n
Hodnoty a – d jsou četnosti splňující danou kombinaci předpokladu a závěru, např. a je počet případů kdy byl splněn předpoklad ant a zároveň nastal závěr suc. Zkoumáme různé charakteristiky této kombinace atributů podle vzorců (4 – 9). Podpora závěru představuje počet objektů, které splňují předpoklad i závěr, viz vzorec (4). P( Ant Suc)
a abcd
(4)
Spolehlivostí rozumíme podmíněnou pravděpodobnost závěru, výpočet provedeme podle vzorce (5). P( Suc | Ant )
a ab
(5)
Absolutní počet objektů splňujících předpoklad vypočteme dle vzorce (6).
Bezpečností informatika III P( Ant )
ab abcd
51
(6)
Absolutní počet objektů splňujících závěr lze vypočítat dle vzorce (7). P( Suc)
ac abcd
(7)
Pokrytí je možné vypočíst jako podmíněná pravděpodobnost předpokladu, pokud platí závěr (4) P( Suc | Ant )
a ac
(8)
Konečně kvalitu vypočteme jako vážený součet spolehlivosti a pokrytí, viz vzorec (9). Kvalita w1
a a w2 ab ac
(9)
Hodnoty vah w1 a w2 volíme tak, aby jejich součet byl roven jedné. Při tvoření asociačních pravidel nás zajímají pravidla: - konzistentní, - úplná a - deterministická. Konzistentní pravidla (pravidla s platností 1) jsou taková, kde levá (předporadová) část pravidla je podmínkou dostatečnou pro splnění části pravé (závěrové) pravidla. Úplná pravidla (pravidla s pokrytím 1) jsou taková, kde strana implikace (předpokladu) je podmínkou nutnou pro splnění pravé strany pravidla. Podmínka však zároveň nemusí být postačující. Deterministická pravidla (pravidla s platností i pokrytím rovna 1) – předporadová část je podmínkou nutnou i postačující pro splnění pravé (závěrečné) strany pravidla. 5.4 Pravidlově orientované metody dataminingu - příklad Mějme data o klientech banky. Naším úkolem bude jejich analýza pomocí pravidlově orientovaných metod. Data jsou znázorněna v tabulce 3 (převzato z [9, 11]). V datovém souboru jsou obsaženy identifikátory řádků (označeny k1 – k12), které v samotných analýzách nevyužijeme. Vstupní atributy představují
52
Bezpečnostní informatika III
příjem, konto, pohlaví a fakt, zda klient je aktuálně zaměstnaný. Cílovým atributem je úvěr – budeme tedy rozhodovat (u rozhodovacích pravidel a stromů), zda klient může nebo nemůže dostat úvěr. Tab. 3: Data pro o klientech banky Klient příjem konto pohlaví vysoký vysoké žena k1 vysoký vysoké muž k2 nízký nízké muž k3 nízký vysoké žena k4 nízký vysoké muž k5 nízký nízké žena k6 vysoký nízké muž k7 vysoký nízké žena k8 nízký střední muž k9 vysoký střední žena k10 nízký střední žena k11 nízký střední muž k12
nezaměstnaný ne ne ne ano ano ano ne ano ano ne ano ne
úvěr ano ano ne ano ano ne ano ano ne ano ne ano
5.4.1 Příklad rozhodovací strom Úkol: rozhodovací strom Na základě dat z tabulky 3 zkonstruujte rozhodovací strom, který umožní rozhodnutí o poskytnutí nebo neposkytnutí úvěru. K výpočtu využijeme entropii (vzorce (2 – 3)). Ke konstrukci budeme potřebovat kontingenční tabulky kombinace vstupní a cílový atribut. Za každý řádek, který splňuje danou kombinaci hodnot atributů, připočteme do daného políčka 1. Součet všech polí se musí rovnat počtu řádků, které byly použity pro konstrukci tabulky. Kombinace atributů naleznete v tabulkách 4 – 7. Tab. 4: Příjem - úvěr Úvěr (ano) Úvěr (ne) 0 Příjem (vysoký) 5 4 Příjem (nízký) 3 Tab. 5: Konto - úvěr Úvěr (ano) Konto (vysoké) 4 Konto (střední) 2 2 Konto (nízké)
Úvěr (ne) 0 2 2
Bezpečností informatika III
53
Tab. 6: Pohlaví – úvěr Úvěr (ano) Úvěr (ne) 2 Pohlaví (muž) 4 2 Pohlaví (žena) 4 Tab. 7: Nezaměstnaný – úvěr Úvěr (ano) Úvěr (ne) 3 Nezaměstnaný (ano) 3 1 Nezaměstnaný (ne) 5 Vypočtené hodnoty dosadíme do vzorců (2 – 3), pro jednotlivé kombinace vstupní – cílový atribut. Příjem 5 7 H ( prijem (vysoky)) H ( prijem (nizky)) 12 12 5 5 0 0 H ( prijem (vysoky)) log 2 log 2 0 0 0 5 5 5 5 3 3 4 4 H ( prijem (nizky)) log 2 log 2 0,52388 0,46135 0,98523 7 7 7 7 5 7 H ( prijem ) 0 0,98523 0,5747 12 12 H ( prijem )
Konto 4 4 4 H (konto(vysoke)) H (konto( stredni )) H (konto(nizke)) 12 12 12 4 4 0 0 H (konto(vysoke)) log 2 log 2 0 0 0 4 4 4 4 2 2 2 2 H (konto( stredni )) log 2 log 2 0,5 0,5 1 4 4 4 4 2 2 2 2 H (konto(nizke)) log 2 log 2 0,5 0,5 1 4 4 4 4 4 4 4 H (konto) 0 0,66666 12 12 12
H (konto)
Pohlaví 6 6 H ( pohlavi(muz)) H ( pohlavi( zena)) 12 12 4 4 2 2 H ( pohlavi(muz)) log 2 log 2 0,38998 0,52832 0,9183 6 6 6 6 4 4 2 2 H ( pohlavi( zena) log 2 log 2 0,38998 0,52832 0,9183 6 6 6 6 6 6 H ( pohlavi) 0,9183 0,9183 0,9183 12 12 H ( pohlavi)
Nezaměstnaný
54
Bezpečnostní informatika III
6 6 H (nezam(ano)) H (nezam(ne)) 12 12 3 3 3 3 H (nezam(ano)) log 2 log 2 0,5 0,5 1 6 6 6 6 5 5 1 1 H (nezam(ne)) log 2 log 2 0,2192 0,43083 0,65002 6 6 6 6 6 6 H (nezam) 1 0,65002 0,82501 12 12 H (nezam)
Shrňme si vypočtené entropie jednotlivých atributů: Příjem H = 0,5747 Konto H = 0,6666 Pohlaví H = 0,9183 Nezaměstnaný H = 0,825 Nejmenší entropii má atribut příjem, proto zvolíme právě jej jako kořenový atribut. Zároveň můžeme usoudit na základě tab. 4, že pokud příjem bude příjem vysoký, úvěr poskytneme, zatímco u příjmu nízkého se budeme muset rozhodovat dále. Pro další úvahy z trénovací množiny odstraníme řádky obsahující hodnotu atributu příjem = vysoký. Upravenou trénovací množinu máme k dispozici v tabulce 8. Tab. 8: Trénovací množina – odstraněn Příjem(vysoký) Klient příjem konto pohlaví nezaměstnaný úvěr nízký nízké muž ne ne k3 nízký vysoké žena ano ano k4 nízký vysoké muž ano ano k5 nízký nízké žena ano ne k6 nízký střední muž ano ne k9 nízký střední žena ano ne k11 nízký střední muž ne ano k12 Postupovat budeme podobně jako v prvním kroku, z úvah už ale vynecháme atribut příjem. Nové tabulky jsou dostupné níže (viz tab. 9 – 11). Tab. 9: Konto - úvěr Úvěr (ano) Konto (vysoké) 2 Konto (střední) 1 0 Konto (nízké)
Úvěr (ne) 0 2 2
Bezpečností informatika III
Tab. 10: Pohlaví – úvěr Úvěr (ano) Úvěr (ne) 2 Pohlaví (muž) 2 2 Pohlaví (žena) 1 Tab. 11: Nezaměstnaný – úvěr Úvěr (ano) Úvěr (ne) 3 Nezaměstnaný (ano) 2 1 Nezaměstnaný (ne) 1 Vypočteme entropie: Konto 2 3 2 H (konto(vysoke)) H (konto( stredni )) H (konto(nizke)) 7 7 7 2 2 0 0 H (konto(vysoke)) log 2 log 2 0 0 0 2 2 2 2 1 1 2 2 H (konto( stredni )) log 2 log 2 0,52832 0,38998 0,9183 3 3 3 3 0 0 2 2 H (konto(nizke)) log 2 log 2 0 0 0 2 2 2 2 2 3 2 H (konto) 0 0,9183 0 0,393557 7 7 7 H (konto)
Pohlaví 4 3 H ( pohlavi(muz)) H ( pohlavi( zena)) 7 7 2 2 2 2 H ( pohlavi(muz)) log 2 log 2 0,5 0,5 1 4 4 4 4 1 1 2 2 H ( pohlavi( zena) log 2 log 2 0,52832 0,38998 0,9183 3 3 3 3 4 3 H ( pohlavi) 1 0,9183 0,97143 0,41633 1,3346 7 7 H ( pohlavi)
Nezaměstnaný 5 2 H (nezam(ano)) H (nezam(ne)) 7 7 2 2 3 3 H (nezam(ano)) log 2 log 2 0,52887 0,44218 0,97095 5 5 5 5 1 1 1 1 H (nezam(ne)) log 2 log 2 0,5 0,5 1 2 2 2 2 5 2 H (nezam) 0,97095 1 0,6935 0,2857 0,9792 7 7 H (nezam)
55
56
Bezpečnostní informatika III
Porovnáme entropie: Konto H = 0,393557 Pohlaví H = 1,3346 Nezaměstnaný H = 0,9792 Nejnižší hodnotu entropie má atribut konto. Zároveň zde můžeme vytipovat dva koncové uzly. Pokud konto bude vysoké – úvěr přidělíme, pokud bude konto nízké – úvěr zamítneme. Při střední úrovni konta budeme muset rozhodnout podle dalších ukazatelů. Z trénovací množiny odstraníme řádky obsahující atribut konto vysoké nebo nízké (viz tab. 12). Tab. 12: Trénovací množina – vyřazeno konto vysoké a nízké Klient příjem konto pohlaví nezaměstnaný úvěr nízký střední muž ano ne k9 nízký střední žena ano ne k11 nízký střední muž ne ano k12 Správně bychom měli pokračovat stejným způsobem jako dosud – tedy konstrukcí tabulek vstupních a cílových atributů a následným výpočtem entropií. V tomto případě je to ale už zbytečné, protože z tab. 12 je očividná schopnost atributu nezaměstnaný vysvětlit zbývající pravidlo. Tedy pokud klient je aktuálně nezaměstnaný, úvěr nepřidělíme, jinak ano. Ověření pravidla Spočtěte samostatně entropii atributů pohlaví a nezaměstnaný a ověřte, že má úvaha o posledním větvení stromu byla správná.
Výsledek našeho snažení můžeme vizualizovat do podoby skutečného stromu (viz obr. 29).
Bezpečností informatika III
57
Obr. 29: Výsledný rozhodovací strom 5.4.2 Příklad rozhodovací pravidla Úkol: rozhodovací pravidla Na základě dat z tabulky 3 zkonstruujte rozhodovací pravidla, která umožní rozhodnutí o poskytnutí nebo neposkytnutí úvěru. Při tvorbě rozhodovacích pravidel budeme postupovat trénovací množinou. Vezmeme první řádek z tab. 3 a transformujeme jej do podoby pravidla. IF příjem(vysoký) AND konto(vysoké) nezaměstnaný(ne) THEN úvěr(ano)
AND
pohlaví(žena)
AND
Takové pravidlo je nepochybně správně, bohužel ale popisuje pouze ten jeden daný řádek, což je z hlediska funkčnosti pravidel málo – naším cílem je najít co možná nejobecnější pravidla, která pokrývají daný koncept. Zobecňování provádíme tak, že procházíme trénovací množinu a hledáme takové případy, kdy se určitá hodnota atributu změnila, ale výsledek zůstal stejný (úvěr(ano)). Podívejme se třeba na řádek K2, který je stejný jako K1 až na pohlaví (K1 – žena, K2 – muž). Můžeme tedy říci, že v tomto případě pohlaví nebylo určující pro přiznání úvěru, proto pravidlo lze zobecnit do podoby:
58
Bezpečnostní informatika III
IF příjem(vysoký) AND konto(vysoké) AND nezaměstnaný(ne) THEN úvěr(ano) Podobným způsobem postupujeme ve zobecňování dále. Na základě K7 můžeme vyvodit, že ani stav konta v tomto není určující: IF příjem(vysoký) AND nezaměstnaný(ne) THEN úvěr(ano) A konečně na základě K8 můžeme usoudit, že ani zaměstnání není v tomto případě důležité. Výsledné, maximálně obecné pravidlo tedy je následující: IF příjem(vysoký) THEN úvěr(ano) Položky z trénovací množiny obsahující příjem(vysoký) můžeme vyloučit. Upravenou trénovací množinu naleznete v tab. 13. Tab. 13: Data pro o klientech banky – vyloučen příjem(vysoký) Klient příjem konto pohlaví nezaměstnaný Úvěr nízký nízké muž Ne ne k3 nízký vysoké žena Ano ano k4 nízký vysoké muž Ano ano k5 nízký nízké žena Ano ne k6 nízký střední muž Ano ne k9 nízký střední žena Ano ne k11 nízký střední muž Ne ano k12 Z tabulky 13 nás zajímá první řádek pozitivně pokrývající náš hledaný koncept (úvěr(ano)) – a to je řádek K4. Na základě něj sestavíme nové pravidlo, atribut příjem již z pravidla můžeme vyloučit, protože obsahoval pouze dvě hodnoty a první již (příjem vysoký) máme pokrytou pravidlem, tedy zbývající hodnota příjem(nízký) nevysvětluje variabilitu při udělování úvěrů: IF konto(vysoké) AND pohlaví(žena) AND nezaměstnaný(ano) THEN úvěr(ano) Na základě K5 můžeme z pravidla vyloučit atribut pohlaví a na základě K9 a K11 pak můžeme usoudit, že nezaměstnanost je spíše přitěžující okolností, než zárukou bonity, protože už při střední hodnotě konta jsme úvěr nepřidělili. Výsledné pravidlo proto vypadá následovně. IF konto(vysoké) THEN úvěr(ano) Z dalších úvah vyloučíme hodnotu atributu konto(vysoké) – viz tab. 14. V trénovací množině nám tak zbude pouze jeden pozitivní případ reprezentovaný řádkem K12.
Bezpečností informatika III
59
Tab. 14: Data pro o klientech banky – vyloučen příjem(vysoký) Klient příjem konto pohlaví nezaměstnaný Úvěr nízký nízké muž Ne ne k3 nízký nízké žena Ano ne k6 nízký střední muž Ano ne k9 nízký střední žena Ano ne k11 nízký střední muž Ne ano k12 IF konto(střední) AND nezaměstnaný(ne) THEN úver(ano) Celá sada pravidel bude vypadat následovně IF příjem(vysoký) THEN úvěr(ano) IF konto(vysoké) THEN úvěr(ano) IF konto(střední) AND nezaměstnaný(ne) THEN úver(ano) Uvedenou sadu pravidel bychom mohli následně transformovat do podoby uspořádaného seznamu. IF příjem(vysoký) THEN Úvěr(ano) ELSE IF Konto(vysoké) THEN Úvěr(ano) ELSE IF Konto(střední) AND nezaměstnaný(ne) THEN úvěr (ano) ELSE úvěr(ne) 5.4.3 Příklad asociační pravidla Úkol: asociační pravidla Na základě dat z tabulky 3 hledejte zajímavé souvislost, které by umožnily lepší pochopení situace.
Základem práce je vytváření všech možných kombinací hodnot atributů. Podívejme se tedy, jakých hodnot atributy nabývají Tab. 15: Hodnoty atributů Atribut Hodnoty Vysoký/nízký Příjem Vysoké/nízké/střední Konto Muž/žena Pohlaví Nezaměstnaný Ano/ne Ano/ne úvěr
počet 2 3 2 2 2
60
Bezpečnostní informatika III
Z tabulky 15 můžeme vyvodit, že počet kombinací délky 1 je 11 (prostá suma počtu hodnot atributů). Kombinace délky 2 pak můžeme spočítat pomocí vzorce (10): k2
m
K
i , j 1,i j
Kde m KA
Ai
K Aj
(10)
počet atributů počet hodnot daného atributu
V našem případě je počet kombinací délky 2 roven 48, délky 3 roven 104, délky 4 roven 112 a délky 5 roven 48 (celkem tedy 323 kombinací). Kombinace se přitom generují nezávisle na trénovací množině. Teprve ve druhé fázi se počítají frekvence výskytů daných kombinací v trénovací množině a z těchto frekvencí se na něco usuzuje. Už ze samotného počtu kombinací, ale také způsobu práce s nimi můžeme usoudit, že bez softwarové podoby se asociační pravidla získávají velmi obtížně a pro rozsáhlejší sady dat je to dokonce nemožné. Což ovšem neznamená, že bychom naše snažení vzdali. Na FBI máme k dispozici systém SAS s modulem SAS Enterprise Miner, který je přizpůsoben dolování dat z různých datových zdroj. SAS je své práci potřebuje data – a my mu je můžeme poskytnout např. ve formátu XLS (formát XLSX z Excel 2007 a novější není z hlediska importu podporován (ve verzi SAS 9.2)) Import provedeme tak, že spustíme SAS, v průzkumníku (explorer) dojdeme k cílovému souboru klasifikace_priklady.xls – máte jej dostupný z http://prometheus.vsb.cz/ a v kontextovém menu kliknete na import. Tímto způsobem se spustí průvodce importem dat z Excelu, který si projdeme trošku podrobněji. Úvodní obrazovka průvodce je znázorněna na obr. 30. Importovat budeme standardní datový zdroj, proto ponecháme zatržený Standard data source a Microsoft Excel Workbook a klikneme next. Vybereme soubor, který chceme importovat (klasifikace_priklady.xls) a klikneme na OK. Z dostupných listů vybereme list, který obsahuje zájmová data (pokud si nejste jisti, otevřete se sešit přímo v MS Excel a podívejte se). V našem případě jsou data obsažena na Listu 1. Důležité ale je také pochopení, jakým způsobem bude SAS tato data zpracovávat. Klikněte na tlačítko Options, tedy možnosti (nebo se podívejte na obr. 31).
Bezpečností informatika III
61
Obr. 30: Úvodní obrazovka průvodce dat z MS Excel
Obr. 31: Možnosti importu listu z MS Excel Procesem importu totiž jednak separujeme tabulky obsažené na jednotlivých listech, jednak je převádíme do podoby, která má vnitřním uspořádáním blíže k databázi, než k tabulce z Excelu. Převod proto vyžaduje, aby tabulka v MS Excel měla určitý tvar. Např. 1 řádek vy měl obsahovat popisky sloupců, na listu by neměla být obsažena více než jedna tabulka a podobně. Tento průvodce nemá v rámci
62
Bezpečnostní informatika III
importu příliš veliké možnosti. Průvodce importem v SAS Enterprise Guide je na tom podstatně lépe, ale k tomuto produktu se dostaneme o dost později. Naštěstí náš soubor s daty je připraven k importu a není potřeba v něm provádět nějaké další úpravy. Na obr. 31 si ale všimněte, co všechno je potřeba brát v úvahu. Zrušte okno s možnostmi (cancel) a zadejte next pro přechod k dalšímu kroku importu. V tomto kroku volíme, kam budou uložena importovaná data. SAS provádí ukládání v tzv. knihovnách (library). Některé knihovny jsou dostupné automaticky (WORK, SASHELP a podobně), pomocí průvodce si můžete nadefinovat vlastní (knihovny uvidíte, pokud budete klikat na o úroveň výše dostatečně dlouho (o úroveň výše než jsou disky lokálního počítače)). Pro naše účely bude postačovat knihovna WORK, která je předvolená, a v rámci ní budeme definovat, resp. necháme průvodce, aby definoval, členy knihovny (member). Člena nazveme uvery. Tento krok je graficky zachycen na obr. 32.
Obr. 32: Cíl importu Klikneme na tlačítko next. V posledním kroku máme možnost nedefinovat jméno souboru, kam se má uložit importační skript pro případ, že bychom toužili import opakovat a nechtěli procházet opětovně jednotlivé kroky průvodce. My, ale nic opakovat nehodláme, proto klikneme rovnou na Finish, abychom provedli import a ukončili průvodce.
Bezpečností informatika III
63
V knihovně WORK by nám měla přibýt tabulka Uvery, kterou můžeme zobrazit dvojitým kliknutím (obr. 33).
Obr. 33: Importovaná tabulka Vizuální kontrola importu je důležitá, protože jinak neodhalíte případné chyby importu. Samotný SAS Enterprise Miner spustíme z menu programu SAS, Solutions -> Analysis -> Enterprise miner. Po spuštění vypadá Enterprise miner podobně jako na obr. 34.
Obr. 34: Hlavní okno Enterprise Miner V Enterprise miner máme dispozici jednotlivé diagramy, které představují tok dat různými nástroji za účelem dosažení cíle dolování dat. Samotné skupiny nástrojů jsou dostupné na záložce Tools nebo také v hlavním panelu nástrojů.
64
Bezpečnostní informatika III
Dvojitým kliknutím na untitled si otevřeme náš nový, zatím nepojmenovaný dataminingový projekt, čímž se nám vytvoří volná plocha vpravo, kde můžeme tvořit. Základem dolování jsou data. My máme data dostupná v knihovně WORK -> Uvery, Enterprise datamineru musíme akorát říci, kde je může najít. K tomuto účelu slouží nástroj Input data source, který naleznete v panelu nástrojů, první zleva, ikona:
Pracujeme tak, že uchopíme nástroj a přetáhneme ho na pracovní plochu. Pomocí drag and drop, pak můžeme manipulovat s umístněním nástroje na pracovní ploše. Pokud na takto vytvořenou ikonu klikneme 2x, objeví se nám okno vlastností tohoto nástroje, kde konečně můžeme provést napojení na naše data, viz obr. 35.
Obr. 35: Vlastnosti Input source data Napojení na datový zdroj provedeme kliknutím na tlačítko select. V knihovne WORK najdeme naši tabulku uvery a potvrdíme výběr. Enterprise miner rovnou také vypočte velikost dat (12 řádků v 6-ti sloupcích). Na záložce variable, která se nám zpřístupní napojením datového zdroje, máme možnost definovat role proměnných. Rolí se myslí úkol, který bude daný sloupec (atribut) plnit v našich analýzách. Jelikož chceme zkusit asociační pravidla, vybereme si libovolný atribut a nastavíme jeho roli na target. Změnu
Bezpečností informatika III
65
role provedeme z kontextového menu (set role). Technicky je možné nastavit libovolné množství atributů jako cílových, asociační analýza v SAS, ale bere v úvahu pouze dvojici. Z panelu nástrojů přetáhneme nástroj Association (ikona níže)
A zavedeme do ní datový tok z tabulky WORK.UVERY. Tento tok nadefinujeme tak, že najedeme kurzorem na tabulku WORK.UVERY (to, že jste na správném místě, poznáte tak že se kurzor změní na křížek), kliknete a táhnete na právě vytvořený uzel asociace. Asociační analýzu spustíte tak, že kliknete pravým tlačítkem na uzlu Association a vyberete možnost run. Výsledkem Vašeho snažení by měl stav podobný obrázku 36.
Obr. 36: Diagram řešení asociací Pokud se Vám objevilo hlášení, že žádná asociace nebyla nalezena, pak jste postupovali správně. Náš datový soubor je prostě příliš malý na to, aby v něm bylo možné smysluplně provádět tento typ analýz. Pokud bychom si chtěli vyzkoušet plnohodnotnou asociační analýzu, potřebovali bychom data jiná a SAS taková cvičební data obsahuje v knihovně SAMPSIO tabulku ASSOCS. Tato tabulka obsahuje pouze 3 sloupce (zákazník, čas a produkt). Jedná se o tabulku v čase ukotvených nákupů. Role zákazníka (customer) bude id, role času (time) bude rejected a role produktu (product) bude target. Časovou hodnotu zatím odmítáme z důvodu
66
Bezpečnostní informatika III
provedení základní asociační analýzy, tak jak jsme si ji vysvětlili, SAS totiž umožňuje i sekvenční analýzu, kterou ale z prostorových důvodů vynecháme. Když si nadefinujeme vhodně diagram (input data source napojený na SAMPSIO.ASSOCS s nastavenými rolemi a připojený na asociační uzel), můžeme z kontextového menu asociačního uzlu provést spuštění analýzy. V tomto případě SAS zahlásí, že měl při výpočtu úspěch a nabídne nám zobrazení výsledku. Výsledek je zobrazen formou tabulky, kterou máte možnost vidět na obr. 37.
Obr. 37: Výsledek asociační analýzy SAMPSIO.ASSOCS A máme zde i zajímavé výsledky – pivo heineken se prodávalo dobře s křupkami (důvěryhodnost 61 – 75%) a spousta jiných důležitých poznatků.
?
Kontrolní otázky 1. Jaký je rozdíl mezi rozhodovacími a asociačními pravidly? 2. Jak nejjednodušeji odhadnout, který uzel je vhodný pro větvení rozhodovacího stromu? 3. Co jsou to sekvenční pravidla a jak se liší od klasických rozhodovacích pravidel? 4. Jak lze řešit chybějící data pro pravidlově orientované metody a na co je potřeba si dát pozor při implementaci těchto řešení?
Bezpečností informatika III
67
6 Bayesovy filtry Průvodce studiem V této kapitole probereme další možnosti řešení klasifikačních problémů. Tentokrát si na pomoc přizveme teorii pravděpodobnosti a závěry, ke kterým přišel již v průběhu 18. století Theadore Bayes. Po prostudování této kapitoly budete znát princip fungování bayesových filtrů možnost jejich nasazení pro řešení klasifikačních problémů některé další aplikace tohoto algoritmu Čas nutný ke studiu Pro prostudování této kapitoly budete potřebovat minimálně hodinu, dvě hodiny v případě že se rozhodnete přepočítat příklady (což rozhodně doporučuji ).
Bayesovy filtry jsou pojmenovány po reverendu Thomasi Bayesovi (1702 – 1761). Posmrtně v roce 1764 byly vydány jeho úvahy o možnostech nasazení pravděpodobnostního počtu pro hodnocení pravděpodobnosti různých jevů na základě pozorování. Tyto spisy obsahovaly také tzv. Bayesův teorém někdy také označován jako Bayesův zákon nebo pravidlo), kterým se zapsal do dějin. Tento teorém dokazuje, že pravděpodobnost události A, která je podmíněna událostí B, je odlišná od pravděpodobnosti události B, která je podmíněna událostí A. Přesto mezi těmito pravděpodobnostmi existuje vztah, který je možno využít pro různé úvahy. Právě tento vztah popisuje Bayesův teorém. V čem tedy spočívá kouzlo teorému? Jedná se o matematické pravidlo, které vysvětluje jakým způsobem je potřeba změnit existující domněnky o určité hypotéze ve světle nových poznatků. Bayesův teroém tedy umožňuje shromažďovat a vyhodnocovat důkazy, které podporují (nebo vyvracejí) určité hypotézy. Teorém je zejména díky některým svým vlastnostem: - podporuje změnu konceptu v čase (řešení pomocí pravidlově orientovaných metod je možné ale musí se použít speciálně upravené algoritmy) - nejsou problém chybějící data - umožňuje kombinovat stávající poznatky s poznatky novými
68
Bezpečnostní informatika III
- relativně jednoduchá softwarová implementace Základní vzorec vypadá následovně (10): P( H | E )
P( E | H ) P( H ) P( E )
(10)
Kde H hypotéza E evidence (důkaz) P(H) apriorní pravděpodobnost hypotézy P(H|E) aposteriorní pravděpodobnost (jak se změní pravděpodobnost hypotézy, pokud nastalo E) P(E|H) pravděpodobnost nových faktů za předpokladu, že hypotéza H je pravdivá P(E) pravděpodobnost evidence Vzorec sám o sobě nám toho mnoho neřekne. Podívejme se raději na příklad aplikace Bayesova teorému, který by jeho nasazení mohl ozřejmit. Příklad: aplikace Bayesova teorému (převzato z [12]) Mějme školu, kterou navštěvuje 60% chlapců a 40% dívek. Studentky nosí kalhoty nebo sukně (přibližně půl na půl), všichni studenti nosí kalhoty. Pozorovatel vidí v dálce (náhodného) studujícího, ale jediné co je schopen rozeznat, je že nosí kalhoty. Jaká je pravděpodobnost že se jedná o dívku?. Událost A = student je dívka P(A) = pravděpodobnost, že studující je dívka bez ohledu na další informace je 40%, tedy P(A) = 0,4 P(B|A) = pravděpodobnost, že studující nosí kalhoty za předpokladu, že se jedná o dívku -> 50%, tedy P(B|A) = 0,5. P(B) = pravděpodobnost, že náhodně vybraný studující nosí kalhoty: P(B) = P(B|A)P(A) + P(B|A´)P(A´) = 0,5 . 0,4 + 1 . 0,6 = 0,8. Pravděpodobnost toho, že náhodně pozorovaný studující je dívka vypočteme následovně: P( A | B )
P( B | A) P( A) 0,5 0,4 0,25 P( B ) 0,8
Tedy šance, že náhodně pozorovaný studující v kalhotách je ženského pohlaví je pouze 25%.
Bezpečností informatika III
69
Výše uvedený příklad pouze obecně aplikuje Bayesův teorém na určité úvahy, ve skutečnosti se nejedná o klasifikační problém, který nás bude vzhledem k našemu zaměření na datamingu primárně zajímat. Zkusme reformulovat příklad výše, aby se z něj klasifikační problém stal. Pokud vidím v dálce studujícího, který má oblečené kalhoty jedná se spíše o dívku nebo chlapce? Klasifikačním úkolem je přiřazení třídy pohlaví k pozorované osobě na základě podpůrných důkazů (nosí kalhoty). V takovém případě nemůžeme vzorec (10) použít samostatně, ale musíme vypočítat aposteriorní pravděpodobnost každé dostupné hypotézy (pohlaví muž/žena) při zohlednění podpůrných důkazů. Přijímáme pak nejpravděpodobnější hypotézu. Matematicky bychom to mohli vyjádřit pomocí vzorce (11). H max H J , právě když
P( H J | E ) max t
P( E | H t ) P( H t ) P( E )
(11)
Vzorec (11) pracuje se skutečnými pravděpodobnostmi. Při nasazování Bayesových filtrů nás ale absolutní pravděpodobnost nezajímá (pokud pomineme samotnou problematičnost určení takové pravděpodobnosti). Vzorec (11) proto lze zjednodušit, aniž by byla narušena schopnost filtru poskytovat validní údaje. Hodnota pravděpodobnosti důkazu P(E) je pro všechny hypotézy totožná, proto nám nepřispívá k volbě nejpravděpodobnější, z úvah ji proto můžeme vyloučit. Podobnou úvahou můžeme vyloučit P(H). Zdůvodněním může být, že pravděpodobnost jednotlivých hypotéz je stejná. To by mohlo platit pro náš příklad, protože rozložení chlapců a dívek v populaci je přibližně stejné). V takovém případě na P(H) nezáleží a můžeme jej vyloučit. Při zohlednění zjednodušujících úvah volíme takovou hypotézu H, která odpovídá maxt P(E|Ht). Zkusme provést výpočet pro náš „kalhotový“ problém. Příklad: klasifikace pomocí Bayesova teorému Pokud vidím v dálce studujícího, který má oblečené kalhoty jedná se spíše o dívku nebo chlapce?
P(kalhoty | dívka) = 0,5 P(kalhoty | chlapec) = 1 Přijímáme hypotézu, že pozorovaná osoba je spíše pohlaví mužského, což je logické (a došli bychom k tomu i bez nasazení Bayesovy věty).
70
Bezpečnostní informatika III
?
Kontrolní úkol Stejný případ, jiné pravděpodobnosti. Pozorujeme v dálce osobu s kalhotami, ale víme, že školu z 80% navštěvují dívky, škola je ale také oblíbena skotskými chlapci (tvoří 20% chlapců) a ti zde zásadně nosí sukně. Tedy: 80% chlapců a 50% dívek nosí kalhoty. Řešení: žena (0,4), muž (zamítá se 0,16)
Výše uvedený příklad je extrémně jednouchý. Máme pouze dvě cílové hypotézy a jeden podpůrný důkaz, který při klasifikace musíme zohlednit. To není dvakrát praktické. Pokud se podíváme zpět na klasifikaci pomocí rozhodovacích pravidel a stromů (na příklad s úvěry), pak zjistíme, že i relativně jednoduché příklady klasifikace pracují s větším množstvím podpůrných důkazů, které je při klasifikaci nutno zohlednit. Zohlednění můžeme provést pomocí tzv. naivního bayesovského klasifikátoru (12). P( H | E1 ,..., E K )
P( E1 ,...Ek ) P( H ) P( E1 ,...E K )
K
P( H )
P( E
K
P( E k 1
k
)
k 1
k
| H)
(12)
Při hledání nejpravděpodobnější hypotézy za daných důkazů opět můžeme P(E) zanedbat. Budeme tedy hledat hypotézu (13): K max P( H t ) P( Ek | H t ) t k 1
(13)
Vstupním podmínkou použití naivního klasifikátoru je vzájemná nezávislost jednotlivých důkazů. Při řešení klasifikačních problémů pomocí Bayesobých filtrů samozřejmě nemáme hodnoty pravděpodobností k dispozici (podobně jako třeba u rozhodovacích stromů). K dispozici ale máme trénovací množinu, která nám umožní pravděpodobnost aproximovat pomocí četností. Pravděpodobnost hypotézy P(H) lze vypočítat následovně (14): P( H t )
Kde nt n
nt n
(14) četnost výskytu hypotézy v trénovací množině celkový počet záznamů v trénovací množině
Pravděpodobnost hypotézy Ht za přítomnosti důkazu Ek můžeme vyjádřit následovně (15):
Bezpečností informatika III
P( E K | H t )
nt ( A j ( vk ))
71
(15)
nt
Kde nt(Aj) četnost výskytu hodnoty atributu vk odpovídající hypotéze Ht nt četnost výskytu hypotézy Ht v trénovací množině Pokud bychom tyto poznatky aplikovali na náš příklad s úvěrováním, který jsme rozebírali už v kapitole 5, s trénovací množinou odpovídající tabulce 3, pak bychom museli spočítat jednotlivé pravděpodobnosti hypotéz samotných, ale také kombinace hodnot jednotlivých atributů a cílové hypotézy, tedy: Celkem řádků 12 P(úvěr(ano)) = 8/12 = 0,667 P(úvěr(ne)) = 4/12 = 0,333 P(příjem(vysoký)|úvěr(ano)) = 5/5 = 1 P(příjem(vysoký)|úvěr(ne)) = 0 P(konto(vysoké)|úvěr(ano)) = 4/4 = 1 P(konto(vysoké)|úvěr(ne)) = 0 … Vypočtené pravděpodobnosti pak dosazujeme do vzorce (13) a vybíráme nejpravděpodobnější hypotézu.
?
Kontrolní úkol Dopočtěte výše uvedený příklad. Proveďte výpočet vstupní hodnoty atributů reprezentované řádky K5 a K9 tabulky 3.
Při malém počtu vstupních údajů v trénovací množině, se vystavujeme riziku, že vypočtené pravděpodobnosti (14 – 15) jsou podhodnocené. V takovém případě se doporučuje nasazovat různé korekční mechanismy jako např. Laplaceovu korekci nebo m-odhad. Způsoby výpočtu naleznete v literatuře např. [9]. Pro úplné zohlednění vzájemné závislosti/nezávislosti jednotlivých důkazů se používají tzv. bayesovské sítě. Jejich konstrukce je ovšem trošku složitější a přesahuje tak možnosti tohoto textu.
?
Kontrolní otázky 1. vysvětlete podstatu baysovského klasifikátoru. 2. Je možné použít v rámci trénovací množiny řádky obsahující chybějící hodnoty? 3. Proveďte srovnání bayesovského klasifikátoru
72
Bezpečnostní informatika III
s rozhodovacími stromy. 4. Za jakých předpokladů můžeme klasifikátoru vynechat P(H)?
z bayesovského
Bezpečností informatika III
73
7 Neuronové sítě Průvodce studiem Zajímavou metodou, která je dobře použitelná v rámci dataminingu, je klasifikace pomocí neuronových sítí. Při klasifikaci se hlavně využívá toho, že pro nalezení vztahu mezi vstupními a cílovými atributy není potřeba znát povahu tohoto vztahu, plně nám postačuje pevná víra v jeho existenci. Po prostudování této kapitoly budete znát princip fungování neuronových sítí úskalí přípravy dat pro adaptaci neuronové síti a jak se vyvarovat tzv. přeučenosti neuronové sítě Čas nutný ke studiu Pro prostudování této kapitoly budete potřebovat přibližně hodinu.
Myšlení je nejspíše tím hlavním, čím se člověk liší od zvířat. Není divu, že snaha o pochopení jeho fungování a následně napodobování jeho některých aspektů pomocí výpočetní techniky inspirovalo tolik různých vědců. Do této oblasti patří také umělé neuronové sítě, které se snaží napodobit fungování neuronů v mozcích živých organismů. První matematický model neuronu vznikl již v roce 1943, nicméně rychlý rozvoj oboru přinesl až rozvoj výpočetní techniky zejména v 70. a 90 letech. V současné době nasazování neuronových sítí zevšednělo natolik, že se staly běžnou součástí nástrojů tzv. business inteligence a nástrojů pro data mining, což je také důvod, proč se s těmito nástroji setkáváme právě zde. Vraťme se ale k předobrazu umělých neuronových sítí – k neuronům v mozku a způsobu, jakým fungují. Na schéma neuronu se můžete podívat na obr. 38. Obr. 38 obsahuje pouze velmi zjednodušené schéma neuronu (nicméně v rozsahu, který nám bude postačovat pro odvození podstatných vlastností umělé reprezentace neuronu. Literatura [13], ale obsahuje i mnohem podrobnější schéma neuronu (i fotografii), které je korektní i z lékařského hlediska. Neuron je tvořen jádrem, které slouží jako zdroj energie pro neuron a umožňuje jeho běžné fungování, tělem, výběžky (dendrity), na které se připojují ostatní neurony pomocí svých axonů. Axony jsou přitom delší výběžky, které
74
Bezpečnostní informatika III
jsou schopny předávat elektrochemické impulzy ostatním neuronům, na které jsou připojeny.
Obr. 38: Schéma neuronu (převzato a doplněno z [13]) Synapse plní velmi důležitou úlohu tzv. prahování. Prahování rozhoduje, jakým způsobem se bude signál šířit v neuronové síti. Prahování funguje tak, že synapse zachytí signál přicházející do neuronu a vyhodnotí jeho sílu, pokud síla signálu přesáhne určitou hodnotu (práh) synapse signál posílí a pošle dál, v opačném případě dojde k utlumení signálu. Nastavení „váhy“ prahu je tedy skutečným základem pro fungování neuronu a schopnosti neuronové sítě se adaptovat na zvolený koncept, což je vlastnost, kterou se snažíme napodobit v umělých neuronových sítích. Podívejme se na strukturu umělého neuronu, v tomto případě se jedná o nejspíše nejpoužívanější model neuronu, který je zároveň velmi blízký svými vlastnostmi neuronu „přírodnímu“. Reprezentaci perceptronu máte k dispozici na obr. 39. Na signály jdoucí do neuronu jsou aplikovány váhy a takto modifikované signály jsou agregovány a podrobovány operaci prahování, která rozhodne o síle signálu, která bude šířena z neuronu dále.
Bezpečností informatika III
75
Obr. 39: Struktura perceptronu Už samotný název neuronové sítě nám naznačuje, že neurony nebudou pracovat samy, ale budou zapojeny do složitější sítě. Pro účely dataminingu se většinou používají více vrstevné sítě, které se „adaptují s učitelem“. Adaptací s učitelem rozumíme, že v rámci adaptace se porovnávají výsledky dosažené s výsledky, které jsou obsaženy v trénovací množině a váhy v síti se upravují tak, aby se chyby dosahované sítí minimalizovaly. Nejpoužívanější metodou adaptace je tzv. backpropagation (metoda zpětného šíření chyb). Vraťme se ke struktuře neuronové sítě. Rozlišujeme tři typy vrstev: - vstupní - pracovní (skrytá) - výstupní V neuronové síti máme vždy jednu vstupní a výstupní vrstvu, jejichž struktura se odvozuje od struktury vstupních a požadovaných výstupních údajů. Pracovních vrstev může být více, počet neuronů v nich také není nijak omezen – určujeme jej více méně intuitivně – volíme počet větší než je počet neuronů ve vstupní vrstvě (většinou máme větší množství vstupních údajů než údajů výstupních). Obecně můžeme znázornit strukturu neuronové sítě podobně jako na obr. 40. Základní otázkou, kterou při použití neuronových sítí řešíme je způsob, jakým odvodíme strukturu neuronové sítě. Zkusme tedy dát dohromady neuronovou sít, která bude mít za úkol vyřešit klasifikační problém s našimi oblíbenými úvěry (jako trénovací množina bude sloužit tab. 3). Pro úvěrový problém bude mít vrstva vstupní 4 neurony odpovídající jednotlivým atributům: - příjem - konto - pohlaví - nezaměstnaný
76
Bezpečnostní informatika III vstupní vrstva
pracovní vrstva
výstupní vrstva
Obr. 40: Obecná struktura neuronové sítě Výstupní vrstva bude mít jediný neuron dopovídající cílovému atributu úvěr. V pracovní vrstvě může být například šest neuronů. Je také očividné, že neuronovou síť zadaptujeme a nasadíme jen velmi obtížně při ručním výpočtu. Zkusme tedy opět použít SAS Enterprise Miner. Provedli bychom to tak, že bychom vložili datový uzel napojený na tabulku UVERY, ve kterém chyhom nastavili role input pro příjem, konto, pohlaví, nezamětnaný a roli target pro úvěr. Následně bychom napojili uzel neuronové sítě (viz. obr. 41).
Obr. 41: Neuronové sítě v SAS Enterprise Mineru A model můžeme spustit (pravým tlačítkem na uzlu neural network a run). SAS by měl zobrazit některé informace o procesu adaptace, které by měly vypadat podobně jako ty znázorněné na obr. 42.
Bezpečností informatika III
77
Obr. 42: Statistiky adaptace neuronové sítě Zajímavé jsou položky, které se týkají chyb zejména average error (průměrná chyba), maximum absolute error (maximální absolutní chyba). Všimněte si, že tyto chyby nejsou nulové a nulové nikdy nebudou bez ohledu na to, s jakou neuronovou sítí pracujeme. Nulová hodnota chyb je v tomto případě dokonce nežádoucí. Ještě lépe je možno vývoj průměrné chyby neuronové sítě vidět z grafu popisujícího adaptaci sítě (obr. 43). Z tohoto grafu je patrné, že celý proces adaptace sítě proběhl velmi rychle, bylo vyžadováno pouze 6 iterací. V rámci adaptačního procesu se nám také výrazným způsobem měnila průměrná chyba sítě. Síť s náhodně nastavenou hodnotou vah začíná s chybou okolo 65%, tato chyba ale v průběhu adaptace prudce klesá a už po pěti iteracích je na úrovni přibližně 1%. Všimněte si, že dále už hodnota chyby příliš neklesá a nemá tedy smysl příliš pokračovat v procesu adaptace, protože další iterace by přinesly pouze zanedbatelná zlepšení. Snahou o minimalizaci chyby za každou cenu dokonce můžeme omezit použitelnost adaptované sítě. Síť totiž sice může naprosto přesně klasifikovat data obsažená v trénovací množině, jiná data, ale mohou být zpracovávána chybně. O takové neuronové síti často říkáme, že je přeučená. Je potřeba si uvědomit, že trénovací množina obvykle neobsahuje vyčerpávající výčet všech možných kombinací hodnot atributů. Tedy přijmutím nevýznamné (přijatelné) chyby získáváme univerzálněji použitelnou neuronovou sít.
78
Bezpečnostní informatika III
Obr. 43: Chyba v průběhu adaptace neuronové sítě Pokaždé adaptaci bychom se přesto měli přesvědčit, že výsledky sítě odpovídají našim představám a to s použitím validační sady dat, která obsahuje také jiná data, než jsou ta obsažená v trénovací množině.
?
Kontrolní otázky 1. Vysvětlete problém přeučenosti neuronové sítě. 2. Zkuste zobecnit principy definice vstupní a výstupní vrstvy neuronové sítě. 3. Kolik neuronů by měla mít pracovní vrstva. 4. Jak určíme počet pracovních vrstev.
Bezpečností informatika III
79
8 Evoluční algoritmy Průvodce studiem Pro úplnost v souvislosti s dataminingem je potřeba zmínit také evolučně orientované metody jako jsou třeba genetické algoritmy. Na rozdíl od předchozích kapitol, je tato pojatá spíše jako přehledová – nebudeme tedy zabíhat k praktickému využití. Ve srovnání s ostatními kapitolami bude tato také stručnější. Čas nutný ke studiu Pro prostudování této kapitoly budete potřebovat přibližně 20 minut.
V předchozí kapitole jsme zmiňovali neuronové sítě. Evoluční algoritmy se podobně jako ony inspirují v živé přírodě. Zatímco se ale neuronové sítě snažily napodobit fungování mozku, evoluční algoritmy se snaží napodobit proces, který vedl k přizpůsobování života podmínkám na Zemi – tedy evoluci. Evoluce v přírodě funguje tak, že jedinci, kteří jsou lépe přizpůsobení prostředí, ve kterém žijí, mají lepší šanci na zachování svých genů v populaci. Postupem generací se z výhody stává standard a preferovány jsou další „přizpůsobení“, která jedinci dávají další výhody. Evoluční algoritmy se snaží tento postup využít ve svůj prospěch. Nepracuje se samozřejmě se skutečnou DNA – DNA je v tomto případě nahrazena určitými nosnými vlastnostmi (atributy) případu (jedince v populaci). Postupujeme tak, že vytvoříme prvotní populaci náhodným nastavením vlastností jedinců a následně vytváříme nové jedince a obměňujeme ty staré. Nový jedinec může vzniknout dvěma způsoby – křížením (kombinací vlastností dvou nebo více jedinců) nebo mutací (náhodná drobná změna vlastnosti jedince). Náhrada jedinců v dané generaci může být úplná nebo částečná – obě přitom mají svůj předobraz v přírodě. Například jednoleté rostliny svou populaci obnoví vždy znovu v období vegetace, pro živočichy je ovšem typická koexistence jedinců různých generací. Při nasazování evolučních algoritmů potřebujeme také vědět, jak moc jsme úspěšní, blížíme se už k cíli, nebo jenom přešlapujeme na místě bez možnosti konvergence k cíli? K tomuto účelu se používá tzv. fitness funkce. Tuto funkci chápeme jako optimalizační funkci, kterou se podle povahy řešeného problému snažíme minimalizovat nebo maximalizovat. Fitness funkci v dataminingu může představovat třeba chyba v klasifikaci, kterou budeme chtít minimalizovat. Protože evoluční algoritmy jsou v podstatě nekonečné (lze je počítat neomezenou dobu) je potřeba také omezit délku, po
80
Bezpečnostní informatika III
kterou bude výpočet prováděn. Omezení může mít povahu maximálního počtu generací nebo třeba požadovaná pozitivní změna ve fitness funkci po období několika generací (tedy podobně vyhodnocení iterací adaptace neuronové sítě a její ukončení v souvislosti se stabilizací průměrné chyby neuronové sítě). Reprezentanti klasifikačních problémů (jedinci) jsou realizováni jako jednotlivé segmenty bitových reprezentací hodnot atributů. Převod lze vyjádřit podobně jako v tabulce 16. Tab. 16: Bitová reprezentace hodnot atributů úvěrový problém Atribut číslo Bitová reprezentace 0 00 Konto Nízké 1 01 Střední 2 10 Vysoké 0 0 Příjem nízký 1 1 Vysoký 0 0 Pohlaví muž 1 1 Žena 0 0 Nezaměstnaný ne 1 1 Ano 0 0 Úvěr ne 1 1 Ano V takovém případě můžeme sestavovat kombinace hodnot atributů do pravidel např. IF konto(nízké) AND nezaměstnaný(ano) THEN úvěr(ne) A tyto pravidla převést do podoby bitové reprezentace: 00 1 0, takové reprezentace pravidla bude představovat jedince v populaci obhospodařované genetickým algoritmem. Tento jedinec bude z hlediska schopnosti slnit naše představy zhodnocen fitness funkcí. V tomto případě se bude hodnotit, zda výsledné pravidlo je schopno správně klasifikovat. Opět je tedy nutná existence trénovací množiny, vůči které se bude kontrolovat populace v průběhu výpočtu. Počáteční populace pravidel bude vytvořena zcela náhodně. S postupem generací, se nabídka pravidel bude měnit v důsledku aplikace operátorů křížení a mutace. Evoluční algoritmy nemusí být nasazovány samostatně, ale spolu s dalšími typy algoritmů, příkladem může být možnost propojení neuronových sítí a genetických algoritmů. Genetické algoritmy mohou posloužit buďto v rámci adaptace neuronové sítě pro nastavování vah nebo mohou být použity pro úpravu struktury neuronové sítě (např. počet pracovních vrstev a neuronů v nich).
Bezpečností informatika III
?
81
Kontrolní otázky 1. Jaké jsou operátory tvorby jedinců v genetických algoritmech? 2. Vysvětlete princip návrhu jedinců pro řešení klasifikačních problémů. 3. Co je to fitness funkce? 4. Vysvětlete rozdíly, výhody a nevýhody generační výměny úplné a částečné. (odpověď na tuto otázku ve skriptech nenajdete, nicméně zkuste uvažovat, trošku oběcněji)
82
Bezpečnostní informatika III
Literatura [1] Wikipedie: Real Time Database [on-line]. Dostupné z WWW
[cit. 2007-08-10] [2] Kao, B.; Garcia – Molina, H.: An Overview of Real-time Database Systems. NATO Advanced Study Institute on Real-Time Computing, 9. října 1992 [cit. 2007-08-10] [3] Domácí stránky firmy MICROSYS s.r.o. [on-line]. Dostupné z WWW [cit. 2007-08-17] [4] Good Practice Guide – Process Controll and SCADA Security [on-line]. National Infrastructure Security Coordination Centre, dostupné z WWW [cit. 2007-10-23], 25str. [5] NISCC Good Practice Guide on Firewall Deployment for SCADA and Process Control Networks [on-line]. National Infrastructure Security Coordination Centre, dostupné z WWW [cit. 2007-10-23], 42str. [6] Windows Personal Firewall Analysis [on-line]. Dostupné z WWW [cit. 2007-10-24]
[7] Dostálek, L.: Velký průvodce protokoly TCP/IP a systémem DNS [on-line]. Dostupné z WWW [cit. 2007-10-24] [8] Ing. Zdeněk Štuksa – konstrukce a výroba jednoúčelových strojů a automatizační techniky [online]. Dostupné z WWW [cit. 2010-06-08] [9] Berka, P.: Dobývání znalostí z databází. Academia: Praha 2003, 366 str., ISBN 80-200-1062-9 [10] Šenovský, P.: Bezpečnostní informatika 2 [online]. 4. vydání, VŠB-TU Ostrava: Ostrava 2010, 60 str., dostupné z WWW [cit. 2010-06-10] [11] Berka, P.: Aplikace systémů dobývání znalostí pro analýzu medicínských dat [online]. Dostupné z WWW [cit. 2010-06-18] [12] Bayes' theorem [online]. Dostupné z WWW [cit. 2010-06-23] [13] Neuron [online]. Dostupné z WWW [cit. 2010-06-28]
Bezpečnostní informatika III Ing. Pavel Šenovský, Ph.D. 2. vydání Ostrava: 2010