NVARE NESUPERVIZAT: REGULI DE ASOCIERE

1. INTRODUCERE

Extragerea de reguli de asociere este o ramur intens studiat a domeniului descoperirii de cunotine, cu un rol crucial n aplicaiile e-business (marketing electronic, comer electronic, etc.).

Interesul pentru gsirii mulimilor frecvente de articole a pornit de la eforturile de a descoperi modele

folositoare in bazele de date ce conin tranzaciile consumatorilor. O baza de date cu tranzaciile

consumatorilor este o secven de tranzacii ),,( 1 nttT K= , unde fiecare tranzacie este o multime de articole.

Determinarea mulimilor frecvente de articole i a regulilor de asociere este esenial pentru problema coului

pieei. Vanzatorii utilizeaz aceste informaii pentru aezarea articolelor in rafturi i controleaz modul in

care un cumparator tipic traverseaz magazinul. Principii similare stau ns i la baza analizei modului n care

utilizatorii navigheaz pe Internet i acceseaz diverse site-uri.

Exista un principiu cheie, numit monotonicitate (monotonicity) sau principiul a-priori care ne ajuta

s gsim mulimile frecvente de articole: dac o mulime de articole S este frecvent (apare cel puin n a s-

a parte a courilor), atunci orice submulime a lui S este asemenea frecvent.

Dterminarea mulimilor frecvente de articole presupune parcurgerea mai multor etape:

1. Procedm nivel cu nivel, gsind inti articolele frecvente (mulimi de dimensiune 1), apoi perechile

frecvente, tripletele frecvente, etc.

2. Gasim toate multimile frecvente de articole maximale (mulimile S astfel inct o mulime care include

strict pe S nu este frecvent) ntr-o singur trecere sau n cteva treceri.

Regulile de asociere reprezint o categorie distinct de implicaii de tipul:

A1 A2 Am => B1 B2 Bn

unde iA i jB sunt perechi de tipul atribut-valoare, asociate ntre ele, cu o frecven mare n baza de date.

Aceste reguli sunt caracterizate de doi parametri, i anume suportul existent n baza de date n privina

asocierii acestor elemente, i gradul de ncredere al regulii.

Un domeniu nrudit este cel al extragerii de episoade frecvente de evenimente o tehnic ce exploreaz secvene de evenimente, avnd ca rezultat episoadele frecvente reprezentate prin mulimi parial

ordonate de evenimente de diverse tipuri.

2. EXTRAGEREA DE REGULI DE ASOCIERE

2.1 Formularea problemei

Regulile de asociere pot fi definite dup cum urmeaz:

Fie I={i1, i2, , im} un numr de simboluri, numite elemente. Fie D o mulime de tranzacii, unde fiecare tranzacie T se constituie ca un subset al lui I, TI. O observaie important, n acest moment, este

aceea c se ia n considerare prezena (reprezentat binar) a elementelor n tranzacie, i nu alte caracteristici

cantitative sau calitative ale acestora. Fiecare tranzacie are asociat un identificator, numit n continuare tid

(transaction identifier).

Definiia 1. Suportul unui subset X al lui I n D, notat cu (X), se calculeaz ca pproporia de tranzacii T din D pentru care XT, deci

(X)=card({TD| XT })/card(D)

Definiia 2. Un set X de elemente din I este denumit frecvent dac suportul lui depete o valoare de prag min_sup, deci

(X)min_sup

Definiia 3. O regul de asociere r: XY

este o implicaie (nu implicaia logic) pentru care XI, YI i XY=.

Definiia 4. Suportul unei reguli de asociere r, notat (r) se calculeaz ca pproporia de tranzacii T din D pentru care XYT, deci

(r)= (XY)

Definiia 5. Coeficientul de ncredere al regulii, notat conf(r) se calculeaz ca pproporia de tranzacii T din D pentru care dac XT atunci i YT (deci XYT), adic probabilitatea condiional ca o

tranzacie s l conin pe Y dac l conine pe X, deci

conf(r)= (X Y)/(X).

Noiunea de suport indic frecvena de apariie a tiparului n D. Coeficientul de ncredere cuantific

tria asocierii ntre elementele regulii.

Cel mai adesea sunt cutate regulile cu suport i grad de ncredere mari (mai mari ca valorile de prag

min_sup i min_conf), acestea fiind denumite i reguli tari; de aceea procesul de descoperire const din doi

pai:

descoperirea seturilor de elemente frecvente, cele ce au suport suficient;

folosirea lor pentru derivarea de reguli tari.

Odat parcurs primul pas, care este costisitor din punct de vedere computaional i al operaiilor de

intrare-ieire, cel de-al doilea se rezolv astfel:

Pentru fiecare set frecvent X i fiecare subset YX se determin parametrii regulii X\YY, pe

considerentul ca mulimea elementelor obinute prin reuniunea prii stngi cu partea dreapt trebuie s se

obin un set frecvent, n cazul nostru X\YY adic X.

Astfel, accentul a fost pus pe gsirea de algoritmi eficieni i scalabili pentru extragerea de seturi

frecvente de elemente.

2.2 Exemplu

Fie elementele {unt, pine, unc, gem, lapte} simbolizate {U, P, S, G, L} i baza de date D de

tranzacii:

id

List de elemente

U P G L

P S L

U P G L

U P S L

U P S G L

P S G

Seturile frecvente pentru min_sup=50% sunt

{P} (X)=100%;

{L}{P L} (X)=83%;

{U} {S} {G} {U P}

{U L}{P S} {P G}

{U P L}

(X)=67%;

{U G} {S L} {G L}

{U P G}{U G L}

{P S L} {P G L}

{U P G L}

(X)=50%.

Seturile frecvente maximale sunt {P S L} i {U P G L}.

Regulile de asociere pentru min_conf=80%

cu conf(r)= 100%

UP UL UP L SP

GP L P U PL U GP

U GL U LP S LP G LU

G LP U GP L G L U P

U P GL U G LP P G LU

cu conf(r)80%

LU PL LU P

Rezultatele obinute se citesc astfel:

U GL cu conf(r)=100% nseamn c cine cumpr unt i gem cumpr ntotdeauna i lapte;

LU P cu conf(r) 80%, nseamn c cine cumpr lapte cumpr n proporie de cel puin 80% i

unt i pine.

2.3 Proprietile seturilor frecvente i ale regulilor de asociere

In cazul seturilor de elemente cele mai importante proprieti sunt urmtoarele:

suportul submulimilor

Dac YX, atunci (Y) (X), deoarece toate tranzaciile din D ce l conin pe X l conin n mod

necesar i pe Y

Superseturile seturilor nefrecvente sunt nefrecvente

Dac setul de elemente X nu are suportul minim necesar pe D, adic (X) < min_sup, orice superset

YX nu va avea suportul minim necesar, deoarece (Y) (X) < min_sup.

Subseturile seturilor frecvente sunt frecvente

Dac setul de elemente Y este frecvent pe D, deci (X) min_sup, orice subset XY va fi i el

frecvent deoarece (X) (X)min_sup.

Pentru regulile de asociere consideraiile urmtoare sunt eseniale:

Regulile nu se compun n antecedent

Dac XZ i YZ nu este neaprat adevrat c XYZ, deoarece reuniunea la nivelul elementelor

nseamn intersecie la nivelul mulimilor de tranzacii ce asigur suportul pentru X i Y, aceasta putnd fi .

Regulile nu se descompun n antecedent

Dac XYZ nu este neaprat adevrat c XZ i YZ, deoarece n acest caz restriciile de suport

rmn valabile dar nu avem controlul restriciilor de grad de ncredere, dat fiind faptul ca suportul pentru X

sau pentru Y poate fi considerabil mai mare dect suportul reuniunii lor, ceea ce micoreaz gradul de

ncredere al noilor reguli.

Regulile se descompun n consecvent

Dac XYZ atunci XY i XZ, deoarece dac XYZ este set frecvent orice subset al lui este

frecvent, iar la nivelul gradului de ncredere numitorul raportului rmne neschimbat dar numitorul crete,

deci regulile au parametri mai buni; totui acest aspect nu este foarte interesant n contextul extragerii de

reguli pentru c se dorete obinerea de reguli din ce n ce mai mari din reguli mici i nu invers.

Regulile nu sunt tranzitive

Dac XY i YZ nu se poate spune c XZ; n primul rnd mulimile ce asigur suportul celor

dou reguli, adic XY i YZ, nu conduc la nici o concluzie n privina lui XZ; de asemenea nu se poate

spune nimic despre gradele de ncredere ale regulilor.

Inferena regulilor

Dac regula (Z-X)X este valabil atunci YX, Y (Z-Y)Y; suportul ambelor reguli este

acelai (Z), gradul de ncredere crete deoarece Z-YZ-X, deci suportul aflat la numitor scade.

De asemenea dac regula X (Z-X) nu este valabil atunci YX, Y, regula Y (Z-Y) nu este

nici ea valabil; suportul ambelor reguli este acelai (Z), gradul de ncredere scade deoarece YX, deci

suportul aflat la numitor crete.

2.4 Legtura dintre descoperirea seturilor frecvente i analiza formal a conceptelor

(lectur opional)

In aceasta seciune se va analiza corelaia dintre extragerea de asociaii i analiza formal a

conceptelor (Formal Concept Analysis n limba englez) introdus de Wille Error! Reference source not found.. Pentru aceasta se vor prezenta cteva elemente din teoria laticilor.

Definiia 6. Tripletul (L, , ), unde L este o mulime nevid, iar i sunt dou operaii binare pe L se numete latice, dac pentru a, b, c L sunt satisfcute urmtoarele axiome:

comutativitate ab = ba i ab = ba;

asociativitate a(bc) =(ab) c i a(bc) = (ab)c;

absorbie a(ab) = a i a(ab) = a;

Definiia 7. O latice (L, , ) se numete complet dac X, XL exist

UXx

x

i IXx

x

Definiia 8. Fie (L1, 1,1) i (L2, 2,2) dou latici. O aplicaie f: L1L2 se numete homomorfism de latice dac pstreaz operaiile, adic:

f(a 1b) = f(a) 2 f(b), a, b L1;

f(a 1b) = f(a) 2 f(b), a, b L1.

Definiia 9. Fie (L1, 1,1) i (L2, 2,2) dou latici. O aplicaie f: L1L2 se numete izomorfism dac exist un homomorfism g: L2L1 astfel nct:

21Lgf =o i 11Lfg =o .

Definiia 10. Fie S o mulime i c: (S) (S) o aplicaie pe mulimea prilor lui S. c se numete operator de nchidere pe S dac pentru X, Y S, c satisface urmtoarele proprieti:

extensie, X c(X);

monotonie, dac XY, atunci c(X) c(Y);

idempoten, c(c(X)) = c(X).

In acest context o submulime X a lui S se numete nchis dac c(X) = X..

Definiia 11. Un context este un triplet (G, M, I), unde G i M sunt mulimi i IGM. Elementele lui G sunt numite obiecte iar cele ale lui M sunt numite atribute. Pentru orice gG i mM se noteaz gIm

relaia dintre g i m adic (g, m) I.

Definiia 12. Fie (G,M,I) un context. Atunci maprile:

s: (G) (M), cu s(X)={mM| gX, gIm} i

t: (M) (G), cu t(Y)={gG| mY, gIm}

definesc o conexiune Galois ntre mulimile prilor lui G respectiv M.

Mulimea s(X) reprezint setul tuturor atributelor comune obiectelor din X iar t(Y) setul tuturor

obiectelor comune atributelor din Y. Se poate demonstra cu uurin c funciile c=s o t i t o s sunt

operatori de nchidere pe mulimea prilor lui M respectiv G.

Definiia 13. Un concept al contextului (G,M,I) este definit ca perechea (X,Y) unde XG i YM pentru care s(X)=Y i t(Y)=X.

Altfel spus, un concept este o pereche de mulimi nchise (X,Y) deoarece X=t(Y)=t(s(X)), t o s fiind

un operator de nchidere. X poart numele de extensiune a conceptului iar Y pe cel de intensiune.

Un concept generat de un singur atribut mM, se determin ca (m) = ( t({m}), c({m}) ) se numete

concept-atribut, n timp ce un concept generat de un obiect gG se determin ca (g) = ( c({g}), s({g}) ) i se

numete concept-obiect.

Mulimea tuturor conceptelor unui context se noteaz cu (G,M,I).

Un concept (X1,Y1) este un subconcept al lui (X2,Y2), notat prin (X1,Y1) (X2,Y2) dac i numai dac

X1 X2, echivalent cu Y2 Y1.

Definiia 14. Un subset P al unui set ordonat Q se numete dens fa de un operator binar , dac qQ, exist ZP, astfel nct q = Z.

Teorema 1 (Teorema fundamental a analizei formale a conceptelor Error! Reference source not found.). Fie (G,M,I) un context; atunci (G,M,I) este o latice complet cu operatorii , calculai astfel:

)),((),( IU j jj jjjj YXcYXV = , respectiv I Uj j jjjjj YcXYX ))(,(),( = .

Reciproc, dac L este o latice complet, L este izomorfic fa de (G,M,I) dac i numai dac exist

maprile :GL i :ML, astfel nct (G) este -dens n L, (M) este -dens n L, i gIm este echivalent

cu (g) (m) pentru orice gG i mM. In particular, L este izomorfic cu (L,L,).

Laticea (G,M,I) este denumit laticea Galois a contextului. O latice de concepte poate fi reprezentat printr-o diagram Hasse, n care fiecare concept este figurat printr-un cerc, iar relaia concept -

subconcept printr-o linie ce unete cele dou cercuri, subconceptul fiind figurat mai jos dect conceptul. In

figura 1 este figurat diagrama Hasse a unei latici Galois. Etichetele asociate conceptelor sunt obiectele, n cazul conceptelor-obiect, atributele, n cazul conceptelor-atribut, n celelalte cazuri reprezentnd diferenele

specifice dintre conceptele subsumate unul altuia.

Figura 1. Exemplificare a laticei Galois a conceptelor.

Conceptele frecvente sunt perechile (X,Y) pentru care card(X)>card(D)*min_sup. Figura 2 reprezint conceptele frecvente din exemplul dat anterior

Figura 2. Conceptele frecvente pentru exemplul dat

({1,2,3,4,5,6}, {P})

({1,2,3,4,5}, {P,L})

({1,3,5,6}, {G,P})

({1,3,4,5},

{U,P,L})

({1,3,5}, {U,P,G,L})

({5}, {U,P,S,G,L})

({2,4,5,6}, {P,S})

({5,6}, {P,S,G}) ({2,4,5}, {P,S,L})

({4,5}, {U,P,S,L})

P

L

U

S

G

5

4

1,

3

6 2

({1,2,3,4,5,6}, {P})

({1,2,3,4,5}, {P,L})

({1,3,5,6}, {G,P})

({1,3,4,5}, {U,P,L})

({1,3,5}, {U,P,G,L})

({2,4,5,6}, {P,S})

({2,4,5}, {P,S,L})

P

L

U

1,3 2

G

S