Základy vytěžování dat

Základy vytěžování dat předmět A7Bb36vyd – Vytěžování dat Filip Železný, Miroslav Čepek, Radomír Černoch, Jan Hrdlička katedra kybernetiky a katedra počítačů ČVUT v Praze, FEL

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Časté množiny

Odkaz na výukové materiály: https://cw.felk.cvut.cz/doku.php/courses/a7b36vyd/moduly/start (oddíl 4)


Vytěžování dat, přednáška 6: Vyhledávání častých množin Filip Železný


Fakulta elektrotechnická, ČVUT

1 / 16

Časté množiny

Asociace

I

Pokračujeme v metodách vytěžování bez učitele I

tedy modelování rozdělení PX , z něhož jsou generována data

I

Připomínka: X = X1 × X2 × . . . × Xn , kde Xi je množina hodnot příznaku i

I

Úloha: najít hodnoty nějaké podmnožiny příznaků, které se často objevují společně tj. jsou asociovány

I

Příklad: X = příjem × bydliště × pohlaví × úvěr

I

Častá asociace např. příjem = vysoký & bydliště = Praha

I

“častá” znamená, že pravděpodobnost Ppříjem,bydliště (vysoký, Praha) je vysoká

2 / 16

Časté množiny

Podpora asociace Podpora: podíl instancí, v nichž asociace platí, mezi všemi instancemi příjem vysoký vysoký nízký vysoký střední I

bydliště Praha Plzeň Praha Praha Brno

pohlaví M M M Ž M

úvěr splácí splácí nesplácí splácí splácí

Asociace A = příjem = vysoký & bydliště = Praha má podporu 2/5 = 0.4. Zapisujeme podp(A) = 0.4 I

podp(A) je odhadem Ppříjem,bydliště (vysoký, Praha) 3 / 16

Časté množiny

Podpora asociace Všechny asociace s podporou alespoň 0.4 příjem vysoký vysoký nízký vysoký střední


příjem vysoký vysoký nízký vysoký střední


příjem

bydliště

4 / 16

Časté množiny

1. “true” (prázdná asociace)

Asociace jako množiny I I

Hledání asociací se uplatňuje zejm. v “analýze transakcí” (“analýze nákupních košíků”) Příznaky: položky sortimentu. Instance: obsah nákupního košíku. Hodnoty příznaků jsou binární {ano, ne}. pivo ano ne

I

párky ne ano

horčice ne ano

pleny ano ne

Zde místo např. pivo = ano & pleny = ano

I

zapisujeme (a chápeme) asociaci jako množinu položek, např. {pivo, pleny} 5 / 16

Časté množiny

Princip monotonicity

6 / 16

pivo ano ano ne ano ano

párky ne ne ano ano ano

horčice ne ano ano ano ano

pleny ano ano ne ne ano

pivo ano ano ne ano ano

párky ne ne ano ano ano

horčice ne ano ano ano ano

pleny ano ano ne ne ano

pivo párky ano ne ano ne ne ano Časté množiny

horčice ne ano ano

pleny ano ano ne

Hledání častých množin položek algoritmem APRIORI Postupujeme z vyšších pater do nižších

Prázdná množina je vždy častá. Kandidáti o patro níž: {A}, {B}, {C}, {D}. 7 / 16

Časté množiny

Algoritmus APRIORI Apriori: C1 = ∀ množiny položek velikosti 1 L1 = ∀ časté množiny z C1 (podpora ≥ min_podp) i=1 repeat i := i + 1 Ci = Apriori-Gen(Li−1 ) Li := všechny časté množiny z Ci {Vyžaduje průchod databází} until∪Li = ∅ L = Li ,∀i return L

8 / 16

Časté množiny

Apriori-Gen(Li−1 ): Ci = ∅ for ∀ dvojice množin položek Mp , Mq ∈ Li−1 do if se shodují v i − 2 položkách then přidej Mp ∪ Mq do Ci end if end for for ∀ množiny položek M ∈ Ci do if jakákoliv podmnožina M o délce i − 1 není v Li−1 then odstraň M z Ci end if end for return Ci

Maximální množiny položek

I

Častých množin může být velmi mnoho

I

Výstup algoritmu je pak nepřehledý

I

Možné zjednodušení výstupu: zachovat pouze maximální množiny Maximální množina:

I

I

Je častá a žádná z jejích vlastních nadmnožin není častá

9 / 16

Časté množiny

Uzavřené množiny položek

I

Množina častých množin může být redundantní

I

Informace o všech častých množinách je implicitně obsažena v množině uzavřených častých množin Uzavřená množina:

I

I

žádná její vlastní nadmnožina nemá stejnou podporu

I

Každá maximální množina je uzavřená

I

(obráceně nemusí platit)

10 / 16

Časté množiny

Maximální a uzavřené množiny I

časté množiny položek barevně (podpora alespoň 3 instance), maximální množiny červeně

Transakce

Položky

t1 t2 t3 t4 t5 t6 t7 t8 t9 t10

a, d, e b, c, d a, c, e a, c, d, e a, e a, c, d b, c a, c, d, e b, c, e a, d, e

11 / 16

Časté množiny

Asociační pravidlo I

Pravidlo ve tvaru if Ant then Suc kde Ant a Suc jsou množiny položek nazývané antecedent resp. sukcedent. Pravidlo též zapisujeme jako Ant → Suc

I

Podpora asociačního pravidla R definována jako podp(Ant → Suc) = podp(Ant ∪ Suc)

I

Spolehlivost (confidence) asociačního pravidla R definována jako spol(Ant → Suc) = 12 / 16

Časté množiny

podp(Ant ∪ Suc) podp(Ant)

Asociační pravidlo

13 / 16

Časté množiny

Hledání asociačních pravidel algoritmem APRIORI I

Hledáme pravidla Ant → Suc, která jsou častá (tj. s podporou alespoň p) a spolehlivá (tj. se spolehlivostí alespoň s).

I

Je-li pravidlo Ant → Suc časté, tak množina položek (asociace) Ant ∪ Suc je častá.

I

Nejprve tedy najdeme všechny časté množiny položek.

I

Pro každou častou množinu položek M a každou její neprázdnou vlastní podmnožinu P ⊂ M zkusíme, zda podp(M) podp(P)

I

Pokud ano, tak pravidlo P→M\P je časté a spolehlivé. 14 / 16

Časté množiny

Hledání asociačních pravidel: příklad I

Hledáme asociační pravidla s podporou alespoň 0.1 a spolehlivostí alespoň 0.6. Právě 13% nákupních košíků obsahuje každou položku z množiny {párky, hořčice, pivo, otvírák}

I

Množina je tedy častá. Vyberme nějakou její vlastní neprázdnou podmnožinu, např. {párky, hořčice}

I

Pravidlo {párky, hořčice} → {pivo, otvírák} má podporu 13%. Pokud navíc právě 19% nákupních košíků obsahuje párky i horčici, má pravidlo spolehlivost 13 > 0.6 19 a je tedy časté i spolehlivé. 15 / 16

Časté množiny

Algoritmus AR-Gen Vytvoří množinu asociačních pravidel ze zadané množiny L častých množin položek a zadaného parametru min_spol minimální spolehlivosti. AR-Gen: R := ∅ for ∀M ∈ L do for ∀P ⊂ M, P 6= ∅ do if podp(M)/podp(P) ≥ min_spol then R := R ∪ {P → M \ P} end if end for end for return R

16 / 16

Časté množiny

Vytěžování dat, cvičení 8: Hledání množin častých položek a asociačních pravidel Jan Hrdlička


Fakulta elektrotechnická, ČVUT

1/7

Asociační pravidla

Analýza nákupního koše

I

Cílem této úlohy je zjistit, které produkty zákazníci kupují společně a z kterých produktů lze vytvořit asociační pravidla

I

Jedná se o aplikaci úlohy ”Vyhledávání častých množin” kterou znáte z přednášky.

2/7


Dataset

I

V matlabu načtěte soubor marketBasket.mat obsahující transakční databázi supermarketu vhodnou k analýze nákupního košíku.

I

V daném souboru se nachází proměnné ”tranDb” a ”info”.

I

Proměnná ”tranDb” je transakční databáze v maticové booleanovské formě. Každý řádek je transakce - jeden nákupní košík jednoho zákazníka.

I

Každý sloupec je jedna možná položka v košíku (item). Slovní popis těchto položek je v proměnné ”info”.

3/7


Apriori

I

Stáhněte si aprioriFPM.m, tato funkce vygeneruje množinu častých položek pro danou transakční databázi algoritmem apriori. Způsob použití funkce aprioriFPM.m zjistíte příkazem ”help aprioriFPM”.

I

Najděte množinu častých položek pro vámi zvolenou mininální relativní podporu. Tu odůvodněte.

I

Nalezené množiny vypište do souboru pomocí funkce printFreqSets.m

I

Mezivýsledek: Pro minimální relativní podporu rovnou 0.02 vám má vyjít 1302 častých množin.

4/7


Srovnání položek

I

Spusťte aprioriFPM pro množinu položek lexikálně srovnanou sestupně podle častosti výskytu a srovnanou vzestupně. Porovnejte časy obou běhů.

I

Výsledek popište a zdůvodněte.

5/7



I

Použijte funkci associationRules.m pro vygenerování asociačních pravidel. Způsob použití funkce aprioriFPM.m zjistíte příkazem ”help associationRules”.

I

Vygenerujte všechna asociační pravidla pro vámi zvolenou minimální relativní spolehlivost. Tu odůvodněte.

I

Mezivýsledek: Pro minimální relativní spolehlivost rovnou 0.7 (a dříve danou minimální relativní podporu 0.02) vám vyjde 480 asociačních pravidel.

I

Nalezená pravidla vypište do souboru pomocí funkce printRules.m

6/7


Faktické náležitosti protokolu

Váš protokol by měl obsahovat: I

Časté množiny položek pro vámi vybranou minimalní relativní podporu, minimální relativni podporu, kterou jste použili, její zdůvodnění

I

Časy běhů funkce aprioriFPM pro obě lexikální řazení, váš komentář k časům

I

Asociační pravidla pro vámi vybranou minimalní relativní spolehlivost, minimální relativní spolehlivost, kterou jste použili, její zdůvodnění

7/7


Základy vytěžování dat

Recommend Documents