Dolování dat Asociační pravidla Jan Górecki Název prezentace Název projektu Rozvoj vzdělávání na Slezské univerzitě v Opavě Registrační číslo projektu CZ.02.2.69/0.0./0.0/16_015/0002400 Logolink_OP_VVV_hor_barva_cz Obsah přednášky •Co jsou Asociační pravidla •Základní charakteristiky pravidel •Hledání asociačních pravidel •Generování kombinací •Algoritmus apriori mineiro2.jpg •Úloha hledání souvislostí mezi hodnotami atributů. •Analýza nákupního košíku (Agrawal, 1993) • •párky & hořčice Þ rohlíky •obecněji •Ant Þ Suc, •kde Ant (antecedent) i Suc (sukcedent) jsou konjunkce hodnot KATEGORIÁLNÍCH atributů (kategorií) • Asociační pravidla csvukrs Základní charakteristiky pravidel Suc ØSuc å Ant a b r ØAnt c d s å k l n kontingenční tabulka Ant Þ Suc párky & hořčice Þ rohlíky podpora – relativní četnost kombinace Ant  Suc v datech spolehlivost – podmíněná pravděpodobnost závěru pravidla pokud platí jeho předpoklad Hledání asociačních pravidel 1)generování syntakticky korektního pravidla (někdy nutná binarizace) 2)testování vygenerovaného pravidla Generování = prohledávání prostoru pravidel, neboli generování všech přípustných konjunkcí atributů (atribut se nesmí opakovat!) ·Shora dolů ·Slepé i heuristické T6-asociace_jako_prohledavani Testování = zjišťování (na datech), zda pravidlo splňuje zadané požadavky na hodnoty numerických charakteristik Konto Konto(vysoké) Konto(střední) Konto(nízké) Vysoké 1 0 0 Střední 0 1 0 Nízké 0 0 1 Střední 0 1 0 Generování kombinací ·do šířky ·do hloubky ·heuristicky kombinace 1n 1v 2n 2s 2v 3m 3z 4a 4n 5a 5n 1n 2n 1n 2s 1n 2v 1n 3m 1n 3z 1n 4a 1n 4n 1n 5a 1n 5n 1v 2n 1v 2s 1v 2v 1v 3m 1v 3z 1v 2v 3z 4n 5a kombinace 1n 1n 2n 1n 2n 3m 1n 2n 3m 4a 1n 2n 3m 4a 5a 1n 2n 3m 4a 5n 1n 2n 3m 4n 1n 2n 3m 4n 5a 1n 2n 3m 4n 5n 1n 2n 3m 5a 1n 2n 3m 5n 1n 2n 3z 1n 2n 3z 4a 1n 2n 3z 4a 5a 1n 2n 3z 4a 5n 1n 2n 3z 4n 1n 2n 3z 4n 5a 1n 2n 3z 4n 5n 1n 2n 3z 5a 1n 2n 3z 5n 1n 2n 4a 1n 2n 4a 5a 1n 2n 4a 5n 1n 2n 4n 5n 5n Frq kombinace 8 5a 7 1n 6 3m 6 3z 6 4a 6 4n 5 1v 5 1n 4a 5 4n 5a 5 1v 5a 4 2v 4 2s 4 2n 4 5n 4 3m 5a 4 1n 3m 4 3z 5a 4 3z 4a 4 3m 4n 4 1v 4n 4 2v 5a 4 1n 5n 4 1v 4n 5a 3 1n 5a 3 1n 3z 1 1v 2s 3z 4n 5a Do šířky Do hloubky Heuristicky Kurzívou je prázdná kombinace Algoritmus apriori – 1. krok 1.do L1 přiřaď všechny hodnoty atributů, které dosahují alespoň požadované četnosti 2.polož k=2 3.dokud Lk-1 je neprázdná: a)pomocí funkce apriori-gen vygeneruj na základě Lk-1 množinu kandidátů Ck b)do Lk zařaď ty kombinace z Ck, které dosáhly alespoň požadovanou četnost c)proveď k := k + 1 Funkce apriori-gen(Lk-1) 1)pro všechny dvojice kombinací p, q z Lk-1: Pokud p a q se shodují v k-2 kategoriích přidej sjednocení p ∧ q do Ck 2)pro každou kombinaci c z Ck: Pokud některá z jejich podkombinací délky k-1 není obsažena v Lk-1 odstraň c z Ck A1A2A3 – nutnost minimální podpory všech podkombinací: A1 A2 první čtyři řádky, A1 A3 další čtyři řádky – může se stát, že A2 A3 můžou mít podporu 0! Značení: n(Comb) – počet objektů v datech splňujících kombinaci Comb, např. n(1n4a) = 5 Algoritmus apriori – 2. krok •Každá kombinace Comb se rozdělí na všechny možné dvojice podkombinací Ant a Suc takové, že Suc = Comb - Ant. •Hledají se pravidla Ant Þ Suc tak, že se postupně přesouvají kategorie z Ant do Suc Platí totiž, že: je-li Ant‘ podkombinací Ant, potom conf(Ant’ Þ Comb-Ant’) £ conf(Ant Þ Comb-Ant) Např. když Comb = A1A2A3 a Ant´ = A1, Ant = A1A2, pak: je-li conf(A1A2 => A3) < minconf, pak conf(A1 => A2A3) < minconf , tedy pro A1 => A2A3 není třeba ověřovat minimální spolehlivost, protože víme, že ji splňovat nemůže Algoritmus apriori – příklad Pro data o klientech banky, minsup = 4 (min absolutní podpora) a minconf = 0.8 Značení: n(Comb) – počet objektů v datech splňujících kombinaci Comb, např. n(1n4a) = 5 Algoritmus apriori – příklad (2. krok bez zkratek) Rule (Support, Confidence) uver_ne -> prijem_nizky (33.3333%, 100%) prijem_vysoky -> uver_ano (41.6667%, 100%) konto_vysoke -> uver_ano (33.3333%, 100%) prijem_vysoky & nezamestnany_ne -> uver_ano (33.3333%, 100%) nezamestnany_ano -> prijem_nizky (41.6667%, 83.3333%) nezamestnany_ne -> uver_ano (41.6667%, 83.3333%) prijem_vysoky -> nezamestnany_ne (33.3333%, 80%) prijem_vysoky -> nezamestnany_ne & uver_ano (33.3333%, 80%) prijem_vysoky & uver_ano -> nezamestnany_ne (33.3333%, 80%) nezamestnany_ne & uver_ano -> prijem_vysoky (33.3333%, 80%) Interpretace výsledků •Je potřeba spolupracovat s experty, jinak hrozí mylná interpretace získaných pravidel •Např. pleny & mléko => pivo (spolehlivost = 80%) Shrnutí •Hledání asociačních pravidel je metoda učení bez učitele – nevolí se žádný cílový atribut •První krok algoritmu apriori je založen na faktu, že: mám-li kombinaci Comb délky k, tak pokud její jakákoli podkombinace délky k-1 nesplňuje minimální podporu, tak ani Comb nemůže splňovat minimální podporu => výrazné zrychlení prohledávání prostoru kombinací •Druhý krok algoritmu apriori je založen na faktu, že: je-li Ant’ podkombinací Ant, potom conf(Ant’ Þ Comb-Ant’) £ conf(Ant Þ Comb-Ant) => výrazné zrychlení generování pravidel splňujících minimální podporu Děkuji za pozornost Některé snímky převzaty od: prof. Ing. Petr Berka, CSc. berka@vse.cz