Avându-şi originea în analiza coşului pieţei, explorarea regulilor de asociere este una dintre principalele aplicaţii ale Data Mining-ului. Popularitatea lor se datorează în mare parte eficienţei prelucrării datelor cu ajutorul algoritmilor, în special prin dezvoltarea algoritmului Apriori.
Dându-se un set de tranzacţii ale clienţilor, scopul regulilor de asociere este de a găsi corelaţii între articolele vândute. Regulile de asociere sunt de tipul “dacă-atunci reguli” cu două măsuri care cuantifică sprijinul şi încrederea regulii pentru un set de date dat. Cea mai mare parte a companiilor au acumulat de la clienţi, de-a lungul timpului, cantităţi mari de date. Cu aplicaţii de comerţ electronic care au crescut repede, companiile au avut o creştere semnificativă de date în doar câteva luni. Data mining are rolul de a descoperi tendinţe, modele, corelaţii, anomalii în aceste baze de date, care ne pot ajuta să luăm decizii corecte pe viitor. Nimeni nu poate garanta că deciziile obţinute vor duce la rezultate corecte. Data mining-ul doar ajută experţii să înţeleagă datele şi să ia decizii corecte. Data mining-ul este o intersecţie între câmpurile bazelor de date, inteligenţă artificială şi statistică. Câteva exemple de aplicaţii care folosesc data mining:
Analiza coşului pieţei (Explorarea asocierilor) - scopul analizei coşului pieţei este de a descoperi relaţii sau corelaţii între mulţimile de articole;
Clasificare - analizează un set de obiecte de antrenament cu etichete cunoscute şi încearcă să formeze un model pentru fiecare clasă, pe baza caracteristicilor datelor;
Regresia - anticipează valorile unor date lipsă sau construieşte un model pentru anumite atribute folosind alte atribute ale datelor;
Analiza seriilor de timp - analizează datele seriilor de timp pentru a găsi anumite regularităţi în date;
Clustering - este folosit pentru a identifica grupuri încapsulate în date. Sarcina lui este de a realiza grupuri astfel încât similarităţile dintre grupuri să fie scăzute şi similarităţile din interiorul grupurilor să fie mari.
Se consideră explorarea asocierilor în baze de date mari ce conţin tranzacţii ale clienţilor. În continuare se va face o prezentare de ansamblu a problemei şi se va explica abordările care au fost folosite pentru a ataca această problemă.
Căutarea asocierilor
Regulile de asociere îşi au originea în analiza coşului pieţei şi au ca obiectiv înţelegerea comportamentului şi intereselor clienţilor în comerţul cu amănuntul. Această înţelegere ajută în gruparea produselor şi în marketingul direct. Clientul are la dispoziţie o mulţime mare de articole pentru a alege diferite coşuri cu produse. Presupunând că numărul de articole este în jur de 10000 şi dacă nu se iau în considerare variaţii de cantităţi ale aceloraşi articole, pentru articole diferite în acelaşi coş de cumpărături se pot forma aproximativ coşuri diferite. În practică, nici un coş nu va conţine foarte multe articole. Chiar dacă vom considera coşuri de cumpărături cu cel mult de 30 de articole fiecare, tot vom avea mai mult de 10100 posibilităţi. Acesta este un exemplu de “blestem al dimensionalităţii”. Orice algoritm data mining va avea de a face într-un fel sau altul cu acest blestem. Regulile de asociere pentru analiza coşului pieţei descoperă modele care apar frecvent în cadrul coşurilor de cumpărături.
Analiza pieţei a fost de asemenea utilizată şi în medicină şi în alte servicii industriale. Mai mult, aplicaţii ale regulilor de asociere sunt folosite mult mai departe decât în analiza coşului pieţei, în detectarea intruşilor în diferite reţele sau în atacuri asupra serverelor web şi folosirea paginilor webserverelor. Regulile de asociere sunt folosite şi de oamenii de ştiinţă în descoperirea secvenţelor ADN şi structurilor de proteine şi în investigarea seriilor de timp.
Două tipuri de modele pot fi găsite în cadrul regulilor de asociere:
Primul tip este “dacă-atunci-reguli” şi este de forma “Dacă un client cumpără lapte atunci el va cumpăra şi pâine.”
Al doilea tip se referă la reuniunea de articole în cadrul unui coş de cumpărături: “Un client cumpără pâine şi lapte împreună.”
Descoperirea celui de al doilea model este mai simplă decât a primului, dar putem observa că la descoperirea primului model ne putem baza pe descoperirea celui de-al doilea. În continuare ne vom concentra pe al doilea tip de model.
Cercetările recente s-au concentrat pe scalarea algoritmilor data mining. Se spune că un algoritm este scalabil dacă timpul său de execuţie creşte linear cu numărul de înregistrări din baza de date. În general, un proces de descoperie a cunoştinţelor constă în parcurgerea următorilor paşi:
Curăţarea datelor, cum sunt zgomotul, datele eronate, datele lipsă sau irelevante;
Integrarea datelor, unde sursele de date sunt integrate într-un întreg;
Selectarea datelor, unde datele relevante sunt selectate din baza de date;
Transformarea datelor, unde datele sunt transformate într-un format apropiat pentru exploatare;
Explorarea datelor, care este procesul esenţial, unde sunt aplicate metode inteligente;
Evaluarea modelului, care identifică modelele folosind măsurători interesante;
Prezentarea cunoştinţelor, unde sunt folosite tehnici de vizualizare pentru a prezenta utilizatorului datele explorate.
Explorarea regulilor de asociere, denumită şi analiza coşului pieţei, este una dintre zonele de aplicaţii ale data mining-ului. Conceptul de explorare a regulilor de asociere a fost prima dată introdus de Agrawal et al. Considerăm o piaţă cu o colecţie mare de tranzacţii ale clienţilor. O regulă de asociere este de tipul X => Y unde X este antecedentul iar Y este consecutivul. X şi Y sunt mulţimi de articole şi o regulă înseamnă că un client care cumpără articolele din mulţimea X o să cumpere şi articolele din mulţimea Y cu o probabilitate %c unde c se numeşte încredere. O regulă poate fi enunţată astfel: “Optzeci de procente din cei care au cumpărat ţigări, au cumpărat şi chibrituri”. O asemenea regulă ne ajută să răspundem la întrebarea “Cu ce se vinde Coca Cola?”, sau dacă suntem interesaţi să verificăm dependenţa dintre două articole A şi B putem găsi reguli care au mulţimea A ca şi consecutiv şi mulţimea B ca şi antecedent.
Scopul este acela de a genera asemenea reguli dându-se o bază de date de tranzacţii ale clienţilor. În general, algoritmii încearcă să optimizeze viteza de execuţie întrucât mărimea bazei de date a tranzacţiilor este foarte mare. Acest tip de informaţie poate fi folosită în design-ul catalogului, structura magazinului, plasarea produselor, obiective de marketing etc. Analiza coşului este legată de aceste informaţii, dar este diferită de sistemul de Management al Relaţiilor cu Clienţii (Customer Relationship Management - CRM) unde scopul este de a găsi dependenţe între datele demografice ale clienţilor (vârstă, starea civilă, sex) şi produse.
Descrierea formală a problemei
Fie I o mulţime de articole. Fiecare i reprezintă un articol al tranzacţiei. D este o mulţime de tranzacţii, unde fiecare tranzacţie T este o mulţime de articole, astfel încât T<=I. Fiecare tranzacţie are un identificator unic TID. O mulţime de elemente care are k articole se numeşte k-mulţime de articole. Fie X şi Y două mulţimi de articole distincte. Suportul mulţimii de articole X este numărul de submulţimi care conţin toate articolele mulţimii X.
Fie |X| numărul de mulţimi de articole care conţin mulţimea X şi |D| numărul tuturor tranzacţiilor, |X,Y| numărul tuturor mulţimilor care conţin elementele mulţimilor X şi Y. Suportul mulţimii X este definit în felul următor:
Regula are suportul s dacă %s al tranzacţiilor din D conţin mulţimile X şi Y împreună.
Frontiera unei mulţimi de articole X constă dintr-un set de identificatori de tranzacţii al tranzacţiilor din baza de date care conţin mulţimea X:
.
Atunci, suportul unei mulţimi de articole X reprezintă numărul de tranzacţii din frontiera lui X:
support(X)=|cover(X)|.
Suportul măsoară cât de comune sunt mulţimile de articole în baza de date iar încrederea măsoară cât de puternică este regula. O regulă se spune că are încrederea c dacă %c al tranzacţiilor care îl conţin pe X îl conţin şi pe Y.
Dându-se o mulţime de tranzacţii D sarcina explorării regulilor de asociere este să găsească reguli astfel încât suportul regulei să fie mai mare decât un suport minim specificat de utilizator, numit minsupp, iar încrederea să fie mai mare decât o încredere minimă specificată de utilizator, denumită minconf. O mulţime de articole se numeşte frecventă dacă suportul ei este mai mare decât minsupp.
Colecţia mulţimilor frecvente de articole din D care au suportul mai mare decât minsupp o vom nota cu F.
F={| support(X) ≥ minsupp}.
Sarcina explorării regulilor de asociere poate fi împărţită în două faze. În prima fază, sunt găsite mulţimile mari de articole folosind minsupp, iar în a doua fază se generează regula folosind minconf.
Colecţia regulilor de asociere frecvente şi de încredere care respectă suportul minsupp şi încrederea minconf o vom nota cu R.
.
Algoritmii care implementează explorarea asocierilor parcurg mulţimea datelor de mai multe ori. Majoritatea algoritmilor găsesc pentru început mulţimile frecvente de articole apoi, în consecinţă, generează regula. Deoarece găsirea mulţimilor frecvente de articole este partea dificilă, cercetările se concentrează pe acest aspect.
Această problemă a fost aprofundată din diferite perspective prin câţiva algoritmi. Agrawal, Imielinski şi Swami definesc conceptul de suport şi încredere şi propun un algoritm care foloseşte o mulţime Y cu un singur articol. Algoritmul face mai multe treceri asupra înregistrărilor bazei de date. La fiecare trecere, suportul fiecărei mulţimi de articole este măsurat. Aceste mulţimi de articole, denumite mulţimi de articole candidat sunt derivate din tuplele bazei de date. Listingul 1 conţine pseudocodul acestui algoritm.
Listingul 1. Găsirea mulţimilor frecvente de articole
procedure LargeItemsets{
let Large set L = ;
let Frontier set F = {};
while (F ){
let Candidate set C = ;
forall database tuple t{
forall itemsets f in F{
if(t contains f){
let Cf = candidate itemsets that are
extensions of f and contained in t;
forall itemsets cf in Cf{
if(CfC)
cf.count++;
else{
cf.count=0;
C=C+cf;
}
}
}
}
}
let F = ;
forall itemsets c in C{
if(count(c)/|D|>minsupp)
L = L+c;
if(c should be used asa frontier in the next pass)
F = F+c;
}
}
}
Agrawal şi Srikant definesc algoritmii Apriori şi AprioriTid în care mulţimea Y poate conţine mai multe articole.
În explorarea asocierilor pot fi folosite şi interogările iceberg. Un mod eficient de a calcula aceste interogările, este dat de Fang. O interogare iceberg reprezintă o funcţie peste un atribut (sau o mulţime de atribute) pentru găsirea valorilor care sunt mai mari decât un prag stabilit. O interogare iceberg se efectuează asupra unei relaţii . Un exemplu de interogare iceberg este următorul:
SELECT t1,t2,...,tk, count(ID) FROM R
GROUP BY t1,t2,...,tk HAVING count(ID)>T
În cazul nostru t1,t2,...,tk corespund articolelor. Se numesc interogări iceberg pentru că datele pe care încercăm să le căutăm sunt mari, ca un iceberg, dar rezultatele pe care încercăm să le obţinem şi care au o valoare mai mare decât un anumit prag, sunt de obicei foarte mici, ca vârful unui iceberg. Tehnicile sunt aplicate dacă rezultatele sunt foarte mici în comparaţie cu întreg set de date.
Toivonen a ales o mostră dintr-o baza de date şi a calculat regulile pe această mostră. Apoi regulile au fost verificate pe întreaga bază de date. În continuare au fost generate mulţimile frecvente de articole care conţin această mostră folosind un prag foarte mic. După găsirea mulţimilor de articole, acestea au fost testate pe întregul set de date şi au fost obţinute rezultatele. Algoritmul de alegere a uuei mostre este dat în listingul 2.
Listingul 2. Algoritmul de alegere a unei mostre
s = Draw a Random Sample from database D;
S = Large_Itemsets in s;
F = Itemsets having support minSupp in S;
Report if Error;
return(F);
Fu şi Kwong nu folosesc constrângeri suport, dar în schimb sunt găsite primele N reguli de asociere. Se foloseşte o restricţie numai pentru numărul de reguli generate. La fiecare pas al algoritmului sunt alese N-cele mai interesante k-mulţimi de articole, apoi primele N mulţimi de articole cu cele mai mari valori suport. În continuare vom trimite aceste posibile mulţimi, care pot forma o mulţime frecventă de articole, în pasul următor al algoritmului. Algoritmul este prezentat în listingul 3. Funcţiile din algoritm sunt următoarele: Find_potential_1_itemset(D,N) caută primele N cele mai interesante 1-mulţimi de articole şi le returnează împreună cu suportul lor. Apoi mulţimile de articole găsite sunt ordonate descrescător după suport. Gen_candidate(Pk) folosesc algoritmul Apiori_Gen pentru a genera candidaţii (k+1)-mulţimi de articole. Find_N_potential_k_intemset(Ck,N,k) caută primele N cele mai interesante k-mulţimi de articole. Reduce(newsupport) reduce valoarea pragului dacă nu sunt destule k-mulţimi de articole.
Listingul 3. Găsirea celor N – cele mai interesante mulţimi de articole
function Itemset_Loop(supportk,lastsupportk,N,Ck,Pk,D){
(P1,support1,lastsupport1)=find_potential_1_itemset(D,N);
C2 = gen_candidate(P1);
for(k=2; k<m; k++){
(Pk,supportk,lastsupportk)=Find_N_potential_k_itemset(Ck,N,k);
if(k<m) Ck+1=Gen_Candidate(Pk); }
Ik = N – most Interesting k-itemsets in Pk;
;
return(I);
}
function Find_N_potential_k_itemset(Ck,N,k){
(Pk,supportk,lastsupportk)=find_potential_k_itemset(Ck,N);
Newsupport = supportk;
for(i=2; ik; i++)
updatedi = FALSE;
for(i=2; ik; i++){
if(i==2){
if(newsupportlastsupporti){
(Pi=find_potential_1_itemsets_with_support(D,newsupport));
if(i<k) Ci+1=gen_candidate(Pi);
if(Ci+1 is updated) updatedi+1=TRUE;
}
}
else{
if((newsupportlastsupporti) || updatedi=TRUE){
(Pi=find_potential_k_itemsets_with_support(Ci,newsupport));
if(i<k) Ci+1=gen_candidate(Pi);
if(Ci+1 is updated) updatedi+1=TRUE;
}
}
if((number of k-items < N)&&(i==k)&&(k==m)){
newsupport=reduce(newsupport);
for(j=2; jk; j++)
updatedj=FALSE;
i=1;
}
}
return(Pk,supportk,lastsupportk);
}
Altă cale de a explora regulile de asociere o reprezintă utilizarea algoritmilor distribuiţi şi paraleli. Presupunem ca DB este o bază de date cu |D| tranzacţii şi este distribuită în n părţi DB1, DB2,..., DBn. Fie Di mărimea partiţiei DBi, X.sup şi X.supi suportul global şi local pentru o mulţime X. O mulţime de articole se spune că este globală mare dacă pentru un suport s dat. Dacă atunci X se numeşte de asemenea globală mare. Mulţimea L conţine toate mulţimile globale mari de articole din DB. Scopul este găsirea mulţimii L. Algoritmi paraleli pentru explorarea regulilor de asociere sunt descrişi de Agrawal şi Shafer.
Cheung et al. implementează un algoritm distribuit pentru explorarea regulilor de asociere. Algoritmul se numeşte FDM (Fast Distribution Mining of association rules) şi este prezentat în listingul 4.
Listingul 4. Algoritmul Fast Distributed Mining of association rules
if(k==1)
Ti(1)=get_local_count(DBi,,1);
else{
}
forall
if(X.supi)
for(j=1; jn; j++)
if(polling_site(X)==Sj)
insert <X,X.supi> into LLi,j(k)
for(j=1; jn; j++) send LLi,j(k) to site Sj
for(j=1; jn; j++){
receive LLi,j(k);
forall XLLi,j(k) {
if()
insert X into LPi(k);
update X.largesites;
}
}
forall
send_polling_request(X);
reply_polling_request(Ti(k));
forall {
receive X.suppj from the sites Sj where SjX.largesites;
;
if(X.sup )
insert X into Gi(k);
}
broadcast Gi(k);
receive Gj from all other sites ;
divide Lk into GLi(k)(i=1,2,…,n)
return (Lk)
Ganti et al. se concentrează pe trei probleme de bază ale data mining-ului. Ei definesc şi oferă biliografie pentru mai mulţi algoritmi care rezolvă probleme de analiză a coşului pieţei, grupare şi clasificare.
Bibliografie
Agrawal, R., Imielinski T.and Swami A. N., Mining Association Rules between Sets of Items in Large Databases, Proceedings of the 1993 ACM SIGMOD Iternational Conference on Management of Data, pg. 207-216, Washington, D.C..
Agrawal, R. and Shafer J., Parallel Mining of Association Rules, IEEE Transactions on Knowledge And Data Engineering, Vol. 8.
Agrawal, R. and Srikant R., Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), Santiago, Chile.
Cheung, D., Han J., Ng V., Fu A. and Fu Y., A Fast Distributed Algorithm for Mining Association Rules, Proceedings of the 1996 International Conference on Parallel and Distributed Information Systems, Miami Beach, Florida, USA.
Fu A., Kwong R. and Tang J., Mining N-most Interesting Itemsets, Proceedings of the 12th International Symposium on Methodologies for Intelligent Systems (ISMIS), Springer-Verlag, LNCS, Charlotte, North Carolina, USA.
Ganti V., Gehrke J. and Ramakrishnan R., Mining Very Large Databases, IEEE Computer, Vol. 32, No. 8, pg. 68-75.
Toivonen H., Sampling Large Databases for Association Rules, Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB
コメント