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ů ve tvaru pravidel.
•
•
•
•
•
•Úloha typu učení bez učitele
•Cílem je nalézt všechna pravidla podpořená daty, která splňují předem stanovená kritéria
•Kritéria ovlivňují množství a vlastnosti nalezených pravidel
•Analýza nákupního košíku (Agrawal, 1993)
•
Asociační pravidla
Ant  Þ  Suc,
kde Ant (antecedent) i Suc (sukcedent) jsou konjunkce hodnot KATEGORIÁLNÍCH atributů (kategorií)
párky & hořčice Þ rohlíky

csvukrs

Základní charakteristiky pravidel

Suc
ØSuc
Ant
a
b
ØAnt
c
d
Ant  Þ  Suc
párky & hořčice Þ rohlíky
Jak najít všechna pravidla s danou podporou a spolehlivostí?
Kolik kombinací je možno generovat z těchto dat?

podpora – odhad pravděpodobnosti výskytu kombinace Ant  Suc
spolehlivost – odhad podmíněné pravděpodobnosti výskytu Suc pokud platí Ant

Hledání asociačních pravidel
1)Generování syntakticky korektního pravidla
= prohledávání prostoru pravidel, neboli generování všech přípustných konjunkcí atributů (atribut
se nesmí opakovat!)
a)Do šířky, do hloubky
b)Heuristické
(někdy nutná binarizace)
2)Testování vygenerovaného pravidla = zjišťování (na datech), zda pravidlo splňuje zadané požadavky
na hodnoty numerických charakteristik
3)
T6-asociace_jako_prohledavani
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
2n
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
Lidl.cz: „Stálý sortiment zahrnuje přibližně 2 400 druhů výrobků.“ Tesco: 14 000 online

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í apriori-gen(Lk-1) vygeneruj 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
Geniální myšlenka:
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ýsledek kombinace p a q má pak délku k
Kurzívou jsou vyznačeny kroky, kde je potřeba sahat na původní data (pomalé)

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 – příklad
Pro data o klientech banky: n = 12
Minimální podpora: minsup = 1/3 (4 z 12)
Minimální spolehlivost: minconf = 0.8
1         2       3             4            5

Značení: n(Comb) – počet objektů v datech splňujících kombinaci Comb, např. n(1n4a) = 5

Algoritmus apriori – 2. krok (do hry přichází spolehlivost)
•
•
•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
•
•
•
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
Využívají se četnosti kombinací (a a a+b) spočtené v kroku 1! (na data se již nesahá)
Je-li Ant’ podkombinací Ant (tedy Ant’ je kratší než Ant), potom
conf(Ant’ Þ Comb-Ant’) £ conf(Ant Þ Comb-Ant)
tedy, odebíráním kategorií z předpokladu pravidla snižujeme (přesněji nemůžeme zvýšit) jeho
spolehlivost!

Algoritmus apriori – příklad
Pro data o klientech banky: n = 12
Minimální podpora: minsup = 1/3 (4 z 12)
Minimální spolehlivost: 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
•Aplikace metody zahrnuje např. analýzu nákupního košíku (supermarkety, e-shopy, atd.).

Děkuji za pozornost
Některé snímky převzaty od:
prof. Ing. Petr Berka, CSc. berka@vse.cz