Výpočet z asociačných pravidiel - ppt stiahnuť
Výpočet prednášky o pravidlách asociácie v dátovom sklade a ťažbe
Obsah Úvod: Pôvod, nomenklatúra Apriori: základný algoritmus Hierarchické položky Položky v množstve
Úvod Vytvorenie apriórnej hierarchie, kvantita Úvod Vytvorenie väčších množín údajov, presnejších množín údajov, lepších hardvérových zdrojov Túžba po rozpoznaní zaujímavých pravidiel v týchto veľkých množinách údajov Pravidlá asociácie
Nomenklatúra transakcie: Akcia v databáze (nákup.) Úvod Apriori hierarchia, množstvo Nomenklatúrna transakcia: Akcia v databáze (nákup.) Položka: Časť transakcie (mlieko.) Sada položiek: Množstvo položiek Asociačné pravidlo: X Y (ak transakcia obsahuje X, potom obsahuje aj Y) Dôvera c: c% transakcií sa riadi Asociačnými pravidlami (minconf: dolná hranica algoritmu) Podpora s: s% transakcií obsahuje X a Y (minsup: dolná hranica algoritmu) Pravidlá asociácie
Príklad T1 T2 Úvod Apriori Hierarchia Množstvo Príklad T1 T2 T3 T4 T5 Podpora dôveryhodnosti Chlieb Syr 100% 40% Syr Mlieko 66,6% 40% Zubná pasta Čokoláda 50% 20% Pravidlá asociácie
Úvod Apriori hierarchia Množstvo Motivácia Túžba po automatickom rozpoznaní týchto asociačných pravidiel: Algoritmus „Apriori“ Niektoré položky majú základnú závislosť, hierarchický pôvod (mlieko plnotučné mlieko) Niektoré pravidlá asociácie vyžadujú kvantitatívne položky (2 autá 2 deti nad 18 rokov) Pravidlá asociácie
Úvod Apriori Hierarchia Kvantitatívny algoritmus Apriori Objavovanie asociačných pravidiel, ktoré možno rozdeliť na dva problémy. Nájsť všetky sady položiek s minimálnou podporou Pomocou týchto skupín položiek môžete určiť pravidlá asociácie Pravidlá asociácie
Nájsť sady položiek Nájsť všetky sady položiek s minimálnou podporou Úvod A priori hierarchia Množstvo Nájsť sady položiek Nájsť všetky sady položiek s minimálnou podporou Začať s jednoprvkovými sadami (1-sady) -> jednoduché „počítanie“ Stanovené (k-1) sady kombinovať do nových k-súborov Pripojte sa krok: Vytvorenie kandidátov Prerobte krok: Odstránenie všetkých kandidátov, ktorí majú „nesprávnu“ podmnožinu Asociačných pravidiel
Príklad: Súbory položiek Príklad: 3-sady kandidátov na 4-sady Úvod Apriori hierarchia Množstvo Príklad: Sady položiek Príklad: 3-sady kandidátov na 4-sady Pripojte sa k Prune Pravidlá asociácie 4-sady
Generovanie Generovanie asociačných pravidiel Úvod Apriori Hierarchia Generovanie množstva Generovanie asociačných pravidiel Preskúmanie všetkých podmnožín a množiny položiek I a (I - a), ak Podpora (I) Podpora (a)> = minconf Asociačné pravidlá
Príklad: Generácia zavedenia apriórnej hierarchie, kvantita Príklad: Generácia I = [40%] Podmnožiny: minconf = 75% Podpora (I) = 40% Podpora (a) = 50% Dôvera = 80% OK! Podpora (I) = 40% Podpora (a) = 80% Dôvera = 50% NIE! Asociačné pravidlá
Úvod Apriori Hierarchia Množstvo Úvod Doteraz: Mlieko Chlieb [80%] by bolo oveľa informatívnejšie, ak by si Diétne mlieko Biely chlieb [75%] prialo pravidlá asociácie hierarchie
Príklad Čím hlbšia je položka v hierarchii, tým viac sa iniciuje apriórna hierarchia, množstvo, príklad, jedlo, mlieko, chlieb. Strava. Plné biele celé zrno. Čím hlbšie je položka v hierarchii, tým menšia požadovaná podpora by mala byť Asociačné pravidlá
Rozšírenie kódovania Apriori: Zavedenie množstva aprioriho hierarchie Rozšírenie kódovania Apriori: Kódovanie rôznych produktov Mlieko 1 Diétne mlieko 11 Plnotučné mlieko 12 Chlieb 2 Biely chlieb 21 Celozrnný chlieb 22 Transakčná tabuľka: T1: T2:. Asociačné pravidlá
Prvé sady položiek Najprv na najvyššej úrovni Vyhľadajte sady položiek: Úvod a priori hierarchie, množstvo Prvé sady položiek Najskôr na najvyššej úrovni vyhľadajte sady položiek: Výpočet asociačných pravidiel a filtrovanie tabuľky transakcií 30% 40% 30% T1: T2: pravidlá asociácie
Úvod Apriori hierarchia Množstvo Iterácia Iterácia: Hľadať ďalšie sady položiek na filtrovanej tabuľke (až do prázdnej tabuľky alebo na konci hierarchie) Výpočet asociačných pravidiel a filtrovanie transakčnej tabuľky 20% 30% 30% 20% 20% Pravidlá asociácie
Úvod Zatiaľ: iba „binárne“ pravidlá asociácie, napr. Chlieb mlieko Apriori hierarchická kvantita Úvod Zatiaľ: iba „binárne“ pravidlá asociácie, napr. Chlieb Rozšírenie mlieka na „kvantitatívne“ pravidlá asociácie, napr. Pravidlá asociácie
Problémy Triviálna konverzia hodnoty nastavenej na binárnu tabuľku, ALE: Úvod a priori kvantitu hierarchie Problémy Triviálna konverzia hodnoty nastavenej na binárnu tabuľku, ALE: Počet explodujúcich položiek (čas vykonania!) Počet pravidiel exploduje Pravidlá asociácie
Intervaly Upravený algoritmus: Úvod Apriori Hierarchia Množstvo Intervaly Upravený algoritmus: Pre každý atribút množstva je vybratý interval Asociačné pravidlá
Výber intervalov Problém s výberom intervalu: Úvod Apriori kvantita množstva Výber intervalov Problém s výberom intervalu: príliš veľa kombinácií intervalov Úvod čiastočnej úplnosti: miera straty informácií pri zovšeobecňovaní intervalu Asociačné pravidlá
Čiastočná úplnosť k-Čiastočná úplnosť: Úvod Apriori Hierarchia Množstvo Čiastočná úplnosť k-Čiastočná úplnosť: Pre zovšeobecnenie množiny položiek sa podpora nesmie zvýšiť o viac ako faktor k 1,5-Čiastočná úplnosť: 5% 6% 8% 5% 6 % 6% 8% 6% Pravidlá asociácie
Zníženie AR Vymazanie „očakávaných“ Asociačných pravidiel Úvod Apriori hierarchia množstva Zníženie AR Vymazanie „očakávaných“ Asociačných pravidiel 12x 3x -> 8% podpora, 70% dôvera -> 2% podpora, 70% dôvera Môže byť vymazaný ako žiadny nový nález Asociačné pravidlá
Apriori hierarchia kvantitatívny výhľad výhľadový algoritmus „apriori“: optimalizované verzie s rýchlejším časom chodu alebo s menšími požiadavkami na pamäť hierarchické položky: nielen nájsť asociačné pravidlá na rovnakej úrovni, ale aj asociačné pravidlá na rôznych úrovniach