Uživatelské nástroje

Nástroje pro tento web


mrm:ea:start

Generování umělých dat

Pro vygenerování vhodné varianty dat je použit evoluční algoritmus. Jeden jedinec představuje jednu možnou variantu umělých dat. V zadání se určí sloupce, které mají být ve vytvářené datové matici, jejich typ a zejména rozsahy (případně četnosti) hodnot. Zároveň je nastaven i celkový počet záznamů v datové matici.

FIXME Zadání úlohy pro generování umělých dat se nazývá RM případ (RM Case) pro odlišení od standardních DZD úloh, které se používají pro definici požadavků na vztahy „skryté“ v generovaných datech.

Evoluční proces

Na začátku evolučního procesu je populace jedinců vytvořena zcela náhodně. Při generování konkrétních hodnot v daném sloupci jsou dodržovány požadavky na minimální/maximální hodnotu, případně pouze povolené hodnoty dané výčtem. Zároveň je zajištěno, že histogram četností vygenerovaných hodnot bude odpovídat zadané volbě (uniformní, gaussovské nebo podle zadaných frekvencí u výčtu hodnot).

Pro každou variantu dat (jedince) jsou následně vyřešeny všechny zadané data-miningové úlohy a je zjištěn počet skutečně nalezených hypotéz. Ten závisí na konkrétní podobě hodnot ve sloupcích datové matice právě zkoumaného jedince. Fitness jedince je odvozena od rozdílu mezi požadovaným počtem hypotéz a počtem hypotéz skutečně získaným. Pokud varianta dat splňuje všechny požadavky na skryté vztahy, je její fitness rovna 0.

Perspektivní jedinci (s nižšími hodnotami fitness) mají větší šanci přenést své vlastnosti do další generace pomocí některé evoluční operace. Po dostatečném počtu evolučních iterací by se měla podoba dat představovaných nejlepším jedincem dostat do stavu, že nad nimi spuštěné data-miningové úlohy budou mít na výsledku požadované počty hypotéz. Tím evoluce končí.

Primární míra zajímavosti

Rozlišování pouze na úrovní hypotéza je × hypotéza není ve výsledcích, obvykle nestačí. Evoluce potřebuje vědět, že jeden jedinec je „o něco“ lepší, než druhý. A to i v případě, že ani jeden z nich ještě neplní daný požadavek úplně.

Více viz: Primární míra zajímavosti

Frekvence hodnot a povolené rozpětí

Počáteční frekvence hodnot v jednotlivých sloupcích je nutné volit s ohledem na požadované vztahy, které chceme do dat „skrýt“. V průběhu evoluce dochází k různým změnám hodnot s cílem nalézt data, která splňují všechny požadované vztahy. To však může vést k deformaci dat, kdy některé z hodnot začnou výrazně převažovat a jiné se naopak úplně vytratí.

Tomu můžeme zabránit požadavkem na udržení stále stejného rozložení hodnot v daném sloupci v průběhu celé evoluce. To však může zabránit evoluci v nalezení varianty dat splňující všechny požadavky. V tom případě povolíme změnu rozložení hodnot, ale zadáme maximální rozpětí, ve kterém se četnost každé z hodnot musí pohybovat.

Mějme například sloupec Vzdělání s hodnotami , a . Pro každou z kategorií zadáme povolené rozpětí pro každou jako „33 % ± 10 p.b.“. Tím bude zaručeno, že v celém průběhu evoluce (a tedy i ve finální variantě dat) budou četnosti kategorií udržovány v povoleném rozpětí <23;43>.

Frequency guiding rules

Požadavky na četnost hodnot se zadávají stejně jako jiné požadavky na data – tedy jako úlohy DZD. V tomto případě jako dvě úlohy pro 4ft-Miner – první pro dolní a druhá pro horní mez. Pro tento typ požadavků používáme označení Frequency guiding rules.

Protože by ruční zadávání požadavků bylo pracné (zejména pro sloupce s mnoha hodnotami), je možné požadavky vytvářet automaticky. Zároveň je však možné následně meze upravit individuálně pro každou z kategorií.

Dílčí evoluce

U rozsáhlejších úloh může trvat velmi dlouho, než se pomocí náhodných evolučních operací podaří nalézt variantu dat, která splňuje všechny požadavky. Potom může být vhodné řešit nejprve jednotlivé dílčí požadavky samostatně.

Máme-li deset vztahů, které chceme do dat „skrýt“, vytvoříme nejprve deset RM případů, kde každý bude hledat variantu dat pro jeden dílčí vztah. Následně vytvoříme finální RM případ, do kterého vložíme všech deset požadavků. Počáteční populace však nebude vytvořena zcela náhodně, ale prvních deset jedinců bude odpovídat výsledkům dílčích evolucí (pomocí Data Presets). Od samého počátku tak v populaci bude pro každý z požadovaných vztahů jedinec, který jej splňuje. Tím zvyšujeme pravděpodobnost, že se pomocí evolučních operací rychleji nalezne varianta dat, která bude splňovat všech deset požadavků zároveň.

Pro rozšiřování vlastností řešení dílčí evoluce do celé populace se hodí zejména operace šlechtění. Jedinec představující řešení dílčí evoluce bude obvykle zároveň nejlepším řešením odpovídajícího dílčího požadavku i ve finální evoluci. Bude proto potenciálním druhým rodičem při šlechtění a jeho hodnoty se tak budou kombinovat s aktuálně úplně nejlepším jedincem.

Mutant

Speciálním typem dílčí evoluce je RM případ pracovně nazývány mutant. Výsledkem je varianta dat, která obsahuje ve všech svých řádcích hodnoty splňující daný dílčí požadavek. Budeme například chtít, aby v datech platil vztah:

Nocí( 28) ⇒95 % TypPobytu( služební) ∧ DenTýdne( pondělí)

Jde o velmi silný požadavek (platnost je 95 %), jehož četnost je naopak velmi nízká – pobytů na 28 nocí (čtyři týdny) je totiž v datech velmi málo (kolem 2 %). Evoluci by trvalo velmi dlouho, než by se jí podařilo nalézt variantu dat, která by takovýto vztah obsahovala.

Zachycení vztahu v datech by navíc ztěžovaly i další dílčí požadavky, které na data máme a které mohou být částečně protichůdné (v datech Hotel 2015 to byl vztah požadující, že služební cesty jsou obvykle pouze na jednu noc).

V takovém případě pomůže vytvoření RM případu typu „mutant“, u kterého rovnou v zadání generovaných sloupců zadáme, že ve sloupci PNoci se může objevit pouze hodnota 28, ve sloupci PTypPobytu pouze hodnota služební a ve sloupci PPobytOd (ze kterého je odvozen sloupec PDenTydne) pouze datumu reprezentující pondělí. Na evoluci nebudeme mít žádné další požadavky, takže skončí hned v první iteraci.

Takto získaný „výsledek“ následně použijeme jako Data Preset v definici finálního RM případu. Zároveň budeme požadovat, aby odpovídající jedinec byl neustále přítomný v populaci. V následně spuštěné evoluci se v každé iteraci může pomocí evoluční operace šlechtění snadno přenést do aktuálně nejlepšího jedince řádek obsahující požadovanou kombinaci hodnot 28, služební a pondělí.

To je způsobeno tím, že ve variantě dat typu mutant je úplně jedno, který řádek se při šlechtění přenese, protože hodnoty jsou ve všech řádcích stejné. Někdy se změnou hodnot „zkazí“ jiné požadované vztahy, ale alespoň někdy se podaří zlepšit celkovou fitness. Zároveň můžeme zkoušet nastavovat různou pravděpodobnost šlechtění a počet přenášených řádků.

mrm/ea/start.txt · Poslední úprava: 2015/10/12 21:09 (upraveno mimo DokuWiki)