Home » Blog » Arhiva » Volumul 1 » Numărul 2 » Învățarea automată a regulilor de asociere în mineritul datelor (data mining)

Învățarea automată a regulilor de asociere în mineritul datelor (data mining)

Bentley, Drew (2022), Învățarea automată a regulilor de asociere în mineritul datelor (data mining), Cunoașterea Științifică, 1:2, x-x, Traducere și adaptare independente: Nicolae Sfetcu, https://www.cunoasterea.ro/invatarea-automata-a-regulilor-de-asociere-in-mineritul-datelor-data-mining/

Rezumat

Î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. 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. Din analiza coșului de piață, regulile de asociere sunt folosite astăzi în multe domenii 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.

 

Cuvinte cheie: învățarea automată, reguli de asociere, mineritul datelor, data mining

 

CUNOAȘTEREA ȘTIINȚIFICĂ, Volumul 1, Numărul 2, Decembrie 2022, pp. x-x
ISSN 2821 – 8086, ISSN – L 2821 – 8086
URL: https://www.cunoasterea.ro/invatarea-automata-a-regulilor-de-asociere-in-mineritul-datelor-data-mining/
© 2022 Nicolae Sfetcu. Responsabilitatea conținutului, interpretărilor și opiniilor exprimate revine exclusiv autorilor. Responsabilitatea traducerii revine translatorului. Licența CC BY-NC-SA 4.0

 

Învățarea automată a regulilor de asociere în mineritul datelor (data mining)

Drew Bentley

 

Î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. 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. Din analiza coșului de piață, regulile de asociere sunt folosite astăzi în multe domenii 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 = {i1, i2, …, in} un set de atribute n binare numite itemuri.

Fie D = {t1, t2, …, tm} 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(EX ∩ EY), unde EX și EY 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(EY | EX), probabilitatea de a găsi RHS a regulii în tranzacții cu condiția ca aceste tranzacții să conțină și LHS.

Creștere

Creșterea (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 creșterii 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.

Proces

(Setul de articole frecvente, unde culoarea casetei indică câte tranzacții conțin combinația de articole. Rețineți că nivelurile inferioare ale rețelei pot conține cel mult numărul minim de articole ale părinților lor; de exemplu. {ac} poate avea numai cel mult min(a, c) elemente. Aceasta se numește proprietatea de închidere în jos.)

Regulile de asociere sunt de obicei necesare pentru a satisface un suport minim specificat de utilizator și o încredere minimă specificată de utilizator în același timp. Generarea regulilor de asociere este de obicei împărțită în două etape separate:

  1. Se aplică un prag minim de asistență pentru a găsi toate seturile de articole frecvente dintr-o bază de date.
  2. O constrângere minimă de încredere se aplică acestor seturi frecvente de articole pentru a forma reguli.

În timp ce al doilea pas este simplu, primul pas necesită mai multă atenție.

Găsirea tuturor seturilor de articole frecvente într-o bază de date este dificilă, deoarece presupune căutarea tuturor seturilor de articole posibile (combinații de articole). Setul de seturi de articole posibile este setul de putere peste I și are dimensiunea 2n -1 (excluzând setul gol care nu este un set de articole valid). Deși dimensiunea setului de putere crește exponențial în numărul de elemente n în I, este posibilă căutarea eficientă folosind proprietatea de închidere în jos a suportului (numită și anti-monotonitate) care garantează că pentru un set de articole frecvente, toate subseturile sale sunt de asemenea, frecvente și, prin urmare, pentru un set de articole rar, toate super-seturile sale trebuie să fie, de asemenea, rare. Exploatând această proprietate, algoritmii eficienți (de exemplu, Apriori și Eclat) pot găsi toate seturile de articole frecvente.

Istorie

Conceptul de reguli de asociere a fost popularizat în special datorită articolului din 1993 al lui Agrawal și colab., care a obținut peste 18.000 de citări conform lui Google Scholar, în august 2015, și este, prin urmare, una dintre cele mai citate lucrări din domeniul mineritului de date. Cu toate acestea, este posibil ca ceea ce se numește acum „reguli de asociere” să fie similar cu ceea ce apare în lucrarea din 1966 despre GUHA, o metodă generală de extragere a datelor dezvoltată de Petr Hajek și colab.

O utilizare timpurie (circa 1989) a suportului minim și a încrederii pentru a găsi toate regulile de asociere este cadrul de modelare bazată pe caracteristici, care a găsit toate regulile cu supp(X) și conf(X ⇒ Y) mai mari decât constrângerile definite de utilizator.

Măsuri alternative de interes

Pe lângă încredere, au fost propuse și alte măsuri de interes pentru reguli. Câteva măsuri populare sunt:

  • Toată încrederea
  • Puterea colectivă
  • Convingerea
  • Pârghia
  • Creșterea (numit inițial dobândă)

Mai multe măsuri sunt prezentate și comparate de Tan și colab. și de Hahsler. Căutarea tehnicilor care să modeleze ceea ce a cunoscut utilizatorul (și folosirea acestor modele ca măsuri de interes) este în prezent o tendință de cercetare activă sub numele de „Interesantitate subiectivă”.

Asociații statistice solide

O limitare a abordării standard de a descoperi asocieri este că, prin căutarea unui număr masiv de asocieri posibile pentru a căuta colecții de articole care par a fi asociate, există un risc mare de a găsi multe asocieri false. Acestea sunt colecții de elemente care apar concomitent cu o frecvență neașteptată în date, dar o fac doar întâmplător. De exemplu, să presupunem că luăm în considerare o colecție de 10.000 de articole și căutăm reguli care conțin două articole în partea stângă și 1 articol în partea dreaptă. Există aproximativ 1.000.000.000.000 de astfel de reguli. Dacă aplicăm un test statistic pentru independență cu un nivel de semnificație de 0,05 înseamnă că există doar 5% șanse de a accepta o regulă dacă nu există asociere. Dacă presupunem că nu există asociații, ar trebui să ne așteptăm totuși să găsim 50.000.000.000 de reguli. Descoperirea statistică a asocierilor controlează acest risc, în majoritatea cazurilor reducând riscul de a găsi asocieri false la un nivel de semnificație specificat de utilizator.

Algoritmi

De-a lungul timpului au fost prezentați mulți algoritmi pentru generarea regulilor de asociere.

Unii algoritmi bine cunoscuți sunt Apriori, Eclat și FP-Growth, dar fac doar jumătate din treabă, deoarece sunt algoritmi pentru extragerea de elemente frecvente. Un alt pas trebuie făcut după generarea regulilor din seturile de articole frecvente găsite într-o bază de date.

Algoritmul Apriori

Apriori folosește o strategie de căutare pe lățime mai întâi pentru a număra suportul seturilor de articole și utilizează o funcție de generare a candidatului care exploatează proprietatea de închidere descendentă a suportului.

Algoritmul Eclat

Eclat (alt. ECLAT, înseamnă Equivalence Class Transformation) este un algoritm de căutare în profunzime care utilizează intersecția setată. Este un algoritm natural elegant, potrivit atât pentru execuție secvențială, cât și pentru execuție paralelă, cu proprietăți de îmbunătățire a localizării. A fost introdus pentru prima dată de Zaki, Parthasarathy, Li și Ogihara într-o serie de lucrări scrise în 1997:

  • Mohammed Javeed Zaki, Srinivasan Parthasarathy, M. Ogihara, Wei Li: New Algorithms for Fast Discovery of Association Rules. KDD 1997.
  • Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li: Parallel Algorithms for Discovery of Association Rules. Data Min. Knowl. Discov. 1(4): 343-373 (1997)

Algoritmul de creștere FP

FP înseamnă tipar frecvent (frequent pattern).

În prima trecere, algoritmul contorizează apariția elementelor (perechile atribut-valoare) din setul de date și le stochează în „tabelul antetului”. În a doua trecere, construiește structura arborelui FP prin inserarea instanțelor. Elementele din fiecare instanță trebuie să fie sortate în ordinea descrescătoare a frecvenței lor în setul de date, astfel încât arborele să poată fi procesat rapid. Elementele din fiecare caz care nu îndeplinesc pragul minim de acoperire sunt eliminate. Dacă multe cazuri au cele mai frecvente elemente în comun, arborele FP oferă o compresie ridicată aproape de rădăcina arborelui.

Procesarea recursivă a acestei versiuni comprimate a setului de date principal crește direct seturi mari de articole, în loc să genereze elemente candidate și să le testeze pe întreaga bază de date. Creșterea începe din partea de jos a tabelului antet (având cele mai lungi ramuri), prin găsirea tuturor instanțelor care se potrivesc condiției date. Este creat un nou arbore, cu numărătoare proiectate din arborele inițial corespunzătoare setului de instanțe care sunt condiționate de atribut, fiecare nod primind suma numerelor fii. Creșterea recursivă se încheie atunci când niciun element individual condiționat de atribut nu mai atinge pragul minim de suport, iar procesarea continuă pentru elementele de antet rămase ale arborelui FP original.

Odată ce procesul recursiv s-a încheiat, toate seturile mari de articole cu acoperire minimă au fost găsite și începe crearea regulilor de asociere.

Alți algoritmi

AprioriDP

AprioriDP utilizează programarea dinamică în extragerea frecventă a seturilor de articole. Principiul de funcționare este eliminarea generației candidate, cum ar fi arborele FP, dar stochează numărul de suport într-o structură de date specializată în loc de arbore.

Algoritmul de minerit cu reguli de asociere bazată pe context

CBPNARM (Context Based Association Rule Mining Algorithm) este algoritmul dezvoltat în 2013 pentru a aplica regulile de asociere miniere pe baza contextului. Folosește o variabilă de context pe baza căreia suportul unui set de articole este modificat pe baza căreia regulile sunt în cele din urmă populate în setul de reguli.

Algoritmi bazați pe seturi de noduri

FIN, PrePost și PPV sunt trei algoritmi bazați pe seturi de noduri. Ei folosesc noduri într-un arbore FP de codare pentru a reprezenta seturile de articole și folosesc o strategie de căutare în profunzime pentru a descoperi seturi de articole frecvente folosind „intersecția” seturilor de noduri.

Procedura GUHA ASOC

GUHA este o metodă generală de analiză exploratorie a datelor care are fundamente teoretice în calculul observațional.

Procedura ASSOC este o metodă GUHA care analizează regulile de asociere generalizate folosind operații rapide cu șiruri de biți. Regulile de asociere extrase de această metodă sunt mai generale decât cele produse de Apriori, de exemplu, „articolele” pot fi conectate atât cu conjuncții, cât și cu disjuncții, iar relația dintre antecedent și consecință a regulii nu se limitează la stabilirea unui suport și încredere minime, ca în Apriori: poate fi utilizată o combinație arbitrară de măsuri de interes susținut.

Căutare OPUS

OPUS este un algoritm eficient pentru descoperirea regulilor care, spre deosebire de majoritatea alternativelor, nu necesită constrângeri monotone sau antimonotone, cum ar fi suportul minim. Folosit inițial pentru a găsi reguli pentru un rezultat fix, a fost ulterior extins pentru a găsi reguli cu orice element ca o consecință. Căutarea OPUS este tehnologia de bază în popularul sistem de descoperire a asociației Magnum Opus.

Lore

O poveste faimoasă despre minerit cu reguli de asociere este povestea „berei și scutecului”. Un presupus sondaj privind comportamentul cumpărătorilor din supermarketuri a descoperit că clienții (prezumabil bărbați tineri) care cumpără scutece tind să cumpere și bere. Această anecdotă a devenit populară ca exemplu al modului în care regulile de asociere neașteptate pot fi găsite din datele de zi cu zi. Există opinii diferite cu privire la cât de adevărată este povestea. Daniel Powers spune:

”În 1992, Thomas Blischok, managerul unui grup de consultanță de retail la Teradata, și personalul său au pregătit o analiză a 1,2 milioane de coșuri de piață de la aproximativ 25 de magazine Osco Drug. Au fost dezvoltate interogări de baze de date pentru a identifica afinitățile. Analiza „a descoperit că între orele 17:00 și 19:00 consumatorii cumpărau bere și scutece”. Managerii Osco NU au exploatat relația bere și scutece prin apropierea produselor pe rafturi.”

Alte tipuri de minerit a asocierilor

Reguli de asociere cu relații multiple: Reguli de asociere cu relații multiple (MRAR) este o nouă clasă de reguli de asociere care, spre deosebire de regulile de asociere primitive, simple și chiar multi-relaționale (care sunt de obicei extrase din baze de date multi-relaționale), fiecare element de regulă constă dintr-o entitate dar mai multe relații. Aceste relații indică relații indirecte între entități. Luați în considerare următorul MRAR în care primul element constă din trei relații locuința, vecinătatea și umiditatea: „Cei care locuiesc într-un loc care este în apropierea unui oraș cu tip de climă umedă și, de asemenea, au mai puțin de 20 de ani -> starea lor de sănătate este bună” . Astfel de reguli de asociere pot fi extrase din datele RDBMS sau din datele web semantice.

Regulile de asociere bazate pe context este o formă de regulă de asociere. Regulile de asociere bazate pe context pretind mai multă acuratețe în analizarea regulilor de asociere, luând în considerare o variabilă ascunsă numită variabilă de context care modifică setul final de reguli de asociere în funcție de valoarea variabilelor de context. De exemplu, orientarea coșurilor în analiza coșului de piață reflectă un model ciudat în primele zile ale lunii. Acest lucru se poate datora unui context anormal, adică salariul este luat la începutul lunii.

Învățarea setului de contrast este o formă de învățare asociativă. Cursanții cu set de contrast folosesc reguli care diferă semnificativ în distribuția lor între subseturi.

Învățarea la clasă ponderată este o altă formă de învățare asociativă în care ponderea poate fi atribuită claselor pentru a se concentra pe o anumită problemă de interes pentru consumatorul rezultatelor mineritului de date.

Descoperirea modelelor de ordin înalt facilitează capturarea de modele de ordin înalt (politetice) sau asocieri de evenimente care sunt intrinseci datelor complexe din lumea reală.

Descoperirea modelului K-optimal oferă o alternativă la abordarea standard a învățării regulilor de asociere care necesită ca fiecare model să apară frecvent în date.

Mineritul setului de articole frecvente aproximat este o versiune relaxată a mineritului setului de articole frecvente care permite ca unele dintre elementele din unele rânduri să fie 0.

Taxonomie ierarhică a regulilor de asociere generalizate (ierarhie conceptuală)

Reguli de asociere cantitativă, date categorice și cantitative

Reguli de asociere a datelor cu intervale, de ex. împărțiți vârsta în reguli de asociere maxime cu intervale de 5 ani

Mineritul secvențial al modelelor descoperă subsecvențele care sunt comune pentru mai mult decât secvențele minsup într-o bază de date de secvențe, unde minsup este setat de utilizator. O secvență este o listă ordonată de tranzacții.

Reguli secvențiale care descoperă relațiile dintre articole, luând în considerare ordinea în timp. Se aplică în general pe o bază de date de secvențe. De exemplu, o regulă secvențială găsită în baza de date cu secvențe de tranzacții ale clienților poate fi aceea că clienții care au cumpărat un computer și CD-Rom-uri, au cumpărat ulterior o cameră web, cu o anumită încredere și suport.

Clusteringul subspațial, un tip specific de clustering de date cu dimensiuni înalte, se bazează, în multe variante, și pe proprietatea de închidere descendentă pentru anumite modele de clustering.

Warmr este livrat ca parte a suitei de extragere a datelor ACE. Permite învățarea regulilor de asociere pentru reguli relaționale de ordinul întâi.

Minimizarea așteptată a entropiei flotante descoperă simultan relațiile dintre nodurile (denumite elemente aici) ale unui sistem și, de asemenea, între diferitele stări în care se pot afla nodurile. Teoria leagă asocierile inerente sistemelor, precum creierul, de asocierile prezente în percepție.

Referințe

Hâjek, Petr; Feglar, Tomas; Rauch, Jan; and Coufal, David; The GUHA method, data preprocessing and mining, Database Support for Data Mining Applications, Springer, 2004, ISBN 978-3-540-22479-2

Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). “Chapter 6. Association Analysis: Basic Concepts and Algorithms” (PDF). Introduction to Data Mining. Addison-Wesley. ISBN 0-321-32136-7.

 

Sursa: Drew Bentley, Business Intelligence and Analytics. © 2017 Library Press, Licență CC BY-SA 4.0. Traducere și adaptare: Nicolae Sfetcu

Lasă un răspuns

Adresa ta de email nu va fi publicată.