Metoda GUHA a systém LISp-Miner

Pro asociační pravidla a proceduru 4ft-Miner jsou k dispozici tato témata:

• základní informace
• příklady typických aplikací
• typové úlohy pro hledání výjimek a odlišností
• neúplná informace
• dedukce a prostota
• práce s doménovou znalostí a automatizace.
• porovnání procedury 4ft-Miner a arules package v R

Procedura 4ft-Miner pracuje s GUHA asociačními pravidly φ≈ψ a s podmíněnými GUHA asociačními pravidly φ≈ψ/χ. Zde φ, ψ a χ jsou booleovské atributy, ≈ je 4ft-kvantifikátor. Booleovský atribut φ se nazývá antecedent, ψ je sukcedent (konsequent) a χ je podmínka. Podrobnosti jsou uvedeny zde.

Je uvedeno několik typických příkladů aplikací procedury 4ft-Miner, které lze opakovat na vlastních datech bez podrobného studia náležitostí zadání.

1. Vysoká konfidence. Příklady jsou uvedeny zde, zde, a zde. K tomuto typu úloh je k dispozici i obecný postup pro řešení.
2. Vysoká konfidence - podmíněná pravidla. Příklad je uveden zde
3. Vysoký lift. Příklad je uveden zde.
4. Využití disjunkcí. Příklady jsou uvedeny zde a zde.
5. Výjimky z histogramu. Příklady jsou uvedeny zde a zde.

Pro proceduru 4ft-Miner jsou popsány následující typové úlohy na hledání výjimek a odlišností:

1. asociační pravidlo - výjimka z histogramu
2. výrazná změna hodnoty liftu prodloužením antecedentu.

Zpracování neúplné informace je jeden z důležitých problémů data mining. V souvislosti s metodou GUHA je tento problém řešen od sedmdesátých let minulého století, podrobnosti jsou zde. Důležitý je zabezpečený přístup k neúplné informaci který zaručuje, že když je vztah podle tohoto přístupu platný v dané matici dat s neúplnou informací, tak je tento vztah platný v každé matici dat která vznikne doplněním neúplné informace v analyzované matici.

Přístupy vyvinuté v souvislosti s metodou GUHA jsou implementovány v proceduře 4ft-Miner spolu s přístupem používaným v package arules systému R.

Porovnání zabezpečeného přístupu k neúplné informaci a přístupu používaného v arules je v článku Apriori and GUHA – Comparing two approaches to data mining with association rules, viz také příklad uvedený zde. Ukazuje se, že přístup dle arules vede ke zvýšení obvykle již dost vysokého počtu vystupujících pravidel. Pravidla, která jsou navíc však nemusí být ve skutečnosti pravdivá.

GUHA asociační pravidla jsou podstatně obecnější než „klasická“ asociační pravidla produkovaná algoritmem apriori. Důsledkem je možnost využití dedukčních pravidel, důležité příklady dedukčních pravidel jsou zde.

Korektní dedukční pravidla jsou používána pro optimalizaci běhu i výstupu procedury 4ft-Miner. Je možno zvolit, že do výstupu procedury budou zařazena pouze prostá pravidla, tedy taková, která neplynou z jiných, ve výstupu již uvedených a jednodušších pravidel.

Podrobnosti zadávání výstupu pouze prostých pravidel jsou zde.

S procedurou 4ft-Miner je spojen i výzkum možností práce s doménovou znalostí a s její automatizací. Ukázky jsou uvedeny zde a v článku Expert deduction rules in data mining with association rules: a case study.

Procedura 4ft-Miner pracuje s GUHA asociačními pravidly která jsou obecnější než asociační pravidla poskytovaná algoritmem apriori. S GUHA asociačními pravidly je spojena teorie observačních kalkulů. Procedura 4ft-Miner je implementována s využitím bitových řetízků pomocí jiného algoritmu než apriori, viz například tento článek. To vede k širším možnostem a také k jiným vlastnostem procedury 4ft-Miner ve srovnání s algoritmem apriori.

Populární implementací algoritmu apriori je arules package v systému R. Porovnání procedury 4ft-Miner a arules package na datech Adult je k dispozici zde. Podrobnější informace jsou v článku Apriori and GUHA – Comparing two approaches to data mining with association rules. Hlavní závěry uvedené v článku jsou:

• 4ft-Miner je pomalejší než arules. To je způsobeno mimo jiné tím, že 4ft-Miner udržuje informace potřebné pro různé způsoby práce s neúplnou informací, které nabízí. Doba běhu procedury 4ft-Miner je však stále přijatelná a je pouhým zlomkem celkové doby potřebné k řešení úloh data mining.
• Obě procedury obvykle produkují mnoho pravidel, které je třeba dále interpretovat. Tento počet je u arules v případě dat s neúplnou informací ještě dále zvyšován produkcí pravidel, která mohou být nepravdivá při doplnění chybějících hodnot skutečnými hodnotami. Příklad je uveden zde.
• Různé typy koeficientů umožňují řešit procedurou 4ft-Miner úlohy, které prakticky nelze řešit pomocí procedury arules. Příklady jsou uvedeny zde
• Procedura 4ft-Miner pracuje i s podmíněnými asociačními pravidly což umožňuje řešit úlohy, které nejde přímo řešit pomocí procedury arules.
• Procedura arules vyžaduje zadání minimálních hodnot konfidence a podpory. To může vést ke ztrátě pravidel s vysokým liftem. Tento problém lze obejít zadáním velmi nízkého prahu pro podporu, což však může vést ke značnému nárůstu vystupujících pravidel. Tento problém se netýká procedury 4ft-Miner.