====== ZALOHA Typové úlohy ====== Cílem příkladů je naznačit možnosti systému [[https://lispminer.vse.cz/wiki/|LISp-Miner]]. Tento systém je v současné době pravděpodobně nejrozsáhlejší implementace původní české [[https://lispminer.vse.cz/guhate/doku.php?id=start|metody GUHA]] explorační analýzy dat. Tato metoda je, v souladu s článkem [[https://dl.acm.org/citation.cfm?id=1655709|The GUHA method and its meaning for data mining]], prezentována jako metoda pro dobývání znalostí z databází. Příklady prezentují důležité typové úlohy řešitelné pomocí sedmi z devíti GUHA procedur implementovaných v systému LISp-Miner. Přehled prezentovaných typových úloh je [[lm_guha_di_typy_uloh|zde]]. Některé z těchto typových úloh poukazují na důležité rysy jednotlivých GUHA procedur, kterými se liší od jiných procedur řešících podobné úlohy. Jedná se o * proceduru 4ft-Miner pro hledání asociačních pravidel, která je porovnávána s asociačními pravidly produkovanými známým [[https://dl.acm.org/citation.cfm?id=672836|algoritmem apriori]], podrobnosti jsou [[lm_guha_di_uvod_resene_prikl#Procedura 4ft-Miner a algoritmus apriori|zde]] * proceduru Ac4ft-Miner pro hledání akčních pravidel, která je porovnávána s akčními pravidly popsanými v knize [[https://www.springer.com/gp/book/9783642356490|Action Rules Mining]], podrobnosti jsou [[lm_guha_di_uvod_resene_prikl#Procedura Ac4ft-Miner a akční pravidla|zde]]. Další typové úlohy poukazují na vybrané směry výzkumu spojené se systémem LISp-Miner a metodou GUHA, podrobnosti jsou [[lm_guha_di_uvod_resene_prikl#Typové úlohy a vybrané směry výzkumu|zde]]. Procedura 4ft-Miner je rozšířením původních GUHA procedury [[https://www.sciencedirect.com/science/article/pii/S0020737381800090|ASSOC a IMPL]]. Při její implementaci vznikly prostředky pro práci s bitovými řetízky a pro rychlý výpočet kontingenčních tabulek. To bylo využito k implementaci dalších GUHA procedur krom již zmíněné procedury Ac4ft-Miner. Typové úlohy jsou k dispozici pro procedury [[lm_guha_di_uvod_resene_prikl#CF-Miner a KL-Miner|CF-Miner a KL-Miner]] pracující s histogramy a kontingenčními tabulkami a pro tři [[lm_guha_di_uvod_resene_prikl#GUHA procedury typu SD|procedury typu SD]] hledající dvě podmnožiny analyzovaných objektů lišící se zadaným způsobem. Krom toho je uvedeno několik dalších [[lm_guha_di_uvod_resene_prikl#Poznámky k prezentovaným příkladům|poznámek k prezentovaným příkladům]]. Prezentované příklady jsou také zdrojem [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_namety_vyzkum|námětů pro další výzkum]]. ===== Procedura 4ft-Miner a algoritmus apriori ===== Procedura [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_4ft_proc|4ft-Miner]] pracuje s GUHA asociačními pravidly, která jsou obecnější než asociační pravidla poskytovaná algoritmem apriori. Pracuje i s podmíněnými pravidly asociačními pravidly. Přesný formální popis je zde. Příklady uvedené dále ukazují možnosti využití * [[lm_guha_di_uvod_resene_prikl#Koeficienty u základních booleovských atributů|koeficientů u základních booleovských atributů]] * [[lm_guha_di_uvod_resene_prikl#Disjunkce základních booleovských atributů|disjunkcí základních booleovských atributů]] * [[lm_guha_di_uvod_resene_prikl#Podmíněná asociační pravidla|podmíněných asociačních pravidel]] * [[lm_guha_di_uvod_resene_prikl#Asociační pravidla - výjimky z histogramů|asociačních pravidel - výjimek z histogramů]] * [[lm_guha_di_uvod_resene_prikl#Zpracování neúplné informace|zpracování neúplné informace]]. Uvedené příklady také demonstrují [[lm_guha_di_uvod_resene_prikl#Rychlost procedury 4ft-Miner|rychlost procedury 4ft-Miner]] v různých situacích. ==== Koeficienty u základních booleovských atributů ==== 4ft-Miner pracuje se [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_zakl_bool|základními booleovskými atributy]] A(α), kde α je vlastní podmnožina množiny hodnot (kategorií) atributu A. Algoritmus apriori pracuje pouze s booleovskými atributy - dvojicemi A(a) kde a je jedna z přípustných hodnot atributu A. Základní booleovské atributy A(α) jsou použity ve většině prezentovaných příkladů aplikace procedury 4ft-Miner, podrobněji je jejich použití vysvětleno v příkladech , ... . Na základě uvedených příkladů lze konstatovat, že použití koeficientů poskytuje možnosti, které lze jen jen těžko nebo prakticky vůbec realizovat pomocí algoritmu apriori. To je zdůrazněno zejména v příkladech .... . Další podrobnosti jsou též v článku [[https://content.iospress.com/articles/intelligent-data-analysis/ida160069|Apriori and GUHA – Comparing two approaches to data mining with association rules]]. ==== Disjunkce základních booleovských atributů ==== Procedura 4ft-Miner pracuje s [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_pravidlo#GUHA asociační pravidlo|GUHA asociačními pravidly]] φ≈ψ kde φ a ψ jsou konjunkce [[https://lispminer.vse.cz/wiki/doku.php?id=lmtask:settings:ftpartialcedent|dílčích cedentů]]. Dílčí cedent je konjunkce nebo disjunkce literálů. Algoritmus apriori nepracuje s disjunkcemi literálů. Možnosti využití disjunkcí literálů ukazují dva příklady dostupné [[lm_guha_di_typul_4ft#Data Traffic Maryland - využití disjunkcí 1|zde]] a [[lm_guha_di_typul_4ft#Data Traffic Maryland - využití disjunkcí 2|zde]]. ==== Podmíněná asociační pravidla ==== Procedura 4ft-Miner pracuje s [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_pravidlo#podminene_asociacni_pravidlo|podmíněnými asociačními pravidly]] φ≈ψ/χ, kde φ≈ψ je asociační pravidlo a χ je booleovský atribut který nazýváme podmínkou //asociačního pravidla//. Vztah mezi podmíněným asociačním pravidlem φ≈ψ/χ a asociačním pravidlem φ∧χ≈ψ podstatně závisí na 4ft-kvantifikátoru ≈, podrobnosti jsou !!!zde!!!!. Příklad uvedený !!!zde!!! ukazuje, že při použití kvantifikátorů lift nelze nahradit podmíněné asociační pravidlo φ≈ψ/χ vhodným pravidlem φ∧χ≈ψ na rozdíl od kvantifikátoru konfidence. ==== Asociační pravidla - výjimky z histogramů ==== Příklady uvedené [[lm_guha_di_typul_4ft#hledani_asociacnich_pravidel_-_vyjimek_z_histogramu|zde]] ukazují, že pomocí procedury 4ft-Miner lze řešit úlohy hledání pravidel φ → A(ai) takových, že konfidence pravidla φ → A(ai) je výrazně jiná, než odpovídá výšce sloupce kategorie ai v histogramu atributu A na celé matici dat nebo na dané podmatici dat. Takové úlohy také nelze snadno řešit pomocí algoritmu apriori. ==== Zpracování neúplné informace ==== Procedura 4ft-Miner nabízí [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_miss_prehled|čtyři přístupy ke zpracování neúplné informace]]. Příklad uvedený [[lm_guha_di_typul_4ft##data_adult_-_chybejici_informace|zde]] porovnává zabezpečený přístup ke zpracování neúplné informace s přístupem používaným v [[https://cran.r-project.org/web/packages/arules/index.html|arules package v systému R]] . Zabezpečený přístup poskytuje pouze taková asociační pravidla, která jsou pravdivá ve všech možných doplněních analyzované matice dat přípustnými hodnotami, což není pravda pro arules package. Další podrobnosti a souvislosti jsou v článku [[https://content.iospress.com/articles/intelligent-data-analysis/ida160069|Apriori and GUHA – Comparing two approaches to data mining with association rules]]. ==== Rychlost procedury 4ft-Miner ==== Procedura 4ft-Miner nevyužívá [[https://dl.acm.org/citation.cfm?id=672836|algoritmus apriori]], ale jiný algoritmus založený na využití [[https://www.sciencedirect.com/science/article/pii/S0020737378800327|reprezentace dat pomocí bitových řetízků]]. Porovnání procedury 4ft-Miner a algoritmu apriori implementovaného v rámci package arules systému R uvedené v již zmíněném článku [[https://content.iospress.com/articles/intelligent-data-analysis/ida160069|Apriori and GUHA – Comparing two approaches to data mining with association rules]] ukazuje, že apriori je často poněkud rychlejší, avšak 4ft-Miner umožňuje efektivní řešení podstatně obecnějších úloh jak dokládají i výše zmíněné příklady. Je také pravda, že rozdíl v rychlosti řešení je většinou zanedbatelný s ohledem na celkovou dobu řešení analytické úlohy a čas k řešení spotřebovaný procedurou 4ft-Miner je uspokojivý vzhledem k řadě prakticky důležitých úloh. Pro získání představy o době řešení různých úloh uvádíme přehled doby řešení úloh v jednotlivých příkladech aplikací procedury 4ft-Miner, je k dispozici zde. Poznamenejme, že doba řešení je ovlivněna velikostí matice dat (lineární závislost), počtem verifikovaných pravidel (jsou využívány různé možnosti vynechání podmnožiny zadaných pravidel, jejich aplikovatelnost však závisí na konfiguraci dat) a počtem nalezených prostých pravidel (zápis prostého pravidla do metabáze vyžaduje jistý čas). ===== Procedura Ac4ft-Miner a akční pravidla ===== Procedura [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_ac4ft_proc|Ac4ft-Miner]] využívá podprogramy pro práci s bitovými řetízky vytvořené pro proceduru 4ft-Miner. To umožňuje práci s koeficienty stejně jako v proceduře 4ft-Miner a také možnost odhadování důsledků navržené akce, viz příklady uvedené [[lm_guha_di_typul_ac4ft|zde]]. Tím se procedura Ac4ft-Miner odlišuje od nástrojů popsaných v knize [[https://www.springer.com/gp/book/9783642356490|Action Rules Mining]]. Podrobnější porovnání procedury Ac4ft-Miner s těmito jednotlivými nástroji není prozatím k dispozici. ===== Typové úlohy a vybrané směry výzkumu ===== Typové úlohy souvisí i s dvěma směry výzkumu souvisejícího s metodou GUHA a systémem LISp-Miner. Úloha [[lm_guha_di_typul_4ft#Data Adult - využití expertních dedukčních pravidel|využití expertních dedukčních pravidel]] souvisí s [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_vyzkum#vyuziti_domenovych_znalosti|využitím doménových znalostí]]. Úloha [[lm_guha_di_typul_4ft#Data Stulong - automatické odfiltrování důsledků doménové znalosti|automatické odfiltrování důsledků doménové znalosti]] souvisí s [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_vyzkum#vyuziti_domenovych_znalosti|využitím doménových znalostí]] i s [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_vyzkum#automatizace_procesu_dobyvani_znalosti|automatizací procesu dobývání znalostí z databází]]. ===== CF-Miner a KL-Miner ===== Procedura [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_cf_proc|CF-Miner]] hledá podmatice dané matice na kterých histogram daného atributu splňuje zadané podmínky, typové úlohy jsou [[lm_guha_di_typul_cf|zde]]. Procedura [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_kl_proc|KL-Miner]] hledá podmatice dané matice, na kterých kontingenční tabulka dvou kategoriálních atributů splňuje zadané podmínky, typové úlohy jsou [[lm_guha_di_typul_kl|zde]]. Obě procedury mají společné typy kvantifikátorů. Jedná se o * kvantifikátory využívající různé statistické a informačně teoretické přístupy * kvantifikátory využívající jednoduché podmínky na frekvence v histogramu nebo v kontingenční tabulce * kvantifikátory definované na základě vzdálenosti histogramů nebo kontingenčních tabulek. Procedura CF-Miner poskytuje navíc kvantifikátory založené na vhodně definovaných schodech v histogramu. ===== GUHA procedury typu SD ===== GUHA procedury typu SD hledají dvě podmatice M/α a M/β dané matice M, které se zadaným způsobem liší ohledně charakteristik některého z relevantních vztahů. Jedná se o tyto procedury: * [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_sd4ft_proc|SD4ft-Miner]], která hledá podmatice M/α a M/β a asociační pravidla φ≈ψ taková, že charakteristiky asociačního pravidla φ≈ψ na podmaticích M/α a M/β se liší zadaným způsobem. Typové úlohy jsou dostupné [[lm_guha_di_typul_sd4ft|zde]]. * [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_sdcf_proc|SDCF-Miner]], která hledá podmatice M/α a M/β a podmíněné histogramy A/χ takové, že histogram A/χ na M/α se zadaným způsobem liší od histogramu A/χ na M/β. Typové úlohy jsou dostupné [[lm_guha_di_typul_sdcf|zde]]. * [[https://lispminer.vse.cz/guhate/doku.php?id=lm_guha_te_sdkl_proc|SDKL-Miner]], která hledá podmatice M/α a M/β a booleovské atributy χ takové, že vztah kategoriálních atributů R a C na podmaticích daných booleovskými atributy M/α∧χ a M/β∧χ se liší zadaným způsobem. Typové úlohy jsou dostupné [[lm_guha_di_typul_sdkl|zde]]. Poznamenejme, že prezentované typové úlohy ukazují pouze malou část typových úloh, které lze těmto procedurami řešit. ===== Poznámky k prezentovaným příkladům ===== Metoda GUHA byla původně vyvíjena jako metoda explorační analýzy dat využívající zejména statistické testy hypotéz. S rozvojem dobývání znalostí z databází kdy jsou často k dispozici všechna data týkající se daného procesu (například všechny návštěvy v daném hotelu, všechny nákupy v daném supermarketu nebo všechny dopravní nehody) stoupl význam různých analýz založených na jednoduchých podmínkách týkajících se frekvencí různých konfigurací v datech. Tomu odpovídají kvantifikátory použité ve většině typových úloh. U těchto kvantifikátorů je důležité, aby uživatel jemuž jsou analýzy určeny (a samozřejmě i analytik) dobře rozuměl významu použitých kvantifikátorů. K tomu slouží i prezentované příklady, je třeba věnovat pozornost slovní interpretaci výsledků. Z tohoto důvodu není při řešení praktických problémů rychlost procedur nejdůležitější. Podstatné je porozumění problematice, formulace analytické otázky a její převod do zadání pro vhodnou analytickou proceduru a následná interpretace výsledků. Je však také pravda, že v prezentovaných příkladech je doba běhu použitých procedur přijatelná, viz zde.