Uživatelské nástroje

Nástroje pro tento web


Postranní lišta

Úvod


Data Hotel

Další data


Typové úlohy




Všechny řešené příklady


Řešené příklady s detaily na wiki

Histogramy na wiki

Asociační pravidla na wiki

Kontingenční tabulky na wiki

Dvojice asociačních pravidel


lm_guha_di_zaloha

ZALOHA Typové úlohy

Cílem příkladů je naznačit možnosti systému LISp-Miner. Tento systém je v současné době pravděpodobně nejrozsáhlejší implementace původní české metody GUHA explorační analýzy dat. Tato metoda je, v souladu s článkem 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 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 algoritmem apriori, podrobnosti jsou 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 Action Rules Mining, podrobnosti jsou zde.

Další typové úlohy poukazují na vybrané směry výzkumu spojené se systémem LISp-Miner a metodou GUHA, podrobnosti jsou zde.

Procedura 4ft-Miner je rozšířením původních GUHA procedury 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 CF-Miner a KL-Miner pracující s histogramy a kontingenčními tabulkami a pro tři 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 poznámek k prezentovaným příkladům.

Prezentované příklady jsou také zdrojem námětů pro další výzkum.

Procedura 4ft-Miner a algoritmus apriori

Procedura 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í

Uvedené příklady také demonstrují rychlost procedury 4ft-Miner v různých situacích.

Koeficienty u základních booleovských atributů

4ft-Miner pracuje se 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 Apriori and GUHA – Comparing two approaches to data mining with association rules.

Disjunkce základních booleovských atributů

Procedura 4ft-Miner pracuje s GUHA asociačními pravidly φ≈ψ kde φ a ψ jsou konjunkce 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é zde a zde.

Podmíněná asociační pravidla

Procedura 4ft-Miner pracuje s 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é 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í čtyři přístupy ke zpracování neúplné informace. Příklad uvedený zde porovnává zabezpečený přístup ke zpracování neúplné informace s přístupem používaným v 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 Apriori and GUHA – Comparing two approaches to data mining with association rules.

Rychlost procedury 4ft-Miner

Procedura 4ft-Miner nevyužívá algoritmus apriori, ale jiný algoritmus založený na využití 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 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 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é zde. Tím se procedura Ac4ft-Miner odlišuje od nástrojů popsaných v knize 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 využití expertních dedukčních pravidel souvisí s využitím doménových znalostí.

Úloha automatické odfiltrování důsledků doménové znalosti souvisí s využitím doménových znalostí i s automatizací procesu dobývání znalostí z databází.

CF-Miner a KL-Miner

Procedura CF-Miner hledá podmatice dané matice na kterých histogram daného atributu splňuje zadané podmínky, typové úlohy jsou zde.

Procedura 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 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:

  • 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é zde.
  • 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é zde.
  • 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é 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.

lm_guha_di_zaloha.txt · Poslední úprava: 2019/10/28 09:16 (upraveno mimo DokuWiki)