LISp-Miner: systém pro získávání znalostí z dat1 Petr Berka, Jan Rauch, Milan Šimůnek VŠE Praha Nám. W. Churchilla 4, Praha 3 e-mail: {berka,rauch,simunek}@vse.cz Abstrakt. Systém LISp-Miner je otevřený akademický systém pro podporu výzkumu a výuky v oblasti dobývání znalostí z databází. Systém nabízí řadu algoritmů pro hledání zajímavých vztahů v datech (navazuje zde na metodu GUHA) i algoritmus pro tvorbu pravidel rozhodovacích. Článek podává základní charakteristiky jednotlivých algoritmů. LISp-Miner je volně dostupný z http://lispminer.vse.cz
1 Úvod Dobývání znalostí z databází (KDD) lze definovat jako netriviální extrakci implicitních, dříve neznámých a potenciálně užitečných informací z dat (Fayyad a kol, 1996). Jedná se o interaktivní a iterativní proces tvořený kroky selekce, předzpracování, transformace, vlastního „dolování“ (data mining) a interpretace. Technikami dobývání znalostí můžeme řešit řadu různých typů úloh. Podle autorů metodiky CRISP-DM jsou to deskripce dat a sumarizace, segmentace, deskripce konceptů, analýza závislostí, klasifikace a predikce (Chapman a kol, 2000). V prvních čtyřech úlohách hledáme zajímavé znalosti interpretovatelné expertem, v úlohách klasifikace a predikce jde o to získat znalosti použitelné pro automatizovanou podporu rozhodování. Podle typu úlohy a podle charakteru dat můžeme zvolit různé algoritmy pro vlastní „dolování“, a tedy i různé způsoby reprezentování nalezených znalostí: rozhodovací stromy, rozhodovací pravidla, asociační pravidla, neuronové sítě, genetické algoritmy, bayesovské klasifikátory. Náš příspěvek je věnován na znalostem v podobě pravidel, tedy v podobě použitelné pro většinu výše zmíněných úloh dobývání znalostí. Zaměříme se přitom na představení různých typů pravidel a zajímavých vztahů, generovaných systémem LISp-Miner vyvíjeném na VŠE v Praze. 1.1 Asociační a rozhodovací pravidla V oblasti dobývání znalostí se obvykle rozlišují dva typy pravidel: asociační a rozhodovací (klasifikační). V případě asociačních pravidel nás zajímají vzájemné souvislosti mezi hodnotami atributů, v případě rozhodovacích pravidel hledáme znalosti použitelné pro automatizované řešení klasifikačních úloh. Termín asociační pravidla široce zpopularizoval počátkem 90. let Agrawal (Agrawal a kol, 1993) v souvislosti s analýzou nákupního košíku. Při této analýze se zjišťuje, jaké druhy zboží si současně kupují zákazníci v supermarketech (např. pivo a párek). Jde tedy o hledání vzájemných vazeb (asociací) mezi různými položkami sortimentu prodejny. Formálně lze tedy asociační pravidlo vyjádřit jako: 1
Předneseno na semináři Znalostní management pořádaného na VŠM v Bratislavě 10-12.6.2007
předpoklad ⇒ závěr, kde předpoklad (levá strana pravidla, antecedent) i závěr (pravá strana pravidla, sukcedent) jsou kombinace kategorií (hodnot atributů, položek v nákupním košíku). Základními charakteristikami asociačních pravidel v Agrawalově pojetí jsou podpora (support) a spolehlivost (confidence). Tyto charakteristiky jsou počítány ze čtyřpolní kontingenční tabulky, která ukazuje, kolik příkladů v datech splňuje resp. nesplňuje předpoklad nebo závěr (viz tabulka 1). Podpora je pak (absolutní resp. relativní) počet příkladů, splňujících předpoklad i závěr, tedy hodnota a a resp. . a+b+c+d Spolehlivost (též nazývaná platnost, konsistence, nebo správnost) je pak podíl počtu příkladů splňujících předpoklad i závěr a počtu příkladů splňujících předpoklad (tedy vlastně podmíněná pravděpodobnost závěru pokud platí předpoklad):
a . a+b Tabulka 1. Čtyřpolní kontingenční tabulka závěr ¬závěr ∑ předpoklad a b r c d s ¬předpoklad k l n ∑ V algoritmech pro tvorbu asociačních pravidel se opakovaně prolínají dva kroky: generování a testování. Základem je generování kombinací (konjunkcí) hodnot atributů - procházíme (prohledáváme) prostor všech přípustných konjunkcí. Vygenerované pravidlo se pak testuje, zda splňuje uživatelem zadané hodnoty numerických charakteristik (např. podpory a spolehlivosti). Výsledek tohoto testu rozhoduje o dalším generování. Nejznámějším algoritmem je algoritmus apriori. (Agrawal a kol., 1996). Jádrem algoritmu je hledání často se opakujících množin položek (frequent itemsets). Jedná se kombinace (konjunkce) kategorií které dosahují předem zadané četnosti (podpory minsup) v datech. Z kombinací dosahujících požadované četnosti se pak vytvářejí pravidla. Zatímco asociační pravidla hledala zajímavé souvislosti mezi hodnotami různých atributů a jejich kombinací, rozhodovací pravidla se používají pro klasifikaci. Syntaxe pravidla je tedy
předpoklad ⇒ třída
kde předpoklad je kombinace vytvořená z kategorií vstupních atributů a třída je informace o zařazení příkladu do nějaké třídy. Typickým příkladem algoritmu pro tvorbu rozhodovacích pravidel je algoritmus pokrývání množin (Michalski, 1969), či (Clark, Nibblet, 1989). Při pokrývání množin jde o to nalézt pravidla (konzistentní hypotézy), které pokrývají nějaké příklady hledaného konceptu a tyto příklady oddělit od jiných příkladů téhož konceptu i od příkladů třídy jiné. Použití rozhodovacích pravidel pro klasifikaci nových příkladů je velice prosté. Postupně procházíme soubor pravidel až nalezneme pravidlo, které lze použít. Závěr pravidla pak určí třídu, do které máme uvažovaný příklad zařadit.
2 Metoda GUHA Zhruba 30 let před Agrawalem přišla s konceptem asociačních pravidel skupina českých vědců. Základní myšlenkou jejich metody GUHA (General Unary Hypotheses Automaton) bylo nalézt v datech všechny zajímavé souvislosti (hypotézy) a nabídnout je uživateli (Hájek, Havránek, 1978), (Hájek a kol.,1983). V době svého vzniku, kdy se ještě nic netušilo o metodách dobývání znalostí, se GUHA řadila k metodám explorační analýzy dat. Na rozdíl od konfirmační analýzy, kdy cílem bylo ověřit platnost konkrétní statistické hypotézy, při explorační analýze je cílem tyto hypotézy nejen testovat ale i vytvářet. Neboli, jak pravila dobová metafora, zatímco konfirmační analýza se dá přirovnat k chytání ryb na udici, metoda GUHA umožňuje výlov celého rybníka. Postupem času bylo formulováno několik typů hypotéz (pravidel) a s tím souvisejících algoritmů pro jejich generování. Nejblíže k asociačním pravidlům v Agrawalově pojetí měla procedura ASSOC. Metoda GUHA ale nabízela podstatně více typů hypotéz (pravidel): hledají se vztahy mezi kombinacemi hodnot binárních atributů, korelace mezi numerickými atributy podmíněné kombinací kategoriálních atributů, nebo zdroje závislosti v nominálních datech. Metoda GUHA byla v průběhu let implementována v různých podobách. Jedna z posledních implementací je systém LISp-Miner vyvíjený na VŠE v Praze.
3 Systém LISp-Miner Systém LISp-Miner je otevřený akademický systém pro podporu výzkumu a výuky v oblasti dobývání znalostí z databází – viz např. (Rauch, Šimůnek 2003), (Šimůnek 2003). Systém je tvořen modulem pro přípravu a předzpracování dat a sedmi analytickými procedurami: 4FT-Miner, KL-Miner, CF-Miner, SD4FT-Miner, SDKLMiner, SDCF-Miner a KEX. S výjimkou procedury KEX pro tvorbu rozhodovacích pravidel (a tedy pro úlohy klasifikačního typu) jsou všechny ostatní procedury zaměřeny na hledání různých typů pravidel popisujících daná data (v souladu s metodou GUHA nazývaných hypotézy). LISp-Miner jde tedy za rámec „klasických“ asociačních pravidel popsaných v části 1.1. Systém využívá originální techniku bitových řetězců při generování a testování, což výrazně zvyšuje rychlost výpočtu (Rauch, Šimůnek, 2005).
Naše představení jednotlivých procedur budeme ilustrovat na příkladu jednoduché datové tabulky obsahující údaje o žadatelích o úvěr. Část těchto dat můžeme vidět v tabulce 2. Tabulka 2. Ilustrační data klient k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12
příjem vysoký vysoký nízký nízký nízký nízký vysoký vysoký nízký vysoký nízký nízký
Konto vysoké vysoké nízké vysoké vysoké nízké nízké nízké střední střední střední střední
pohlaví žena muž muž žena muž žena muž žena muž žena žena muž
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
Základním stavebním kamenem pro konstrukci hypotéz je takzvaný literál (pozitivní nebo negativní), definovaný jako atribut(koeficient) v případě pozitivního literálu resp. jako ¬atribut(koeficient) v případě negativního literálu. Koeficient (seznam hodnot atributu) pak může být:
• podmnožina omezené délky např. literál město(Praha, Brno) obsahuje podmnožinu délky 2, •
interval omezené délky např. literály věk(nízký, střední), věk(střední), věk(střední, vysoký) obsahují interval délky 1 až 2,
•
řez (interval, obsahující krajní hodnotu) omezené délky např. literály věk(nízký), věk(nízký, střední), věk(nízký, střední, vysoký) obsahují dolní řez délky 1 až 3.
Z literálů jsou pak vytvářeny (generovány metodou „do hloubky“) konjunkce, které tvoří jednotlivé části nějakého pravidla (hypotézy). 3.1 Procedura 4FT-Miner Hypotézy generované a testované procedurou 4FT-Miner mají podobu
φ ≈ ψ / γ, kde φ (antecedent), ψ (sukcedent) a γ, (podmínka) jsou konjunkce literálů a symbol ≈ charakterizuje typ vztahu mezi α a β na podmatici objektů, které splňují podmínku γ. Pokud není podmínka γ definována, analyzuje se celá datová matice.
Vztahy mezi antecedentem a sukcedentem nemusí odpovídat pouze implikacím, tak jak je tomu u asociačních pravidel v Agrawalově pojetí, tedy vztahům, kdy základní charakteristika počítaná ze čtyřpolní tabulky má podobu a . a+b Dalším typem vztahu jsou tzv. dvojité implikace, charakterizované hodnotou
a , a+b+c nebo ekvivalence, charakterizované hodnotou
a+d . a+b+c+d Vztah mezi antecedentem a sukcedentem můžeme hodnotit i na základě chí-kvadrát nebo Fischerova testu (seznam všech typů vztahů je uveden v dodatku). Při generování pravidla se nejprve vytvoří nějaký antecedent, k němu se pak naleznou všechny sukcedenty tak, aby pravidlo vyhovovalo zadaným parametrům. Při vytváření kombinací se postupuje do hloubky, literály jsou přitom uspořádány podle abecedy (podle názvů atributů resp. názvů hodnot). Parametry zadávané uživatelem jsou: • seznam literálů, které se mohou vyskytnout v antecedentu, sukcedentu a podmínce, • maximální délka konjunkce tvořící antecedent, sukcedent a podmínku • typ vztahu a prahové (dolní) hodnoty kritérií pro hledané hypotézy Podívejme se nyní na naše ilustrační data. Zadání parametrů vidíme na obrázku 3, část výpisu nalezených pravidel ukazuje tabulka 3, detail jednoho pravidla (vizualizace příslušné kontingenční tabulky) je pak na obrázku 4. Považujeme za nutné zdůraznit, že pouze tato procedura vychází z klasických prací spojených s metodou GUHA (jde o nejnovější implementaci GUHA procedury ASSOC). Všechny dále uvedené procedury jsou výsledkem práce kolektivu autorů z VŠE (Berka – návrh procedury KEX, Rauch – návrh ostatních procedur, Šimůnek – implementace).
Obrázek 3. Zadání parametrů pro proceduru 4FT-Miner
Obrázek 4. Vizualizace kontingenční tabulky jedné konkrétní hypotézy procedury 4FT-Miner
Tabulka 3. Hypotézy nalezené procedurou 4FT-Miner Konto( nízké) ∧ Nezaměstnaný( ano) ⇒ Pohlaví( žena) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Pohlaví( žena) ∧ Příjem(nízký) ⇒ Úvěr( ne) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Pohlaví( žena) ∧ Příjem(vysoký) ⇒ Úvěr( ano) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Pohlaví( žena) ∧ Úvěr( ano) ⇒ Příjem(vysoký) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Pohlaví( žena) ∧ Úvěr( ne) ⇒ Příjem(nízký) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Příjem(nízký) ⇒ Úvěr( ne) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Příjem(nízký) ⇒ Pohlaví( žena) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Příjem(nízký) ∧ Úvěr( ne) ⇒ Pohlaví( žena) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Příjem(vysoký) ⇒ Úvěr( ano) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Příjem(vysoký) ⇒ Pohlaví( žena) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Příjem(vysoký) ∧ Úvěr( ano) ⇒ Pohlaví( žena) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Úvěr( ano) ⇒ Pohlaví( žena) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Úvěr( ano) ⇒ Příjem(vysoký) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Úvěr( ne) ⇒ Pohlaví( žena) Konto( nízké) ∧ Nezaměstnaný( ano) ∧ Úvěr( ne) ⇒ Příjem(nízký) Konto( nízké) ∧ Nezaměstnaný( ne) ⇒ Pohlaví( muž) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Pohlaví( muž) ∧ Příjem(nízký) ⇒ Úvěr( ne) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Pohlaví( muž) ∧ Příjem(vysoký) ⇒ Úvěr( ano) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Pohlaví( muž) ∧ Úvěr( ano) ⇒ Příjem(vysoký) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Pohlaví( muž) ∧ Úvěr( ne) ⇒ Příjem(nízký) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Příjem(nízký) ⇒ Úvěr( ne) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Příjem(nízký) ⇒ Pohlaví( muž) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Příjem(nízký) ∧ Úvěr( ne) ⇒ Pohlaví( muž) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Příjem(vysoký) ⇒ Úvěr( ano) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Příjem(vysoký) ⇒ Pohlaví( muž) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Příjem(vysoký) ∧ Úvěr( ano) ⇒ Pohlaví( muž) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Úvěr( ano) ⇒ Pohlaví( muž) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Úvěr( ano) ⇒ Příjem(vysoký) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Úvěr( ne) ⇒ Pohlaví( muž) Konto( nízké) ∧ Nezaměstnaný( ne) ∧ Úvěr( ne) ⇒ Příjem(nízký) Konto( nízké) ∧ Pohlaví( muž) ⇒ Nezaměstnaný( ne) Konto( nízké) ∧ Pohlaví( muž) ∧ Příjem(nízký) ⇒ Úvěr( ne) Konto( nízké) ∧ Pohlaví( muž) ∧ Příjem(nízký) ⇒ Nezaměstnaný( ne) Konto( nízké) ∧ Pohlaví( muž) ∧ Příjem(nízký) ∧ Úvěr( ne) ⇒ Nezaměstnaný( ne) Tabulka 3 ukazuje stručnou část výpisu nalezených hypotéz; vidíme jen syntaxi jednotlivých implikací. K úplnému obrázku chybí kvantitativní údaje z příslušných kontingenčních tabulek. K tomu dodejme, že všechna zobrazené implikace mají spolehlivost rovnou 1 – tedy pokud nějaký klient splňuje předpoklad splňuje i závěr. Implikace jsou uvedeny v tom pořadí v jakém byly generovány. Interpretační modul procedury 4FT-Miner ale nabízí řadu dalších možností třídění, vybírání ze seznamu nalezených hypotéz a vizualizace (obrázek 4); interpretační moduly jsou součástí i všech dalších procedur).
3.2 Procedura KL-Miner Hypotézy generované a testované procedurou KL-Miner mají podobu R ~ C / γ. Tato procedura tedy nabízí kontingenční analýzu dvou vícehodnotových kategoriálních atributů. Počítané charakteristiky vzájemného vztahu mezi oběma atributy vychází ze statistických kritérií (např. Chí-kvadrát nebo Kendallův test), nebo z kritérií z oblasti teorie informace (např. entropie nebo vzájemná informace). Zpracovávají se přitom pouze příklady vyhovující podmínce γ. Pokud není podmínka γ definována, analyzuje se celá datová matice. V našem příkladu můžeme analyzovat celkem 20 kontingenčních tabulek, lze tedy získat až 20 KL hypotéz. Vizualizaci jedné z nich vidíme na obrázku 5.
Obrázek 5. Vizualizace kontingenční tabulky jedné konkrétní hypotézy procedury KL-Miner
3.3 Procedura CF-Miner Hypotézy generované a testované procedurou CF-Miner mají podobu ~C / γ Analyzuje se zde tedy histogram frekvencí kategorií atributu C u příkladů splňujících podmínku γ. Cílem procedury je hledání okolností, za kterých jsou zajímavým způsobem rozloženy frekvence jednotlivých kategorií některého kategoriálního atributu. Zajímavost je zde chápána jako to, že frekvence splňují požadavek definovaný vztahem ~ . Příkladem vztahu ~ může být požadavek, aby všechny kategorie dosahovaly alespoň zadané četnosti a, či aby rozptyl hodnot byl menší než zadaná hodnota.
Obrázek 6. Vizualizace kontingenční tabulky jedné konkrétní hypotézy procedury CF-Miner
3.4 Procedura SD4FT-Miner Procedura SD4FT-Miner je jednou ze tří tzv. „set differs from set“ procedur. Tyto procedury hledají hypotézy, jejichž numerické charakteristiky se liší na dvou podmnožinách analyzovaných dat. Hypotézy generované a testované procedurou SD4FT-Miner mají podobu φ ≈ ψ / (α, β, γ) Hledáme tedy situace, kdy při splněné podmínce γ je vzájemný 4ft-vztah mezi φ a ψ na množině α je jiný než na množině β. Tedy např. hledáme situace, kdy spolehlivost implikace φ ⇒ ψ na množině příkladů splňujících α je jiná než spolehlivost implikace φ ⇒ ψ na množině příkladů splňujících β: a1 a2 − ≥ 0 .2 a1 + b1 a 2 + b2
Příklad takovéto situace vidíme na obrázku 7. Ve skupině nezaměstnaných je spolehlivost implikace konto(střední) ⇒ příjem(nízký) rovna 1 zatímco ve skupině zaměstnaných je spolehlivost této implikace rovna 0.5.
Obrázek 7. Vizualizace kontingenční tabulky jedné konkrétní hypotézy procedury SD4FT-Miner
3.5 Procedura SDKL-Miner Hypotézy generované a testované procedurou SDKL-Miner mají podobu R ~ C / (α, β, γ) Hledáme tedy dvojice podmnožin definovaných booleovskými atributy α, β, podmínku definovanou booleovským atributem γ a kategoriální atributy R, C tak, že za podmínky γ se podmnožiny α, β liší vzhledem k vzájemnému vztahu atributů R a C. Podmínka γ nemusí být zadána, pak se výpočet provádí pro celou datovou matici. V našich datech můžeme například zjistit, že vztah mezi výší konta a výší příjmu u nezaměstnaných je jiný než vztah mezi výší konta a výší příjmu u zaměstnaných (obrázek 8).
Obrázek 8. Vizualizace kontingenční tabulky jedné konkrétní hypotézy procedury SDKL-Miner
3.6 Procedura SDCF-Miner Hypotézy generované a testované procedurou SDCF-Miner mají podobu
~C / (α, β, γ). Hledáme dvojice podmnožin definovaných booleovskými atributy α, β, podmínku definovanou booleovským atributem γ a kategoriální atribut C tak, že za podmínky γ se podmnožiny α, β liší vzhledem k frekvencím jednotlivých kategorií atributu C. Podmínka γ nemusí být zadána, pak se výpočet provádí pro celou datovou matici. Obrázek 9 ukazuje, že rozdělení četností hodnot atributu příjem je různé pro skupinu nezaměstnaných a skupinu zaměstnaných.
Obrázek 9. Vizualizace kontingenční tabulky jedné konkrétní hypotézy procedury SDCF-Miner
3.7 Procedura KEX Z pojetí metody GUHA se vymyká procedura KEX. Tato procedura slouží pro hledání klasifikačních pravidel, tedy pravidel, která je možno přímo použít v procesu automatizovaného rozhodování (Berka, Ivánek, 1994). Při specifikaci tohoto procesu musíme rozhodnout o:
•
podobě báze znalostí,
•
podobě inferenčního mechanismu,
•
způsobu, jak v souboru vztahů nalézt znalosti.
Báze znalostí je vytvářena v podobě souboru pravidel tvořených vztahy implikace k zadané cílové kombinaci. Vztahy jsou opatřeny váhou která vyjadřuje neurčitost ve znalostech. Pravidla v bázi znalostí tedy mají podobu
předpoklad ⇒ třída (w), kde
předpoklad je kombinace kategorií vstupních atributů, třída je kombinace definující pozitivní příklady, w z intervalu [0,1] je váha vyjadřující neurčitost pravidla.
Inferenční mechanismus budovaného systému pracuje metodou přímého řetězení. V průběhu konzultace se pro nový objekt popsaný hodnotami vstupních atributů (popis objektu nemusí být úplný!) naleznou všechna aplikovatelná pravidla. Příspěvky těchto pravidel se složí pomocí kombinační funkce ⊕ a tak se naleznou výsledné váhy všech cílů. Jako kombinační funkce se používá pseudobayesovské skládání vah známé z expertního systému PROSPECTOR (Duda, Gasching, 1979). Jsou-li w1, w2 váhy dvou pravidel, spočítá se jejich kombinace jako: w1 × w2 . w1 ⊕ w2 = w1 × w2 + (1 − w1 ) × (1 − w2 ) Při tvorbě báze pravidel se vlastně provádí postupné zpřesňování a zjemňování již existujících znalostí (knowledge refinement). Bázi pravidel vytváříme „shora dolů“ postupným přidáváním nových (speciálnějších) pravidel ve chvíli, kdy báze přestane být konsistentní s trénovacími daty reprezentovanými souborem všech implikací k zadanému cíli. Na počátku obsahuje báze pravidel tzv. prázdný vztah, který odpovídá rozdělení tříd v trénovacích datech. Do báze pravidel se pak postupně zařazují jen ty implikace, které nejsou odvoditelné z již získaných kratších pravidel. Obrázek 10 ukazuje bázi pravidel získaných z našich ukázkových dat
Obrázek 10. Klasifikační pravidla nalezená procedurou KEX
Při klasifikaci nového příkladu použijeme všechna aplikovatelná pravidla a pomocí funkce ⊕ poskládáme jejich váhy. Příklad zařadíme ke třídě, pro kterou odvodíme nejvyšší váhu. 3.8 Struktura a implementace systému Struktura systému LISp-Miner je naznačena na obrázku 11. Systém je tvořen řadou samostatných modulů (exe souborů), které pracují nad analyzovanými daty a nad metadaty. Analyzovaná data jsou uložena v databázi MS Access. Koncept metadat, rovněž realizovaný jako databáze MS Access, umožňuje uchovávat zadání i výsledky jednotlivých analýz. LISp-Miner je tedy z implementačního pohledu zasazen do prostředí MS Windows. Z pohledu metodiky CRISP-DM, standardní metodiky pro řešení úloh dobývání znalostí z databází (viz obrázek 12), systém LISp-Miner podporuje kroky porozumění datům, přípravy dat, modelování a evaluace. Systém je volně dostupný na http://lispminer.vse.cz. pParams (ODBC DSN)
ANALYZED DATA
META BASE
LM Admin Administration
Read-Only
Data Exploration & Preparation modules
Obrázek 11. Schéma systému LISp-Miner
Obrázek 12. Metodika CRISP-DM
Data Processing modules
Interpretation modules
4 Poděkování Systém LISp-Miner je vyvíjen s podporou grantů MSMT č. MSM138439910, GAČR č. 201/05/0325. Na návrhu procedur, jejich implementaci či testování se kromě autorů příspěvku podílela řada studentů a doktorandů VŠE, za všechny zmiňme V. Lína, M. Kejkulu a P. Dolejšího.
5 Závěr Příklady popisované v příspěvku jsou výhradně ilustrační. Z rozsáhlejších (a serióznějších) aplikací systému LISp-Miner můžeme zmínit analýzu dat o rizikových faktorech aterosklerózy u mužů středního věku prováděnou v rámci výzkumného centra EuroMISE (Lín a kol. 2004), analýzu dat o příčinách dopravních nehod ve Velké Británii prováděnou v rámci evropského výzkumného projektu Sol-Eu-Net (Flach a kol., 2003), analýzu dat o názorech obyvatel Prahy na kvalitu života v hlavním městě (Svátek, Rauch, Ralbovský, 2006) nebo analýzu popisů událostí vztahujících se k fotbalovým utkáním (v rámci evropského výzkumného projektu K-Space). Již tento neúplný výčet ukazuje, že LISp-Miner je vhodným nástrojem všude tam, kde hledáme zajímavé souvislosti mezi hodnotami atributů v datech z různých oblastí.
Literatura Agrawal, R., Imielinski, T., Swami,A.: Mining associations between sets of items in massive databases. In: Proc. of the ACM-SIGMOD 1993 Int Conference on Management of Data, Washington D.C., May 1993, 207-216. Agrawal, R., a kol.: Fast discovery of association rules. In: (Fayyad, Piatetsky-Shapiro, Smyth, Uthurusamy, eds.) Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996 Berka, P.: Dobývání znalostí z databází. Academia Praha, 2003 Berka, P., Ivánek, J.: Automated knowledge acquisition for PROSPECTOR-like expert systems. In. (Bergadano, de Raedt eds.) Proc. ECML'94, Springer 1994, 339-342. Clark, P., Niblett, T.: The CN2 induction algorithm. Machine Learning, 3 (1989), 261283. Duda, R.O., Gasching, J.E.: Model design in the Prospector consultant system for mineral exploration. In: Michie, D. (ed.), Expert Systems in the Micro Electronic Age, Edinburgh University Press, UK, 1979. Fayyad,U. a kol.. eds.: Advances in Knowledge Discovery and Data Mining. AAAI Press/MIT Press, 1996 Hájek, P., Havránek, T.: Mechanising Hypothesis Formation – Mathematical Foundations for a General Theory. Springer, 1978. Flach, P. a kol.: On the Road to Knowledge. In: Mladenič, a kol. (ed.). Data mining and Decision Support. Integration and Collaboration. Boston : Kluwer Academic Publishers, 2003, 143–155. Hájek, P., Havránek, T., Chytil, M.K.: Metoda GUHA. Automatická tvorba hypotéz. Academia, 1983.
Chapman, P. a kol.: CRISP-DM 1.0 Step-by-step data mining guide. SPSS Inc. 2000. Lín, V., a kol.: The KL-Miner Procedure for Datamining. Neural Network World , 2004, č. 5, 411–420. Michalski, R.S.: On the Quasi-minimal solution of the general covering problem. In: Proc. 5th Int. Symposium on Information Processing FCIP’69, Bled, Yugoslavia, 1969, 125-128. Rauch, J., Šimůnek, M.: System LISp-Miner. In: Svátek,V. (ed.). Znalosti 2003. Ostrava: TU Ostrava, 2003, 83–92. Rauch, J., Šimůnek, M.: GUHA Method and Granular Computing. In: Hu, a kol. (ed.). IEEE Int. Conf. On Granular Computing 2005. 2005, 630–635. Svátek, V., Rauch, J., Ralbovský, M.: Ontology-Enhanced Association Mining. In: Ackermann, M., a kol. (eds): Semantics, Web and Mining. Berlin Springer, 2006, 163– 179 Šimůnek, M.: Academic KDD Project LISp-Miner. In: Abraham,A., Franke,K., Koppen, K. (eds.). Advances in Soft Computing – Intelligent Systems Desing and Applications. Heidelberg: Springer-Verlag, 2003, 263–272
Dodatek: seznam kvantifikátorů procedury 4FT-Miner Název
parametry
Základní (fundovaná) implikace
0
Dolní kritická implikace
0
Horní kritická implikace
Base > 0
podmínka platnosti a a + b ≥ p ∧ a ≥ Base a+b
Base > 0
∑
0
a
0<α<1
0<α<1 Base > 0
Základní 0
0 dvojitá implikace Dolní kritická 0 0 Horní kritická 0 0 Základní (fundovaná) ekvivalence
0 0
Dolní kritická ekvivalence
0 0
Horní kritická ekvivalence
0 0
(a + b)! i a+b-i ≤ α ∧ a ≥ Base i!(a + b - i)! p (1 - p)
i=a
∑
(a + b)! i a+b-i > α ∧ a ≥ Base i!(a + b - i)! p (1 - p)
i=0 a a + b + c ≥ p ∧ a ≥ Base a+b+c
∑ i!(a + b + c - i)! p (1 - p) (a + b + c)!
i
a+b+c-i
≤ α ∧ a ≥ Base
i=a a
∑
(a + b + c)! i a+b+c-i > α ∧ a ≥ Base i!(a + b + c - i)! p (1 - p)
i=0 a+d a + b + c + d ≥ p ∧ a ≥ Base a+b+c+d (a + b + c + d)! i a+b+c+d-i ≤ α i!(a + b + + d - i)! p (1 - p) i=a a ≥ Base
∑
∧
a
∑ i!(a(a ++ bb ++ cc +d+ d)!- i)! p (1 - p) i
a+b+c+d-i
> α
∧
i=0 a ≥ Base E-kvantifikátor
0<δ<1
b c a+b>0 ∧ a+b<δ ∧ c+d>0 ∧ c+d<δ
název
parametry
podmínka platnosti
Prosté vychýlení
δ>0 Base > 0
ab > eδcd ∧ a ≥ Base
Fisherův kvantifikátor
0 < α ≤ 0.5 min(r,k) Base > 0
r!s!k!l! ≤α ∑ n!i!(r-i)!(k-i)!(n-r-k-i)!
∧ a ≥ Base
i=a
Chi-kvadrát kvantifikátor
0 < α ≤ 0.5 Base > 0
podpora
0<σ≤1
above average
-1 < p
below average
-1 < p
ad > bc ∧
n(ad - bc) klrs > α ∧ a ≥ Base
a a+b+c+d ≥σ a(a + b + c + d) a + b > 0 ∧ a + c > 0 ∧ (a + b) (a + c) ≥ (1-p) a(a + b + c + d) a + b > 0 ∧ a + c > 0 ∧ (a + b) (a + c) < (1-p)
