Reguli de Asociere DM 4a

DATA MINING MACHINE LEARNING.

Reguli de asociere. Algoritmul APriori

50

4. Algoritmi pentru descoperirea regulilor de asociere

4.1. Introducere

Progresul n tehnologia codurilor de bare a fcut posibil ca firmele de comercializare a produselor s colecteze i s stocheze cantiti imense de date despre vnzri, referite ca i basket data basket market (date despre coul de cumprturi). O nregistrare n astfel de date const n mod tipic dintr-un:

- identificator de tranzacie, - data tranzaciei i - produsele cumprate n acea tranzacie. Firmele privesc aceste baze de date ca i pri eseniale ale infrastructurii de

marketing. Ele sunt interesate n introducerea unor procese de marketing conduse de informaii, coordonate prin folosirea tehnologiilor de baze de date, care s permit agenilor de marketing s dezvolte i s implementeze programe i strategii de marketing adaptate diverselor categorii de clieni. Acestea au la baza stabilirea unui profil al comparatorului care poate rezulta din produsele cumprate de acesta. (ce produse sunt cumprate mpreuna). Problema minrii regulilor de asociere din aceste date (basket data) a fost introdus de Agrawal n Mining association rules between sete of items in large databases. In Proc. of the ACM SIGMOD Conference on Management of Data, Washington, D. C., May 1993. Un exemplu de astfel de regul ar putea fi aceea c 98% din clienii care cumpr cauciucuri i accesorii auto, solicit de asemenea i servicii de verificare a mainii. Gsirea tuturor astfel de reguli este folositoare de exemplu pentru un marketing ncruciat. Alte aplicaii includ designul de cataloage, vnzri suplimentare, aezarea mrfurilor n magazin, i categorisirea clienilor pe baza tiparelor de cumprturi. De obicei bazele de date implicate n astfel de aplicaii sunt foarte mari. Este important, astfel, utilizarea unor algoritmi rapizi pentru aceste aplicaii.

Descoperirea regulilor de asociere are ca scop descoperirea unui set de atribute comune care aparin unui numr mare de obiecte dintr-o baz de date. Altfel spus scopul este de a gsi regulariti care apar in seturile de date

Descoperirea regulilor frecvente de asociere dintr-o baz de date de dimensiuni mari este o problem complex deoarece spaiul de cutare crete exponenial cu numrul de atribute din baza de date i cu obiectele bazei de date. Cele mai recente abordri sunt de natur iterativ necesitnd scanri multiple ale bazei de date, ceea ce este foarte costisitor.

n acest capitol se ncearc prezentarea celor mai des ntlnii algoritmi de descoperire a regulilor de asociere, gen APriori i se face o comparaie a acestora.



51

4.2.Definirea problemei 5.2.1. Definiie i terminologie

(a) Problema determinrii regulilor de asociere poate fi formulat astfel:

Avnd o baz de date de tranzacii ale clienilor i fiecare tranzacie fiind o list de obiecte (cumprturile unui client ntr-o vizit la magazin). Gsete toate regulile care coreleaz prezena unui set de obiecte cu alt set de obiecte.

De exemplu o baza de date de tranzacii este prezentata in Tabel 4.1.

Tabel 4.1 Lista de 9 tranzacii (cumprturi ) market data

Un set de articole de acest tip sunt cunoscute sub denumire de articolset. Un articolset care conine k articole este cunoscut sub denumirea de k-articolset. (de exemplu un set de articole {Books, CD, DVD, Video} este un 4-articolset).

O posibila regula de asociere care poate fi determinata din baza de date de tranzacii va avea urmtorul aspect:

98% din cei care cumpr Books cumpr de asemenea i CD-uri.

Regula nu trebuie s fie restricionat de numrul de obiecte cumprate nainte sau dup. De asemenea, exist posibilitatea de specificare a unor constrngeri pe reguli (de exemplu numai reguli care invoc anumite obiecte, cum ar fi: Books).

(b) Problema descoperirii tiparelor secveniale poate fi formulat astfel:

Transactia 1: {Books, CD, DVD} Transactia 2: {CD, Games} Transactia 3: {CD, DVD} Transactia 4: {Books, CD, Games} Transactia 5: {Books, DVD} Transactia 6: {CD, DVD} Transactia 7: {Books, DVD} Transactia 8: {Books, CD, DVD, Video} Transactia 9: {Books, CD, DVD}



52

Avnd o baz de date de tranzacii. Gsete tiparele secveniale maximale susinute de mai mult dect un

procentaj specificat de clieni.

De exemplu:

10% din clieni au cumprat books i DVD-uri la o cumprtur, urmat apoi de games ntr-o alt cumprtur.

Uneltele de asociere i secveniere analizeaz datele pentru a descoperi reguli care identific tipare de comportament, de exemplu, ce produse sau servicii tind clienii s aleag la aceeai cumprare, sau alt dat ca i cumprri ulterioare (adic ce cumpr deseori un client). Procesul care utilizeaz un algoritm de asociere sau secveniere pentru a gsi tipuri de reguli este n general numit analiza coului zilnic (market basket analysis) Exemple de reguli:

Cnd clienii cumpr o carte turistic ei de asemenea cumpr un dicionar de buzunar n 20% din cazuri.

(c) Fiecare regul are dou msuri, i anume:

preponderena sau suportul (support).

Suportul indic frecvena unui tipar, de exemplu ct de des articolele apar mpreun. n exemplul de mai sus, suportul este de 20%. Regulile cu o valoare mic a suportului pot fi rezultatul unei anomalii statistice. Un suport minim este necesar pentru ca o regul de asociere s fie folosit eficient.

If X and Y then Z with support s.

Interpretare: Regula este valid n s% din totalul tranzaciilor. Msura suport (preponderena)

este calculat n felul urmtor:

)()( YXPYXs = sau

.

i tranzactide totalNumarulY si X pe continand i tranzactide seturi de Numarul

Suportul



53

confidena (confidence)

Cea de-a doua msur confidena indic puterea unei asocieri, de exemplu ct de mult un articol specificat este dependent de altul. De exemplu:

If X and Y then Z with confidence c.

Interpretare: Dac X i Y sunt n acelai co (sunt cumprate de aceeai persoan), atunci Z este

de asemenea n co n c% din cazuri.

Msura confidena este calculat n felul urmtor:

).(/)()()( XPYXPXYPYXc ==

Numarul de seturi de tranzactii continand pe X si Y.

Numarul total de tranzactii continand pe XConfidenta

Presupunnd c X i Y apar mpreun n numai 1% din tranzacii dar de fiecare dat cnd apare X ansa ca Y s apar este de 80%. n acest caz 1% este prezena lui X i Y mpreun i reprezint suportul (preponderena) i 80% reprezint confidena (ncrederea n regul).

Pentru baza de tranzacii data in Tabelul 4.1 de exemplu: - un suport (preponderena) de 1% si - o confidena (ncrederea n regul) de 50% nseamn ca:

1% din transactiile analizate conin cumprturi e-cri si software si 50% din clienii care au cumprat e-carte au cumprat de asemenea si software.

- 2-articolset {Books, DVD} are o valoare suport de 5 in baza de tranzacii din tabelul 4.1

Exerciiu Baza de date (tabel 4.1) conine 9 tranzacii. Gsii valoarea suport si confidena pentru 2-articolset {Books, DVD}.

Rezolvare In primul rnd numrul de tranzacii care conin 2-articolset {Books, DVD} este 5. Numrul de tranzacii in care apare aticolset-ul {Books} este 6.

(1) In consecina suportul pentru 2-articolset-ul {Books, DVD} este

(5/9) * (100%) = 55.6%

(2) confidena pentru 2-articolset-ul {Books, DVD} este

(Valoare Support ({Books, DVD}) / Valoare Support ({Books}) * (100%) .



54

In consecina confidena pentru 2-articolset-ul {Books, DVD} este

((5/6) * 100%) = 83.3%

(d) Datele utilizate de algoritmii de asociere sunt formate din entiti i atribute i pot exista n unul din cele dou formate numite vertical sau orizontal.

1. n formatul orizontal exist un rnd pentru fiecare entitate i de asemenea coloane pentru fiecare atribut, de exemplu un rnd pentru fiecare co cu cumprturi (market basket) i coloane pentru fiecare produs Tabel 4.2. Problema este aceea c numrul de coloane poate deveni destul de mare (numrul de produse ar putea depi 100 000), i pentru a reduce numrul de coloane la un numr rezonabil este nevoie ca produsele similare s fie grupate mpreun.

Trans.ID Item A Item B Item C Item D Item E 132 Y Y 428 Y Y Y Tabel 4.2. Exemplu de date n format orizontal n regulile de asociere

2. n formatul vertical se folosesc rnduri multiple pentru memorarea unei entiti, utiliznd un rnd pentru fiecare atribut. Rndurile care corespund unei singure entiti au un numr de identificare comun (Trans.ID) ca n tabelul Tabel 4.3. Acest tip de reprezentare este mai normalizat n sens relaional i permite ca o entitate s aib o mai mare variabilitate referitor la numrul de atribute.

Trans.ID Product 132 Item A 428 Item B 428 Item C 428 Item D 132 Item E

Tabel 4.3. Exemplu de date n format vertical n regulile de asociere.

Unele produse Data Mining suport operaia de conversie din format orizontal n format vertical. Algoritmii de asociere pot opera numai pe date de tip enumerare (categorical data). Dac ar trebui utilizate atribute care nu sunt de tip enumerare, de exemplu cum ar fi venitul, atunci aceste date ar trebui grupate ntr-un interval (de exemplu: 0 la 20000; 20001 la 40000; 40001 la 70000; > 70001) transformnd fiecare interval ntr-un atribut.



55

(e) O alt caracteristic comun a algoritmilor regulilor de asociere este ierarhia de articole. Ierarhia de articole poate fi utilizat pentru a reduce numrul de combinaii la o dimensiune rezonabil prin gruparea articolelor similare mpreun. Utilizarea ierarhiei de articole duce la reducerea numrului de combinaii i de asemenea ajut la o mai mare generalizare i la o mai bun folosire a relaiilor.

In Concluzie

Problema descoperiri regulilor de asociere a fost introdus pentru prima dat de Agrawal i ali n 1993 , i poate fi formulat astfel:

Fiind dat un set de articole I = {I1, I2, , Im} i o baz de date de tranzacii D = {t1, t2, , tm} unde fiecare tranzacie are un

identificator unic i conine un set de articole, t1 = {Ii1, Ii2, , Iik}

Problema gsirii regulilor de asociere const n : identificarea tuturor regulilor de forma YX cu un suport (s) minim i o

confiden ( ) minim. Aceste valori ),( s sunt date ca i parametri de intrare.

Caracteristici (1) O regul de asociere este o expresie YX , unde X i Y sunt seturi de

articole. (2) Fiecare regul are dou msuri, i anume confidena (confidence) i

preponderena sau suportul (support). (3) Suportul indic frecvena unui tipar, de exemplu ct de des apar articolele mpreun. Msura suport este calculat n felul urmtor: )()( YXPYXs =


Numarul total de tranzactii Support

(4) Cea de-a doua msur confidena (confidence) indic puterea unei asocieri, de exemplu ct de mult un articol specific este dependent de altul.

If X and Y then Z with confidence .

Dac X i Y sunt n acelai co (sunt cumprate de aceeai persoan), atunci Z este de asemenea n co n % din cazuri.

).(/)()()( XPYXPXYPYxc ==



56


Numarul total de tranzactii continand pe XConfidence

Problema descoperirii regulilor de asociere const n generarea regulilor care au un suport mai mare dect suportul minim s i o confiden mai mare dect confidena minim .

Abordarea este independent de reprezentarea lui D. De exemplu D ar putea fi un fiier cu date, o tabel relaional sau rezultatul unei interogri.

Un algoritm pentru gsirea tuturor regulilor de asociere, AIS, a fost prezentat n Mining association rules between sete of items in large databases. In Proc. of the ACM SIGMOD Conference on Management of Data, Washington, D. C., May 1993.

Un alt algoritm numit SETM, a fost propus n M. Houtsma and A. Swami. Set-oriented mining of association rules. Research Report RJ 9567, IBM Almaden Research Center, San Jose, California, October 1993.

Dar algoritmul cu impactul cel mai mare Apriori a fost prezentat n Rakesh Agrawal, Ramakrishnan Srikant Fast Algorithms for Mining Association Rules, Proc. of 20th Intl conf. on VLDB pag. 487-499, 1994.

.

4.3. Descoperirea seturilor frecvente de articole Problema descoperirii tuturor regulilor de asociere poate fi descompus n dou

sub probleme:

1. Gsirea tuturor seturilor de k-articolset care au suportul mai mare dect suportul minim specificat de utilizator

2. Folosirea seturilor frecvente de articole pentru generarea regulilor dorite. (a) Pentru fiecare set frecvent de articole l, gsete toate subseturile a ne vide

ale lui l. (b) Pentru fiecare astfel de subset a, tiprete o regul de forma a (l a)

dac raportul suport(l) / suport(a) este cel puin minconf (minim pentru o confidena ceruta) .

Algoritmii de descoperire a seturilor frecvente de articole n general fac mai multe treceri asupra datelor. Pentru a ilustra aceti pai (algoritm Apriori) considerm urmtorul exemplu:

Baza de Date T1 Item 10 A C D 20 B C E 30 A B C E 40 B E

Presupunem ca suportul minim impus de utilizator este de =.49



57

n prima trecere, se calculeaz suportul pentru articole individuale i se determin care dintre ele sunt frecvente, adic satisfac suportul minim.

n urmtoarele treceri, se pornete cu seturile de articole gsite a fi frecvente. Acestea sunt folosite pentru generarea de noi seturi potenial frecvente de articole, denumite seturi de articole candidat, i se calculeaz suportul actual pentru aceste candidate. Raionamentul este acela c: orice subset al unui set frecvent trebuie s fie frecvent. Astfel, seturile candidate avnd k articole pot fi generate prin reunirea seturilor frecvente avnd k-1 articole, i tergnd acelea care conin orice subset care nu este frecvent. Aceast procedur rezult n generarea a mult mai puini candidai.

La sfritul trecerii, se determin care dintre candidai sunt ntr-adevr frecveni i acetia sunt folosii n urmtoarea trecere. Acest proces continu pn cnd numai sunt gsite noi seturi frecvente de articole.

(k = 1) articolset

C1 Suport L1 {A} .50 Y {B} .75 Y {C} .75 Y {D} .25 N {E} .75 Y

(k = 2) articolset

C2 Suport L2 {A,B} .25 N {A,C} .50 Y {A,E} .25 N {B,C} .50 Y {B,E} .75 Y {C,E} .50 Y

(k = 3) articolset

C1 Suport L1 {B,C,E} .50 Y

(k = 4) articolset

C1 Suport L1 {A,B,C,E} .25 N

Y este articol frecvent (s>0.49) N- nu este articol frecvent

Y este articol frecvent (s>0.49) N- nu este articol frecvent



58

REGULA DE ASOCIERE care poate fi creat in acest moment este: If B and C then E. unde: suportul este .50 confidena este 1

Pentru a descrie principalii algoritmi utilizai vom recurge la urmtoarele Notaii:

(a) Presupunem c articolele din fiecare tranzacie sunt pstrate ntr-o ordine lexicografic. Adaptarea acestor algoritmi la baze de date normalizate n care fiecare nregistrare const din perechi , unde TID este identificatorul de tranzacie, este o operaie relativ simpl.

(b) Numrul de articole dintr-un set reprezint dimensiunea acestuia, iar un set de articole de dimensiune k l denumim un k-articolset.

(c) Articolele din cadrul unui set sunt meninute n ordine lexicografic. Folosim notaia c[1]c[2] c[k] pentru a reprezenta un k-articolset c constnd din articolele c[1],c[2],,c[k], unde c[1]



59

4.4. Algoritmul APriori

Scopul algoritmului poate fi rezumat astfel: Gsete articolele frecvente: setul de articole care au un support minim Foloseste articolele frecvente pentru a genera reguli

Principiul de baza de funcionare a acestui algoritm este urmtorul: Orice subset a unui articol frecvent trebuie de asemenea sa fie frecvent

De exemplu: Daca {AB} este un articol frecvent , atunci att {A} cat si {B} trebuie sa fie

articole frecvente. Acest aspect este evident. De exemplu

In figura de mai jos se prezint un exemplu de generare a celui mai frecvent articol care definete o macheta pentru setul de date din care provine. Acest exemplu este o ilustrare a modului in care funcioneaz algoritmul Apriori.



60

Figura 4.5. prezint algoritmul APriori. 1) Primul pas numr apariiile fiecrui articol pentru a determina seturile de

articole frecvente de lungime 1 (1-articolset-urile frecvente). 2) Un pas ulterior, de exemplu pasul k, const din dou faze. n primul rnd articolset-urile frecvente gsite n pasul (k-1) sunt folosite

pentru generarea articolset-urilor candidat Ck, folosind funcia apriori-gen descris n seciunea 4.3.1.

Pe urm baza de date este scanat i suportul pentru candidaii din Ck este calculat. Pentru un calcul rapid, trebuie s determinm ntr-un mod eficient candidaii din Ck care sunt coninui ntr-o anume tranzacie t. Seciunea 4.3.2 descrie funcia subset folosit n acest scop.

1) L1 = {1-articolset-urile mari}; 2) for (k = 0; Lk-1 ; k++) do begin 3) Ck = apriori-gen(Lk-1); // generare de candidati 4) forall tranzacii t D do begin 5) Ct = subset(Ck, t); // candidai n t 6) forall candidai c Ct do 7) c.count++; 8) end 9) Lk = {c Ck | c.count minsup}; 10) end 11) Rezultat = kLk;

Fig. 4.5. Algoritmul Apriori

Generarea candidailor Apriori

Pentru a ilustra principiul de generare a candidailor plecam de la urmtorul exemplu:

Fie L3 = {{1 2 3}, {1 2 4}, {1 3 4}, {1 3 5}, {2 3 4}}. Dup pasul de reunire, L3* L3

C4 va fi {{1 2 3 4}, {1 3 4 5}}. {1 2 3 4}, va rezulta din {1 2 3}, {1 2 4} si {2 3 4} {1 3 4 5}, va rezulta din {1 3 4} si {2 3 4}

Pasul de curare va terge articolset-ul {1 3 4 5} deoarece articolset-ul {1 4 5} nu este n L3.

Deci n C4 va rmne doar {1 2 3 4}.



61

Generarea candidailor Funcia apriori-gen primete ca i argument Lk-1, setul tuturor (k-1) articolset-

urilor frecvente i ntoarce un superset al setului tuturor k-articolset-urilor frecvente. Funcia lucreaz n felul urmtor. n primul rnd, n pasul de reunire, se reunete Lk-1 cu Lk-1:

insert into Ck select p.item1, p.item2,...,p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1 = q.item1, ..., p.itemk-2 = q.itemk-2, p.itemk-1 < q.itemk-1;

Pe urm, n pasul de curare, se terg toate articolset-urile c Ck a cror orice (k-1) subset nu se regsete n Lk-1: forall articolset-uri c Ck do forall (k-1)subset s al lui c do

if (s Lk-1) then delete c din Ck;

n continuare se prezint algoritmul pentru funcia apriori-gen n Fig. 4.6

Intrare: Li-1 // articolseturi frecvente de dimensiunea i-1

Ieire Ci // candidai de dimensiunea i

Funcia apriori-gen: Ci ; for each I Li-1 do for each J I Li-1 do

if primele i-2 din elementele din I si J sunt egale then Ck = Ck {I J};

Fig.4.6. Funcia apriori-gen

4.4.1. Reducerea numrului de candidai. Funcia subset Seturile de articole candidat Ck sunt pstrate ntr-un arbore hash (hash-tree). Un

nod al acestui arbore fie conine: list de articolset-uri (un nod frunz) sau o tabel hash (un nod interior). ntr-un nod interior, fiecare intrare n tabel arat

ctre un alt nod. Rdcina arborelui este definit a avea adncimea 1. Un nod interior la

adncimea d arat spre noduri cu adncime d+1. Articolset-urile sunt stocate n frunze.



62

Cnd adugm un articolset c, pornim de la rdcin i parcurgem n jos arborele pn cnd atingem un nod frunz. La un nod interior la adncimea d, pentru alegerea ramurii de parcurs se aplic o funcie hash asupra articolului d al articolset-ului. Toate nodurile sunt create iniial ca i noduri frunz. Cnd numrul de articolset-uri dintr-un nod frunz depete un anumit prag specificat, nodul frunz este convertit ntr-un nod interior.

ncepnd de la nodul rdcin, funcia subset gsete toi candidaii coninui ntr-o anumit tranzacie t dup cum urmeaz. Dac suntem la un nod frunz, gsim care dintre articolset-uri din nodul frunz sunt coninute n t i adugm referine la ele n setul de rspuns. Dac suntem la un nod interior la care am ajuns prin aplicarea funciei hash pe articolul i, aplicm funcia hash pe fiecare articol care urmeaz dup articolul i n tranzacia t i n mod recursiv aplicm aceast procedur nodului corespunztor. Pentru nodul rdcin aplicm funcia hash pe fiecare articol din t.

Reguli de Asociere DM 4a

Documents

Transcript of Reguli de Asociere DM 4a