Învățarea regulilor de asociere în mineritul datelor (Data Mining)

Învățarea regulilor de asociere este o metodă de învățare automată bazată pe reguli pentru a descoperi relații interesante între variabilele din bazele de date mari. Este destinată să identifice reguli puternice descoperite în bazele de date folosind unele măsuri de interes. Pe baza conceptului de reguli puternice, Rakesh Agrawal et al. a introdus reguli de asociere pentru descoperirea regularităților dintre produse în datele tranzacțiilor la scară largă înregistrate de sistemele de puncte de vânzare (POS) din supermarketuri. De exemplu, regula {ceapa, cartofi} ⇒ {burger} din datele de vânzări ale unui supermarket ar indica faptul că, dacă un client cumpără ceapă și cartofi împreună, este probabil să cumpere și carne de hamburger. Astfel de informații pot fi folosite ca bază pentru deciziile cu privire la activitățile de marketing, cum ar fi, de exemplu, prețurile promoționale sau plasările de produse. În plus față de exemplul de mai sus din analiza coșului de piață, regulile de asociere sunt folosite astăzi în multe domeni de aplicații, inclusiv mineritul utilizării web, detectarea intruziunilor, producția continuă și bioinformatica. Spre deosebire de mineritul secvenței, învățarea regulilor de asociere nu ia în considerare, de obicei, ordinea elementelor fie într-o tranzacție, fie între tranzacții.

Definiție

Exemplu de bază de date cu 5 tranzacții și 5 articole
ID tranzacție	lapte	pâine	unt	bere	scutece
1	1	1	0	0	0
2	0	0	1	0	0
3	0	0	0	1	1
4	1	1	1	0	0
5	0	1	0	0	0

Urmând definiția originală a lui Agrawal și colab., problema minării regulilor de asociere este definită astfel:

Fie I = {i₁, i₂, …, i_n}un set de atribute n binare numite itemuri.

Fie D = {t₁, t₂, …, t_m} un set de tranzacții numit bază de date.

Fiecare tranzacție din D are un ID de tranzacție unic și conține un subset de articole din I.

O regulă este definită ca o implicație a formei:

X ⇒ Y

unde X, Y ⊆ I și X ∩ Y = Ø.

Fiecare regulă este compusă din două seturi diferite de elemente, cunoscute și sub denumirea de seturi de itemuri, X și Y, unde X este numit antecedent sau partea stângă (LHS) și Y consecvent sau partea dreaptă (RHS).

Pentru a ilustra conceptele, folosim un mic exemplu din domeniul supermarketurilor. Setul de articole este I = {lapte,pâine,unt,bere,scutece} iar în tabel este prezentată o mică bază de date care conține articolele, unde, în fiecare intrare, valoarea 1 înseamnă prezența articolului în tranzacția corespunzătoare, iar valoarea 0 reprezintă absența unui articol în tranzacția respectivă.

Un exemplu de regulă pentru supermarket ar putea fi {unt, pâine} ⇒ {lapte}, ceea ce înseamnă că, dacă se cumpără unt și pâine, clienții cumpără și lapte.

Notă: acest exemplu este extrem de mic. În aplicațiile practice, o regulă are nevoie de un suport de câteva sute de tranzacții înainte de a putea fi considerată semnificativă din punct de vedere statistic, iar seturile de date conțin adesea mii sau milioane de tranzacții.

Concepte utile

Pentru a selecta reguli interesante din setul tuturor regulilor posibile, se folosesc constrângeri asupra diferitelor măsuri de semnificație și interes. Cele mai cunoscute constrângeri sunt pragurile minime de sprijin și încredere.

Fie X un set de articole, X ⇒ Y o regulă de asociere și T un set de tranzacții ale unei baze de date date.

Suport

Suportul este o indicație a frecvenței cu care setul de articole apare în baza de date.

Valoarea suport a lui X în raport cu T este definită ca proporția de tranzacții din baza de date care conține setul de articole X . În formula: supp(X)/N

În exemplul de bază de date, setul de articole {bere,scutece} are suport, deoarece apare în 20% din toate tranzacțiile (1 din 5 tranzacții). Argumentul supp() este un set de precondiții și, prin urmare, devine mai restrictiv pe măsură ce crește (în loc să fie mai incluziv).

Încredere

Încrederea este un indiciu al cât de des s-a constatat că regula este adevărată.

Valoarea de încredere a unei reguli, X ⇒ Y, în raport cu un set de tranzacții T, este proporția tranzacțiilor care conține X care conține și Y.

Încrederea este definită ca:

conf(X ⇒ Y) = supp(X ∪ Y)/supp(X).

De exemplu, regula {unt,pâine} ⇒ {lapte} are un nivel de încredere de 0,2 > în baza de date, ceea ce înseamnă că pentru 100% dintre tranzacțiile care conțin unt și pâine regula este corectă (100% din cazurile în care un client cumpără unt si paine, cumpără și lapte).

Rețineți că supp( X ∪ Y) înseamnă suportul uniunii elementelor din X și Y. Acest lucru este oarecum confuz, deoarece în mod normal gândim în termeni de probabilități de evenimente și nu de seturi de elemente. Putem rescrie supp(X ∪ Y) ca probabilitate comună P(E_X ∩ E_Y), unde E_X și E_Y sunt evenimentele pentru care o tranzacție conține setul de articole X sau, respectiv, Y.

Astfel, încrederea poate fi interpretată ca o estimare a probabilității condiționate P(E_Y | E_X), probabilitatea de a găsi RHS a regulii în tranzacții cu condiția ca aceste tranzacții să conțină și LHS.

Ridicare

Ridicarea (lift) unei reguli este definită astfel:

lift(X ⇒ Y) = supp(X ∪ Y) / supp(X) × supp(Y)

sau raportul dintre suportul observat și cel așteptat dacă X și Y ar fi independenți.

De exemplu, regula {lapte,pâine} ⇒ {unt} are o creștere de 0,2 / 0,4 × 0,4 = 1,25.

Dacă regula ar avea o creștere de 1, ar implica faptul că probabilitatea de apariție a antecedentului și cea a consecinței sunt independente una de cealaltă. Când două evenimente sunt independente unul de celălalt, nu poate fi luată în considerare nicio regulă care să implice aceste două evenimente.

Dacă creșterea este > 1, asta ne permite să cunoaștem gradul în care aceste două apariții sunt dependente una de cealaltă și face ca acele reguli să fie potențial utile pentru prezicerea consecințelor în seturile de date viitoare.

Valoarea ridicării este că ia în considerare atât încrederea regulii, cât și setul de date general.

Convingere

Convingerea unei reguli este definită ca conv(X ⇒ Y) = (1- supp(Y))/(1 – conf(X ⇒ Y)) .

De exemplu, regula {lapte, pâine} ⇒ {unt} are o convingere de (1 – 0,4)/(1 – 0,5) = 1,2, și poate fi interpretată ca raportul dintre frecvența așteptată pe care X apare fără Y (adică frecvența la care regula face o predicție incorectă) dacă X și Y au fost independenți, împărțit la frecvența observată a predicțiilor incorecte. În acest exemplu, valoarea convingerii de 1,2 arată că regula {lapte, pâine} ⇒ {unt} ar fi incorectă cu 20% mai des (de 1,2 ori mai des) dacă asocierea între X și Y ar fi pur întâmplătoare.