CURS 1

Data Mining

CURS 10Algoritmi pentru determinarea mulimilor frecvente

de articole i a regulilor de asociereMulimile frecvente joac un rol esenial n multe aplicaii data mining, ncercnd s gseasc modele interesante n bazele de date. Cea mai des ntlnit aplicaie este gsirea regulilor de asociere, care a avut ca prim motivaie analizarea tranzaciilor dintr-un supermarket pentru examinarea comportamentului clienilor n funcie de produsele cumprate.

Notaiile folosite n continuare sunt cele prezentate n cursul anterior.

Pentru calcularea suportului unei colecii de mulimi de articole, este nevoie s se acceseze baza de date. Deoarece bazele de date ce memoreaz tranzaciile tind s fie foarte mari, nu este ntotdeauna posibil stocarea acestora n memoria principal. Un factor important al marii majoriti a algoritmilor este reprezentarea bazei de date a tranzaciilor. Conceptual, baza de date poate fi reprezentat ca o matrice bidimensional n care fiecare linie reprezint o tranzacie individual iar coloanele reprezint articolele din I. O astfel de matrice poate fi reprezentat n mai multe feluri. Cel mai des utilizat este modelul orizontal al datelor. n acest model, fiecare tranzacie are un identificator de tranzacie i o list de articole ce apar n cadrul tranzaciei. Alt model foarte des utilizat este modelul vertical al datelor n care baza de date este alctuit dintr-o mulime de articole, fiecare articol fiind nsoit de frontiera sa. De asemenea, algoritmii pot folosi i o combinaie a celor dou modele.

Pentru a calcula suportul unei mulimi de articole X folosind modelul orizontal al bazei de date, este nevoie s se parcurg toat baza de date i s se testeze pentru fiecare tranzacie dac . n cadrul aceleiai parcurgeri, aceast operaie poate fi fcut pentru o colecie mare de mulimi de articole. O concepie greit despre explorarea modelelor frecvente este c scanarea bazei de date este o operaie de I/O foarte complex. n cele mai multe cazuri, aceast operaie nu reprezint costul principal al timpului de execuie al unui algoritm. n schimb, actualizarea suportului tuturor mulimilor de articole candidat coninute de o anumit tranzacie consum considerabil mai mult timp dect citirea acelei tranzacii dintr-un fiier sau dintr-un cursor al bazei de date. ntr-adevr, pentru fiecare tranzacie trebuie verificat pentru fiecare mulime de articole candidat dac este inclus n acea tranzacie, sau trebuie verificat pentru fiecare submulime a acelei tranzacii dac este coninut de o mulime de articole candidat. Pe de alt parte, numrul tranzaciilor dintr-o baz de date este deseori corelat cu dimensiunea maxim a tranzaciilor din baza de date. Prin urmare, numrul tranzaciilor nu are o mare influen pentru timpul necesar calculrii suportului, nefiind factorul determinant.

Modelul vertical al bazei de date are avantajul major c suportul unei mulimi X poate fi calculat uor prin simpla intersecie a frontierelor a dou din submulimile sale , astfel nct . Dndu-se o colecie de mulimi de articole candidat, aceast tehnic cere ca frontierele unui numr mare de mulimi de articole s fie disponibile n memoria principal, ceea ce nu este ntotdeauna posibil.

nc de la introducerea lor in 1993, de ctre Argawal et al., problema mulimilor frecvente i a explorrii regulilor de asociere a primit o mare atenie din partea cercettorilor. n ultimii ani, sute de lucrri de cercetare care au fost publicate au prezentat algoritmi noi i mbuntiri ale algoritmilor existeni, pentru rezolvarea ct mai eficient a acestei probleme. n acest curs vom descrie tehnicile de baz folosite pentru rezolvarea acestor probleme i voi face un studiu exhaustiv al celor mai influeni algoritmi propui n ultimii ani.

1. Algoritmul Apriori

Algoritmul Apriori determin suportul mulimilor de articol prin metoda BFS (Breadth First Search). Pentru nceput el determin suportul mulimilor cu un articol, apoi suportul mulimilor cu 2 articole etc.

Algoritmul nu determin suportul tuturor mulimilor posibile, ci folosete o strategie inteligent pentru a determina candidai pentru mulimile frecvente. El gsete mulimile cu k articole ce conin toate submulimile frecvente. Observaia de baz const n faptul c selecia de candidai se bazeaz pe principiul Apriori, conform cruia orice submulime a unei mulimi frecvente trebuie s fie frecvent i toate mulimile frecvente cu cel mult k elemente vor fi submulimi ale mulimilor frecvente de k+1 elemente. Deci, odat aleas o mulime de candidai doar k+1 pot fi submulimi frecvente corespunztoare. Aceasta este mulimea cu numr minim de candidai care poate fi gsit, fr a se face alte scanri ale bazei de date, avndu-se n vedere mulimile frecvente pn la nivelul k.

Modalitatea simpl de a determina candidaii mulimii este s enumerm toate k+1 submulimi posibile i s le nlturm pe cele care nu sunt submulimi frecvente.

Complexitatea determinrii potenialilor candidai este redus i mai mult folosind operatorul de join. Dac mulimile de elemente sunt reprezentate ntr-o list ordonat A[1:k], operaia de join a unei mulimi frecvente Lk, ce conine k articole, cu ea nsi este mulimea cu k+1 submulimi ce sunt definite ca o reuniune de mulimi frecvente de k articole.

Efectuarea operaiei de join necesit vizitarea elementelor lui Lk cel puin de dou ori, dac ele sunt n ordine alfabetic.

Succesiunea operaiilor i etapele algoritmului Apriori se regsesc n figura 1.

Figura 1. Etapele algoritmului Apriori

Exist dou probleme majore de calcul la folosirea algoritmului Apriori pentru descoperirea regulilor de asociere. Prima problem const n faptul c algoritmul furnizeaz un numr mare de asocieri, multe din ele fiind neinteresante. Ct timp putem controla numrul de asocieri create cu ajutorul pragului minim de suport, numrul de reguli de asociere este redus la un numr rezonabil. Regulile interesante sunt deseori gsite ntr-o zon intermediar a dimensiunii suportului. O singur valoare pentru suport nu este ntotdeauna suficient pentru a gsi structuri interesante.

A doua problem major de calcul nu se refer la numrul de mulimi frecvente de articole (mrimea lui ), ci la mrimea unei mulimi frecvente de articole. Dac folosim algoritmul Apriori pentru fiecare mulime frecvent de articole, gsirea suportului tuturor submulimilor trebuie realizat nainte ca mulimea s devin un candidat. Pentru o mulime care conine k articole, trebuie calculat suportul pentru submulimi. Dac de exemplu k=20, numrul de submulimi ce trebuie analizate este foarte mare. Complexitatea determinrii suportului pentru toate aceste mulimi crete proporional cu numrul de articole din fiecare submulime considerat. Astfel, mulimile frecvente de articole de dimensiuni mari nu sunt fezabile. Limitarea dimensiunii mulimilor este o proprietate pe care metoda BFS o folosete. Pentru gsirea mulimilor frecvente de articole foarte mari avem nevoie de alt metod.

Primul algoritm care a generat toate mulimile frecvente de articole i reguli de asociere de ncredere a fost algoritmul AIS propus de Agrawal et al.. La scurt timp dup, algoritmul a fost mbuntit i redenumit n Apriori, exploatnd proprietatea de monotonie a suportului mulimilor de articole i a regulilor de asociere. Aceleai tehnici au fost independent propuse de Mannila et al..

Proprietatea 1. (Monotonia suportului) Dndu-se o baz de date de tranzacii D peste mulimea de articole I, fie dou mulimi de articole. Atunci,

support(Y)support(X).

Prin urmare, n cazul n care o mulime de articole nu este frecvent, atunci toate mulimile care o vor conine nu vor fi nici ele frecvente. n literatura de specialitate, aceast proprietate de monotonie este denumit i nchidere de proprietate deoarece mulimea de mulimi frecvente este nchis n raport cu includerea mulimilor.

Proprietatea 2. (Monotonia ncrederii) Fie trei mulimi de articole, astfel nct . Atunci,

ncrederea este monoton descresctoare cu privire la prelungirea regulii generate.

1.1. Explorarea mulimilor de articole

Pentru simplitate, vom presupune n continuare c articolele din tranzacii i mulimile de articole sunt sortate n ordine lexicografic, cu excepia cazurilor n care se specific altfel.

Faza explorrii mulimilor din algoritmul Apriori este dat n listingul 1. Voi folosi notaia X[i] pentru a reprezanta al i-lea articol din X. Submulimea k-prefix a unei mulimi X este k-mulimea de articole {X[1],,X[k]}.Listingul 1. Algoritmul Apriori Explorarea mulimilor de articole

Input: D, minsupp

Output: F C1={{i}|iI};

k=1;

while Ck{} do{ //Compute the supports of all candidate itemsets

forall transactions(tid,D)D forall candidate itemsets XCk if ()

X.support++;

//Extract all frequent itemsets

Fk = {X|X.support minsupp};

//Generate new candidate itemsets

forall X,Y Fk, X[i]=Y[i] for 1 i k-1, and X[k}