Calcul din regulile de asociere - descărcare ppt
Calculul regulilor de asociere Prelegere în Data Warehouse and Mining
Cuprins Introducere: Origine, nomenclatură Apriori: algoritm de bază Elemente ierarhice Elemente valorice în cantitate Reguli de asociere Outlook
Introducere Crearea ierarhiei a priori, cantitatea Introducere Crearea unor seturi de date mai mari, seturi de date mai precise, resurse hardware mai bune. Dorința de recunoaștere a regulilor interesante în aceste seturi mari de date. Reguli de asociere
Nomenclatura tranzacției: Acțiune asupra bazei de date (achiziție.) Introducere Ierarhie Apriori, cantitate Nomenclatură tranzacție: Acțiune pe baza de date (achiziție.) Element: Parte dintr-o tranzacție (lapte.) Set de elemente: Cantitatea de articole Regula de asociere: X Y (dacă tranzacția conține X, apoi conține și Y) Încredere c: c% din tranzacții respectă Regulile de asociere (minconf: limită inferioară pentru algoritm) Suport s: s% din tranzacții conțin X și Y (minsup: limită inferioară pentru algoritm) Reguli de asociere
Exemplu T1 T2 Introducere Ierarhia Apriori Cantitate Exemplu T1 T2 T3 T4 T5 Încredere Suport Pâine ese Brânză 100% 40% Brânză Lapte 66,6% 40% Pastă de dinți Ciocolată 50% 20% Reguli de asociere
Introducere Ierarhia Apriori Cantitatea Motivația Dorința de recunoaștere automată a acestor reguli de asociere: Algoritmul „Apriori” Unele articole au o dependență de bază, descendență ierarhică (lapte milk lapte integral) Anumite reguli de asociere necesită articole cantitative (2 mașini 2 copii peste 18 ani) Reguli de asociere
Introducere Ierarhia Apriori Algoritmul de cantitate Apriori Descoperirea regulilor de asociere poate fi împărțit în două probleme. Găsiți toate seturile de articole cu suport minim. Utilizați aceste seturi de articole pentru a determina regulile de asociere Regulile de asociere
Găsiți seturi de elemente Găsiți toate seturile de articole cu suport minim Introducere Ierarhie prioritară Cantitate Găsiți seturi de elemente Găsiți toate seturile de elemente cu suport minim Începeți cu seturi cu un singur element (1 seturi) -> simplu „numărare” Combinați seturile determinate (k-1) în seturi noi de k Pas de alăturare: Crearea candidaților Pasul de tăiere: Ștergerea tuturor candidaților care au un subset „greșit” Regulile de asociere
Exemplu: Seturi de articole Exemplu: 3-seturi de candidați pentru 4-sets Introducere Ierarhie Apriori Cantitate Exemplu: Seturi de elemente Exemplu: 3-seturi de candidați pentru 4-sets Alăturați-vă Prune 4-sets Reguli de asociere
Generare Generare de reguli de asociere Introducere Ierarhie Apriori Generare de cantitate Generare de reguli de asociere Examinarea tuturor subseturilor a unui set de articole I a (I - a), dacă Asistență (I) Asistență (a)> = minconf
Exemplu: Generarea introducerii unei ierarhii a priori, cantitate Exemplu: Generarea I = [40%] Subseturi: minconf = 75% Suport (I) = 40% Suport (a) = 50% Încredere = 80% OK! Suport (I) = 40% Suport (a) = 80% Încredere = 50% NU! Regulile de asociere
Introducere Ierarhia Apriori Cantitate Introducere Până în prezent: Lapte Pâine [80%] ar fi mult mai informativ dacă Dieta Lapte Pâine albă [75%] doresc regulile Asociației Ierarhiei
Exemplu Cu cât un element este mai adânc în ierarhie, cu atât mai mare este introducerea ierarhiei a priori, cantitatea, exemplu, mâncare, lapte, pâine. Dietă. Cereale întregi albe. Cu cât un element este mai adânc în ierarhie, cu atât suportul necesar ar trebui să fie mai mic Regulile de asociere
Extinderea codificării Apriori: Introducerea cantității ierarhiei Apriori Extinderea codificării Apriori: Codificarea diferitelor produse Lapte 1 Lapte dietetic 11 Lapte integral 12 Pâine 2 Pâine albă 21 Pâine integrală 22 Tabel de tranzacții: T1: T2:. Regulile de asociere
Primele seturi de articole Mai întâi la nivelul superior Căutați seturile de articole: Introducere ierarhie a priori, cantitate Primele seturi de articole Mai întâi la nivelul superior, căutați seturile de articole: Calculul regulilor de asociere și filtrarea tabelului de tranzacții 30% 40% 30% T1: T2: Reguli de asociere
Introducere Ierarhie Apriori Cantitate Iterare Iterare: Căutați următoarele seturi de elemente pe o masă filtrată (până la tabel gol sau la sfârșitul ierarhiei) Calculul regulilor de asociere și filtrarea tabelului de tranzacții 20% 30% 30% 20% 20% Reguli de asociere
Introducere Până în prezent: numai regulile de asociere „binare” de ex. Pâine Lapte Ierarhie Apriori Cantitate Introducere Până în prezent: numai reguli de asociere „binare” de ex. Pâine Lapte Extinderea la regulile de asociere „cantitative”, de ex. Rules Reguli de asociere
Probleme Conversia banală a valorii setate în tabel binar, DAR: Introducere cantitate ierarhică a priori Probleme Conversia banală a valorii setate în tabel binar, DAR: Numărul articolului explodează (timpul de execuție!) Numărul de reguli explodează Regulile de asociere
Algoritm modificat la intervale: Introducere Ierarhie Apriori Cantitate Algoritm modificat la intervale: Se selectează un interval pentru fiecare atribut de cantitate Reguli de asociere
Alegerea intervalelor Problemă cu alegerea intervalului: Introducere Cantitatea ierarhiei Apriori Alegerea intervalelor Problemă cu alegerea intervalului: mult prea multe combinații de intervale Introducerea completitudinii parțiale: măsurarea pierderii de informații la generalizarea unui interval Regulile de asociere
Completitatea parțială k-Completarea parțială: Introducere Ierarhia Apriori Cantitatea Completitatea parțială k-Completarea parțială: Pentru generalizarea unui set de articole, suportul nu trebuie să crească cu mai mult de factorul k 1,5-Parțial-complet: 5% 6% 8% 5% 6 % 6% 8% 6% Regulile de asociere
Reducerea ștergerii RA a regulilor de asociere „așteptate” Introducere Cantitatea ierarhiei Apriori Reducerea ștergerii RA a regulilor de asociere „așteptate” 12x 3x -> 8% suport, 70% încredere -> 2% suport, 70% încredere Poate fi șters deoarece nu există o nouă constatare Regulile de asociere
Ierarhia Apriori cantitatea algoritmul de perspectivă „apriori”: versiuni optimizate cu un timp de rulare mai rapid sau cu mai puține cerințe de memorie